Breaking ECC2K-130

We wrote a paper about the implementation details and the math behind breaking ECC2K-130. A totally anonymous version can be found here. You can also follow us on twitter as ECCchallenge.

What is this all about? Certicom has published a series of challenges to further the understanding of the Elliptic Curve Discrete Logarithm Problem (ECDLP). The challenge is described on their website, a pdf file with the challenge details is also available as is a list of curve parameters.

This webpage describes progress in breaking the Certicom challenge ECC2K-130. We have implemented the attack on CPUs, GPUs, Cells, and FPGAs; this page reports the number of distinguished points found so far (usually with a day or two delay). Finding a distinguished point takes on average 2^25.27 iterations; we estimate a total computation time of 2^60.9 iterations (corresponding to finding about 2^35.63 distinguished points).

We are still in the phase where we see new clusters join. The following graph
server statistics picture
shows the timeline of the total number of distinguished points reported to the central servers since the beginning of the project.

Here is a small glimpse of how beautiful the whole thing will look once it's finished:

A rho within a random walk on 1024 elements. Short walks ending in distinguished points (big circles); the blue and the orange path have found the same distinguished point.

Cycle counts on various platforms

The following table shows the speeds of our latest implementations:

Platform Single-core cycles per iteration Iterations per second Number of copies of this platform to carry out 2^60.9 iterations in one year

Opteron 875 (2 cores, 2.210GHz) 1058 4.17 million 16360

Phenom II X4 905e (4 cores, 2.508GHz) 596 16.83 million 4054

Core 2 Extreme Q6850 (4 cores, 2.997GHz) 534 22.45 million 3039

PlayStation 3 (Cell CPU with 6 accessible SPEs, 1 PPE) 749 (SPE) 27.67 million 2466

Spartan-3 XC3S5000-4FG676 FPGA N/A 33.67 million 2026

GTX 295 video card (60 cores, 1.242GHz, in 2 GT200b GPUs) 1379 (new!) 54.03 million 1263

16 mm^2 ASIC, 90nm process N/A estimated 800 million 85


A rho within a random walk on 1024 elements.	Short walks ending in distinguished points (big circles); the blue and the orange path have found the same distinguished point.

Platform	Single-core cycles per iteration	Iterations per second	Number of copies of this platform to carry out 2^60.9 iterations in one year
Opteron 875 (2 cores, 2.210GHz)	1058	4.17 million	16360
Phenom II X4 905e (4 cores, 2.508GHz)	596	16.83 million	4054
Core 2 Extreme Q6850 (4 cores, 2.997GHz)	534	22.45 million	3039
PlayStation 3 (Cell CPU with 6 accessible SPEs, 1 PPE)	749 (SPE)	27.67 million	2466
Spartan-3 XC3S5000-4FG676 FPGA	N/A	33.67 million	2026
GTX 295 video card (60 cores, 1.242GHz, in 2 GT200b GPUs)	1379 (new!)	54.03 million	1263
16 mm^2 ASIC, 90nm process	N/A	estimated 800 million	85