ERCIM News No.40 - January 2000

Irish mathematician Robert Harley, a member of INRIA’s Cristal research group together with a team of 195 researchers has cracked the seventh and most difficult Certicom Elliptic Curve Cryptosystem (ECC) Challenge problem to date, a 97-bit encryption system based on elliptic curves.The challenge took place in a set of about 1029 points on an elliptic curve chosen by Certicom. To solve the problem, the participants first computed 119,248,522,782,547 (more than 1014) points using open-source software developed by Harley. Among these points, they screened 127,492 ‘distinguished’ points and collected them on an 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 team struck it lucky, finding the solution in less than a third of the expected time. The distributed computation was run by 195 volunteers, on a total of 740 computers, over 40 days. 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 and his colleagues on 26 August 1999 (see ERCIM News No. 39). This result strengthens the case of those who contend that a crypto system based on ECDL (Elliptic Curve Discrete Logarithms) is stronger even when using short keys than RSA with much longer keys, although it does not prove that assertion. Rather, it indicates that at the current state of the art, the best mathematical tools and algorithms known for cracking ECDL take longer to run than the best tools known for cracking RSA. Out of the $5000 prize money, the team members will gave $4000 to the Free Software Foundation. Further information at http://cristal.inria.fr/~harley/ecdl/.

return to the ERCIM News 40 contents page