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