Skip main navigation

Hurry, only 3 days left to get one year of Unlimited learning for £249.99 £174.99. New subscribers only. T&Cs apply

Find out more

The maths behind the RSA algorithm

This article looks at the maths behind the trapdoor function at the heart of the RSA algorithm.
A combination lock, set to 000
© University of York

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

© University of York
This article is from the free online

The Mathematics of Cryptography: From Ancient Rome to a Quantum Future

Created by
FutureLearn - Learning For Life

Reach your personal and professional goals

Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.

Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.

Start Learning now