fast way to decode RSA encryption

Bill Stewart bill.stewart at pobox.com
Fri Feb 9 00:36:04 PST 2001


At 12:17 AM 2/6/01 -0500, Phillip H. Zakas wrote:
>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.)  

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

Yes, your analysis is way off base.  
The reason is that there are much better algorithms for factoring - 
a factor of 10 difference in the number of clock cycles per step
is rapidly dwarfed by an algorithm that takes far fewer steps.

If you look at Schneier's book, there's a discussion of
factoring algorithms - Quadratic Sieve algorithms are good for
fewer that 120-150 digits, and above that there are algorithms like
the Number Field Sieve and its variants with run times of
	e**( (ln n)**(1/3) * (ln (ln n)**(2/3)) )
which is a lot fewer than trial division.

Check out Odlyzko's work on solutions to the discrete log problem.


	
				Thanks! 
					Bill
Bill Stewart, bill.stewart at pobox.com
PGP Fingerprint D454 E202 CBC8 40BF  3C85 B884 0ABE 4639





More information about the cypherpunks-legacy mailing list