[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