Impacts of not using RSA exponent of 65537

Question

This RFC says the RSA Exponent should be 65537. Why is that number recommended and what are the theoretical and practical impacts & risks of making that number higher or lower?

What are the impacts of making that value a non-Fermat number, or simply non prime?

Answer 1

Using $e\ne65537$ would reduce compatibility with existing hardware or software, and break conformance to some standards or prescriptions of security authorities. Any higher $e$ would make the public RSA operation (used for encryption, or signature verification) slower. Some lower $e$, in particular $e=3$, would make that operation appreciably faster (up to 8.5 times). If using a proper padding scheme, the choice of $e$ is not known to make a security difference; but for many less than perfect padding schemes that have been (or are still) used, high values of $e$ (compared to the number of bits in the public modulus $n$) are generally safer.

---

$e=65537$ is a common compromise between being high, and increasing the cost of raising to the $e$-th power: any higher odd $e$ cost at least one more multiplication (or squaring), which is true for odd exponents of the form $2^k+1$. Also, $e=65537$ is prime, which slightly simplify generating a prime $p$ suitable as RSA modulus, implying $\gcd(p-1,e)=1$, which reduce to $p\not\equiv 1\pmod e$ for prime $e$. Only the Fermat primes $3,5,17,257,65537$ have both properties, and all are common choices of $e$. It is conjectured that there are no other Fermat prime; and if there was any, it would we unusably huge.

Using $e=65537$ (or higher) in RSA is an extra precaution against a variety of attacks that are possible when bad message padding is used; these attacks tend to be more likely or devastating with much smaller $e$. Using $e=3$ would otherwise be attractive, since raising to the power $e=3$ cost 1 squaring and 1 multiplication, to be compared to 16 squaring and 1 multiplication when raising to the power $e=65537=2^{16}+1$.

For example, RSA with $e=65537$ has a security advantage over $e=3$ when:

1. Sending a message naively encrypted as $\mathtt{ciphertext}=\mathtt{plaintext}^e\bmod n$; the greater $e$ makes it more likely that $\log_2(\mathtt{plaintext})\gg \log_2(n)/e$ (which is necessary for security).
2. Sending the same message encrypted to $k$ recipients using the same padding (including any deterministic padding independent of $n$); the greater $e$ makes it less likely that $k\ge e$ (which allows a break).
3. Signing messages chosen by the adversary with a bad signature scheme. For example, with the scheme of the (withdrawn) ISO/IEC 9796 standard (described in HAC section 11.3.5), the adversary could obtain a forged signature from only 1 legitimate signature if $e=3$, but needs 3 legitimate signatures for $e=65537$; trust me on that one. The security advantage of $e=65537$ is wider for attacks against scheme 1 of the (current) ISO/IEC 9796-2.

For more explanations and examples of the risk of the combination of questionable message padding and low $e$, see section 4 in Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem.

---

There is no known technical imperative not to use $e=3$ when using a sound message padding scheme, such as RSAES-OAEP or RSASSA-PSS from PKCS#1, or scheme 2 or 3 from ISO/IEC 9796-2. However, it still makes sense to use $e=65537$:

• The only known drawbacks are the performance loss (by a factor like 8), and the risk of leaving a bug in the key generator when a prime $p\equiv 1\pmod{65537}$ is hit; and when performance matters, there is an even better choice than $e=3$, with provable security (but more complex and uncommon).
• Some attacks on less than perfect RSA schemes that are (or have been) in wide use are significantly harder than with $e=3$ (as discussed above).
• $e=65537$ has become an industry standard (I have yet to find any RSA hardware of software that does not allow it), and is prescribed by some certification authorities.

Answer 2

65537 is commonly used as a public exponent in the RSA cryptosystem. This value is seen as a wise compromise, since it is famously known to be prime, large enough to avoid the attacks to which small exponents make RSA vulnerable, and can be computed extremely quickly on binary computers, which often support shift and increment instructions. Exponents in any base can be represented as shifts to the left in a base positional notation system, and so in binary the result is doubling - 65537 is the result of incrementing shifting 1 left by 16 places, and 16 is itself obtainable without loading a value into the register (which can be expensive when register contents approaches 64 bit), but zero and one can be derived more 'cheaply'. -wikipedia ('twas lazy)

-thus, lower is vulnerable to quick factoring, higher is not insecure, but computationally more expensive.

Answer 3

e=2^16+1 is a good compromise between security and performance. It is small enough, and with low hamming weight, to provide good performance, and not too small, to be safe enough. Explanation: In general, a smaller exponent with lower hamming weight (fewer '1' bits) provide better performance for the calculation of the modular exponentiation. However, e=3 is too small and generates a security risks. e=2^16+1 has only two '1' bits, so low hamming weight, and its value is large enough to guarantee adequate security. Due to this property, a lot of industrial IP, both HW and SW, assume this constant as exponent. Using a larger exponent will not decrease security, but will be more time / power consuming.