This is the fourth article in a series on Cryptography for the Everyday Developer. Follow along to learn the basics of modern cryptography and encryption.

Modular arithmetic is the foundation for asymmetric cryptography like RSA, elliptic curves, or Diffie-Hellman — all of them rely on the properties of modular arithmetic to guarantee security and secrecy.

Since modular arithmetic is so important to cryptography, it pays to understand how it works. This post will help us along the journey by demystifying modular arithmetic, explaining how it works, and why it matters for cryptography.

Modular Arithmetic

Generally speaking, most cryptosytems are based on sets of numbers that are:

  1. discrete
  2. finite

This sounds very abstract, but simply means working with a countable set of unique numbers or objects — modular arithmetic is a system that allows us to perform computations on such sets of numbers while guaranteeing that the results of any operation stay within the limits of the set.

We intuitively use a modular arithmetic system whenever we tell the time. When using the numbers of a clock as an example, any addition or multiplication operation should result in numbers that stay within the set of twelve.

For example, if it is noon and someone says let’s meet again 20 hours from now, we don’t expect that the time of our meeting will be 32 o’clock (12 + 20). Instead, we know that time wraps around after it reaches 12 hours (or 24 depending on where you live), and that the time when we meet will be 8 AM (because 32 = 12 noon + 12 midnight + 8 = 8AM). Even though the numbers are incremented every hour, we never leave the set of 12 integers that make up our clock. The set is discrete (12 unique hours) and finite (never goes past 12).

The Modulus Operation

The core operation describing a modular arithmetic system is the “modulus operation”.

The modulus operation \( \bmod \) is defined for numbers \(a\), \(r\), and \(m\):

$$ a \equiv r \mod m $$

Where \(r - a\) is divisible by \(m \). \(m\) is called the modulus and \(r\) the remainder. The symbol \(\equiv\) means “congruent” (or “equivalent to”). The value of \(m\) is typically called the “modulus”, and \(r\) the “remainder”.

For example:

  • Let \(a=12\) and \(m=9\), then: \(12 \equiv 3 \mod 9\)
  • Let \(a=37\) and \(m=9\), then: \(34 \equiv 7 \mod 9\)
  • Let \(a=-7\) and \(m=9\), then: \(-7 \equiv 2 \mod 9\)

In each case, we are simply dividing the value \(a\) by the modulus \(m\) to get the remainder \(r\). With larger numbers, we might know the values of the modulus \(m\) and the number \(a\). The question is how can we compute \(r\) when division operations become more complicated? The brute force method would be to see how many times \(m \) fits into \(a\) through division, and then take the remainder to find \(r\).

Although this seems very basic, and is something we have done before in basic math, modular arithmetic has some interesting and surprising properties. Foremost being that the remainder is not unique. The formal definition for modulus states that \( a \equiv r \mod m \) if \(m\) divides \( (r-a) \). An interesting side effect of this is that if we can satisfy this for many different values for \(r \):

  • If \(r\) is a valid remainder
  • Then the value \(r + k \cdot m \) is also a valid remainder for any integer \(k\) because if \(m\) evenly divides \(r-a\) then it also divides multiples of that value.

For example, if \(a = 12 \) and \(m = 9\):

  • \(12 \equiv 3 \mod 9 \) is valid because \(9\) divides \(3-12 = -9\)
  • \(12 \equiv 12 \mod 9 \) is valid because \(9\) divides \(12-12 = 0\)
  • \(12 \equiv 21 \mod 9 \) is valid because \(9\) divides \(21-12 = 9\)
  • \(12 \equiv -6 \mod 9 \) is valid because \(9\) divides \(-6-12 = -18\)
  • \(12 \equiv -15 \mod 9 \) is valid because \(9\) divides \(-15-12 = -27\)

All of these are mathematically correct remainders according to the formal definition!

By convention, we usually agree on the smallest positive integer \(r\) as remainder. This value will be less than \(m-1\).

Equivalence Classes

In the example above, the values for \(r\) are all multiples of \(9\). We can list them out in order as a set.

$$ \{ \ldots, -15, -6, 3, 12, 21, \ldots \} $$

This set forms an “equivalence class”, so called because all members of the class exhibit the same behaviour for operations with modulo \(9\).

We can also list out different equivalent classes for different values. For example, we could use the following set of values that are representative of all integers modulo \(5\).

$$ \begin{aligned} \text{set A} & = \{ \ldots, -10, -5, 0, 5, 10, \ldots \} \cr \text{set B} & = \{ \ldots, -9, -4, 1, 6, 11, \ldots \} \cr \text{set C} & = \{ \ldots, -8, -3, 2, 7, 12, \ldots \} \cr \text{set D} & = \{ \ldots, -7, -2, 3, 8, 13, \ldots \} \cr \text{set E} & = \{ \ldots, -6, -1, 4, 9, 14, \ldots \} \end{aligned} $$

Now if we have a tough problem to solve using modular arithmetic, such as

$$ 13 \cdot 16 - 8 = 208 - 8 = 0 $$

We can substitute any value in the problem with a different member of the equivalency class. For example, we could substitute the value \(13\) with any member of the set \(D\), and so on.

$$ 13 \cdot 16 - 8 = D \cdot B - D = 0 $$

Using the simplest values from the set makes the equation much easier to solve. For example, we can substitute both \(13\) and \(8\) for \(3\), which is the smallest positive integer in the equivalence class \(D\). Similarly, we can substitute \(16\) for \(1\) from the equivalence class \(B\). This gives us the much simpler equation:

$$ 3 \cdot 1 - 3 = 3 - 3 = 0 $$

Real-world applications in RSA

A very typical situation in public key cryptography is computing the modular exponent and the inverse. Both the Diffie–Hellman key exchange and RSA public/private key pairs use modular operations to establish secure TLS connections.

Modular Exponentiation

Modular exponentiation is the remainder when an integer \(b\) (the base) is raised to the power \(e\) (the exponent), and divided by a positive integer \(m\) (the modulus); that is,

$$ c \equiv b^e \mod m $$

To find the solution to this problem, we would do usual arithmetic steps:

  • Raise \(b\) to the power of \(e\)
  • Divide the result by \(m\)
  • Take the remainder

For example, given \(b = 5\), \(e = 3\) and \(m = 13\):

  • \(5^3 \mod 13 = 125 \mod 13\)
  • Dividing \(125\) by \(13\) leaves \(8\), so that
  • \(c = 8\)

There are efficient algorithms for performing these operations, and as numbers get larger, we are free to substitute any other value from the same equivalence class to make our computation more efficient and avoid integer overflow.

Modular Inverse

If you perform modular exponentiation with a negative exponent \(e\), this is called the modular inverse. Unlike modular exponentiation, there is no simple formula to compute the modular inverse. The most common way is with a brute force numerical approach using repeated iterations of the Extended Euclidean Algorithm.

This means that modular inverse is difficult to compute, especially for large integers, while modular exponentiation is efficient to compute. This difference makes modular exponentiation a “one-way” function: it is relatively easy to do, and difficult to undo without knowing additional information.

RSA in Action

RSA relies on the efficiency of exponentiation and the difficulty of calculating the inverse to secure communications. In the RSA, basic encryption is done as:

  • \(\text{ciphertext} = \text{plaintext}^e \mod n\)

And decryption is:

  • \(\text{plaintext} = \text{ciphertext}^d \mod n\)

where \(d\) is the modular inverse of \(e \mod (p-1)\cdot(q-1)\)

Without knowing the values for \(p\) and \(q\), we cannot efficiently calculate the modular inverse. Crucially, RSA keeps one of these values secret (the private key).

To see RSA in action, let’s go through a simplified example of encryption and decryption using small numbers. In real-world cryptography, RSA uses large prime numbers, but the underlying principles remain the same.

Step 1: Choose Prime Numbers

Select two prime numbers, \(p = 3\) and \(q = 11\). Compute their product:

$$ n = p \cdot q = 3 \cdot 11 = 33 $$

This is our modulus \(n\).

Step 2: Compute Euler’s Totient

Euler’s Totient counts the numbers lesser than a number (say \(n\)) that do not share any common positive factor other than \(1\) with \(n\).

Some common properties of totient are:

  • If \(n\) is a prime number, the totient of \(n\) is \(n - 1\) (because all numbers less than \(n\) are co-prime to \(n\)).
  • If \(a\) and \(b\) are co-prime, then the totient of \(a \cdot b\) is the totient of \(a\) times the totient of \(b\)

For the value of \(n\) that we selected, the number is made up of co-prime numbers. Using the properties of the totient, we can express Euler’s totient function (using the symbol \(\varphi\) in a simplified way as:

$$ \varphi(n) = \varphi(p \cdot q) = \varphi(p) \cdot \varphi(q) = (p - 1) \cdot (q - 1) = (3 - 1) \cdot (11 - 1) = 2 \cdot 10 = 20 $$

Step 3: Choose a Public Exponent

We select \(e = 7\) (a small prime).

Step 4: Compute the Private Key

The private key \(d\) is the modular inverse of \(e \mod \varphi(n)\), meaning:

$$ d \cdot e \equiv 1 \mod \varphi(n) $$

Solving for \(d\), we get \(d = 3\) since \(7 \cdot 3 = 21 \equiv 1 \mod 20\).

Step 5: Encrypt a Message

Suppose we want to encrypt the message \(M = 5\). We use the formula:

$$ \begin{aligned} C & = M^e \mod n \cr C & = 5^7 \mod 33 \cr C & = 78125 \mod 33 \cr C & = 14 \end{aligned} $$

The encrypted message is \(14\).

Step 6: Decrypt the Message

To decrypt, we compute:

$$ \begin{aligned} M & = C^d \mod n \cr M & = 14^3 \mod 33 \cr M & = 2744 \mod 33 \cr M & = 5 \end{aligned} $$

We recover the original message \(5\)!

The decryption process relies on the knowledge of the private key \(d\), which is a modular inverse and therefore impossible to practically compute given large enough numbers. Without access to the private key, we cannot compute the inverse.

Conclusion

Modular arithmetic might seem like an abstract mathematical concept, but it’s the backbone of cryptographic implementations. As a software developer working in cryptography, investing time to understand these principles will give you deeper insight into how security systems work and how to implement them correctly and efficiently.