An interactive intro to Elliptic Curve Cryptography

Hacker News · Mar 2, 2026 · Collected from RSS

Full Article

Suppose two people want to communicate privately over the internet. They could encrypt their messages, scrambling them so that only someone with the right secret key can read them. But that raises an immediate problem: how do they agree on that secret key in the first place? They can't whisper it to each other. Every message between them passes through the open internet, where anyone could be listening. One solution is public-key cryptography: each person has two linked keys, a private key they keep secret and a public key they share openly. The keys are mathematically related, but computing the private key from the public key is so hard it's effectively impossible. That one-way relationship is what lets you encrypt messages, agree on shared secrets, and sign data to prove authorship. The first widely used public-key systems were built on the difficulty of specific math problems. RSA relies on the fact that multiplying two large prime numbers is easy, but factoring the result back into those primes is extremely hard. Diffie-Hellman relies on a similar idea using exponents in modular arithmetic (clock arithmetic where numbers wrap around at a fixed value). Both systems work, and both are still in use. But they share a practical problem: the keys are enormous. A commonly recommended minimum for RSA today is 2048 bits (about 617 decimal digits), but for 128-bit security equivalence RSA needs 3072 bits. As we push for stronger security, the numbers grow fast: RSA key sizes grow much faster than security targets, because the underlying factoring attacks are sub-exponential. What if a different mathematical structure could give us the same guarantees (easy in one direction, effectively impossible in reverse) but with much smaller numbers? That structure exists, and it comes from the geometry of curves. Drawing the curve A mathematical equation can define a shape. Take the equation y=x2y = x^2, which says "y equals x squared." To draw it, you pick values of xx, compute yy, and plot each resulting point on a grid. Step through the process below: Each step picks an xx value, squares it to get yy, and places a dot at that coordinate. As the points accumulate, a curve appears: the parabola. The equation defined the shape all along; we just needed enough points to see it. Different equations produce different shapes. The equation x2+y2=1x^2 + y^2 = 1 gives a circle (every point at distance 1 from the center). Toggle between these below: An elliptic curve is another equation of this kind: y2=x3+ax+by^2 = x^3 + ax + bSelect y2=x3−x+1y^2 = x^3 - x + 1 in the demo above to see one. The x3x^3 term makes the right side grow much faster than the left, giving the curve its distinctive looping shape, different from the smooth symmetry of a circle or the open bowl of a parabola. Despite the name, elliptic curves have nothing to do with ellipses. The name comes from elliptic integrals, which arose historically when computing the arc length of an ellipse. The connection is purely mathematical and not worth worrying about. The constants aa and bb determine the curve's shape. Adjust the sliders below and watch the curve change. Click anywhere on the curve to place a point: Click a few different spots. Every point you place has a mirror: if (x,y)(x, y) is on the curve, then (x,−y)(x, -y) is too, because squaring a negative number gives the same result as squaring its positive counterpart ((−y)2=y2(-y)^2 = y^2). The curve is always symmetric across the x-axis. This symmetry will matter when we define addition. One constraint on the parameters: certain combinations of aa and bb produce a curve with a cusp or a self-intersection (a sharp point where the curve crosses itself). These are called singular curves, and they break the algebraic structure we need. Toggle between the three cases below to see what goes wrong: At a cusp, the curve comes to a sharp point where the tangent line is undefined. At a self-intersection, two branches of the curve cross, giving two tangent lines at one point. Both situations break the point addition we're about to define, which depends on there being exactly one tangent line at every point. The mathematical condition for avoiding singularities is that the discriminant 4a3+27b2≠04a^3 + 27b^2 \neq 0. Cryptographic curves always satisfy this. We have a curve. Now what? The idea that turned this into cryptography was to define an arithmetic on the points of the curve: a way to "add" two points together and get a third point, also on the curve. Adding points on a curve The geometric construction goes like this. Take two points PP and QQ on the curve. Draw a straight line through them. Because the equation is cubic (the x3x^3 term), this line will generally intersect the curve at exactly one more point, call it R′R' (special cases like vertical lines or tangencies are handled by the point at infinity and the doubling rule). Now reflect R′R' over the x-axis, which means flipping its y-coordinate from positive to negative or vice versa. The reflected point RR is the result. We define P+Q=RP + Q = R. Move the sliders below to slide PP and QQ along the curve and watch the addition happen: The dashed line goes through PP and QQ. It hits the curve at R′R' (the unfilled circle). Reflecting R′R' over the x-axis gives us P+QP + Q (the red point). This "addition" isn't ordinary addition. We're not adding the coordinates together. We're using a geometric recipe (draw a line, find the intersection, reflect) to produce a new point from two existing ones. But mathematicians call it addition because it behaves like addition in the ways that matter. It's associative, meaning that P+(Q+R)=(P+Q)+RP + (Q + R) = (P + Q) + R. There's an identity element called the "point at infinity" OO, which acts like zero: P+O=PP + O = P for any point PP. And every point has an inverse: the point directly below (or above) it, the reflection, since P+(−P)P + (-P) gives the point at infinity. These properties make the curve's points a mathematical group. That's the algebraic structure the rest of this article depends on. The algebra behind this construction uses the line's slope. For two distinct points P=(x1,y1)P = (x_1, y_1) and Q=(x2,y2)Q = (x_2, y_2), the slope of the line through them is:m=y2−y1x2−x1m = \frac{y_2 - y_1}{x_2 - x_1}And the result point (x3,y3)(x_3, y_3) is:x3=m2−x1−x2,y3=m(x1−x3)−y1x_3 = m^2 - x_1 - x_2, \quad y_3 = m(x_1 - x_3) - y_1But what happens when PP and QQ are the same point? You can't draw a line through a single point. Instead, you use the tangent line, the line that just touches the curve at PP. Its slope comes from calculus (implicit differentiation of the curve equation):m=3x12+a2y1m = \frac{3x_1^2 + a}{2y_1}The rest of the formula is the same. This operation, adding a point to itself, is called point doubling, and it's the building block for everything that follows. Climbing the curve With point doubling, we can compute 2P=P+P2P = P + P. Then 3P=2P+P3P = 2P + P. Then 4P4P, 5P5P, and so on. Computing nPnP for some integer nn is called scalar multiplication: we're multiplying a point by a number to get another point. The naive approach takes n−1n - 1 additions: add PP to itself nn times. But there's a much faster method. To compute 100P100P, observe that 100=64+32+4100 = 64 + 32 + 4 in binary. So compute 2P2P, 4P4P, 8P8P, 16P16P, 32P32P, 64P64P by repeated doubling (six doublings), then add 64P+32P+4P64P + 32P + 4P (two additions). That's eight operations instead of 99. In general, computing nPnP takes roughly log⁡2(n)\log_2(n) operations using this double-and-add algorithm. Even for a 256-bit number (roughly 107710^{77}), that's only about 256 doublings and additions, which a computer does in a fraction of a second. Step through the computation of nGnG on a small curve: Watch the points hop around in what looks like a random pattern. Even on this small curve, there's no visible relationship between nn and the position of nGnG. The points don't march along the curve in any recognizable order. They scatter unpredictably. Elliptic curve cryptography depends on that apparent randomness. The trapdoor Going forward is easy: given PP and nn, computing Q=nPQ = nP takes roughly log⁡2(n)\log_2(n) steps using double-and-add. Going backward is hard: given PP and QQ, finding nn such that Q=nPQ = nP has no known shortcut on a well-chosen curve. This is a one-way function (sometimes called a trapdoor): easy to compute forward, practically impossible to reverse. Every public-key system has one. For RSA, multiplying two large primes is easy but factoring their product is hard. For elliptic curves, scalar multiplication is easy but recovering the scalar is hard. The problem of recovering nn is called the Elliptic Curve Discrete Logarithm Problem (ECDLP). The name "discrete logarithm" comes from an analogy with regular logarithms: in regular math, if bn=xb^n = x, then n=log⁡b(x)n = \log_b(x). Here, if nP=QnP = Q, we're looking for a kind of "logarithm" in the world of elliptic curve points. "Discrete" means we're working with integers, not continuous numbers. On a well-chosen curve, the best generic attacks (like Pollard's rho) require roughly O(n)O(\sqrt{n}) operations, no fundamentally better shortcut is known. Step through a brute-force search to see what "going backward" looks like: On the small curve in this demo, the search finishes quickly because nn is small. In real cryptography, nn is roughly 22562^{256} (a number with 77 digits). Even the best known algorithms would need about 21282^{128} operations. If every computer on Earth worked on the problem, it would take longer than the age of the universe. From smooth curves to scattered dots Everything so far used real-number coordinates: smooth curves, infinite precision, irrational slopes. Real cryptography can't work this way. Computers represent real numbers with floating-point arithmetic, which introduces tiny rounding errors. In cryptography, a single wrong bit means the wro