Yawn,
Rob.
------------------------------------------------------------------------------
This message is copyright (c) Robert J. Harley, 1998.
If you wish to quote more than one paragraph, please quote the whole thing.
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 `-'
------------------------------------------------------------------------------