Public key cryptography with the RSA algorithm
An introduction to the original mathematics of asymmetric cryptography, February 2018
Last year I spent a few months working on a system which made extensive use of public key cryptography to sign and encrypt messages. It was my job to explain to new starters how the system all fitted together and how cryptography protected the confidentiality and integrity of messages.
At some point I started saying things like, "you can do RSA on the back of a napkin if you use small primes". Which in retrospect is a fairly bold claim (you definitely benefit from using a calculator), but the point I was trying to make is that the maths to generate secure messages is not that complex. You don't have to be a mathematician to understand this stuff.
In an attempt to prove that point and refresh my knowledge I thought I'd write up the method. So I'll step through the RSA algorithm now, creating a public key pair which I'll use to encrypt and decrypt a message. The terminology gets a bit difficult-sounding, but the underlying concepts and mathematical operations are simple enough. I hope to make this as easy to follow as possible.
Step 1: Choose two primes and compute their product
To start with you need two distinct primes, which we'll refer to as
q. In real world applications the primes selected need to be very big for RSA to be secure, but to make it possible to do the maths with mental arithmetic I've chosen very small ones.
p = 3
q = 7
Once you've picked some primes you need to multiply them together. We'll call the product
n = pq
n = 21
Step 2: Compute Euler's totient of
Euler's what? What's a
Euler's totient of
n is the lowest common multiple of
q-1. That number is represented by
To calculate it you multiply
q-1 together and divide by their greatest common divisor, which I'll abbreviate to
gcd. That is the largest number that divides into both.
p-1 = 2
q-1 = 6
gcd(6, 2) = 2
λ(n) = (2 x 6) / 2
λ(n) = 6
Step 3: Find an encryption key
The encryption key needs to be greater than
1 but smaller than the totient,
λ(n). It must not share any factors with
1, which means it must be coprime.
6 in this example, so the encryption key must be a number between
6 which does not share any common factors with
6. There is only one possible encryption key,
e = 5
Checking for common factors is intensive work and in real world applications, where you don't want to wait all day to generate a key, the short cut is to select a prime number which is not a divisor of
λ(n). That gives you a coprime by default. So although
e doesn't technically need to be prime, a prime will almost always be used.
Step 4: Find a decryption key
The decryption key must be the modular multiplicative inverse of
e mod λ(n), which is actually a tricky one to explain, but the maths isn't particularly complex once you know what to do. The idea is to find the value of
(d x e) mod λ(n) = 1
We can substitute the numbers we already know, so it's easier to read.
(d x 5) mod 6 = 1
mod stands for modulo, and refers to the remainder after division. So we're looking for a number where when you multiply it by
5 and then divide it by
6 the remainder is
To calculate this properly you can use the Extended Euclidean Algorithm, but
6 are small enough numbers to work out that
85 fits the bill without getting into that.
d = 85 / 5
d = 17
25 would also fit the bill, but then we'd end up with
d = 5 and
e = 5 which would be a case of accidental symmetric encryption and just be confusing. What's you may not have realised before is that there are a whole load of possible encryption and decryption keys for any value of
n, but that's the way it works.
Step 5: Send secret messages
We now have a public and private key pair,
e to encrypt and
d to decrypt. Let's encrypt something!
e = 5
d = 17
The encryption algorithm is.
m ^ e mod n = c
Let's start with something super small, the number
2 ^ 5 mod 21 = 11
This gives us the ciphertext
c = 11.
Decryption takes place with the same function, but with the private key used as the exponent.
c ^ d mod n = m
This bit is not easy to do in your head, given that
11 ^ 17 = 505447028499293771, so feel free to use a calculator to check the following.
11 ^ 17 mod 21 = 2
And that's it. A public key pair created on the digital equivalent of the back of a napkin.
If you're interested in encrypting a larger message than
2 then have a go. If you try something ambitious then you'll find the system breaks down if your message is larger than the modulus
n = 21. That's a limitation of RSA. In real world applications a message tends to be encrypted with a symmetrical algorithm like AES, and then the sender will encrypt the key for that message using RSA.
Anyway, if you got this far reading this then I hope it's been interesting. If you are baying for more then try Prime Number Hide and Seek: How the RSA Cipher Works by Brian Raiter, it's an absolute gem of a webpage.