Openssl & RSA : how many public exponents are possible?

Question

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 ?

Answer 1

The 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:

• The modulus $n$ must not be larger than 16384 bits.
• The public exponent $e$ must not be greater than $n$.
• If $n$ is larger than 3072 bits, then $e$ must fit in 64 bits.

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:

• Its binary representation contains mostly zeros, which gives a small performance advantage in a square-and-multiply algorithm (you still need to do 16 squarings, but only one non-squaring multiplication).
• It is prime, which is good for some key generation algorithms: for a RSA key, you need to generate two big primes $p$ and $q$, such that $e$ is relatively prime to $p-1$ and $q-1$. By choosing $e = 65537$, you can generate $p$ and $q$ without caring about $e$, and just start over if the "relatively prime" condition turns out not to be fulfilled (happens with probability $1/65537$ for each prime, so quite rarely).
• It is bigger than $3$, which appeases people.

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.

Answer 2

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.