Number Theory: In Context and Interactive

Subsection 11.6.1 Beating the man in the middle

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. I'll just use the first three letters in order to keep the encoding small enough to use small primes.

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

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

The reason this works is because

and \(ef=fe\) in a commutative setting:

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!)

Subsection 11.6.2 A cautionary tale

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 (maybe) chosen exponent \(e\text{.}\) (Notice that if \(\gcd(e,\phi(pq))\neq 1\text{,}\) 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

Let me impersonate Eve, trying to snoop. On a hunch (or, as [E.2.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!

Subsection 11.6.3 The explanation

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\text{,}\) because

Similarly, for any possible message \(m\) and public key \(e\text{,}\) there will always be some power \(k\) of \(e\) such

which is the same as

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\text{.}\) Then Euler's Theorem 9.2.5 says that the order of \(e\) modulo \(\phi(n)\) is a divisor of \(\phi(n)\text{,}\) so we will sometimes find \(e\) where that order is a small divisor of \(\phi(n)\text{.}\)

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)\text{.}\) Here's how I created this not-quite-random example!

What was the problem here? The issue is that we had an \(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 an \(n\) with a \(\phi(n)\) such that \(U_{\phi(n)}\) had elements of very small order in it, so that

was possible. How can we avoid this?

Subsection 11.6.4 A solution

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 choosing \(n\) factoring as a small number of primes to powers should make it easy to find elements of big order in the group of units. (For instance, we saw that \(2^n\) had elements pretty close to being primitive roots.)

And we do know something about \(\phi(n)\text{.}\) 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'\text{,}\) where \(p'\) and \(q'\) are both prime. In that case

so that \(\phi(n)\) at least is 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)}\text{,}\) just like we had elements of order \(p-1\) in \(U_p\text{.}\) To be precise, we get elements of order

if \(\frac{p-1}{2}\) and \(\frac{q-1}{2}\) are both prime. Here is an example of this with very small \(p\) and \(q\text{,}\) where we at least have elements of order four.

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)}\text{.}\) In this example, \(p'=5\) and \(q'=3\text{.}\)

Such primes \(p'\) and \(q'\) are called Germain primes, for French mathematician Sophie Germain. The primes \(p\) and \(q\) are then called safe primes, presumably because they might be ‘safe’ to use under some circumstances.