Safe elliptic curve point addition using projective coordinates: How do I tell if the points are the same?

Question

I am trying to implement elliptic curve point addition in hardware for NIST p256 and p384 curves. I have noticed the following issue with the suggested NIST routines:

Consider routine 2.2.7 of http://www.nsa.gov/ia/_files/nist-routines.pdf: Point addition $R = S + T$ is not valid for the case $S = T$ (this would be a point doubling).

1. Is it correct to state that before performing point addition, you must first check if the two points are the same point and if they are the same point then perform a point doubling instead? If so how do you test if the points are the same?

2. I am using Jacobian coordinates for my intermediate computations so a given point may have a large number of congruent representations: $(x,y) \mapsto (x/Z^2,y/Z^3,Z)$, e.g. $(16,64,1) \equiv (4,4,2) \equiv (p+16, p+64,1)\equiv\dots$.

   How does one determine if two points are the same if they have a large number of possible representations?

   A naive method could be that before performing point addition to convert back to affine coordinates and reduce all coordinates to the range $0 \leq x < p$ so then both points have a unique representation but this defeats the purpose of using projective coordinates which is to avoid modular inverse during intermediate computation. In this case it would be better to do all computation in affine coordinates. There must be an easier way to test if $S \equiv T$ without doing this but I have not found many references to this problem. How is this handled in the real world?

In addition to using Jacobian coordinates, all of my intermediate results are not bounded by $0 \leq n < p$ but are instead bounded by $0 \leq n < M*p$ where $1 \leq M < 2^r$ which is because of my modular multiplication algorithm which has not posed an issue except if trying to determine if the two points are congruent. This increases the search space in affine coordinates to $M$ possible congruent points.

Does there exist a safe addition algorithm for generalized curves?

Inb4 use Edwards curves: I am required to support NIST p256 and p384 curves so I can't pick arbitrary curves.

Answer 1

The routine you link to is already performing that check (lines 15-17): it returns $(0,0,0)$ when $S$ and $T$ are equal, and the caller is expected to handle this by calling the doubling routine.

The equality verification is performed by checking whether $$X_1Z_2^2 - X_2Z_1^2 = 0$$ $$Y_1Z_2^3 - Y_2Z_1^3 = 0$$

It is easy to see that, since $x = X/Z^2$ and $y = Y/Z^3$, the above equations only hold when the points are equal. Indeed, if neither point is at infinity, $$ X_1/Z_2^2 - X_2/Z_1^2 = \frac{X_1Z_1^2-X_2Z_2^2}{(Z_1Z_2)^2}, $$ $$ Y_1/Z_2^3 - Y_2/Z_1^3 = \frac{Y_1Z_1^3-Y_2Z_2^3}{(Z_1Z_2)^3}. $$

We can safely ignore the denominator, since the result is $0$ if and only if the numerator is $0$.

While this implementation is correct, I would not call it safe; timing or power usage information could be used to learn a secret key. This is a good overview of what can happen, and the available options to counter it.

Answer 2

For my software "Academic Signature", this necessary check for equality is explained with a code snippet here. Contrasting the statements by Bernstein and Lange, this check can easily be done in a very efficient way.

You can view the full routines of my implementation if you look at the open source code and search for the routine "int proj_jacobian::add(proj_jacobian* summand, ellipse* ewp)" in the module "elliptic1.cpp".