Factoring attack against RSA based on Pollard's Rho
Victor Duchovni
Victor.Duchovni at morganstanley.com
Sun Jun 7 14:17:52 EDT 2009
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
More information about the cryptography
mailing list