"INRIA led Worldwide Calculation for Biggest Public-key Cryptography Crack"

Researchers at INRIA announced on 13th April the solution to the most difficult public key cryptographic challenge ever solved after a huge calculation on close to 10,000 computers throughout the Internet. The challenge, called ECC2K-108, was set by Canadian cryptographic company Certicom in 1997 to encourage researchers to test the security of cryptography based on elliptic curves.

This extraordinary achievement demonstrates the high level of security that elliptic-curve cryptography (ECC) 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.

Organisation of the Project
Robert Harley and three INRIA colleagues, Damien Doligez, Daniel de Rauglande and Xavier Leroy, found the 109-bit cryptographic key after four months of computation with the help of 1300 volunteers in 40 countries.( one of which being The School of Computing). 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 organised 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 AlphaServer at INRIA where a Web site allowed participants to follow the computations' 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.

Of the US$10,000 prize money offered by Certicom, $8,000 will be donated to the Apache Software Foundation to support development of the Apache open-source Web server software package. the remaining $2,000 will go to two participants who found crucial distinguished points used in computing the solution.

Implications
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 RSA of at least 600 bits".

Conclusion
For INRIA researchers, such experiments are very important: they enable theoretical assessments of the security of cryptosystems to be confirmed by experiment. In this way a large-scale test of their resistance to attack is achieved, which helps to improve their security just as crash-tests by automobile manufacturers contribute to the safety of cars.

extracts from article in ERCIM News No. 42 , July 2000