[144508] in cryptography@c2.net mail archive
Re: Factoring attack against RSA based on Pollard's Rho
daemon@ATHENA.MIT.EDU (Ben Laurie)
Sun Jun 7 13:38:30 2009
Date: Sun, 07 Jun 2009 17:10:30 +0100
From: Ben Laurie <ben@links.org>
To: Paul Hoffman <paul.hoffman@vpnc.org>
CC: Greg Perry <Greg.Perry@liveammo.com>, cryptography@metzdowd.com
In-Reply-To: <p06240805c650b6976fa3@[10.20.30.158]>
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.
--
http://www.apache-ssl.org/ben.html http://www.links.org/
"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
