Oxford Sedleian Professor of Natural Philosophy Jon Keating explains the RSA Cryptography Algorithm. RSA encryption is used everyday to secure information online, but how does it work? And why is it referred to as a type of public key cryptography? Professor Jon Keating worked alongside the UK intelligence agency GCHQ for many years, and therefore knows a thing or two about encrypting secret messages. Here, he explains how the RSA algorithm works in general, and goes through 2 worked examples with small prime numbers.

The algorithm relies on the idea that whilst it is very easy to multiply two prime numbers together, it is extremely difficult to break up a large number (with several hundred digits) back into its prime factors. Using some clever results from Number Theory – including Fermat’s Little Theorem and the Euler Totient Function – the message can be decrypted only if you know the original prime factors. This means advertising the product of the primes, or ‘public key’, enables people to send you a message without compromising the security of the encryption system. Even if the message is intercepted, it can only be decoded with knowledge of the prime factors – and these are incredibly difficult to obtain.