Re: Prime magnitude and keys...a ?

[mpd@netcom.com (Mike Duvos)]

Perry E. Metzger, who is evidently having a bad hair day, said
the following not very nice things to Jim Choate:

 > Who cares what you think you are talking about? You haven't
 > shown much common sense thus far.

 > You can't find a reference in the library on why you can't
 > build a machine that cracks DES by repeatedly trying the
 > digitized sound tracks of porno films, either. Maybe you
 > should try that -- who knows, it might work.

 > Ahem. Perhaps you should have kept awake in school. Log
 > base 2 of a number just means the number of bits in it.

In the words of Rodney King, "Can't we all just get along?"

Perry further comments:

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

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.

Performing such an algorithm log2(n) times does not yield an
algorithm which is O(log2(n)) in computational complexity, unless
Jim's magic function happens to be hardwired into your CPU and
executes in a constant of clock cycles regardless of its
operands.

 > I'm afraid that given such a function, I can derive the
 > original key within log[base2](n) operations.

Your fears are unfounded. :)

-- 
     Mike Duvos         $    PGP 2.6 Public Key available     $
     mpd@netcom.com     $    via Finger.                      $