ECC2-79 cracked: Alpha Linux did it.

 
From Robert.Harley(at)inria.fr Fri Dec 19 15:45:18 1997 
Date: 1997年12月16日 14:18:54 +0100 (MET) 
From: Robert Harley <Robert.Harley(at)inria.fr> 
Reply-To: axp-list(at)redhat.com 
To: axp-list(at)redhat.com 
Subject: ECC2-79 cracked: Alpha Linux did it. 
Resent-Date: 16 Dec 1997 13:19:42 -0000 
Resent-From: axp-list(at)redhat.com 
Resent-cc: recipient list not shown: ; 
 
Jus' sent this out. 
 
------------------------------------------------------------------------------ 
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(at)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(at)cwi.nl 
 Christopher Brown cbrown(at)alaska.net 
 Zach Brown zab(at)zabbo.net 
 Jay Estabrook Jay.Estabrook(at)digital.com 
 Rick Gorton gorton(at)amt.tay1.dec.com 
 Oleg Gusev oleg(at)usm.uni-muenchen.de 
 Robert Harley Robert.Harley(at)inria.fr 
 Richard Holmes holmes(at)lanl.gov 
 Andy Isaacson adi(at)acm.org 
 Greg Lindahl lindahl(at)cs.virginia.edu 
 Jon Nathan jon(at)blading.com 
 Dennis Opacki dopacki(at)mac-guru.com 
 Vance Petree vwp(at)vancpower.com 
 Tim Rowley tor(at)cs.brown.edu 
 Michael Sandfort sandfort(at)post.cis.smu.edu 
 Jason Shiffer jshiffer(at)home.com 
 Aaron Spink spink(at)pa.dec.com 
 B.T. Labs Team jcs(at)zoo.bt.co.uk 
 Bart-Jan Vrielink bartjan(at)mail.de-boulevard.nl 
 Marinos Yannikos nino(at)complang.tuwien.ac.at 
 Xiaoguang Zhang xgz(at)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(at)inria.fr .-. 
 / \ .-. .-. / \ 
 / \ / \ .-. _ .-. / \ / \ 
 / \ / \ / \ / \ / \ / \ / \ 
 / \ / \ / `-' `-' \ / \ / \ 
 \ / `-' `-' \ / 
 `-' Linux + 500MHz Alpha + 256MB SDRAM = heaven `-' 
------------------------------------------------------------------------------. 
 
S'pose that means that Alpha Linux is pretty cool. 
 
Who's up for ECCp-89? =:-) 
 
 
 

---