# RSA

RSA is an incredibly useful asymmetric algorithm. It is currently used as the foundation for digital certificates, like the kind that secure financial transactions on the web. There is a new asymmetric algorithm that will likely take its place, but RSA is still important. And it's really easy to understand.

## Inverse functions

If I make up two functions that do the opposite, those functions are called inverses. Say, one function adds 2, and the other subtracts 2. I feed a number into the first function, and then feed the answer into the second. I'll get the original number out.

Adding and subtracting are pretty easy to reverse, but what if I made up a pair of functions that were harder to figure out? If I could do that, I could safely give one function to you, and you would not be able to figure out its inverse. I would keep that one to myself.

What good would that do me? Well, if I had the inverse function, and I didn't share it with anybody else, then I could prove my identity with it. Here's how. You make up a number and run it through the function I gave you. Then I take your answer and run it through my inverse function. I would be able to tell you what your original number was. Nobody else would be able to do that, because nobody else has my inverse function.

The RSA algorithm is a way of generating two functions, one to give away, and an inverse to keep secret. If the inverse is hard to guess, then I can use RSA to prove my identity. The function I give away is called my public key, and the one that I keep is called my private key.

## Exponentiation in a Modulus

The functions I'm going to generate are both exponentiation in a modulus. I'm going to choose a modulus n and two exponents e and d. If I choose them carefully, I can generate two inverse functions:

f(x) = xe (mod n)

f-1(x) = xd (mod n)

So you could plug in a message m to compute a ciphertext c by taking c = f(m). Only I, with my secret inverse function, could compute the original message with m = f-1(c).

So I have to choose e, d, and n such that:

me = c (mod n), and cd = m (mod n)

Or substituting c into the second equation, I get:

(me)d = m (mod n)

Or:

med = m (mod n)

For all values of m less than n.

## Solving for e and d

Let's see if we can find an e and a d such that that is always true. I know that:

1 * m = m (mod n)

So if I can factor out an m and get something that's always 1, I've solved the problem. When I factor out an m, I get:

med-1 * m = m (mod n)

So now the challenge is to choose e and d such that:

med - 1 = 1 (mod n)

That reminds me of Fermat's Little Theorem! So what if n is prime, and e times d is equal to n? Well, that won't work, because the product of two numbers isn't going to be prime.

So what if ed - 1 is simply a multiple of n - 1? In other words, there is a number h that I can multiply by ed - 1 to get n - 1:

ed - 1 = h(n - 1)

Then I would have:

med - 1 = m(n - 1)h = (mn - 1)h = 1h (mod n)

So it would be 1.

Unfortunately, that would not be a good alrogithm. The math works out, but the inverse is too easy to calculate. If I give you e and n, you could use a process called the Extended Euclidean Algorithm to compute d in no time. So we have to keep looking.

## The product of primes

Let's suppose, now, that I chose n not to be prime, but instead to be the product of two primes p and q. How does that change things?

First of all, we examine the original equation:

med - 1 = m (mod n)

In other words, the numbers m^(ed - 1) and m both fall on the same point in the number line n. If n were the product of two numbers p and q, then that means that the number line n is made up of a bunch of shorter number lines of length p. There are q of them. As I walk those shorter number lines, I'll wrap back around. By the time I'm wrapping around the longer number line n, I'll be in sync, so I'll also wrap around the shorter number line p.

That means that in order for two numbers to be equal in mod n, then must also be equal in mod p.

Bt the same logic, they are equal in mod q, so I can write:

med - 1 = m (mod p), and med - 1 = m (mod q)

Now I'm getting somewhere. I can make up a number e, and compute d using the Extended Eclidean Algorithm such that ed - 1 is a multiple of both p - 1 and q - 1. In other words:

ed - 1 = h(p - 1)(q - 1)

I can do this easily, because I know the prime numbers p and q. But you would have a hard time doing this if you only knew their product n. You would have to factor a large number into its two primes, which as far as we can tell is very hard.

## Summary

So that's the RSA algorithm. Find two large primes, p and q. Compute:

n = pq

And then make up an e and use the Extended Euclidean Algorithm to compute d such that:

ed - 1 = h(p - 1)(q - 1)

Give away the public key:

f(x) = xe (mod n)

And keep secret the private key:

f-1(x) = xd (mod n)