Factoring attack against RSA based on Pollard's Rho

[Victor Duchovni]

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 majordomo at metzdowd.com