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@Algebra.COM [mailto:owner-cypherpunks@Algebra.COM]On Behalf Of Alan Olsen Sent: Monday, February 05, 2001 4:43 PM To: Warren Piece Cc: cypherpunks@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@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."