Slashdot Mirror

← Back to Stories (view on slashdot.org)

RSA-576 Factored

Posted by michael on from the long-division dept.

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"

9 of 321 comments (clear)

  1. Is 576bit big? by The+Real+Chrisjc · · Score: 3, Interesting

    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

    1. Re:Is 576bit big? by cgranade · · Score: 4, Interesting

      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

    2. Re:Is 576bit big? by Ageless · · Score: 5, Interesting

      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.

    3. Re:Is 576bit big? by Ageless · · Score: 4, Interesting

      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.

  2. Hmmm. Complexity vs. Cash by silentbozo · · Score: 4, Interesting

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

  3. Re:Mersenne Primes by millette · · Score: 4, Interesting

    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.

  4. Germany? by gr8_phk · · Score: 4, Interesting

    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?

  5. Re:Easily Multiplied Numbers !!?? by Ageless · · Score: 4, Interesting

    I'm sure Slashcode will eat this Java source for lunch, but here we go.

    import java.math.*;

    public class Calculator
    {
    public static void main(String[] args)
    {
    BigInteger x = new

    BigInteger("398075086424064937397125500550386491 19 9064362342526708406385189575946388957261768583317" );
    BigInteger y = new

    BigInteger("472772146107435302536223071973048224 63 2914695302097116459852171130520711256363590397527" );
    BigInteger z = x.multiply(y);
    System.out.println(z.toString());
    }
    }

    [c:\temp]\j2sdk1.4.2_01\bin\javac Calculator.java

    [c:\temp]java Calculator
    18819881292060796383869723946165043980 716356337941 73827007633564229888597152346654853190606065047430 45317388011303396716199692321205734031879550656996 221305168759307650257059

  6. Re:Symmetric vs. public-key cyphers... by randombit · · Score: 3, Interesting

    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.