fast way to decode RSA encryption

Phillip H. Zakas pzakas at toucancapital.com
Mon Feb 5 21:17:51 PST 2001



I spent a little bit of time studying this approach.  I know Rivest is
dismissing it, but from a computational perspective it's more efficient in
terms of clock cycles than trying to factor a number using
multiplication/division (at least using the Pentium chip.)  Here is a link
detailing pentium clock cycles for various instructions:
http://orakel.tihlde.org/kurs/3d/download/PENTIUM.TXT
You'll see that the instructions for loading 8-bit values and performing an
XOR, shift and compare is pretty low (<25 clock cycles on paper anyway).
The clock cycles for an average multiplication is in the tens-to-hundreds of
clock cycles.  It's a bit more difficult to calculate the clock cycles for
larger values, but in principle this should engage much fewer clock cycles
than traditional factoring techniques. If this isn't a true crack as Rivest
claims, it's at least a (computationally) faster factoring technique.
Perhaps this is the way to more quickly win the next DES-cracking challenge.
Is my analysis off-base?? I've contacted the amateur mathematician to see if
we can obtain more info.

phillip


-----Original Message-----
From: owner-cypherpunks at Algebra.COM
[mailto:owner-cypherpunks at Algebra.COM]On Behalf Of Alan Olsen
Sent: Monday, February 05, 2001 4:43 PM
To: Warren Piece
Cc: cypherpunks at cyberpass.net
Subject: Re: fast way to decode RSA encryption



On Mon, 5 Feb 2001, Warren Piece wrote:

> anyone else seen this claim?
> http://www.mb.com.ph/INFO/2001-02/IT020201.asp

Yep.  Slashdot has a quote from Ron Rivest on why it is not a break or a
big deal.  (The method works, but it is *slower* than factoring.)

http://slashdot.org/article.pl?sid=01/02/05/1911258&mode=flat

alan at ctrl-alt-del.com | Note to AOL users: for a quick shortcut to reply
Alan Olsen            | to my mail, just hit the ctrl, alt and del keys.
    "In the future, everything will have its 15 minutes of blame."






More information about the cypherpunks-legacy mailing list