The maths behind the RSA algorithm

The RSA public key cryptosystem uses the difficulty of factoring large numbers as the basis of its trapdoor function. Unlike Diffie-Hellman, this system can be used to securely send messages. Let’s see how this works.

The RSA algorithm

Alice thinks up two large prime numbers, call them (p) and (q), but unlike in Diffie-Hellman, she keeps the primes secret. Instead she publishes their product (N=p times q).

She also thinks up a public exponent, (e). For reasons we shall see later, this (e) cannot have any factors in common with either (p-1) or (q-1).

She also secretly finds what’s called a decrypting exponent, (d), which is chosen so that (ed equiv 1 text{ (mod }p-1text{)}) and also (ed equiv 1 text{ (mod }q-1text{)}). Again, we shall see why we need this later.

Bob knows (N) and (e) because Alice published them. He wants to send her a message (m) (which we shall assume has been turned into a number (0<m<N)).

Similar to Diffie-Hellman, Bob calculates (C equiv m^e text{ (mod }Ntext{)}). Bob sends (C) to Alice.

To decrypt, Alice calculates (C^d text{ (mod }Ntext{)}): magically, this is the same value as (m).

Why it works

Given (C equiv m^e text{ (mod }Ntext{)}), the main mystery is why should it be true that (C^d equiv m text{ (mod }Ntext{)}) when (d) is such that (ed equiv 1 text{ (mod }p-1text{)}) and also (ed equiv 1 text{ (mod }q-1text{)})?

Fermat’s Little Theorem

In 1679 Fermat announced his Little Theorem (not to be confused with his Last Theorem which is something completely different!). It says that if an integer (a) is not divisible by (p), a prime, then (a^{p-1} equiv 1 text{(mod }ptext{)}).

There are several neat proofs of this fact (for example, using the notion of a generator modulo (p), which we saw when we looked at Diffie-Hellman). However, it will take us too far afield to include it here.

In the context of RSA, remember that (C equiv m^e text{ (mod }Ntext{)}). Since (p) divides (N), a little bit of thought shows this equation still holds true modulo (p), so rather than reducing things modulo (N) let’s work modulo (p).

Since (d) is such that (ed equiv 1 text{ (mod }p-1text{)}) we can write (ed = 1 + k(p-1)) for some integer (k). Therefore

[begin{split} C^d &equiv (m^e)^d = m^{ed} = m^{1 + k(p-1)} \ &= m times (m^k)^{p-1} equiv m times 1 = m text{ (mod }ptext{)} end{split}]

where we made use of Fermat’s Little Theorem in the penultimate step.

The same statement will also be true modulo (q).

Therefore, since it is true both modulo (p) and modulo (q), it is true modulo (N), and we have shown that raising (C) to the (d)th power modulo (N) reveals the secret message (m), just as we required.

The last piece of the puzzle is for Alice to calculate the decryption exponent (d), knowing the secret primes (p) and (q).