Editing Elliptic-curve cryptography (section)

=== Key sizes ===
{{See also|Discrete logarithm records#Elliptic curves}}

Because all the fastest known algorithms that allow one to solve the ECDLP ([[baby-step giant-step]], [[Pollard's rho algorithm for logarithms|Pollard's rho]], etc.), need <math>O(\sqrt{n})</math> steps, it follows that the size of the underlying field should be roughly twice the security parameter. For example, for 128-bit security one needs a curve over <math>\mathbb{F}_q</math>, where <math>q \approx 2^{256}</math>. This can be contrasted with finite-field cryptography (e.g., [[Digital Signature Algorithm|DSA]]) which requires<ref>NIST, [http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_part1_rev3_general.pdf Recommendation for Key Management—Part 1: general],  Special Publication 800-57, August 2005.</ref> 3072-bit public keys and 256-bit private keys, and integer factorization cryptography (e.g., [[RSA (algorithm)|RSA]]) which requires a 3072-bit value of ''n'', where the private key should be just as large. However, the public key may be smaller to accommodate efficient encryption, especially when processing power is limited.

The hardest ECC scheme (publicly) broken to date{{When|date=November 2022}} had a 112-bit key for the prime field case and a 109-bit key for the binary field case. For the prime field case, this was broken in July 2009 using a cluster of over 200 [[PlayStation 3]] game consoles and could have been finished in 3.5 months using this cluster when running continuously.<ref>{{cite web|url=http://lacal.epfl.ch/page81774.html|title=112-bit prime ECDLP solved – LACAL|website=lacal.epfl.ch|access-date=2009-07-11|archive-url=https://web.archive.org/web/20090715060838/http://lacal.epfl.ch/page81774.html|archive-date=2009-07-15|url-status=dead}}</ref> The binary field case was broken in April 2004 using 2600 computers over 17 months.<ref>{{cite web|url=http://www.certicom.com/index.php/2004-press-releases/36-2004-press-releases/300-solution-required-team-of-mathematicians-2600-computers-and-17-months- |title=Certicom Announces Elliptic Curve Cryptography Challenge Winner |work=Certicom |date=April 27, 2004 |url-status=dead |archive-url=https://web.archive.org/web/20110719233751/https://www.certicom.com/index.php/2004-press-releases/36-2004-press-releases/300-solution-required-team-of-mathematicians-2600-computers-and-17-months- |archive-date=2011-07-19 }}</ref>

A current project is aiming at breaking the ECC2K-130 challenge by Certicom, by using a wide range of different hardware: CPUs, GPUs, FPGA.<ref>{{cite web|url=http://www.ecc-challenge.info/|title=Breaking ECC2K-130|website=www.ecc-challenge.info}}</ref>