Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /** 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.
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement