3
$\begingroup$

Quote from Wiki:

$e$ having a short bit-length and small Hamming weight results in more efficient encryption — most commonly $2^{16} + 1 = 65537$. However, much smaller values of $e$ (such as $3$) have been shown to be less secure in some settings.

Does this mean that it is secure to choose the smallest possible public key exponent possible that is larger than a certain threshold, such as $65537$? If it is not so, how are values of the public key exponent generated in more secure RSA implementations?

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ Very small exponent such as $e=3$, are subject to some attacks in some precise protocols such as enciphering the same plaintext message to different recipients, and broadcasting. It can also help in attacks which involve LLL. When $e=3$ for example the public modulus and the Euler totient $\phi(n)$ share approximately half of the most significant bits. Moderately sized exponents such as $2^{16}+1$ or $2^{32}+1$, are commonly used by applications if the implementation has been secured against all known attacks. $\endgroup$ – Robert NACIRI Jan 15 '15 at 18:32
  • 3
    $\begingroup$ "When e=3 for exemple the public modulus and the Euler totient $\phi(n)$ share approximatly half of the most significant bits." The fact is correct, the reasoning is wrong. The choice of $e$ has no influence on $\phi(n)=(p-1)(q-1)$. But the fact is also meaningless: If we assume two random numbers of equal length (that's the case for $\phi(n)$ in general), then they share the same bit in half of all positions. $\endgroup$ – tylo Jan 16 '15 at 15:51
  • 1
    $\begingroup$ @tylo : $\;\;\;$ It one starts by choosing $e$, then $\: e=3 \:$ will force the primes to have $\hspace{1.31 in}$ remainder 2 mod 3 rather than 1 mod 3. $\;\;\;\;\;\;\;\;$ $\endgroup$ – user991 May 26 '15 at 2:03
  • $\begingroup$ @Robert NACIRI: I've never met $e=2^{32}+1$ (and that's not a prime, which triggers annoying corner cases in the generation of $p$). Did you mean $e=2^{8}+1$, which indeed is common? $\endgroup$ – fgrieu♦ May 26 '15 at 13:30
  • $\begingroup$ @fgrieu: The public exponent don't need to be a prime number. For a mathematical point of view (and for testing purpose), you don't ignore the relation between e and Euler Totient to allow calculation of the private exponent. However you're right when you mention the standards which fix the value of e? But aren't they only informative? $\endgroup$ – Robert NACIRI May 26 '15 at 21:08
2
$\begingroup$

Usually the public exponent is first chosen. Often it is the fifth prime of Fermat (e.g. -f4 for openssl), 65537. It's the fifth number as the index starts with 0.

This number in binary is:

0000 0000 0000 0000 0001 0000 0000 0000 0001

Fermat primes are primes with just 2 bits set. 3, 5, 17, 257 and 65537 are the only known Fermat primes. Because only two bits are set the exponentiation is relatively fast compared to other exponents.

After the choice of public exponent the primes $p$ and $q$ are chosen in such a way that they comply with the chosen public key. To be precise, this means that $p - 1$ and $q - 1$ need to be relative prime to $e$. This is slightly different than most text book methods of generating an RSA key pair where $p$ and $q$ are chosen first.

Smaller and much larger exponents may be vulnerable to some kind of attacks. Usually other properties for which the keys are used - mainly padding - cause these attacks to be impossible. Cryptographers and standardization institutes however like to play it safe, so current implementations almost unanimously choose the fourth prime of Fermat as public exponent.

Choosing a high valued public exponent will hurt performance because higher values will take more time during the modular exponentiation used for encryption and verification. In the worst case the exponentiation is as slow or even slower than the private key operation. If $e$ is randomized then it is usually 16, 32 or 64 bit value at most (e.g. original implementations of PGP). Some implementations (.NET) only accept small public exponents.

Improve this answer
$\endgroup$
3
  • $\begingroup$ An exception to " usually 16 bit value at most " occurs in the European Digital Tachograph, CSM_014, where that is optionally up to 64-bit. Smart Cards that have a certificate (or/and a certification authority certificate) with these extra-long $e$ are annoyingly slower to use than others using $e=2^{16}+1$. $\endgroup$ – fgrieu♦ May 26 '15 at 13:25
  • $\begingroup$ @fgrieu It's a good thing that that standard limits the size of the public exponent, but it would be better to have it standardized on $e=2^{16}+1$. Now every terminal (box) has to test for larger $e$ values as well. Of course, it's pretty moronic to chose a large value $e$ even if the standard allows such values (this could be a bit of a dangerous statement for me to make, but whatever :) ). Just standardizing on 1024 is a bit dangerous as well, even though I don't see anybody factor such a private key just to attack a single tacho card. You could buy a truck for that amount of money :) $\endgroup$ – Maarten Bodewes♦ May 26 '15 at 13:40
  • $\begingroup$ 1024-bit is also used for certification authorities, and root CA keys, which is becoming obsolete; on the other hand compromise of any Member State key or Tachograph (VU) key would allow breaching the integrity of data recorded in all cards, without possibility of revocation or time limit, longer keys would not have changed this. $\endgroup$ – fgrieu♦ May 26 '15 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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