Re: PGP's e exponent too small? Not!

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

hfinney@shell.portal.com wrote:

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

Yeah, I guess I should have proofread that better.  You are correct.

I was stating that it was possible to narrow your search significantly
if d*e=(p-1)(q-1)+1.   In retrospect, it was probably a mostly
irrelevant tangent.

-> The correct equation is
->
-> 	d*e = 1  mod (p-1)(q-1)

You mean   1 = d*e mod (p-1)(q-1)   Right?

-> or, in other words:
->
-> 	d*e = k(p-1)(q-1) + 1

Yup.

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

Oh.  Okay.  That was not made clear in the original post.  Yes, I can
see how that could be a problem... and random padding would solve it.  
I don't think that would actually reveal the secret key, but the message
could be decrypted...