# The elegant maths behind the RSA Encryption

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:

`3^(7–1) = 3⁶ = 729 = 104 * 7 + 1 = 1 (mod 5), as expected`

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

`21⁴ = 38,896 * 5 + 1 = 1 (mod 5)`

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:

H(7) → 7 + 17 = 24 (Y)E(4) → 4 + 17 = 21 (V)L(11) → 11 + 17 = 28 = 2 mod 26 (C)L(11) → 11 + 17 = 28 = 2 mod 26 (C)O(14) → 14 + 17 = 5 mod 26 (F)HELLOthen becomesYVCCF

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:

Y (24) → 24 + 9 = 7 mod 26 (H)

V (21) → 24 + 9 = 7 mod 26 (E)

C (2) → 2 + 9 = 11 (L)

C (2) → 2 + 9 = 11 (L)

F (14) → 5 + 9 = 14 (O)YVCCFthen becomesHELLOagain

**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:

` k’*k = 1 (mod n)`

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:

H(7) --> 7 * 7 = 23 mod 26 (X)E(4) --> 4 * 7 = 2 mod 26 (C)L(11) --> 11 * 7 = 25 mod 26 (Z)L(11) --> 11 * 7 = 25 mod 26 (Z)O(14) --> 14 * 7 = 20 mod 26 (U)HELLObecomesXCZZU

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:

**X** (23) --> 23 * 15 = 7 mod 26 (H)

**C** (2) --> 2 * 15 = 4 mod 26 (E)

**Z** (25) --> 25 * 15 = 11 mod 26 (L)

**Z** (25) --> 25 * 15 = 11 mod 26 (L)

**U** (25) --> 25 * 15 = 11 mod 26 (L)

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 xWe then use the Euclidean algorithm and rewrite the equation with the remainder on one side:26 = 7 * 3 + 5, which can be rewritten as5 = 26 - 7 * 3

7 = 5 + 2, which can be rewritten as2 = 7 - 5

5 = 2 * 2 + 1, which can be rewritten as1 = 5 - 2 * 2We 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 * 7So 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):

H(7) --> 7⁵ = 16 mod 29 (Q)E(4) --> 4⁵ = 9 mod 29 (J)L(11) --> 11⁵ = 14 mod 29 (O)L(11) --> 11⁵ = 14 mod 29 (O)O(14) --> 14⁵ = 19 mod 29 (T)SoHELLObecomesQJOOTWe can use the technique described in the box below to find the modulus of those exponential, for example 11⁵ = 161,051 = 14 mod 29 can also be obtained as follows:11² = 121 =5mod 29

So we can deduce that 11⁴ =5² = 25 mod 29

Finally, to calculate 11⁵ we can multiply 11 (mod 29) and 11⁴ (mod 29), so 11 * 25 = 14 mod 29, as expected.

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

**Q** (16) --> 16¹⁷ = 7 mod 29 (H)

**J** (9) --> 9¹⁷ = 4 mod 29 (E)

**O** (14) --> 14¹⁷ = 11 mod 29 (L)

**O** (14) --> 14¹⁷ = 11 mod 29 (L)

**T** (19) --> 19¹⁷ = 14 mod 29 (O)

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 exponentsFor 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² = 4And 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:

H(7) --> 7⁵ = 11 mod 221E(4) --> 4⁵ = 140 mod 221L(11) --> 11⁵ = 163 mod 221L(11) --> 11⁵ = 163 mod 221O(14) --> 14⁵ = 131 mod 221SoHELLObecomes (11, 140, 163, 163, 131). We keep the numerical values as we don't have matching symbols for values higher than 25 in this case.

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), **Z**192. That multiplicative inverse k’ is equal to 77, because 77 *5 (mod 192) =1 . So I get:

`11 --> 11⁷⁷ (mod 221) = 7 (H)`

140 --> 140⁷⁷ (mod 221) = 4 (E)

163 --> 163⁷⁷ (mod 221) = 11 (L)

163 --> 163⁷⁷ (mod 221) = 11 (L)

131 --> 131⁷⁷ (mod 221) = 14 (O)

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:

`def rsa_cipher(text='HELLO', public_key=[13*17,5]):`

text=text.upper()

k=public_key[1]

pq=public_key[0]

x=[]

for t in text:

m=ord(t)-65

x.append((m**k)%pq)

return x

And to decrypt it:

`def rsa_decipher(nbers_list=[], private_key=[13*17,77):`

x=[]

k=private_key[1]

pq=private_key[0]

for t in nbers_list:

x.append(chr((t**k)%pq+65))

return x

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