# Why is “mod(n)” so central to most aspects of cryptography?

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?

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

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

-
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

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.

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