RSA public key exponent generation confusion 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?
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.