------------------------------------------------------------------------------ This message is copyright (c) Robert J. Harley, 1998. If you wish to quote more than one paragraph, please quote the whole thing. To: certicom-ecc-challenge@certicom.com Robert J. Harley, Sèvres, France, 21st of May, 1998. Dear Mr. Gallant, The solution to Certicom's ECC2K-95 problem is the residue class of 37837308472231540269443981458 modulo 39614081257132074233778707191. The calculation was carried out in 25 days by a group of 47 people: Ettore Aldrovandi Michael Pfeiffer Wayne Baisley Jon Reeves Eric Bohm Panu Rissanen Craig Burley Brian Romansky James Childers Anthony Rumble Sven Dietrich Peter Rye Mike Ditto John Sager Einar Dorum Jaap Schellekens Mike DuVernois Mike Schloss Christopher Endsley David Seal Douglas Frank Al Simons Mark Gelinas Mikko Siren Rick Gorton Chris Smith Rick Gorton Ted Spradley Alexey Guzeev Greg Thomas Mikolaj Habryn Bill Viggers Robert Harley Bart-Jan Vrielink Robert Harley Mike Warren Mika Kortelainen Robert Wilhelm Andreas Krall John Wilkins Bernd Meyer Tom Woodburn Andres Meyer Gavin Woodhatch Willi More Berndt Wulf Wieger Opmeer Almost all of the work was done on 200 Alpha's ranging from desktop workstations to big parallel servers. 60.1% was done with Linux, 36.1% with Digital Unix, 3.4% with OpenVMS and 0.2% with NetBSD. The remaining 0.2% was on 32-bit machines running Linux, Risc OS, Windows NT and OS/2. Mike Warren made the biggest contribution using the Avalon network of seventy 533 MHz Alpha Linux workstations at Los Alamos. The next biggest teams were Digital, INRIA, Vienna University of Technology, British Telecom Labs, the University of Klagenfurt, Victoria University of Wellington Center for Water Research and "csmith". The method we used was a birthday paradox algorithm iterating from many random starting points with a pseudo-random iteration and reporting those points with a distinguishing characteristic back to base until a matching pair was found, as for the previous Elliptic Curve Discrete Logarithm records set by Alpha enthusiasts, British Telecom Labs and others who worked with us. A total of roughly 21600 billion iterations were performed, of which 20202935925971 led to the 74268 distinguished points that were reported back to base. The fastest systems were 600 MHz Alpha's doing up to 177 K iterations per second. A distinguished point matching a previously discovered one was found at 4:31 this morning, allowing us to compute the final answer. The matching points were found by Mike Warren with Avalon and by myself with an Alphastation 500/500 at INRIA. Since an ECC2K-95 iteration took about 2.5 times as long as an ECCp-97 iteration, this problem was easier by a factor of 3.7. A priori, the two problems appear to be of similar difficulty and since ECCp-97 was solved with a low number of iterations due to good luck, one might have expected this one to be the most difficult yet. However we used some extra structure by gathering the points into clusters of 194 points (technically, orbits under the involution [-1] and the Frobenius endomorphism [(-1+sqrt(-7))/2]). We chose a pseudo-random iteration that respected this structure: it was multiplicative, multiplying each point by 2, 6, 88, 90 or 92 according to a pseudo-random function of the orbit it belonged to. The distinguishing characteristic also respected the extra structure. This variant of the algorithm can be used with any curve but only rarely gives a speedup. For that, it needs a pseudo-random function and a distinguishing characteristic which respect the orbit structure and can be computed quickly. This can be done whenever points can be multiplied by some small-order roots of unity sufficiently quickly, by walking through the entire orbits under those multiplications. Our first implementation did so by repeatedly squaring the point coordinates in a polynomial basis, gaining a factor of five speed-up! The hint page put up by Certicom, http://www.certicom.ca/chal/note.htm, mentioned using a normal basis in which squaring is just a rotation; this gave a factor of seven. In our final implementation we avoided walking through the orbits by instead using a population count in a normal basis, even though all arithmetic was in a polynomial basis, gaining a factor of ten. Our source code can be downloaded from: http://pauillac.inria.fr/~harley/ecdl5/Alpha_111/source/ I would like to point out that the hint-page remark: >Recently, a successful solution to the ECCp-97 exercise was >submitted. The ECCK-95 exercise is easier, and suggests that not >everyone is aware of the speedups available for computing discrete >logs on a binary anomalous curve. strikes me as particularly disingenuous since when ECCp-97 was started, nobody yet knew how to speed up ECC2K-95. It is all the more disingenuous that the "hint" is to change only the definition of distinguished points, which is not sufficient to get any speed-up at all (although the preprint added later fixed this). I would also like to thank Rob Zuccherato for sending his and Michael Wiener's paper, "Faster Attacks on Elliptic Curve Cryptosystems", in which they describe another algorithm: they keep an additive pseudo-random function, adapt it for orbits of points and propose a mechanism for getting rid of almost all of the short cycles that would otherwise cause problems. Finally, I draw the conclusion that cryptographic codes must no longer be based on the difficulty of discrete logarithms on curves defined over GF(2), since these logs are now demonstrably easier than on random curves and since it is not unlikely that much greater weaknesses will be discovered in future. Bye, Rob. .-. Robert.Harley@inria.fr .-. / \ .-. .-. / \ / \ / \ .-. _ .-. / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / `-' `-' \ / \ / \ \ / `-' `-' \ / `-' Linux + 500MHz Alpha + 256MB SDRAM = heaven `-' ------------------------------------------------------------------------------