3.5.5 What is the Certicom ECC Challenge?
The Certicom ECC Challenge is the elliptic curve counterpart to the RSA Factoring Challenge (see Question 2.3.6). The challenge is to find the private key in an elliptic curve cryptosystem given the public key and associated parameters. Mathematically, the challenge is to solve a discrete logarithm problem (see Question 2.3.7) in an elliptic curve group (see Question 2.3.10). The competitors may choose whether they want to attack a key over GF(2m) or over GF(p), where p is a given prime.
The challenge is divided into three levels. "Level 0" consists of several Exercises with keys consisting of 79, 89, and, 97 bits. The key sizes in Level I are 109 and 131, while the key sizes in Level II are 163, 191, 239, and 359.
Among the Level I and II challenges, the 109-bit challenges are provably feasible given today's computational power, while the 131-bit challenges seem to be infeasible for the moment; in commercial applications, 132 is the minimal key size recommended by Lenstra and Verheul (see Question 18.104.22.168).
The Exercise Level was completed in September 1999, when a group led by Robert Harley at INRIA in France managed to solve ECC2-97, a challenge concerning an elliptic curve over GF(297). In April 2000, the first Level I challenge (the 109-bit key ECC2K-108) was solved by Harley's team after four months of computations on 9,500 machines. The required computational power has been estimated to be about 50 times that required to factor RSA-155 (see Question 2.3.6).