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