Forgot your password?
typodupeerror
Encryption Security

RSA-576 Factored 321

Posted by michael
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"
This discussion has been archived. No new comments can be posted.

RSA-576 Factored

Comments Filter:
  • by Wigfield (730339) on Sunday December 07, 2003 @11:05PM (#7657006) Journal
    Ontday oyay inkthay osay?
    • I don't know... maybe...
      u sib;r jbiq (shifted all the keys to the left.)

      Seriously, though, all of these ciphers can be broken. It's just a task of minimizing the value to the cracker by making it take as long as possible to get the data, under the thought that it just won't be worth the time.

      • by wurp (51446) on Sunday December 07, 2003 @11:51PM (#7657237) Homepage
        Sure, all codes (except one time pads and equivalents) can be broken. The difference is whether it takes a day to crack the code or it can be proven that it requires either a centuries-sought breakthrough in mathematics or all the computers in the world working for ten thousand years.

        I don't know how you feel about it, but quantitative differences on those scales qualify as qualitative differences to me. Your 2048 bit PGP key simply isn't crackable by any reasonable standard. The reason people succeed at these challenges is because the bar has been set intentionally low.
        • by hank (294) on Monday December 08, 2003 @12:00AM (#7657272)
          They also set the bar at your "reasonable standard" - the factorization of a 2048-bit number brings in $200,000 USD.

          http://www.rsasecurity.com/rsalabs/challenges/fa ct oring/numbers.html
      • It's just a task of minimizing the value to the cracker by making it take as long as possible to get the data, under the thought that it just won't be worth the time.

        Why do people always assume that code-breakers will be White Guys?

    • Ontday oyay inkthay osay?

      otgay otay dmitaay tiay siay rettypay oodgay.

    • V guvax gurer fubhyq or n fynfuqbg frpgvba jurer nyy cbfgf unir gb or va EBG13.
      Guvf fvgr qbrfa'g yrg zr jnfgr rabhtu gvzr nf vg vf!

      And while we're on this kind of thing, does anyone know what the point of the UNIX command "rev" is? (as in "$ echo This is pointless | rev" -> sseltniop si sihT)? Why on earth does that come installed on Debian, and does every distro and UNIX variant use it?
    • by the_argent (28326) on Sunday December 07, 2003 @11:36PM (#7657178) Homepage
      Or my personal favorite....

      Double ROT13.

      Which incidently, is hereby covered under the DMCA, if you manage to decipher it will be fully procecutable under the fullest extent of the law.

  • by mcc (14761) <amcclure@purdue.edu> on Sunday December 07, 2003 @11:07PM (#7657014) Homepage
    I think that composite numbers everywhere will sleep just a little bit less securely tonight, knowing that the Bundesamt fur Sicherheit in der Informationstechnik is out there, somewhere, waiting for them.

    Yup.
  • Is 576bit big? (Score:3, Interesting)

    by The Real Chrisjc (576622) * <slashdotNO@SPAMamoose.com> on Sunday December 07, 2003 @11:08PM (#7657023) Homepage
    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
    • Re:Is 576bit big? (Score:5, Interesting)

      by cgranade (702534) <cgranade AT gmail DOT com> on Sunday December 07, 2003 @11:11PM (#7657042) Homepage Journal
      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.
      • by I Be Hatin' (718758) on Sunday December 07, 2003 @11:36PM (#7657179) Journal
        However, with Beowulf clusters and the new primability test, this is being offset

        Woop! Woop! Woop! Bush-ism alert! Bush-ism alert!

        Perhaps you meant primality?

      • Re:Is 576bit big? (Score:5, Informative)

        by dirtydamo (160364) on Monday December 08, 2003 @12:09AM (#7657301)
        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.


        For the n-th time...

        The new primality test has little practical value, because the previous testing algorithms, although probabilistic, are vastly faster in practice.

        Primality testing also has little to do with factorization algorithms.
      • Beowulf clusters aren't any threat to 1024-bit RSA - you're not going to put enough machines in a room to do the job, nor are you likely to put enough on the continent. On the other hand, for smart cards and cash machines and "export-approved" software with 512-bit keys in them, they're starting to really kick ass.

        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

      • Re:Is 576bit big? (Score:3, Interesting)

        by Just Some Guy (3352)
        However, with Beowulf clusters and the new primability test, this is being offset quickly.

        No, the biggest Beowulf won't put a dent in the bit length. Consider a 1024-bit prime being tested by a gigantic 65536- (2^16) node cluster. You've now reduced the problem so that each machine has a mere 1008-bit (1024-16) search space. Put another way, parallelization is relatively useless against exponential algorithms.

    • Re:Is 576bit big? (Score:4, Informative)

      by Sage Gaspar (688563) on Sunday December 07, 2003 @11:15PM (#7657064)
      Well, there is no uncrackable code. The idea is to make it as hard as possible. For each message transmitted using one of those keys, a potential codebreaker would have to dedicate however much time this team of professional scientists on powerful computers would take.

      As technology gets better, the level of encryption gets better with it. It's a constant battle. Of course, you're not going to want to make RSA your sole method of encryption and post the key all over the web if you're working on ridiculously top-secret government projects, but then again, you wouldn't want to rely solely on any type of encryption and you wouldn't be transmitting it openly over the Internet.
      • Re:Is 576bit big? (Score:3, Insightful)

        by mattjb0010 (724744)
        Well, there is no uncrackable code

        except for a correctly used one-time pad.
    • Re:Is 576bit big? (Score:5, Interesting)

      by Ageless (10680) on Sunday December 07, 2003 @11:19PM (#7657090) Homepage
      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.
      • Re:Is 576bit big? (Score:2, Insightful)

        by LnxAddct (679316)
        not too mention that currently factoring a 512 bit key will still take months, if not years. If someone is willing to put all that money and effort into cracking your key then you've got worse problems on your hands, I'd recommend buying a gun. My point is that just because one key was factored of that length, doesn't mean it is all the sudden faster or easier, it just means that a group of people put alot of effort, money, and thinking into one number and were able to factor that one number. They can't go
      • > Those people could be concerned at this point that
        > their old messages could be cracked.

        Who would want to spend zillions of hours of computer time to read some geek's old messages?

        "Great news, today I have finally managed to install the latest 0.99.1 kernel and boy is it great! I'm so glad I picked SLS instead of slackware, whose installer sucks big time. With my beloved SLS all I had to do was swap four floppies in and out and everything works beautifully! No crashes yet. I never realized how muc
    • Re:Is 576bit big? (Score:3, Informative)

      by damiam (409504)
      No. RSA encryption, and public-key encryption in general, uses significantly higher keysizes to attain the same security as private-key cryptosystems at lower keysizes. The difference is that, in a public-key cryptosystem, two parties can talk securely without already both knowing a secret key.

      128-bit private-key encryption is virtually impossible to break, because you'd have to test every single 128-bit number. 576-bit public-key encryption is much easier, because you don't have to test every possible key

    • Re:Is 576bit big? (Score:5, Informative)

      by Stephan Schulz (948) <schulz@informatik.tu-muenchen.de> on Sunday December 07, 2003 @11:24PM (#7657117) Homepage
      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?
      There is a different between keys for symmetric encryption algorithms like DES, 3DES, Blowfish, and keys for asymmetric (public key) algorithms like RSA and Diffie-Hellman. Symmetric 128 bit keys are still considered safe. 1024 bit asymetric keys are safe for the moment - I belive for long-term security sensitive applications, 2048 bit keys are recommended nowadays. Here [digitalenterprise.org] is a table comparing the cost of breaking (well, brute-forcing) symmetric and asymmetric cyphers for a given key lenght.

      My PGP key is still 1024 bits, and I don't break a sweat.

      • You can get away with much shorter key sizes using elliptic curve methods. Currently reccomended sizes are at least 80 bits for a symmetric key and 160 bits for an asymmetric key.
    • Re:Is 576bit big? (Score:5, Informative)

      by Fnkmaster (89084) * on Sunday December 07, 2003 @11:25PM (#7657127)
      128-bit encryption generally refers to key size in symmetric encryption algorithms, like 3DES, IDEA, etc. These encryption methods generally are broken by brute force searching a 128-bit space of keys - that means you have to check on the order of 2^128 different keys until you know if you've found the right one (obviously, this assumes that there are no fundamental cryptographic weaknesses in the algorithm, known-plaintext attacks or other stuff like that).


      Assymmetric encryption algorithms, like RSA, rely on a hard problem with two parts needed to reconstruct the solution. In the case of RSA, those two parts are a large composite number with precisely two prime factors, and one of the prime factors (without one of the prime factors, finding out the other prime factor is deucedly difficult). Basically to "crack" RSA you have to factor the large composite number into its two prime factors. With RSA, the keysize refers to the size, in bits, of the composite and prime numbers you're working with. The thing is that you don't have to search an entire 512-bit keyspace to crack a 512-bit RSA key, you just have to try every reasonably possible _prime_ number that might be a factor of that 512-bit composite. And actually, you don't even really have to do that, since there are substantially better techniques for factoring numbers than brute force, requiring less computational effort.


      So that, my friend, is why comparing "128-bit" encryption to "512-bit" or "1024-bit" RSA or other assymmetric encryption techniques (which are similar but rely on numerical problems other than factoring large numbers) isn't terribly meaningful.

    • Re:Is 576bit big? (Score:2, Interesting)

      by FU_Fish (140910)
      You may be comparing two different types of encryption. For block algorithms such as DES and AES, 128 bit is still fairly reasonable, however not for RSA (and other public key algorithms). Currently, 1024 bit RSA is considered reasonably secure and 576 is, as we can clearly see, quite insecure. I won't go into the details of why different algorithms need such drastically different key sizes here, but if you'd like to know more, the Crypto-FAQ [rsasecurity.com] is a good place to start.
    • by Goonie (8651) * <robert DOT merkel AT benambra DOT org> on Sunday December 07, 2003 @11:44PM (#7657210) Homepage
      I'm not an expert, but IIRC you're talking about apples and oranges here.

      When 128-bit cyphers are described as "secure", they're almost certainly talking about symmetriccyphers - that is, the key you use to encrypt the message is the same as the key you use to decrypt the message. There are no known ways to break currently acceptable symmetric cyphers (such as 3-DES and AES) faster than brute force - that is, trying each key one at a time. If you have a 128-bit key, this will on average take (2^128 / 2 = 2^127 ~= 10^38) tries before you get the key. This will take billions of years to do, even using a massively parallel computer.

      The other sort of encryption, the sort we are talking about here, is public-key encryption, where you use two different keys to scramable and descramble the message. The advantage of this method is you can create a key pair, and give one key to everyone who wants to send you a message (the public key), and while they can send you message securely, it is very difficult for them to figure out your private key (and thhus read messages other people have sent you).

      The bad news with public-key encryption is that the algorithms are considerably weaker than with secret-key cyphers. You can mount considerably quicker attacks than just brute-forcing the keyspace. Therefore, you need longer keys for equivalent levels of security. With RSA, the most common method, figuring out your private key from your public key is done by trying to figure out the factor of a very, very large number that is the product of two very large prime numbers. This is still very difficult to do, but it is a simpler problem than brute-forcing an entire keyspace. These Germans have just demonstrated the ability to factor a larger such number than anyone else has done before.

      Whilst this is interesting, from what (little) I understand of cryptography it's still a very long way from here to cracking 1024 bit RSA keys. 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. The one proviso is, of course, the security of data encrypted by older cyphers.

      • by randombit (87792) on Monday December 08, 2003 @08:17AM (#7658667) Homepage
        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.
    • Re:Is 576bit big? (Score:3, Informative)

      by mage_naes (730698)
      This represents a significant improvement on the previous factorization record. I show the following as the current top 10 hardest factorizations:

      RSA-576 2003 1881 C174=P87*P87 GNFS Bahr/Franke/Kleinjung/Montgomery/te Riele/Leclair/Leyland/Wackerworth
      RSA-160 2003 2152 C160=P80*P80 GNFS Bahr/Franke/Kleinjung/Lochter/Bohm
      2^953+1 2002 3950 C158=P73*P86 GNFS Bahr/Franke/Kleinjung
      RSA-155 1999 1094 C155=P78*P78 GNFS te Riele/CWI et al.
      Code Book 2000 1074 C155=P78*P78 GNFS Almgre
  • That's Easy (Score:4, Funny)

    by paul248 (536459) on Sunday December 07, 2003 @11:10PM (#7657035) Homepage
    Look! I did it too!

    1 2 3 4 6 8 9 12 16 18 24 32 36 48 64 72 96 144 192 288 576
  • by silentbozo (542534) on Sunday December 07, 2003 @11:10PM (#7657041) Journal
    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.)
  • Mersenne Primes (Score:2, Informative)

    by penguinoid (724646)
    Mersenne primes [wikipedia.org] are a number of the form 2^n - 1, where n is some prime number. Mersenne primes are one of the easiest to find, and there is a quick (relatively) algorithm for checking whether it is prime. Not all Mersenne numbers are prime.
  • Reaction (Score:5, Funny)

    by Angram (517383) on Sunday December 07, 2003 @11:15PM (#7657066)
    I think I speak for 99% of the population when I say...

    "Oh."
  • Cheaters! (Score:3, Funny)

    by Anonymous Coward on Sunday December 07, 2003 @11:15PM (#7657067)
    They probably just looked in the back of the book.
  • Now there needs to be cash prize for discovering the discoverer when the challenge has been met. I just checked that site today.
  • Oh no... (Score:5, Funny)

    by RSA-576 (730686) on Sunday December 07, 2003 @11:28PM (#7657141)
    How could they *factor* ME without *my* own knowledge?! Somebody call the doctor... -RSA-576
  • Notify RSA (Score:5, Informative)

    by TheRedHorse (559375) on Sunday December 07, 2003 @11:28PM (#7657142)
    In order to win the prize, you must submit your result to RSA, they don't actively seek out winners. That's why RSA's page hasn't been updated.

    They can submit their answer here [rsasecurity.com].
  • Germany? (Score:5, Interesting)

    by gr8_phk (621180) on Sunday December 07, 2003 @11:34PM (#7657169)
    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?
    • Took 4 days for word to get to Slashdot, maybe. Mathpuzzle.com reported [mathpuzzle.com] this 3 days ago.
  • by product byproduct (628318) on Sunday December 07, 2003 @11:39PM (#7657187)
    They're busy multiplying the two 87-digit factors by hand, just to be sure.
  • Awww (Score:5, Funny)

    by JDWTopGuy (209256) on Sunday December 07, 2003 @11:39PM (#7657189) Homepage Journal
    Crap, there go my plans to factor it myself.
  • by Proudrooster (580120) on Monday December 08, 2003 @12:38AM (#7657411) Homepage
    And I quoth from the article:
    3980750 8642406493 7397125500 5503864911 9906436234 2526708406 3851895759 4638895726 1768583317
    x
    4727721 4610743530 2536223071 9730482246 3291469530 2097116459 8521711305 2071125636 3590397527
    which can easily be multiplied to verify that they do indeed give the original number.


    Does anyone have a calculator that can "easily" multiply these two numbers... Holy Cow!
    • I think you were typing on one a minute ago.
    • Try GNU bc:

      39807508642406493739712550055038649119906436234252 6708406385189575946388957261768583317 * 47277214610743530253622307197304822463291469530209 7116459852171130520711256363590397527

      188198812 92060796383869723946165043980716356337941738270076 33564229888597152346654853190606065047430453173880 11303396716199692321205734031879550656996221305168 759307650257059

      See? That was easy enough. And it would have been even easier if i hadn't had to remove all those spaces you put in there! :)

    • Does anyone have a calculator that can "easily" multiply these two numbers...

      A pencil and paper seem to do a great job at storing the values for calculation. As for actually carrying out the calculation, that's what your brain cells are for.

      They said "easily". They didn't say "quickly". :-)
    • by Ageless (10680) on Monday December 08, 2003 @12:56AM (#7657476) Homepage
      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
      • In python:

        print 39807508642406493739712550055038649119906436234252 6708406385189575946388957261768583317 * \
        47277214610743530253622307197304822463291469530209 7116459852171130520711256363590397527

  • I don't see anything about how long it took them! I do know that RSA-155 took 7 months of computation to break...
  • by Anonymous Coward on Monday December 08, 2003 @12:53AM (#7657465)
    not being the math wiz that most /.ers are I was wondering what this meant for me...I found the below statement on RSA's FAQs and it answered my question that I'm sure many here like me have..
    ***************
    What does it mean when a Challenge Number is factored?

    Users of the RSA public-key cryptosystem may wonder what the factoring of a challenge number implies about the security of their keys. Should they immediately replace their keys with larger ones? Should they stop using RSA altogether?

    Clearly, the factoring of a challenge-number of specific length does not mean that the RSA cryptosystem is "broken." It does not even mean, necessarily, that keys of the same length as the factored challenge number must be discarded. It simply gives us an idea of the amount of work required to factor a modulus of a given size. This can be translated into an estimate of the cost of breaking a particular RSA key pair.

    Suppose, for example, that in the year 2010 a factorization of RSA-768 is announced that requires 6 months of effort on 100,000 workstations. In this hypothetical situation, would all 768-bit RSA keys need to be replaced? The answer is no. If the data being protected needs security for significantly less than six months, and its value is considerably less than the cost of running 100,000 workstations for that period, then 768-bit keys may continue to be used.

    Applications that require longer-term security or have data with a high financial value should migrate to longer keys before the factoring of the corresponding challenge number is announced. In either case, the results of the Factoring Challenge provide real data to help the cryptosystem user choose the appropriate key size.

    RSA Laboratories' Frequently Asked Questions About Today's Cryptography provides more information on choosing RSA key lengths for various applications. RSA Laboratories Bulletin #13 discusses key length requirements for various cryptosystems.
    ***********************
    And honsetly I think for most people the idea of someone devoting a cluster of computers just so they can read some documents you may have on your hard drive kindof egotistical for the end user...but hey we all know that the NSA breaks every key they can right?...even ones from people just trying to protect their data from average joe hackers...
  • by Multics (45254) on Monday December 08, 2003 @01:10AM (#7657515) Journal
    Perhaps I should submit this as an Ask Slashdot instead of a comment here, but what happens when the quantum computers make breaking these things easy? (I'll leave out the word trivial since I can't imagine quantum computing being trivial anytime soon.)

    What will be the face of the next from of Crypto? Only one-time pads? That sounds way painful.

    -- Multics

    • by freuddot (162409)
      > but what happens when the quantum computers
      > make breaking these things easy?

      People start using quantum cryptography. There already are commercial products offering you unconditial security, based on quantum computing, whereas the quantum computer is not ready to factor anything larger than 21...

      J.
    • by billstewart (78916) on Monday December 08, 2003 @02:29AM (#7657773) Journal
      Quantum computers are too speculative at the moment, but they're the main new threat to near-exponentially-strong crypto algorithms. (Moore's law is theoretically a problem, but it can only continue for so long, and theoretical breakthroughs in the mathematics of factoring or a constructive proof of P=NP don't sound likely but could happen.) But they need to have a really high resolution to be any real threat at all - the Heisenberg limit of ~10**-47 only gets you ~150 bits, so you need to have large numbers of separate qubits coupled together to a be useful, rather than one highly-precise device.

      For symmetric algorithms, like the DES family, at most they're expected to cut the number of bits of algorithm strength in half, so instead of 3-DES you might need to use 5-DES or 7-DES, which is only a minor annoyance. For key distribution, it does mean returning to systems based on key distribution centers, like Kerberos. That's a big loss of functionality, unless we find asymmetric algorithms that quantum computing can't break. I'm not aware of any results on whether elliptic curve algorithms are susceptible to Quantum Computers, though it's possible that that could also happen.

    • by Ibag (101144) on Monday December 08, 2003 @04:16AM (#7658030)
      Actually, if you assume that quantum computing becomes main stream and people have enough qbits to factor large numbers (It was only like a year ago that IBM built a 7 qbit computer and implemented Shor's algorithm to factor 15), then you have one time pads being very possible.

      One of the nice things about quantum computing is that you can send a message to someone and tell if anybody intercepted it. Therefore, you can send one time pads until one gets through without being viewed. Once you have a one time pad, you can encrypt your message and send it fairly easaily using conventional means.

      Of course, I don't know what will happen with things like authentication which rely on public key schemes. I don't believe that eliptic curve encryption methods have an easy attack from quantum computing, but I don't know enough to say that they can be used for anything but encryption.
    • I use LJ-5, which I believe to be sufficently safe.

      No-one is going to wade through 5 pages of a Live Journal blog to find my secrets.

A committee is a group that keeps the minutes and loses hours. -- Milton Berle

Working...