linefunction.c 5.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184
  1. /*
  2. * File: dclxvi-20130329/linefunction.c
  3. * Author: Ruben Niederhagen, Peter Schwabe
  4. * Public Domain
  5. */
  6. //AVANT
  7. //#include "fp2e.h"
  8. //#include "curvepoint_fp.h"
  9. //#include "twistpoint_fp2.h"
  10. //APRES
  11. #include "mul.h"
  12. extern "C" {
  13. #include "fpe.h"
  14. #include "fp2e.h"
  15. }
  16. #include "curvepoint_fp.h"
  17. #include "twistpoint_fp2.h"
  18. #ifdef N_OPS
  19. unsigned long long linefunction_addctr;
  20. unsigned long long linefunction_doublectr;
  21. #endif
  22. void linefunction_add_ate(
  23. fp2e_t rop11,
  24. fp2e_t rop12,
  25. fp2e_t rop13,
  26. twistpoint_fp2_t rop2,
  27. const twistpoint_fp2_t op1,
  28. const twistpoint_fp2_t op2,
  29. const curvepoint_fp_t op3,
  30. const fp2e_t r2 // r2 = y^2, see "Faster Computation of Tate Pairings"
  31. )
  32. {
  33. #ifdef N_OPS
  34. linefunction_addctr++;
  35. #endif
  36. fp2e_t tmp0, tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7, tmp8, tmp9, tmp10; // Temporary variables needed for intermediary results
  37. fp2e_mul(tmp0, op2->m_x, op1->m_t); /* tmp0 = B = x2 * T1 = x2z1^2*/
  38. fp2e_add(tmp1, op2->m_y, op1->m_z);
  39. //fp2e_short_coeffred(tmp1);
  40. fp2e_square(tmp1, tmp1);
  41. fp2e_sub2(tmp1, r2);
  42. fp2e_sub2(tmp1, op1->m_t);
  43. //fp2e_short_coeffred(tmp1);
  44. fp2e_mul(tmp1, tmp1, op1->m_t); /* tmp1 = D = ((y2 + Z1)^2 - R2 - T1)T1 = 2y2z1^3 */
  45. fp2e_sub(tmp2, tmp0, op1->m_x); /* tmp2 = H = B - X1 = x2z1^2 - x1*/
  46. //fp2e_short_coeffred(tmp2);
  47. fp2e_square(tmp3, tmp2); /* tmp3 = I = H^2 = (x2z1^2 - x1)^2*/
  48. fp2e_double(tmp4, tmp3);
  49. fp2e_double2(tmp4); /* tmp4 = E = 4I = 4(x2z1^2 - x1)^2*/
  50. fp2e_short_coeffred(tmp4);
  51. fp2e_mul(tmp5, tmp2, tmp4); /* tmp5 = J = HE = 4(x2z1^2 - x1)(x2z1^2 - x1)^2*/
  52. fp2e_sub(tmp6, tmp1, op1->m_y);
  53. fp2e_sub2(tmp6, op1->m_y); /* tmp6 = r = 2(D - 2Y1) = (2y2z1^3 - 2y1)*/
  54. fp2e_short_coeffred(tmp6);
  55. fp2e_mul(tmp9, tmp6, op2->m_x); /* Needed later: tmp9 = x2(2y2z1^3 - 2y1)*/
  56. fp2e_mul(tmp7, op1->m_x, tmp4); /* tmp7 = V = X1*E = 4x1(x2z1^2 - x1)^2*/
  57. fp2e_square(rop2->m_x, tmp6);
  58. fp2e_sub2(rop2->m_x, tmp5);
  59. fp2e_sub2(rop2->m_x, tmp7);
  60. fp2e_sub2(rop2->m_x, tmp7); /* X3 = r^2 - J - 2V = (2y2z1^3 - 2y1)^2 - 4(x2z1^2 - x1)(x2z1^2 - x1)^2 - 8x1(x2z1^2 - x1)^2*/
  61. fp2e_short_coeffred(rop2->m_x);
  62. fp2e_add(rop2->m_z, op1->m_z, tmp2);
  63. fp2e_short_coeffred(rop2->m_z);
  64. fp2e_square(rop2->m_z, rop2->m_z);
  65. fp2e_sub2(rop2->m_z, op1->m_t);
  66. fp2e_sub2(rop2->m_z, tmp3); /* Z3 = (z1 + H)^2 - T1 - I = 2z1(x2z1^2 - x1) */
  67. fp2e_short_coeffred(rop2->m_z);
  68. fp2e_add(tmp10, op2->m_y, rop2->m_z); /* Needed later: tmp10 = y2 + z3*/
  69. //fp2e_short_coeffred(tmp10);
  70. fp2e_sub(tmp8, tmp7, rop2->m_x);
  71. //fp2e_short_coeffred(tmp8);
  72. fp2e_mul(tmp8, tmp8, tmp6);
  73. fp2e_mul(tmp0, op1->m_y, tmp5);
  74. fp2e_double2(tmp0);
  75. fp2e_sub(rop2->m_y, tmp8, tmp0); /* Y3 = r(V - X3) - 2Y1*J = (2y2z1^3 - 2y1)(4x1(x2z1^2 - x1)^2 - x3) - 8y1(x2z1^2 - x1)(x2z1^2 - x1)^2*/
  76. fp2e_short_coeffred(rop2->m_y);
  77. fp2e_square(rop2->m_t, rop2->m_z); /* T3 = Z3^2 */
  78. fp2e_square(tmp10, tmp10); /* tmp10 = (y2 + z3)^2 */
  79. fp2e_sub2(tmp10, r2);
  80. fp2e_sub2(tmp10, rop2->m_t);
  81. //fp2e_short_coeffred(tmp10);
  82. fp2e_double2(tmp9);
  83. fp2e_sub(rop11, tmp9, tmp10); /* tmp9 = 4x2(y2z1^3 - y1) - 2z3y2 */
  84. fp2e_short_coeffred(rop11);
  85. fp2e_mul_fpe(tmp10, rop2->m_z, op3->m_y); /* tmp10 = z3y_Q */
  86. fp2e_double(rop13, tmp10);
  87. //fp2e_short_coeffred(rop13);
  88. fp2e_neg(tmp6, tmp6);
  89. fp2e_mul_fpe(tmp1, tmp6, op3->m_x);
  90. fp2e_double(rop12, tmp1);
  91. fp2e_short_coeffred(rop12);
  92. }
  93. void linefunction_double_ate(fp2e_t rop11, fp2e_t rop12, fp2e_t rop13, twistpoint_fp2_t rop2, const twistpoint_fp2_t op1, const curvepoint_fp_t op3)
  94. {
  95. #ifdef N_OPS
  96. linefunction_doublectr++;
  97. #endif
  98. fp2e_t tmp0, tmp1, tmp2, tmp3, tmp4, tmp5, tmp7, dummy; // Temporary variables needed for intermediary results
  99. fp2e_square(tmp0, op1->m_x); /* tmp0 = A = X1^2 = x1^2 */
  100. fp2e_square(tmp1, op1->m_y); /* tmp1 = B = Y1^2 = y1^2 */
  101. fp2e_square(tmp2, tmp1); /* tmp2 = C = B^2 = y1^4 */
  102. fp2e_add(tmp3, op1->m_x, tmp1);
  103. //fp2e_short_coeffred(tmp3);
  104. fp2e_square(tmp3, tmp3);
  105. fp2e_sub2(tmp3, tmp0);
  106. fp2e_sub2(tmp3, tmp2);
  107. fp2e_double2(tmp3); /* tmp3 = D = 2(X1 + B)^2 - A - C) = 4x1y1^2 */
  108. fp2e_triple(tmp4, tmp0); /* tmp4 = E = 3A = 3x1^2 */
  109. fp2e_short_coeffred(tmp4);
  110. fp2e_add(tmp7, tmp4, op1->m_x); /* Needed later */
  111. //fp2e_short_coeffred(tmp7);
  112. fp2e_square(tmp5, tmp4); /* tmp5 = G = E^2 = 9x1^4 */
  113. fp2e_sub(rop2->m_x, tmp5, tmp3);
  114. fp2e_sub2(rop2->m_x, tmp3); /* X3 = G - 2D = 9x1^4 - 8x1y1^2 */
  115. fp2e_short_coeffred(rop2->m_x);
  116. fp2e_add(rop2->m_z, op1->m_y, op1->m_z);
  117. //fp2e_short_coeffred(rop2->m_z);
  118. fp2e_square(rop2->m_z, rop2->m_z);
  119. fp2e_sub2(rop2->m_z, tmp1);
  120. fp2e_sub2(rop2->m_z, op1->m_t); /* Z3 = (Y1 + Z1)^2 - B - T1 = 2y1z1; */
  121. fp2e_short_coeffred(rop2->m_z);
  122. fp2e_sub(rop2->m_y, tmp3, rop2->m_x);
  123. fp2e_short_coeffred(rop2->m_y);
  124. fp2e_mul(rop2->m_y, rop2->m_y, tmp4);
  125. fp2e_double(dummy, tmp2);
  126. fp2e_double2(dummy);
  127. fp2e_double2(dummy);
  128. fp2e_sub2(rop2->m_y, dummy); /* Y3 = E(D - X3) - 8C = 3x1^2(4x1y1^2 - X3) - 8y1^4 */
  129. fp2e_short_coeffred(rop2->m_y);
  130. fp2e_mul(tmp3, tmp4, op1->m_t);
  131. fp2e_double2(tmp3);
  132. fp2e_neg(tmp3, tmp3);
  133. fp2e_mul_fpe(rop12, tmp3, op3->m_x); /* tmp3 = -6x1^2z1^2 * x_Q */
  134. fp2e_square(tmp7, tmp7);
  135. fp2e_sub2(tmp7, tmp0);
  136. fp2e_sub2(tmp7, tmp5);
  137. fp2e_double(dummy, tmp1);
  138. fp2e_double2(dummy);
  139. fp2e_sub(rop11, tmp7, dummy); /* tmp7 = 6x1^3 - 4y1^2 */
  140. fp2e_short_coeffred(rop11);
  141. fp2e_mul(tmp0, rop2->m_z, op1->m_t);
  142. fp2e_double2(tmp0);
  143. fp2e_mul_fpe(rop13, tmp0, op3->m_y);
  144. fp2e_square(rop2->m_t, rop2->m_z);
  145. }