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"
Wow, I havn't really read in to it, but is that very big? I mean, they were talking about not too long ago that 128bit encryption is "almost impossiable" to break. If this is 576bit encryption, and they've broken it, doesn't this mean that 1024bit is looking slightly weak? Whats the 'difficulty' of breaking this key on a relative scale?
Chris
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.)
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.
Factoring composite is probably somewhat easier in the sense that it doesn't require more hardware/brute force computational power, however, its probably harder in the sense that you need to be very famillar with the very latest in factoring algorithms and essentially be skilled and willing enough to implement the very leading edge known algorithms.
In other words, factoring RC5-72 requires Moore's law, plus a massively growing audience of people willing to participate. But even with the most optimistic projections, RC5-72 will not fall for decades. Factoring something like RSA-574 requires that you be up on the latest in computational mathematics as it relates to number theory. If you think you can bone up on the latest in factoring techniques in less than 10 years, then you probably have a better shot at the RSA prizes.
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?
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
Here is the latest cipher with perfect secrecy, with an added assumption on the memory limits of the adversary.
The real threat is Shamir's TWIRL and TWINKLE optical factorization-assistance gadgets. They aren't necessarily a threat to 1024-bit keys, but they're a definite threat to 768-bit keys, and it's time to start thinking seriously about threat models before embedding 1024-bit limitations in hardware. That's probably big enough that only national governments are likely to be funding, rather than bank robbers and other Mafiosi.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Factoring RSA-2048 might considerably contribute to global warming due to computer activity. Got anybody an idea how big the temperature rise will be assuming the efficiency given by the RSA-576 challenge?
I still remember homework about a driver being stopped because he ignored a red traffic light. He claimed the light was green because of Doppler shift caused by high speed of the car. The amount of fuel required to reach this speed was by far higher than the total consumption by mankind.
There are no known ways to break currently acceptable symmetric cyphers (such as 3-DES and AES) faster than brute force
Just a quibble: you can actually break both 3DES and AES faster than brute force. In the cast of 3DES, there is a time/memory tradeoff, and AES has some key schedule weaknesses (though in the case of AES, you need to collect nearly the entire codebook before you can proceed with the attack (at least the one I'm thinking of)). Basically, you're right in practice, just not in theory; none of the (publicly known) attacks on 3DES or AES are remotely close to being practical in any sense of the word.
In any case, as the hardware makes it easier for the attackers, it makes it practical to go with longer encryption keys, so faster hardware is neither a help nor hindrance to attackers.
Actually, the win is probably for the defenders. Double the length of an RSA key, the encryptor has to do 3-4 times as much work, but the person trying to factor it faces an increase that is much, much larger.