Advertisement
Guest User

Untitled

a guest
Sep 21st, 2019
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.55 KB | None | 0 0
  1. /** In:
  2. * Eric Brier and Marc Joye, Weierstrass Elliptic Curves and Side-Channel Attacks.
  3. * In D. Naccache and P. Paillier, Eds., Public Key Cryptography, vol. 2274 of Lecture Notes in Computer Science, pages 335-345. Springer-Verlag, 2002.
  4. * we find as solution for a unified addition/doubling formula:
  5. * lambda = ((x1 + x2)^2 - x1 * x2 + a) / (y1 + y2), with a = 0 for secp256k1's curve equation.
  6. * x3 = lambda^2 - (x1 + x2)
  7. * 2*y3 = lambda * (x1 + x2 - 2 * x3) - (y1 + y2).
  8. *
  9. * Substituting x_i = Xi / Zi^2 and yi = Yi / Zi^3, for i=1,2,3, gives:
  10. * U1 = X1*Z2^2, U2 = X2*Z1^2
  11. * S1 = Y1*Z2^3, S2 = Y2*Z1^3
  12. * Z = Z1*Z2
  13. * T = U1+U2
  14. * M = S1+S2
  15. * Q = T*M^2
  16. * R = T^2-U1*U2
  17. * X3 = 4*(R^2-Q)
  18. * Y3 = 4*(R*(3*Q-2*R^2)-M^4)
  19. * Z3 = 2*M*Z
  20. * (Note that the paper uses xi = Xi / Zi and yi = Yi / Zi instead.)
  21. *
  22. * This formula has the benefit of being the same for both addition
  23. * of distinct points and doubling. However, it breaks down in the
  24. * case that either point is infinity, or that y1 = -y2. We handle
  25. * these cases in the following ways:
  26. *
  27. * - If b is infinity we simply bail by means of a VERIFY_CHECK.
  28. *
  29. * - If a is infinity, we detect this, and at the end of the
  30. * computation replace the result (which will be meaningless,
  31. * but we compute to be constant-time) with b.x : b.y : 1.
  32. *
  33. * - If a = -b, we have y1 = -y2, which is a degenerate case.
  34. * But here the answer is infinity, so we simply set the
  35. * infinity flag of the result, overriding the computed values
  36. * without even needing to cmov.
  37. *
  38. * - If y1 = -y2 but x1 != x2, which does occur thanks to certain
  39. * properties of our curve (specifically, 1 has nontrivial cube
  40. * roots in our field, and the curve equation has no x coefficient)
  41. * then the answer is not infinity but also not given by the above
  42. * equation. In this case, we cmov in place an alternate expression
  43. * for lambda. Specifically (y1 - y2)/(x1 - x2). Where both these
  44. * expressions for lambda are defined, they are equal, and can be
  45. * obtained from each other by multiplication by (y1 + y2)/(y1 + y2)
  46. * then substitution of x^3 + 7 for y^2 (using the curve equation).
  47. * For all pairs of nonzero points (a, b) at least one is defined,
  48. * so this covers everything.
  49. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement