First, remember one problem with Diffie-Hellman key exchange (Section 11.4). 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 \begin{equation*}ef\equiv 1\text{ (mod }\phi(n))\end{equation*} and \(ef=fe\) in a commutative setting: \begin{equation*}\left(Name^f\right)^e=\left(Name\right)^{ef}\equiv Name^1\equiv Name \text{ (mod }n)\end{equation*} Naturally, implementing this is somewhat more complex in real life (e.g. padding is used), but it is one major digital signing method implemented on many secure systems.

Interestingly, this concept also can be used in the opposite way. Suppose that someone sends a message using their public signature as above – a message which later turns out to implicate him or her in illegal activity, a scandal, offensive behavior, etc. The author may wish to repudiate this message, but (at least in principle) the digital signature cannot be repudiated in the same way as other types of messages. (Of course, one can always say that one's private key was stolen, so it's not foolproof!) I am indebted to my colleague, Russ Tuck, for this observation.

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 at all.)

The above cell just does the RSA algorithm for a particular case, verifying it works.

Now suppose Alice has sent Bob this message using Bob's impressive RSA key (above) of \begin{equation*}(n,e)=(116555088756283019,52665067560570823)\; .\end{equation*} Let me impersonate Eve, trying to snoop. On a hunch (or, as [C.1.3] puts it, after attending a seminar at a decryption conference), I figure I don't have much to lose by just trying random arithmetic, so I decide to just keep taking \(e\)th powers of the encrypted text (which was already raised to the \(e\)th power once).

What's this? You should see a meaningful message appear. Eve would barely have to do anything to decrypt this!

This circumstance may seem mysterious, but it really is related to mathematics 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 \begin{equation*}a^{-1}\equiv a^{\phi(n)-1}\text{ (mod }n)\end{equation*} Similarly, for any possible message \(m\) and public key \(e\), there will always be some power \(k\) of \(e\) such \begin{equation*}m^{e^k}\equiv m^1\text{ (mod }n)\end{equation*} which is the same as \begin{equation*}e^k\equiv 1\text{ (mod }\phi(n))\end{equation*}

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\). Then Euler's Theorem 9.2.3 says that the order of \(e\) modulo \(\phi(n)\) is a divisor of \(\phi(n)\), so we will sometimes find \(e\) 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 \begin{equation*}e^{very small order}\equiv 1\text{ (mod }\phi(n))\end{equation*} was possible. How can we avoid this?

When we found elements of big order (primitive roots, for prime modulus) in Chapter 10, 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 \begin{equation*}\phi(n)=\phi(pq)=\phi(p)\phi(q)=2p'2q'=4p'q'\end{equation*} 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 \begin{equation*}p'-1 = \frac{p-1}{2}-1\text{ and }q'-1=\frac{q-1}{2}-1\end{equation*} if \begin{equation*}\frac{p-1}{2}\text{ and }\frac{q-1}{2}\end{equation*} 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.