Slashdot Mirror

← Back to Stories (view on slashdot.org)

Factors Found in 200-Digit RSA Challenge

Posted by Zonk on from the really-big-numbers dept.

diodesign writes "The two unique prime factors of a 200-digit number have been discovered by researchers at Bonn University (Germany) and the CWI (Netherlands). The number is the largest integer yet factored with a general purpose algorithm and was one of a series of such numbers issued as a challenge by security company RSA security in March 1991 in order to track the real-world difficulty of factoring such numbers, used in the public-key encryption algorithm RSA. RSA-200 beats the previous record number 11281+1 (176 digits, factored on May 2nd, 2005), and RSA-576 (174 digits, factored on December 3rd, 2003)."

9 of 184 comments (clear)

  1. 55 CPU years by Inkieminstrel · · Score: 4, Insightful

    The article says it took 55 CPU years to factor the number, though they did it in parallel for about a year and a half. I'd hate to imagine the teams that we don't hear about who are, say, 30 CPU years into the problem who just found out it's already been done.

    1. Re:55 CPU years by 0x461FAB0BD7D2 · · Score: 4, Insightful

      Well, those teams could still pursue with their endeavors, hopefully beating the time used by these researchers.

      This would mean that their algorithm and/or heuristics is/are superior, which would be beneficial to everyone, including these researchers who "won".

      The good thing about research like this is that no one really loses.

    2. Re:55 CPU years by TedCheshireAcad · · Score: 4, Informative

      Another victory for the General Number Field Sieve (I think). The article was a little light on the details, but it mentioned they used a "general algorithm", which I'm assuming is the GNFS. The original paper may shed some light on the algorithm, for the algebraically inclined Slashdotter. (Link courtesty of Google Scholar)

  2. Waste of time! by Tom7 · · Score: 4, Insightful

    I think these RSA challenges are a waste of computer power. It's trivial to compute how much computing resources it will take to factor numbers using an existing algorithm on paper, and you get a more accurate estimate than you get from sampling experimentally. I'm all for the development of new, faster algorithms and implementations, but the challenge should be for the development and demonstration of these algorithms, not the brute-force months-on-end search that ensues.

    1. Re:Waste of time! by Anonymous Coward · · Score: 5, Insightful

      If someone claims to have found a better factoring method, then it's easier for RSA to check that p,q < n and p*q = n, than to read his algorithm and analysis and award a prize based on that. (Imagine how many crackpots would apply with 100 pages long "proofs").

    2. Re:Waste of time! by Vellmont · · Score: 4, Insightful


      It's trivial to compute how much computing resources it will take to factor numbers using an existing algorithm on paper, and you get a more accurate estimate than you get from sampling experimentally
      You can certainly make a decent estimate of how long it will take, but you're never going to get a close approximation of the real-world performance of your implementation until you actually write the code and run it.

      The other side is that theoretical calculations are nice, but there's nothing quite like actual verification. It's much easier for a programmer to justify using larger key lengths when someone has actually cracked smaller key lengths rather than using calculations based on estimates of computing power.

      --
      AccountKiller
  3. Re:Notation? by iMaple · · Score: 5, Informative

    Does anyone know what the notation "11281+1" means?

    It means 11282 :) .
    There seems to be a typo in the article post (A typo on slashdaot .. thats news ..I mean just one typo thats cool). Its probably due to some filter. It should say 11^281 +1

  4. I don't want to spoil the ending but... by fxer · · Score: 5, Funny

    ...the punchline is

    3,532,461,934,402,770,121,272,604,978,198,464,36 8, 671,197,400,197,625,023,649,303,468,776,121,253,67 9,423,200,058,547,956,528,088,349
    and
    7,925,869, 954,478,333,033,347,085,841,480,059,687, 737,975,857,364,219,960,734,330,341,455,767,872,81 8,152,135,381,409,304,740,185,467

    tip your waitresses! :)

  5. Real Discovery! by kenp2002 · · Score: 4, Interesting

    I have found a way to crack any code in a matter of minutes. It's simple!!! It works plenty of times!!

    Find out where the subject lives that encrypted the data. (1-3 days)

    Break into their home. (10 minutes)

    Look under their keyboard (1 minute)

    Read their private and public key off the notecard taped under the keyboard. (2 minutes.)
    Optionally: Steal the notecard and leave a fake one with the wrong key written down.
    Laugh maniacally... Done!!!

    To date when doing security sweeps at my various clients sites, 80% of staff have their password somewhere in their cube. 50% had their PGP keys under the keyboard, 10% had pen drives marked "Passwords" handing off a thumb tack on their cube wall. Who cares about better encyption, physical security (or perhaps mental security is a better choice) is where we need to focus.

    And remember network admins! Have you users spade or neutered :)

    --
    -=[ Who Is John Galt? ]=-