When I first started learning cryptography, I had my first a-ha moment when I fu

Question

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?

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.