Slashdot Mirror

← Back to Stories (view on slashdot.org)

RSA-576 Factorization Officially Announced

Posted by timothy on from the what-google-does-in-its-spare-time dept.

product byproduct writes "RSA Security finally has a news item about the December 2003 factorization of RSA-576. (See earlier Slashdot coverage). We now know what the computational cost was: the 174-digit number was factored "using approximately 100 workstations in a little more than three months"."

9 of 141 comments (clear)

  1. Lots of hardware... by basil+montreal · · Score: 5, Insightful

    That's a ton of computer hardware to use on factoring... I wonder why they didn't just use a distributed system (like seti@home) to do this... at least it's free.

    1. Re:Lots of hardware... by ezzzD55J · · Score: 5, Interesting

      Because it's difficult to efficiently parallelize (distribute) the factorisation algorithm, especially the final step which so far has always happened on 1 machine. In fact, if you can paralellize the final step of the GNFS (general number field sieve is generally used for these factorisations), you have yourself a PhD. thesis (in math and/or CS), I remember reading in sci.crypt.

  2. Still safe for a while by BuddieFox · · Score: 5, Interesting

    We should still be reasonably safe using the RSA-algorithm for a while more since the number is the equivalent of a 576-bit key. Most cryptography programs support upto 4096-bit keys, and the strength of a key increases exponentially for every bit if my memory does not fail me (correct me if it does).

    Safe, that is unless someone invents quantum computers and makes them easy to produce.. :)

    1. Re:Still safe for a while by Ckwop · · Score: 5, Interesting

      Also remember the moore's law doesn't apply to factoring algorithms.. This is because for the GNFS the *memory* speed is what's important and that isn't growing nearly as quickly..

      Not convinced? Look at the linear proportionality in this graph

      Simon.

    2. Re:Still safe for a while by thedanc · · Score: 5, Informative

      Bear in mind, using bits to exponentially increase cryptographic strength only works until you reach the Berenstein factor, which is a practical limit on the number of S-boxes that can be stacked in any particular corner of the cryptographic chamber. After a certain point, which varies according to the chamber ceiling, it is possible albiet less space efficient to take advantage of parallel stacking to some extent.

      Mods -- how could you let this get modded up? First, S-boxes are in DES, not RSA. Next, even if the random reference was to the correct cryptographic algorithm, the rest of the comment still makes no sense at all.

      C'mon people, post if you have a clue, and only if you have a clue.

  3. Security by nuclear305 · · Score: 5, Insightful

    Of course, the whole idea behind key strength is rather moot if the user gets careless with his keys/passphrase.

    Unfortunately, crypto is only as strong as the user(weakest link)

    While it's not always comforting to know these things can be factored, at least we can take comfort in knowing that *most* hackers/spooks don't exactly have a 100 node server farm laying around just dying to crack your keys.

    Of course, unless you're the NSA and measure their servers by acres...

  4. Hundred computers * 3 months by Gopal.V · · Score: 5, Interesting

    That makes it 240000 computer hours ... too cheap .. Think about this :

    "Toy Story 2" had about 800,000 computer hours worth of rendering.
    "The Hulk" had 2.5 Million computer hours
    My office has nearly 400 fast machines , imagine this running them makes it 25 days . Running that every weekend makes it 12 weeks or 3 months ... It's a weekend job if I can sneak this in as along with the next upgrade.

    DDoS time is over with all networks being careful about... the next big windows worm will be a distributed processing program :)

    --
    Quidquid latine dictum sit, altum videtur
  5. Re:Factoring in advance by tadmas · · Score: 5, Insightful

    You won't know the number you need factored until you intercept or steal the encrypted data.

    You don't have to steal anything. The number to factor (the modulus) is given away as part of the public key.

    organise a database of the results but the storage - even if you just store some sort of clue to the primes used - would be staggering, even for just 1024-bit RSA.

    For 1024-bit numbers, the factors will be on the order of 512-bits. The density of primes is rougly 1/ln(n), and ln(2^512) is about 355, so you should expect around every 355 numbers to be prime. That's only 3e151 numbers, not to mention that you'd have to figure every product of the two, which is 0.5*(3e151)^2, or 7e302 numbers.

    Staggering doesn't begin to describe how many of these things you'd have to store.

  6. Jens Franke by greppling · · Score: 5, Interesting
    (As far as I understand, he and Thorsten Kleinjung wrote most of the software used, and did most of the work in the project, while the other institutions were rather donating computing time.)

    I happen to know him a little, as one of my friends is his student, and another one was. If you think mathematicians are crazy, Franke is more than that. When you talk to him, he will usually just continue to stare at the piece of paper he has directly in front of his eyes (Nobody knows why he isn't wearing glasses.) and think of that as a normal way of communicating. His office consists of 3 huge desks (plus a computer desk); on each of them there is huge bunch of completely unorganized papers lying around, mixed with empty yoghurt cans.

    His mathematical skill is enormous, he has done research in quite a lot of different areas of mathematics (analysis, algebraic geometry, algebraic topology, category theory), but he never bothers at all with making his results well-known. (In fact, at least one time he actually had to be persuaded to even publish his result, which got immediately accepted in Inventionaes, the most highly regarded journal in pure mathematics.) He even couldn't be bothered to apply for a much better-payed position at another university in Germany when he was almost urged to do so.

    Anyone who knows him will burst out laughing when he reads that he supposedly said "I'm very proud of all these individuals from around the world and their efforts to solve this first factoring challenge." and all this other stuff in that paragraph of the article. I bet the author of this press release desperately tried to get some phrases longer than 5 words out of his mouth, gave up, and then decided to just make up all the quotes.

    Now with his mathematical skills, number factoring is (in his own opinion) a rather dull activity. The reason he is doing this is that he expects an economic breakdown soon, and he thinks of his knowledge in number-factoring as an assurance against the coming job crisis. (Of course, his position is guaranteed by the German state until his retirement.)

    But if you manage to get along with him, he is actually quite nice and extremely helpful.