First, remember our problem with Diffie-Hellman key exchange - that someone who can control your messages can actually fake them? This can't happen with public-key systems (at least not as easily). Here's why.

Suppose I want to let someone verify I am who I say I am. In a public-key system, I never need to let \(f\) get known, so I encode my signature with \(f\) itself as the exponent!

First, I just turn my signature into a number.

Then I raise it to the power of the secret key \(f\), the inverse of the public key \(e\).

Now anyone in the world can check my signature by raising this version of the signature to the public power \(e\) modulo \(n\).

The reason this works is because \[ef\equiv 1\text{ mod }(\phi(n))\] and \(ef=fe\) in a commutative setting: \[\left(Name^f\right)^e=\left(Name\right)^{ef}\equiv Name^1\equiv Name \text{ mod }(n)\]

Lest you think we are now completely secure, let me warn you about one possible problem. Remember how we said above that it seems not to matter too much what \(e\) is? Well, that is sort of true, and sort of untrue.

Suppose we chose to send a message using the following primes and randomly (?) chosen exponent \(e\). Notice that if \(gcd(e,\phi(pq))\neq 1\), this code wouldn't have worked.

Suppose Alice has sent Bob this message using Bob's impressive RSA key of \[(n,e)=(116555088756283019,52665067560570823)\; .\] Now I will be Eve, trying to snoop. On a hunch (or, as another book puts it, after attending a seminar at a decryption conference), I figure I don't have much to lose, so I'll take \(e\)th powers of the encrypted text.

What's this? Eve barely had to do anything to decrypt this!

This may seem mysterious, but it really is related to something we already used a number of times before. Remember that we could find an inverse for \(a\) modulo \(n\) by just taking powers of \(a\), because \[a^{-1}\equiv a^{\phi(n)-1}\text{ mod }(n)\] Similarly, for any possible message \(m\) and public key \(e\), there will always be some power \(k\) of \(e\) such \[m^{e^k}\equiv m^1\text{ mod }(n)\] which is the same as \[e^k\equiv 1\text{ mod }(\phi(n))\] For this to happen, we would have to coincidentally have that not only \(gcd(e,n)=1\) (which we always pick), but also that \(gcd(e,\phi(n))=1\); but then Euler's theorem says that the order of \(e\) modulo \(\phi(n)\) is a divisor of \(\phi(n)\), so we will sometimes find ones where that order is a small divisor of \(\phi(n)\).

Of course, in real life this would only happen randomly, so you could just protect against it by checking the order of \(e\) modulo \(\phi(n)\). Here's how I created this not-quite-random example!

What was the problem here? The issue is that we had a \(\phi(n)\) such that its group of units had elements of tiny order in its group of units. (Two levels deep here!)

More precisely, we had a \(\phi(n)\) such that \(U_{\phi(n)}\) had elements of very small order in it, so that \[e^{very small order}\equiv 1\text{ mod }(\phi(n))\] was possible. How can we avoid this?

When we found elements of big order (primitive roots, in fact) before, we relied on having the original modulus \(p\) being prime. We did not tell the whole story, but we did do enough of what happens with other moduli to know that we should suspect that having a small number of primes to small powers should let us keep finding elements of big order. (For instance, we saw that \(2^n\) had elements pretty close to being primitive roots.)

And we do know something about \(\phi(n)\). Namely, since \(n=pq\) is the product of two primes, we know that \(\phi(n)=(p-1)(q-1)\) is also the product of two numbers. It would be too much to hope for those to be prime! After all, \(p-1\) and \(q-1\) will both be even, since \(p\) and \(q\) will be odd primes.

However, it's possible to pick \(p\) and \(q\) so that \(p-1=2p'\) and \(q-1=2q'\), where \(p'\) and \(q'\) are both prime. In that case \[\phi(n)=\phi(pq)=\phi(p)\phi(q)=2p'2q'=4p'q'\] so that \(\phi(n)\) at least has order four times a product of (still big) prime numbers.

We will not prove it, but it turns out this is enough to guarantee the existence of elements of orders \(p'-1\) and \(q'-1\) in \(U_{\phi(pq)}\), just like we had elements of order \(p-1\) in \(U_p\). To be precise, we get elements of order \[p'-1 = \frac{p-1}{2}-1\text{ and }q'-1=\frac{q-1}{2}-1\] if \[\frac{p-1}{2}\text{ and }\frac{q-1}{2}\] are both prime. Here is an example of this with very small \(p\) and \(q\).

Going backwards, we are looking for prime numbers \(p',q'\) such that \(2p'+1,2q'+1\) are also prime, and then we use \(p=2p'+1\) and \(q=2q'+1\) in RSA, finding an exponent that has big order in \(U_{\phi(n)}\). In this example, \(p'=5\) and \(q'=3\).

Such primes \(p'\) and \(q'\) are called Germain primes, for French mathematician Sophie Germain – the only female number theorist of note before the twentieth century, and definitely an important figure.