Slashdot Mirror
RSA-576 Factored
An anonymous reader writes "I thought Slashdot would have picked this up
several days ago, but apparently not. Although
you still won't see any mention of it on the
RSA challenge site, Mathworld is carrying the news that a team at the German Bundesamt fur Sicherheit in der Informationstechnik submitted a factorization of
RSA-576 on December 3. RSA-576 is the smallest challenge number that RSA Security offers a cash prize for, to the tune of $10,000"
Does anyone know the relative computational difficulty of cracking RC5-72 vs. trying to factor one of the RSA numbers? Given the higher monetary payoff, I'm wondering if I wouldn't be better off implementing and running a prime factor sieve, rather than running the RC5 client (which only runs on my W2k workstation, because the distributed folks never rewrote the older cores that run on my pre-OSX Macs.)
It should go up exponentially, so that 1024 is much more than twice as hard. However, with Beowulf clusters and the new primability test, this is being offset quickly.
#define DRM chmod 000
the 40th Mersenne prime has been discovered 2-3 weeks ago and just proven to be correct. See http://www.mersenne.org/history.htm for more info.
When people talk about 128 bit encryption being hard to break they are talking about symmetric algorithms such as Blowfish. A 128 bit symmetric algorithm is still very, very tough to crack a key for.
This particular challenge is for the RSA algorithm which is an asymmetric algorithm. They require much longer keys to be secure. Right now most people recommend at least a 2048 bit key for RSA and plenty of people are using 4096 bit keys.
Comparativly, it should be a long, long time before anyone is worried about their current keys. Back in the day when PGP came out, it was fairly common for people to use a 512 bit key with RSA, but most used 1024. Those people could be concerned at this point that their old messages could be cracked.
I'm not suprised that someone has done it. Even the RSA site suggested 576 would fall soon. What I do find interesting is that it took 4 days for word to get out, and that the factorization was done in Germany. More interesting would be knowing what algorithm was used - is it new, or just further refinement of GNFS or MPQS with faster hardware?
RSA has been the defacto standard for public key exchange since it came around. PGP was based on it, and if I remember correctly that's all it supported for a long time. RSA is still a very strong algorithm and has a few benefits over ElGamal. The main reason that people wanted to switch from RSA to something else was that until September of 2000 RSA was covered under a patent and required royalties to use.
I'm sure Slashcode will eat this Java source for lunch, but here we go.
1 19 9064362342526708406385189575946388957261768583317" );
4 63 2914695302097116459852171130520711256363590397527" );
0 716356337941 73827007633564229888597152346654853190606065047430 45317388011303396716199692321205734031879550656996 221305168759307650257059
import java.math.*;
public class Calculator
{
public static void main(String[] args)
{
BigInteger x = new
BigInteger("39807508642406493739712550055038649
BigInteger y = new
BigInteger("47277214610743530253622307197304822
BigInteger z = x.multiply(y);
System.out.println(z.toString());
}
}
[c:\temp]\j2sdk1.4.2_01\bin\javac Calculator.java
[c:\temp]java Calculator
1881988129206079638386972394616504398