[RC5] RSA 576 broken

Ray Booysen rj_booysen at rjb.za.net
Fri Apr 30 08:37:21 EDT 2004


>
> 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.
-- 
Ray Booysen
rj_booysen at rjb.za.net


More information about the rc5 mailing list