[RC5] RSA 576 broken

Elektron 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 :
>>> http://www.rsasecurity.com/company/news/releases/pr.asp?doc_id=3520
>>
>> I'm currently wondering if that's vaguely possible. 100 computers for 
>> 3
>> months is 777600000 seconds, but there are roughly 2^280 288-bit 
>> primes
>> (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.
> http://mathworld.wolfram.com/NumberFieldSieve.html
>
> 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 
> among
> the data and ultimately leverage those dependencies to factor the 
> number.

Hm.

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.

- Purr



More information about the rc5 mailing list