(A Javascript-enabled browser is required to email me.)


Certicom ECC Challenge(s) Cracked
from TBTF for 1997-12-24
 TBTF for 1997-12-08
 TBoDay for 1998-01-15



Certicom is a maker of eliptical-curve encryption software. ECC algorithms are drawing considerable interest and study because they hold out the possibility of offering security comparable to the RSA algorithms using smaller keys, therefore requiring less computation. This possibility is not yet considered verified by most of the mathematics and cryptosystems research community.

In order to gain exposure and to jumpstart the expert scrutiny that ECC will need if it is to be widely trusted, Certicom is sponsoring a crypto challenge.


ECCp-79

To: certicom-ecc-challenge@certicom.com

6th of December, 1997.

Dear Anonymous,

Certicom's professed aim in setting its ECC challenge is to encourage research into secure cryptosystems based on elliptic curve discrete logarithms. Yet Certicom is a member of the Key Recovery Alliance, a lobby group whose purpose is to promote the use of back-doors allowing supposedly secure communications to be intercepted. How are these contradictory positions reconciled?

The solution to your ECCp-79 problem is the residue class of 92221507219705345685350 modulo 466597814831947642887217. It was found by Wayne Baisley and myself using several Digital Alpha workstations running Linux and Digital Unix at the Institut National de Recherche en Informatique et Automatique (INRIA), at Fermi National Accelerator Laboratory and at the California Institute of Technology C.S. Department.

The method used was a "birthday paradox" algorithm iterating from a random initial point (one per machine) with a random function (the same on all machines) until a collision was detected at 17:58 today at INRIA, Rocquencourt, France by a 500MHz Linux machine. This machine did 25 billion elliptic curve operations per day. The peak rate of all machines was approximately 6 six times as much. A total of about 1400 billion iterations were performed.

If this is the first correct submission, please send the prize (a copy of "Handbook of Applied Cryptography" and Maple software) to the following address:

  Robert Harley,
  c/o Sylvie Loubressac,
  Projet CRISTAL,
  INRIA,
  Domaine de Voluceau - Rocquencourt,
  78153 Le Chesnay,
  France.

Thank you,
  Rob.
     .-.                     Robert.Harley@inria.fr                    .-.
    /   \           .-.                                 .-.           /   \
   /     \         /   \       .-.     _     .-.       /   \         /     \
  /       \       /     \     /   \   / \   /   \     /     \       /       \
 /         \     /       \   /     `-'   `-'     \   /       \     /         \
            \   /         `-'                     `-'         \   /
             `-'  Linux + 500MHz Alpha + 256MB SDRAM = heaven  `-'



ECC2-79

Robert J. Harley,
Sevres, France,
16th of December, 1997.

To: certicom-ecc-challenge@certicom.com

Dear Mr. Gallant,

There are two types of communications. On the one hand are secure communications, intelligible only to their intended recipient, and on the other are all the rest. Between them, as Louis Freeh would say, there is a "bright line". On what side of that line does Certicom stand?

The solution to your ECC2-79 problem is the residue class of 276856274258963891889538 modulo 302231454903954479142443. The work was led by a group of Alpha Linux enthusiasts, and the British Telecom Labs team joined in too. We used about 30 Alphas running Linux, from UDBs up to 600 MHz workstations. Jay Estabrook's new 21264 machine made a cameo appearance! There were also 4 Alphas running Digital Unix.

Contributors were:

    Andries Brouwer     Andries.Brouwer@cwi.nl
    Christopher Brown   cbrown@alaska.net
    Zach Brown          zab@zabbo.net
    Jay Estabrook       Jay.Estabrook@digital.com
    Rick Gorton         gorton@amt.tay1.dec.com
    Oleg Gusev          oleg@usm.uni-muenchen.de
    Robert Harley       Robert.Harley@inria.fr
    Richard Holmes      holmes@lanl.gov
    Andy Isaacson       adi@acm.org
    Greg Lindahl        lindahl@cs.virginia.edu
    Jon Nathan          jon@blading.com
    Dennis Opacki       dopacki@mac-guru.com
    Vance Petree        vwp@vancpower.com
    Tim Rowley          tor@cs.brown.edu
    Michael Sandfort    sandfort@post.cis.smu.edu
    Jason Shiffer       jshiffer@home.com
    Aaron Spink         spink@pa.dec.com
    B.T. Labs Team      jcs@zoo.bt.co.uk
    Bart-Jan Vrielink   bartjan@mail.de-boulevard.nl
    Marinos Yannikos    nino@complang.tuwien.ac.at
    Xiaoguang Zhang     xgz@mn.ms.ornl.gov
and some anonymous others.

The method we used was a "birthday paradox" algorithm iterating from a random initial point (one per machine) with a pseudo-random function (the same on all machines) until a collision was detected at 12:47 today. A total of 1737410165382 iterations were performed, finding 1617 "distinguished" points and one collision. Our source code can be downloaded from:

http://pauillac.inria.fr/~harley/ecdl/

We would like to thank Michael Wiener for sending his paper, co-authored with Paul van Oorschot, in which they suggest using distinguished points for discrete log calculations. We used this idea to simplify our client program.

Thanks also to John Sager who spotted a broken line of code in one version of the program. We were quickly able to verify that it had caused no harm.

If this is the first correct submission, then, well I don't really know what you should do with the prize! Perhaps hold a raffle among the contributors?

Thank you,
  Rob.
     .-.                     Robert.Harley@inria.fr                    .-.
    /   \           .-.                                 .-.           /   \
   /     \         /   \       .-.     _     .-.       /   \         /     \
  /       \       /     \     /   \   / \   /   \     /     \       /       \
 /         \     /       \   /     `-'   `-'     \   /       \     /         \
            \   /         `-'                     `-'         \   /
             `-' Linux + 500MHz Alpha + 256MB SDRAM = heaven   `-'



ECCp-89

To: certicom-ecc-challenge@certicom.com

Robert J. Harley,
Rocquencourt, France,
12th of January, 1998.

Dear Mr. Gallant,

Please note that this submission, like the previous two, carries a copyright notice. If you wish to quote it on your Web pages, or anywhere else, you may not strip off the copyright notice nor replace it with "Copyright Certicom Corp." or any similar notice.

The solution to your ECCp-89 problem is the residue class of 333373190151749761757285479 modulo 416363315556124458285894983. The calculation was carried out in 24 days by a group of 57 people using Alpha workstations running Linux, Digital Unix, VMS and NetBSD:

             Zach Brown                    Jon Reeves
          Dragisa Duric                    Tim Rowley
           Martin Edu                     John Sager
           Adrian Escott               Michael Sandfort
          Douglas Frank                   Mike Schloss
             Rick Gorton                  Alex Selkirk
             Oleg Gusev                     Al Simons
           Robert Harley                 Aaron Spink
            David Hauan                 Murray Stokely
             Dave Hill                  Adrian En-Wei Sun
          Richard Holm                   Peter Swardes
         Chatchai Janta                   Greg Thomasraprim
             Olav Kongas              Dimitris Tsapakidis
             Mika Kortela                 Jeff Uphoffinen
           Edward Lee                    Marko Vendelin
             Greg Lindah                Carlos Vidall
            Brian Lund                Bart-Jan Vrielink
              Rob Millner                  Tom Woodburn
         Francois Morai           Berndt Josef Wulfn
             Pete Murray               Marinos Yannikos
              Jon Nathan                  Paul Young
and a person who prefers to remain anonymous.

The method we used was a "birthday paradox" algorithm iterating from a random initial point (one per machine) with a pseudo-random function (the same on all machines) until a collision was detected at 15:33 today. A total of 24249418904337 iterations were performed, finding 36345 "distinguished" points and one collision. The British Telecom team found 11333 of the points, people from Digital found 7853, people from INRIA found 4680 and individuals in more than a dozen countries found 12479. Our source code can be downloaded from: http://pauillac.inria.fr/~harley/ecdl2/

Bye,
  Rob.
     .-.                     Robert.Harley@inria.fr                    .-.
    /   \           .-.                                 .-.           /   \
   /     \         /   \       .-.     _     .-.       /   \         /     \
  /       \       /     \     /   \   / \   /   \     /     \       /       \
 /         \     /       \   /     `-'   `-'     \   /       \     /         \
            \   /         `-'                     `-'         \   /
             `-' Linux + 500MHz Alpha + 256MB SDRAM = heaven   `-'


[ TBTF for 1997-12-24 ]
[ TBTF for 1997-12-08 ]
[ TBoDay for 1998-01-15 ]