Elliptic Curve Cryptography (ECC / ECDSA)

Elliptic Curve Cryptography builds public-key systems on the algebra of points on an elliptic curve over a finite field, rather than on integer factorization. The hard problem here is the elliptic curve discrete logarithm problem (ECDLP): given a starting point G and a resulting point Q = kG (k applications of a 'point addition' operation), it's computationally infeasible to recover k.

Crucially, no sub-exponential classical algorithm is known for ECDLP the way one exists for factoring — which means ECC achieves equivalent classical security to RSA with far smaller keys. A 256-bit ECC key is considered roughly as strong as a 3072-bit RSA key.

"Adding" two points on an elliptic curve has a genuinely geometric definition, which is part of why ECC feels less intuitive than RSA's arithmetic at first. To add two distinct points P and Q, draw a straight line through them — since the curve is cubic, that line crosses it at exactly one more point. Reflecting that third point across the x-axis gives P + Q. This isn't a metaphor for the algebra; it's literally how the group operation is defined, and it has a closed-form algebraic formula that a computer evaluates directly, with no actual line-drawing involved.

Doubling a point (adding P to itself, needed whenever a bit of the private key is 1 during scalar multiplication) works the same way in the limit: instead of a line through two distinct points, you use the tangent line at P.

Computing Q = kG for a 256-bit private key k doesn't mean adding G to itself k times — that would be astronomically slow. Instead, implementations use double-and-add, the same square-and-multiply idea behind fast RSA exponentiation: scan the bits of k, doubling a running point at every step and adding G whenever that bit is 1. A 256-bit scalar multiplication takes on the order of 256 doublings and up to 256 additions — fast enough to run thousands of times per second, while still being, as far as anyone knows, computationally impossible to reverse.

Real curves use primes hundreds of bits long, but the arithmetic works identically at toy scale. Take the curve y² = x³ + 2x + 2 (mod 17) — a small finite field with only 17 possible values for each coordinate — with base point G = (5, 1).

Computing 2G (doubling G) using the curve's point-doubling formula gives (6, 3). Computing 3G = 2G + G gives (10, 6). An attacker who only sees G and 3G = (10, 6) has to recover the scalar 3 — trivial here with a 17-element field, but the identical computation over a 256-bit field is the ECDLP that underpins every ECC key in production.

The chord-and-tangent picture is the geometry; here's the algebra a computer actually evaluates. To add two distinct points P = (x₁, y₁) and Q = (x₂, y₂), compute the slope m = (y₂ − y₁) / (x₂ − x₁) — using the modular inverse for that division — then x₃ = m² − x₁ − x₂ and y₃ = m(x₁ − x₃) − y₁, all reduced mod p. Doubling a point uses the tangent slope instead: m = (3x₁² + a) / (2y₁).

Worked example: on the same curve, compute 2G + 3G using 2G = (6, 3) and 3G = (10, 6). The slope is m = (6−3)/(10−6) = 3/4 mod 17. The modular inverse of 4 mod 17 is 13 (since 4×13 = 52 ≡ 1), so m = 3×13 mod 17 = 39 mod 17 = 5. Then x₃ = 5² − 6 − 10 = 9 mod 17, and y₃ = 5×(6−9) − 3 = −18 mod 17 = 16. So 2G + 3G = (9, 16) — which is exactly 5G, confirming the arithmetic is consistent.

Just as the integers mod p form a group of size p−1 under multiplication, the points on an elliptic curve mod p form a group too — and counting every point (including the point at infinity) gives the curve's order. Hasse's theorem guarantees this count stays close to p+1, but the exact value matters enormously: if the order has small factors, the same small-subgroup confinement attack covered in the Diffie-Hellman module works against ECC too, forcing a shared secret into a tiny, brute-forceable set of possibilities.

The toy curve used throughout this module happens to have exactly 19 points (18 finite points plus infinity) — and 19 is prime. That's not a coincidence for a well-chosen curve: real production curves like secp256k1 and P-256 are specifically selected to have prime (or near-prime) order precisely so there are no small subgroups for an attacker to confine anything into.

On the toy curve (order 19), the ECDLP is small enough to brute force by hand: starting from G and repeatedly adding G, check after each addition whether the running point matches the target Q. With only 19 possible scalars, this terminates fast — but the exact same search against a 256-bit curve would need to check roughly 2²⁵⁶ points, which is the entire reason ECC is considered secure at that scale.

Smaller keys mean less data to transmit and store, faster key generation, and faster signing operations — which is why ECC dominates mobile, IoT, and high-volume TLS deployments. Curve25519 (for key exchange, as X25519) and Curve448 are widely used modern curves chosen partly to avoid pitfalls found in some earlier NIST-standardized curves.

The Elliptic Curve Digital Signature Algorithm (ECDSA) uses ECC to produce digital signatures — proof that a message came from the holder of a private key, without revealing that key. It's the signature scheme behind most modern TLS certificates and behind Bitcoin and Ethereum transaction signing.

ECDSA requires a fresh, truly random per-signature value (the nonce) for every signature. Reusing a nonce, or generating it with a weak random number generator, leaks the private key directly — this has caused real-world key compromises, including a widely cited 2010 Sony PlayStation 3 signing-key leak caused by a static nonce.

The ECDSA signing formula involves the nonce k algebraically alongside the private key d. If an attacker ever learns k for even one signature — through a weak RNG, a side-channel leak, or (as in the PS3 case) the same k reused across two different signatures — they can rearrange the signing equation to solve directly for d. This is a one-shot, deterministic break, not a probabilistic weakening: a single exposed nonce is equivalent to publishing the private key outright.

ECC's smaller keys and wide deployment make it, if anything, a more urgent migration target than RSA in some contexts — it's cryptographically broken by the same Shor's algorithm class of quantum attack, but it's embedded in more places (TLS 1.3 defaults, most modern certificate authorities, cryptocurrency).