formulas for adding points on curve25519

Question

Curve25519 is a Montgomery curve. https://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html#diffadd-dadd-1987-m-3 gives a set of formulas for adding two points (well, more specifically, the X coordinate in XZ form):

  A = X2+Z2
  B = X2-Z2
  C = X3+Z3
  D = X3-Z3
  DA = D*A
  CB = C*B
  X5 = Z1*(DA+CB)2
  Z5 = X1*(DA-CB)2

This series of formulas gives 3x XZ coordinates - not 2x. (X2, Z2), (X3, Z3) and (Z1, X1). If I'm trying to add two points I'd expect two sets of XZ coordinates - not 3x.

Are the formulas wrong or am I missing something?

Answer 1

Classically, if you want to add two points $P = (x_2,y_2)$ and $Q = (x_3, y_3)$, you need all coordinates to compute $R = P+Q = (x_5, y_5)$.

The geometric relation between those points are that $P$, $Q$ and $-R = (x_5, -y_5)$ are aligned. Now, suppose you know only the $x$-coordinates of $P$ and $Q$, meaning you cannot differentiate between $P$ and $-P$ on one hand, and $Q$ and $-Q$ on the other hand. So there are four possible outputs: $P + Q$, $P - Q$, $-P + Q$ and $-P - Q$. We can remark here that $P + Q$ and $-P -Q$ share the same $x$-coordinate $x_5$ according to the previous notation, and $P - Q$ and $- P + Q$ the same $x$-coordinate. Let's call it $x_5'$.

This means by knowning only $x_2$ and $x_3$ we can get the two possible resulting $x$-coordinates of $P+Q$ or $P-Q$. So if you know the $x$-coordinate of $P - Q$, you can compute $P + Q$. That's what happens in the formula you quoted: the coordinates $X_1$ and $Z_1$ correspond to the point $P - Q$.

This is useful for the Montgomery scalar multiplication. It takes on input a point $P$ and compute $nP$ where $n$ is a scalar. At each step of the algorithm, the addition always involve two points $R_0$ and $R_1$ such that $R_1 - R_0 = P$ is a constant. So, since this is known, the addition can always be performed using only the $x$-coordinate (well, $XZ$ projective coordinates).

This can work for other model of curves, but in the case of Montgomery curves, it gives pretty fast formulas for addition and doubling!