On Fri, Jun 05, 2009 at 08:07:21PM -0700, Greg Perry wrote: > I have published a unique factoring method related to Pollard's Rho that > is published here: > > http://blog.liveammo.com/2009/06/factoring-fun/
Several aspects of the RSA encryption algorithm can be attacked: attacks against the quality of the entropy pool used by the random number generator (RNG) that creates the p and q primes; ``side channel'' cryptanalysis attacks where key materials are divined from power rails, shared bus architectures, shared memory segments etc; exponential ``increase by two'' factoring attacks and more esoteric subexponential factoring attacks ---------------------------------------------- such as the General Number Field Sieve; and, even the tried and true (and highly effective) Rubber Hose Cryptanalysis method. What you call "more esoteric" is properly called "more sophisticated" or "more effective". Your "attack" is not sub-exponential, and is of no practical interest for RSA moduli of cryptographic strength. I have not yet compared the performance of this Reduction Sieve method to GNFS or any other subexponential factoring methods. Future testing of this factoring method will include deployment into an 80+ node VMware cluster at our datacenter and experimentation with on-demand cloud computing infrastructures such as Amazon?s EC2 Elastic Compute Cloud. Such performance comparisons are unnecessary, and would be a waste of CPU time and money. GNFS is substantially faster than Pollard's rho for RSA moduli of interest in cryptography. > Any feedback would be appreciated. There is nothing new here. First of all, if N mod 9 is a multiple of 3, then N is divisible by 3, so those cases are of no interest, you would factor N/3 instead. For the other cases, * Either N mod 9 is a quadratic residue mod 9, in which case p*q == N mod 9 has 4 pairs of solutions, (a,a), (b,b), (c,d), (e,f) where a and b are the two square roots of N mod 9, and c,d,e,f are the remaining units. * Or N mod 9 is not a quadratic residue mod 9, in which case p*q == N mod 9 has 3 pairs of solutions: (a,b), (c,d), (e,f) Now indeed if N = p*q for some pair of primes, and N is not a multiple of 3, then p mod 9 is one of six possible values and q is the reciprocal (mod 9) of that value. Now, the "Pollard rho" algoritm is based on the birthday paradox for differences between pairs of random values (x,y) mod N, being *divisible* by a factor "p" of N, i.e. gcd(|x-y|,N) > 1, allowing the attack to run in n^(1/4) time instead of n^(1/2) time for naive division trials. It should be noted that knowing p mod 9 does not tell us much about (x-y) mod 9. We need (x-y) to be random mod "p" and thus be zero mod "p" with the expected birthday paradox probability. So there is no reason for (x-y) to be any particular value mod 9, even multiples of 3 are fine, nothing wrong with (x-y) being divisible by 3p. For the birthday paradox we can't control the difference (x-y) mod 9 for all pairs of a large set, because if (x_1 - x_2) = a mod 9 and (x_2 - x_3) = b mod 9, then (x_1 - x_3) is a + b, mod 9, and the additively closed subsets of z_9 are: {0} {0,3,6} {0,1,2,3,4,5,6,7,8} so you can't practically limit (x-y) mod 9 to a given unit and still use the birthday paradox to make "rho" fast. Speaking of birthday paradoxes and making "rho" fast: your code appears to completely omit any use of the birthday paradox, and so would run in n^(1/2) time instead of n^(1/4) time. If so it is far worse than the real Pollard algorithm that you seem to not have studied with sufficient care. -- Viktor. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com