Helpful context:

In 2005, the NSA recommended that new cryptographic systems migrate from RSA to elliptic curve cryptography. The reason was key size: a 256-bit elliptic curve key provides roughly the same security as a 3072-bit RSA key. This is not a matter of implementation efficiency - it reflects a fundamental difference in the hardness of the underlying mathematical problems. RSA security rests on the difficulty of integer factorization. ECC security rests on the difficulty of the elliptic curve discrete logarithm problem, which appears to be significantly harder for the same parameter size. Understanding why requires understanding what an elliptic curve is and what algebraic structure it carries.

An elliptic curve is not an ellipse. The name comes from their appearance in the computation of arc lengths of ellipses in the 19th century, but as mathematical objects they are quite different. An elliptic curve over a field $F$ is the set of solutions to a cubic equation $y^2 = x^3 + ax + b$ along with a formal point $O$ called the “point at infinity.” What makes these curves remarkable is that the points on the curve form a group under a geometrically defined addition law. This group structure, discovered in the 19th century, was purely a mathematical curiosity until 1985, when Neal Koblitz and Victor Miller independently proposed using it for public-key cryptography.

The Equation and Non-Degeneracy

An elliptic curve in Weierstrass form over a field $F$ is defined by

$$E: y^2 = x^3 + ax + b, \quad a, b \in F,$$

together with a distinguished point $O$ (the “point at infinity”) that is not on the affine curve. The set of points on $E$ is

$$E(F) = \{(x, y) \in F \times F : y^2 = x^3 + ax + b\} \cup \{O\}.$$

For the curve to be non-degenerate (no cusps or self-intersections), we require the discriminant to be nonzero:

$$\Delta = -16(4a^3 + 27b^2) \neq 0.$$

If $4a^3 + 27b^2 = 0$, the cubic $x^3 + ax + b$ has a repeated root, meaning the curve has a singular point (a cusp or a node). Singular curves do not support the group law in the way we need.

Example. The curve $y^2 = x^3 - x$ has $a = -1$, $b = 0$, and $4(-1)^3 + 27(0)^2 = -4 \neq 0$. It is non-degenerate. The curve $y^2 = x^3$ has $a = b = 0$ and $\Delta = 0$ - this has a cusp at the origin and is excluded.

The Group Law

The most important feature of elliptic curves is the chord-and-tangent rule for adding points. Given two points $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ on $E$:

  • Draw the line through $P$ and $Q$ (or the tangent line if $P = Q$).
  • This line intersects $E$ at a third point $R'$ (counting multiplicity, guaranteed by Bezout’s theorem since $E$ is a cubic).
  • Reflect $R'$ over the $x$-axis to get $R = P + Q$.

The point $O$ is the identity: $P + O = P$ for all $P$.

Concretely, for $P \neq Q$ and $x_1 \neq x_2$:

$$\lambda = \frac{y_2 - y_1}{x_2 - x_1}, \quad x_3 = \lambda^2 - x_1 - x_2, \quad y_3 = \lambda(x_1 - x_3) - y_1.$$

For the doubling case $P = Q$ (tangent line):

$$\lambda = \frac{3x_1^2 + a}{2y_1}, \quad x_3 = \lambda^2 - 2x_1, \quad y_3 = \lambda(x_1 - x_3) - y_1.$$

If $P = (x, y)$, then $-P = (x, -y)$ (reflection over $x$-axis). And $P + (-P) = O$.

Why This Is a Group

Verifying the group axioms:

Identity. $O$ is the identity. Geometrically, the line through $P$ and $O$ (a vertical line in projective coordinates) is tangent to $E$ at $O$ and meets $E$ at $-P$; reflecting over the $x$-axis gives $P$. So $P + O = P$.

Inverses. $P + (-P) = O$. The line through $P = (x,y)$ and $-P = (x,-y)$ is vertical; it intersects $E$ at “infinity,” which is exactly the point $O$.

Commutativity. $P + Q = Q + P$. This is clear from the formula: the line through $P$ and $Q$ is the same as the line through $Q$ and $P$.

Associativity. $(P + Q) + R = P + (Q + R)$. This is the non-obvious part. It can be verified by brute-force algebraic computation (tedious but finite), or proved more elegantly using the theory of divisors on algebraic curves. The geometric intuition does not make associativity obvious, which is why the algebraic proof matters.

With these four properties, $(E(F), +)$ is an abelian group.

Curves Over Finite Fields

For cryptography, we work over a finite field $\mathbb{F}_p$ for a large prime $p$. The curve becomes

$$E(\mathbb{F}_p) = \{(x, y) \in \mathbb{F}_p \times \mathbb{F}_p : y^2 \equiv x^3 + ax + b \pmod p\} \cup \{O\}.$$

This is a finite group. Its order (number of elements) is approximately $p$, and by Hasse’s theorem it lies in a tight interval:

Theorem (Hasse, 1936). $|{\ } #E(\mathbb{F}_p) - (p+1)\ | \leq 2\sqrt{p}.$

So the number of points on the curve is in the range $[p + 1 - 2\sqrt{p},\ p + 1 + 2\sqrt{p}]$. For a 256-bit prime $p$, there are approximately $2^{256}$ points on any elliptic curve over $\mathbb{F}_p$.

The group $E(\mathbb{F}_p)$ is either cyclic or a product of two cyclic groups. For cryptographic curves, the group is required to be (essentially) cyclic, with a generator $G$ of large prime order $n$.

Scalar Multiplication and the ECDLP

Given a point $G \in E(\mathbb{F}_p)$ and an integer $k$, define

$$kG = \underbrace{G + G + \cdots + G}_{k \text{ times}}.$$

This is called scalar multiplication. It can be computed in $O(\log k)$ group operations using double-and-add (the same idea as fast modular exponentiation).

The Elliptic Curve Discrete Logarithm Problem (ECDLP) is: given $G$ and $Q = kG$, find $k$.

For carefully chosen curves and parameters, no algorithm is known that solves ECDLP faster than $O(\sqrt{n})$ operations (via Pollard’s rho algorithm), where $n = |E(\mathbb{F}_p)|$. For comparison, the integer discrete logarithm (used in Diffie-Hellman) can be solved in sub-exponential time using the index-calculus method. The absence of an index-calculus attack on elliptic curves (at least generically) is what makes ECDLP harder per bit.

ECDH Key Exchange

Elliptic Curve Diffie-Hellman (ECDH) works exactly like standard DH, with the group $(\mathbb{Z}/p\mathbb{Z})^*$ replaced by $E(\mathbb{F}_p)$:

  1. Alice and Bob agree publicly on a curve $E$, a prime $p$, and a generator $G$ of large prime order $n$.
  2. Alice picks a secret integer $k_A \in [1, n-1]$ and sends $Q_A = k_A G$ to Bob.
  3. Bob picks a secret integer $k_B \in [1, n-1]$ and sends $Q_B = k_B G$ to Alice.
  4. Alice computes $k_A Q_B = k_A k_B G$.
  5. Bob computes $k_B Q_A = k_B k_A G$.
  6. The shared secret is $k_A k_B G$.

An eavesdropper sees $G$, $Q_A = k_A G$, and $Q_B = k_B G$, and must compute $k_A k_B G$ from these - the Computational Diffie-Hellman problem on the curve. This reduces to ECDLP under standard assumptions.

ECDSA Signatures

The Elliptic Curve Digital Signature Algorithm (ECDSA) signs messages using a private key $k$ with public key $Q = kG$:

Signing. To sign a message $m$:

  1. Compute $e = H(m)$ (a cryptographic hash).
  2. Choose a random $r \in [1, n-1]$ (the nonce).
  3. Compute the curve point $R = rG$.
  4. Let $R_x = R.x \bmod n$ (the $x$-coordinate of $R$ reduced mod $n$). If $R_x = 0$, choose a new $r$.
  5. Compute $s = r^{-1}(e + k \cdot R_x) \bmod n$. If $s = 0$, choose a new $r$.
  6. The signature is $(R_x, s)$.

Verification. To verify signature $(R_x, s)$ on message $m$ with public key $Q$:

  1. Compute $e = H(m)$.
  2. Compute $u_1 = e \cdot s^{-1} \bmod n$ and $u_2 = R_x \cdot s^{-1} \bmod n$.
  3. Compute the point $X = u_1 G + u_2 Q$.
  4. Accept if $X.x \equiv R_x \pmod n$.

Why it works. If the signature was generated honestly:

$$u_1 G + u_2 Q = \frac{e}{s} G + \frac{R_x}{s} (kG) = \frac{e + k R_x}{s} G = \frac{e + k R_x}{r^{-1}(e + kR_x)} G = r G = R.$$

Critical security note. The nonce $r$ must be chosen uniformly at random and never reused. In 2010, Sony’s PS3 firmware used a fixed nonce in ECDSA, allowing attackers to recover the private key from two signatures by solving a simple linear equation. The ECDSA security proof relies entirely on nonce unpredictability.

Key Size Comparison

Algorithm Key size Equivalent RSA
ECDH/ECDSA (P-256) 256 bits 3072-bit RSA
ECDH/ECDSA (P-384) 384 bits 7680-bit RSA
ECDH/ECDSA (P-521) 521 bits 15360-bit RSA
RSA-2048 2048 bits -

The equivalences are based on NIST security level estimates. For the same security level, ECC keys are roughly 10x shorter than RSA keys. Shorter keys mean faster signatures, less bandwidth, and smaller certificates - which is why TLS 1.3 defaults to ECDH for key exchange.

Safe Curves and Attacks

Not all elliptic curves are secure for cryptography. Several specific attacks exploit structural properties:

Small subgroup attacks (cofactor attacks). If $#E(\mathbb{F}_p) = hn$ where $n$ is a large prime and $h > 1$ (the “cofactor”), an adversary can send a point in the small subgroup of order $h$, learning information about the private key modulo $h$. Mitigation: use curves with $h = 1$ (prime-order curves) or always check that received points have order $n$.

MOV attack. Some curves admit an efficiently computable “Weil pairing” that maps the ECDLP on $E(\mathbb{F}p)$ to a discrete logarithm problem in $\mathbb{F}{p^k}^*$ for small $k$. If $k$ is small, this can be solved using index calculus. Curves are called “supersingular” when this embedding degree $k$ is small; they are excluded from cryptographic use.

Anomalous curves (SSSA attack). A curve is anomalous over $\mathbb{F}_p$ if $#E(\mathbb{F}_p) = p$. Such curves admit a “lift” to $p$-adic numbers that reduces ECDLP to an easy computation. Anomalous curves over $\mathbb{F}_p$ can be attacked in polynomial time.

Curve25519 and P-256. Modern secure curves are designed to avoid all known attacks. Curve25519 (designed by Bernstein) has prime order $8p$ where $p$ is a large prime, uses a Montgomery form $y^2 = x^3 + 486662x^2 + x$ optimized for fast arithmetic, and is designed so that all constant-time implementations are naturally correct. NIST P-256 is a Weierstrass curve over a 256-bit prime and is the most widely deployed curve in TLS.

Projective Coordinates

The formulas above require field divisions (computing $\lambda$). Over $\mathbb{F}_p$, division means computing a modular inverse, which is relatively expensive. Projective coordinates avoid this.

In projective coordinates, a point is represented as a triple $(X : Y : Z)$ with $(X : Y : Z) \sim (\lambda X : \lambda Y : \lambda Z)$ for $\lambda \neq 0$, corresponding to the affine point $(X/Z, Y/Z)$ when $Z \neq 0$. The point at infinity is $(0 : 1 : 0)$.

The Weierstrass equation becomes $Y^2 Z = X^3 + aXZ^2 + bZ^3$. The addition formulas in projective coordinates involve only multiplications and additions, with a single inversion needed only to convert the final result back to affine form. For computing $kG$ (scalar multiplication), this reduces the number of inversions from $O(\log k)$ to just 1, yielding a significant speedup.

Summary

Concept Description
Curve equation $y^2 = x^3 + ax + b$, with $4a^3 + 27b^2 \neq 0$
Group law Chord-and-tangent rule; identity is point at infinity
Group order (Hasse) $#E(\mathbb{F}_p) \in [p+1-2\sqrt{p},\ p+1+2\sqrt{p}]$
ECDLP Given $G$ and $kG$, find $k$: best known $O(\sqrt{n})$
ECDH Shared secret $k_A k_B G$ from public $k_A G$ and $k_B G$
ECDSA Sign with $s = r^{-1}(H(m) + k R_x) \bmod n$
Key sizes 256-bit ECC $\approx$ 3072-bit RSA security

Read next: