Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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:

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) => (X/Z^2,Y/Z^3,Z)$ e.g. a point $(16,64,1) ≡ (4,4,2) ≡ (p+16, p+64,1), …$.

    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 <= 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 ≡ 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 <= n <= p$ but are instead bounded by $0 <= n <= M*p$ where $1 <= 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.

share|improve this question
add comment

1 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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