Paris, 28 September 1999--A new code-cracking challenge set by Certicom has been successfully overcome using 740 computers in 20 countries over a period of 40 days. The code, ECC2-97, is based on a technique known as elliptic curves.

Led by Robert Harley, a member of the Cristal project at INRIA, France's National Institute for Research in Computer Science and Control, the 195 researchers involved showed that a 97-bit encryption system based on elliptic curves is more difficult to crack than a 512-bit system based on integers such as RSA-155.

Encryption systems based on elliptic curves have been known since the mid-1980s, but have only recently been adopted by leading encryption companies such as RSA Security Inc. Certicom issued its "ECC Challenge" in November 1997, specifying a series of challenges of increasing difficulty. The company offers prizes up to US$100,000. The aim of the challenge is to encourage research in the field of elliptic curves and their applications in encryption, and to strengthen arguments in favor of using elliptic curve cryptography instead of systems based on integer factorization.

The challenge dubbed "ECC2-97" took place in a set of about 10²⁹ points on an elliptic curve chosen by Certicom. To solve the problem, participants first computed 119,248,522,782,547 (more than 10¹⁴) using open-source software developed by Harley. Among these points, they screened 127,492 "distinctive" points and collected them on a Alpha Linux workstation at INRIA where further processing revealed two twin points. Finally Harley computed the solution using information associated with these two points, thus nailing the problem.

The solution was found after less than one third of the predicted computation. The probability of finding the answer so quickly was less than one in ten. Two other twins were detected a few hours after the first - a less than one in 100 probability! Nevertheless the computing power used, around 16,000 MIPS/years, was twice as much as that used for the factorization of RSA-155 announced by Herman Te Riele of CWI (Amsterdam) and his colleagues on 26 August 1999.

"These results strengthen our confidence in codes based on properly-chosen elliptic curves," said Harley. "This needs to be taken into account in standards for security and confidentiality on the Internet."

According to Andrew Odlyzko, Head of Mathematics and Cryptography Research, at AT&T Labs, the code-cracking operation was "a great achievement that demonstrates the value of fruitfully harnessing some of the huge computational power of the Internet that is idle most of the time". He added: "It validates theoretical security predictions, and demonstrates the need to keep increasing cryptographic key sizes to protect against growing threats."

Arjen K. Lenstra, Vice President at Citibanks's Corporate Technology Office in New York and one of the main contributors to the recent successful attack on the RSA-155 challenge, compared the two computational efforts and noted that the present result makes 160-bit ECC keys look even better compared to 1024-bit RSA keys, from a security point of view. "Ideally we would like new theoretical advances to further reinforce these practical results, although such advances appear out of reach for the moment."

Out of the $5000 prize money, the team members will give $4,000 to the Free Software Foundation to encourage the creation of new free software. The remaining $1,000 go to the team members who identified the twin points. Both were in fact found by Paul Bourke using a network of Alpha workstations, mainly used for studying pulsars at the Centre of Astrophysics at Swinburne University in Australia.

      Astrophysics & Supercomputing             Australia
      INRIA                                     France
      University of New South Wales             Australia
      "Friends of Rohit Khare"                  USA and France
      ƒcole Polytechnique                       France
      Compaq                                    USA and Italy
      Technischen UniversitŠt Wien              Autriche
      University of Vermont                     USA
      "WinTeam"                                 International
      British Telecom Labs                      UK
      Internet Security Systems                 UK
      Rupture Dot Net                           USA
      "Jabberwocky"                             USA

Further information:

The ECDL Project

The Certicom ECC Challenge

Technical contact:

Robert Harley, INRIA

Media contacts:

Christine Genest, INRIA
Sylvie Baranger, Andrew Lloyd & Associates