The idea is to make Diffie-Hellman, which technically only relies upon Fermat's Little Theorem and primes, into a system which involves Euler's Theorem, but not so heavily as to make the computation too expensive. It turns out that the easiest way to do that is to choose a large integer \(n\) with only two prime factors, instead of one large prime \(p\) as we did before. For instance:

Now, exponents here live in the world of \(\phi(n)\). We can easily compute this using our magical formula (so that \(\phi(n)=(p-1)(q-1)\)). So the computations are going to be easy for us.

But they will not be so easy to compute without our magical formula, and to use our magical formula we need to have the prime decomposition of \(n\).

• At least that's what people currently believe; if it isn't true, we are in deep trouble security-wise, as we will see later.

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:

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 the sieve of Eratosthenes 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.

In order to encrypt a message \(x\) via RSA with public key \((n,e)\), you do \[x^e\text{ mod }(n)\; ;\] in order for the owner of the key to decrypt a message \(m\), they do \[m^{e^{-1}}=m^f\text{ mod }(n)\; .\] Since \[ef\equiv 1\text{ mod }(\phi(n))\; ,\] \(ef=k\phi(n)+1\) for some integer \(k\). Hence \[(x^e)^f=x^{ef}=x^{k\phi(n)+1}=(x^{\phi(n)})^k x^1\equiv 1^k x\equiv x\text{ mod }(n)\] and it all works out, we recover the original message.

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 \[ef\equiv 1\text{ mod}(\phi(n))\] for \(f\) without actually knowing what \(\phi(n)\) is!