Slashdot Mirror

← Back to Stories (view on slashdot.org)

RSA-640 Factored

Posted by ScuttleMonkey on from the bigger-better-deal dept.

gslin writes to tell us MathWorld News is reporting that RSA-640 has been factored. F. Bahr, M. Boehm, J. Franke, and T. Kleinjung, memebers of the German Federal Agency for Information Technology Security (BSI) announced they had cracked the 193-digit number last Friday using the General Number Field Sieve. The team purportedly used 80 opteron CPUs and 5 months to achieve victory.

6 of 299 comments (clear)

  1. Re:Hmmm. by LnxAddct · · Score: 5, Interesting

    While I think your remark was a joke about them breaking into RSA's computers, this is still worth mentioning. Noone in the entire world knows or has ever known the factors of the remaining numbers. Read this for more info.
    Regards,
    Steve

  2. I'll wait for RSA-2048 by Myria · · Score: 3, Interesting

    I won't be interested until they do RSA-2048. Then we could factor the Xbox private key and do whatever we want.

    Melissa

    --
    "Screw Sun, cross-platform will never work. Let's move on and steal the Java language." - Visual J++ Product Manager
  3. Re:Irrelevant by cpeikert · · Score: 3, Interesting

    What did I write that is inconsistent with the wikipedia entry?

    "Integer factorization is widely suspected to be outside both of those classes [NP-complete and co-NP-complete]."

    Just because a problem is outside P, doesn't mean it's NP-hard. Which is exactly what I said to start with.

  4. Re:Factor? by jgc7 · · Score: 5, Interesting

    Inerestingly enough, there is no proof that encryption is even possible. Presently we do not know of any methods to factor a number in polynomial time while we can create primes in polynomial time, but an algorithm may exist that can factor primes in polynomial time. If one is discovered, encryption as we know it today will be impossible... even with your quantum computer. In fact, a solution to the P NP problem comes with a $1,000,000 prize.

    --
    70% of statistics are made up.
  5. Recommended key sizes by atomm1024 · · Score: 4, Interesting

    Here is a very useful site, listing estimates of how long various algorithms will be secure, and at what key sizes. It covers public- and secret-key algorithms, as well as hashes.

    http://www.keylength.com/

    --
    Signature.
  6. Re:How does this compare to RC5-64? by swillden · · Score: 3, Interesting

    So you are trying to compare numebrs that simply cannot be compared.

    Well, you can compare them, but you have to factor in the relationship between the complexity of the attack and the keysize in each case. In the case of RC5, brute force search of the keyspace is O(2^n) where n is the size of the key in bits. As a previous post mentions, the GNFS algorithm's complexity is O(e^(1.9229+O(1))*ln(n)^(1/3)*ln(ln(n))^(2/3)), where n is the number to be factored.

    So to compare the complexity of these two attacks you just need to see if 2^64 is larger or smaller than e^(1.9229*ln(2^640)^(1/3)*ln(ln(2^640))^(2/3)).

    Unless I made a mistake, the complexity of RSA-640 is about 5.5e13, whereas RC5-64 is about 1.8e19, so RC5-64 is approximately 300,000 times harder than RSA-640. I'm not sure that GNFS is as easy to massively parellelize as RC5 searching, though, so in practice RSA-640 may be harder than RC5-64, even though it has lower complexity. Also, big-O complexity ignores constant multipliers, so if each step in the GNFS algorithm is, say, a million times more complex than each RC5 trial encryption, than RSA-640 may actually be three times as hard as RC5.

    Okay, so maybe you can't compare them :-)

    --
    Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.