79
$\begingroup$

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?

$\endgroup$

3 Answers 3

74
$\begingroup$

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.
$\endgroup$
6
  • $\begingroup$ Related: Fermat Primes on Wikipedia $\endgroup$ Jul 1, 2012 at 13:07
  • $\begingroup$ @fgrieu, Can you please elaborate on weaknesses of using low e (like e=3) with signing? For example, if the same plaintext is signed with different private keys, would choosing e=3 for the corresponding pubkeys make the system less secure? Signing doesn't use randomized padding. (But then it doesn't use e directly either, and yet of course it's still part of the cryptosystem, so it's better to ask a "dumb" question than miss non-obvious connection.) Thanks. $\endgroup$
    – pfalcon
    Oct 15, 2016 at 4:28
  • $\begingroup$ Simple suggestion (please review what I say before you include it) is that a larger e also means a smaller d, and vice-versa. Thus, if I opt to use e=3, I'll make the job much harder for the person who is decrypting. On the other hand, if I use a larger e, it means that the decrypting party will get to use a smaller d. e~=65k seems to be a nice compromise considering how big lcm(p-1,q-1) is. See: crypto.stackexchange.com/questions/777/… $\endgroup$
    – mmdts
    Oct 9, 2019 at 0:20
  • 3
    $\begingroup$ @mmdts ‘a larger e also means a smaller d’—This is not true. There's only a very low probability that large $e$ leads to small $d$. The converse is true: a small $d$ leads to a large $e$, and small $d$ may be tempting for performance reasons (by a foolish designer who doesn't bother to consult the literature). So large $e$ is evidence of small $d$ in an unknown system designed by foolish humans, but a system that chooses large $e$ and then derives $d$ from it does not lead to small $d$ except with low probability. $\endgroup$ Nov 14, 2019 at 15:11
  • 1
    $\begingroup$ @FERcsI: if we want to keep $e=65537$ for maximum compatibility, we need to select prime $p$ such that $p\bmod65537\ge2$, which insures $\gcd(p-1,65537)=1$ since $65537$ is prime. Same for $q$. I have seen code that selects random $r$ in $[2,65536]$ then sieves for prime $p$ with $m\bmod65537=r$. $\endgroup$ Oct 25, 2023 at 20:44
2
$\begingroup$

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.

$\endgroup$
3
  • 6
    $\begingroup$ Lower isn't vulnerable with proper padding. But it is harder to screw up with higher exponents, indeed. $\endgroup$
    – Thomas
    Jul 1, 2012 at 6:40
  • 3
    $\begingroup$ No, lower is NOT vulnerable to quick factoring; whatever (odd) e won't increase or decrease the risk of having the public modulus factored. $\endgroup$ Jul 1, 2012 at 10:26
  • $\begingroup$ That former wikipedia content was quite misguided. For example, the computation cost involved in the choice of the exponent isn't primarily the cost to compute the exponent itself, but rather the cost of computing the corresponding power of many huge integers. $\endgroup$ Jun 5, 2019 at 14:34
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I wonder if the energy consumption is a factor of the quantity of bits (32, 64) the cpu can carry, or if it’s dependent on another part of the system (L2, memory bus, external accessory ...) $\endgroup$ May 22, 2020 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.