I would like to know if it is possible to set the public exponent we want with "OpenSSL RSA" or if it is really limited to 2 possible exponents:
- 3
- 65537
If yes, why ?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this communityThe public exponent of a RSA key is, nominally, an odd integer $e \geq 3$. Any such integer can be used with RSA, although not necessarily with any modulus $n$: $n$ and $e$ must be such that $e$ and $\phi(n)$ are relatively prime to each other. This is why $e$ cannot be even: $\phi(n)$ is even, so it can never be prime to another even number. Apart from that, any odd integer can be theoretically encountered as a public exponent (not $1$, but some implementations will accept it nonetheless, although it is very weak).
A specific implementation of RSA may be more restrictive. OpenSSL appears to have, by default, the following limitations:
These conditions (especially the third) are fairly arbitrary, but so it is. In fact, you want to be even more restrictive, because of interoperability. For instance, the default RSA implementation in Windows (CryptoAPI) cannot process RSA public keys where the public exponent does not fit on 32 bits.
There is no known security advantage to large public exponents over small public exponents. However, there is a quite plain performance advantage to using small exponents, and the smaller the better. Which us why $e = 3$ should be preferred. Using $e = 65537$ is a well-entrenched tradition, for no real good reason (even with $e = 65537$, RSA public-key operations are still quite fast, so it does not matter much in practice).
"65537" was selected for several reasons:
None of these reasons is really strong. Public-key operations in RSA are fast anyway; and $e = 3$ is the fastest you can get. If you really need ultimate performance for public-key operations, then $e = 65537$, while being about the best 17-bit exponent you can find, is still substantially slower than RSA with $e=3$. Not that it really matters most of the time (private-key operations are where performance issues usually are; and if you really need the extra cycles for public-key operations then you should use Rabin signatures, not RSA).
Prime generation can take into account the public exponent, e.g. you can generate candidate $p$ values as $p = 3r+2$ where $r$ is an odd random integer; this ensures that $p$ will not be a multiple of $3$ and that $p-1$ will be relatively prime to $3$ too. This process can be extended to ensure that not only $p-1$ will be relatively prime to your pulbic exponent of choice, but also that the candidate $p$ will not be a multiple of 2, 3, 5, 7, 11, 13... which will make bad candidate pruning faster.
The qualms some people have about $e = 3$ are the consequences of an old piece information that got corrupted along the way and turned into a myth. See this answer for details.
openssl genrsa
only supports 3 and F4=65537. The newer (since 1.0.0 in 2010) and less known commandline genpkey
, or custom code calling the library, can have the broader range described here.
$\endgroup$
Nov 2, 2014 at 9:30
No; you can theoretically use (almost) any $e$ such that $1 < e < \varphi(n)$. There are some potential attacks on RSA with low exponents — see this question by fgrieu — so we tend to prefer larger exponents.
As for why 65537 is an extremely common exponent: it has a lot of benefits while still being large. See this answer by fgrieu for more information. To summarize, 65537 is essentially a compromise between large exponents and efficiency.
To be more precise about which $e$ you can use, the only condition on $e$ is that you must be able to find a $d$ such that $ed \equiv 1 \pmod{\lambda(n)}$, i.e. that a multiplicative modular inverse must exist. This is only the case if $\operatorname{gcd}(e, \lambda(n))=1$. Now, it's well-known in number theory that $\lambda(x) \mid \varphi(x)$ for all $x$, so if we choose an $e$ such that $\operatorname{gcd}(e, \lambda(n)) \ne 1$, then we will have $\operatorname{gcd}(e, \varphi(n)) \ne 1$ as well. But
$$\varphi(n) = \varphi(pq) = \varphi(p)\varphi(q) = (p-1)(q-1),$$
so we would have that $\operatorname{gcd}(e, p-1) \ne 1$ or $\operatorname{gcd}(e, q-1) \ne 1$. So, you cannot use an $e$ that shares a factor with $p-1$ or $q-1$, but other than that, all of them are fair game.