Picking 'e' for RSA encryption

What is the reason behind picking either $$3$$ or $$2^{16}+1$$ for generating the public key in RSA?

• – forest May 17 at 1:25

The cost of computing $$x^e \bmod n$$, which is the bottleneck in any RSA-based cryptosystem, is $$\lfloor\log_2 e\rfloor$$ squarings and $$H(e) - 1$$ multiplications modulo $$n$$, where $$H$$ is Hamming weight.* Since $$e$$ is required to be coprime with $$\operatorname{lcm}(p - 1, q - 1)$$, the most efficient possible choice is $$e = 3$$.

Originally, the 1977 RSA proposal (which was broken by modern standards in several ways, even ignoring parameter sizes) was to choose $$d$$ at random and derive $$e$$ from it. But there's no security advantage to that, and it's much cheaper to choose $$e$$ to be small.

Historical RSA-based cryptosystems were badly designed and failed to provide meaningful security: if you naively try to encrypt a message $$m$$ like a 256-bit secret key by computing $$m^e \bmod n$$, and $$e = 3$$, and $$\log_2 n > 768$$, then it turns out $$m^e \bmod n$$ is just the integer cube of $$m$$ and an attacker can recover $$m$$ from $$m^3$$ just by computing integer (i.e., real number) cube roots.

So, in an attempt to stem the bleeding of such painfully naive use of RSA like this, people started using bigger exponents like $$F_4 = 2^{16} + 1 = 65537$$, despite the additional cost it imposes.

The sensible thing to do would be to choose $$x$$ at random, use a hash of $$x$$ as a secret key for an authenticated cipher, and transmit $$x^3 \bmod n$$ alongside the ciphertext—we call this RSA-KEM today. But because of the decades of RSA abuse, people developed PTSD about small exponents with RSA, and some still break out in a cold sweat when you mention any exponent smaller than 65537.

* For certain exponents the cost may be a little lower with an appropriate choice of Lucas chain, but when $$H(e) = 2$$ as in $$e = 3$$ or $$e = 2^{16} + 1$$ there's not much improvement to be had over the naive square-and-multiply algorithm.

Rabin-type cryptosystems use modular squaring, or ‘$$e = 2$$’, but they are qualitatively different from RSA-type cryptosystems.

• minor comment: a naive left-to-right square and multiply will costs $H(e)-1$ multiplications. e.g. for e=3, $H(e)=2$ but you you do $b^2*b$ – Ruggero May 17 at 10:20
• @Ruggero One of those two hardest things in computing—naming, cache invalidation, and fenceposts! – Squeamish Ossifrage May 17 at 13:59
• What you mean by ~ squarings "and" H(e)-1? Do you mean that they are two different representations of the 'cost'? – dkssud10 May 19 at 10:20
• $\lfloor\log_2 e\rfloor$ squarings, and $H(e) - 1$ multiplications—squarings are usually slightly cheaper than multiplications, but each one is more or less quadratic in $\log n$. The particular choice of cost model varies depending on whom you talk to; popular choices are the RAM metric, the NAND metric, and the AT or area*time metric, the last of which most closely matches physical reality. On a particular machine one might measure cost in CPU cycles, or in joules. – Squeamish Ossifrage May 19 at 11:42