RSA Two-Key Encryption

So everything in the last seven posts has lead up to this.
The RSA Encryption Algorithm is a mathematical method of generating two encryption keys. You then encrypt a message with one key, and decrypt it using the other key.
This allows you to keep one key private, and publish the other key to the entire world.

Then there are two ways you can use these keys:

1. You look up the public key of your friend, and encrypt a message using their public key. You have guaranteed that no-one can read the message except your friend.
   
2. You encrypt a message using your private key. Everyone can read it, but no-one else but you could have sent it.

So the same technology can be used to keep secrets, and prove identity. Cool.


So how can you get two keys that encrypt and decrypt like this?
It turns out that it's possible using the simple mathematical fact that it's easy to multiply numbers together, but much harder to break a number down into its factor.

First we need to find two primes (p and q). RSA generates random numbers and uses the Fermat Primality Test to find these primes. Well there's actually more to it than this – RSA doesn't generate the random numbers in a purely random fashion – it does some extra checks to ensure that the resultant keys are hard to factor, but the concept is the same.

Then we multiply the primes together to get a modulo, n. Because we know what the two primes were, it is easy for us to calculate the totient of n $\varphi(n) = (p – 1)(q – 1)$. (There are p – 1 numbers coprime to p, and q – 1 numbers coprime to q. The total number of coprime values are just the multiple of these.)

Then we look (randomly) for a number e that is coprime to $\varphi(n)$. This can be tested by using the Euclidean Algorithm. Once we've found this, the number pair e and n become one of our encryption keys.
If e and n are coprime, we can use the Extended Euclidean Algorithm to find:

$x \cdot e + y \cdot \varphi(n) = gcd(n,e)$

$d \cdot e + y \cdot \varphi(n) = 1$

$d \cdot e = 1 + y \cdot \varphi(n)$

$d \cdot e = 1 \text{ mod } \varphi(n)$

d in this case represents the inverse of e mod $\varphi(n)$.

Why do we do this? Because we already know from the Euler-Fermat Theory, that raising any message m (that is coprime to n) to the power of $\varphi(n)$, we end up at 1.
We could try to factor $\varphi(n) + 1$ into two values $e \times d = \varphi(n)$ so that $(m^{e})^{d} = m^{\varphi(n)+1} = 1 \times m$. But the whole point is that we want to avoid factoring numbers if at all possible.
By finding the multiplicative inverse of e (mod $\varphi(n)$), we are instead using $(m^{e})^{e^{-1}} = m^1 = m$. The only reason this approach works, is because we wrap around every $\varphi(n)$.

Here's an example using the two primes p = 21 and p = 19.

$n = 21 \times 19$

$n = 399$

$\varphi(n) = (p – 1) (q – 1) $

$\varphi(n) = 20 \times 18 $

$\varphi(n) = 180$

I used python to select a random Integer e = 31 that is coprime to 180. (Verified by the Euclidean Algorithm).

Then using the Extended Euclidean Algorithm to find the inverse of 31 mod 180.

q	r	x	y
	180	1	0
	31	0	1
5	25	1 – 5 * 0 = 1	0 – 5* 1 = -5
1	6	0 – 1* 1 = – 1	1 – 1 * – 5 = 6
4	1	1 – 4 * – 1 = 5	-5 – 4 *6 = – 29
4	0

Checking the second last line:

$ 180 \times 5 + 31 \times – 29 = 1$

So:

$31^{-1} = – 29 \text{ mod } 180$

$31^{-1} = 151$

Checking:

$31 \times 151 = 4681 = 26 \times 180 + 1 = 1 \text{ mod } 180$

Finally, lets test this by encoding a message. We have to ensure that the message is in a numerical format, and that it is coprime to n. We'll pretend that we've already converted a message into the number 14 (One of my favourite numbers).

To encode the message, we want to calculate:

$14^{31} \text{ mod } 399$

Sagemath has a power_mod method that efficiently calculates this value as:

power_mod(14,31,399) = 287

This is our encrypted message. To recover the original message we calculate:

$ 287^{151} \text{ mod } 399$

power_mod(287,151,399) = 14.

using only the message and the published key (151, 399).

There's a lot more to the RSA Algorithm that ensures it is secure. For example, we've used a message that is a pretty small value. If all our messages are this small (say the 17 most commonly used letters of the alphabet represented by the numbers 1 to 17), it may be possible to guess the private key. Using a hash ensures that the possible message is spread out across a lot of possibilities. Also, the bigger the primes, the more secure the encryption will be.