1
$\begingroup$

I'm implementing an elliptic curve system primarily for ECDSA verification. I've evaluated different point representations and decided that using Jacobian projective coordinates suits best for my needs. Using this representation the point at infinity $\infty$ corresponds to $(X:Y:Z)$ = $(1:1:0)$.

As it is required to check for the point at infinity $\infty$ inside the point doubling and point addition functions, I'm currently comparing all three coordinates of an elliptic curve point to $(1:1:0)$. My question here is, if it would already be enough to check only for $Z=0$. As you can imagine this could make some difference in terms of performance, as doublings and additions are repeatedly called for point multiplication and omitting the check for $X$ and $Y$ would thus reduce some time.

Is checking for $Z=0$ enough? Could there be any corner cases for which I get $Z=0$ but actually have not reached the point at infinity? I've tested it with a high number of ECDSA verifications, and it seems to work but who knows if I have really tested the "special" cases especially on curves with 512-bit order.

$\endgroup$
4
$\begingroup$

The curve equation for an elliptic curve in Jacobian form is

$$Y^2 = X^3 + aXZ^4+bZ^6.$$

If $Z=0$, then $Y^2=X^3$, and all points satisfying this are of the form $(\lambda^2 :\lambda^3:0)$, where $\lambda$ is in the finite field you are working over. Projectively, these are all equal to $(1 : 1 : 0)$, and therefore the only point on the curve satisfying $Z=0$ is $(1 : 1 : 0)$. This is why we refer to it as the point at infinity, and not a point at infinity (points with $Z=0$ can be thought of as lying at infinity).

Assuming that your points are one the curve, it is therefore enough to check that $Z=0$.

$\endgroup$
2
$\begingroup$

In general it is wrong to check for $(X:Y:Z)==(1:1:0)$. While correct from a mathematical point of view, your addition and doubling formula will, most likely, never output $(1:1:0)$. In general, what happens when $\infty$ is produced as output of a computation is that the $Z$ will become $0$, but you can't expect the other coordinates to become $1$.

However, it all depends on the exact explicit formulas you are using.

And you should give it a try with specially crafted inputs (which depends on your implementation of the scalar multiplications).

But, in general, I believe that checking $Z=0$ is much better than checking $(X:Y:Z)==(1:1:0)$.

$\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.