[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.

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