------------------------------------------------------------------------------
This message is copyright Robert J. Harley, 1997.
If you wish to quote more than one sentence, please quote the whole thing.
To: certicom-ecc-challenge@certicom.com
Robert J. Harley,
Se`vres, France,
16th of December, 1997.
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 `-'
------------------------------------------------------------------------------.