**From:** Sally Khudairi (*info@zotgroup.com*)

**Date:** Thu Apr 13 2000 - 06:08:06 PDT

**Next message:**Manoj Kasichainula: "Re: Digital cameras again"**Previous message:**John Boyer: "Microsoft gets into the Diva business"

For Immediate Release:

Contact:

ZOT Group (US Press Contact)

B.K. DeLong

bkdelong@zotgroup.com

+1.617.642.7149

4K Associates (Europe)

Robert Harley

Robert@4K-Associates.com

+33.1.3963.5157

4K Associates (US)

Rohit Khare

Rohit@4K-Associates.com

+1.626.806.7574

Biggest Public-key Cryptography Crack Ever

Worldwide Calculation Solves 109-bit Elliptic Curve Challenge

PARIS -- 13th April 2000 -- Irish mathematician Robert Harley and three

colleagues at INRIA, the French National Institute for Research in

Computer Science and Control, announced the solution to the most

difficult public key cryptographic challenge ever solved after a huge

calculation on close to 10000 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 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.

ORGANIZATION OF THE PROJECT

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.

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 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".

CONCLUSION

This large-scale project and others of its kind play a vital role by

putting theoretical assessments of security to the test of experiment.

INRIA's de Rauglaudre drew the analogy "Just as crash-tests by automobile

manufacturers contribute to the safety of cars, this experiment helps

improve cryptosystems currently being deployed to secure electronic

communications and commerce."

FOR MORE INFORMATION:

The ECDL project:

http://cristal.inria.fr/~harley/ecdl/

The Certicom ECC Challenge:

http://www.certicom.com/chal/

4K Associates

http://www.4K-Associates.com/

###

**Next message:**Manoj Kasichainula: "Re: Digital cameras again"**Previous message:**John Boyer: "Microsoft gets into the Diva business"

*
This archive was generated by hypermail 2b29
: Thu Apr 13 2000 - 07:04:53 PDT
*