Hi there,
On Fri, 16 Feb 2001, Deng Lor wrote:
> I'm eager to know why 65537 is selected as the e, and are there
> any fact proofing it is better than other primes seleted out
> randomly?
"e" itself doesn't have to be prime but it does have to satisfy certain
conditions relative to "d" and the underlying RSA primes. However, usually
"e" is chosen in advance, and then the rest of the keygen process is
rigged to try and work out the rest to fit. The common choices for "e" are
3, and 65537 (the latter otherwise known as F4, F=Fermat).
The reasons; 3 is the smallest and fastest exponent to do public-key
operations with. 65537 is also quite fast and small, but "feels" more
secure than 3 (for various reasons already mentioned and more). You'll
note that the binary expansions of the two numbers are;
3 = 11
65537 = 10000000000000001
(ie. they're a little sparse on "1"s which is a good thing for speed ...)
The part mostly responsible for the speed of public key RSA operations are
"mod_exp" calculations - they are of the form "a^e mod n" where (n,e) is
the public key and a is the input data. A technique often used to
calculate this for a given "a" involves calculating a series of squares;
a0 = a mod n
a1 = a^2 mod n = a0^2 mod n
a2 = a^4 mod n = a1^2 mod n
a3 = a^8 mod n = a2^2 mod n
....
and then you can cross-multiply according to the binary expansion of the
desired exponent "e". In other words,
a^3 mod n = (a^2 * a^1) mod n = (a1 * a0) mod n
or
a^65537 mod n = (a^65536 * a^1) mod n = (a16 * a0) mod n
(ie. the multiply only has two operands because the above binary
expansions only have two "1"s in each - if they had lots of "1"s, you'd
have lots of multiplies to do).
So with e=65537, you need to calculate the series up to a16 whereas e=3
only requires the series up to a1. This is still way faster than using
some arbitrary "e" (which would on average require calculating the series
up to a1023 for 1024-bit keys, and the cross-multiplication would on
average use 512 of the series' values). However, for an arbitrarily chosen
"e", CRT or montgomery forms would probably be used anyway rather than
this clunky technique (which is not optimal at all for "noisy" exponents
as is used in private key operations).
That's a highly rough, corner-cutting, hand-wavey, and in some instances,
quite possibly wrong, explanation of the "e". That's all you're going to
get from me however, and with the speed it was banged out you'll probably
have to wait for the more sage lurkers on this list to pick it apart
carefully and give you the *real* truth. :-)
Cheers,
Geoff
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
