Overview

Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys to provide equivalent security, compared to cryptosystems based on modular exponentiation in finite fields, such as the RSA cryptosystem and ElGamal cryptosystem.

Elliptic curves are applicable for key agreement, digital signatures, pseudo-random generators and other tasks. Indirectly, they can be used for encryption by combining the key agreement with a symmetric encryption scheme. They are also used in several integer factorization algorithms that have applications in cryptography, such as Lenstra elliptic-curve factorization.

History

The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S. Miller in 1985. Elliptic curve cryptography algorithms entered wide use starting in 2004.

In 1999, U.S. NIST recommended fifteen elliptic curves for use in the Digital Signature Standard. These curves were later specified in FIPS 186-4, which was superseded by FIPS 186-5 in 2023 and withdrawn in 2024. NIST moved its recommended elliptic-curve domain parameters to Special Publication 800-186. SP 800-186 includes previously recommended Weierstrass curves and two Edwards curves for EdDSA; it also deprecates binary-field curves and strongly recommends use of prime curves.

At the RSA Conference 2005, the National Security Agency (NSA) announced Suite B, which used ECC for digital signature generation and key exchange. Suite B was later superseded by the Commercial National Security Algorithm Suite (CNSA), and NSA announced CNSA 2.0 as a quantum-resistant transition suite for national security systems.

Security concerns

In 2013, The New York Times stated that Dual Elliptic Curve Deterministic Random Bit Generation (or Dual_EC_DRBG) had been included as a NIST national standard due to the influence of NSA, which had included a deliberate weakness in the algorithm and the recommended elliptic curve. RSA Security in September 2013 issued an advisory recommending that its customers discontinue using any software based on Dual_EC_DRBG.

In the wake of the exposure of Dual_EC_DRBG as "an NSA undercover operation", cryptography experts have also expressed concern over the security of the NIST recommended elliptic curves, suggesting a return to encryption based on non-elliptic-curve groups.

Additionally, in August 2015, the NSA announced that it planned to replace Suite B with a new cipher suite due to concerns about quantum computing attacks on ECC. NSA later published CNSA 2.0 guidance for a transition to quantum-resistant algorithms for national security systems.

Patents

While the RSA patent expired in 2000, there may be patents in force covering certain aspects of ECC technology, including at least one ECC scheme (ECMQV). However, RSA Laboratories and Daniel J. Bernstein have argued that the US government elliptic curve digital signature standard (ECDSA; NIST FIPS 186-3) and certain practical ECC-based key exchange schemes (including ECDH) can be implemented without infringing those patents.

Elliptic curve theory

For the purposes of this article, an elliptic curve is a plane curve over a finite field (rather than the real numbers). A common form for curves over finite fields of characteristic not equal to 2 or 3 consists of the points satisfying the equation

along with a distinguished point at infinity, denoted ∞. Curves over fields of characteristic 2 or 3, and curves used in other representations such as Montgomery or Edwards form, are written differently.