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.

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.

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) = x^{e} _{(mod n)}

f^{-1}(x) = x^{d} _{(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:

m^{e} = c _{(mod n)}, and c^{d} = m _{(mod n)}

Or substituting **c** into the second equation, I get:

(m^{e})^{d} = m _{(mod n)}

Or:

m^{ed} = m _{(mod n)}

For all values of m less than n.

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:

m^{ed-1} * m = m _{(mod n)}

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

m^{ed - 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:

m^{ed - 1} = m^{(n - 1)h} = (m^{n - 1})^{h} = 1^{h} _{(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.

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:

m^{ed - 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:

m^{ed - 1} = m _{(mod p)}, and m^{ed - 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.

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) = x^{e} _{(mod n)}

And keep secret the private key:

f^{-1}(x) = x^{d} _{(mod n)}