Elliptic-Curve Cryptography

Elliptic-curve cryptography (ECC) is an approach to asymmetric public-key cryptography in computation and algorithms based on the algebraic structure of elliptic curves defined over finite fields. Proposed independently in 1985 by Neal Koblitz at the University of Washington and Victor S. Miller at the IBM Thomas J. Watson Research Center, ECC replaces the multiplicative group of integers modulo a large prime p (used in classic Diffie–Hellman and DSA) and the ring of integers modulo a composite product N = pq (used in RSA) with the finite abelian group of rational points E(F_q) on a plane cubic curve.

In computational complexity theory, the security of RSA and finite-field Diffie–Hellman is governed by the General Number Field Sieve (GNFS), an index-calculus algorithm that factors composite integers and computes multiplicative discrete logarithms in subpolynomial L_N[1/3, (64/9)^1/3] time, forcing RSA keys to grow to 3,072–15,360 bits to maintain 128–256 bits of cryptographic security. By contrast, generic prime-field elliptic curves possess no natural "smoothness" basis for index calculus; consequently, the fastest known classical algorithm for solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) is John M. Pollard's 1978 rho collision walk, which requires O(√n) ≈ 2^b/2 group operations on a b-bit prime subgroup of order n. A 256-bit elliptic-curve key therefore provides comparable classical security to a 3,072-bit RSA key while reducing key sizes by 12× and accelerating signature generation and TLS key exchange by an order of magnitude.

Short Weierstrass Equation and Non-Singularity

Let F_p = Z/(*p*Z) be a prime finite field of characteristic p > 3. An elliptic curve E over F_p is the locus of affine coordinate pairs (x, y) ∈ F_p × F_p satisfying the short Weierstrass equation:

y² ≡ x³ + ax + b (mod p)

together with a distinguished projective point at infinity, denoted 𝒪 (which serves as the neutral identity element of the group), where the coefficients a, b ∈ F_p must satisfy the non-zero discriminant condition:

Δ = −16 · (4a³ + 27*b*²) ≢ 0 (mod p)

The condition 4a³ + 27*b*² ≢ 0 (mod p) guarantees that the cubic polynomial x³ + ax + b has three distinct roots in the algebraic closure of F_p, ensuring that the curve is smooth (non-singular) with no self-intersecting node or cusp. (If Δ ≡ 0 mod p, the group of smooth points degenerates isomorphically into either the multiplicative group F_p^× or the additive group (F_p, +), rendering the discrete logarithm easy to solve.)

The Chord-and-Tangent Abelian Group Law

By Bézout's theorem in projective algebraic geometry, any projective line intersects a cubic curve in three points counted with multiplicity. This geometric incidence defines an associative, commutative binary operation + on E(F_p) known as the chord-and-tangent rule: if three points P, Q, R′ ∈ E(F_p) are collinear, their sum is defined to be the identity (P + Q + R′ = 𝒪), so P + Q = −R′ is obtained by reflecting the third intersection point R′ across the x-axis.

In affine coordinates over F_p, for any two non-identity points P = (x₁, y₁) and Q = (x₂, y₂):

1. Identity and Inverse: P + 𝒪 = 𝒪 + P = P, and the additive inverse of P = (x₁, y₁) is −P = (x₁, −y₁ mod p), since the vertical line x = x₁ passes through P, −P, and 𝒪.
2. Point Addition (P ≠ ±Q, so x₁ ≢ x₂ mod p): The secant chord through P and Q has modular slope:

λ = (y₂ − y₁) · (x₂ − x₁)⁻¹ mod p

1. Point Doubling (P = Q and y₁ ≢ 0 mod p): Implicit differentiation of y² = x³ + ax + b gives 2y dy = (3x² + a) dx, so the tangent line at P has modular slope:

λ = (3x₁² + a) · (2y₁)⁻¹ mod p

1. Coordinates of R = P + Q = (x₃, y₃): Substituting y = λ(x − x₁) + y₁ into the cubic equation and applying Vieta's root-sum formula yields:

x₃ = (λ² − x₁ − x₂) mod p y₃ = (λ(x₁ − x₃) − y₁) mod p

To avoid computing costly modular multiplicative inverses (z⁻¹ mod p via the extended Euclidean algorithm) at every intermediate addition, high-speed implementations represent points in Jacobian projective coordinates (X : Y : Z) where x = X / Z² and y = Y / Z³, deferring a single modular inversion to the end of scalar multiplication.

Hasse's Theorem and Group Order (N = h · n)

How many points lie on E(F_p)? Because roughly half of the p elements of F_p are quadratic residues modulo p (each yielding two square roots ±y), the point count N = |E(F_p)| stays close to p + 1. Specifically, Hasse's theorem on elliptic curves (proved by Helmut Hasse in 1936, the Riemann hypothesis for function fields of genus 1) states that:

| N − (p + 1) | ≤ 2√p

In 1985, René Schoof discovered a deterministic polynomial-time algorithm (the Schoof–Elkies–Atkin [SEA] algorithm) that computes the group cardinality N = |E(F_p)| for 256-bit primes in milliseconds by evaluating the Frobenius endomorphism modulo small primes ℓ. Cryptographic standards select curves whose total order factors as N = h · n, where n is a large prime and the cofactor h ∈ {1, 4, 8} is tiny.

Given a public base generator point G ∈ E(F_p) of large prime order n and a secret integer scalar k ∈ {1, 2, ..., n − 1}, scalar multiplication computes the k-fold point sum:

Q = kG = G + G + ··· + G (k times)

Using binary double-and-add or Peter L. Montgomery's constant-time Montgomery ladder (which executes one point addition and one point doubling per bit of k regardless of whether the bit is 0 or 1), computing Q = kG requires only Θ(log n) field operations.

Conversely, the Elliptic Curve Discrete Logarithm Problem (ECDLP) asks: given the curve parameters, base point G, and public key point Q = kG, recover the private scalar k ≡ logG(Q) (mod n). For safe curves (avoiding anomalous curves with N = p where Smart's p-adic attack runs in linear time, and supersingular curves with N = p + 1 where the Menezes–Okamoto–Vanstone [MOV] Weil-pairing reduction embeds E(Fp) into Fp2×), the fastest classical attack is Pollard's rho method. By iterating a pseudorandom partition walk Wi+1 = f(Wi) = aiG + biQ via a Monte Carlo method birthday paradox collision (aiG + biQ = ajG + bjQ, yielding k ≡ (ai − aj)(bj − bi)−1 mod n), Pollard's rho requires an expected √(πn / 2) ≈ 0.886 · 2b/2 point additions for a b-bit prime n.

Core Cryptographic Protocols: ECDH and ECDSA / EdDSA

1. Elliptic-Curve Diffie–Hellman (ECDH / X25519): Alice generates secret scalar d_A and sends public point Q_A = d_AG; Bob generates secret scalar d_B and sends public point Q_B = d_BG. Both parties independently compute the shared secret point S = d_AQ_B = d_BQ_A = (d_Ad_B)G and pass its x-coordinate through a key derivation function (HKDF).
2. ECDSA and EdDSA Digital Signatures: To sign a message digest h = H(m) with private key d_A, the signer draws an ephemeral scalar k ∈ [1, n − 1] (in EdDSA / RFC 8032, k is derived deterministically by hashing the private key and message m so that nonce reuse can never leak d_A), computes R = (x₁, y₁) = kG, and outputs signature (r, s) where r = x₁ mod n and s = k⁻¹(h + r · d_A) mod n.

Curve25519 (Montgomery Form) and Complete Edwards Curves

Because the Weierstrass addition formulas have conditional exception branches when P = Q (point doubling) or P = −Q (𝒪), naive software implementations can leak secret scalar bits through CPU branch-prediction and cache-timing side channels. In 2006, Daniel J. Bernstein introduced Curve25519, a Montgomery curve y² = x³ + 486662*x*² + x over the pseudo-Mersenne prime field p = 2²⁵⁵ − 19, alongside birationally equivalent twisted Edwards curves (ax² + y² = 1 + dx²y², used in Ed25519). When the Edwards parameter d is a non-square modulo p, the Edwards addition law has zero exceptional points—a single unified polynomial formula adds any two points P, Q ∈ E(F_p) (including P = Q and P = 𝒪) in constant time with zero conditional branches.

Why does a 256-bit elliptic curve provide the same classical security as a 3,072-bit RSA modulus?

An RSA modulus N = pq embeds inside the ring of integers Z, where smooth prime factorizations allow the General Number Field Sieve (GNFS) to build a linear system of congruences and factor N in subexponential time exp((1.923 + o(1))(ln N)^1/3(ln ln N)^2/3). Points on a prime-field elliptic curve have no notions of prime factorization or smoothness, forcing classical attackers back to generic group algorithms like Pollard's rho, which require 2¹²⁸ operations on a 256-bit group.

Why can reuse of the ephemeral nonce k in ECDSA immediately expose the private key?

In ECDSA, signing two different message hashes h₁ ≠ h₂ with the identical ephemeral scalar k produces two signatures (r, s₁) and (r, s₂) sharing the same r = (kG)_x mod n. Subtracting s₁ − s₂ ≡ k⁻¹(h₁ − h₂) (mod n) reveals k ≡ (h₁ − h₂)(s₁ − s₂)⁻¹ (mod n), from which the private key d_A ≡ r⁻¹(k · s₁ − h₁) (mod n) is recovered in two modular divisions. Deterministic nonce generation (as in Ed25519 and RFC 6979) eliminates this vulnerability.

How does Shor's quantum algorithm affect elliptic-curve cryptography?

On a fault-tolerant quantum computer, Peter Shor's 1994 period-finding algorithm—which applies the quantum Fast Fourier transform to a superposition of group elements |a⟩|b⟩|aG + *bQ*⟩—solves both integer factorization and the ECDLP in polynomial O((log p)³) quantum gate operations. Because a 256-bit elliptic curve has a smaller state register than a 3,072-bit RSA key, breaking 256-bit ECC via Roetteler et al.'s quantum circuit requires roughly 2,330 logical qubits, prompting TLS 1.3 and SSH deployments to pair X25519 with lattice-based post-quantum key encapsulation (X25519MLKEM768).

1. Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of Computation, 48(177), 203–209. https://doi.org/10.1090/S0025-5718-1987-0866109-5
2. Miller, V. S. (1986). Use of elliptic curves in cryptography. In Advances in Cryptology — CRYPTO '85 Proceedings (Lecture Notes in Computer Science, Vol. 218, pp. 417–426). Springer. https://doi.org/10.1007/3-540-39799-X_31
3. Bernstein, D. J. (2006). Curve25519: New Diffie-Hellman speed records. In Public Key Cryptography — PKC 2006 (Lecture Notes in Computer Science, Vol. 3958, pp. 207–228). Springer. https://doi.org/10.1007/11745853_14
4. Bernstein, D. J., Duif, N., Lange, T., Schwabe, P., & Yang, B.-Y. (2012). High-speed high-security signatures. Journal of Cryptographic Engineering, 2(2), 77–89. https://doi.org/10.1007/s13389-012-0027-1
5. Pollard, J. M. (1978). Monte Carlo methods for index computation (mod p). Mathematics of Computation, 32(143), 918–924. https://doi.org/10.1090/S0025-5718-1978-0491431-9