Elliptic curve cryptography, or how a factoring attack became the internet's key
In 1984, a pre-print from Hendrik Lenstra of the University of Amsterdam reached Neal Koblitz’s office at the University of Washington in Seattle. Lenstra had found a new algorithm for factoring large integers — the hard problem that kept RSA safe — and the key structure in his method was an elliptic curve (Lenstra elliptic-curve factorization, Wikipedia). For most cryptographers, the reasonable response was concern. Koblitz, a number theorist whose training ran through algebraic geometry, had a different one: if elliptic curves could threaten a cipher, could they build one?
Working simultaneously and without any knowledge of Koblitz’s thinking, Victor S. Miller at IBM Research in Yorktown Heights, New York, arrived at the same question. At the CRYPTO '85 conference in Santa Barbara, California, Miller presented “Use of Elliptic Curves in Cryptography” — proposing an analogue of Diffie-Hellman key exchange built on elliptic curve arithmetic rather than ordinary modular exponentiation. Koblitz’s parallel paper, “Elliptic Curve Cryptosystems,” appeared in Mathematics of Computation in 1987, developed with no knowledge that Miller had got there first.
An elliptic curve, in the cryptographic sense, is not the oval from high school geometry. Defined over a finite field, it is the set of points satisfying an equation of the form y² = x³ + ax + b, with a precisely defined rule for “adding” any two points together. That addition rule gives the points a group structure, and groups are the algebra on which every public-key cipher rests. The security of ECC depends on the Elliptic Curve Discrete Logarithm Problem: given a point P and a second point Q where Q = nP, find n. For well-chosen curves and large parameters, no known method makes this feasible (Wikipedia).
The practical payoff is stark. A 256-bit ECC key provides roughly the same security as a 3072-bit RSA key — a twelve-fold difference in key length with equivalent resistance to attack (Wikipedia). For a web server handling millions of handshakes per day, or a microcontroller with eight kilobytes of RAM, that ratio is not incidental. It determines whether the scheme is deployable at all.
Neither Koblitz nor Miller patented their discovery. Koblitz, who spent years arguing that mathematical ideas belong to everyone, would not have considered it (whatisbitcoin.com). The result was that ECC entered the public domain the day it was announced — which turned out to matter considerably when standards bodies were choosing what to recommend two decades later.
Adoption was slow regardless. Despite the 1985 presentations, ECC did not reach widespread commercial use until around 2004, when NIST and ANSI X9 standards pushed it into TLS implementations (Wikipedia). By then the case was settled: smaller keys, faster computation on constrained hardware, no patent thicket to navigate. Today, ECDH handles key exchange in virtually every HTTPS connection; Bitcoin uses the secp256k1 curve for transaction signatures; Signal’s Double Ratchet relies on Curve25519.
The mathematics Lenstra aimed at RSA turned out to be the same mathematics that would quietly replace it. The curves kept their shape. Only the direction changed.
Sources
- Elliptic-curve cryptography — Wikipedia — key size comparisons (256-bit ECC ≈ 3072-bit RSA), the discrete logarithm problem, adoption timeline, modern applications in TLS, Bitcoin, and Signal.
- Use of Elliptic Curves in Cryptography — Victor S. Miller (1985), Semantic Scholar — the original CRYPTO '85 paper proposing elliptic curve Diffie-Hellman.
- Who Is Neal Koblitz? — whatisbitcoin.com — Koblitz’s background, the Lenstra pre-print connection, Miller’s concurrent discovery, the patent decision.