The idea behind RSA is to make Diffie-Hellman, which relies only upon Theorem 7.5.2 and primes, into a system which involves Euler's Theorem (9.2.3). We want to do so, but not so heavily as to make the computation too expensive. (With the advent of mobile devices, it turns out that this has once again become a big issue, so much so that even RSA or similar methods are being replaced with more sophisticated ones involving things like the Mordell equation, known as elliptic curves.)

It turns out that the easiest way to keep computation easy while sticking with exponentiation is to choose as a modulus a large integer \(n\) with only two prime factors, instead of one large prime \(p\) as we did before. For instance:

Exponents here live in the world of \(\phi(n)\). We can easily compute this using Fact 9.5.2 (so that \(\phi(n)=(p-1)(q-1)\)). So the computations are going to be easy for us, assuming we know \(p\) and \(q\).

But they will not be so easy to compute without that knowledge, for which we need to have the prime decomposition of \(n\). In particular, for reasonably large \(n\), that means \(\phi(n)\) is essentially secret to anyone who isn't tough enough to factor \(n\).

As an example, in the early 1600s, Fermat believed \(2^{32}+1\) was prime. It took until 1732 and the genius of Euler to factor \(2^{32}+1\) as follows, which shows the one hundred sixteenth prime is the smaller of two factors.

Hence \(n=2^{32}+1\) wouldn't have been a bad \(n\) to choose in the early 1700s, since it would take a lot of trial and error to get to the one hundred sixteenth prime!

That's the preliminaries. From now on, we do exactly the same thing as before, choosing an \(e\) coprime to \(\phi(n)\), etc. This time, though, instead of keeping \(e\) secret, we let anybody know it (along with \(n\), which we have to let people know anyway).

Now we have an encryption method where anyone can encrypt. The modulus \(n\) (not written as \(pq\)) and \(e\) are both published, and anyone who wants to send a message of length \(n\) or less just exponentiates. You just have to be sure that \(\phi(n)\) and \(e\) are coprime for it to be defined properly.

And if someone nefarious were to try to decrypt this, they would need access to \(f\) somehow, or something equivalent to it mathematically. That would mean solving \begin{equation*}ef\equiv 1\text{ (mod }\phi(n))\end{equation*} for \(f\) without actually knowing what \(\phi(n)\) is!

Naturally, that is pretty easy to compute in the cases above. But in real life?

The \(n\) in the cell above is the product of two primes – but would you like to try to compute \(\phi(n)\) by hand? Without knowing the actual primes, it could be very difficult to figure out \(\phi(n)\), which you probably need to get \(f\).

Realistic examples have much larger primes than this, say 100 digits. But let's see what would happen next in a ‘real’ example.

Hopefully the randomness of the \(p\) and \(q\) I picked didn't keep \(n\) from being greater than the numerical value of the message.

Now we pick the other piece of our key, \(e\). Believe it or not, it doesn't really seem to matter (though no one has proved this) what \(e\) is; documentation for a widely used RSA implementation says this:

The modulus size will be \(num\) bits, and the public exponent will be \(e\). Key sizes with \(num < 1024\) should be considered insecure. The exponent is an odd number, typically 3, 17 or 65537.

Well, I figure \(17\) is easier to use than \(65537\) but less obvious than \(3\). Let's check that it's coprime to the modulus of the key.

If you get False above (I did once in a while during testing), then just pick a different \(e\). (Only evaluate this cell if you have to!)

Once we have our key, away we go!

Crack that! Who knows what \(\phi(n)\) is?

But if I know it, I can calculate the inverse of \(e\):