Factoring attack against RSA based on Pollard's Rho

[Victor Duchovni]

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