The Maths Behind RSA

We use RSA every day to secure our online transactions, but how does it work? Let's dive into the mathematical principles behind this widely used encryption algorithm.

21/11/2024 · 8 min read · sapling 🪴

RSA (named after its inventors, Ron Rivest, Adi Shamir, and Leonard Adleman) is one of the most widely used encryption algorithms in the world. It’s used to secure everything from online banking transactions to secure communication between devices. But how does it work? What are the mathematical principles behind it? Let’s dive in.

Historical Context

Asymmetric encryption, also known as public-key cryptography, was a game-changer in the world of cryptography. Before its invention, symmetric encryption was the norm, where both parties shared a secret key to encrypt and decrypt messages.

As the name implies, with asymmetric encryption, we now have two keys: a public and a private one. The public one can be shared with anyone, and the private needs to be kept secret. Let’s take our good old Alice and Bob to illustrate this!

Now, let’s say, we have Charles spying on our two lovers:

Charles will never be able to eavesdrop on Bob and Alice unless he gets access to Alice’s private key. But how is that mathematically possible? Because humans are not clever enough at the moment.

Prime numbers

You are probably used to integers (whole numbers), but did you know some of them are special? The two most basic groups of integers are even (,,,…) and odd (,,,…) numbers. However, some of these numbers are even more special: they cannot be divided into a smaller whole number other than themselves! As small as this detail might seem, this is on what (pretty much) the whole current cryptography system relies on!

Machines are very bad at finding the divisors of a number (humans are even worse). For example, let’s take

We cannot divide and further down, that’s because these are in fact prime numbers. Now let’s say you have two huge prime numbers, like and . Now multiply them together:

That’s quite a big integer! If someone was given the final number and was asked to find the unique solution (the two prime numbers you multiplied together), this would be an impossible task.

Well, in fact here I chose two Fibonacci prime numbers so it would be easier but anyways…

The same goes for a computer, but with even larger numbers.

Modulo

The modulo function also plays an important role in the RSA algorithm. Modulo can be seen as “wrapping around” when a number reaches a certain value (or the remainder of a division). The most common example of this in everyday life is how we use clocks: After 12PM, the clocks “resets” at 1PM and so on at 12AM.

This can be mathematically written as:

We say that ” is congruent to modulo ”, because

Generally speaking,

The RSA Algorithm

The procedure to generate the private (, ) and public (, ) keys is the following:

1. Choose two prime numbers (preferably big ones).
2. Compute .
3. Compute .
   • This value comes from the fact that both and are prime, thus , and
4. Choose the encryption exponent so that it is prime with, and smaller than
5. Compute the decryption exponent , the inverse of modulo ,
   • A quick and easy solution here is to use Euler’s extended algorithm, which we know will work because and is is prime to , which means
   • We then get

The alorithm’s security relies on the following equivalence:

We can now encrypt our message (clear) to (encrypted) with the following formula:

and decrypt to with:

You may now ask: “But these are numbers, I want to encrypt a text message!”. Well, text is just an illusion (on your phone), as its characters are represented as numbers in the underlying system (see UTF-8). We can first transcode our text to numbers:

For simplicity, let’s take each letter’s position in the alphabet, starting from : “I luv u” becomes:

, , , ,

Then we can encrypt each number separately and concatenate them to get our encrypted message.

Let’s encrypt this message by hand !

1. We choose and
2. 
3. 
4. Let’s take
5. We apply Euler’s Extended algorithm for and to find
   1. 
   2. 
   3. 
   4. 
   • is effectively 1, we can find by simplifying the steps backwards:
   1. 
   2. 
   3. 
   • We have , but a modular inverse needs to be positive, so we add :
   • Our keys are: and
6. We can start encrypting!
   1. 
   2. 
   3. 
   4. 

Our encrypted message is

Let’s now check if everything went well by decrypting it:

We did it!

Attack Vectors

The RSA algorithm is not magic, and it can be broken if not implemented correctly. For instance, you may have noticed that the letter “u” has been encoded twice in the sentence, and the output remains the same. Frequency analysis could be used here to guess letters from a longer text. To remedy this, we can use a technique called padding or combine RSA with symmetric encryption, like AES:

Other attack vectors are a bit more complex, like timing attacks or a few others. This is why it is important to use a well-tested library to implement RSA, like OpenSSL.

Data is also often encrypted in blocks, which adds another layer of “security”. This is called block cipher mode of operation.

Proof using Fermat’s little theorem

But who tells us that the RSA algorithm actually works? Let’s prove it!

Fermat’s little theorem states that if is a prime number and is an integer not divisible by , then:

And we want to show that

where with and with .

This basically shows that encrypting and decrypting the same message gives us the original input by first applying the encryption exponent and then the decryption one .

Since , we can rewrite as following:

can be rewritten as :

If isn’t divisible by both and (coprime to ), with Fermat’s little theorem, we know that or

We can then simply replace :

Now, if is divisible by or , this means that:

and likewise for :

The Chinese Remainder Theorem tells us that:

And that’s about it

Conclusion

RSA is a fascinating algorithm that relies on the mathematical properties of prime numbers and modular arithmetic. It’s a great example of how abstract mathematical concepts can be applied to solve real-world problems.

If you’re interested in learning more about RSA, I highly recommend diving into the details of the algorithm and trying to implement it yourself. It’s a great way to deepen your understanding of cryptography and computer science in general.