Skip to main content
Logo image

Section 11.6 RSA and (Lack Of) Security

We are now ready to discuss some elementary security issues regarding RSA. Remember, we aren’t learning to be security experts here, and far more powerful techniques are available! But these are some underlying fundamentals.

Sage note 11.6.1. A final reminder to evaluate definitions.

If you’re online, don’t forget to evaluate the commands in the Sage cell below so we can use words as messages instead of just numbers.

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
\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 7 . 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
\begin{equation*} (n,e)=(116555088756283019,52665067560570823)\text{.} \end{equation*}
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
\begin{equation*} a^{-1}\equiv a^{\phi(n)-1}\text{ (mod }n) \end{equation*}
Similarly, for any possible message \(m\) and public key \(e\text{,}\) 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\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
\begin{equation*} e^{very small order}\equiv 1\text{ (mod }\phi(n)) \end{equation*}
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
\begin{equation*} \phi(n)=\phi(pq)=\phi(p)\phi(q)=2p'2q'=4p'q' \end{equation*}
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
\begin{equation*} p'-1 = \frac{p-1}{2}-1\text{ and }q'-1=\frac{q-1}{2}-1 \end{equation*}
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.

Historical remark 11.6.2. Sophie Germain.

Germain was the only female number theorist of note before the twentieth century, and is definitely an important figure. She is most well-known today for proving cases of Fermat’s Last Theorem and (more importantly) developing a general strategy for attacking it for the first time. During Napoleon’s invasion of various German territories, she intervened to ensure Gauss’ safety, as she had corresponded with him under an assumed name for some time on this problem. Her significant work on an early problem in mathematical physics, while eventually winning an award, was largely ignored during her lifetime by the French mathematical establishment.
Research into security of number-theoretic cryptography is ongoing. There are practical points as well; as just one example, one ePrint 8  discovered that 0.2% of a large set of public keys have “secret keys [which] are accessible to anyone who takes the trouble” to try to find them. Other studies have found even more – often because of poor randomness.
Another interesting vulnerability is that there is a significant (in practice, not in theory) chance that two RSA keys will share a (prime) factor. In another study 9  it was found that not only did a nontrivial number of apparently unrelated keys share a factor (enabling their complete factorization), many keys were the same! These would still be hard to factor, but as the authors says, “[g]iven cryptographic key sizes, we would not expect to see devices generate a single duplicated key for the population sizes we examined if the keys were generated with sufficient entropy.” This chapter is just a small taste of issues to consider, and no substitute for having a real security professional!
I am indebted to my colleague, Russ Tuck, for this observation.
eprint.iacr.org/2012/064
factorable.net/weakkeys12.extended.pdf