Slashdot Mirror

← Back to Stories (view on slashdot.org)

Probable Solution Found for ECC2-109 Challenge

Posted by CowboyNeal on from the waiting-for-the-photo-finish dept.

kpearson writes "The eCompute ECC2-109 distributed computing project discovered a probable solution to Certicom's ECC2-109 challenge today. The challenge was to defeat a 109-bit Elliptic Curve Cryptosystem (ECC). Since the eCompute ECC2-109 project began on November 8, 2002, 1,981 volunteers have run the project's software and found almost 40.5 million distinguished points. From those points the project found two which matched and caused a collision, enabling the project to find a solution to the ECC. The solution was submitted to Certicom this morning for verification."

8 of 130 comments (clear)

  1. Really hard to understand for someone by after · · Score: 5, Interesting
    At least for me, I never heard of this ECC-109 method before. The summery clears it up though.
    Project Overview

    This is a distributed computing project to solve the Certicom ECC2-109 challenge.In general it can be described as a whole lot of computers from all over the world, all of them working together in an attempt to have a collision. Each of the computers runs a program that computes DP (Distinguished Points) values. Each time a computer finds a DP, it is uploaded to a main server. The main server then checks to see if anyone has uploaded a matching DP (this is known as a collision). If a collision happens (two matching DP values exist), then the Certicom challenge is solved!


    Yea ... but what practical use does this have? Was this done _just_ because it could have been done?
    1. Re:Really hard to understand for someone by MBAFK · · Score: 2, Interesting

      "Was this done _just_ because it could have been done?"

      Reading around it seems that the idea is to prove that the encryption method is good rather than just theoretically sound. Probably makes it easier to sell stuff based on ECC if you can show how hard it is to crack.

    2. Re:Really hard to understand for someone by LostCluster · · Score: 3, Interesting

      I'm not sure the government has more efficient algorithms for most of the commerically-used encryption schemes... I seriously doubt the government has encryption-busters publishing classified theory discoveries that we don't know about.

      However, they most certainly have the resources to create a reduced instruction set processor dedicated to breaking an instance of a popular encryption scheme, and the ability to buy lots of such to build a supercomputer.

    3. Re:Really hard to understand for someone by lightspawn · · Score: 2, Interesting

      I think it's enough to say the theory is proven... no number of bits of security is ever going to be "enough" to be uncrackable

      Pet peeve: You can't prove something is always true by providing anecdotal evidence - but you can disprove it.

      Anyway, to the main point: you live in a universe with a finite number of particles and a finite TTL (physics majors are welcome to argue if they want). Or let's put it this way: The total amount of resources available to humanity is limited. Given that, there are problems that, although possible to solve in theory, are impossible in practice - take, for example, the problem of playing perfect chess by fully computing the game tree. With enough bits encryption becomes unbruteforcable too. And most secrets themselves really have a TTL of only a few years or decades and there's no point in trying to protect them any longer.

      So while a "Digital Fortress"-style theoretically uncrackable encryption may not be possible, practically uncrackable encryption certainly is.

  2. Question for the more cryptically inclined crowd: by jamonterrell · · Score: 5, Interesting

    I understand finding a collision (two things that when crypted yield the same result) is considered a goldmine in breaking an encryption algorithm.

    How does finding a collision help break the encryption? Does anyone know the technicalities of why this allows you to break an encryption algorithm, to me, who has no clue, this seems just like a coincidence and not very useful, but i'd like to be enlightened.

    --
    I can count to 1023 on my hands. Ask me about #132.
  3. Re:This reminds me of a Bob Newhart sketch by kpearson · · Score: 2, Interesting

    Believe it or not, there is a distributed computing project for this, too: the Monkey Shakespeare Simulator. So far the best the virtual monkeys have done is the first 14 letters from "Coriolanus."

  4. Some answers, maybe.... by crypto257 · · Score: 5, Interesting

    The purpose of all these challenges is to understand how much computing power is necessary to break encryption or signature schemes. EC109 strength is pretty low, but offer a way-point on the curve. Distinguished points are not really distinguished. They just have an easy search pattern such as a number of trailing zeroes or other constant values. These are searched ad-infinitum and when two matches are found, a little math can get you a private key. The death nell for the DES algorithm was heard when distributed.net, in cooperation with the Electronic Freedom Foundation built a machine that could crack it in 27 days (or so). And the cost made you wonder who might want to build such machines. As a result, we have AES and expanding public key lengths. No-one would really use ECC 109 for current cryptographic systems. The results from this test confirms that. The real question is what is the appropriate key length for a The amount of money (n computers over t time) tells us what sort of advisaries these techniques are useful against. It also

  5. Uh... November 2002? by 1000StonedMonkeys · · Score: 3, Interesting

    Okay, so why does the linked webpage indicate that the 109 challenge was Completed in November of 2002?