[144509] in cryptography@c2.net mail archive
Re: Factoring attack against RSA based on Pollard's Rho
daemon@ATHENA.MIT.EDU (Victor Duchovni)
Sun Jun 7 17:51:30 2009
Date: Sun, 7 Jun 2009 14:17:52 -0400
From: Victor Duchovni <Victor.Duchovni@morganstanley.com>
To: cryptography@metzdowd.com
Mail-Followup-To: cryptography@metzdowd.com
In-Reply-To: <4A2BE676.3070809@links.org>
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@metzdowd.com
