Adding points — Signatures by Hand, lesson 2

Adding points

The chord-and-tangent rule turns two points into a third. It is the only operation elliptic-curve cryptography ever performs.

A set of points is not yet useful. What makes elliptic curves interesting is that you can add two of their points and land on a third — and that this addition behaves like ordinary addition in every way that matters: it is associative, it has an identity, and every element has an inverse. That structure is called a group, and cryptography is built out of it.

The rule comes from geometry, and it is easiest to see over the real numbers before returning to the finite field. Draw the line through P and Q. A cubic and a line meet in exactly three places, so that line hits the curve at one further point. Reflect that third point across the horizontal axis, and the result is defined to be P + Q.

The reflection looks arbitrary and is not. It is what makes the operation associative: with it, the rule becomes “any three collinear points sum to zero”, which is a statement that does not care what order you take the points in. Without it, you would have a construction rather than an arithmetic.

The same rule as algebra

chord and tangent

when P != Q                      when P = Q (doubling)
  lambda = (y2 - y1) / (x2 - x1)   lambda = (3*x1^2 + a) / (2*y1)

then, in both cases
  x3 = lambda^2 - x1 - x2
  y3 = lambda*(x1 - x3) - y1

everything reduced mod p

Two cases, because two points that coincide do not define a chord — the line through them is the tangent, whose slope comes from differentiating the curve equation. And one special case: if Q is the mirror image of P, the line through them is vertical, meets the curve nowhere else, and the sum is the point at infinity. That is precisely what it means for O to be the identity.

The word / in those formulas is the one thing that changes in a finite field. There are no fractions modulo 17. Dividing by 3 means multiplying by the number that turns 3 into 1 — here 6, because 3·6 = 18 = 1. That number is the modular inverse, it exists for every non-zero value precisely because 17 is prime, and it is found with the extended Euclidean algorithm in a handful of steps. Every division in the rest of this course is an inverse in disguise.

Your turn

Compute P + Q by hand

On y² = x³ + 2x + 2 over F₁₇, take P = (5, 1) and Q = (6, 3). Three lines of arithmetic get you the answer; every subtraction and every product is reduced modulo 17 as you go.

the rule

lambda = (y2 - y1) * inv(x2 - x1)   mod p      (chord, when P != Q)
x3     = lambda^2 - x1 - x2         mod p
y3     = lambda*(x1 - x3) - y1      mod p

P + Q =

What is inv(1) here, and how do I divide at all?

You never divide. inv(a) is the number that multiplies a to 1 modulo 17, and multiplying by it plays the role of dividing. Here x2 − x1 = 1, and inv(1) = 1, so this particular slope is easy. The full table for F₁₇, worth a glance because lesson 5 needs it again:

 a   |  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
inv  |  1  9  6 13  7  3  5 15  2 12 14 10  4 11  8 16

Read it as: 2·9 = 18 = 1, 3·6 = 18 = 1, 5·7 = 35 = 1, and so on modulo 17. Every non-zero element has exactly one inverse, which is what makes 17 being prime matter.

P and Q on the curve. Do the algebra first — once you have checked an answer, the line through them appears here and you can see the geometry the formulas were describing.

What you now know

P + Q is the third intersection of the line PQ with the curve, mirrored across the x-axis.
The slope λ has two forms: a chord when P ≠ Q, a tangent when P = Q.
Division in a finite field means multiplying by a modular inverse — never a fraction.