Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Why do we use modular arithmetic so often in Cryptography?

share|improve this question
    
I added the public-key tag to your question as I think it is more applicable to the question. I was tempted to remove the "symmetric" tag as I believe that very few (if any) symmetric ciphers use modular arithmetic. Someone correct me if I am wrong though. –  mikeazo Dec 12 '11 at 14:09
    
@mikeazo: One could say that all ciphers can be defined in terms of bits, i.e. they use mod-2-arithmetic. But I suppose this is not what you mean :-) –  Paŭlo Ebermann Dec 12 '11 at 19:10
1  
I'd add that the Rijndael S-Box is designed to be the set of multiplicative inverses under a finite field $GF(2^8)$ - so whilst modular arithmetic is not strictly necessary for a symmetric cipher it certainly does find use in them. –  Ninefingers Dec 13 '11 at 9:42
    
RC4 uses a mod of 256 which is done to ensure outputs are a byte (similar to #3 in PulpSpy's answer) –  mikeazo Dec 13 '11 at 17:52
    
@Ninefingers Note that $GF(2^8)$ is not the same as $\mathbb Z/2^8\mathbb Z$ (integers modulo $2^8$): It has both different addition ($\oplus$ (XOR) instead of +) and multiplication (e.g. polynomial multiplication modulo some reduction polynomial - in Rijndael's reference implementation this is implemented by a log-table and addition). (Does it show that I just did read the Rijndael-book?) –  Paŭlo Ebermann Dec 13 '11 at 18:35
add comment

3 Answers

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.

share|improve this answer
    
Just a note: AES doesn't use any modular fields (other than $GF(2)$, if one wants to be exact), but uses $GF(2^8)$ (for SubBytes) and $GF(2^{32}) = GF((2^8)^4)$ (for the MixColumns step). These fields are quite different to the (same-size) modular rings modulo $2^8$ and $2^{32}$ (they aren't even fields). –  Paŭlo Ebermann Dec 13 '11 at 19:05
    
I completely agree with you. Thanks for the comment. I tried to answer the question to give a broad overall picture. I decided to keep the technical details to minimum to restrain myself from digressing a bit. From next time, I will be more careful. –  Jalaj Dec 13 '11 at 19:22
add comment

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.
share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.