A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Elliptic curve cryptography (ECC) performs the same operations as classical public-key cryptography (DH, DSA, encryption) but over the group of points on an elliptic curve rather than the multiplicative group of integers modulo a prime. The key advantage is efficiency: the best known attacks on elliptic curve discrete logarithms (Pollard's rho) run in O(sqrt(n)) time, compared to sub-exponential algorithms for integer factorization and modular discrete logarithms. A 256-bit elliptic curve provides ~128 bits of security, matching a 3072-bit RSA/DH key. This makes ECC the default choice for modern protocols (TLS 1.3, Signal, SSH).
Classical public-key cryptography (RSA, DH) works in the multiplicative group of integers modulo a large prime or composite number. These groups are well-understood mathematically, which is both their strength (clear security analysis) and their weakness (sub-exponential algorithms like the Number Field Sieve exploit their structure). Elliptic Curve Cryptography (ECC) performs the same cryptographic operations — key exchange, signatures, encryption — but in a different mathematical group: the set of points on an elliptic curve over a finite field, where the "addition" operation has a geometric definition that translates cleanly into algebraic formulas.
An elliptic curve over a prime field F_p is defined by an equation like y2 = x3 + ax + b mod p. The set of solutions (x, y), together with a special "point at infinity" serving as the identity element, forms an abelian group under point addition. Given two points P and Q on the curve, their sum is defined geometrically (draw the line through P and Q, find its third intersection with the curve, reflect across the x-axis) and computed algebraically using field operations. Scalar multiplication — computing kP = P + P + ... + P (k times) — is the elliptic curve analog of modular exponentiation. The elliptic curve discrete logarithm problem (ECDLP) asks: given P and Q = kP, find k. This is the hard problem underpinning all of ECC.
The critical advantage of ECC is that no sub-exponential algorithm is known for ECDLP on well-chosen curves. The best generic attack is Pollard's rho, which runs in O(sqrt(n)) time where n is the group order. For a 256-bit curve (group order around 2256), this gives roughly 2128 operations — matching the security of 3072-bit RSA, which requires a much larger key because the Number Field Sieve attacks it in sub-exponential time. This roughly 12x key size advantage translates directly into faster computation, lower bandwidth, and smaller certificates, which is why ECDH (Elliptic Curve Diffie-Hellman) and ECDSA (Elliptic Curve Digital Signature Algorithm) have largely replaced their classical counterparts. TLS 1.3, the current web security standard, uses ECDH exclusively for key exchange.
Curve selection matters enormously. The NIST curves (P-256, P-384, P-521) are defined over random-looking primes with parameters that some researchers find suspicious (were they chosen to enable a backdoor?). Curve25519, designed by Daniel Bernstein, uses the prime 2255 - 19 (chosen for fast arithmetic), a Montgomery curve form that enables constant-time scalar multiplication (preventing timing side channels), and fully specified parameters with clear design rationale. Its signature variant Ed25519 has become the default for SSH keys, Signal messages, and many other applications. Both NIST curves and Curve25519 are believed secure against classical attacks, but ECC as a whole falls to Shor's quantum algorithm, motivating the parallel development of post-quantum cryptography based on lattices and other quantum-resistant problems.