[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: PGP's e exponent too small? Not! :)
[email protected] 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...