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: Jim choate <ravage@bga.com>
Message Hash: b95be75db8fb914fe5d714b5c305fdff3d0726db1d22abab80698dc5fa11f46f
Message ID: <9406171646.AA02442@snark.imsi.com>
Reply To: <199406171633.LAA04621@zoom.bga.com>
UTC Datetime: 1994-06-17 16:46:56 UTC
Raw Date: Fri, 17 Jun 94 09:46:56 PDT

Raw message

From: "Perry E. Metzger" <perry@imsi.com>
Date: Fri, 17 Jun 94 09:46:56 PDT
To: Jim choate <ravage@bga.com>
Subject: Re: Prime magnitude and keys...a ?
In-Reply-To: <199406171633.LAA04621@zoom.bga.com>
Message-ID: <9406171646.AA02442@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain



I said:
> > Of course you haven't seen such a thing. If factoring RSA keys
> > requires exponential time, such an algorithm is obviously not
> > possible. Were it possible, you could factor in time proportional to
> > the the number of bits in the key. Anyone who had such a function
> > would either be famous or wouldn't be talking.

Jim choate says:
> How about some evidence on it? I see no reason to compare taking a key
> and determining if it is too large or too small as being necessarily
> equivalent to factoring a large number.

Its called "binary search". You were supposed to learn it in your
intro to computer science class.

Lets play the guessing game, shall we? Its much like twenty questions,
only that just works for twenty bit things or less. We know that we
have a big number. If you give me a function that tells me one bit
(greater or not greater) for every guess, I can get a bit of the
number. After a short time, I'll know the number -- the time is
exactly the number of bits in the number (that is, the log base 2 of
the number.)

Perry

Thread