Elliptic-Curve Cryptography

Almost every secure connection you make — a banking app, a chat message, the padlock in your browser — leans on a single idea: an operation that is easy to do but hard to undo. RSA gets there by multiplying two giant primes; multiplying is cheap, factoring the product back is not.

Elliptic-curve cryptography (ECC) reaches the same goal with a different, more efficient trick. Take a gentle curve like $y^{2}$ = $x^{3}$ + ax + b, pick a starting point G, and define a strange kind of "addition" of points using nothing but a ruler. Adding G to itself k times is fast. But given only the final point, recovering the count k — the elliptic-curve discrete-log problem — appears to be astronomically hard.

The payoff is dramatic: a 256-bit ECC key offers roughly the same security as a 3072-bit RSA key. Smaller keys, faster math, less battery — which is exactly why your phone, your messaging app, and modern websites quietly moved to curves.

Here is a small curve over a finite field. There is a base point G, and a ruler-and-flip rule for "adding" points: draw the line through two points, find where it meets the curve a third time, and reflect that over the horizontal axis. To add a point to itself, use the tangent line.

<p class="hint">{{hint}}</p>
<canvas id="cv" width="360" height="300"></canvas>
<div class="readout" id="readout">P = G</div>
<div class="btns">
  <button id="add" type="button">{{btn_add}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<p class="dlp">{{dlp_prefix}} <b><span id="k">1</span></b>{{dlp_suffix}}</p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { background: #f7f9fb; border: 1px solid #cdd9e3; border-radius: 8px; display: block; max-width: 100%; }
.readout { font: 600 15px ui-monospace, monospace; color: #1d3557; margin: .6rem 0; min-height: 1.3em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.dlp { font-size: .88rem; color: #555; line-height: 1.45; margin: .7rem 0 0; }
.dlp b span { color: #c92f3c; }

// Code not found

Press Add G to compute G, 2G, 3G, … one hop at a time. Going forward is effortless — a short chain of additions lands you on kG. Now imagine I hand you only the red point and ask: how many times did I add G? With a tiny curve you could count. With a real 256-bit curve there are more points than atoms in the visible universe, and counting is hopeless. That asymmetry — easy forward, brutal backward — is the whole game, just like the discrete logarithm.

How hard is it really to break a curve? The security rests entirely on the elliptic-curve discrete-log problem (ECDLP): given G and kG, recover k.

• Forward is cheap. Computing kG takes only about $\log_{2}(*k*)$ point additions via repeated doubling — a few hundred operations even for a 256-bit k.
• Backward looks brutal. The best known general attacks (Pollard's rho, baby-step/giant-step) run in time around the square root of the group size — about $2^{128}$ steps for a 256-bit curve. That is why ECC keys can be so small relative to RSA.
• It is not proven hard. ECDLP is believed intractable, but there is no proof. Nobody has shown it lies outside P, and a clever classical algorithm could in principle exist — the same open uncertainty that surrounds P vs NP.
• Quantum changes everything. Shor's algorithm (1994) solves ECDLP in polynomial time on a large quantum computer, just as it cracks factoring. Curves are safe against today's machines, not tomorrow's.

Elliptic curves in cryptography were proposed independently by Neal Koblitz and Victor Miller in 1985. Four decades on, no efficient classical break exists — but "no one has broken it yet" is a very different statement from "it is provably hard."

You almost certainly used an elliptic curve in the last few minutes:

• The web (TLS/HTTPS): modern key exchange uses Curve25519 (X25519), so the padlock in your browser is backed by point addition.
• Messaging: Signal, WhatsApp and iMessage build their end-to-end encryption on Curve25519 key agreement.
• Cryptocurrency: Bitcoin and Ethereum sign transactions with ECDSA over secp256k1 — your wallet is a secret multiplier.
• Logins and devices: SSH keys, passkeys and smart cards favour ECC because small keys mean fast operations on constrained hardware.

The same one-way structure shows up across cryptography: the hardness of factoring guards RSA, and lattice problems like the shortest vector are the leading candidates for a post-quantum replacement once large quantum computers arrive.

Elliptic-curve cryptography turns a piece of nineteenth-century geometry into a twenty-first-century lock. Adding points with a ruler is fast; running the film backwards — recovering the multiplier — is the elliptic-curve discrete-log problem, and after forty years no one has found an efficient classical way to do it.

But notice the careful wording. ECC is not proven unbreakable; it is believed hard, in the same uneasy way as the questions behind P vs NP. And Shor's algorithm already breaks it in theory, waiting only for the hardware. The next time your browser shows a padlock, it is trusting a curve — and the bet that no one, classically, can walk that one-way street backwards.