Re: Rabin vs. RSA/ElGamal

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.
.

Relevant Pages

  • Re: A possible argument for no more Fermat primes.
    ... there has to be a much deeper reason why there can't be more. ... The reason why there are finitely many Fermat primes is simple. ... We are looking at the intersection of two sets: One is somewhat thin ...
    (sci.math)
  • Re: Determine size of keyspace for RSA keys
    ... >>could pick for p times the number of primes that you could pick for q. ... For the same reason that d does not contribute to the ... keyspace size, q is a function of p and the public n. ... uses a 128-bit key and reveals 88 bits of the key, ...
    (sci.crypt)
  • Re: Simple way to show number is a power?
    ... The reason I asked the question was that the methods I have seen ... and had determined the primes in this ring, ... I said it was easy to show there is an infinity ... by using more general quadratic fields? ...
    (sci.math)
  • Re: A possible argument for no more Fermat primes.
    ... The reason why there are finitely many Fermat primes is simple. ... measure since the number of such sequences is uncountable) ... they are a very very very thin sequence and there is no a priori ...
    (sci.math)
  • Re: Abiogenesis: Where is the model?
    ... proscribres its ability to study living things, ... common sense," which very plainly *cannot* be squared with your claim ... not reason at all. ... offered a premise/definition of "living entity" as spirit. ...
    (talk.origins)