Why is a smaller value preferred for the public key in RSA?

For my practice implementation of the RSA cryptosystem I use a random value generation function such the value of public key e holds:

• The public exponent $$e$$ and the modulus $$n$$ should be $$e<\phi(n)$$

• $$e$$ and $$\phi(n)$$ are coprime, $$gcd(e,\phi(n)) = 1$$

Although this works satisfactorily, the algorithm returns values of $$e$$ which are very large in magnitude which, apparently, is undesirable.

Why is it preferred to generate smaller values for the public exponent in the RSA system?

2 Answers

As you said, choosing a large $$e$$ can make you vulnerable to attacks such as Wiener attack's because a big $$e$$ makes it possible to have a small $$d$$. It will also make the cost of your encryption higher. So big $$e$$ is not necessarily a problem (if make some verification on $$d$$, such as $$d>\frac{1}{3}\times n^{\frac{1}{4}}$$), but not the best choice.

A very common value for the public exponent is $$e=65537$$, because $$65537 = 2^{16}+1$$, which has a nice binary representation (like all Fermat primes): $$10000000000000001$$ This allow a fast computation using algorithm such as the sliding windows

You could choose $$e=3$$ for more efficiency, but you have to use a proper padding (RSA OAEP for instance). Using $$e=3$$ without proper padding will weaker your encryption scheme.

More details can be found in fgrieu's answer to a similar question.

• Big e is necessary for small(ish) d, but not sufficient. People who (stupidly) want small d (overwhelmingly) get big e, but simply choosing big e randomly or arbitrarily has negligible probability of giving small d. Commented Jan 25, 2019 at 4:56
• @dave_thompson_085 You're right, I have edited my answer accordigly Commented Jan 25, 2019 at 8:10

Cheaper encryption in terms of computational resources and time.