14
$\begingroup$

Why do we use modular arithmetic so often in Cryptography?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mikeazo Dec 12 '11 at 14:09
  • $\begingroup$ @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 :-) $\endgroup$ – Paŭlo Ebermann Dec 12 '11 at 19:10
  • 1
    $\begingroup$ 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. $\endgroup$ – user46 Dec 13 '11 at 9:42
  • $\begingroup$ RC4 uses a mod of 256 which is done to ensure outputs are a byte (similar to #3 in PulpSpy's answer) $\endgroup$ – mikeazo Dec 13 '11 at 17:52
  • 1
    $\begingroup$ I would like to note that moduli are more common in asymmetric cryptography while XOR is more used in symmetric cryptography. $\endgroup$ – orlp Jun 30 '13 at 21:49
10
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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.
$\endgroup$
9
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – goodguys_activate Jul 3 '13 at 14:21
  • $\begingroup$ 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. $\endgroup$ – minar Jul 3 '13 at 22:01
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Paŭlo Ebermann Dec 13 '11 at 19:05
  • $\begingroup$ 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. $\endgroup$ – Jalaj Dec 13 '11 at 19:22
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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