1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – dave_thompson_085 Jan 25 at 4:56
  • $\begingroup$ @dave_thompson_085 You're right, I have edited my answer accordigly $\endgroup$ – Faulst Jan 25 at 8:10
2
$\begingroup$

Cheaper encryption in terms of computational resources and time.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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