Elliptic Curve Cryptography: Fast Forward, Hard in Reverse

A curve, a field, and a geometric addition rule

An elliptic curve used in cryptography is the set of points (x, y) satisfying y² = x³ + ax + b, evaluated not over the real numbers but over a finite field of integers modulo a large prime p — so "the curve" is really a finite set of discrete (x, y) pairs plus one extra point at infinity that acts as the identity element. What makes it useful for cryptography is that this finite point set can be given a group structure: there is a well-defined way to "add" two points on the curve and get a third point also on the curve.

Point addition: chord and tangent, over a finite field

Geometrically (easiest to picture over the reals before reducing mod p): to add two distinct points P and Q, draw the straight line through them, find its third intersection with the curve, and reflect that point across the x-axis to get P + Q. To add a point to itself (doubling), use the tangent line at that point instead of a chord. Every step, arithmetic modulo p replaces real-number arithmetic, but the algebraic formulas are the same:

doubling P = (x, y), P ≠ O, y ≠ 0:
  λ = (3x² + a) / (2y)   mod p
  x3 = λ² − 2x        mod p
  y3 = λ(x − x3) − y   mod p

adding P=(x1,y1), Q=(x2,y2), x1 ≠ x2:
  λ = (y2 − y1) / (x2 − x1)   mod p
  x3 = λ² − x1 − x2         mod p
  y3 = λ(x1 − x3) − y1          mod p

Division here means multiplying by the modular inverse, computed with the extended Euclidean algorithm; every operation stays inside the finite field, and the closure of the field under these operations is exactly what guarantees P + Q always lands back on the curve, never off it.

Scalar multiplication: the easy direction

A private key is a random integer k; the corresponding public key is the point kG — the base point G added to itself k times — computed efficiently with double-and-add: to compute kG, write k in binary and, scanning the bits, repeatedly double the running point and add G whenever the current bit is 1. This takes only about log₂(k) doublings and additions, so even a 256-bit private key needs only a few hundred point operations, each of which is itself just a handful of modular multiplications — fast enough to run on a smart card.

double_and_add(k, G):
  R = O                      // point at infinity, the identity
  for bit in binary(k), most significant first:
    R = R + R                // double
    if bit == 1: R = R + G   // add
  return R                   // = kG, computed in O(log k) steps

Why reversing it is hard: the discrete logarithm problem

Given G and the public key Q = kG, recovering k is the Elliptic Curve Discrete Logarithm Problem (ECDLP), and no algorithm is known that solves it faster than roughly √p steps for a well-chosen curve over a field of size p (the best general attacks, Pollard's rho among them, run in time proportional to the square root of the group's order). Contrast this with ordinary modular exponentiation, whose analogous discrete-log problem falls to sub-exponential index-calculus attacks; elliptic curve groups have no known equivalent shortcut, which is exactly why a 256-bit elliptic curve key offers roughly the same practical security as a 3072-bit RSA key — smaller keys, faster operations, for the same resistance to attack.

What ECC is actually used for

ECDH (Elliptic Curve Diffie-Hellman) lets two parties who exchange only their public points, kG and jG, each independently compute the same shared secret kjG without ever transmitting k or j, securing the key exchange behind almost every modern HTTPS connection. ECDSA (Elliptic Curve Digital Signature Algorithm) uses the same hard-to-reverse scalar multiplication to let a holder of private key k produce a signature that anyone with the public key kG can verify, but that nobody without k could have produced — the mechanism behind Bitcoin transaction signatures and TLS certificate verification alike. Both rest entirely on the same asymmetry demonstrated in this simulation: walking forward around the curve k times is fast, but figuring out k from where you landed is not.

Frequently asked questions

Try it live

Everything above runs in your browser — open Elliptic Curve Cryptography and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.