Skip to content

Elliptic Curve Cryptography

The Story Behind the Math

By the mid-1980s, RSA was well-established but had a growing problem: key sizes. As computers got faster, RSA keys had to grow larger to stay secure — from 512 bits to 1024, then 2048. Larger keys meant slower encryption, more bandwidth, and heavier computation. Was there a mathematical structure that could provide the same security with smaller keys?

In 1985, two mathematicians independently proposed the answer. Neal Koblitz at the University of Washington and Victor Miller at IBM Research both realized that elliptic curves — objects studied by pure mathematicians since the 19th century — could form the basis of a new cryptographic system.

The key insight: Elliptic curves over finite fields form an abelian group under a geometric addition operation. The discrete logarithm problem on these curves — given points \(P\) and \(Q = nP\), find \(n\) — is believed to be even harder than factoring integers or computing discrete logs in modular arithmetic. This means ECC can achieve the same security as RSA with dramatically smaller keys.

How much smaller? A 256-bit ECC key provides roughly the same security as a 3072-bit RSA key. This makes ECC ideal for mobile devices, smart cards, and IoT systems where computational resources are limited.

The adoption story was slow. ECC was initially encumbered by patents (held by Certicom), and the NSA's promotion of ECC curves through NIST raised suspicions — particularly after the 2013 Snowden revelations showed that the NSA had backdoored the Dual_EC_DRBG random number generator (which used elliptic curves). The cryptographic community responded by developing independently verifiable curves like Curve25519 (designed by Daniel Bernstein in 2006), which is now the gold standard.

Today, ECC is everywhere: TLS 1.3 defaults to elliptic curve key exchange, Signal uses Curve25519, and Ed25519 signatures are standard in SSH and cryptocurrency.

Why It Matters

  • TLS/HTTPS — Modern web security uses ECDHE (Elliptic Curve Diffie-Hellman Ephemeral) by default
  • Signal Protocol — End-to-end encryption in Signal, WhatsApp, and others uses Curve25519
  • Bitcoin and Ethereum — Transaction signing uses the secp256k1 elliptic curve
  • SSH keys — Ed25519 keys are now preferred over RSA
  • Smart cards and IoT — Small key sizes make ECC feasible on constrained devices
  • Government — NSA Suite B specified ECC for classified communication

Prerequisites

  • Modular arithmetic
  • Basic group theory (groups, generators, order)
  • RSA — For comparison of security assumptions
  • Coordinate geometry (curves in the plane)

The Formulas

The Elliptic Curve

An elliptic curve over a field \(\mathbb{F}\) is defined by the short Weierstrass equation:

\[ y^2 = x^3 + ax + b \]

where \(4a^3 + 27b^2 \neq 0\) (to ensure the curve is non-singular).

Point Addition

Given two points \(P = (x_1, y_1)\) and \(Q = (x_2, y_2)\) on the curve, their sum \(R = P + Q = (x_3, y_3)\) is:

\[ x_3 = \lambda^2 - x_1 - x_2, \qquad y_3 = \lambda(x_1 - x_3) - y_1 \]

where the slope \(\lambda\) is:

\[ \lambda = \begin{cases} \dfrac{y_2 - y_1}{x_2 - x_1} & \text{if } P \neq Q \quad \text{(point addition)} \\[10pt] \dfrac{3x_1^2 + a}{2y_1} & \text{if } P = Q \quad \text{(point doubling)} \end{cases} \]

The Discrete Logarithm Problem (ECDLP)

Given a base point \(G\) on the curve and a point \(Q = nG\) (where \(nG = \underbrace{G + G + \cdots + G}_{n \text{ times}}\)), find the integer \(n\).

This is the hard problem that ECC security relies on.

Derivation

Step 1: Elliptic Curves as Groups

An elliptic curve \(E\) over a field, together with a special point at infinity \(\mathcal{O}\), forms an abelian group under the following operation:

Geometric rule (over \(\mathbb{R}\)): To add points \(P\) and \(Q\), draw the line through them. This line intersects the curve at a third point \(R'\). Reflect \(R'\) across the x-axis to get \(R = P + Q\).

Why this works as a group: - Closure: The line through two curve points always intersects the curve at a third point (by Bézout's theorem, a line and a cubic intersect at exactly 3 points, counting multiplicity) - Identity: The point at infinity \(\mathcal{O}\) acts as the identity (\(P + \mathcal{O} = P\)) - Inverses: The inverse of \((x, y)\) is \((x, -y)\) (reflection across the x-axis) - Associativity: Can be verified algebraically (tedious but true) - Commutativity: The line through \(P\) and \(Q\) is the same as through \(Q\) and \(P\)

Step 2: The Addition Formulas

Case 1: \(P \neq Q\) (point addition)

The line through \(P = (x_1, y_1)\) and \(Q = (x_2, y_2)\) has slope:

\[ \lambda = \frac{y_2 - y_1}{x_2 - x_1} \]

The line equation is \(y = \lambda(x - x_1) + y_1\). Substituting into \(y^2 = x^3 + ax + b\):

\[ [\lambda(x - x_1) + y_1]^2 = x^3 + ax + b \]

Expanding and rearranging gives a cubic in \(x\):

\[ x^3 - \lambda^2 x^2 + \cdots = 0 \]

We know two roots: \(x_1\) and \(x_2\). By Vieta's formulas, the sum of all three roots equals \(\lambda^2\):

\[ x_1 + x_2 + x_3 = \lambda^2 \implies x_3 = \lambda^2 - x_1 - x_2 \]

The y-coordinate of the third intersection point is \(y' = \lambda(x_3 - x_1) + y_1\). Reflecting across the x-axis:

\[ y_3 = -y' = \lambda(x_1 - x_3) - y_1 \]

Case 2: \(P = Q\) (point doubling)

When \(P = Q\), the "line through both points" is the tangent to the curve at \(P\). Implicit differentiation of \(y^2 = x^3 + ax + b\):

\[ 2y \frac{dy}{dx} = 3x^2 + a \implies \lambda = \frac{3x_1^2 + a}{2y_1} \]

The rest of the calculation proceeds identically.

Step 3: Moving to Finite Fields

For cryptography, we work over a finite field \(\mathbb{F}_p\) (integers modulo a prime \(p\)). The curve equation becomes:

\[ y^2 \equiv x^3 + ax + b \pmod{p} \]

The addition formulas are identical, but all arithmetic is done modulo \(p\). Division by \((x_2 - x_1)\) becomes multiplication by the modular inverse \((x_2 - x_1)^{-1} \mod p\).

The set of points on \(E(\mathbb{F}_p)\) (plus \(\mathcal{O}\)) forms a finite abelian group of some order \(N\). By Hasse's theorem:

\[ |N - (p + 1)| \leq 2\sqrt{p} \]

So the group has approximately \(p\) elements.

Step 4: Scalar Multiplication and the ECDLP

Scalar multiplication is repeated addition:

\[ nP = \underbrace{P + P + \cdots + P}_{n \text{ times}} \]

This can be computed efficiently in \(O(\log n)\) group operations using double-and-add (analogous to square-and-multiply for modular exponentiation):

To compute nP:
  Write n in binary: n = b_k b_{k-1} ... b_1 b_0
  Start with R = O (point at infinity)
  For i from k down to 0:
    R = 2R          (point doubling)
    If b_i = 1:
      R = R + P     (point addition)
  Return R

The ECDLP: Given \(P\) and \(Q = nP\), find \(n\).

Forward computation (\(P \to nP\)) takes \(O(\log n)\) operations. The best known algorithm for the reverse (Pollard's rho) takes \(O(\sqrt{n})\) operations — exponential in the bit length of \(n\). There is no known sub-exponential algorithm for ECDLP on properly chosen curves.

Step 5: ECC Key Exchange (ECDH)

Public parameters: An elliptic curve \(E\) over \(\mathbb{F}_p\) and a base point \(G\) of order \(n\).

  1. Alice picks secret \(a\), computes \(A = aG\), sends \(A\) to Bob
  2. Bob picks secret \(b\), computes \(B = bG\), sends \(B\) to Alice
  3. Alice computes \(S = aB = a(bG) = abG\)
  4. Bob computes \(S = bA = b(aG) = abG\)

Both arrive at the same shared secret \(S = abG\), but an eavesdropper who sees only \(A = aG\) and \(B = bG\) cannot compute \(abG\) without solving the ECDLP.

Variables Explained

Symbol Name Description
\(E\) Elliptic curve The curve \(y^2 = x^3 + ax + b\)
\(\mathbb{F}_p\) Finite field Integers modulo prime \(p\)
\(a, b\) Curve parameters Define the shape of the curve
\(G\) Generator/base point A point of large prime order on the curve
\(n\) Order The smallest positive integer such that \(nG = \mathcal{O}\)
\(\mathcal{O}\) Point at infinity Identity element of the group
\(\lambda\) Slope Slope of the secant or tangent line
\(P, Q, R\) Points Points on the elliptic curve

Worked Example

A Tiny Curve: \(y^2 \equiv x^3 + 2x + 3 \pmod{5}\)

Finding points: Test each \(x \in \{0, 1, 2, 3, 4\}\):

\(x\) \(x^3 + 2x + 3 \mod 5\) \(y^2 \mod 5\) \(y\) values
0 3 3 no solution (\(y^2 \equiv 3\) has no root mod 5)
1 6 ≡ 1 1 \(y = 1, 4\)
2 15 ≡ 0 0 \(y = 0\)
3 36 ≡ 1 1 \(y = 1, 4\)
4 75 ≡ 0 0 \(y = 0\)

Points: \(\{(1,1), (1,4), (2,0), (3,1), (3,4), (4,0), \mathcal{O}\}\) — 7 points total.

Point addition: Compute \((1, 1) + (3, 1)\):

\[ \lambda = \frac{1 - 1}{3 - 1} = \frac{0}{2} = 0 \]
\[ x_3 = 0^2 - 1 - 3 = -4 \equiv 1 \pmod{5} \]
\[ y_3 = 0(1 - 1) - 1 = -1 \equiv 4 \pmod{5} \]

So \((1, 1) + (3, 1) = (1, 4)\).

Security Comparison

Security Level RSA Key Size ECC Key Size Ratio
80 bits 1024 bits 160 bits 6.4×
112 bits 2048 bits 224 bits 9.1×
128 bits 3072 bits 256 bits 12×
192 bits 7680 bits 384 bits 20×
256 bits 15360 bits 521 bits 29.5×

Common Mistakes

  • Using curves with small subgroups: The base point \(G\) must have large prime order. Curves with composite-order groups are vulnerable to small-subgroup attacks.

  • Not validating points: Always verify that a received point lies on the curve. Invalid curve attacks can leak the private key if points are not validated.

  • Rolling your own curves: Use standardized, audited curves (Curve25519, P-256, secp256k1). Poorly chosen parameters can hide backdoors.

  • Confusing ECC with RSA: ECC is not based on factoring. It's based on the discrete logarithm problem on elliptic curves. Different math, different attacks, different strengths.

  • Thinking ECC is quantum-safe: Like RSA, ECC is broken by Shor's algorithm (adapted for elliptic curves). Post-quantum alternatives are needed.

History

  • 1609 — Diophantus-style problems on cubic curves studied by Bachet
  • 1850s — Weierstrass develops the theory of elliptic functions
  • 1985 — Koblitz and Miller independently propose ECC
  • 1987 — Lenstra uses elliptic curves for integer factoring (ECM)
  • 1999 — NIST standardizes elliptic curves for federal use (P-256, P-384, P-521)
  • 2005 — NSA announces Suite B, recommending ECC for classified communication
  • 2006 — Daniel Bernstein publishes Curve25519
  • 2011 — Ed25519 signature scheme published
  • 2013 — Snowden revelations raise concerns about NIST curves; Dual_EC_DRBG backdoor confirmed
  • 2018 — TLS 1.3 defaults to ECDHE key exchange
  • 2020 — Ed25519 becomes the default SSH key type in OpenSSH

References

  • Koblitz, N. (1987). Elliptic Curve Cryptosystems. Mathematics of Computation, 48(177), 203–209.
  • Miller, V. S. (1986). Use of Elliptic Curves in Cryptography. Advances in Cryptology — CRYPTO '85, LNCS 218, 417–426.
  • Bernstein, D. J. (2006). Curve25519: New Diffie-Hellman Speed Records. Public Key Cryptography — PKC 2006, LNCS 3958, 207–228.
  • Washington, L. C. (2008). Elliptic Curves: Number Theory and Cryptography. Chapman & Hall/CRC.
  • Hankerson, D., Menezes, A., & Vanstone, S. (2004). Guide to Elliptic Curve Cryptography. Springer.