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$
  • 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 receipients, and broadcating. It can also help in attacks which involve LLL. When e=3 for exemple the public modulus and the Euler totient $\phi(n)$ share approximatly half of the most significant bits. A moderatly exponent as $2^16+1$ or $2^32+1$, are commonly used by applications with no particular threat if the implementation has been secured against all the know attacks. $\endgroup$ – Robert NACIRI Jan 15 '15 at 18:32
  • 1
    $\begingroup$ $2^{16}+1$ or $2^{32}+1$ $\endgroup$ – Robert NACIRI Jan 15 '15 at 18:39
  • 2
    $\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
  • $\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
2
$\begingroup$

Usually the public exponent is first chosen. Often it is the 4th prime of Fermat (e.g. -f4 for openssl), 65537. 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. It is relatively easy to use this as exponent as only two bits are set. This makes the exponentiation rather fast.

After that 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. If $e$ is randomized then it is usually 16 bit value at most (e.g. original implementations of PGP).

|improve this answer
$\endgroup$
  • $\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 - reinstate Monica♦ 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.