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.

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).