Re: Rabin vs. RSA/ElGamal
- From: Bodo Moeller <bmoeller@xxxxxxx>
- Date: 7 Mar 2006 21:21:39 GMT
David Wagner <daw@xxxxxxxxxxxxxxxxxxxxxxxx>:
My impression is that most RSA implementations that use e=65537 do
so more out of ignorance than out of reasoned analysis. Maybe not all,
but a common pattern I hear, when I ask why they use e=65537, is the
confusion that the implementor thought there were known attacks against
e=3 (which, as I said above, is just a confusion).
I don't know for sure why e = 65537 (= 2^16 + 1) is often preferred
to e = 3, but I always assumed it is because this choice of e
doesn't restrict the choice of p and q that much.
RSA with exponent n = p*q requires that e has no common divisors
with p-1 or with q-1, so if you'd prefer to use a random pair (p,q)
of primes of some order of magnitude, the probability that you can
actually use p*q for RSA with e = 3 is only about 4/9 (since about
2/3 of the primes p are suitable and about 2/3 of the primes q are
suitable). To improve on this, it's a good idea to use some prime for
e that isn't too small (to keep the probability of the event
gcd(e, p-1) > 1 or gcd(e, p-1) > 1 small), and preferrably is of the
form e = 2^k + 1, since this makes exponentiation simple and fast.
This makes the Fermat prime 2^16+1 a reasonable choice.
So why would one prefer to use an e that works with more pairs
(p, q)? One possible explanation is that improves the efficiency
of key generation with very simple prime generation algorithms, which
may be relevant for some small devices, or just to reduce the
implementation effort. Another possible explanation is that one might
be suspicious (or rather, supersticious) that the choice of primes
might have security implications, e.g. that factoring might be easier
for the subset of RSA moduli that work for e = 3. Nothing of this
is actually a compelling reason, but it might explain why the choice
e = 65537 became common.
- Prev by Date: Re: terminology question
- Next by Date: Re: AES/RSA encryption program
- Previous by thread: Re: Rabin vs. RSA/ElGamal
- Next by thread: Re: Rabin vs. RSA/ElGamal