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