From: hfinney@shell.portal.com
Date: Sun, 16 Jan 94 19:18:15 PST
To: cypherpunks@toad.com
Subject: Re: PGP's e exponent too small?  Not!
Message-ID: <199401170317.TAA24162@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

Matthew J Ghio, <mg5n+@andrew.cmu.edu>, argues that low public exponents
such as are used by PGP are unsafe in the RSA public-key cryptosystem.

I think his analysis is mistaken, although there were a fair number of
typing errors which make it hard to be sure I am understanding him
correctly.

> Here's why
> you shouldn't use low powers of d:

The issue is not whether the d power should be low; of course it should
not be, since that is the secret exponent, and choosing a small one
will make it easier to guess.  The question is whether small e values
are unsafe.  I think this is just a typographical mistake.

> Remember that d and e are factors of (p-1)(q-1)+1.

This is the fundamental error in his analysis.  The correct equation
is

	d*e = 1  mod (p-1)(q-1)

or, in other words:

	d*e = k(p-1)(q-1) + 1

All of Matthew's reasoning about putting bounds on d*e (he often writes
of bounding p*q, but I'm pretty sure he means d*e) is based on this false
assumption that d*e is a factor of (p-1)(q-1)+1.  Actually, the true
relation is that (p-1)(q-1) is a factor of d*e-1.

The concern about low values of e in the Schneier book relates to the
issue of RSA-encrypting the same value with the same low e value and
different RSA moduli.  This might be done if you were using "pure" RSA
(which PGP and PEM do not) and encrypting the same message for multiple
recipients.  Kaliski is right that adding random padding to what is
encrypted will eliminate this attack.  PGP and PEM do add such random
padding, following RSA's Public Key Crypto System standard.

Hal

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLTnW4agTA69YIUw3AQFPOAP9Hk+bwFCgF6F16Cl+WUh0ZfoUvHXLQGuV
+pGVySmTe1yftSUq4NQTVMFmzHXc16MvxJjMBYgH445qpwn9EgHVHISG/YdaDsFs
9AA7c5lcgLxUPwzwkOLlUhICXyFLy+Hz9kWqE90ypd+7RFk0UiCwtIT9EsVywC0c
3GM8BKtJNJI=
=/BA8
-----END PGP SIGNATURE-----