curvepoint_fp.c 9.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355
  1. /*
  2. * File: dclxvi-20130329/curvepoint_fp.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 "curvepoint_fp.h"
  10. //////////////////////////////////////////////////////////////////////////////////////////////////////////
  11. // Point initialization and deletion functions
  12. //////////////////////////////////////////////////////////////////////////////////////////////////////////
  13. // Global dummies usable by all curvepoints:
  14. // Set the coordinates of a curvepoint_fp_t by copying the coordinates from another curvepoint_fp
  15. void curvepoint_fp_set(curvepoint_fp_t rop, const curvepoint_fp_t op)
  16. {
  17. fpe_set(rop->m_x, op->m_x);
  18. fpe_set(rop->m_y, op->m_y);
  19. fpe_set(rop->m_z, op->m_z);
  20. fpe_setzero(rop->m_t);
  21. }
  22. void curvepoint_fp_setneutral(curvepoint_fp_t rop)
  23. {
  24. fpe_setone(rop->m_x);
  25. fpe_setone(rop->m_y);
  26. fpe_setzero(rop->m_z);
  27. fpe_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 curvepoint_fp_mixadd(curvepoint_fp_t rop, const curvepoint_fp_t op1, const curvepoint_fp_t op2)
  33. {
  34. fpe_t tfpe1, tfpe2, tfpe3, tfpe4, tfpe5, tfpe6, tfpe7, tfpe8, tfpe9; // Temporary variables needed for intermediary results
  35. fpe_square(tfpe1, op1->m_z);
  36. fpe_mul(tfpe2, op1->m_z, tfpe1);
  37. fpe_mul(tfpe3, op2->m_x, tfpe1);
  38. fpe_mul(tfpe4, op2->m_y, tfpe2);
  39. fpe_sub(tfpe5, tfpe3, op1->m_x);
  40. fpe_short_coeffred(tfpe5);
  41. fpe_sub(tfpe6, tfpe4, op1->m_y);
  42. fpe_square(tfpe7, tfpe5);
  43. fpe_mul(tfpe8, tfpe7, tfpe5);
  44. fpe_mul(tfpe9, op1->m_x, tfpe7);
  45. fpe_double(tfpe1, tfpe9);
  46. fpe_add(tfpe1, tfpe1, tfpe8);
  47. fpe_square(rop->m_x, tfpe6);
  48. fpe_sub(rop->m_x, rop->m_x, tfpe1);
  49. fpe_short_coeffred(rop->m_x);
  50. fpe_sub(tfpe1, tfpe9, rop->m_x);
  51. fpe_mul(tfpe2, tfpe1, tfpe6);
  52. fpe_mul(tfpe3, op1->m_y, tfpe8);
  53. fpe_sub(rop->m_y, tfpe2, tfpe3);
  54. fpe_short_coeffred(rop->m_y);
  55. fpe_mul(rop->m_z, op1->m_z, tfpe5);
  56. }
  57. */
  58. void curvepoint_fp_double(curvepoint_fp_t rop, const curvepoint_fp_t op)
  59. {
  60. fpe_t tfpe1, tfpe2, tfpe3, tfpe4; // Temporary variables needed for intermediary results
  61. fpe_square(tfpe1, op->m_y);
  62. fpe_mul(tfpe2, tfpe1, op->m_x);
  63. fpe_double(tfpe2, tfpe2);
  64. fpe_double(tfpe2, tfpe2);
  65. fpe_square(tfpe3, tfpe1);
  66. fpe_double(tfpe3, tfpe3);
  67. fpe_double(tfpe3, tfpe3);
  68. fpe_double(tfpe3, tfpe3);
  69. fpe_square(tfpe4, op->m_x);
  70. fpe_triple(tfpe4, tfpe4);
  71. fpe_short_coeffred(tfpe4);
  72. fpe_square(rop->m_x, tfpe4);
  73. fpe_double(tfpe1, tfpe2);
  74. fpe_sub(rop->m_x, rop->m_x, tfpe1);
  75. fpe_short_coeffred(rop->m_x);
  76. fpe_sub(tfpe1, tfpe2, rop->m_x);
  77. fpe_short_coeffred(tfpe1);
  78. fpe_mul(rop->m_z, op->m_y, op->m_z);
  79. fpe_double(rop->m_z, rop->m_z);
  80. fpe_mul(rop->m_y, tfpe4, tfpe1);
  81. fpe_sub(rop->m_y, rop->m_y, tfpe3);
  82. fpe_short_coeffred(rop->m_y);
  83. }
  84. void curvepoint_fp_add_vartime(curvepoint_fp_t rop, const curvepoint_fp_t op1, const curvepoint_fp_t op2)
  85. {
  86. if(fpe_iszero(op1->m_z))
  87. curvepoint_fp_set(rop,op2);
  88. else if(fpe_iszero(op2->m_z))
  89. curvepoint_fp_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. fpe_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. fpe_square(z1z1, op1->m_z);
  96. //Z2Z2 = Z2^2
  97. fpe_square(z2z2, op2->m_z);
  98. //U1 = X1*Z2Z2
  99. fpe_mul(u1, op1->m_x, z2z2);
  100. //U2 = X2*Z1Z1
  101. fpe_mul(u2, op2->m_x, z1z1);
  102. //t0 = Z2*Z2Z2
  103. fpe_mul(t0, op2->m_z, z2z2);
  104. //S1 = Y1*t0
  105. fpe_mul(s1,op1->m_y,t0);
  106. //t1 = Z1*Z1Z1
  107. fpe_mul(t1,op1->m_z, z1z1);
  108. //S2 = Y2*t1
  109. fpe_mul(s2,op2->m_y,t1);
  110. if(fpe_iseq(u1,u2))
  111. {
  112. if(fpe_iseq(s1,s2))
  113. curvepoint_fp_double(rop,op1);
  114. else
  115. curvepoint_fp_setneutral(rop);
  116. }
  117. //H = U2-U1
  118. fpe_sub(h,u2,u1);
  119. //t2 = 2*H
  120. fpe_add(t2, h, h);
  121. //I = t2^2
  122. fpe_short_coeffred(t2);
  123. fpe_square(i,t2);
  124. //J = H*I
  125. fpe_mul(j,h,i);
  126. //t3 = S2-S1
  127. fpe_sub(t3,s2,s1);
  128. //r = 2*t3
  129. fpe_add(r,t3,t3);
  130. //V = U1*I
  131. fpe_mul(v,u1,i);
  132. //t4 = r^2
  133. fpe_short_coeffred(r);
  134. fpe_square(t4,r);
  135. //t5 = 2*V
  136. fpe_add(t5,v,v);
  137. //t6 = t4-J
  138. fpe_sub(t6,t4,j);
  139. //X3 = t6-t5
  140. fpe_sub(rop->m_x,t6,t5);
  141. fpe_short_coeffred(rop->m_x);
  142. //t7 = V-X3
  143. fpe_sub(t7,v,rop->m_x);
  144. //t8 = S1*J
  145. fpe_mul(t8,s1,j);
  146. //t9 = 2*t8
  147. fpe_add(t9,t8,t8);
  148. //t10 = r*t7
  149. fpe_mul(t10,r,t7);
  150. //Y3 = t10-t9
  151. fpe_sub(rop->m_y,t10,t9);
  152. fpe_short_coeffred(rop->m_y);
  153. //t11 = Z1+Z2
  154. fpe_add(t11,op1->m_z,op2->m_z);
  155. //t12 = t11^2
  156. fpe_short_coeffred(t11);
  157. fpe_square(t12,t11);
  158. //t13 = t12-Z1Z1
  159. fpe_sub(t13,t12,z1z1);
  160. //t14 = t13-Z2Z2
  161. fpe_sub(t14,t13,z2z2);
  162. //Z3 = t14*H
  163. fpe_mul(rop->m_z,t14,h);
  164. fpe_short_coeffred(rop->m_z);
  165. }
  166. }
  167. static void curvepoint_fp_add_nocheck(curvepoint_fp_t rop, const curvepoint_fp_t op1, const curvepoint_fp_t op2)
  168. {
  169. //See http://www.hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/addition/add-2007-bl.op3
  170. fpe_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;
  171. //Z1Z1 = Z1^2
  172. fpe_square(z1z1, op1->m_z);
  173. //Z2Z2 = Z2^2
  174. fpe_square(z2z2, op2->m_z);
  175. //U1 = X1*Z2Z2
  176. fpe_mul(u1, op1->m_x, z2z2);
  177. //U2 = X2*Z1Z1
  178. fpe_mul(u2, op2->m_x, z1z1);
  179. //t0 = Z2*Z2Z2
  180. fpe_mul(t0, op2->m_z, z2z2);
  181. //S1 = Y1*t0
  182. fpe_mul(s1,op1->m_y,t0);
  183. //t1 = Z1*Z1Z1
  184. fpe_mul(t1,op1->m_z, z1z1);
  185. //S2 = Y2*t1
  186. fpe_mul(s2,op2->m_y,t1);
  187. //H = U2-U1
  188. fpe_sub(h,u2,u1);
  189. //t2 = 2*H
  190. fpe_add(t2, h, h);
  191. //I = t2^2
  192. fpe_short_coeffred(t2);
  193. fpe_square(i,t2);
  194. //J = H*I
  195. fpe_mul(j,h,i);
  196. //t3 = S2-S1
  197. fpe_sub(t3,s2,s1);
  198. //r = 2*t3
  199. fpe_add(r,t3,t3);
  200. //V = U1*I
  201. fpe_mul(v,u1,i);
  202. //t4 = r^2
  203. fpe_short_coeffred(r);
  204. fpe_square(t4,r);
  205. //t5 = 2*V
  206. fpe_add(t5,v,v);
  207. //t6 = t4-J
  208. fpe_sub(t6,t4,j);
  209. //X3 = t6-t5
  210. fpe_sub(rop->m_x,t6,t5);
  211. fpe_short_coeffred(rop->m_x);
  212. //t7 = V-X3
  213. fpe_sub(t7,v,rop->m_x);
  214. //t8 = S1*J
  215. fpe_mul(t8,s1,j);
  216. //t9 = 2*t8
  217. fpe_add(t9,t8,t8);
  218. //t10 = r*t7
  219. fpe_mul(t10,r,t7);
  220. //Y3 = t10-t9
  221. fpe_sub(rop->m_y,t10,t9);
  222. fpe_short_coeffred(rop->m_y);
  223. //t11 = Z1+Z2
  224. fpe_add(t11,op1->m_z,op2->m_z);
  225. //t12 = t11^2
  226. fpe_short_coeffred(t11);
  227. fpe_square(t12,t11);
  228. //t13 = t12-Z1Z1
  229. fpe_sub(t13,t12,z1z1);
  230. //t14 = t13-Z2Z2
  231. fpe_sub(t14,t13,z2z2);
  232. //Z3 = t14*H
  233. fpe_mul(rop->m_z,t14,h);
  234. fpe_short_coeffred(rop->m_z);
  235. }
  236. /*
  237. void curvepoint_fp_scalarmult_vartime_old(curvepoint_fp_t rop, const curvepoint_fp_t op, const scalar_t scalar, const unsigned int scalar_bitsize)
  238. {
  239. size_t i;
  240. curvepoint_fp_t r;
  241. curvepoint_fp_set(r, op);
  242. for(i = scalar_bitsize-1; i > 0; i--)
  243. {
  244. curvepoint_fp_double(r, r);
  245. if(scalar_getbit(scalar, i - 1))
  246. curvepoint_fp_mixadd(r, r, op);
  247. }
  248. curvepoint_fp_set(rop, r);
  249. }
  250. */
  251. static void choose_t(curvepoint_fp_t t, struct curvepoint_fp_struct *pre, signed char b)
  252. {
  253. if(b>0)
  254. *t = pre[b-1];
  255. else
  256. {
  257. *t = pre[-b-1];
  258. curvepoint_fp_neg(t,t);
  259. }
  260. }
  261. void curvepoint_fp_scalarmult_vartime(curvepoint_fp_t rop, const curvepoint_fp_t op, const scalar_t scalar)
  262. {
  263. signed char s[65];
  264. int i;
  265. curvepoint_fp_t t;
  266. struct curvepoint_fp_struct pre[8];
  267. scalar_window4(s,scalar);
  268. /*
  269. for(i=0;i<64;i++)
  270. printf("%d ",s[i]);
  271. printf("\n");
  272. */
  273. pre[0] = *op; // P
  274. curvepoint_fp_double(&pre[1], &pre[0]); // 2P
  275. curvepoint_fp_add_nocheck(&pre[2], &pre[0], &pre[1]); // 3P
  276. curvepoint_fp_double(&pre[3], &pre[1]); // 4P
  277. curvepoint_fp_add_nocheck(&pre[4], &pre[0], &pre[3]); // 5P
  278. curvepoint_fp_double(&pre[5], &pre[2]); // 6P
  279. curvepoint_fp_add_nocheck(&pre[6], &pre[0], &pre[5]); // 7P
  280. curvepoint_fp_double(&pre[7], &pre[3]); // 8P
  281. i = 64;
  282. while(!s[i]&&i>0) i--;
  283. if(!s[i])
  284. curvepoint_fp_setneutral(rop);
  285. else
  286. {
  287. choose_t(rop,pre,s[i]);
  288. i--;
  289. for(;i>=0;i--)
  290. {
  291. curvepoint_fp_double(rop, rop);
  292. curvepoint_fp_double(rop, rop);
  293. curvepoint_fp_double(rop, rop);
  294. curvepoint_fp_double(rop, rop);
  295. if(s[i])
  296. {
  297. choose_t(t,pre,s[i]);
  298. curvepoint_fp_add_nocheck(rop,rop,t);
  299. }
  300. }
  301. }
  302. }
  303. // Negate a point, store in rop:
  304. void curvepoint_fp_neg(curvepoint_fp_t rop, const curvepoint_fp_t op)
  305. {
  306. fpe_set(rop->m_x, op->m_x);
  307. fpe_neg(rop->m_y, op->m_y);
  308. fpe_set(rop->m_z, op->m_z);
  309. }
  310. // Transform to Affine Coordinates (z=1)
  311. void curvepoint_fp_makeaffine(curvepoint_fp_t point)
  312. {
  313. fpe_t tfpe1;
  314. fpe_invert(tfpe1, point->m_z);
  315. fpe_mul(point->m_x, point->m_x, tfpe1);
  316. fpe_mul(point->m_x, point->m_x, tfpe1);
  317. fpe_mul(point->m_y, point->m_y, tfpe1);
  318. fpe_mul(point->m_y, point->m_y, tfpe1);
  319. fpe_mul(point->m_y, point->m_y, tfpe1);
  320. fpe_setone(point->m_z);
  321. }
  322. // Print a point:
  323. void curvepoint_fp_print(FILE *outfile, const curvepoint_fp_t point)
  324. {
  325. fprintf(outfile, "[");
  326. fpe_print(outfile, point->m_x);
  327. fprintf(outfile, ", ");
  328. fpe_print(outfile, point->m_y);
  329. fprintf(outfile, ", ");
  330. fpe_print(outfile, point->m_z);
  331. fprintf(outfile, "]");
  332. }