Re: Factoring attack against RSA based on Pollard's Rho
At 8:07 PM -0700 6/5/09, Greg Perry wrote: Greetings list members, I have published a unique factoring method related to Pollard's Rho that is published here: http://blog.liveammo.com/2009/06/factoring-fun/ Any feedback would be appreciated. Is there any practical value to this work? That's a serious question. The main statement about the value is This is a factoring attack against RSA with an up to 80% reduction in the search candidates required for a conventional brute force key attack. Does that mean that it reduces the search space for a 1024-bit RSA key to, at best 205 bits (0.2 * 1024) of brute force? That is a silly reduction; reducing it to anything less than the estimate for NFS (about 80 bits) is not useful. Or, can this attack be combined with NFS? Or...? --Paul Hoffman, Director --VPN Consortium - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Factoring attack against RSA based on Pollard's Rho
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
Re: Factoring attack against RSA based on Pollard's Rho
Paul Hoffman wrote: At 8:07 PM -0700 6/5/09, Greg Perry wrote: Greetings list members, I have published a unique factoring method related to Pollard's Rho that is published here: http://blog.liveammo.com/2009/06/factoring-fun/ Any feedback would be appreciated. Is there any practical value to this work? That's a serious question. The main statement about the value is This is a factoring attack against RSA with an up to 80% reduction in the search candidates required for a conventional brute force key attack. Does that mean that it reduces the search space for a 1024-bit RSA key to, at best 205 bits (0.2 * 1024) of brute force? No, no. You don't multiply by .2, you add log_2(.2), which is around -3. So, 1021 bits. -- http://www.apache-ssl.org/ben.html http://www.links.org/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Factoring attack against RSA based on Pollard's Rho
On Sun, Jun 07, 2009 at 05:10:30PM +0100, Ben Laurie wrote: Paul Hoffman wrote: At 8:07 PM -0700 6/5/09, Greg Perry wrote: Greetings list members, I have published a unique factoring method related to Pollard's Rho that is published here: http://blog.liveammo.com/2009/06/factoring-fun/ Any feedback would be appreciated. Is there any practical value to this work? That's a serious question. The main statement about the value is This is a factoring attack against RSA with an up to 80% reduction in the search candidates required for a conventional brute force key attack. Does that mean that it reduces the search space for a 1024-bit RSA key to, at best 205 bits (0.2 * 1024) of brute force? No, no. You don't multiply by .2, you add log_2(.2), which is around -3. So, 1021 bits. Well, if this were a correct implementation of Pollard's rho, with a polynomial (not some unspecified PRNG) iterator coupled with a cycle finder (not just the computation of the gcd of each term with N), then the run time would be a non-interesting O(2^256). Now the claimed improvements of 80% are for a misconceived Pollard rho, which uses random trials gcd(PRNG, N), with a non-polynomial PRNG and no cycle finder. This should have a run-time of O(2^512), and the author claims an 80% cost reduction to ~O(2^509), but even this claim is dubious. -- Viktor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Factoring attack against RSA based on Pollard's Rho
On Sun, Jun 07, 2009 at 05:41:00PM -0700, Greg Perry wrote: The significance of this method is the ability to determine any properties of p and q from a simple operation to n. To be blunt, I see no significance of any kind... You have observed that unless N is divisible by 3, p and q are both also not divisible by 3. This is not new, and does not speed up factorization in any significant way (yes, you can skip candidate factors that are divisible by 3, but this is not new, and only speeds up the really slow naive algorithms like trial division). You have also observed that: N = p*q = for all moduli m, N = p * q (mod m) this too is not new, and does not speed up factorization. One does not search for both p and q simultaneously, finding the smaller of the two is sufficient, and with q not in the picture the p candidates are not constrained in any way by this relation: any prime N has an inverse mod m, provided p does not divide m. So for every prime candidate ( that is not a factor of m) the equation N = p * q (mod m) has a solution. n is a black box with p and q irretrievably discarded after key materials are created, are you aware of any process other than this method that can determine with any level of accuracy properties of p and q from n? Certainly C.F. Gauss was aware of interesting properties of this type. In Section VI, Articles 329-334 of Disquisitiones Arithmeticae, he showed a sieve for prime factors of composite numbers based on quadratic reciprocity. This sieve was useful (no computers in ~1800) for numbers difficult to factor by hand without effective short-cuts, 7-10 digit numbers with 3-5 digit prime factors. Gauss had tables of residues that made it possible to quickly read off primes that simultaneously satisfied all the residue constraints. -- Viktor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Factoring attack against RSA based on Pollard's Rho
On Mon, Jun 8, 2009 at 11:51 AM, Victor Duchovni victor.ducho...@morganstanley.com wrote: On Sun, Jun 07, 2009 at 05:41:00PM -0700, Greg Perry wrote: The significance of this method is the ability to determine any properties of p and q from a simple operation to n. To be blunt, I see no significance of any kind... You have observed that unless N is divisible by 3, p and q are both also not divisible by 3. This is not new, and ... I do not have it to hand, but at one point I had a solution for N = pq = (a-b)(a+b) = a^2 - b^2 where I could find unique values for a^2 and b^2 mod 9, mod 16, or by combining those mod 144. Mod 25, mod 49 et cetera gave constraints but not unique solutions. After playing with this a while, I concluded that it was not actually useful, -- Sandy Harris, Quanzhou, Fujian, China - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Factoring attack against RSA based on Pollard's Rho
Greetings list members, I have published a unique factoring method related to Pollard's Rho that is published here: http://blog.liveammo.com/2009/06/factoring-fun/ Any feedback would be appreciated. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
