cryptoanarchy.wiki

Arise, you have nothing to lose but your barbed wire fences!

1994-06-17 - Re: Prime magnitude and keys…a ?

Header Data

From: “Perry E. Metzger” <perry@imsi.com>
To: cypherpunks@toad.com
Message Hash: a380de21c2d705cff4fc3df423fd8a03a3b7c35b353eb6aace0d026212091542
Message ID: <9406171813.AA02620@snark.imsi.com>
Reply To: <199406171537.KAA01766@zoom.bga.com>
UTC Datetime: 1994-06-17 18:13:48 UTC
Raw Date: Fri, 17 Jun 94 11:13:48 PDT

Raw message

From: "Perry E. Metzger" <perry@imsi.com>
Date: Fri, 17 Jun 94 11:13:48 PDT
To: cypherpunks@toad.com
Subject: Re: Prime magnitude and keys...a ?
In-Reply-To: <199406171537.KAA01766@zoom.bga.com>
Message-ID: <9406171813.AA02620@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain



Jim choate says:
> What I am looking at is a way to do binary searches in the key space w/ a 
> function that would look at a test key and the result of running RSA on 
> it and then tell me the relative magnitude between the real key and the
> test key. 

And you think no one would have noticed such a thing before.

I can pretty much hint to you that such a thing can't really be done
in log base 2 of n time in the sense that I believe I can prove that
any algorithm that did that would have to involve none of the basic
four arithmetic operations on the numbers in question. (Algorithms
involving no arithmetic on the numbers are still possible, but
intuitively quite unlikely.)

Perry

Thread