4
$\begingroup$

I am trying to understand point addition in RFC8032 section 5.1.4, which references the paper "Twisted Edwards Curves Revisited" (https://eprint.iacr.org/2008/522.pdf) to describe the quick way they perform twisted Edwards curve addition with fewer inversions.

I am reading through the paper and it makes sense until I get to the statement in section 3.1 under figure (5), which says that the unified addition formulae for extended coordinates are somehow derived from the affine addition formulae in figure (1). I cannot for the life of me understand how the formula $$ X_3\:=\:\left(X_1Y_2\:+\:Y_1X_2\right)\left(Z_1Z_2-dT_1T_2\right)$$

can be derived from the formula $$X_3\:=\:\frac{\left(X_1Y_2\:+\:Y_1X_2\right)}{\left(1+dT_1T_2\right)}$$ even with the extended coordinates, and dividing every X1 or Y1 by Z1. Can anyone explain their derivation to me?

$\endgroup$

1 Answer 1

3
$\begingroup$

To convert extended twisted Edwards coordinates to extended projective coordinates one needs to divide

$$X_3 = (X_1Y_2 + Y_1X_2)(Z_1Z_2 − d T_1T_2)$$

by

$$Z3 = (Z_1Z_2 − d T_1T_2)(Z_1Z_2 + d T_1T_2)$$

\begin{align}\frac{X_3}{Z_3} & = \frac{(X_1Y_2 + Y_1X_2)\color{red}{(Z_1Z_2 − d T_1T_2)}}{\color{red}{(Z_1Z_2 − d T_1T_2)}(Z_1Z_2 + d T_1T_2)} & \text{//cancels}\\[1.5ex] & = \frac{(X_1Y_2 + Y_1X_2)}{(Z_1Z_2 + d T_1T_2)}\\[1.5ex] & = \frac{\frac{(X_1Y_2 + Y_1X_2)}{\color{blue}{Z_1Z_2}}}{\frac{(Z_1Z_2 + d T_1T_2)}{\color{blue}{Z_1Z_2}}} & \text{//divide by } Z_1Z_2 \tag{1}\label{lab1}\\[1.5ex] & = \frac{\frac{\color{green}{X_1}Y_2}{\color{green}{Z_1}Z_2} + \frac{Y_1X_2}{Z_1Z_2} } {\frac{Z_1Z_2}{Z_1Z_2} + \frac{d T_1T_2}{Z_1Z_2} } & { use } X/Z \to Z, Y/Z \to Z\\[1.5ex] & = \frac{(X_1Y_2 + Y_1X_2)}{(1 + d T_1T_2)} \end{align}

Step $\ref{lab1}$ is the confusing step, the coordinates are still in the extended twisted Edwards coordinates need to be translated.

$\endgroup$
2
  • $\begingroup$ Ahhhh okay... so: X in the extended coordinates is equal to (the affine x)/Z, Y in the extended is equal to (the affine y) / Z, Z in the extended coordinates is equal to Z * Z, and T in the extended coordinates is equal to (the affine x * the affine y) / Z. I think I got confused when the paper said that (X : Y : Z) can be passed from the projective coordinates to the extended coordinates by computing T as XY instead of XY / Z; Z was probably understood to be 1 most of the time when passing from projective to extended. $\endgroup$ Sep 21 at 4:50
  • $\begingroup$ It is completely agreeable to have confusion since they both use the same letters that is hard to follow... $\endgroup$
    – kelalaka
    Sep 21 at 7:04

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.