2
$\begingroup$

From what I understand, we can arbitrarily choose an exponent e as long as $\gcd(e,\phi(n)) =1$.

  • But what is the most appropriate choice for it?
  • Should it be small compared to $\phi(n)$ or approach it?
$\endgroup$
5
$\begingroup$

we can arbitrarily choose an exponent $e$ as long as $\gcd(e,\phi(n))=1$.

No. If we want any security, we further :

  • Must NOT choose $e=1$, because that makes $x\to x^e\bmod n$ the identity function over $[0,n)$.
  • Must NOT choose $e$ in a way revealing information about of $\phi(n)$ or the factors of $n$ beyond that $\gcd(e,\phi(n))=1$. For example we can not choose $e$ as $e=p$, nor $e=\phi(n)-3$, nor as the first integer larger than $\phi(n)/42$ with $\gcd(e,\phi(n))=1$, nor in such a way that $d$ is small.
  • Should choose $e$ not too small if there is a regulatory minimum or we have little assurance about how the key will be used. This mitigates to some degree some poor message padding and some poor decryption implementations. Using $e\ge2\log_2(n)$ should be technically OK for all except the worse or absent paddings.

What is the most appropriate choice for $e$?

The simple, safe, standard choice is: $e=F_4=2^{(2^4)}+1=65537$, then choosing prime factors $p$ of $n$ with $p\bmod e\ne1$. This test (and factors being distinct of $e$, which holds for suitably large factors) is enough to ensure $\gcd(e,\phi(n))=1$, since we picked $e$ prime. And picking factors as a function of $e$, rather than the other way around, ensures minimal information is revealed about $\phi(n)$ and factors of $n$. $65537$ is large enough that $e\ge2\log_2(n)$ is met for practical sizes of $n$, and conforms to recommendations by all major security authorities.

If for some reason we must choose $e$ after factors of $n$, a common practice is to choose the lowest $e$ above some minimum with $\gcd(e,\phi(n))=1$. A very slightly safer practice would be to choose $e$ randomly in some interval $[m,2m)$ until $\gcd(e,\phi(n))=1$, but that's overkill (and there's seldom a good reason to choose $e$ after the factors of $n$ anyway).

Should $e$ be small compared to $\phi(n)$ or approach it?

The former: $e$ should be small, and $\phi(n)$ large. There is often a conventional upper limit to $e$, like $e<2^{256}$ in FIPS 186-4, or $e<2^{32}$ in some Windows APIs, when $\phi(n)$ must be in the thousands bits. And for reasons already spelled, $e$ must not be chosen close to $\phi(n)$. Also it is best to keep $e$ not too large for performance reason: public-key use requires time roughly proportional to the bit size of $e$. The standard $e=F_4=2^{(2^4)}+1$ is attractive because any larger $e$ and most slightly lower $e$ require more time. Still, that $e$ makes public-key use about $8$ times slower than $e=3$, which can be a good choice when performance of public-key use is paramount, appropriate padding and implementations are used, and regulatory requirements allow.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure that "using $e$ at least twice the bit size of $n$ should be fine" is that clear. Should $e$ really be twice as large as the modulus? Or do you mean that $e \ge 2 \cdot \log_2(n)$? $\endgroup$ – Maarten Bodewes Dec 7 '19 at 16:20
2
$\begingroup$

But what is the most appropriate choice for it?

For public exponent $e$, small values are preferred like $\{3, 5, 17, 257, \text{ or } 65537\}$. With this, we can guarantee that the number of operations is low. We can control this with our choice. Of course, for the choice of $e$, we must have $\gcd(e,p)=1$ for any prime $p$ divides the modulus $n$. This guarantees that we have the inverse of $e$ such that $e\cdot d = 1 \bmod \phi(n)$, and $\gcd(e',n) = \gcd(e,n)$

Should it be small compared to $\phi(n)$ or approach it?

You can choose a public exponent $e'$ bigger than $\phi(n)$, however due to the congruence, we can always find an $e$ such that $ e' \equiv e \bmod \phi(n)$ with $e < \phi(n)$.

Of course, RSA should never be used without proper padding scheme. For example, if you use $e=3$ without a proper padding scheme than you will be vulnerable to cube-root attack.

And note that RSA Signing is Not RSA Decryption!

$\endgroup$

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.