What is the importance of Modular arithmetic in cryptography?

Question

Why do we use modular arithmetic so often in Cryptography?

Answer 1

One major reason is that modular arithmetic allows us to easily create groups, rings and fields which are fundamental building blocks of most modern public-key cryptosystems.

For example, Diffie-Hellman uses the multiplicative group of integers modulo a prime $p$. There are other groups which would work (i.e., certain elliptic curves).

Answer 2

A few reasons:

1. As mentioned, modular arithmetic allows groups. See @mikeazo's answer.
2. Cryptography requires hard problems. Some problems become hard with modular arithmetic. For example, logarithms are easy to compute over all integers (and reals), but can become hard to compute when you introduce a modular reduction. Similarly with finding roots.
3. Cryptography is implemented digitally. It is nice if values can't be of arbitrary size. If you work with modular arithmetic, you have guarantees about the largest value you will see and can allocate the correct amount of space to hold values.

Answer 3

Your question first calls for a remark, the XOR itself already is an instance of taking a modulo. Namely, XOR is just another name for addition modulo 2. As a consequence, using modulo n can be seen as a generalization of the XOR to larger sets. A simple example is Caesar's cipher which adds a key modulo 26 (the size of the alphabet).

To come back to the main question "why is mod(n) used so frequently in cryptography?", a first reason is that computing modulo n is a very nice method for working in a set of finite size, while keeping good algerbraic properties. In particular, when working modulo a prime p, you are using the simplest form of finite fields: the Galois field GF(p).

With a composite n, working modulo n gives less structure, Z/nZ is not a field, just a ring. However, it remains usable. Of course, when n is large and a product of two primes, working modulo n leads to RSA. (This is an additional reason, historical this time, for the ubiquitous presence of moduli in cryptography.)

Answer 4

Theoretically speaking, modular arithmetic is not anyhow special. Any crypto-system that uses modular arithmetic can be constructed in an analogous way with a group having certain properties under associated group operations. What works in favor of modular arithmetic is the implementation. Modular arithmetic is very well understood in terms of algorithms for various basic operations. That is one of the reason why we use finite fields (AES) in symmetric key cryptography.

Stressing on the point already raised and naively yet broadly speaking, there are many problems which are very easy when asked in the rational field, but they seem infeasible to perform when done on finite field and become easy when some trapdoor is given. For example, performing square-roots, finding logarithm to any base, representing any rational number in form of $pq^{-1}$, fractional knapsack problem is simple on rational field; however, the associated problems, of finding square root, finding discrete logarithm, finding factors, $0/1$ knapsack problem are widely considered to be hard on finite field without a trapdoor but are easy when given some additional information. This additional information acts as the private key. This additional properties helps in construction of public-key cryptosystems.

Note that this hardness is not restricted to just the above. For example, solving a linear programming is in $\mathsf{P}$ while solving the associated integer programming is $\mathsf{NP}$-hard (knapsack is an example). Somehow, nature has this rule that easy problems in a rational field become hard problems in a finite field.

Answer 5

What is consistent, special or useful about mod(n) that makes it so consistently used by cryptographers such as XOR is?

The operation's result is finite - you're working in a field/ring with it. Now there are various ways to work in fields and rings, but moduli are easy to understand and analyze and come pre-shipped with algebraic operations.

Answer 6

The answer is: cryptographers use different finite constructions and make use of the different properties.

In computer science you almost always consider finite sets implicitly: Integers are defined with certain ranges, depending on their bitsize. Arrays have a maximum length when you limit the index to such a limited integer, etc. The only "unlimited" set is strings (if there is no max length), but you don't use strings to use calculate something.

So, almost anything we do happens on finite sets. If we do bitwise XOR, we can interpret bit-arrays as a vectors over $\mathbb{F}_2$ and XOR becomes a vector addition. As you can see, the arithmetics in finite constructions are always there, but they are not mentioned explicitly. It is already clear from "this is an integer".

In symmetric crypto, most of the time the usual calculations on "normal" integers are used. But since most of the systems use different integer sizes in their algorithms, the bitsizes are also given explicity, e.g. "Take the input of 256 bit and split it into 16 blocks of 16 bit - and then do something, do something else and then put them back together."

In public key crypto, this is done for a different reason: There are different properties in different constructions, which are used to build public key schemes. Based on the construction we can use different assumptions about computational hardness, e.g. DLOG, RSA, DRCA, etc. These assumptions enable the construction of oneway-trapdoor functions, which are used to build public key cryptosystems. Their entire hardness depends fundamentally on the underlying construction, and therefore it is required to define them explicitly.