Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 ?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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)$ must be 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).

share|improve this answer

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.

share|improve this answer
    
There are no security benefits to large exponents (assuming you use RSA properly, including proper padding and so forth; and if you don't use RSA properly, then you've got bigger problems and might be in trouble no matter what exponent you use). –  D.W. Oct 7 '13 at 20:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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