From: "Perry E. Metzger" <perry@imsi.com>
Date: Mon, 20 Jun 94 05:06:48 PDT
To: Jim choate <ravage@bga.com>
Subject: Re: Prime magnitude and keys...a ?
In-Reply-To: <199406172325.SAA22491@zoom.bga.com>
Message-ID: <9406201206.AA05037@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain



Jim choate says:
> > 
> > If you can get the sign of the difference between RSA(your number) and
> > RSA(unknown key), then you can discover (unknown key) in log n time.
> > That implies, due to the nature of RSA, that you can factor in log n
> > time using whatever algorithm it is that makes the determination of
> > the sign of the difference. 
> 
> No, again   it will allow you to find the secret key, it will not 
> provide any information about the factors of that number.

The two are equivalent. Unfortunately, no amount of explanation will
get that into your head. I've revised my thoughts on the matter over
the weekend after scribbling on a pad for a few minutes -- it should
be fairly straightforward to prove that if you can get the private key
given the public key that you can factor arbitrary numbers. (This is
not the equivalent of saying RSA can be broken only by factoring -- it
is possible that there is an algorithm to get the plaintext given the
public key and the ciphertext without first determining the private
key.)

Anyway, no one is interested any more, and most people are likely
quite unhappy to have received so much unwanted flame mail about this,
so I won't reply to Jim any further.


Perry