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.

When I first started learning cryptography, I had my first a-ha moment when I fully appreciated the value of a One Time Pad and XOR and all the functions that attempt to emulate that OTP's randomness (PRP/PRF).

Now that I'm learning about the math behind various lemmas, I see a recurring theme regarding "take the modulo of a number, and then do f()". That is a reoccurring theme that I don't fully appreciate, or understand.

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

share|improve this question
    
I would like to note that moduli are more common in asymmetric cryptography while XOR is more used in symmetric cryptography. –  nightcracker Jun 30 '13 at 21:49
    
@nightcracker Unless you count bitwise modulo's, which are still there but just hidden and implied :p (though I agree with you that symmetric cryptography doesn't need as much number-theoretic baggage - it just needs to be able to throw bits around efficiently) –  Thomas Jun 30 '13 at 22:01
2  
Possible duplicate of or at least related to crypto.stackexchange.com/questions/1441/… –  mikeazo Jun 30 '13 at 23:08
    
@mikeazo: Definitely at least related. I'm still on the fence about the duplication; they are essentially the same question, modulo (pun not intended) the mention of XOR, but asked in rather different ways. In particular, merging the answers wouldn't really work in either direction. –  Ilmari Karonen Jul 1 '13 at 2:46
    
Here is the official take on duplicate questions on this site Where this particular question falls I'm open to whatever is decided. –  makerofthings7 Jul 1 '13 at 3:15
add comment

3 Answers

up vote 6 down vote accepted

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

share|improve this answer
    
In an OTP, XOR was explained to me as having a 50% chance of being 1 or 0, resulting in an output with perfect secrecy (up the the limits of the PRG). Is it true that any modulo done in base 10 has a 10% chance of being a given number? If the answer is yes, then I am totally on board. –  makerofthings7 Jul 3 '13 at 14:21
    
Yes, adding a uniform random number modulo n to any constant number yields a uniform random number. In particular, you can do OTP on a latin alphabet by using the Vignere cipher with a purely random key as long as the message to encrypt. –  minar Jul 3 '13 at 22:01
add comment

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.

share|improve this answer
add comment

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.

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.