twistpoint_fp2.c 9.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375
  1. /*
  2. * File: dclxvi-20130329/twistpoint_fp2.c
  3. * Author: Ruben Niederhagen, Peter Schwabe
  4. * Public Domain
  5. */
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include "fpe.h"
  9. #include "twistpoint_fp2.h"
  10. //////////////////////////////////////////////////////////////////////////////////////////////////////////
  11. // Point initialization and deletion functions
  12. //////////////////////////////////////////////////////////////////////////////////////////////////////////
  13. // Global dummies usable by all curvepoints:
  14. // Set the coordinates of a twistpoint_fp2_t by copying the coordinates from another twistpoint_fp2
  15. void twistpoint_fp2_set(twistpoint_fp2_t rop, const twistpoint_fp2_t op)
  16. {
  17. fp2e_set(rop->m_x, op->m_x);
  18. fp2e_set(rop->m_y, op->m_y);
  19. fp2e_set(rop->m_z, op->m_z);
  20. fp2e_setzero(rop->m_t);
  21. }
  22. void twistpoint_fp2_setneutral(twistpoint_fp2_t rop)
  23. {
  24. fp2e_setone(rop->m_x);
  25. fp2e_setone(rop->m_y);
  26. fp2e_setzero(rop->m_z);
  27. fp2e_setzero(rop->m_t);
  28. }
  29. // Addition of two points, op2 is assumed to be in affine coordinates
  30. // For the algorithm see e.g. DA Peter Schwabe
  31. /*
  32. void twistpoint_fp2_mixadd(twistpoint_fp2_t rop, const twistpoint_fp2_t op1, const twistpoint_fp2_t op2)
  33. {
  34. fp2e_t tfpe1, tfpe2, tfpe3, tfpe4, tfpe5, tfpe6, tfpe7, tfpe8, tfpe9; // Temporary variables needed for intermediary results
  35. fp2e_square(tfpe1, op1->m_z);
  36. fp2e_mul(tfpe2, op1->m_z, tfpe1);
  37. fp2e_mul(tfpe3, op2->m_x, tfpe1);
  38. fp2e_mul(tfpe4, op2->m_y, tfpe2);
  39. fp2e_sub(tfpe5, tfpe3, op1->m_x);
  40. fp2e_short_coeffred(tfpe5);
  41. fp2e_sub(tfpe6, tfpe4, op1->m_y);
  42. fp2e_square(tfpe7, tfpe5);
  43. fp2e_mul(tfpe8, tfpe7, tfpe5);
  44. fp2e_mul(tfpe9, op1->m_x, tfpe7);
  45. fp2e_double(tfpe1, tfpe9);
  46. fp2e_add(tfpe1, tfpe1, tfpe8);
  47. fp2e_square(rop->m_x, tfpe6);
  48. fp2e_sub(rop->m_x, rop->m_x, tfpe1);
  49. fp2e_short_coeffred(rop->m_x);
  50. fp2e_sub(tfpe1, tfpe9, rop->m_x);
  51. fp2e_mul(tfpe2, tfpe1, tfpe6);
  52. fp2e_mul(tfpe3, op1->m_y, tfpe8);
  53. fp2e_sub(rop->m_y, tfpe2, tfpe3);
  54. fp2e_short_coeffred(rop->m_y);
  55. fp2e_mul(rop->m_z, op1->m_z, tfpe5);
  56. }
  57. */
  58. void twistpoint_fp2_double(twistpoint_fp2_t rop, const twistpoint_fp2_t op)
  59. {
  60. fp2e_t tfpe1, tfpe2, tfpe3, tfpe4; // Temporary variables needed for intermediary results
  61. fp2e_square(tfpe1, op->m_y);
  62. fp2e_mul(tfpe2, tfpe1, op->m_x);
  63. fp2e_double(tfpe2, tfpe2);
  64. fp2e_double(tfpe2, tfpe2);
  65. fp2e_square(tfpe3, tfpe1);
  66. fp2e_double(tfpe3, tfpe3);
  67. fp2e_double(tfpe3, tfpe3);
  68. fp2e_double(tfpe3, tfpe3);
  69. fp2e_square(tfpe4, op->m_x);
  70. fp2e_triple(tfpe4, tfpe4);
  71. fp2e_short_coeffred(tfpe4);
  72. fp2e_square(rop->m_x, tfpe4);
  73. fp2e_double(tfpe1, tfpe2);
  74. fp2e_sub(rop->m_x, rop->m_x, tfpe1);
  75. fp2e_short_coeffred(rop->m_x);
  76. fp2e_sub(tfpe1, tfpe2, rop->m_x);
  77. fp2e_short_coeffred(tfpe1);
  78. fp2e_mul(rop->m_z, op->m_y, op->m_z);
  79. fp2e_double(rop->m_z, rop->m_z);
  80. fp2e_mul(rop->m_y, tfpe4, tfpe1);
  81. fp2e_sub(rop->m_y, rop->m_y, tfpe3);
  82. fp2e_short_coeffred(rop->m_y);
  83. }
  84. void twistpoint_fp2_add_vartime(twistpoint_fp2_t rop, const twistpoint_fp2_t op1, const twistpoint_fp2_t op2)
  85. {
  86. if(fp2e_iszero(op1->m_z))
  87. twistpoint_fp2_set(rop,op2);
  88. else if(fp2e_iszero(op2->m_z))
  89. twistpoint_fp2_set(rop,op1);
  90. else
  91. {
  92. //See http://www.hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/addition/add-2007-bl.op3
  93. fp2e_t z1z1, z2z2, r, v, s1, s2, u1, u2, h, i, j, t0,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11,t12,t13,t14;
  94. //Z1Z1 = Z1^2
  95. fp2e_square(z1z1, op1->m_z);
  96. //Z2Z2 = Z2^2
  97. fp2e_square(z2z2, op2->m_z);
  98. //U1 = X1*Z2Z2
  99. fp2e_mul(u1, op1->m_x, z2z2);
  100. //U2 = X2*Z1Z1
  101. fp2e_mul(u2, op2->m_x, z1z1);
  102. //t0 = Z2*Z2Z2
  103. fp2e_mul(t0, op2->m_z, z2z2);
  104. //S1 = Y1*t0
  105. fp2e_mul(s1,op1->m_y,t0);
  106. //t1 = Z1*Z1Z1
  107. fp2e_mul(t1,op1->m_z, z1z1);
  108. //S2 = Y2*t1
  109. fp2e_mul(s2,op2->m_y,t1);
  110. if(fp2e_iseq(u1,u2))
  111. {
  112. if(fp2e_iseq(s1,s2))
  113. twistpoint_fp2_double(rop,op1);
  114. else
  115. twistpoint_fp2_setneutral(rop);
  116. }
  117. //H = U2-U1
  118. fp2e_sub(h,u2,u1);
  119. //t2 = 2*H
  120. fp2e_add(t2, h, h);
  121. //I = t2^2
  122. fp2e_short_coeffred(t2);
  123. fp2e_square(i,t2);
  124. //J = H*I
  125. fp2e_mul(j,h,i);
  126. //t3 = S2-S1
  127. fp2e_sub(t3,s2,s1);
  128. //r = 2*t3
  129. fp2e_add(r,t3,t3);
  130. //V = U1*I
  131. fp2e_mul(v,u1,i);
  132. //t4 = r^2
  133. fp2e_short_coeffred(r);
  134. fp2e_square(t4,r);
  135. //t5 = 2*V
  136. fp2e_add(t5,v,v);
  137. //t6 = t4-J
  138. fp2e_sub(t6,t4,j);
  139. //X3 = t6-t5
  140. fp2e_sub(rop->m_x,t6,t5);
  141. fp2e_short_coeffred(rop->m_x);
  142. //t7 = V-X3
  143. fp2e_sub(t7,v,rop->m_x);
  144. //t8 = S1*J
  145. fp2e_mul(t8,s1,j);
  146. //t9 = 2*t8
  147. fp2e_add(t9,t8,t8);
  148. //t10 = r*t7
  149. fp2e_mul(t10,r,t7);
  150. //Y3 = t10-t9
  151. fp2e_sub(rop->m_y,t10,t9);
  152. fp2e_short_coeffred(rop->m_y);
  153. //t11 = Z1+Z2
  154. fp2e_add(t11,op1->m_z,op2->m_z);
  155. //t12 = t11^2
  156. fp2e_short_coeffred(t11);
  157. fp2e_square(t12,t11);
  158. //t13 = t12-Z1Z1
  159. fp2e_sub(t13,t12,z1z1);
  160. //t14 = t13-Z2Z2
  161. fp2e_sub(t14,t13,z2z2);
  162. //Z3 = t14*H
  163. fp2e_short_coeffred(t14);
  164. fp2e_mul(rop->m_z,t14,h);
  165. fp2e_short_coeffred(rop->m_z);
  166. }
  167. }
  168. static void twistpoint_fp2_add_nocheck(twistpoint_fp2_t rop, const twistpoint_fp2_t op1, const twistpoint_fp2_t op2)
  169. {
  170. //See http://www.hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/addition/add-2007-bl.op3
  171. fp2e_t z1z1, z2z2, r, v, s1, s2, u1, u2, h, i, j, t0,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11,t12,t13,t14;
  172. //Z1Z1 = Z1^2
  173. fp2e_square(z1z1, op1->m_z);
  174. //Z2Z2 = Z2^2
  175. fp2e_square(z2z2, op2->m_z);
  176. //U1 = X1*Z2Z2
  177. fp2e_mul(u1, op1->m_x, z2z2);
  178. //U2 = X2*Z1Z1
  179. fp2e_mul(u2, op2->m_x, z1z1);
  180. //t0 = Z2*Z2Z2
  181. fp2e_mul(t0, op2->m_z, z2z2);
  182. //S1 = Y1*t0
  183. fp2e_mul(s1,op1->m_y,t0);
  184. //t1 = Z1*Z1Z1
  185. fp2e_mul(t1,op1->m_z, z1z1);
  186. //S2 = Y2*t1
  187. fp2e_mul(s2,op2->m_y,t1);
  188. //H = U2-U1
  189. fp2e_sub(h,u2,u1);
  190. //t2 = 2*H
  191. fp2e_add(t2, h, h);
  192. //I = t2^2
  193. fp2e_short_coeffred(t2);
  194. fp2e_square(i,t2);
  195. //J = H*I
  196. fp2e_mul(j,h,i);
  197. //t3 = S2-S1
  198. fp2e_sub(t3,s2,s1);
  199. //r = 2*t3
  200. fp2e_add(r,t3,t3);
  201. //V = U1*I
  202. fp2e_mul(v,u1,i);
  203. //t4 = r^2
  204. fp2e_short_coeffred(r);
  205. fp2e_square(t4,r);
  206. //t5 = 2*V
  207. fp2e_add(t5,v,v);
  208. //t6 = t4-J
  209. fp2e_sub(t6,t4,j);
  210. //X3 = t6-t5
  211. fp2e_sub(rop->m_x,t6,t5);
  212. fp2e_short_coeffred(rop->m_x);
  213. //t7 = V-X3
  214. fp2e_sub(t7,v,rop->m_x);
  215. //t8 = S1*J
  216. fp2e_mul(t8,s1,j);
  217. //t9 = 2*t8
  218. fp2e_add(t9,t8,t8);
  219. //t10 = r*t7
  220. fp2e_mul(t10,r,t7);
  221. //Y3 = t10-t9
  222. fp2e_sub(rop->m_y,t10,t9);
  223. fp2e_short_coeffred(rop->m_y);
  224. //t11 = Z1+Z2
  225. fp2e_add(t11,op1->m_z,op2->m_z);
  226. //t12 = t11^2
  227. fp2e_short_coeffred(t11);
  228. fp2e_square(t12,t11);
  229. //t13 = t12-Z1Z1
  230. fp2e_sub(t13,t12,z1z1);
  231. //t14 = t13-Z2Z2
  232. fp2e_sub(t14,t13,z2z2);
  233. //Z3 = t14*H
  234. fp2e_short_coeffred(h);
  235. fp2e_mul(rop->m_z,t14,h);
  236. fp2e_short_coeffred(rop->m_z);
  237. }
  238. /*
  239. void twistpoint_fp2_scalarmult_vartime_old(twistpoint_fp2_t rop, const twistpoint_fp2_t op, const scalar_t scalar, const unsigned int scalar_bitsize)
  240. {
  241. size_t i;
  242. twistpoint_fp2_t r;
  243. twistpoint_fp2_set(r, op);
  244. for(i = scalar_bitsize-1; i > 0; i--)
  245. {
  246. twistpoint_fp2_double(r, r);
  247. if(scalar_getbit(scalar, i - 1))
  248. twistpoint_fp2_mixadd(r, r, op);
  249. }
  250. twistpoint_fp2_set(rop, r);
  251. }
  252. */
  253. static void choose_t(twistpoint_fp2_t t, struct twistpoint_fp2_struct *pre, signed char b)
  254. {
  255. if(b>0)
  256. *t = pre[b-1];
  257. else
  258. {
  259. *t = pre[-b-1];
  260. twistpoint_fp2_neg(t,t);
  261. }
  262. }
  263. void twistpoint_fp2_scalarmult_vartime(twistpoint_fp2_t rop, const twistpoint_fp2_t op, const scalar_t scalar)
  264. {
  265. signed char s[65];
  266. int i;
  267. twistpoint_fp2_t t;
  268. struct twistpoint_fp2_struct pre[8];
  269. scalar_window4(s,scalar);
  270. /*
  271. for(i=0;i<64;i++)
  272. printf("%d ",s[i]);
  273. printf("\n");
  274. */
  275. pre[0] = *op; // P
  276. twistpoint_fp2_double(&pre[1], &pre[0]); // 2P
  277. twistpoint_fp2_add_nocheck(&pre[2], &pre[0], &pre[1]); // 3P
  278. twistpoint_fp2_double(&pre[3], &pre[1]); // 4P
  279. twistpoint_fp2_add_nocheck(&pre[4], &pre[0], &pre[3]); // 5P
  280. twistpoint_fp2_double(&pre[5], &pre[2]); // 6P
  281. twistpoint_fp2_add_nocheck(&pre[6], &pre[0], &pre[5]); // 7P
  282. twistpoint_fp2_double(&pre[7], &pre[3]); // 8P
  283. i = 64;
  284. while(!s[i]&&i>0) i--;
  285. if(!s[i])
  286. twistpoint_fp2_setneutral(rop);
  287. else
  288. {
  289. choose_t(rop,pre,s[i]);
  290. i--;
  291. for(;i>=0;i--)
  292. {
  293. twistpoint_fp2_double(rop, rop);
  294. twistpoint_fp2_double(rop, rop);
  295. twistpoint_fp2_double(rop, rop);
  296. twistpoint_fp2_double(rop, rop);
  297. if(s[i])
  298. {
  299. choose_t(t,pre,s[i]);
  300. twistpoint_fp2_add_nocheck(rop,rop,t);
  301. }
  302. }
  303. }
  304. }
  305. // Negate a point, store in rop:
  306. void twistpoint_fp2_neg(twistpoint_fp2_t rop, const twistpoint_fp2_t op)
  307. {
  308. fp2e_t tfpe1;
  309. fp2e_neg(tfpe1, op->m_y);
  310. fp2e_set(rop->m_x, op->m_x);
  311. fp2e_set(rop->m_y, tfpe1);
  312. fp2e_set(rop->m_z, op->m_z);
  313. }
  314. void twistpoint_fp2_set_fp2e(twistpoint_fp2_t rop, const fp2e_t x, const fp2e_t y, const fp2e_t z)
  315. {
  316. fp2e_set(rop->m_x, x);
  317. fp2e_set(rop->m_y, y);
  318. fp2e_set(rop->m_z, z);
  319. fp2e_setzero(rop->m_t);
  320. }
  321. void twistpoint_fp2_affineset_fp2e(twistpoint_fp2_t rop, const fp2e_t x, const fp2e_t y)
  322. {
  323. fp2e_set(rop->m_x, x);
  324. fp2e_set(rop->m_y, y);
  325. fp2e_setone(rop->m_z);
  326. fp2e_setzero(rop->m_t);
  327. }
  328. // Transform to Affine Coordinates (z=1)
  329. void twistpoint_fp2_makeaffine(twistpoint_fp2_t point)
  330. {
  331. fp2e_t tfpe1;
  332. fp2e_invert(tfpe1, point->m_z);
  333. fp2e_mul(point->m_x, point->m_x, tfpe1);
  334. fp2e_mul(point->m_x, point->m_x, tfpe1);
  335. fp2e_mul(point->m_y, point->m_y, tfpe1);
  336. fp2e_mul(point->m_y, point->m_y, tfpe1);
  337. fp2e_mul(point->m_y, point->m_y, tfpe1);
  338. fp2e_setone(point->m_z);
  339. }
  340. // Print a point:
  341. void twistpoint_fp2_print(FILE *outfile, const twistpoint_fp2_t point)
  342. {
  343. fprintf(outfile, "[");
  344. fp2e_print(outfile, point->m_x);
  345. fprintf(outfile, ", ");
  346. fp2e_print(outfile, point->m_y);
  347. fprintf(outfile, ", ");
  348. fp2e_print(outfile, point->m_z);
  349. fprintf(outfile, "]");
  350. }