Elliptic-Curve Cryptography

An elliptic curve over a field `F` (in cryptography, a large finite field `F_p` or `F_{2^m}`) is the set of points `(x, y)` satisfying a cubic equation, together with a special point at infinity `O`. The most common form used in cryptography is the short Weierstrass equation: ``` y² = x³ + ax + b (mod p) ``` with the non-singularity condition `4a³ + 27b² ≠ 0 (mod p)`, which guarantees the curve has no cusps or self-intersections — a requirement for the group law below to be well defined. The remarkable fact is that the points on this curve, plus the point at infinity `O`, form an abelian group under a geometrically defined addition rule: draw the line through two points, find its third intersection with the curve, and reflect across the x-axis. This "chord-and-tangent" rule is associative — a nontrivial algebraic fact, provable via the theory of divisors on curves — with `O` as identity and each point `P = (x, y)` having inverse `−P = (x, −y)`. Cryptographic use replaces ordinary exponentiation `g^k mod p` with scalar multiplication `kP = P + P + ... + P` (`k` times), computed efficiently by double-and-add, the exact analog of fast modular exponentiation. The hard problem — the Elliptic Curve Discrete Logarithm Problem (ECDLP) — is: given `P` and `Q = kP`, find `k`. This is the same conceptual problem as The Discrete Logarithm Problem in `Z_p`, transported into a new group. What changes is the difficulty* of that problem relative to the group's size, which is the entire point of ECC.

Setting up the group. A curve for cryptography is specified by domain parameters: the field `F_p`, coefficients `a, b`, a base point `G` (the generator), the order `n` of `G` (smallest positive integer with `nG = O`), and a cofactor `h`. Standardized curves (P-256, Curve25519, secp256k1) fix these so implementers never choose them ad hoc — a poorly chosen curve can leak the private key.

Point addition (the group law). For two distinct points `P = (x1, y1)` and `Q = (x2, y2)` on `y² = x³ + ax + b`: ``` λ = (y2 − y1) / (x2 − x1) (slope of the line through P, Q) x3 = λ² − x1 − x2 y3 = λ(x1 − x3) − y1 ```

Point doubling (adding `P` to itself) uses the tangent line at `P` instead: ``` λ = (3x1² + a) / (2y1) x3 = λ² − 2x1 y3 = λ(x1 − x3) − y1 ``` All arithmetic is performed modulo `p`; division means multiplication by the modular inverse. If `x1 = x2` and `y1 = −y2`, the result is `O` (the lines are vertical, meeting the curve "at infinity").

Scalar multiplication computes `kP` using double-and-add, mirroring square-and-multiply exponentiation: ```pseudocode function SCALAR-MULT(P, k): // computes k P using the group law, k >= 0 if k == 0: return O // identity (point at infinity) R = O // accumulator Q = P // running doubling of P bits = BINARY-REPRESENTATION(k) // little-endian bit list for b in bits: if b == 1: R = POINT-ADD(R, Q) Q = POINT-DOUBLE(Q) return R ``` ```pseudocode function POINT-ADD(P1, P2): if P1 == O: return P2 if P2 == O: return P1 if P1.x == P2.x and P1.y != P2.y: return O // P2 == -P1 if P1 == P2: return POINT-DOUBLE(P1) lambda = (P2.y - P1.y) MOD-INVERSE(P2.x - P1.x, p) mod p x3 = (lambdalambda - P1.x - P2.x) mod p y3 = (lambda(P1.x - x3) - P1.y) mod p return (x3, y3) function POINT-DOUBLE(P): if P == O: return O if P.y == 0: return O // tangent is vertical lambda = (3P.xP.x + a) MOD-INVERSE(2P.y, p) mod p x3 = (lambdalambda - 2P.x) mod p y3 = (lambda*(P.x - x3) - P.y) mod p return (x3, y3) ```

Key exchange (ECDH). Alice picks a random private scalar `d_A ∈ [1, n-1]` and publishes `Q_A = d_A · G`. Bob does the same with `d_B, Q_B`. Both compute the shared secret: ``` S = d_A · Q_B = d_A · (d_B · G) = (d_A · d_B) · G = d_B · Q_A ``` An eavesdropper sees `G, Q_A, Q_B` but, to recover `S`, must either solve ECDLP to extract `d_A` or `d_B`, or solve the related Computational Diffie-Hellman problem directly in the curve group. This is the elliptic-curve analog of classical Diffie-Hellman, foreshadowing its full use inside The TLS Handshake.

Group operation cost. Each `POINT-ADD` or `POINT-DOUBLE` requires a constant number of finite-field operations: one modular inversion (or, with projective coordinates, none — inversions are deferred and batched) plus a handful of multiplications and additions mod `p`. Over a field with `w`-bit elements, each multiplication costs `O(w²)` with schoolbook arithmetic or `O(w^{1.585})` with Karatsuba, so one group operation costs `O(M(w))` where `M(w)` is the field-multiplication cost.

Scalar multiplication cost. `SCALAR-MULT` performs one doubling per bit of `k` and one addition per set bit, so for a `w`-bit scalar it costs `O(w)` group operations, i.e. `O(w · M(w))` total field operations — the direct analog of fast modular exponentiation's `O(w)` squarings and multiplications. This is efficient: computing `kP` naively by repeated addition would cost `O(k) = O(2^w)` operations, exponentially worse.

Correctness of double-and-add. The invariant maintained by the loop is: after processing bit `i` (from least significant), `R` holds `(k mod 2^{i+1}) · P`. Initially `R = O = (k mod 1)·P` trivially. If the invariant holds before processing bit `i`, then: ``` new R = R + [bit_i]·(2^i · P) = (k mod 2^i)·P + bit_i·2^i·P = (k mod 2^{i+1})·P ``` because `Q` is maintained as `2^i · P` at step `i` via repeated doubling. After all `w` bits are processed, `R = (k mod 2^w)·P = k·P` since `k < 2^w`. This is exactly the same inductive argument used to prove square-and-multiply correct for exponentiation.

Why the discrete log is hard here. The best general-purpose attack against ECDLP is Pollard's rho algorithm, which finds `k` in expected `O(√n)` group operations, where `n` is the order of the base point — using a birthday-paradox argument over a pseudo-random walk on the group. Crucially, there is no known analog of index calculus for generic elliptic curves. Index calculus is what makes classical discrete log (and factoring, via a related structure) breakable in sub-exponential time `L_p[1/3, c]`, because `Z_p*` has a rich supply of "smooth" elements (products of small primes) that let an attacker build linear relations. Elliptic-curve groups have no known analogous notion of smoothness, so Pollard's rho's `O(√n)` remains the best known attack for well-chosen curves.

The security-per-bit consequence. If `n ≈ 2^m`, breaking ECDLP costs about `2^{m/2}` group operations. To match 128-bit security, `m ≈ 256` bits suffices. RSA and classical DH, vulnerable to sub-exponential index calculus, need moduli of roughly 3072 bits for the same 128-bit security level — because their effective work factor is `L_p[1/3, c] = exp((c + o(1))(ln p)^{1/3}(ln ln p)^{2/3})`, not `√p`. This asymptotic gap — square-root security versus sub-exponential security — is precisely why ECC keys, ciphertexts, and signatures are so much smaller for equivalent strength.

Honest tradeoffs. ECC is not free of risk: curve parameters must be chosen carefully (some historical curves, and certain constructions with hidden structure, invite suspicion or admit attacks), implementations must run in constant time to avoid side-channel leakage during scalar multiplication, and special curves (supersingular curves, or curves with small embedding degree) can transfer ECDLP to an easier problem in a related finite field via the MOV attack — standard curves avoid this by design. Pairing-based and quantum threats (Shor's algorithm breaks ECDLP in polynomial time on a quantum computer, exactly as it breaks factoring) apply equally to ECC and classical schemes, motivating post-quantum alternatives.

Use the toy curve `E: y² = x³ + 2x + 2 (mod 17)`. Check non-singularity: `4(2)³ + 27(2)² = 32 + 108 = 140 ≡ 4 (mod 17) ≠ 0`, so the curve is valid. Take base point `G = (5, 1)`. Verify: `y² = 1`; `x³ + 2x + 2 = 125 + 10 + 2 = 137 ≡ 137 - 8·17 = 137 - 136 = 1 (mod 17)`. It checks out. Compute `2G` (point doubling at `(5,1)`): ``` λ = (3·5² + 2) · (2·1)^-1 mod 17 = (75 + 2) · 2^-1 mod 17 = 77 · 9 mod 17 (since 2·9=18≡1, so 2^-1 = 9) = 693 mod 17 = 693 - 40·17 = 693 - 680 = 13 x3 = λ² - 2x1 = 169 - 10 = 159 mod 17 = 159 - 9·17 = 159-153 = 6 y3 = λ(x1 - x3) - y1 = 13·(5 - 6) - 1 = 13·(-1) - 1 = -14 mod 17 = 3 ``` So `2G = (6, 3)`. Verify: `y² = 9`; `x³+2x+2 = 216+12+2 = 230 ≡ 230 - 13·17 = 230-221 = 9`. Correct. Now compute `3G = 2G + G = (6,3) + (5,1)`: ``` λ = (1 - 3) · (5 - 6)^-1 mod 17 = (-2) · (-1)^-1 mod 17 = (-2) · (-1) mod 17 (since (-1)^-1 = -1 mod 17) = 2 x3 = λ² - x1 - x2 = 4 - 6 - 5 = -7 mod 17 = 10 y3 = λ(x1 - x3) - y1 = 2·(6 - 10) - 3 = 2·(-4) - 3 = -11 mod 17 = 6 ``` So `3G = (10, 6)`. Verify: `y² = 36 ≡ 2`; `x³+2x+2 = 1000+20+2=1022 ≡ 1022 - 60·17 = 1022-1020 = 2`. Correct.

This traces `SCALAR-MULT(G, 3)` exactly: it reproduces `3G = (10,6)`, matching the direct chord computation above and confirming the double-and-add invariant. In a real ECDH exchange over this toy curve (never use it in practice — the field is far too small), if Alice's private key is `d_A = 3` her public key is `Q_A = 3G = (10, 6)`, published in the clear. Recovering `d_A = 3` from `G` and `Q_A` is the ECDLP; over a 17-element field brute force is instant, but over a 256-bit prime field it requires roughly `2^128` operations by Pollard's rho — computationally infeasible.

The elliptic-curve approach to public-key cryptography was proposed independently by two researchers who saw that the group law on elliptic curves — long studied in number theory for its role in Fermat-style Diophantine problems — could host the discrete logarithm problem far more efficiently than integer groups.

ECC is the workhorse of modern public-key infrastructure. TLS 1.3 uses ECDHE (Elliptic Curve Diffie-Hellman Ephemeral) almost exclusively for key exchange, giving every HTTPS connection forward secrecy at a fraction of the computational cost of RSA-based key transport — a mechanism explored fully in The TLS Handshake. SSH, WireGuard, and Signal's protocol rely on Curve25519 for both key agreement and, via EdDSA, signatures — the natural next topic after this one, Digital Signatures, builds ECDSA and Schnorr-style schemes directly on the scalar-multiplication machinery introduced here. Bitcoin, Ethereum, and most blockchain systems derive every wallet address and transaction signature from secp256k1 point arithmetic — an entire financial ecosystem resting on the hardness of ECDLP. Embedded devices, smart cards, and IoT sensors favor ECC precisely because a 256-bit key fits in far less memory and computes far faster than an RSA-equivalent key, extending battery life and reducing silicon area. Government and NIST-approved cryptographic suites (Suite B / CNSA) mandate ECC curves for classified and sensitive communications, reflecting confidence built over decades of cryptanalytic scrutiny.

Ask the tutor: How does the Pohlig-Hellman algorithm actually recombine discrete logs across small prime-order subgroups using the Chinese Remainder Theorem?