0
$\begingroup$

I am having a hard time understanding how to convert from projective coordinates, back to affine.

I am trying to compute point addition for Edward curves. Say we have the following: $$\begin{align} x_i &= X_i/Z_i\\ y_i &= Y_i/Z_i\\ A &= Z_1*Z_2\\ B &= A^2\\ C &= X_1*X_2 \\ D &= Y_1*Y_2 \\ E &= d*C*D\\ F &= B-E\\ G &= B+E\\ X_3 &= A* F*((X_1+Y_1)*(X_2+Y_2)-C-D)\\ Y_3 &= A* G*(D-C)\\ Z_3 &= c* F*G\\ \end{align}$$

[Editor's note: equations match hyperelliptic.org's add-2007-bl]

Now after obtaining values for $X_3$ and $Y_3$, to get back to affine coordinates, would I have to compute $X_3/Z_3$ and $Y_3/Z_3$ to get $(x_3,y_3)$ ?

$\endgroup$
  • 1
    $\begingroup$ Yes.­­­­­­­­­­­ $\endgroup$ – yyyyyyy Jan 18 '18 at 18:00
2
$\begingroup$

Yes, after obtaining values for $X_3$ and $Y_3$ (and $Z_3$), in order to get back to affine coordinates, one would have to compute $X_3/Z_3$ and $Y_3/Z_3$ to get $(x_3,y_3)$.

However, in most cryptographic applications, we're making point multiplication with a large multiplier, which requires many point additions, which can be carried entirely in projective coordinates. We get back to affine coordinates only at the end of that. Therefore, the field inversion required to get back to affine coordinates is performed once per point multiplication, and represents a low proportion of the computational cost.

Whatever the base field, one can use the extended Euclidean algorithm to compute $1/Z_3$; or better the half-extended version there, which is specialized for the inverse; or $1/Z_3={Z_3}^{p-2}$ where $p$ is the number of elements in the base field. For the base field $\mathbb Z_p$ with $p$ prime, there's also the half-extended binary GCD algorithm there.

| improve this answer | |
$\endgroup$
2
$\begingroup$

would I have to compute X3/Z3X3/Z3 and Y3/Z3Y3/Z3 to get (x3,y3)(x3,y3)

Yes. The way you do division here is multiplying the nominator with the Modular_multiplicative_inverse of the denominator.

Note that a naive implementation of extended euclidean is vulnerable to side-channel attacks, so using exponentiation using a hardcoded addition chain is often preferred for computing the inverse.

| improve this answer | |
$\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.