Elliptic curves

Your Pearl private key is just a huge random number. Your public key is a point on a curve, made from that number. The magic is that the step from one to the other only works in one direction.

That one-way step is the arithmetic of an elliptic curve. Pearl uses the same curve as Bitcoin, called secp256k1. This page builds the idea on a tiny toy curve you can check by hand, then scales it up.

Try it

Pick two points and add them, or multiply a point by a number, and watch the result jump around the dots.

What is an elliptic curve?

It’s the set of points (x, y) that satisfy one equation. Pearl’s curve uses about the simplest one possible:

Over ordinary numbers that draws a smooth curve. But cryptography uses whole numbers with modular arithmetic, where everything wraps around at a prime p, like a clock. With p = 17, for example, 15 + 5 = 20 wraps to 3.

On a toy curve with p = 17, only 17 points (x, y) fit the equation. Add one special point, the “point at infinity”, which plays the role of zero, and there are 18 points in all.

How do you add two points?

Geometrically: draw a straight line through the two points. It crosses the curve at exactly one more point. Flip that point to the other side (negate its y) and you have the sum.

To add a point to itself (“doubling”), use the tangent line at that point instead. And adding a point to its mirror image gives the point at infinity, the zero of this arithmetic.

On a modular curve there’s no picture to draw, but the same rule becomes a formula. Here is G + 2G on the toy curve, with G = (6, 6) and 2G = (1, 5), all arithmetic mod 17:

1. The slope

   $\lambda = \dfrac{y_2 - y_1}{x_2 - x_1} = \dfrac{5 - 6}{1 - 6} = \dfrac{-1}{-5} = \dfrac{1}{5}$. Dividing by 5 mod 17 means multiplying by 7, because 5 × 7 = 35 = 2 × 17 + 1. So λ = 7.

2. The new x

   $x_3 = \lambda^2 - x_1 - x_2 = 49 - 6 - 1 = 42 \equiv 8$

3. The new y

   $y_3 = \lambda(x_1 - x_3) - y_1 = 7 \cdot (6 - 8) - 6 = -20 \equiv 14$

4. Check

   (8, 14): 14² = 196 ≡ 9, and 8³ + 7 = 519 ≡ 9. On the curve. That’s 3G.

What does it mean to multiply a point?

Multiplying G by a number k means adding G to itself k times: 3G = G + G + G. Here are all the multiples on the toy curve:

At 18 it wraps back to the point at infinity and starts again. The number of steps before the wrap, 18 here, is called the order.

This is exactly how keys work. Pick a secret number, say 5: that’s the toy private key. Multiply the generator point: 5G = (10, 15). That’s the toy public key.

For a real 256-bit key, adding G to itself trillions of trillions of times would take forever. Computers use double-and-add instead: write k in binary, double for every bit and add G for every 1 bit. A 256-bit key takes about 256 doublings, which is instant.

Why can’t anyone work backwards?

Going from 5G back to 5 means asking “how many times was G added?” That’s the discrete logarithm problem.

On the toy curve it’s trivial: try G, 2G, 3G… and you’re done within 18 steps. Nothing smarter is needed. On secp256k1 the same search has about 10⁷⁷ steps, and the best known methods only take that down to about 2¹²⁸ steps, still far beyond every computer on Earth. That gap between “easy forwards” and “impossible backwards” is what keeps a private key private.

What are secp256k1’s real numbers?

secp256k1 is the toy curve with enormous numbers. Same equation, y² = x³ + 7:

A private key is any number from 1 to n − 1, about 1.16 × 10⁷⁷ choices. Its public key is that number times G. Here are the first three, computed with this site’s code:

Private key 1 gives G itself. Nobody should use these keys: anyone can compute them.

How is a point written down?

A point is two 32-byte numbers, x and y. Pearl writes it in one of two short forms:

• Compressed, 33 bytes: a prefix 02 or 03 saying whether y is even or odd, then x. Used in extended keys and fingerprints.
• X-only, 32 bytes: just x, with y assumed even. Everything on chain uses this: Taproot output keys, Schnorr signatures and tapscript keys.

Each x has only two possible y values (y and p − y, one even, one odd), so the short forms lose nothing.

const p = 17;
const mod = (a) => ((a % p) + p) % p;
const inv = (a) => { let r = 1, b = mod(a), e = p - 2; while (e) { if (e & 1) r = (r * b) % p; b = (b * b) % p; e >>= 1; } return r; };

function add(P, Q) {
  if (!P) return Q;
  if (!Q) return P;
  if (P.x === Q.x && mod(P.y + Q.y) === 0) return null;          // P + (−P) = ∞
  const l = P.x === Q.x
    ? mod(3 * P.x * P.x * inv(2 * P.y))                          // tangent (doubling)
    : mod((Q.y - P.y) * inv(Q.x - P.x));                          // chord
  const x = mod(l * l - P.x - Q.x);
  return { x, y: mod(l * (P.x - x) - P.y) };
}

add({ x: 6, y: 6 }, { x: 1, y: 5 });   // { x: 8, y: 14 } = 3G