[RC5] RSA 576 broken
elektron_rc5 at yahoo.ca
Fri Apr 30 12:14:43 EDT 2004
On 30 Apr, 2004, at 20:37, Ray Booysen wrote:
>> On 30 Apr, 2004, at 14:37, Christophe Evrard wrote:
>>> Interesting news on RSA website :
>> I'm currently wondering if that's vaguely possible. 100 computers for
>> months is 777600000 seconds, but there are roughly 2^280 288-bit
>> (since the 576-bit number is the product of two primes, one of the
>> primes must be less than 2^288).
> Of course it is. They don't try every single number. They used an
> algorithm called the GNFS (discussed below)
> Here is a good site to visit to see how it works.
> Quoting from the RSA site:
> The factoring of RSA-576 was completed using the general number field
> sieve factoring algorithm (GNFS) to gather data, find dependencies
> the data and ultimately leverage those dependencies to factor the
Calculating O for n=2^576 gives about 1.24e21, or 1.60e12 per second
per computer, which seems a little large (the O given in Wikipedia is
much, much larger, strangely).
The scary part? Factoring a 1024-bit number should only take about a
million times longer.
More information about the rc5