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: mpd@netcom.com (Mike Duvos)
Message Hash: 9fffb4889e4ac3d5411e7eb4893db6e0e3bb7008b0265d525ff11b322b27446c
Message ID: <9406172015.AA02813@snark.imsi.com>
Reply To: <199406171958.MAA07441@netcom5.netcom.com>
UTC Datetime: 1994-06-17 20:18:30 UTC
Raw Date: Fri, 17 Jun 94 13:18:30 PDT

Raw message

From: "Perry E. Metzger" <perry@imsi.com>
Date: Fri, 17 Jun 94 13:18:30 PDT
To: mpd@netcom.com (Mike Duvos)
Subject: Re: Prime magnitude and keys...a ?
In-Reply-To: <199406171958.MAA07441@netcom5.netcom.com>
Message-ID: <9406172015.AA02813@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain



Mike Duvos says:
>  > If I have an algorithm that will take any arbitrary RSA key
>  > and produce the private key by a mechanism such as the one
>  > you propose, you are (almost certainly) proposing an
>  > algorithm that will factor arbitrary numbers that are a
>  > product of two primes.
> 
> This is likely true.  However, it does not necessarily follow
> that such an algorithm will be any faster than current methods of
> factoring and might very well be a good deal slower.

Ahem. He was proposing a mechanism that will work in log(n) time. All
current known methods are subexponential. As you SHOULD know, a log
function will eventually be smaller than a subexponential one if you
only let N grow large enough. This is baby complexity theory. I find
it astonishing that I should even have to mention it.

> What you seem to be overlooking is that the function Jim
> proposes, which tells the numerical order of two keys from an
> examination of the results of using them, is probably an
> exponential time algorithm itself as a function of keysize.

Thats not what he was proposing. Obviously one can build such an
algorithm given a factoring algorithm, and we know of exponential
factoring algorithms. That wasn't the idea. His notion was that there
might be a CHEAP algorithm to do this.

Perry

Thread