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.

- Select two very large prime numbers
*p*and*q*. - Compute
*n*=*pq*and φ(*n*) = (*p*– 1)(*q*– 1). - Choose an encryption key
*e*relatively prime to φ(*n*). - Calculate the decryption key
*d*such that*ed*= 1 (mod φ(*n*)). - 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*, φ(*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 φ(*n*). Instead, we pick *p* and *q*, and hence *n*, and usually φ(*n*) will be relatively prime to 65537, but if it’s not, we choose *p* and *q* again until gcd(65537, φ(*n*)) = 1. Kraft and Washington [1] have this to say about the choice of *e*:

… surprisingly,

edoes not have to be large. Sometimese= 3 has been used, although it is usually recommended that larger values be used. In practice, the most common value ise= 65537, The advantages are that 65537 is a relatively large prime, so it’s easier to arrange that gcd(e, φ(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.

Heninger and Shacham [2] go into more detail.

The choice

e= 65537 = 2^{16}+ 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 hadeat 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

[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.