Crypto Math Crash Course: Quotient Rings

In this crash course I will try to explain the fundamentals of some commonly used cryptographic algorithms and the underlying math. I hope that it will be understandable by non-experts and I try to avoid technical proofs and instead explain what happens.

Most cryptographic algorithms can be based on ordinary numbers, but these often cause security flaws since they are ordered. For example the multiplication of two positive numbers will always create a larger number. When trying to brute force break an algorithm this allows the attacker to exclude large parts of the potential search space in advance.

The solution are Quotient Rings. First choose a prime number p. Whenever you make an addition or multiplication the result is divided by p and only the residual is kept. Lets take the p=7 as an example. By repeatedly adding ones in this ring we count

Instead of getting a line of numbers, we now have a closed ring of numbers. There is no start and no end; there is no such thing as a larger number anymore. 3+5 = 1 for example. Obviously we are limited to only six elements as opposed to an infinite amount off natural numbers, but in actual applications large prime numbers are chosen so that this is not an issue.

Rings can be formed from any number, not only primes. But prime rings are special because they have very advantageous mathematical properties. There exists a multiplicative inverse for all elements. That means we can do all divisions within the ring! For p=7 these are 1 / 1 = 1, 1/ 2 = 4 , 1/ 3 = 5, 1/4 = 2, 1/5 = 3 and 1/ 6 = 6 (since for example 3*5 = 1) . We are allowed to calculate additions and multiplications using the ordinary rules well known from the real numbers.
For example (5 * 2 + 4 * 2)/4 = 4/4 = 1 or (5 * 2 + 4 * 2)/4 = (5+4) * 2 / 4 = (5+4) * 2 * 2 = 2 * 4 = 1
This property is crucial for example for the elliptical signature algorithm employed in bitcoin.

But what happens in a non-prime quotient ring (p=6 for example)? There exists an inverse for 1 and 5 only: 1 * 1 = 1 and 5 * 5 = 1 and these numbers are the coprimes to 6 (they do not share a common prime divisor). All other numbers cannot be inverted. Obviously when p is a prime all smaller numbers are automatically coprimes.

For the remaining numbers b it is always possible to find an element k such that b * k = 0, where k is simply k = p / b which is a natural number since p and b share a common prime divisor. But this immediately implies that there cannot exist an inverse to b

In fact looking at the case p=6 we find
2 * 1 = 2, 2 * 2 = 4 , 2 * 3 = 0, 2 * 4 = 2, 2 * 5 = 4
and there is no possible k such that 2 * k = 1.

Summary: Quotient rings can be formed from any number by looking at the residual after division by that number (modulo). For prime numbers there exists an inverse for each element. In that sense they are actually better than the natural numbers in which division can only be done in special cases (for example 3/2 = 1.5 and not an element of the natural numbers anymore, but in the p=7 ideal 3/2 = 3*4 = 5. In both cases 4/2 = 2).
In quotient rings not based on prime numbers there exists an inverse for all numbers coprime to p, but not for the remaining numbers.

Quotient rings might seem incredibly useless, and they typically are in everyday life. But they are the fundamental basis of modern cryptography. Without understanding them and not knowing why 3/2 can be 5 you are in cryptography at the level of a small child that is just learning to count.