From: Matthew J Ghio <mg5n+@andrew.cmu.edu>
Date: Sun, 16 Jan 94 21:08:16 PST
To: cypherpunks@toad.com
Subject: Re: PGP's e exponent too small? Not! :)
In-Reply-To: <199401170317.TAA24162@jobe.shell.portal.com>
Message-ID: <shCVnFC00awIE3m10K@andrew.cmu.edu>
MIME-Version: 1.0
Content-Type: text/plain


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