fp12e.c 8.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332
  1. /*
  2. * File: dclxvi-20130329/fp12e.c
  3. * Author: Ruben Niederhagen, Peter Schwabe
  4. * Public Domain
  5. */
  6. #include <stdio.h>
  7. #include <assert.h>
  8. #include "fp6e.h"
  9. #include "fp12e.h"
  10. extern const fp2e_t bn_zpminus1;
  11. extern const fpe_t bn_zeta;
  12. // Set fp12e_t rop to given value:
  13. void fp12e_set(fp12e_t rop, const fp12e_t op)
  14. {
  15. fp6e_set(rop->m_a, op->m_a);
  16. fp6e_set(rop->m_b, op->m_b);
  17. }
  18. // Initialize an fp12e, set to value given in two fp6es
  19. void fp12e_set_fp6e(fp12e_t rop, const fp6e_t a, const fp6e_t b)
  20. {
  21. fp6e_set(rop->m_a, a);
  22. fp6e_set(rop->m_b, b);
  23. }
  24. // Set rop to one:
  25. void fp12e_setone(fp12e_t rop)
  26. {
  27. fp6e_setzero(rop->m_a);
  28. fp6e_setone(rop->m_b);
  29. }
  30. // Set rop to zero:
  31. void fp12e_setzero(fp12e_t rop)
  32. {
  33. fp6e_setzero(rop->m_a);
  34. fp6e_setzero(rop->m_b);
  35. }
  36. // Compare for equality:
  37. int fp12e_iseq(const fp12e_t op1, const fp12e_t op2)
  38. {
  39. int ret = fp6e_iseq(op1->m_a, op2->m_a);
  40. ret = ret && fp6e_iseq(op1->m_b, op2->m_b);
  41. return ret;
  42. }
  43. int fp12e_isone(const fp12e_t op)
  44. {
  45. int ret = fp6e_iszero(op->m_a);
  46. ret = ret && fp6e_isone(op->m_b);
  47. return ret;
  48. }
  49. int fp12e_iszero(const fp12e_t op)
  50. {
  51. int ret = fp6e_iszero(op->m_a);
  52. ret = ret && fp6e_iszero(op->m_b);
  53. return ret;
  54. }
  55. void fp12e_cmov(fp12e_t rop, const fp12e_t op, int c)
  56. {
  57. fp6e_cmov(rop->m_a, op->m_a, c);
  58. fp6e_cmov(rop->m_b, op->m_b, c);
  59. }
  60. // Compute conjugate over Fp6:
  61. void fp12e_conjugate(fp12e_t rop, const fp12e_t op2)
  62. {
  63. fp6e_neg(rop->m_a, op2->m_a);
  64. fp6e_set(rop->m_b, op2->m_b);
  65. }
  66. // Add two fp12e, store result in rop:
  67. void fp12e_add(fp12e_t rop, const fp12e_t op1, const fp12e_t op2)
  68. {
  69. fp6e_add(rop->m_a, op1->m_a, op2->m_a);
  70. fp6e_add(rop->m_b, op1->m_b, op2->m_b);
  71. }
  72. // Subtract op2 from op1, store result in rop:
  73. void fp12e_sub(fp12e_t rop, const fp12e_t op1, const fp12e_t op2)
  74. {
  75. fp6e_sub(rop->m_a, op1->m_a, op2->m_a);
  76. fp6e_sub(rop->m_b, op1->m_b, op2->m_b);
  77. }
  78. // Multiply two fp12e, store result in rop:
  79. void fp12e_mul(fp12e_t rop, const fp12e_t op1, const fp12e_t op2)
  80. {
  81. #ifdef BENCH
  82. nummultp12 ++;
  83. multp12cycles -= cpucycles();
  84. #endif
  85. fp6e_t tmp1, tmp2, tmp3; // Needed to store intermediary results
  86. fp6e_mul(tmp1, op1->m_a, op2->m_a);
  87. fp6e_mul(tmp3, op1->m_b, op2->m_b);
  88. fp6e_add(tmp2, op2->m_a, op2->m_b);
  89. fp6e_short_coeffred(tmp2);
  90. fp6e_add(rop->m_a, op1->m_a, op1->m_b);
  91. fp6e_short_coeffred(rop->m_a);
  92. fp6e_set(rop->m_b, tmp3);
  93. fp6e_mul(rop->m_a, rop->m_a, tmp2);
  94. fp6e_sub(rop->m_a, rop->m_a, tmp1);
  95. fp6e_sub(rop->m_a, rop->m_a, rop->m_b);
  96. fp6e_short_coeffred(rop->m_a);
  97. fp6e_multau(tmp1, tmp1);
  98. fp6e_add(rop->m_b, rop->m_b, tmp1);
  99. fp6e_short_coeffred(rop->m_b);
  100. #ifdef BENCH
  101. multp12cycles += cpucycles();
  102. #endif
  103. }
  104. void fp12e_mul_fp6e(fp12e_t rop, const fp12e_t op1, const fp6e_t op2)
  105. {
  106. fp6e_mul(rop->m_a, op1->m_a, op2);
  107. fp6e_mul(rop->m_b, op1->m_b, op2);
  108. }
  109. // Square an fp12e, store result in rop:
  110. void fp12e_square(fp12e_t rop, const fp12e_t op)
  111. {
  112. #ifdef BENCH
  113. numsqp12 ++;
  114. sqp12cycles -= cpucycles();
  115. #endif
  116. fp6e_t tmp1, tmp2, tmp3; // Needed to store intermediary results
  117. fp6e_mul(tmp1, op->m_a, op->m_b);
  118. fp6e_add(tmp2, op->m_a, op->m_b);
  119. fp6e_short_coeffred(tmp2);
  120. fp6e_multau(tmp3, op->m_a);
  121. fp6e_add(rop->m_b, tmp3, op->m_b);
  122. fp6e_short_coeffred(rop->m_b);
  123. fp6e_mul(rop->m_b, rop->m_b, tmp2);
  124. fp6e_sub(rop->m_b, rop->m_b, tmp1);
  125. fp6e_multau(tmp2, tmp1);
  126. fp6e_sub(rop->m_b, rop->m_b, tmp2);
  127. fp6e_short_coeffred(rop->m_b);
  128. fp6e_add(rop->m_a, tmp1, tmp1);
  129. fp6e_short_coeffred(rop->m_a);
  130. #ifdef BENCH
  131. sqp12cycles += cpucycles();
  132. #endif
  133. }
  134. // Multiply an fp12e by a line function value, store result in rop:
  135. // The line function is given by 3 fp2e elements op2, op3, op4 as
  136. // line = (op2*tau + op3)*z + op4 = a2*z + b2.
  137. void fp12e_mul_line(fp12e_t rop, const fp12e_t op1, const fp2e_t op2, const fp2e_t op3, const fp2e_t op4)
  138. {
  139. #ifdef BENCH
  140. nummultp12 ++;
  141. multp12cycles -= cpucycles();
  142. #endif
  143. fp2e_t fp2_0, tmp;
  144. fp6e_t tmp1, tmp2, tmp3; // Needed to store intermediary results
  145. fp2e_setzero(fp2_0); // fp2_0 = 0
  146. fp6e_set_fp2e(tmp1, fp2_0, op2, op3); // tmp1 = a2 = op2*tau + op3
  147. fp6e_mul_shortfp6e(tmp1, op1->m_a, tmp1); // tmp1 = a1*a2
  148. fp6e_mul_fp2e(tmp3, op1->m_b, op4); // tmp3 = b1*op4 = b1*b2
  149. fp2e_add(tmp, op3, op4);
  150. fp2e_short_coeffred(tmp);
  151. fp6e_set_fp2e(tmp2, fp2_0, op2, tmp); // tmp2 = a2 + b2
  152. fp6e_add(rop->m_a, op1->m_a, op1->m_b); // a3 = a1 + b1
  153. fp6e_short_coeffred(rop->m_a);
  154. fp6e_set(rop->m_b, tmp3); // b3 = b1*b2
  155. fp6e_mul_shortfp6e(rop->m_a, rop->m_a, tmp2);// a3 = (a1+b1)*(a2+b2)
  156. fp6e_sub(rop->m_a, rop->m_a, tmp1);
  157. fp6e_sub(rop->m_a, rop->m_a, rop->m_b); // a3 = a1*b2 + a2*b1
  158. fp6e_short_coeffred(rop->m_a);
  159. fp6e_multau(tmp1, tmp1); // tmp1 = a1*a2*tau
  160. fp6e_add(rop->m_b, rop->m_b, tmp1); // b3 = b1*b2 + a1*a2*tau
  161. fp6e_short_coeffred(rop->m_b);
  162. #ifdef BENCH
  163. multp12cycles += cpucycles();
  164. #endif
  165. }
  166. void fp12e_pow_vartime(fp12e_t rop, const fp12e_t op, const scalar_t exp)
  167. {
  168. fp12e_t dummy;
  169. unsigned int startbit;
  170. startbit = scalar_scanb(exp);
  171. fp12e_set(dummy, op);
  172. fp12e_set(rop,op);
  173. int i;
  174. for(i = startbit; i > 0; i--)
  175. {
  176. fp12e_square(rop, rop);
  177. if(scalar_getbit(exp, i - 1))
  178. fp12e_mul(rop, rop, dummy);
  179. }
  180. }
  181. // Implicit fp4 squaring for Granger/Scott special squaring in final expo
  182. // fp4e_square takes two fp2e op1, op2 representing the fp4 element
  183. // op1*z^3 + op2, writes the square to rop1, rop2 representing rop1*z^3 + rop2.
  184. // (op1*z^3 + op2)^2 = (2*op1*op2)*z^3 + (op1^2*xi + op2^2).
  185. void fp4e_square(fp2e_t rop1, fp2e_t rop2, const fp2e_t op1, const fp2e_t op2)
  186. {
  187. fp2e_t t1, t2;
  188. fp2e_square(t1, op1); // t1 = op1^2
  189. fp2e_square(t2, op2); // t2 = op2^2
  190. //fp2e_mul(rop1, op1, op2); // rop1 = op1*op2
  191. //fp2e_add(rop1, rop1, rop1); // rop1 = 2*op1*op2
  192. fp2e_add(rop1, op1, op2);
  193. fp2e_short_coeffred(rop1);
  194. fp2e_square(rop1, rop1);
  195. fp2e_sub2(rop1, t1);
  196. fp2e_sub2(rop1, t2); // rop1 = 2*op1*op2
  197. fp2e_mulxi(rop2, t1); // rop2 = op1^2*xi
  198. fp2e_add2(rop2, t2); // rop2 = op1^2*xi + op2^2
  199. }
  200. // Special squaring for use on elements in T_6(fp2) (after the
  201. // easy part of the final exponentiation. Used in the hard part
  202. // of the final exponentiation. Function uses formulas in
  203. // Granger/Scott (PKC2010).
  204. void fp12e_special_square_finexp(fp12e_t rop, const fp12e_t op)
  205. {
  206. fp2e_t f00, f01, f02, f10, f11, f12;
  207. fp2e_t t00, t01, t02, t10, t11, t12, t;
  208. fp6e_t f0, f1;
  209. fp4e_square(t11, t00, op->m_a->m_b, op->m_b->m_c);
  210. fp4e_square(t12, t01, op->m_b->m_a, op->m_a->m_c);
  211. fp4e_square(t02, t10, op->m_a->m_a, op->m_b->m_b);
  212. fp2e_mulxi(t, t02);
  213. fp2e_set(t02, t10);
  214. fp2e_set(t10, t);
  215. fp2e_mul_scalar(f00, op->m_b->m_c, -2);
  216. fp2e_mul_scalar(f01, op->m_b->m_b, -2);
  217. fp2e_mul_scalar(f02, op->m_b->m_a, -2);
  218. fp2e_double(f10, op->m_a->m_c);
  219. fp2e_double(f11, op->m_a->m_b);
  220. fp2e_double(f12, op->m_a->m_a);
  221. fp2e_triple2(t00);
  222. fp2e_triple2(t01);
  223. fp2e_triple2(t02);
  224. fp2e_triple2(t10);
  225. fp2e_triple2(t11);
  226. fp2e_triple2(t12);
  227. fp2e_add2(f00, t00);
  228. fp2e_add2(f01, t01);
  229. fp2e_add2(f02, t02);
  230. fp2e_add2(f10, t10);
  231. fp2e_add2(f11, t11);
  232. fp2e_add2(f12, t12);
  233. fp6e_set_fp2e(f0, f02, f01, f00);
  234. fp6e_short_coeffred(f0);
  235. fp6e_set_fp2e(f1, f12, f11, f10);
  236. fp6e_short_coeffred(f1);
  237. fp12e_set_fp6e(rop,f1,f0);
  238. }
  239. void fp12e_invert(fp12e_t rop, const fp12e_t op)
  240. {
  241. #ifdef BENCH
  242. numinvp12 ++;
  243. invp12cycles -= cpucycles();
  244. #endif
  245. fp6e_t tmp1, tmp2; // Needed to store intermediary results
  246. fp6e_squaredouble(tmp1, op->m_a);
  247. fp6e_squaredouble(tmp2, op->m_b);
  248. fp6e_multau(tmp1, tmp1);
  249. fp6e_sub(tmp1, tmp2, tmp1);
  250. fp6e_short_coeffred(tmp1);
  251. fp6e_invert(tmp1, tmp1);
  252. fp6e_add(tmp1,tmp1,tmp1);
  253. fp6e_short_coeffred(tmp1);
  254. fp12e_set(rop, op);
  255. fp6e_neg(rop->m_a, rop->m_a);
  256. fp12e_mul_fp6e(rop, rop, tmp1);
  257. #ifdef BENCH
  258. invp12cycles += cpucycles();
  259. #endif
  260. }
  261. void fp12e_frobenius_p(fp12e_t rop, const fp12e_t op)
  262. {
  263. fp6e_frobenius_p(rop->m_a, op->m_a);
  264. fp6e_frobenius_p(rop->m_b, op->m_b);
  265. fp6e_mul_fp2e(rop->m_a, rop->m_a, bn_zpminus1);
  266. }
  267. void fp12e_frobenius_p2(fp12e_t rop, const fp12e_t op)
  268. {
  269. fp6e_t t;
  270. fp6e_frobenius_p2(rop->m_a, op->m_a);
  271. fp6e_frobenius_p2(rop->m_b, op->m_b);
  272. fp6e_mul_fpe(t, rop->m_a, bn_zeta);
  273. fp6e_neg(rop->m_a, t);
  274. }
  275. // Print the element to stdout:
  276. void fp12e_print(FILE *outfile, const fp12e_t op)
  277. {
  278. fp6e_print(outfile, op->m_a);
  279. fprintf(outfile, " * Z + ");
  280. fp6e_print(outfile, op->m_b);
  281. }