In: Eric Brier and Marc Joye, Weierstrass Elliptic Curves and Side-Channel Attacks. In D. Naccache and P. Paillier, Eds., Public Key Cryptography, vol. 2274 of Lecture Notes in Computer Science, pages 335-345. Springer-Verlag, 2002. we find as solution for a unified addition/doubling formula: lambda = ((x1 + x2)^2 - x1 * x2 + a) / (y1 + y2), with a = 0 for secp256k1's curve equation. x3 = lambda^2 - (x1 + x2) 2*y3 = lambda * (x1 + x2 - 2 * x3) - (y1 + y2).
Substituting x_i = Xi / Zi^2 and yi = Yi / Zi^3, for i=1,2,3, gives: U1 = X1*Z2^2, U2 = X2*Z1^2 S1 = Y1*Z2^3, S2 = Y2*Z1^3 Z = Z1*Z2 T = U1+U2 M = S1+S2 Q = T*M^2 R = T^2-U1*U2 X3 = 4*(R^2-Q) Y3 = 4*(R*(3*Q-2*R^2)-M^4) Z3 = 2*M*Z (Note that the paper uses xi = Xi / Zi and yi = Yi / Zi instead.)
This formula has the benefit of being the same for both addition of distinct points and doubling. However, it breaks down in the case that either point is infinity, or that y1 = -y2. We handle these cases in the following ways:
- If b is infinity we simply bail by means of a VERIFY_CHECK.
- If a is infinity, we detect this, and at the end of the computation replace the result (which will be meaningless, but we compute to be constant-time) with b.x : b.y : 1.
- If a = -b, we have y1 = -y2, which is a degenerate case. But here the answer is infinity, so we simply set the infinity flag of the result, overriding the computed values without even needing to cmov.
- If y1 = -y2 but x1 != x2, which does occur thanks to certain properties of our curve (specifically, 1 has nontrivial cube roots in our field, and the curve equation has no x coefficient) then the answer is not infinity but also not given by the above equation. In this case, we cmov in place an alternate expression for lambda. Specifically (y1 - y2)/(x1 - x2). Where both these expressions for lambda are defined, they are equal, and can be obtained from each other by multiplication by (y1 + y2)/(y1 + y2) then substitution of x^3 + 7 for y^2 (using the curve equation). For all pairs of nonzero points (a, b) at least one is defined, so this covers everything.
If lambda = R/M = 0/0 we have a problem (except in the "trivial" case that Z = z1z2 = 0, and this is special-cased later on).
In case a->infinity == 1, replace r with (b->x, b->y, 1).
Definition at line 493 of file group_impl.h.
1.9.4