Breaking ECC2K-130

ECC2K-130 is the smallest unsolved Certicom discrete-logarithm challenge. Certicom originally stated that breaking ECC2K-130 was “infeasible” and would require 2700000000 machine days.

This talk reports on an ongoing joint project by researchers from 12 different universities to break ECC2K-130. The project has increased our knowledge of the mathematical speedups for attacking elliptic-curve cryptosystems, has led to a new representation for finite fields in ‘optimal polynomial bases’, and has led to a better understanding of the randomness of pseudorandom walks used in Pollard’s rho method. The project has produced optimized implementations of a highly tuned iteration function for different platforms ranging from standard CPUs to customized FPGA clusters. These optimizations have moved the ECC2K-130 computation to the range of feasibility. The computation would finish in only two years using 1595 standard PCs, or 1231 PlayStation 3 game consoles, or 534 GTX 295 graphics cards, or 308 XC3S5000 FPGAs, or any combination of the above. We are now actively performing the computations. See our twitter page for updates.

Date:
Speakers:
Tanja Lange
Affiliation:
Technische Universiteit Eindhoven
    • Portrait of Jeff Running

      Jeff Running