Factoring attack against RSA based on Pollard's Rho

[Victor Duchovni]

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