# Appropriate public exponent choice for RSA encryption

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?

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\mapsto 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 worst (or absent) paddings.

What is the most appropriate choice for $$e$$?

The simple, safe, standard option is: choose $$e=F_4=2^{(2^4)}+1=65537$$, then choose 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 of 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 encryption with it is faster than with larger values of $$e$$ (and as well as most lower values). Still, that $$e$$ makes public-key use about 8 times slower than with $$e=3$$; the latter can be a good choice when the performance of public-key use is paramount, appropriate padding and implementations are used, and regulatory requirements allow.

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!