About · Consultants · Clients · Library · Press · Contact
ZOT Group (US Press Contact)
4K Associates (Europe)
4K Associates (US)
This extraordinary achievement demonstrates the high level of security that ECC (elliptic-curve cryptography) can offer with much shorter keys than RSA. It also highlights the relative weakness of some curves with special properties and confirms that for optimal security one should pick random curves with no special characteristics.
Robert Harley and colleagues, Damien Doligez, Daniel de Rauglaudre and Xavier Leroy, found the 109-bit cryptographic key after four months of computation distributed on 9500 computers with the help of 1300 volunteers in 40 countries. Two thirds of the computation were done on Unix workstations and one third on Windows PCs. On a single 450 MHz machine the computation would have taken 500 years.
The project, called ECDL, was organized into teams which used open-source software developed by Harley to calculate more than two million billion points on a particular type of elliptic curve, called a Koblitz curve by Certicom. Among these points, the teams discovered "distinguished" points and sent them to an AlphaServer at INRIA where a Web site allowed participants to follow the computation's progress in real-time. After two million distinguished points had been collected, a final phase of processing was able to extract the solution.
The participants also stayed in constant communication via the Web site and a good-humoured competition quickly developed among them. The most productive people were: Paul Bourke at Swinburne Astrophysics and Supercomputing in Australia, Rajit Manohar at Cornell Computer Systems Laboratory, Bruno Verlyck and Philippe Deschamp at INRIA, Vincent Goffin with AT&T, Bernd Leibing at Ulm University in Germany, Mark Brown with Rhythm and Hues Studios in Los Angeles.
Of the US$10000 prize money offered by Certicom, $8000 will be donated to the Apache Software Foundation to support development of the Apache open-source Web server software package. The remaining $2000 will go to two participants who found crucial distinguished points used in computing the solution: Asa Reed with Colorado Group and a person who prefers to remain anonymous.
Arjen Lenstra, vice president at Citibank's Corporate Technology Office in New York and a participant in the project, noted "The amount of computation we did is more than what is needed to crack a secret-key system like DES and enough to crack a public-key system like RSA of at least 600 bits".
Harley remarked "Even so, it was only about one tenth of what should normally be required for a 109-bit curve. That's because Certicom chose a particular curve with some useful properties but we used those same properties to speed up our attack". He went on to say "This underlines the danger in adopting particular curves and the need to pick random ones with no special characteristics. I'm concerned about Koblitz curves and complex-multiplication curves, which some people advocate using in order to avoid the point-counting problem".
François Morain, Professor of Computer Science at École Polytechnique, explained: "To use a curve for ECC one first has to calculate the number of points on it, which is quite a difficult task. To improve security one should use arbitrary curves picked at random and change them frequently, but currently most cryptosystems use fixed curves chosen to have particular properties which make it easy to compute the cardinality. These very properties could one day endanger them, as happened with super-singular curves. There have been dramatic improvements in point-counting algorithms and good implementations are now becoming available. Recent progress should soon undermine any remaining argument in favour of special curves".
The ECDL Project
The Certicom ECC Challenge