1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.