Elliptic Curve Discrete Logarithms: ECC2K-108

Brought to you by:

Robert Harley	Damien Doligez	Daniel de Rauglaudre	Xavier Leroy

Up to the ECDL Project front page.

SOLVED on April 4th 2000!

The answer is 47455661896223045299748316018941 modulo 324518553658426701487448656461467.

Press releases:

By 4K-Associates (English, ZOT Group copy),

By INRIA (English, French),

By Certicom (English).

The biggest public-key crypto crack ever has just finished! Certicom have confirmed that the solution is correct. There is press coverage by:

• Slashdot,
• National Post,
• ZDNet,
• Impress (Japanese),
• Developer.com,
• Yahoo,
• Crypto-News (French),
• Punto Informatico (Italian),
• NyTeknik (Swedish),
• Europe 1 (French radio),
• TF1 (French TV),
• M6 (French TV),
• Yahoo France,
• Dr. Dobb's Journal,
• InfoWorld,
• Micro Hebdo (French),
• Science & Vie Micro (French),
• Info PC (French),
• Le Figaro: on 26th April -- numéro du 26 avril, section multimédia,
• LinuxGram,
• PCeXtremist.com,
• RFI (French radio): on 13th May -- émission Microméga du 13 mai,
• SecuriNews (French),
• Open Source IT,
• Veron@ quotidiano (Italian),
• Computerworld Rossiya (Russian),
• AsiaBizTech.

Others include Agence France Presse, La Tribune, Le Républicain Lorrain, L'Ardennais, HPCwire...

A useful fact-sheet. A technical FAQ. Certicom's page about ECC2K-108.

Everybody who was running the ECDL client can stop it now, and perhaps join one of these other interesting projects. Note: The CABAL773 project is now finished.

Calling all users of free and open-source software!

The plan:

• Solve part of Certicom's ECC challenge.
• Win $10000 and give most of it to the Apache Software Foundation.
• Um, that's it.

We've got some awesome machines and are capable of solving big problems if a large enough percentage of us are mobilised. We have solved the first seven problems in the Certicom ECC challenge, but this next problem is by far the hardest yet.

For comparison: it requires roughly 150% as much computation as a DES crack, which is much more than the recently completed RSA-155 factorisation. But we use an interesting parallel algorithm like the RSA-155 factorisation rather than an exhaustive search like DES.

We need to find distinguished points on a certain elliptic curve until the same point is found in two different ways and then the solution can be computed easily. Each point takes 1.4 billion elliptic curve operations on average and it is estimated that a matching pair will be found after about 1.3 million points.

Certicom is offering a prize of $10000 for the first correct solution. If we win it, $1000 will go to each of the two people who find the match and we will donate the remaining $8000 to the Apache Software Foundation. Note that following our previous successes, we have already donated $12000 to the Free Software Foundation.

So why not participate in the project?

Just grab the code and leave it running in the background. The program uses CPU time but almost no other resources, so you'll hardly notice it. Once in a while it sends a result back to base (or you can send batches of results manually).

Good luck!
Rob, Damien, Daniel and Xavier.

PS: Constructive comments are very welcome. Come discuss them on the ecdl mailing-list (see below).

Useful links:

Register as a participant using this form (optional).

Submit batches of points manually using this handy form.

Browse some tables with info on our progress:

• by team (fast Lynx version),
• by participant (fast Lynx version),
• by machine (fast Lynx version),
• by day (fast Lynx version),
• full details (fast Lynx version). Note: big table!

Check out some nice graphs (Java required) and this speed table.

Read the slightly technical FAQ about ECDLs.

Download the warez:

• Source code (32-bit, 64-bit).
• RPMs for Linux (on Alpha, ARM, PPC, Sparc, x86).
• MacOS port, now with speedy Altivec code by Dan Oetting.

• Windows ports:

  simple one, runs in a DOS box;

  Windows-aware one by Brian Gladman and Jeff Gilchrist, can be run as a background service;

  Windows-aware one by Jim Fougeron, GUI app.

• Binary executables:

  for FreeBSD on x86;

  for HP-UX on PA-RISC;

  for Irix on MIPS;

  for Linux on Alpha, ARM, PPC, Sparc, x86;

  for Solaris on UltraSPARC;

  for Tru64 Unix on Alpha.

Jon Nathan has a mirror site in the U.S. (if you're at the mirror you may want to get back to the original).

Mailing lists:

We have set up two mailing lists.

• A low-volume list for important announcements only:

  ecdl-announce@cristal.inria.fr

• A high-volume list for general discussion:

  ecdl-list@cristal.inria.fr

To subscribe or to read the archives, please go to:

• ecdl-announce
• ecdl-list

Timeline:

April 4th:
- Solved! We got the matching points.

March 22nd:
- N.A.P.L.M. virtual pilots merged with the INRIA team - competition is heating up at the top!

March 17th:
- St. Patrick's day: join us for a virtual pint!

March 9th:
- We passed the 50% chance-of-having-finished mark last night. There's no sign of matching points just yet though...

February 26th:
- Version 1.1.1 of the 32-bit code is out. Main difference: it's slightly faster.

February 21st:
- HTTP connections with our server failed briefly this weekend. Some people may have points that were not sent. Grep your ecdl.log file for "send by hand". See here for details.

February 16th:
- Apache is going from strength to strength. Read all about it at the Netcraft Web Server Survey.

January 16th:
- Distributed.net just announced that they found the CS-Cipher key. Congratulations, guys!

January 11th:
- There are now more than 1000 people participating. We have found 300000 points using over 3500 machines!

January 1st:
- Happy new year to everybody!
- OK, so there was no Y2K disaster. Surprise, surprise. Now let's switch those machines back on and get the daily rate back up again...

December 31st, midday:
- Happy new year to ECDL-ers in New Zealand!
- Let's see what this Y2K thingie does to our statistics. Not the "bug" of course, but people turning off machines to "solve" it.

December 25th:
- We have more than 100000 points already.
- Merry Christmas everybody!

December 21st:
- Passed 5% and we're accelerating fast!
- Watch out Debian: here comes No Team Yet, the team of people who aren't in any team. =:-)

December 13th:
- Version 1.1.0 ready for the big time.
- We now need as much publicity as we can get.
- If you are reading this and can do something about it, then please help!

December 10th:
- Windows port with nice installer.

December 7th:
- HTTP mode added.

December 3rd:
- Version 1.0.0 announced on ecdl-announce.

December 1st:
- Call for testers of version 0.99.0.

INRIA, Domaine de Voluceau - Rocquencourt, 78153 Le Chesnay, France.