What is the importance of Modular arithmetic in cryptography?

Question

Why do we use modular arithmetic so often in Cryptography?

Answer 1

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 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

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).