RSA encryption exponents are mostly all the same

The big idea of public key cryptography is that it lets you publish an encryption key e without compromising your decryption key d. A somewhat surprising detail of RSA public key cryptography is that in practice e is nearly always the same number, specifically e = 65537. We will review RSA, explain how this default e was chosen, and discuss why this may or may not be a problem.

RSA setup

Here's the setup for RSA encryption in a nutshell.

1. Select two very large prime numbers p and q.
2. Compute n = pq and I(n) = (p - 1)(q - 1).
3. Choose an encryption key e relatively prime to I(n).
4. Calculate the decryption key d such that ed = 1 (mod I(n)).
5. Publish e and n, and keep d, p, and q secret.

The asymmetry in the encryption scheme comes from the fact that the person who knows p and q can compute n, I(n), and d easily, but no one else can find d without factoring n. (Or so it seems.)

The encryption exponent

Here we focus on the third step above. In theory e could be very large, but very often e = 65537. In that case, we don't actually choose e to be relatively prime to I(n). Instead, we pick p and q, and hence n, and usually I(n) will be relatively prime to 65537, but if it's not, we choose p and q again until gcd(65537, I(n)) = 1. Kraft and Washington [1] have this to say about the choice of e:

" surprisingly, e does not have to be large. Sometimes e = 3 has been used, although it is usually recommended that larger values be used. In practice, the most common value is e = 65537, The advantages are that 65537 is a relatively large prime, so it's easier to arrange that gcd(e, I(n)) = 1, and it is one more than a power of 2, so raising a number to the 65537th power consists mostly of squarings "

In short, the customary value of e was chosen for efficiency. Also, there aren't many choices for similar values of e [3].

Heninger and Shacham [2] go into more detail.

The choice e = 65537 = 2¹⁶ + 1 is especially widespread. Of the certificates observed in the UCSD TLS 2 Corpus (which was obtained by surveying frequently-used TLS servers), 99.5% had e = 65537, and all had e at most 32 bits.

So the "most common value" mentioned by Kraft and Washington appears to be used 99.5% of the time.

Is this a problem?

Is it a problem that e is very often the same number? At first glace no. If the number e is going to be public anyway, there doesn't seem to be any harm in selecting it even before you choose p and q.

There may be a problem, however, that the value nearly everyone has chosen is fairly small. In particular, [2] gives an algorithm for recovering private RSA keys when some of the bits are know and the exponent e is small. How would some of the bits be known? If someone has physical access to a computer, they can recover some bits from it's memory.

Related posts

• RSA numbers and factoring
• Why RSA should avoid similar-sized primes

[1] James S. Kraft and Lawrence C. Washington. An Introduction to Number Theory with Cryptography. 2nd edition.

[2] Nadia Heninger and Hovav Shacham. Reconstructing RSA Private Keys from Random Key Bits.

[3] The property that makes e an efficient exponent is that it is a Fermat prime, i.e. it has the form 2^2m + 1 with m = 4. Raising a number to a Fermat number exponent takes n squarings and 1 multiplication. And being prime increases the changes that it will be relatively prime to I(n). Unfortunately 65537 may be the largest Fermat prime. We know for certain it's the largest Fermat prime that can be written in less than a billion digits. So if there are more Fermat primes, they're too large to use.

However, there are smaller Fermat primes than 65537, and in fact the quote from [1] mentions the smallest, 3, has been used in practice. The remaining Fermat primes are 5, 17, and 257. Perhaps these have been used in practice as well, though that may not be a good idea.