The elegant maths behind the RSA Encryption

Photo by Stefan Steinbauer on Unsplash
Adi Shamir, by Ira Abramov — (Flickr) CC BY-SA 2.0

RSA was named after Rivest, Shamir and Adleman, from the Massachusetts Institute of Technology (MIT). It is an exponential cryptosystem based on concepts from Number Theory: modular arithmetic and Fermat’s Little Theorem. In this article we’ll cover the additive, multiplicative and exponential ciphers and show, with simple examples, what makes RSA so interesting.

But before we move to the above-mentioned ciphers, we need to cover Fermat’s Little Theorem. Pierre de Fermat was a 17th century French mathematician mainly known in popular culture for his Last Theorem, which was proved in the nineties by Andrew Wiles, after centuries of attempts.

One of his other theorems, the so-called ‘Little Theorem’, forms the basis for the exponential ciphers. It says that if p is a prime number and a is greater than zero and is not a multiple of p, the following identity applies:

(if you need a refresher in modular arithmetic, check this page)

Let’s take an example, with p=7 and a=3, we have:

Another example, let’s take p=5 and a=21 and thus:

We’ll see later how this theorem is relevant for exponential ciphers.

Additive ciphers

Additive ciphers, also called Caesar’s ciphers, are very straightforward and use basic modular addition. To simplify let’s use values from 0 to 25 to represent letters and so we’ll be working with addition mod 26. The additive cipher simply transforms a letter by adding a fixed value, k, to it.

For instance, if we use a key k=17, and we match letters to their position in the alphabet (from 0 to 25): H=7, E=4, L=11 and 0=14 we have:

To decipher the message we simply add the additive inverse of 17 (mod 26), which is 9 — as 17 + 9 = 0 (mod 26) — and we get:

Multiplicative ciphers

Multiplicative ciphers use modular multiplication instead of addition. It is a similar process but we need to make sure that our k value (the one we are multiplying each element by) is coprime with n, the total number of elements in our set of symbols. The reason we need k and n to be coprimes is that to decipher a coded message, we need the multiplicative inverse — k’ — of k and this multiplicative inverse will always exist if k and n are coprimes. As a reminder, k’ is the multiplicative inverse modulo n of k if:

Let’s look at an example, if we take the same word (“HELLO”) with the corresponding numerical values: (7, 4, 11, 11, 14), with n=26 (for the 26 letters of the alphabet) and k=7, coprime with 26 we get:

To decipher the message, we need the multiplicative inverse of 7 modulo 26, which is 15, as 15 * 7 = 105 = 1 (mod 26). See in the box below how to find the multiplicative inverse using the Euclidean algorithm.

We can then decipher our “XVZZU” message as follows: XVZZU has numerical values (23, 21, 25, 25, 20) and so:

Finding multiplicative inverses using the Euclidean algorithmWe are looking for k' such that k'*k=1 (mod n), which in our example (with k=7) is k'* 7 = 1 (mod 26). This is equivalent to stating:
7 * k' = 26 * x + 1, for some integer x
We then use the Euclidean algorithm and rewrite the equation with the remainder on one side:26 = 7 * 3 + 5, which can be rewritten as 5 = 26 - 7 * 3
7 = 5 + 2, which can be rewritten as 2 = 7 - 5
5 = 2 * 2 + 1, which can be rewritten as 1 = 5 - 2 * 2
We then extend the Euclidean algorithm, starting from the last equation and replacing 2, 5 and 7 by the equalities above:1 = 5 - 2 * 2
1 = 5 - 2 * (7 - 5) = (-2) * 7 + 3 * 5
1 = (-2) * 7 + 3 * (26 - 3 * 7) = 3 * 26 - 11 * 7
So we end up with the following equation:7 * (-11) = 26 * 3 + 1, in the form 7 * k' = 26 * x + 1 we were looking for.And so k' = (-11) = 15 (mod 26)

Exponential ciphers

After this quick overview of the additive and multiplicative filters, we can now move to the next step, the exponential ciphers and a specific implementation of them, the RSA. Exponential ciphers have the following form:

With:

  • p a prime number,
  • 0 <= k <= p-1 and
  • k coprime with (p-1)

To decipher it we use the multiplicative inverse of k in Z(p-1), k’:

Again, let’s take an example with p=29 for instance and k=5, coprime with (p-1)=28. Again, let’s use HELLO encoded as (7, 4, 11, 11, 14):

To decipher the message “QJOOT”, we use the multiplicative inverse of 5 in Z28, 17 (as 5 * 17 = 1 mod 28)

A 'trick' for dealing with the modulus of big exponentialsThere is a neat property of modulos:
if a = b (mod n) then m*a = m*b (mod n)
And that obviously also works with exponents
For example:
3² (mod 5) = 4
Now, if we want to find the result of 3⁴=81 (mod 5) we can also square the result of 3² (mod 5)
We know that 3⁴ = 81 = 1 (mod 5)
But also, using the result of 3² mod 5 (4), we get: 4² = 16 = 1 (mod 5)
This trick allows us to use repeated squaring to find the modulo of very big exponents. Let's say we want to find the result of 5³⁵ (mod 7).
We would do as follows:
5² (mod 7) = 4
5⁴ (mod 7) = 4²(mod 7) = 2
5⁸ (mod 7) = 2² = 4
5¹⁶ (mod 7) = 4² = 2
5³² (mod 7) = 2² = 4
And as 5³⁵ = 5³² * 5² * 5, we now know that 5³⁵ (mod 7) = 4 * 4 * 5 (mod 7) = 80 (mod 7) = 3 (mod 7)

Why does it work?

To see why exponential ciphers work and how they can be deciphered, we need to refer back to Fermat’s Little Theorem. Our decipher key k’ is the multiplicative inverse of k in Z(p-1) so we know that k’ * k = 1 and thus:

k * k’ = l * (p-1) + 1 (mod p-1), for some integer l, by definition.

Thus when we encipher a message we get x^k and when we decipher it:

But, as we have seen above kk’ = l (p -1) + 1 and thus:

And we know, using Fermat’s Little Theorem, that x^(p-1) = 1 (mod p) so we are left with:

As expected, we get our initial message back.

And finally, the RSA cryptosystem

The RSA cipher is based on the exponential system seen above but with an extra twist. For RSA, we need 2 prime numbers, p and q, and we use their product pq as part of a public key (more on that later). It works as follows:

With p, q prime numbers and k in Z(p-1)(q-1) and coprime with (p-1)(q-1)

To decipher the message we use:

With k’ is the multiplicative inverse of k in Z(p-1)(q-1)

Let’s follow with an example, with p=13 and q=17, we get pq=221. We also need our k, coprime with (p-1)*(q-1)=12*16=192, so for instance k=5. The combination of pq and k is my public key: (221, 5) 😎

Now, I can share this public key with anyone so they can encode a message that only I can decipher. Obviously in real life we would use the product of larger primes (way larger!). 😵

So let’s take an example, let’s say I share my public key (221, 5) with you and you want to send me an encoded message “HELLO”, you would proceed as follows:

I then receive the following message: (11, 140, 163, 163, 131) and will need my secret key to decipher it. My secret key is the multiplicative inverse of k=5 in Z(p-1)(q-1), Z192. That multiplicative inverse k’ is equal to 77, because 77 *5 (mod 192) =1 . So I get:

Even if someone intercepts my public key, (221, 5), they would need to know the two prime factors of 221. Very easy in this case but a lot more complicated when dealing with big numbers, such as 9,995,533,757,761,999 which is the product of 99,959,203 and 99,996,133 (in reality much larger numbers than the one above are used). Have a look at this tool to generate big primes: https://bigprimes.org/

The maths: why RSA works

Let’s look at an intuition of why this works. This is in no way a formal proof, by the way. Remember that x^k is our encrypted message and (x^k)^k’=x^kk’ should decipher it.

k’ is the multiplicative inverse of k in (p-1)(q-1) so kk’=1 mod (p-1)(q-1) and thus:

by definition. This gives us:

Using Fermat’s Little Theorem we know that:

And so:

And by the same logic:

And so:

Is divisible by both p and q, and thus also by pq, as p and q are both primes. This finally gives us the expected result:

A simplistic implementation in Python

Before we finish here is a very simplistic and non-robust implementation in Python, first a function to encrypt a text:

And to decrypt it:

Final note: Euler’s Totient Function

Leonard Euler was a very prolific 18th century Swiss mathematician, known for the Euler identity, considered one of the most emblematic in mathematics. He is also the creator of the Euler’s totient function, also called the phi function. The totient function φ(n) gives the number of integers smaller than n that are coprime to n. So for instance The totient φ(4)=2, as 1 and 3 are coprime to 4. φ(10)=4 as 1,3,7 and 9 are coprime to 10. It turns out that this equation can be used to generalise Fermat’s Little Theorem we saw in at the start of this article in the following way, for n a positive integer and x and n coprime:

We can easily see that Fermat’s version is a special case of this equality when n is prime (as, when p is prime, φ(p)=p-1).

Msc in Mathematics and Statistics, Data Analytics