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 expectedAnother 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)HELLO then becomes YVCCF
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)YVCCF then becomes HELLO again
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)HELLO becomes XCZZU
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 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 * 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)So HELLO becomes QJOOTWe 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 = 5 mod 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 Z28, 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 221
E (4) --> 4⁵ = 140 mod 221
L (11) --> 11⁵ = 163 mod 221
L (11) --> 11⁵ = 163 mod 221
O (14) --> 14⁵ = 131 mod 221So HELLO becomes (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), Z192. 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 xAnd 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 xFinal 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).
