MPHELL  4.0.0
mphell-weierstrass.c
Go to the documentation of this file.
1 /*
2  MPHELL-4.0
3  Author(s): The MPHELL team
4 
5  (C) Copyright 2015-2018 - Institut Fourier / Univ. Grenoble Alpes (France)
6 
7  This file is part of the MPHELL Library.
8  MPHELL is free software: you can redistribute it and/or modify
9  it under the terms of the GNU Lesser General Public License as published by
10  the Free Software Foundation, version 3 of the License.
11 
12  MPHELL is distributed in the hope that it will be useful,
13  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  GNU Lesser General Public License for more details.
16 
17  You should have received a copy of the GNU Lesser General Public License
18  along with MPHELL. If not, see <http://www.gnu.org/licenses/>.
19 */
20 
26 /*
27  Formulae:
28  Refererences for different formulae are:
29  -[CMO98] Efficient elliptic curve exponentiation using mixed coordinates
30  by Cohen Henri, Miyaji Atsuko, and Ono Takatoshi. International Conference
31  on the Theory and Application of Cryptology and Information Security.
32  Springer, Berlin, Heidelberg, 1998.
33 
34  -[CC74] Sequences of numbers generated by addition in formal groups and new
35  primality and factorization tests. by Chudnovsky, David V., and Gregory
36  V. Chudnovsky. Advances in Applied Mathematics 7.4 (1986): 385-434.
37 
38  -[Ber01] A software implementation of NIST P-224 by Daniel J. Bernstein
39  slides available here: http://cr.yp.to/talks.html#2001.10.29
40 
41  -[BL] Explicit-formulas database Bernstein, Daniel J., Lange, Tania
42  http://www.hyperelliptic.org/EFD/oldefd/jacobian.html
43  mentionned in [BL07]
44 
45  -[BL07] Faster addition and doubling on elliptic curves.by Bernstein, Daniel J.
46  and Lange, Tanja. In : International Conference on the Theory and Application
47  of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2007.
48  p. 29-50.
49 
50 
51  CoZ formulae:
52  References for CoZ formulae are:
53  -[Mel07] New point addition formulae for ECC applications by Meloni
54  Nicolas published in International Workshop on the Arithmetic of Finite
55  Fields in 2007
56  -[GJM10] CoZ addition formulae and binary ladder on elliptic curves by
57  Goundar, Joye and Miyaji published in International Workshop on
58  Cryptographic Hardware and Embedded Systems in 2010
59 
60 */
61 
62 #include <stdlib.h>
63 #include <string.h>
64 
65 #include "mphell-curve.h"
66 
67 /************************************SETTERS**********************************/
68 
69 void
70 weierstrass_compute_disc(ec_curve E, uint8_t stack)
71 {
72  field_t *k = E->k;
73  /* disc = -16(4a3 + 27b2) */
74  /* D = -(4a3 + 27b2) */
75  field_elt tmp, tmp1;
76  field_elt_get_pool_elt(&tmp, k, stack);
77  field_elt_get_pool_elt(&tmp1, k, stack);
78 
79  field_elt_pow_ui(tmp, E->a, 3, k, stack);
80  field_elt_set_ui(tmp1, 4, false, k, stack);
81  field_elt_mul(tmp, tmp, tmp1, k, stack);
82 
83  field_elt_sqr(E->D, E->b, k, stack);
84  field_elt_set_ui(tmp1, 27, false, k, stack);
85  field_elt_mul(E->D, E->D, tmp1, k, stack);
86 
87  field_elt_add(E->D, E->D, tmp, k);
88  field_elt_neg(E->D, E->D, k);
89 
90  field_elt_set_ui(tmp1, 16, false, k, stack);
91  field_elt_mul(E->disc, E->D, tmp1, k, stack);
92 
93  field_elt_relax_pool_elt(&tmp, k, stack);
94  field_elt_relax_pool_elt(&tmp1, k, stack);
95 }
96 
97 #include "mphell-drbg_internal.h"
98 #include "mphell-sha1.h"
99 
100 bool weierstrass_verify_random_generation(ec_curve E, const char * seed, uint8_t stack)
101 {
102  /* Source : Working Draft AMERICAN NATIONAL STANDARD X9.62-1998, section A.3.4.2 */
103  field_t *k = E->k;
104 
105  field_elt b2, a3, r1;
106  field_elt_get_pool_elt(&b2, k, stack);
107  field_elt_get_pool_elt(&a3, k, stack);
108  field_elt_get_pool_elt(&r1, k, stack);
109 
110  number tmp;
111  number_tmp_alloc(&tmp, k->size, stack);
112 
113  /* t = log2(p) */
114  uint16_t t;
115  switch(k->type)
116  {
117  case FP:
118  t = number_log2(((fp_param)k->param)->p);
119  break;
120  case FP2:
121  case FP3:
122  t = number_log2(((fp_param)((fp2_param)k->param)->base)->p);
123  break;
124  default:
125  return false;
126  }
127  /* s = (t-1) / 160 */
128  uint16_t s = (t-1)/160;
129  /* h = t - 160*s */
130  uint16_t h = t - (160*s);
131  h --; /* set the leftmost bit of c0 to 0 */
132  uint16_t hbytes = (h / 8) + (h%8 != 0);
133 
134  /* Alloc W' */
135 
136  uint8_t * Wprime = calloc(s*20+hbytes, sizeof(uint8_t));
137 
138  /* Step 1 and 2, compute W0: */
139 
140  uint8_t H[20];
141  uint8_t seed_bin[20];
142  /* Convert hexadecimal seed into binary seed */
143  hex2bin(seed, seed_bin);
144  sha1(H, seed_bin, 160);
145  /* c0 = h rightmost bits of H */
146  memcpy(Wprime, H+(20-hbytes), hbytes);
147  uint8_t mask;
148  switch (h%8)
149  {
150  case 0:
151  mask = 0xff;
152  break;
153  case 1:
154  mask = 0x1;
155  break;
156  case 2:
157  mask = 0x3;
158  break;
159  case 3:
160  mask = 0x7;
161  break;
162  case 4:
163  mask = 0xf;
164  break;
165  case 5:
166  mask = 0x1f;
167  break;
168  case 6:
169  mask = 0x3f;
170  break;
171  case 7:
172  mask = 0x7f;
173  break;
174  }
175 
176  Wprime[0]&=mask;
177 
178  /* Step 2 : done with h--*/
179 
180  /* Step 3 and 4 : */
181 
182  uint16_t i;
183  for (i=0; i<s; i++)
184  {
185  drbg_incr_data(seed_bin, 20);
186  sha1(H, seed_bin, 160);
187  memcpy(Wprime+i*20+hbytes, H, 20);
188  }
189 
190  /* Step 5 : Transform Wprime into a field element */
191 
192  /* Convert binary hash into hexadecimal string */
193  unsigned char Wprime_hex[2*(s*20+hbytes)+1];
194  bin2hex(Wprime, s*20+hbytes, Wprime_hex);
195 
196  switch(k->type)
197  {
198  case FP:
199  field_elt_set_str(r1, (const char *)Wprime_hex, 16, false, k, stack);
200  break;
201  case FP2:
202  case FP3:
203  number_set_str(tmp, (const char *)Wprime_hex, 16);
204  field_elt_set_number(r1, false, k, stack, 1, tmp);
205  break;
206  default:
207  field_elt_set_one(r1, k);
208  }
209 
210  /* Step 6 : Accept or reject */
211 
212  field_elt_sqr(b2, E->b, k, stack);
213  field_elt_pow_ui(a3, E->a, 3, k, stack);
214  field_elt_mul(r1, r1, b2, k, stack);
215  int8_t res = field_elt_cmp(r1, a3, k);
216 
217  number_tmp_free(&tmp, k->size, stack);
218 
219  field_elt_relax_pool_elt(&a3, k, stack);
220  field_elt_relax_pool_elt(&b2, k, stack);
221  field_elt_relax_pool_elt(&r1, k, stack);
222  free(Wprime);
223 
224  return (res == 0);
225 }
226 
227 void weierstrass_curve_random_generation(fe_ptr a, fe_ptr b, char * seed_res, field_srcptr k, uint8_t stack)
228 {
229  /* Source : Working Draft AMERICAN NATIONAL STANDARD X9.62-1998, section A.3.3.2 */
230  bool test;
231  number seed;
232  number bound_h;
233  number bound_l;
234  number tmp;
235  number_tmp_alloc(&tmp, k->size, stack);
236  number_tmp_alloc(&seed, bits_to_nblock(160), stack);
237  number_tmp_alloc(&bound_h, bits_to_nblock(160), stack);
238  number_tmp_alloc(&bound_l, bits_to_nblock(160), stack);
239  number_set_str(bound_h, "ffffffffffffffffffffffffffffffffffffffff", 16); /* 2^161 - 1 */
240  number_set_str(bound_l, "1000000000000000000000000000000000000000", 16); /* 2^160 */
241 
242  field_elt b2, a3, r1, tmp1, tmp2;
243  field_elt_get_pool_elt(&b2, (field_ptr)k, stack);
244  field_elt_get_pool_elt(&a3, (field_ptr)k, stack);
245  field_elt_get_pool_elt(&r1, (field_ptr)k, stack);
246  field_elt_get_pool_elt(&tmp1, (field_ptr)k, stack);
247  field_elt_get_pool_elt(&tmp2, (field_ptr)k, stack);
248 
249  char * seed_hex;
250 
251  /* t = log2(p) */
252  uint16_t t;
253  switch(k->type)
254  {
255  case FP:
256  t = number_log2(((fp_param)k->param)->p);
257  break;
258  case FP2:
259  case FP3:
260  t = number_log2(((fp_param)((fp2_param)k->param)->base)->p);
261  break;
262  default:
263  t = 0;
264  }
265  /* s = (t-1) / 160 */
266  uint16_t s = (t-1)/160;
267  /* h = t - 160*s */
268  uint16_t h = t - (160*s);
269  h --; /* set the leftmost bit of c0 to 0 */
270  uint16_t hbytes = (h / 8) + (h%8 != 0);
271 
272  /* Alloc W' */
273  uint8_t * Wprime = calloc(s*20+hbytes, sizeof(uint8_t));
274 
275  do
276  {
277  /* Step 1 : Choose an arbitrary bit string SEED of bit length at least 160 bits */
278  do
279  {
280  number_random1(seed, bound_h, stack);
281  }
282  while(number_cmp(seed, bound_l)<0);
283 
284  number_str(&seed_hex, seed, 16);
285 
286  /* Step 2 and 3, compute W0 : */
287 
288  uint8_t H[20];
289  uint8_t seed_bin[20];
290  /* Convert hexadecimal seed into binary seed */
291  hex2bin(seed_hex, seed_bin);
292  sha1(H, seed_bin, 160);
293  /* c0 = h rightmost bits of H */
294  memcpy(Wprime, H+(20-hbytes), hbytes);
295  uint8_t mask;
296  switch (h%8)
297  {
298  case 0:
299  mask = 0xff;
300  break;
301  case 1:
302  mask = 0x1;
303  break;
304  case 2:
305  mask = 0x3;
306  break;
307  case 3:
308  mask = 0x7;
309  break;
310  case 4:
311  mask = 0xf;
312  break;
313  case 5:
314  mask = 0x1f;
315  break;
316  case 6:
317  mask = 0x3f;
318  break;
319  case 7:
320  mask = 0x7f;
321  break;
322  }
323 
324  Wprime[0]&=mask;
325 
326  /* Step 4 and 5 : */
327 
328  uint16_t i;
329  for (i=0; i<s; i++)
330  {
331  drbg_incr_data(seed_bin, 20);
332  sha1(H, seed_bin, 160);
333  memcpy(Wprime+i*20+hbytes, H, 20);
334  }
335 
336  /* Convert binary hash into hexadecimal string */
337  unsigned char Wprime_hex[2*(s*20+hbytes)+1];
338  bin2hex(Wprime, s*20+hbytes, Wprime_hex);
339 
340  /* Step 6 : Transform Wprime into a field element */
341 
342  switch(k->type)
343  {
344  case FP:
345  field_elt_set_str(r1, (const char *)Wprime_hex, 16, false, k, stack);
346  break;
347  case FP2:
348  case FP3:
349  number_set_str(tmp, (const char *)Wprime_hex, 16);
350  field_elt_set_number(r1, false, k, stack, 1, tmp);
351  break;
352  default:
353  field_elt_set_one(r1, k);
354  }
355 
356 
357  /* Step 7: Choose a and b */
358 
359  do
360  {
361  field_elt_random(a, k, stack);
362  field_elt_pow_ui(a3, a, 3, k, stack);
363  field_elt_div(b2, a3, r1, k, stack);
364  }
365  while(!field_elt_issquare(b2, k, stack));
366 
367  field_elt_sqrt(b, b2, k, stack);
368  field_elt_set_ui(tmp1, 4, false, k, stack);
369  field_elt_set_ui(tmp2, 27, false,k, stack);
370  field_elt_mul(tmp1, tmp1, a3, k, stack); /* 4a^3 */
371  field_elt_mul(tmp2, tmp2, b2, k, stack); /* 27b^2 */
372  field_elt_add(tmp1, tmp1, tmp2, k); /* 4a^3 + 27b^2 */
373  test = field_elt_iszero(tmp1, k);
374  if (test)
375  {
376  free(seed_hex);
377  }
378  }
379  /* Step 8: verifie that the curve is elliptic */
380  while(test);
381 
382  strcpy(seed_res, seed_hex);
383  number_tmp_free(&tmp, k->size, stack);
384  number_tmp_free(&seed, bits_to_nblock(160), stack);
385  number_tmp_free(&bound_h, bits_to_nblock(160), stack);
386  number_tmp_free(&bound_l, bits_to_nblock(160), stack);
387  field_elt_relax_pool_elt(&a3, (field_ptr)k, stack);
388  field_elt_relax_pool_elt(&b2, (field_ptr)k, stack);
389  field_elt_relax_pool_elt(&r1, (field_ptr)k, stack);
390  field_elt_relax_pool_elt(&tmp1, (field_ptr)k, stack);
391  field_elt_relax_pool_elt(&tmp2, (field_ptr)k, stack);
392  free(seed_hex);
393  free(Wprime);
394 }
395 
396 void
397 weierstrass_point_set_neutral (ec_point_ptr dst, ec_curve_srcptr E, uint8_t stack)
398 {
399  field_t *k = E->k;
400 
401  switch(E->f)
402  {
403  case PROJECTIVE :
404  field_elt_set_ui(dst->x, 0, true, k, stack);
405  field_elt_set_one(dst->y, k);
406  field_elt_set_ui(dst->z, 0, true, k, stack);
407  field_elt_set_one(dst->t, k);
408  break;
409 
410  case JACOBIAN :
411  field_elt_set_one(dst->x, k);
412  field_elt_set_one(dst->y, k);
413  field_elt_set_ui(dst->z, 0, true, k, stack);
414  field_elt_set_one(dst->t, k);
415  break;
416 
417  default :
418  break;
419  }
420 }
421 
422 void
423 weierstrass_point_set_aff (ec_point_ptr P, fe_srcptr x, fe_srcptr y, field_srcptr k)
424 {
425  field_elt_copy(P->x, x, k);
426  field_elt_copy(P->y, y, k);
427  field_elt_set_one(P->z, k);
428  field_elt_set_one(P->t, k);
429 }
430 
431 void
432 weierstrass_point_set_aff_str (ec_point_ptr P, const char *str_x, const char *str_y,
433  const bool is_reduced, const uint8_t base, field_srcptr k, uint8_t stack)
434 {
435  field_elt_set_str(P->x, str_x, base, is_reduced, k, stack);
436  field_elt_set_str(P->y, str_y, base, is_reduced, k, stack);
437  field_elt_set_one(P->z, k);
438  field_elt_set_one(P->t, k);
439 }
440 
441 bool
442 weierstrass_belongs (ec_point_srcptr P, ec_curve_srcptr E, uint8_t stack)
443 {
444  /* P1 = (X1, Y1, Z1) */
445  /* E: y^2 = x^3 + ax + b */
446 
447  field_t *k = E->k;
448 
449  field_elt t1, t2, t3;
450  field_elt_get_pool_elt(&t1, k, stack);
451  field_elt_get_pool_elt(&t2, k, stack);
452  field_elt_get_pool_elt(&t3, k, stack);
453 
454  switch(E->f)
455  {
456  case PROJECTIVE :
457 
458  field_elt_sqr(t1, P->y, k, stack); /* t1 = Y1^2 */
459  field_elt_mul(t1, t1, P->z, k, stack); /* t1 = (Y1^2).Z1 */
460 
461  field_elt_sqr(t2, P->z, k, stack); /* t2 = Z1^2 */
462  field_elt_mul(t2, t2, E->a, k, stack); /* t2 = (Z1^2).a */
463  field_elt_mul(t2, t2, P->x, k, stack); /* t2 = (Z1^2).a.X1 */
464 
465  field_elt_sqr(t3, P->z, k, stack); /* t3 = Z1^2 */
466  field_elt_mul(t3, t3, P->z, k, stack); /* t3 = Z1^3 */
467  field_elt_mul(t3, t3, E->b, k, stack); /* t3 = (Z1^3).b */
468 
469  field_elt_add(t2, t2, t3, k); /* t2 = (Z1^2).a.X1 + (Z1^3).b */
470 
471  field_elt_sqr(t3, P->x, k, stack); /* t3 = X1^2 */
472  field_elt_mul(t3, t3, P->x, k, stack); /* t3 = X1^3 */
473  field_elt_add(t2, t2, t3, k); /* t2 = X1^3 + (Z1^2).a.X1 + (Z1^3).b */
474  break;
475 
476  case JACOBIAN :
477 
478  field_elt_sqr(t1, P->y, k, stack); /* t1 = Y1^2 */
479 
480  field_elt_sqr(t2, P->z, k, stack); /* t2 = Z1^2 */
481  field_elt_sqr(t2, t2, k, stack); /* t2 = Z1^4 */
482  field_elt_mul(t2, t2, E->a, k, stack); /* t2 = (Z1^4).a */
483  field_elt_mul(t2, t2, P->x, k, stack); /* t2 = (Z1^4).a.X1 */
484 
485  field_elt_sqr(t3, P->z, k, stack); /* t3 = Z1^2 */
486  field_elt_mul(t3, t3, P->z, k, stack); /* t3 = Z1^3 */
487  field_elt_sqr(t3, t3, k, stack); /* t3 = Z1^6 */
488  field_elt_mul(t3, t3, E->b, k, stack); /* t3 = (Z1^6).b */
489 
490  field_elt_add(t2, t2, t3, k); /* t2 = (Z1^4).a.X1 + (Z1^6).b */
491 
492  field_elt_sqr(t3, P->x, k, stack); /* t3 = X1^2 */
493  field_elt_mul(t3, t3, P->x, k, stack); /* t3 = X1^3 */
494  field_elt_add(t2, t2, t3, k); /* t2 = X1^3 + (Z1^4).a.X1 + (Z1^6).b */
495  break;
496 
497  default :
498  break;
499  }
500 
501  bool res = (field_elt_cmp(t1, t2, k) == 0);
502 
503  field_elt_relax_pool_elt(&t1, k, stack);
504  field_elt_relax_pool_elt(&t2, k, stack);
505  field_elt_relax_pool_elt(&t3, k, stack);
506 
507  return res;
508 }
509 
510 void
511 weierstrass_point_random (ec_point_ptr P, ec_curve_srcptr E, uint8_t stack)
512 {
513  field_t *k = E->k;
514 
515  field_elt t1, t2;
516  field_elt_get_pool_elt(&t1, k, stack);
517  field_elt_get_pool_elt(&t2, k, stack);
518 
519  do{
520  field_elt_random(P->x, k, stack);
521  field_elt_mul(t1, E->a, P->x, k, stack); /* t1 = a.x */
522  field_elt_sqr(t2, P->x, k, stack); /* t2 = x^2 */
523  field_elt_mul(t2, t2, P->x, k, stack); /* t2 = x^3 */
524  field_elt_add(t1, t1, t2, k); /* t1 = x^3 + a.x */
525  field_elt_add(t1, t1, E->b, k); /* t1 = x^3 + a.x + b */
526  }
527  while(!field_elt_issquare(t1, k, stack));
528 
529  field_elt_sqrt(t2, t1, k, stack);
530  weierstrass_point_set_aff(P, P->x, t2, k);
531 
532  field_elt_relax_pool_elt(&t1, k, stack);
533  field_elt_relax_pool_elt(&t2, k, stack);
534 }
535 
536 void
537 weierstrass_point_norm (ec_point_ptr P, ec_curve_srcptr E, uint8_t stack)
538 {
539  field_t *k = E->k;
540  field_elt u;
541  field_elt_get_pool_elt(&u, k, stack);
542 
543  if(!weierstrass_point_is_neutral(P, E, stack))
544  {
545  switch(E->f)
546  {
547  case PROJECTIVE :
548  field_elt_inv(u, P->z, k, stack); /* u = 1/Z */
549  field_elt_mul(P->x, P->x, u, k, stack); /* X = X / Z */
550  field_elt_mul(P->y, P->y, u, k, stack); /* Y = Y / Z */
551  field_elt_set_one(P->z, k); /* Z = 1 */
552  field_elt_set_one(P->t, k); /* T = 1 */
553  break;
554 
555  case JACOBIAN :
556  field_elt_inv(u, P->z, k, stack); /* u = 1/Z */
557  field_elt_sqr(P->t, u, k, stack); /* T = 1/Z^2 */
558  field_elt_mul(P->x, P->x, P->t, k, stack); /* X = X/Z^2 */
559  field_elt_mul(u, u, P->t, k, stack); /* u = 1/Z^3 */
560  field_elt_mul(P->y, P->y, u, k, stack); /* Y = Y/Z^3 */
561  field_elt_set_one(P->z, k); /* Z = 1 */
562  field_elt_set_one(P->t, k); /* T = 1 */
563  break;
564 
565  default :
566  break;
567  }
568  }
569  else
570  {
571  /* Write neutral element under classical form */
572  weierstrass_point_set_neutral(P, E, stack);
573  }
574  field_elt_relax_pool_elt(&u, k, stack);
575 }
576 
577 void
578 weierstrass_point_get_x_affine (field_elt x, ec_point_ptr P, ec_curve_srcptr E, uint8_t stack)
579 {
580  field_t *k = E->k;
581  field_elt u;
582  field_elt_get_pool_elt(&u, k, stack);
583 
584  switch(E->f)
585  {
586  case PROJECTIVE :
587  field_elt_inv(u, P->z, k, stack); /* u = 1/Z */
588  field_elt_mul(x, P->x, u, k, stack); /* x = X / Z */
589  break;
590 
591  case JACOBIAN :
592  field_elt_inv(u, P->z, k, stack); /* u = 1/Z */
593  field_elt_sqr(u, u, k, stack); /* u = 1/Z^2 */
594  field_elt_mul(x, P->x, u, k, stack); /* x = X/Z^2 */
595  break;
596 
597  default :
598  break;
599  }
600  field_elt_relax_pool_elt(&u, k, stack);
601 }
602 
603 void
604 weierstrass_point_get_y_affine (field_elt y, ec_point_ptr P, ec_curve_srcptr E, uint8_t stack)
605 {
606  field_t *k = E->k;
607  field_elt u;
608  field_elt_get_pool_elt(&u, k, stack);
609 
610  switch(E->f)
611  {
612  case PROJECTIVE :
613  field_elt_inv(u, P->z, k, stack); /* u = 1/Z */
614  field_elt_mul(y, P->y, u, k, stack); /* y = Y / Z */
615  break;
616 
617  case JACOBIAN :
618  field_elt_inv(u, P->z, k, stack); /* u = 1/Z */
619  field_elt_sqr(u, u, k, stack); /* u = 1/Z^2 */
620  field_elt_mul(u, P->z, P->t, k, stack); /* u = 1/Z^3 */
621  field_elt_mul(y, P->y, u, k, stack); /* y = Y/Z^3 */
622  break;
623 
624  default :
625  break;
626  }
627  field_elt_relax_pool_elt(&u, k, stack);
628 }
629 
630 /*******************************COMPARISON************************************/
631 
632 bool
633 weierstrass_point_is_neutral (ec_point_srcptr P, ec_curve_srcptr E, uint8_t stack)
634 {
635  field_t *k = E->k;
636  switch(E->f)
637  {
638  case PROJECTIVE :
639  return (field_elt_iszero(P->x, k) &&
640  field_elt_isone(P->y, k) && field_elt_iszero(P->z, k));
641  break;
642 
643  case JACOBIAN :
644  /* The infinity point as representation (t^2, t^3, 0) */
645  if(field_elt_iszero(P->z, k))
646  {
647  field_elt a, b;
648  field_elt_get_pool_elt(&a, k, stack);
649  field_elt_get_pool_elt(&b, k, stack);
650  field_elt_sqr(a, P->y, k, stack);
651  field_elt_pow_ui(b, P->x, (block)3, k, stack);
652  if(field_elt_cmp(a, b, k)==0)
653  {
654  field_elt_relax_pool_elt(&a, k, stack);
655  field_elt_relax_pool_elt(&b, k, stack);
656  return true;
657  }
658  else
659  {
660  field_elt_relax_pool_elt(&a, k, stack);
661  field_elt_relax_pool_elt(&b, k, stack);
662  return false;
663  }
664  }
665  else
666  {
667  return false;
668  }
669  break;
670 
671  default :
672  return false;
673  }
674 }
675 
676 bool
677 weierstrass_point_are_equal (ec_point_srcptr P1, ec_point_srcptr P2,
678  ec_curve_srcptr E, uint8_t stack)
679 {
680  field_t *k = E->k;
681  field_elt u, v, tmp, tmp1;
682  bool res = false;
683  /* P1=(x1,y1,z1), P2=(x2,y2,z2) */
684  if (field_elt_iszero(P1->z, k) || field_elt_iszero(P2->z, k))
685  {
686  return (weierstrass_point_is_neutral(P1, E, stack) && weierstrass_point_is_neutral(P2, E, stack));
687  }
688 
689  switch(E->f)
690  {
691  case PROJECTIVE :
692  if (field_elt_iszero(P1->y, k))
693  {
694  if(field_elt_iszero(P2->y, k))
695  {
696  if(field_elt_cmp(P1->x, P2->x, k)==0)
697  {
698  res = true;
699  break;
700  }
701  else
702  {
703  res = false;
704  break;
705  }
706  }
707  else
708  {
709  res = false;
710  break;
711  }
712  }
713 
714  field_elt_get_pool_elt(&u, k, stack);
715  field_elt_get_pool_elt(&v, k, stack);
716  field_elt_mul(u, P1->x, P2->z, k, stack); /* u = x1 * z2 */
717  field_elt_mul(v, P1->z, P2->x, k, stack); /* v = z1 * x2 */
718  if(field_elt_cmp(u, v, k) != 0)
719  {
720  res = false;
721  field_elt_relax_pool_elt(&u, k, stack);
722  field_elt_relax_pool_elt(&v, k, stack);
723  break;
724  }
725  field_elt_mul(u, P1->y, P2->z, k, stack); /* u = y1 * z2 */
726  field_elt_mul(v, P1->z, P2->y, k, stack); /* v = z1 * y2 */
727 
728  res = (field_elt_cmp(u, v, k) == 0);
729  field_elt_relax_pool_elt(&u, k, stack);
730  field_elt_relax_pool_elt(&v, k, stack);
731  break;
732 
733  case JACOBIAN :
734  field_elt_get_pool_elt(&u, k, stack);
735  field_elt_get_pool_elt(&v, k, stack);
736  field_elt_get_pool_elt(&tmp, k, stack);
737  field_elt_get_pool_elt(&tmp1, k, stack);
738 
739  field_elt_sqr(u, P1->z, k, stack);
740  field_elt_sqr(v, P2->z, k, stack);
741 
742  field_elt_mul(tmp, P2->x, u, k, stack); /* tmp = x2 * z1^2 */
743  field_elt_mul(tmp1, P1->x, v, k, stack); /* tmp1 = x1 * z2^2 */
744  if((field_elt_cmp(tmp, tmp1, k) != 0))
745  {
746  res = false;
747  field_elt_relax_pool_elt(&u, k, stack);
748  field_elt_relax_pool_elt(&v, k, stack);
749  field_elt_relax_pool_elt(&tmp, k, stack);
750  field_elt_relax_pool_elt(&tmp1, k, stack);
751  break;
752  }
753  field_elt_mul(u, u, P1->z, k, stack);
754  field_elt_mul(v, v, P2->z, k, stack);
755  field_elt_mul(tmp, P2->y, u, k, stack); /* tmp = y2 * z1^3 */
756  field_elt_mul(tmp1, P1->y, v, k, stack); /* tmp1 = y1 * z2^3 */
757  res = (field_elt_cmp(tmp, tmp1, k) == 0);
758 
759  field_elt_relax_pool_elt(&u, k, stack);
760  field_elt_relax_pool_elt(&v, k, stack);
761  field_elt_relax_pool_elt(&tmp, k, stack);
762  field_elt_relax_pool_elt(&tmp1, k, stack);
763  break;
764  default :
765  res = false;
766  }
767  return res;
768 }
769 
770 /*******************************OPERATIONS************************************/
771 
774 void
775 weierstrass_point_add_ZADDU (ec_point_ptr P3, ec_point_ptr P1, ec_point_srcptr P2,
776  ec_curve_srcptr E, uint8_t stack)
777 {
778 
779  /* Those formulae are taken from [GJM10, §2.2, Algorithm 1] */
780  /* Costs 5M, 2S, 7Add */
781  field_t *k = E->k;
782  field_elt tmp1, tmp3;
783 
784  field_elt_get_pool_elt(&tmp1, k, stack);
785  field_elt_get_pool_elt(&tmp3, k, stack);
786 
787  field_elt_sub(tmp1, P1->x, P2->x, k); /* tmp1 = X1 - X2 */
788  field_elt_mul(P3->z, P2->z, tmp1, k, stack); /* Z3 = Z1 * (X1 - X2) */
789  field_elt_sqr(tmp1, tmp1, k, stack); /* tmp1 = (X1 - X2)^2 = C */
790 
791  field_elt_mul(P1->x, P1->x, tmp1, k, stack); /* X1 = X1 * C = W1 */
792  field_elt_mul(tmp3, P2->x, tmp1, k, stack); /* tmp3 = X2 * C = W2 */
793 
794  field_elt_sub(P3->y, P1->y, P2->y, k); /* Y3 = Y1 - Y2 */
795  field_elt_sqr(tmp1, P3->y, k, stack); /* tmp1 = (Y1 - Y2)^2 = D */
796 
797  field_elt_sub(P1->z, P1->x, tmp3, k); /* Z1 = W1 - W2 */
798  field_elt_mul(P1->y, P1->y, P1->z, k, stack); /* Y1 = Y1 * (W1 - W2) = A1 */
799 
800  field_elt_sub(P3->x, tmp1, P1->x, k); /* X3 = D - W1 */
801  field_elt_sub(P3->x, P3->x, tmp3, k); /* X3 = D - W1 - W2 */
802 
803  field_elt_sub(tmp3, P1->x, P3->x, k); /* tmp3 = W1 - X3 */
804  field_elt_mul(P3->y, P3->y, tmp3, k, stack); /* Y3 = (Y1 - Y2) * (W1 - X3) */
805  field_elt_sub(P3->y, P3->y, P1->y, k); /* Y3 = (Y1 - Y2) * (W1 - X3) - A1 */
806 
807  field_elt_copy(P1->z, P3->z, k); /* Z1 = Z3 */
808  field_elt_set_one(P3->t, k); /* T3 = 1 */
809 
810  field_elt_relax_pool_elt(&tmp1, k, stack);
811  field_elt_relax_pool_elt(&tmp3, k, stack);
812 }
813 
814 void
815 weierstrass_point_add_ZADDC (ec_point_ptr P3, ec_point_ptr P4, ec_point_srcptr P1,
816  ec_point_srcptr P2, ec_curve_srcptr E, uint8_t stack)
817 {
818  /* Those formulae are taken from [GJM10,§4 Algorithm 6] */
819  /* Costs 6M, 3S, 11Add */
820  field_t *k = E->k;
821  field_elt tmp1, tmp6;
822 
823  field_elt_get_pool_elt(&tmp1, k, stack);
824  field_elt_get_pool_elt(&tmp6, k, stack);
825 
826  field_elt_sub(tmp1, P1->x, P2->x, k); /* tmp1 = X1 - X2 */
827  field_elt_mul(P3->z, P1->z, tmp1, k, stack); /* Z3 = Z * (X1 - X2) */
828  field_elt_sqr(tmp1, tmp1, k, stack); /* tmp1 = (X1 - X2)^2 = C */
829 
830  field_elt_mul(P4->t, P1->x, tmp1, k, stack); /* tmp2 = X1 * C = W1 */
831  field_elt_mul(P4->x, P2->x, tmp1, k, stack); /* tmp3 = X2 * C = W2 */
832  field_elt_add(tmp1, P4->t, P4->x, k); /* tmp1 = W1 + W2 */
833 
834  field_elt_sub(P4->z, P4->t, P4->x, k); /* tmp5 = W1 - W2 */
835  field_elt_mul(P4->z, P1->y, P4->z, k, stack); /* tmp5 = Y1 * (W1 - W2) = A1 */
836 
837  field_elt_sub(P4->x, P1->y, P2->y, k); /* tmp3 = Y1 - Y2 */
838  field_elt_sqr(tmp6, P4->x, k, stack); /* tmp4 = (Y1 - Y2)^2 = D */
839 
840  field_elt_sub(P3->x, tmp6, tmp1, k); /* X3 = D - W1 - W2 */
841 
842  field_elt_add(P4->y, P1->y, P2->y, k); /* tmp4 = Y1 + Y2 */
843 
844  field_elt_sub(tmp6, P4->t, P3->x, k); /* tmp6 = W1 - X3 */
845  field_elt_mul(P3->y, P4->x, tmp6, k, stack); /* Y3 = (Y1 - Y2) * (W1 - X3) */
846  field_elt_sub(P3->y, P3->y, P4->z, k); /* Y3 = (Y1 - Y2) * (W1 - X3) - A1 */
847 
848  field_elt_set_one(P3->t, k); /* T3 = 1 */
849 
850  field_elt_sqr(P4->x, P4->y, k, stack); /* tmp3 = (Y1 + Y2)^2 = D */
851  field_elt_sub(P4->x, P4->x, tmp1, k); /* X4 = D - W1 - W2 */
852 
853  field_elt_sub(tmp6, P4->t, P4->x, k); /* tmp6 = W1 - X4 */
854  field_elt_mul(P4->y, P4->y, tmp6, k, stack); /* Y4 = (Y1 + Y2) * (W1 - X4) */
855  field_elt_sub(P4->y, P4->y, P4->z, k); /* Y4 = (Y1 + Y2) * (W1 - X4) - A1 */
856 
857  field_elt_copy(P4->z, P3->z, k); /* Z4 = Z3 */
858 
859  field_elt_set_one(P4->t, k); /* T4 = 1 */
860 
861  field_elt_relax_pool_elt(&tmp1, k, stack);
862  field_elt_relax_pool_elt(&tmp6, k, stack);
863 }
864 
865 void
866 weierstrass_point_add_ZDAU (ec_point_ptr P3, ec_point_srcptr P1, ec_point_ptr P2,
867  ec_curve_srcptr E, uint8_t stack)
868 {
869  /* Those formulae are taken from [GJM10,§4.4 and Algorithm 9] */
870  /* Costs 9 M + 7 S + 22 Add + 1*2 + 1*4 */
871  field_t *k = E->k;
872  field_elt c,cp,a1,w1,w1p,w2p,d,x3;
873 
874  field_elt_get_pool_elt(&cp, k, stack);
875  field_elt_get_pool_elt(&w1p, k, stack);
876  field_elt_get_pool_elt(&w2p, k, stack);
877  field_elt_get_pool_elt(&d, k, stack);
878  field_elt_get_pool_elt(&a1, k, stack);
879  field_elt_get_pool_elt(&w1, k, stack);
880  field_elt_get_pool_elt(&x3, k, stack);
881  field_elt_get_pool_elt(&c, k, stack);
882 
883  field_elt_sub(P3->z, P1->x, P2->x, k);
884  field_elt_sqr(cp, P3->z, k, stack); /* C' = (X1-X2)^2 */
885  field_elt_mul(w1p, P1->x, cp, k, stack); /* W1' = X1C' */
886  field_elt_mul(w2p, P2->x, cp, k, stack); /* W2' = X2C' */
887  field_elt_sub(a1, w1p, w2p, k);
888  field_elt_mul(a1, P1->y, a1, k, stack); /* A1' = Y1(W1'-W2') */
889  field_elt_sub(P3->y, P1->y, P2->y, k);
890  field_elt_sqr(d, P3->y, k, stack); /* D' = (Y1-Y2)^2 */
891  field_elt_sub(x3, d, w1p, k);
892  field_elt_sub(x3, x3, w2p, k); /* X3' = D' - W1' -W2' */
893  field_elt_sub(P3->x, x3, w1p, k);
894  field_elt_sqr(c, P3->x, k, stack); /* C = (X3' - W1')^2 */
895  field_elt_add(P3->z, P3->z,P3->x, k);
896  field_elt_sqr(P3->z, P3->z, k, stack);
897  field_elt_sub(P3->z, P3->z,cp, k);
898  field_elt_sub(P3->z, P3->z,c, k);
899  field_elt_mul(P3->z, P3->z,P2->z, k, stack); /* Z3 =Z((X1-X2+X3'-W1')^2-C'-C) */
900  field_elt_sub(cp, P3->y,P3->x, k);
901  field_elt_sqr(cp, cp, k, stack);
902  field_elt_sub(cp, cp, d, k);
903  field_elt_sub(cp, cp, c, k);
904  field_elt_mul2(a1, a1, k);
905  field_elt_sub(cp, cp, a1, k); /* Y3' = [(Y1-Y2) - (X3'-W1')]^2 - D' - C - 2A1' (stored in cp) */
906  field_elt_mul4(d, c, k);
907  field_elt_mul(w1, x3, d, k, stack); /* W1 = 4X3'C */
908  field_elt_mul(w2p, d, w1p, k, stack); /* W2 = 4W1'C */
909  field_elt_sub(w1p, cp, a1, k);
910  field_elt_sqr(d, w1p, k, stack); /* D = (Y3' - 2A1')^2 */
911  field_elt_add(P2->y, w1, w2p, k);
912  field_elt_sub(P3->x, d, P2->y, k); /* X3 = D - W1 - W2 */
913  field_elt_sub(c, w1, w2p, k);
914  field_elt_mul(c, c, cp, k, stack); /* A1 = Y3'(W1-W2) (stored in c) */
915  field_elt_sub(d, w1, P3->x, k);
916  field_elt_mul(P3->y, w1p, d, k, stack);
917  field_elt_sub(P3->y, P3->y, c, k); /* Y3 = (Y3' - 2A1')(W1 - X3) - A1 */
918  field_elt_add(w1p, cp, a1, k);
919  field_elt_sqr(d, w1p, k, stack); /* D = (Y3' + 2A1')^2 */
920  field_elt_sub(P2->x, d, P2->y, k); /* X2 = D - W1 - W2 */
921  field_elt_sub(P2->y, w1, P2->x, k);
922  field_elt_mul(P2->y, P2->y, w1p, k, stack);
923  field_elt_sub(P2->y, P2->y, c, k); /* Y2 = (Y3'+ 2A1')(W1-X2)-A1 */
924  field_elt_copy(P2->z, P3->z, k); /* Z2 = Z3 */
925 
926  field_elt_set_one(P3->t, k); /* T3 = 1 */
927 
928  field_elt_relax_pool_elt(&c, k, stack);
929  field_elt_relax_pool_elt(&w1p, k, stack);
930  field_elt_relax_pool_elt(&w2p, k, stack);
931  field_elt_relax_pool_elt(&w1, k, stack);
932  field_elt_relax_pool_elt(&a1, k, stack);
933  field_elt_relax_pool_elt(&x3, k, stack);
934  field_elt_relax_pool_elt(&cp, k, stack);
935  field_elt_relax_pool_elt(&d, k, stack);
936 
937 }
938 
939 void
940 weierstrass_point_DBLU (ec_point_ptr P3, ec_point_ptr P4, ec_point_srcptr P1,
941  ec_curve_srcptr E, uint8_t stack)
942 {
943  field_t *k = E->k;
944  field_elt tmp1, tmp2, tmp3, tmp4, tmp5, tmp6;
945 
946  /* Those formulae are taken from [GJM10,§4.3] for the case of P1->z==1 */
947  /* Very similar to those of Jacobian case */
948  /* Costs 1 M 5 S 6 Add 3*2 1*3 1*8 */
949 
950  /* It is supposed that Z1==1 */
951  MPHELL_ASSERT( field_elt_isone(P1->z, k), "\nThis point P1 should have its Z coordinate equals to 1 to apply DBLU\n");
952 
953  field_elt_get_pool_elt(&tmp1, k, stack);
954  field_elt_get_pool_elt(&tmp2, k, stack);
955  field_elt_get_pool_elt(&tmp3, k, stack);
956  field_elt_get_pool_elt(&tmp4, k, stack);
957  field_elt_get_pool_elt(&tmp5, k, stack);
958  field_elt_get_pool_elt(&tmp6, k, stack);
959 
960  field_elt_sqr(tmp1, P1->x, k, stack); /* B = X1^2 */
961  field_elt_sqr(tmp2, P1->y, k, stack); /* E = Y1^2 */
962 
963  field_elt_sqr(tmp3, tmp2, k, stack); /* L = E^2 */
964 
965  field_elt_add(tmp4, P1->x, tmp2, k); /* tmp4 = X1 + E */
966  field_elt_sqr(tmp4, tmp4, k, stack); /* tmp4 = (X1 + E)^2 */
967  field_elt_sub(tmp4, tmp4, tmp1, k); /* tmp4 = (X1 + E)^2 - B */
968  field_elt_sub(tmp4, tmp4, tmp3, k); /* tmp4 = (X1 + E)^2 - B - L */
969  field_elt_mul2(tmp4, tmp4, k); /* S = 2((X1 + E)^2 - B - L) */
970 
971  field_elt_mul3(tmp5, tmp1, k, stack); /* tmp5 = 3 * B */
972  field_elt_add(tmp5, tmp5, E->a, k); /* M = 3 * B + a */
973 
974  field_elt_sqr(P3->x, tmp5, k, stack); /* X3 = M^2 */
975  field_elt_mul2(tmp1, tmp4, k); /* tmp1 = 2.S */
976  field_elt_sub(P3->x, P3->x, tmp1, k); /* X3 = M^2 - 2 * S */
977 
978  field_elt_sub(P3->y, tmp4, P3->x, k); /* Y3 = S - X3 */
979  field_elt_mul(P3->y, tmp5, P3->y, k, stack); /* Y3 = M * (S - X3) */
980  field_elt_mul8(tmp3, tmp3, k); /* tmp3 = 8 * L */
981 
982  field_elt_sub(P3->y, P3->y, tmp3, k); /* Y3 = M * (S - X3) - 8 * L */
983 
984  field_elt_mul2(P3->z, P1->y, k); /* Z3 = 2 * Y1 */
985  field_elt_set_one(P3->t, k); /* T3 = 1 */
986 
987  field_elt_copy(P4->x, tmp4, k); /* X4 = S */
988  field_elt_copy(P4->y, tmp3, k); /* Y4 = 8 * L */
989  field_elt_copy(P4->z, P3->z, k); /* Z4 = Z3 */
990  field_elt_set_one(P4->t, k); /* T4 = 1 */
991 
992  field_elt_relax_pool_elt(&tmp1, k, stack);
993  field_elt_relax_pool_elt(&tmp2, k, stack);
994  field_elt_relax_pool_elt(&tmp3, k, stack);
995  field_elt_relax_pool_elt(&tmp4, k, stack);
996  field_elt_relax_pool_elt(&tmp5, k, stack);
997  field_elt_relax_pool_elt(&tmp6, k, stack);
998 }
999 
1000 void
1001 weierstrass_point_TPLU (ec_point_ptr P3, ec_point_ptr P4, ec_point_srcptr P1,
1002  ec_curve_srcptr E, uint8_t stack)
1003 {
1004  /* Those formulae are taken from [GJM10,§4.3] */
1005  weierstrass_point_DBLU(P3, P4, P1, E, stack);
1006  weierstrass_point_add_ZADDU(P3, P4, P3, E, stack);
1007 }
1008 
1019 void
1020 weierstrass_point_dbl_projective_dedicated (ec_point_ptr P3, ec_point_srcptr P1, ec_curve_srcptr E, uint8_t stack)
1021 {
1022  /* P1 = (X1, Y1, Z1) */
1023  /* P3 = (X3, Y3, Z3) */
1024  /* E: y^2 = x^3 + ax + b */
1025 
1026  field_t *k = E->k;
1027  field_elt tmp1, tmp2, tmp3, tmp4, tmp5;
1028 
1029  field_elt_get_pool_elt(&tmp1, k, stack);
1030  field_elt_get_pool_elt(&tmp2, k, stack);
1031  field_elt_get_pool_elt(&tmp3, k, stack);
1032  field_elt_get_pool_elt(&tmp4, k, stack);
1033  field_elt_get_pool_elt(&tmp5, k, stack);
1034 
1035  if(E->ec_spec1 == true)
1036  {
1037  /* To improve efficiency for NIST curve */
1038  /* Formula taken from [BL07] viewable here: http://www.hyperelliptic.org/EFD/g1p/auto-shortw-projective-3.html#doubling-dbl-2007-bl-2 */
1039  /* Costs 7M 3S 5add 4*2 1*3 */
1040 
1041  field_elt_sub(tmp1, P1->x, P1->z, k); /* tmp1 = X1 - Z1 */
1042  field_elt_add(tmp2, P1->x, P1->z, k); /* tmp2 = X1 + Z1 */
1043  field_elt_mul(tmp1, tmp1, tmp2, k, stack); /* tmp1 = (X1 - Z1).(X1 + Z1) */
1044  field_elt_mul3(tmp2, tmp1, k, stack); /* tmp2 = 3*(X1 - Z1).(X1 + Z1) = w */
1045 
1046  field_elt_mul(tmp1, P1->y, P1->z, k, stack); /* tmp1 = Y1.Z1 */
1047  field_elt_mul2(tmp1, tmp1, k); /* tmp1 = 2.Y1.Z1 = s */
1048 
1049  field_elt_mul(tmp3, P1->y, tmp1, k, stack); /* tmp3 = Y1.s = R */
1050  field_elt_mul(tmp4, P1->x, tmp3, k, stack); /* tmp4 = X1.R */
1051  field_elt_mul2(tmp4, tmp4, k); /* tmp4 = 2.X1.R = B */
1052 
1053  field_elt_sqr(P3->x, tmp2, k, stack); /* X3 = w^2 */
1054  field_elt_mul2(tmp5, tmp4, k);
1055  field_elt_sub(P3->x, P3->x, tmp5, k); /* X3 = w^2 - 2.B = h */
1056 
1057  field_elt_sub(P3->y, tmp4, P3->x, k); /* Y3 = B - h */
1058  field_elt_mul(P3->x, P3->x, tmp1, k, stack); /* X3 = h.s */
1059 
1060  field_elt_mul(P3->y, P3->y, tmp2, k, stack); /* Y3 = (B - h).w */
1061  field_elt_sqr(tmp2, tmp3, k, stack); /* tmp2 = R^2 */
1062  field_elt_mul2(tmp2, tmp2, k);
1063  field_elt_sub(P3->y, P3->y, tmp2, k); /* Y3 = (B - h).w - 2.R^2 */
1064 
1065  field_elt_sqr(P3->z, tmp1, k, stack); /* Z3 = s^2 */
1066  field_elt_mul(P3->z, P3->z, tmp1, k, stack); /* Z3 = s^3 */
1067  }
1068  else
1069  {
1070  /*Formula taken from [BL07] viewable here: http://www.hyperelliptic.org/EFD/g1p/auto-shortw-projective.html#doubling-dbl-2007-bl */
1071  /* Costs 5M 6 S 1*a 7 add 3*2 1*3 */
1072  field_elt_sqr(tmp1, P1->x, k, stack); /* tmp1 = X1^2 */
1073  field_elt_sqr(tmp2, P1->z, k, stack); /* tmp2 = Z1^2 */
1074  field_elt_mul(tmp2, tmp2, E->a, k, stack); /* tmp2 = a.Z1^2 */
1075  field_elt_mul3(tmp3, tmp1, k, stack); /* tmp3 = 3.X1^2 */
1076  field_elt_add(tmp2, tmp2, tmp3, k); /* tmp2 = a.Z1^2 + 3.X1^2 = w */
1077  field_elt_mul(P3->z, P1->y, P1->z, k, stack); /* Z3 = Y1.Z1 */
1078  field_elt_mul2(P3->z, P3->z, k); /* Z3 = 2.Y1.Z1 = s */
1079 
1080  field_elt_mul(tmp3, P1->y, P3->z, k, stack); /* tmp3 = Y1.s = R */
1081 
1082  field_elt_add(P3->y, P1->x, tmp3, k); /* Y3 = X1 + R */
1083  field_elt_sqr(P3->y, P3->y, k, stack); /* Y3 = (X1 + R)^2 */
1084  field_elt_sub(P3->y, P3->y, tmp1, k); /* Y3 = (X1 + R)^2 - X1^2 */
1085  field_elt_sqr(tmp1, tmp3, k, stack); /* tmp1 = R^2 */
1086  field_elt_sub(P3->y, P3->y, tmp1, k); /* Y3 = (X1 + R)^2 - X1^2 - R^2 = B */
1087 
1088  field_elt_sqr(P3->x, tmp2, k, stack); /* X3 = w^2 */
1089  field_elt_mul2(tmp3, P3->y, k);
1090  field_elt_sub(P3->x, P3->x, tmp3, k); /* X3 = w^2 - 2.B = h */
1091 
1092  field_elt_sub(P3->y, P3->y, P3->x, k); /* Y3 = B - h */
1093  field_elt_mul(P3->x, P3->x, P3->z, k, stack); /* X3 = h.s */
1094 
1095  field_elt_mul(P3->y, P3->y, tmp2, k, stack); /* Y3 = (B - h).w */
1096  field_elt_mul2(tmp3, tmp1, k);
1097  field_elt_sub(P3->y, P3->y, tmp3, k); /* Y3 = (B - h).w - 2.R^2 */
1098 
1099  field_elt_sqr(tmp1, P3->z, k, stack); /* tmp1 = s^2 */
1100  field_elt_mul(P3->z, P3->z, tmp1, k, stack); /* Z3 = s^3 */
1101  }
1102  field_elt_set_one(P3->t, k); /* T3 = 1 */
1103 
1104  field_elt_relax_pool_elt(&tmp1, k, stack);
1105  field_elt_relax_pool_elt(&tmp2, k, stack);
1106  field_elt_relax_pool_elt(&tmp3, k, stack);
1107  field_elt_relax_pool_elt(&tmp4, k, stack);
1108  field_elt_relax_pool_elt(&tmp5, k, stack);
1109 }
1110 
1120 void
1121 weierstrass_point_add_projective_dedicated (ec_point_ptr P3, ec_point_srcptr P1,
1122  ec_point_srcptr P2, ec_curve_srcptr E, uint8_t stack)
1123 {
1124  /* P1 = (X1, Y1, Z1) */
1125  /* P2 = (X2, Y2, Z2) */
1126  /* P3 = (X3, Y3, Z3) */
1127  /* E: y^2 = x^3 + ax + b */
1128 
1129  /* Formula taken from [CMO98, formula 3] viewable at this adress: http://www.hyperelliptic.org/EFD/g1p/auto-shortw-projective.html#addition-add-1998-cmo-2 */
1130  /* Cost 12 M 2 S 6 Add 1*2 */
1131 
1132  field_t *k = E->k;
1133  field_elt tmp1, tmp2, tmp3, tmp4, tmp5, tmp6;
1134 
1135  field_elt_get_pool_elt(&tmp1, k, stack);
1136  field_elt_get_pool_elt(&tmp2, k, stack);
1137  field_elt_get_pool_elt(&tmp3, k, stack);
1138  field_elt_get_pool_elt(&tmp4, k, stack);
1139  field_elt_get_pool_elt(&tmp5, k, stack);
1140  field_elt_get_pool_elt(&tmp6, k, stack);
1141 
1142  field_elt_mul(tmp1, P1->y, P2->z, k, stack); /* tmp1 = Y1 * Z2 */
1143  field_elt_mul(tmp2, P1->x, P2->z, k, stack); /* tmp2 = X1 * Z2 */
1144  field_elt_mul(tmp3, P1->z, P2->z, k, stack); /* tmp3 = Z1 * Z2 */
1145 
1146  field_elt_mul(tmp4, P2->y, P1->z, k, stack); /* tmp4 = Y2 * Z1 */
1147  field_elt_mul(tmp5, P2->x, P1->z, k, stack); /* tmp5 = X2 * Z1 */
1148 
1149  if(field_elt_cmp(tmp2, tmp5, k)==0)
1150  {
1151  /* Same x-coordinates (in affine) */
1152  if(field_elt_cmp(tmp1, tmp4, k)!=0)
1153  {
1154  /* Different y-coordinates (in affine) */
1155  weierstrass_point_set_neutral(P3, E, stack);
1156  }
1157  else
1158  {
1159  /* Same y-coordinates (in affine) */
1160  if(field_elt_iszero(P1->y, k))
1161  {
1162  /* y = 0 */
1163  weierstrass_point_set_neutral(P3, E, stack);
1164  }
1165  else
1166  {
1167  weierstrass_point_dbl_projective_dedicated(P3, P1, E, stack);
1168  }
1169  }
1170  }
1171  else
1172  {
1173  field_elt_sub(tmp4, tmp4, tmp1, k); /* tmp4 = (Y2 * Z1) - tmp1 = u */
1174  field_elt_sub(tmp5, tmp5, tmp2, k); /* tmp5 = (X2 * Z1) - tmp2 = v */
1175 
1176  field_elt_sqr(P3->x, tmp4, k, stack); /* X3 = u^2 */
1177  field_elt_mul(P3->x, P3->x, tmp3, k, stack); /* X3 = u^2*Z1Z2 */
1178  field_elt_sqr(P3->y, tmp5, k, stack); /* Y3 = v^2 */
1179  field_elt_mul(tmp6, P3->y, tmp5, k, stack); /* tmp6 = tmp5^3 = v^3 */
1180  field_elt_sub(P3->x, P3->x, tmp6, k); /* X3 = u^2*Z1Z2 - v^3 */
1181 
1182  field_elt_mul(P3->y, P3->y, tmp2, k, stack); /* Y3 = tmp5^2 * tmp2 = v^2*X1Z2 = R */
1183  field_elt_mul2(tmp2, P3->y, k);
1184  field_elt_sub(P3->x, P3->x, tmp2, k); /* X3 = u^2*Z1Z2 - v^3 - 2R = A */
1185 
1186  field_elt_sub(P3->y, P3->y, P3->x, k); /* Y3 = R - A */
1187  field_elt_mul(P3->x, P3->x, tmp5, k, stack); /* X3 = X3 * tmp5 = v * A */
1188 
1189  field_elt_mul(P3->z, tmp6, tmp3, k, stack); /* Z3 = tmp6 * tmp3 = v^3 * Z1Z2 */
1190 
1191  field_elt_mul(P3->y, P3->y, tmp4, k, stack); /* Y3 = (R - A) * u */
1192  field_elt_mul(tmp1, tmp1, tmp6, k, stack); /* tmp1 = Y1Z2 * v^3 */
1193  field_elt_sub(P3->y, P3->y, tmp1, k); /* Y3 = (R - A) * u - Y1Z2 * v^3 */
1194  }
1195  field_elt_set_one(P3->t, k); /* T3 = 1 */
1196 
1197  field_elt_relax_pool_elt(&tmp1, k, stack);
1198  field_elt_relax_pool_elt(&tmp2, k, stack);
1199  field_elt_relax_pool_elt(&tmp3, k, stack);
1200  field_elt_relax_pool_elt(&tmp4, k, stack);
1201  field_elt_relax_pool_elt(&tmp5, k, stack);
1202  field_elt_relax_pool_elt(&tmp6, k, stack);
1203 }
1204 
1214 void
1215 weierstrass_point_add_projective_unified (ec_point_ptr P3, ec_point_srcptr P1,
1216  ec_point_srcptr P2, ec_curve_srcptr E, uint8_t stack)
1217 {
1218  /* P1 = (X1, Y1, Z1) */
1219  /* P2 = (X2, Y2, Z2) */
1220  /* P3 = (X3, Y3, Z3) */
1221  /* E: y^2 = x^3 + ax + b */
1222 
1223  /* Formula taken from [add-2007-bl] viewable at this adress: http://www.hyperelliptic.org/EFD/g1p/data/shortw/projective/addition/add-2007-bl */
1224  /* Cost 11M + 6S + 1*a + 10add + 4*2 + 1*4 */
1225 
1226  field_t *k = E->k;
1227  field_elt U1, U2, S1, S2, ZZ, T, TT, M, R, F, L, LL, G, W;
1228  field_elt t0, t1, t2, t3;
1229 
1230  field_elt_get_pool_elt(&U1, k, stack);
1231  field_elt_get_pool_elt(&U2, k, stack);
1232  field_elt_get_pool_elt(&S1, k, stack);
1233  field_elt_get_pool_elt(&S2, k, stack);
1234  field_elt_get_pool_elt(&ZZ, k, stack);
1235  field_elt_get_pool_elt(&T, k, stack);
1236  field_elt_get_pool_elt(&TT, k, stack);
1237  field_elt_get_pool_elt(&M, k, stack);
1238  field_elt_get_pool_elt(&R, k, stack);
1239  field_elt_get_pool_elt(&F, k, stack);
1240  field_elt_get_pool_elt(&L, k, stack);
1241  field_elt_get_pool_elt(&LL, k, stack);
1242  field_elt_get_pool_elt(&G, k, stack);
1243  field_elt_get_pool_elt(&W, k, stack);
1244 
1245  field_elt_get_pool_elt(&t0, k, stack);
1246  field_elt_get_pool_elt(&t1, k, stack);
1247  field_elt_get_pool_elt(&t2, k, stack);
1248  field_elt_get_pool_elt(&t3, k, stack);
1249 
1250  field_elt_mul(U1, P1->x, P2->z, k, stack); /* U1 = X1*Z2 */
1251  field_elt_mul(U2, P2->x, P1->z, k, stack); /* U2 = X2*Z1 */
1252  field_elt_mul(S1, P1->y, P2->z, k, stack); /* S1 = Y1*Z2 */
1253  field_elt_mul(S2, P2->y, P1->z, k, stack); /* S2 = Y2*Z1 */
1254 
1255  if(field_elt_cmp(U1, U2, k)==0)
1256  {
1257  /* Same x-coordinates (in affine) */
1258  if(field_elt_cmp(S1, S2, k)!=0)
1259  {
1260  /* Different y-coordinates (in affine) */
1261  weierstrass_point_set_neutral(P3, E, stack);
1262  return;
1263  }
1264  else
1265  {
1266  /* Same y-coordinates (in affine) */
1267  if(field_elt_iszero(P1->y, k))
1268  {
1269  weierstrass_point_set_neutral(P3, E, stack);
1270  return;
1271  }
1272  }
1273  }
1274 
1275  field_elt_mul(ZZ, P1->z, P2->z, k, stack); /* ZZ = Z1*Z2 */
1276  field_elt_add(T, U1, U2, k); /* T = U1+U2 */
1277  field_elt_sqr(TT, T, k, stack); /* TT = T2 */
1278  field_elt_add(M, S1, S2, k); /* M = S1+S2 */
1279  field_elt_sqr(t0, ZZ, k, stack); /* t0 = ZZ^2 */
1280  field_elt_mul(t1, E->a, t0, k, stack); /* t1 = a*t0 */
1281  field_elt_mul(t2, U1, U2, k, stack); /* t2 = U1*U2 */
1282  field_elt_sub(t3, TT, t2, k); /* t3 = TT-t2 */
1283  field_elt_add(R, t3, t1, k); /* R = t3+t1 */
1284  field_elt_mul(F, ZZ, M, k, stack); /* F = ZZ*M */
1285  field_elt_mul(L, M, F, k, stack); /* L = M*F */
1286  field_elt_sqr(LL, L, k, stack); /* LL = L^2 */
1287  field_elt_add(t0, T, L, k); /* t0 = T+L */
1288  field_elt_sqr(t1, t0, k, stack); /* t1 = t0^2 */
1289  field_elt_sub(t2, t1, TT, k); /* t2 = t1-TT */
1290  field_elt_sub(G, t2, LL, k); /* G = t2-LL */
1291  field_elt_sqr(t3, R, k, stack); /* t3 = R^2 */
1292  field_elt_mul2(t0, t3, k); /* t0 = 2*t3 */
1293  field_elt_sub(W, t0, G, k); /* W = t0-G */
1294  field_elt_mul(t1, F, W, k, stack); /* t1 = F*W */
1295  field_elt_mul2(P3->x, t1, k); /* X3 = 2*t1 */
1296  field_elt_mul2(t2, W, k); /* t2 = 2*W */
1297  field_elt_sub(t3, G, t2, k); /* t3 = G-t2 */
1298  field_elt_mul2(t0, LL, k); /* t0 = 2*LL */
1299  field_elt_mul(t1, R, t3, k, stack); /* t1 = R*t3 */
1300  field_elt_sub(P3->y, t1, t0, k); /* Y3 = t1-t0 */
1301  field_elt_sqr(t2, F, k, stack); /* t2 = F^2 */
1302  field_elt_mul(t3, F, t2, k, stack); /* t3 = F*t2 */
1303  field_elt_mul4(P3->z, t3, k); /* Z3 = 4*t3 */
1304 
1305  field_elt_set_one(P3->t, k); /* T3 = 1 */
1306 
1307  field_elt_relax_pool_elt(&U1, k, stack);
1308  field_elt_relax_pool_elt(&U2, k, stack);
1309  field_elt_relax_pool_elt(&S1, k, stack);
1310  field_elt_relax_pool_elt(&S2, k, stack);
1311  field_elt_relax_pool_elt(&ZZ, k, stack);
1312  field_elt_relax_pool_elt(&T, k, stack);
1313  field_elt_relax_pool_elt(&TT, k, stack);
1314  field_elt_relax_pool_elt(&M, k, stack);
1315  field_elt_relax_pool_elt(&R, k, stack);
1316  field_elt_relax_pool_elt(&F, k, stack);
1317  field_elt_relax_pool_elt(&L, k, stack);
1318  field_elt_relax_pool_elt(&LL, k, stack);
1319  field_elt_relax_pool_elt(&G, k, stack);
1320  field_elt_relax_pool_elt(&W, k, stack);
1321 
1322  field_elt_relax_pool_elt(&t0, k, stack);
1323  field_elt_relax_pool_elt(&t1, k, stack);
1324  field_elt_relax_pool_elt(&t2, k, stack);
1325  field_elt_relax_pool_elt(&t3, k, stack);
1326 }
1327 
1338 void
1339 weierstrass_point_dbl_jacobian_dedicated (ec_point_ptr P3, ec_point_srcptr P1, ec_curve_srcptr E, uint8_t stack)
1340 {
1341  /* P1 = (X1, Y1, Z1) */
1342  /* P3 = (X3, Y3, Z3) */
1343  /* E: y^2 = x^3 + ax + b */
1344 
1345  /* Formulae adapted from the formulae used by Intel IPPCP */
1346  /* Costs 5 M 3 S 5 Add 4*2 1*3 when E->a == -3 mod p */
1347  /* Costs 7 M 3 S 4 Add 4*2 1*3 when E->a != -3 mod p */
1348 
1349  field_t *k = E->k;
1350 
1351  field_elt S, U, M;
1352  field_elt_get_pool_elt(&S, k, stack);
1353  field_elt_get_pool_elt(&U, k, stack);
1354  field_elt_get_pool_elt(&M, k, stack);
1355 
1356  field_elt_mul2(S, P1->y, k); /* S = 2*Y */
1357  field_elt_sqr(U, P1->z, k, stack); /* U = Z^2 */
1358 
1359  field_elt_mul(M, S, P1->y, k, stack); /* M = 2*Y^2 */
1360  field_elt_mul(P3->z, S, P1->z, k, stack); /* Z3 = 2*Y*Z */
1361 
1362  field_elt_sqr(P3->y, M, k, stack); /* Y3 = 4*Y^4 */
1363  field_elt_mul2(P3->y, P3->y, k); /* Y3 = 8*Y^4 */
1364 
1365  field_elt_mul(S, M, P1->x, k, stack); /* S = 2*X*Y^2 */
1366  field_elt_mul2(S, S, k); /* S = 4*X*Y^2 */
1367 
1368  if(E->ec_spec1 == true)
1369  {
1370  field_elt_add(M, P1->x, U, k); /* M = 3*(X^2-Z^4) */
1371  field_elt_sub(U, P1->x, U, k);
1372  field_elt_mul(M, M, U, k, stack);
1373  field_elt_mul3(M, M, k, stack);
1374  }
1375  else
1376  {
1377  field_elt_sqr(M, P1->x, k, stack); /* M = 3*X^2 */
1378  field_elt_mul3(M, M, k, stack);
1379  field_elt_sqr(U, U, k, stack); /* M = 3*X^2+a*Z^4 */
1380  field_elt_mul(U, U, E->a, k, stack);
1381  field_elt_add(M, M, U, k);
1382  }
1383 
1384  field_elt_mul2(U, S, k); /* U = 8*X*Y^2 */
1385  field_elt_sqr(P3->x, M, k, stack); /* X3 = M^2 */
1386  field_elt_sub(P3->x, P3->x, U, k); /* X3 = M^2 - U */
1387 
1388  field_elt_sub(S, S, P3->x, k); /* S = 4*X*Y^2-X3 */
1389  field_elt_mul(S, S, M, k, stack); /* S = M*(4*X*Y^2-X3) */
1390  field_elt_sub(P3->y, S, P3->y, k); /* Y3 = M*(4*X*Y^2-X3) - 8*Y^4 */
1391 
1392  field_elt_set_one(P3->t, k); /* T3 = 1 */
1393 
1394  field_elt_relax_pool_elt(&S, k, stack);
1395  field_elt_relax_pool_elt(&U, k, stack);
1396  field_elt_relax_pool_elt(&M, k, stack);
1397 }
1398 
1408 void
1409 weierstrass_point_add_jacobian_dedicated (ec_point_ptr P3, ec_point_srcptr P1, ec_point_srcptr P2, ec_curve_srcptr E, uint8_t stack)
1410 {
1411  /* P1 = (X1, Y1, Z1) */
1412  /* P2 = (X2, Y2, Z2) */
1413  /* P3 = (X3, Y3, Z3) */
1414  /* E: y^2 = x^3 + ax + b */
1415 
1416  /* Formulae adapted from the formulae used by Intel IPPCP */
1417  /* Costs 12 M 4 S 6 Add 1*2 */
1418 
1419  field_t *k = E->k;
1420  field_elt U1, U2, S1, S2, H, R;
1421  field_elt_get_pool_elt(&U1, k, stack);
1422  field_elt_get_pool_elt(&U2, k, stack);
1423  field_elt_get_pool_elt(&S1, k, stack);
1424  field_elt_get_pool_elt(&S2, k, stack);
1425  field_elt_get_pool_elt(&H, k, stack);
1426  field_elt_get_pool_elt(&R, k, stack);
1427 
1428  field_elt_mul(S1, P1->y, P2->z, k, stack); /* S1 = Y1*Z2 */
1429  field_elt_sqr(U1, P2->z, k, stack); /* U1 = Z2^2 */
1430 
1431  field_elt_mul(S2, P2->y, P1->z, k, stack); /* S2 = Y2*Z1 */
1432  field_elt_sqr(U2, P1->z, k, stack); /* U2 = Z1^2 */
1433 
1434  field_elt_mul(S1, S1, U1, k, stack); /* S1 = Y1*Z2^3 */
1435  field_elt_mul(S2, S2, U2, k, stack); /* S2 = Y2*Z1^3 */
1436 
1437  field_elt_mul(U1, P1->x, U1, k, stack); /* U1 = X1*Z2^2 */
1438  field_elt_mul(U2, P2->x, U2, k, stack); /* U2 = X2*Z1^2 */
1439 
1440  field_elt_sub(R, S2, S1, k); /* R = S2 - S1 */
1441  field_elt_sub(H, U2, U1, k); /* H = U2 - U1 */
1442 
1443  if(field_elt_iszero(H, k))
1444  {
1445  /* Same x-coordinates (in affine) */
1446  if(!field_elt_iszero(R, k))
1447  {
1448  /* Different y-coordinates (in affine) */
1449  weierstrass_point_set_neutral(P3, E, stack);
1450  }
1451  else
1452  {
1453  /* Same y-coordinates (in affine) */
1454  if(field_elt_iszero(P1->y, k))
1455  {
1456  /* y = 0 */
1457  weierstrass_point_set_neutral(P3, E, stack);
1458  }
1459  else
1460  {
1461  weierstrass_point_dbl_jacobian_dedicated(P3, P1, E, stack);
1462  }
1463  }
1464  }
1465  else
1466  {
1467  field_elt_mul(P3->z, P1->z, P2->z, k, stack); /* Z3 = Z1*Z2 */
1468  field_elt_sqr(U2, H, k, stack); /* U2 = H^2 */
1469  field_elt_mul(P3->z, P3->z, H, k, stack); /* Z3 = (Z1*Z2)*H */
1470  field_elt_sqr(S2, R, k, stack); /* S2 = R^2 */
1471  field_elt_mul(H, H, U2, k, stack); /* H = H^3 */
1472 
1473  field_elt_mul(U1, U1, U2, k, stack); /* U1 = U1*H^2 */
1474  field_elt_sub(P3->x, S2, H, k); /* X3 = R^2 - H^3 */
1475  field_elt_mul2(U2, U1, k); /* U2 = 2*U1*H^2 */
1476  field_elt_mul(S1, S1, H, k, stack); /* S1 = S1*H^3 */
1477  field_elt_sub(P3->x, P3->x, U2, k); /* X3 = (R^2 - H^3) - 2*U1*H^2 */
1478 
1479  field_elt_sub(P3->y, U1, P3->x, k); /* Y3 = R*(U1*H^2 - X3) - S1*H^3 */
1480  field_elt_mul(P3->y, P3->y, R, k, stack);
1481  field_elt_sub(P3->y, P3->y, S1, k);
1482  field_elt_set_one(P3->t, k); /* T3 = 1 */
1483  }
1484 
1485  field_elt_relax_pool_elt(&U1, k, stack);
1486  field_elt_relax_pool_elt(&U2, k, stack);
1487  field_elt_relax_pool_elt(&S1, k, stack);
1488  field_elt_relax_pool_elt(&S2, k, stack);
1489  field_elt_relax_pool_elt(&H, k, stack);
1490  field_elt_relax_pool_elt(&R, k, stack);
1491 }
1492 
1495 void
1496 weierstrass_Zmontgomery_ladder(ec_point_ptr P3, number_srcptr n, ec_point_srcptr P1,
1497  ec_curve_srcptr E, uint8_t stack)
1498 {
1499  /* The Montgomery ladder permits to have at each ladder R0-R1=+/-P,
1500  * therefore if we want to avoid to have in input of ZADDU with z
1501  * coordinate=0 we must avoid that R0=R1 or R0=-R1 in input of ZADDC
1502  * we have to solve the following equation +/-[k]P = [k +/-1] P
1503  * which simplifies to 2k = +/-1 mod p with p the order of P
1504  * Therefore we obtain that the case k = p-1/2 must be avoided
1505  * which forbids the input n=p-1 for this function.
1506  */
1507  ec_point_set_neutral(P3, E, stack);
1508  if(!number_iszero(n))
1509  {
1510  field_t *k = E->k;
1511  ec_point R0, R1;
1512  ec_point_get_pool_elt(R0, k, stack);
1513  ec_point_get_pool_elt(R1, k, stack);
1514 
1515  ec_point_copy(R0, P1, k);
1516  weierstrass_point_DBLU(R1, R0, R0, E, stack);
1517  char n_str[k->bit_size+4];
1518  number_to_bit_string(n_str, n);
1519 
1520  uint32_t i;
1521 
1522  for(i = 1; i < strlen(n_str); i++)
1523  {
1524  if(n_str[i] == '0')
1525  {
1526  weierstrass_point_add_ZADDC(R1, R0, R0, R1, E, stack);
1527  weierstrass_point_add_ZADDU(R0, R1, R0, E, stack);
1528  }
1529  else
1530  {
1531  weierstrass_point_add_ZADDC(R0, R1, R1, R0, E, stack);
1532  weierstrass_point_add_ZADDU(R1, R0, R1, E, stack);
1533  }
1534  }
1535 
1536  ec_point_copy(P3, R0, k);
1537  ec_point_relax_pool_elt(R0, k, stack);
1538  ec_point_relax_pool_elt(R1, k, stack);
1539  }
1540 }
1541 
1542 
1543 void setup_Kim(fe_ptr X1, fe_ptr X2, fe_ptr K, fe_ptr L, fe_ptr A, fe_ptr S, fe_ptr T, fe_srcptr x0, fe_srcptr y0, bool bit, ec_curve_srcptr E, uint8_t stack)
1544 {
1545  /* From the work Speeding up Elliptic Curve Scalar Multiplication without Precomputation by Kim, Choe, Kim, Kim and Hong 2017 */
1546  /* Section 4 algorithm setup*/
1547  /* Costs 8M + 7S + 15A */
1548 
1549  field_t *k = E->k;
1550  field_elt T7;
1551  field_elt_get_pool_elt(&T7, k, stack);
1552 
1553  field_elt_random(K,k,stack);
1554  while(field_elt_iszero(K,k))
1555  {
1556  field_elt_random(K,k,stack);
1557  }
1558  field_elt_sqr(L ,K, k, stack); /* T3 = T2^2 = Z^2 */
1559  field_elt_mul(A, x0, L, k, stack); /* T4 = x0*T3 = x0*Z^2 */
1560  field_elt_mul(S, y0, L, k, stack); /* T5 = y0*T3 = y0*Z^2 */
1561  field_elt_mul(X2, S, K, k, stack); /* T1 = T5*T2 = y0*Z^3 */
1562  field_elt_sqr(T7 ,X2, k, stack); /* T7 = T1^2 = y0^2*Z^6 */
1563  field_elt_mul(X1, A, T7, k, stack); /* T0 = T4*T7 = x0*y0^2*Z^8 */
1564  field_elt_mul2(X1, X1, k);
1565  field_elt_mul2(X1, X1, k); /* T0 = 4*T0 = 4*x0*y0^2*Z^8 = X1 =S */
1566  field_elt_sqr(T, T7, k, stack); /* T6 = T7^2 = y0^4*Z^12 */
1567  field_elt_mul2(T, T, k);
1568  field_elt_mul2(T, T, k);
1569  field_elt_mul2(T, T, k); /* T6 = 8*T6 = 8*y0^4*Z^12= N^~ =T */
1570  field_elt_sqr(S, A, k, stack); /* T5 = T4^2 = x0^2*Z^4 */
1571  field_elt_mul2(A, S, k);
1572  field_elt_add(A, A, S, k); /* T4 = 3*T5 = 3*x0^2*Z^4 */
1573  field_elt_sqr(S, L, k, stack); /* T5 = T3^2 = Z^4 */
1574  field_elt_mul(T7, S, E->a, k, stack); /* T7 = T5*a = a*Z^4 */
1575  field_elt_add(T7, A, T7, k); /* T7 = T4 + T7 = 3*x0^2*Z^4 + a*Z^4 */
1576  field_elt_sqr(X2, T7, k, stack); /* T1 = T7^2 = (3*x0^2*Z^4 + a*Z^4)^2 */
1577  field_elt_sub(X2, X2, X1, k); /* T1 = T1-T0=(3*x0^2*Z^4 + a*Z^4)^2-X1 */
1578  field_elt_sub(X2, X2, X1, k); /* T1 = T1-T0=(3*x0^2*Z^4 + a*Z^4)^2-2X1 = X2 */
1579  field_elt_sub(K, X1, X2, k); /* T2 = T0-T1= X1 -X2 */
1580  field_elt_mul(A, T7, K, k, stack); /* T4 = T7*T2 = (3*x0^2*Z^4 + a*Z^4)(X1-X2) */
1581  field_elt_sub(S, T, A, k); /* T5 = T6 - T4 = N */
1582  field_elt_mul(L, S, T, k, stack); /* T3 = T5+*T6 = N * N^~ */
1583  field_elt_mul2(L, L, k); /* T3 = 2*N * N^~ = L */
1584  if(bit)
1585  {
1586  field_elt_mul(A, S, K, k, stack); /* T4 = (X1-X2)*N */
1587  }
1588  else
1589  {
1590  field_elt_mul(A, T, K, k, stack); /* T4 = N^~(X1-X2) */
1591  }
1592  field_elt_mul2(A, A, k); /* T4 = A = 2(X1-X2)*N / 2 N^~(X1-X2) */
1593  if(bit)
1594  {
1595  field_elt_sqr(K, S, k, stack); /* K = T5^2 = N^2 */
1596  }
1597  else
1598  {
1599  field_elt_sqr(K, T, k, stack); /* T2 = T6^2 =N^~^2 */
1600  }
1601  field_elt_mul2(K, K ,k); /* T2 = K */
1602 
1603  field_elt_copy(S ,X1 ,k);
1604 
1605  field_elt_relax_pool_elt(&T7, k, stack);
1606 }
1607 
1608 void update_Kim(fe_ptr X1, fe_ptr X2, fe_ptr K, fe_ptr L, fe_ptr A, fe_ptr S, fe_ptr T, bool prev, bool new, ec_curve_srcptr E, uint8_t stack)
1609 {
1610  /* From the work Speeding up Elliptic Curve Scalar Multiplication without Precomputation by Kim, Choe, Kim, Kim and Hong 2017 */
1611  /* Algorithm from section 4 8M +4S +15.5A */
1612  field_t *k = E->k;
1613  field_elt T7;
1614  field_elt_get_pool_elt(&T7, k, stack);
1615 
1616  if(prev)
1617  {
1618  /* We work like if u=1 in the formula of section 4 */
1619 
1620  field_elt_sub(X1, X2, X1, k); /* T0 = T1-T0 */
1621  field_elt_sub(X2, S, X2, k); /* T1 = T5-T1 */
1622  field_elt_sqr(T7, X1, k, stack); /* T7 = T0^2 */
1623  field_elt_mul(X1, X2, T7, k, stack); /* T0 = T1*T7 */
1624  field_elt_sqr(X2, A, k, stack); /* T1 = T4^2 */
1625  field_elt_mul(T7, X2, S, k, stack); /* T7 = T1*T5 */
1626  field_elt_copy(S, T7, k); /* T5 = T7 */
1627  field_elt_mul(T7, A, T, k, stack); /* T7 = T4*T6 */
1628  field_elt_mul(T, X2, T7, k, stack); /* T6 = T1*T7 */
1629  field_elt_mul(A, K, L, k, stack); /* T4 = T2*T3 */
1630  field_elt_add(K, K, L, k); /* T2 = T2+T3 */
1631  field_elt_add(L, X1, K, k); /* T3 = T0+T2 */
1632  field_elt_mul2(A, A, k);
1633  field_elt_mul2(A, A, k); /* T4 = 4*T4 */
1634  field_elt_add(X1, A, S, k); /* T0 = T4+T5 */
1635  field_elt_sqr(A, L, k, stack); /* T4 = T3^2 */
1636  field_elt_sub(A, A, S, k); /* T4 = T4 - T5 */
1637  field_elt_sub(X2, A, X1, k); /* T1 = T4 - T0 */
1638  if(new) /* v = 1 */
1639  {
1640  field_elt_sub(A, X2, S, k); /* T4 = T1 -T5 */
1641  }
1642  else
1643  {
1644  field_elt_sub(A, X1, S, k); /* T4 = T0 - T5 */
1645  }
1646  field_elt_sub(T7, X2, X1, k); /* T7 = T1 - T0 */
1647  field_elt_mul(K, L, A, k, stack); /* T2 = T3 * T4 */
1648  field_elt_sub(K, K, T, k); /* T2 = T2 - T6 */
1649  field_elt_mul(A, K, T7, k, stack); /* T4 = T2 * T7 */
1650  field_elt_mul2(A, A, k); /* T4 = 2*T4 */
1651  field_elt_sqr(T7, K, k, stack); /* T7 = T2^2 */
1652  field_elt_mul2(K, T7, k); /* T2 = 2*T7 */
1653  field_elt_mul(T7, L, A, k, stack); /* T7 = T3 * T4 */
1654  field_elt_neg(L, T7, k); /* T3 =-T7 */
1655  if(!new)
1656  {
1657  field_elt_sub(L, K, L, k);
1658  }
1659  else
1660  {
1661  field_elt_sub(L, K, T7, k);
1662  }
1663  }
1664  else
1665  {
1666  /* We work like if u=0 in the formula of section 4*/
1667 
1668  field_elt_sub(X2, X1, X2, k); /* T1 = T0-T1 */
1669  field_elt_sub(X1, S, X1, k); /* T0 = T5-T0 */
1670  field_elt_sqr(T7, X2, k, stack); /* T7 = T1^2 */
1671  field_elt_mul(X2, X1, T7, k, stack); /* T1 = T0*T7 */
1672  field_elt_sqr(X1, A, k, stack); /* T0 = T4^2 */
1673  field_elt_mul(T7, X1, S, k, stack); /* T7 = T0*T5 */
1674  field_elt_copy(S, T7, k); /* T5 = T7 */
1675  field_elt_mul(T7, A, T, k, stack); /* T7 = T4*T6 */
1676  field_elt_mul(T, X1, T7, k, stack); /* T6 = T0*T7 */
1677  field_elt_mul(A, K, L, k, stack); /* T4 = T2*T3 */
1678  field_elt_add(K, K, L, k); /* T2 = T2+T3 */
1679  field_elt_add(L, X2, K, k); /* T3 = T1*T2 */
1680  field_elt_mul2(A, A, k);
1681  field_elt_mul2(A, A, k); /* T4 = 4*T4 */
1682  field_elt_add(X2, A, S, k); /* T1 = T4+T5 */
1683  field_elt_sqr(A, L, k, stack); /* T4 = T3^2 */
1684  field_elt_sub(A, A, S, k); /* T4 = T4 - T5 */
1685  field_elt_sub(X1, A, X2, k); /* T0 = T4 - T1 */
1686  if(new) /* v = 1 */
1687  {
1688  field_elt_sub(A, S, X2, k); /* T4 = T5 -T1 */
1689  }
1690  else
1691  {
1692  field_elt_sub(A, S, X1, k); /* T4 = T5 - T0 */
1693  }
1694  field_elt_sub(T7, X2, X1, k); /* T7 = T1 - T0 */
1695  field_elt_mul(K, L, A, k, stack); /* T2 = T3 * T4 */
1696  field_elt_sub(K, K, T, k); /* T2 = T2 - T6 */
1697  field_elt_mul(A, K, T7, k, stack); /* T4 = T2 * T7 */
1698  field_elt_mul2(A, A, k); /* T4 = 2*T4 */
1699  field_elt_sqr(T7, K, k, stack); /* T7 = T2^2 */
1700  field_elt_mul2(K, T7, k); /* T2 = 2*T7 */
1701  field_elt_mul(T7, L, A, k, stack); /* T7 = T3 * T4 */
1702  field_elt_neg(L, T7, k); /* T3 =-T7 */
1703  if(new)
1704  {
1705  field_elt_sub(L, K, L, k);
1706  }
1707  else
1708  {
1709  field_elt_sub(L, K, T7, k);
1710  }
1711  }
1712 
1713  field_elt_relax_pool_elt(&T7, k, stack);
1714 }
1715 
1716 void recovery_Kim(fe_ptr P3x, fe_ptr P3y, fe_ptr X1, fe_ptr X2, fe_ptr K, fe_ptr L, fe_ptr A, fe_ptr S, fe_ptr T, fe_srcptr x0, fe_srcptr y0, field_ptr k, bool safe, uint8_t stack)
1717 {
1718  /* From the work Speeding up Elliptic Curve Scalar Multiplication without Precomputation by Kim, Choe, Kim, Kim and Hong 2017*/
1719  /* Algorithm from section 4 costs M + S + A */
1720  field_elt T7;
1721  field_elt_get_pool_elt(&T7, k, stack);
1722 
1723 
1724  field_elt_sub(X2, X1, X2, k); /* T1 = T0 - T1 = X1-X2 */
1725  field_elt_mul(K, L, X2, k, stack); /* T2 = T3 * T1 = K * (X1-X2) */
1726  field_elt_mul(T7, A, T, k, stack); /* T7 = T4 * T6 = A * T */
1727  field_elt_mul(T, T7, S, k, stack); /* T6 = T7 * T5 = A * T *S */
1728 
1729  if(safe)
1730  {
1731  /* FLT */
1732  number tmp; number_tmp_alloc(&tmp, k->size, stack);
1733  field_get_size(tmp,k);
1734  number_dec(tmp, tmp);
1735  number_dec(tmp, tmp);
1736  field_elt_pow_number(X2, T, tmp, k, stack);
1737  number_tmp_free(&tmp, k->size, stack);
1738  }
1739  else
1740  {
1741  field_elt_inv(X2, T, k, stack); /* T1 = 1 / T6 = 1 /(A*T*S) */
1742  }
1743  field_elt_mul(L, X2, T7, k, stack); /* T3 = T1 * T7 = (1)/(S) */
1744  field_elt_mul(T7, L, X1, k, stack); /* T7 = T3 * T0 = X1/(S) */
1745  field_elt_mul(X1, T7, x0, k, stack); /* T0 = T7 * x0 = x0X1/(S) */
1746  field_elt_mul(A, S, X2, k, stack); /* T4 = T5 * T1 = 1/(A*T) */
1747  field_elt_mul(L, A, K, k, stack); /* T3 = T4 * T2 = K(X1-X2)/(AT) */
1748  field_elt_mul(X2, L, y0, k, stack); /* T1 = T3 * y0 = y0K(X1-X2)/(AT) */
1749 
1750  field_elt_copy(P3x, X1, k);
1751  field_elt_copy(P3y, X2, k);
1752 
1753  field_elt_relax_pool_elt(&T7, k, stack);
1754 }
1755 
1756 void
1757 weierstrass_Zmontgomery_Kim(ec_point_ptr P3, number_srcptr n, ec_point_srcptr P1,
1758  ec_curve_srcptr E, uint8_t stack)
1759 {
1760  /* From the work Speeding up Elliptic Curve Scalar Multiplication without Precomputation by Kim, Choe, Kim, Kim and Hong 2017*/
1761  /* As in weierstrass_Zmontgomery_ladder
1762  * The Montgomery ladder permits to have at each ladder R0-R1=+/-P,
1763  * therefore if we want to avoid to have in input of ZADDU with z
1764  * coordinate=0 we must avoid that R0=R1 or R0=-R1 in input of ZADDC
1765  * we have to solve the following equation +/-[k]P = [k +/-1] P
1766  * which simplifies to 2k = +/-1 mod p with p the order of P
1767  * Therefore we obtain that the case k = p-1/2 must be avoided
1768  * which forbids the input n=p-1 for this function.
1769  * In addition here it is not permitted to obtain a final result of the
1770  * neutral point since recovery_Kim will divide the values by the
1771  * Z-coordinate (equals to 0 in neutral point)
1772  */
1773  /* Algorithm 2 section 4*/
1774  ec_point_set_neutral(P3, E, stack);
1775  if(!number_iszero(n))
1776  {
1777  field_t *k = E->k;
1778  field_elt X1, X2, K, L, A, S, T;
1779  field_elt_get_pool_elt(&X1, k, stack);
1780  field_elt_get_pool_elt(&X2, k, stack);
1781  field_elt_get_pool_elt(&K, k, stack);
1782  field_elt_get_pool_elt(&L, k, stack);
1783  field_elt_get_pool_elt(&A, k, stack);
1784  field_elt_get_pool_elt(&S, k, stack);
1785  field_elt_get_pool_elt(&T, k, stack);
1786 
1787  char n_str[k->bit_size+4];
1788  number_to_bit_string(n_str, n);
1789 
1790  setup_Kim(X1, X2, K, L, A, S, T, P1->x, P1->y, n_str[1]=='1', E, stack);
1791 
1792  uint32_t i;
1793  //printf("\nstrlen(n_str):%ld\n", strlen(n_str));
1794  for(i = 1; i < strlen(n_str)-1; i++)
1795  {
1796  if(n_str[i] == '0')
1797  {
1798  if(n_str[i+1]== '0')
1799  {
1800  update_Kim(X1, X2, K, L, A, S, T, false, false, E, stack);
1801  }
1802  else
1803  {
1804  update_Kim(X1, X2, K, L, A, S, T, false, true, E, stack);
1805  }
1806  }
1807  else
1808  {
1809  if(n_str[i+1]== '0')
1810  {
1811  update_Kim(X1, X2, K, L, A, S, T, true, false, E, stack);
1812  }
1813  else
1814  {
1815  update_Kim(X1, X2, K, L, A, S, T, true, true, E, stack);
1816  }
1817  }
1818  }
1819  if(n_str[strlen(n_str)-1]=='0')
1820  {
1821  update_Kim(X1, X2, K, L, A, S, T, false, true, E, stack);
1822  }
1823  else
1824  {
1825  update_Kim(X1, X2, K, L, A, S, T, true, true, E, stack);
1826  }
1827 
1828  recovery_Kim(P3->x, P3->y, X1, X2, K, L, A, S, T, P1->x, P1->y, E->k,false, stack);
1829  field_elt_set_one(P3->z, k);
1830 
1831  field_elt_relax_pool_elt(&X1, k, stack);
1832  field_elt_relax_pool_elt(&X1, k, stack);
1833  field_elt_relax_pool_elt(&K, k, stack);
1834  field_elt_relax_pool_elt(&L, k, stack);
1835  field_elt_relax_pool_elt(&A, k, stack);
1836  field_elt_relax_pool_elt(&S, k, stack);
1837  field_elt_relax_pool_elt(&T, k, stack);
1838  }
1839 }
1840 
1841 
1842 void
1843 weierstrass_Zjoye_mul(ec_point_ptr P3, number_srcptr n, ec_point_srcptr P1,
1844  ec_curve_srcptr E, uint8_t stack)
1845 {
1846  ec_point_set_neutral(P3, E, stack);
1847  if(!number_iszero(n))
1848  {
1849  /* From Co-Z Addition Formulæ and Binary Ladders on Elliptic Curves, algorithm 10 */
1850  field_t *k = E->k;
1851  ec_point R0, R1;
1852  ec_point_get_pool_elt(R0, k, stack);
1853  ec_point_get_pool_elt(R1, k, stack);
1854 
1855  int32_t i;
1856  char n_str[k->bit_size+4];
1857  number_to_bit_string(n_str, n);
1858 
1859  if(n_str[strlen(n_str)-1] == '1')
1860  {
1861  if(n_str[strlen(n_str)-2] == '0')
1862  {
1863  ec_point_copy(R0, P1, k);
1864  weierstrass_point_TPLU(R1, R0, R0, E, stack);
1865  }
1866  else
1867  {
1868  ec_point_copy(R1, P1, k);
1869  weierstrass_point_TPLU(R0, R1, R1, E, stack);
1870  }
1871 
1872  for(i = strlen(n_str) - 3; i >=0; i--)
1873  {
1874  if(n_str[i] == '0')
1875  {
1876  weierstrass_point_add_ZDAU(R1, R1, R0, E, stack);
1877  }
1878  else
1879  {
1880  weierstrass_point_add_ZDAU(R0, R0, R1, E, stack);
1881  }
1882  }
1883  ec_point_copy(P3, R0, k);
1884  }
1885  else
1886  {
1887  if(n_str[strlen(n_str)-2] == '0')
1888  {
1889  ec_point_copy(R0, P1, k);
1890  weierstrass_point_TPLU(R1, R0, R0, E, stack);
1891  }
1892  else
1893  {
1894  ec_point_copy(R1, P1, k);
1895  weierstrass_point_TPLU(R0, R1, R1, E, stack);
1896  }
1897 
1898  for(i = strlen(n_str) - 3; i >=0; i--)
1899  {
1900  if(n_str[i] == '0')
1901  {
1902  weierstrass_point_add_ZDAU(R1, R1, R0, E, stack);
1903  }
1904  else
1905  {
1906  weierstrass_point_add_ZDAU(R0, R0, R1, E, stack);
1907  }
1908  }
1909  /* Remove 1 x P1 that we add */
1910  weierstrass_point_neg(R1, P1, E);
1911  weierstrass_point_add_jacobian_dedicated(P3, R0, R1, E, stack);
1912  }
1913  ec_point_relax_pool_elt(R0, k, stack);
1914  ec_point_relax_pool_elt(R1, k, stack);
1915  }
1916 }
1917 
1920 void
1921 weierstrass_point_add_dedicated (ec_point_ptr P3, ec_point_srcptr P1, ec_point_srcptr P2,
1922  ec_curve_srcptr E, uint8_t stack)
1923 {
1924  if(field_elt_iszero(P1->z, E->k))
1925  {
1926  ec_point_copy(P3, P2, E->k);
1927  }
1928  else if(field_elt_iszero(P2->z, E->k))
1929  {
1930  ec_point_copy(P3, P1, E->k);
1931  }
1932  else
1933  {
1934  /* P1 and P2 != infinity */
1935  switch(E->f)
1936  {
1937  case PROJECTIVE :
1938  weierstrass_point_add_projective_dedicated(P3, P1, P2, E, stack);
1939  break;
1940 
1941  case JACOBIAN :
1942  weierstrass_point_add_jacobian_dedicated(P3, P1, P2, E, stack);
1943  break;
1944  default :
1945  break;
1946  }
1947  }
1948 }
1949 
1950 void
1951 weierstrass_point_add_unified (ec_point_ptr P3, ec_point_srcptr P1, ec_point_srcptr P2,
1952  ec_curve_srcptr E, uint8_t stack)
1953 {
1954  if(field_elt_iszero(P1->z, E->k))
1955  {
1956  ec_point_copy(P3, P2, E->k);
1957  }
1958  else if(field_elt_iszero(P2->z, E->k))
1959  {
1960  ec_point_copy(P3, P1, E->k);
1961  }
1962  else
1963  {
1964  /* P1 and P2 != infinity */
1965  switch(E->f)
1966  {
1967  case PROJECTIVE :
1968  weierstrass_point_add_projective_unified(P3, P1, P2, E, stack);
1969  break;
1970 
1971  case JACOBIAN :
1972  /* Not implemented because the COZ arithmetic is anyhow faster in this case */
1973  break;
1974  default :
1975  break;
1976  }
1977  }
1978 }
1979 
1980 void
1981 weierstrass_point_dbl_dedicated (ec_point_ptr P3, ec_point_srcptr P1, ec_curve_srcptr E, uint8_t stack)
1982 {
1983  if(field_elt_iszero(P1->y, E->k) || field_elt_iszero(P1->z, E->k))
1984  {
1985  /* Then 2 P1 = point at the infinity */
1986  weierstrass_point_set_neutral(P3, E, stack);
1987  }
1988  else
1989  {
1990  /* P1 != infinity, 2*P1 != infinity */
1991  switch(E->f)
1992  {
1993  case PROJECTIVE :
1994  weierstrass_point_dbl_projective_dedicated(P3, P1, E, stack);
1995  break;
1996 
1997  case JACOBIAN :
1998  weierstrass_point_dbl_jacobian_dedicated(P3, P1, E, stack);
1999  break;
2000  default :
2001  break;
2002  }
2003  }
2004 }
2005 
2006 void
2007 weierstrass_point_neg (ec_point_ptr P3, ec_point_srcptr P1, ec_curve_srcptr E)
2008 {
2009  field_t *k = E->k;
2010  field_elt_copy(P3->x, P1->x, k);
2011  field_elt_neg(P3->y, P1->y, k);
2012  field_elt_copy(P3->z, P1->z, k);
2013  field_elt_copy(P3->t, P1->t, k);
2014 }
2015 
2018 void
2019 weierstrass_point_of_order_2 (ec_point_ptr dst, ec_curve_srcptr E, uint8_t stack)
2020 {
2021  ec_point Q;
2022  field_elt c, d, e, f, g, c2, d2, e2, f2, non_residue;
2023  field_t *k = E->k;
2024  field k2;
2025  int i=0;
2026  ec_point_get_pool_elt(Q, k, stack);
2027  field_elt_get_pool_elt(&c, k, stack);
2028  field_elt_get_pool_elt(&d, k, stack);
2029  field_elt_get_pool_elt(&e, k, stack);
2030  field_elt_get_pool_elt(&f, k, stack);
2031  field_elt_get_pool_elt(&g, k, stack);
2032  field_elt_get_pool_elt(&non_residue, k, stack);
2033 
2034  field_find_nonsquare(non_residue, k, stack);
2035  field_alloc(k2, FP2, E->k->size, k);
2036  field_create(k2, "", stack, 2, k, non_residue);
2037 
2038  field_elt_get_pool_elt(&c2, k2, stack);
2039  field_elt_get_pool_elt(&d2, k2, stack);
2040  field_elt_get_pool_elt(&e2, k2, stack);
2041  field_elt_get_pool_elt(&f2, k2, stack);
2042 
2043 
2044  MPHELL_ASSERT( E->type == WEIERSTRASS, "This curve is not a Weierstrass Curve \n");
2045  /* First we compute the abscissa of a point of order 2 of the Curve */
2046  /* To obtain such a point we solve the cubic equation x^3 + E->a*x + E->b */
2047  /* We first use Cardano's formulas */
2048  field_elt_set_one(c, k);
2049  field_elt_inc(c, c, k);
2050  field_elt_div(d, E->b, c, k, stack); /* d = B / 2 */
2051  field_elt_inc(c, c, k);
2052  field_elt_div(c, E->a, c, k, stack); /* c = A / 3 */
2053  field_elt_sqr(e, c, k, stack); /* e = (A / 3)^2 */
2054  field_elt_mul(c, c, e, k, stack); /* c = (A / 3)^3 */
2055  field_elt_sqr(f, d, k, stack); /* f = (B/2)^2 */
2056  field_elt_add(c, c, f, k); /* c = (A / 3)^3 + (B/2)^2 */
2057 
2058  if(field_elt_issquare(c, k, stack)==false)
2059  {
2060  /* Cardano's formulas do not apply in k */
2061  /* We search for a simple root of the cubic equation x^3 + A x + B */
2062  switch(k->type)
2063  {
2064  case FP:
2065  /* We have to create first the quadratic extension FP2 of FP in which we will do the intermediate computations */
2066  field_elt_set_ui(e, 0, true, k, stack);
2067  field_elt_set_fp_elts(c2, k2, 2, c, e);
2068  field_elt_set_fp_elts(d2, k2, 2, d, e);
2069  field_elt_sqrt(c2, c2, k2, stack); /* c = ((A / 3)^3 + (B/2)^2) ^(1/2) */
2070 
2071  field_elt_neg(d2, d2, k2); /* d = -B / 2 */
2072  field_elt_sub(e2, d2, c2, k2); /* e = -B / 2 - ((A / 3)^3 + (B/2)^2) ^(1/2) */
2073  field_elt_add(f2, d2, c2, k2); /* f = -B / 2 + ((A / 3)^3 + (B/2)^2) ^(1/2) */
2074 
2075  MPHELL_ASSERT( field_elt_ispower_ui(e2, 3, k2, stack), "This curve do not seem to have points of order 2 defined \n");
2076  MPHELL_ASSERT( field_elt_ispower_ui(f2, 3, k2, stack), "This curve do not seem to have points of order 2 defined \n");
2077  field_elt_cube_root(e2, e2, k2, stack); /* S = (-B / 2 - ((A / 3)^3 + (B/2)^2) ^(1/2))^(1/3) (stored in e) */
2078  field_elt_cube_root(f2, f2, k2, stack); /* T = (-B / 2 + ((A / 3)^3 + (B/2)^2) ^(1/2))^(1/3) (stored in f) */
2079  field_elt_add(c2, e2, f2, k2); /* c = S + T */
2080  field_elt_set_one(d, k);
2081  field_elt_dec(d, d, k);
2082  field_elt_get_fp_elt(c, c2, 2, k2);
2083  field_elt_set_one(d2, k2);
2084  field_elt_unity_nth_root(d2, 3, k2, stack);
2085  if(!field_elt_iszero(c, k))
2086  {
2087  /* In this case we search for a solution defined in FP */
2088  field_elt_mul(f2, f2, d2, k2, stack);
2089  field_elt_add(c2, e2, f2, k2);
2090  field_elt_get_fp_elt(c, c2, 2, k2);
2091  if(!field_elt_iszero(c, k))
2092  {
2093  field_elt_mul(f2, f2, d2, k2, stack);
2094  field_elt_add(c2, e2, f2, k2);
2095  }
2096  }
2097 
2098  /*We update (choice of cubic root) the value of c2 to get a point of order 2 */
2099  do
2100  {
2101  i=i+1;
2102  field_elt_get_fp_elt(c, c2, 1, k2);
2103  field_elt_sqr(e, c, k, stack);
2104  field_elt_add(e, E->a, e, k);
2105  field_elt_mul(e, e, c, k, stack);
2106  field_elt_add(e, e, E->b, k); /* e = c^3 + a c + b */
2107  field_elt_mul(c2, c2, d2, k2, stack);
2108  }while(!field_elt_iszero(e, k) && i<3);
2109  MPHELL_ASSERT( field_elt_iszero(e, k), "\nThere is no point of order 2 defined in FP \n");
2110  break;
2111  case FP2:
2112  case FP3:
2113  MPHELL_ASSERT( k->type==FP, "We have to work in an a quadratic extension and it is not implemented for non FP field type \n");
2114  break;
2115  }
2116  }
2117  else
2118  {
2119  /* Cardano's formula apply we use them */
2120  field_elt_sqrt(c, c, k, stack); /* c = ((A / 3)^3 + (B/2)^2) ^(1/2) */
2121  field_elt_neg(d, d, k); /* d = -B / 2 */
2122  field_elt_sub(e, d, c, k); /* e = -B / 2 - ((A / 3)^3 + (B/2)^2) ^(1/2) */
2123  field_elt_add(f, d, c, k); /* f = -B / 2 + ((A / 3)^3 + (B/2)^2) ^(1/2) */
2124  MPHELL_ASSERT(field_elt_ispower_ui(e, 3, k, stack), "This curve do not seem to have points of order 2 defined \n");
2125  MPHELL_ASSERT(field_elt_ispower_ui(f, 3, k, stack), "This curve do not seem to have points of order 2 defined \n");
2126  field_elt_cube_root(e, e, k, stack); /* S = (-B / 2 - ((A / 3)^3 + (B/2)^2) ^(1/2))^(1/3) (stored in e) */
2127  field_elt_cube_root(f, f, k, stack); /* T = (-B / 2 + ((A / 3)^3 + (B/2)^2) ^(1/2))^(1/3) (stored in f) */
2128  field_elt_unity_nth_root(d, 3, k, stack);
2129  /* In this do while loop we update (choice of cubic root) the value of c to get a point of order 2 */
2130 
2131  do
2132  {
2133  i=i+1;
2134  field_elt_add(c, e,f, k); /* c = S + T */
2135  field_elt_sqr(g, c, k, stack);
2136  field_elt_add(g, E->a, g, k);
2137  field_elt_mul(g, g, c, k, stack);
2138  field_elt_add(g, g, E->b, k); /* g = c^3 + a c + b */
2139  field_elt_mul(e, e, d, k, stack);
2140  }while(i<3 && !field_elt_iszero(g, k));
2141  field_elt_set_one(d, k);
2142  field_elt_dec(d, d, k);
2143 
2144  }
2145 
2146  weierstrass_point_set_aff(Q, c, d, k);
2147  /* We verify that this point computed belongs to the curve*/
2148  MPHELL_ASSERT(weierstrass_belongs(Q, E, stack),"The Point of order 2 computed does not belong to the Weierstrass curve E ! \n");
2149  ec_point_copy(dst, Q, k);
2150 
2151  field_elt_relax_pool_elt(&non_residue, k, stack);
2152  field_elt_relax_pool_elt(&c, k, stack);
2153  field_elt_relax_pool_elt(&d, k, stack);
2154  field_elt_relax_pool_elt(&e, k, stack);
2155  field_elt_relax_pool_elt(&f, k, stack);
2156  field_elt_relax_pool_elt(&g, k, stack);
2157  field_elt_relax_pool_elt(&c2, k2, stack);
2158  field_elt_relax_pool_elt(&d2, k2, stack);
2159  field_elt_relax_pool_elt(&e2, k2, stack);
2160  field_elt_relax_pool_elt(&f2, k2, stack);
2161  field_free(k2);
2162  ec_point_relax_pool_elt(Q, k, stack);
2163 }
2164 
2165 void
2166 weierstrass_points_of_order_2 (ec_point_ptr dst1, ec_point_ptr dst2, ec_point_ptr dst3, ec_curve_srcptr E, uint8_t stack)
2167 {
2168  ec_point Q;
2169  field_elt c, d, e, f, g, c2, d2, e2, f2, non_residue;
2170  field_t *k = E->k;
2171  field k2;
2172  int i=0;
2173  ec_point_get_pool_elt(Q, k, stack);
2174  field_elt_get_pool_elt(&c, k, stack);
2175  field_elt_get_pool_elt(&d, k, stack);
2176  field_elt_get_pool_elt(&e, k, stack);
2177  field_elt_get_pool_elt(&f, k, stack);
2178  field_elt_get_pool_elt(&g, k, stack);
2179  field_elt_get_pool_elt(&non_residue, k, stack);
2180 
2181  field_find_nonsquare(non_residue, k, stack);
2182  field_alloc(k2, FP2, E->k->size, k);
2183  field_create(k2, "", stack, 2, k, non_residue);
2184 
2185  field_elt_get_pool_elt(&c2, k2, stack);
2186  field_elt_get_pool_elt(&d2, k2, stack);
2187  field_elt_get_pool_elt(&e2, k2, stack);
2188  field_elt_get_pool_elt(&f2, k2, stack);
2189 
2190  MPHELL_ASSERT(E->type == WEIERSTRASS, "This curve is not a Weierstrass Curve \n");
2191  /* First we compute the abscissa of a point of order 2 of the Curve */
2192  /* To obtain such a point we solve the cubic equation x^3 + E->a*x + E->b */
2193  /* We first use Cardano's formulas */
2194  field_elt_set_one(c, k);
2195  field_elt_inc(c, c, k);
2196  field_elt_div(d, E->b, c, k, stack); /* d = B / 2 */
2197  field_elt_inc(c, c, k);
2198  field_elt_div(c, E->a, c, k, stack); /* c = A / 3 */
2199  field_elt_sqr(e, c, k, stack); /* e = (A / 3)^2 */
2200  field_elt_mul(c, c, e, k, stack); /* c = (A / 3)^3 */
2201  field_elt_sqr(f, d, k, stack); /* f = (B/2)^2 */
2202  field_elt_add(c, c, f, k); /* c = (A / 3)^3 + (B/2)^2 */
2203 
2204  if(field_elt_issquare(c, k, stack)==false)
2205  {
2206  /* Cardano's formulas do not apply in k */
2207  /* We search for a simple root of the cubic equation x^3 + A x + B */
2208  switch(k->type)
2209  {
2210  case FP:
2211  /* We have to create first the quadratic extension FP2 of FP in which we will do the intermediate computations */
2212  field_elt_set_ui(e, 0, true, k, stack);
2213  field_elt_set_fp_elts(c2, k2, 2, c, e);
2214  field_elt_set_fp_elts(d2, k2, 2, d, e);
2215 
2216  field_elt_sqrt(c2, c2, k2, stack); /* c = ((A / 3)^3 + (B/2)^2) ^(1/2) */
2217  field_elt_neg(d2, d2, k2); /* d = -B / 2 */
2218  field_elt_sub(e2, d2, c2, k2); /* e = -B / 2 - ((A / 3)^3 + (B/2)^2) ^(1/2) */
2219  field_elt_add(f2, d2, c2, k2); /* f = -B / 2 + ((A / 3)^3 + (B/2)^2) ^(1/2) */
2220 
2221  MPHELL_ASSERT( field_elt_ispower_ui(e2, 3, k2, stack), "This curve do not seem to have points of order 2 defined \n");
2222  MPHELL_ASSERT( field_elt_ispower_ui(f2, 3, k2, stack), "This curve do not seem to have points of order 2 defined \n");
2223  field_elt_cube_root(e2, e2, k2, stack); /* S = (-B / 2 - ((A / 3)^3 + (B/2)^2) ^(1/2))^(1/3) (stored in e) */
2224  field_elt_cube_root(f2, f2, k2, stack); /* T = (-B / 2 + ((A / 3)^3 + (B/2)^2) ^(1/2))^(1/3) (stored in f) */
2225  field_elt_add(c2, e2, f2, k2); /* c = S + T */
2226 
2227  field_elt_get_fp_elt(c, e2, 2, k2);
2228  field_elt_get_fp_elt(d, f2, 2, k2);
2229  field_elt_set_one(d2, k2);
2230  field_elt_unity_nth_root(d2, 3, k2, stack);
2231  while(field_elt_cmp(c, d, k)!=0 && i<9)
2232  {
2233  i=i+1;
2234  if(i%3!=0)
2235  {
2236  field_elt_mul(e2, e2, d2, k2, stack);
2237  }
2238  else
2239  {
2240  field_elt_mul(f2, f2, d2, k2, stack);
2241  }
2242  field_elt_add(c2, e2, f2, k2); /* c = S + T */
2243  field_elt_get_fp_elt(c, e2, 2, k2);
2244  field_elt_get_fp_elt(d, f2, 2, k2);
2245  }
2246  i=0;
2247  field_elt_set_one(d, k);
2248  field_elt_dec(d, d, k);
2249  field_elt_get_fp_elt(c, c2, 2, k2);
2250 
2251  /*We update (choice of cubic root) the value of c2 to get a point of order 2 */
2252  do
2253  {
2254  i=i+1;
2255  field_elt_get_fp_elt(c, c2, 1, k2);
2256  field_elt_sqr(e, c, k, stack);
2257  field_elt_add(e, E->a, e, k);
2258  field_elt_mul(e, e, c, k, stack);
2259  field_elt_add(e, e, E->b, k); /* e = c^3 + a c + b */
2260  field_elt_mul(c2, c2, d2, k2, stack);
2261  }while(!field_elt_iszero(e, k) && i<3);
2262  MPHELL_ASSERT( field_elt_iszero(e, k), "\nThere is no point of order 2 defined in FP \n");
2263  break;
2264  case FP2:
2265  case FP3:
2266  MPHELL_ASSERT(k->type==FP, "We have to work in an a quadratic extension and it is not implemented for non FP field type \n");
2267  break;
2268  }
2269  }
2270  else
2271  {
2272  /* Cardano's formula apply we use them */
2273  field_elt_sqrt(c, c, k, stack); /* c = ((A / 3)^3 + (B/2)^2) ^(1/2) */
2274  field_elt_neg(d, d, k); /* d = -B / 2 */
2275  field_elt_sub(e, d, c, k); /* e = -B / 2 - ((A / 3)^3 + (B/2)^2) ^(1/2) */
2276  field_elt_add(f, d, c, k); /* f = -B / 2 + ((A / 3)^3 + (B/2)^2) ^(1/2) */
2277  MPHELL_ASSERT(field_elt_ispower_ui(e, 3, k, stack), "This curve do not seem to have points of order 2 defined \n");
2278  MPHELL_ASSERT(field_elt_ispower_ui(f, 3, k, stack), "This curve do not seem to have points of order 2 defined \n");
2279  field_elt_cube_root(e, e, k, stack); /* S = (-B / 2 - ((A / 3)^3 + (B/2)^2) ^(1/2))^(1/3) (stored in e) */
2280  field_elt_cube_root(f, f, k, stack); /* T = (-B / 2 + ((A / 3)^3 + (B/2)^2) ^(1/2))^(1/3) (stored in f) */
2281  field_elt_unity_nth_root(d, 3, k, stack);
2282  /* In this do while loop we update (choice of cubic root) the value of c to get a point of order 2 */
2283  do
2284  {
2285  i=i+1;
2286  field_elt_add(c, e, f, k); /* c = S + T */
2287  field_elt_sqr(g, c, k, stack);
2288  field_elt_add(g, E->a, g, k);
2289  field_elt_mul(g, g, c, k, stack);
2290  field_elt_add(g, g, E->b, k); /* g = c^3 + a c + b */
2291  field_elt_mul(e, e, d, k, stack);
2292  }while(i<3 && !field_elt_iszero(g, k));
2293  field_elt_set_one(d, k);
2294  field_elt_dec(d, d, k);
2295  }
2296  weierstrass_point_set_aff(Q, c, d, k);
2297  /* We verify that this point computed belongs to the curve*/
2298  MPHELL_ASSERT(weierstrass_belongs(Q, E, stack),"The Point of order 2 computed does not belong to the Weierstrass curve E ! \n");
2299 
2300  ec_point_copy(dst1, Q, k);
2301  /* In this case we compute the two others points of order 2 assuming they exist */
2302  /* Fist we compute the discriminant of the quadratic equation */
2303  field_elt_sqr(e, c, k, stack); /* e = alpha^2 */
2304  field_elt_add(d, e, E->a, k); /* d = alpha^2 + a */
2305  field_elt_add(g, d, d, k);
2306  field_elt_add(g, g, g, k);
2307  field_elt_sub(f, e, g, k); /* f = alpha^2 - 4 d (discriminant) */
2308  field_elt_set_one(d, k);
2309  field_elt_inc(d, d, k);
2310  if(field_elt_issquare(f, k, stack))
2311  {
2312  /* In this case we compute the 3 points of order 2 */
2313  field_elt_sqrt(f, f, k, stack); /* f = (alpha^2 - 4 d)^(1/2) */
2314  field_elt_add(e, f, c, k);
2315  field_elt_neg(e, e, k);
2316  field_elt_div(e, e, d, k, stack); /* e =- ( (alpha^2 - 4 d)^(1/2) + alpha ) / 2 */
2317  field_elt_sub(c, f, c, k);
2318  field_elt_div(c, c, d, k, stack); /* c = ( (alpha^2 - 4 d)^(1/2) - alpha ) / 2 */
2319  field_elt_set_one(d, k);
2320  field_elt_dec(d, d, k);
2321  weierstrass_point_set_aff(Q, c, d, k);
2322  MPHELL_ASSERT(weierstrass_belongs(Q, E, stack),"The Point of order 2 computed does not belong to the Weierstrass curve E ! \n");
2323  ec_point_copy(dst2, Q, k);
2324  weierstrass_point_set_aff(Q, e, d, k);
2325  MPHELL_ASSERT(weierstrass_belongs(Q, E, stack),"The Point of order 2 computed does not belong to the Weierstrass curve E ! \n");
2326  ec_point_copy(dst3, Q, k);
2327  }
2328  else
2329  {
2330  /* Otherwise we just return 3 times the same point */
2331  ec_point_copy(dst2, Q, k);
2332  ec_point_copy(dst3, Q, k);
2333  }
2334 
2335  /* Now we free the memory */
2336  field_elt_relax_pool_elt(&non_residue, k, stack);
2337  field_elt_relax_pool_elt(&c, k, stack);
2338  field_elt_relax_pool_elt(&d, k, stack);
2339  field_elt_relax_pool_elt(&e, k, stack);
2340  field_elt_relax_pool_elt(&f, k, stack);
2341  field_elt_relax_pool_elt(&g, k, stack);
2342  field_elt_relax_pool_elt(&c2, k2, stack);
2343  field_elt_relax_pool_elt(&d2, k2, stack);
2344  field_elt_relax_pool_elt(&e2, k2, stack);
2345  field_elt_relax_pool_elt(&f2, k2, stack);
2346  field_free(k2);
2347  ec_point_relax_pool_elt(Q, k, stack);
2348 }
weierstrass_point_neg
void weierstrass_point_neg(ec_point_ptr P3, ec_point_srcptr P1, ec_curve_srcptr E)
Set P3 to -P1.
Definition: mphell-weierstrass.c:2007
weierstrass_point_add_ZADDC
void weierstrass_point_add_ZADDC(ec_point_ptr P3, ec_point_ptr P4, ec_point_srcptr P1, ec_point_srcptr P2, ec_curve_srcptr E, uint8_t stack)
Conjugate Co-Z point addition: Set P3 to P1 + P2 and P4 to P1 - P2 such that Z3=Z4.
Definition: mphell-weierstrass.c:815
number_iszero
bool number_iszero(number_srcptr src)
Test if src is zero.
Definition: mphell-number.c:744
weierstrass_verify_random_generation
bool weierstrass_verify_random_generation(ec_curve E, const char *seed, uint8_t stack)
Test if E if generated from the seed "seed".
Definition: mphell-weierstrass.c:100
field_elt
fp_elt * field_elt
Generic field element.
Definition: mphell-field.h:39
field_elt_unity_nth_root
void field_elt_unity_nth_root(fe_ptr dst, const block n, field_ptr k, uint8_t stack)
Set dst to a non trivial n-th root of unity if it exists (ie n divides order(k)-1),...
Definition: mphell-field.c:1067
ec_point::y
field_elt y
Definition: mphell-curve.h:106
ec_point_set_neutral
void ec_point_set_neutral(ec_point_ptr dst, ec_curve_srcptr E, uint8_t stack)
Set dst to the neutral element.
Definition: mphell-curve.c:780
field_elt_iszero
static bool field_elt_iszero(fe_srcptr src, field_srcptr k)
Test if src is zero.
Definition: mphell-field.h:504
field_elt_mul
static void field_elt_mul(fe_ptr dst, fe_srcptr src1, fe_srcptr src2, field_srcptr k, uint8_t stack)
Set dst <- src1 * src2, if Montgomery arithmetic is used, the Montgomery multiplication will be used ...
Definition: mphell-field.h:753
drbg_incr_data
void drbg_incr_data(uint8_t *data, const uint16_t data_len)
Increment data (Set data to data + 1 where data is an array of data_len bytes)
Definition: mphell-drbg_common.c:66
mphell-sha1.h
Declaration of sha1 functions.
field_elt_mul4
static void field_elt_mul4(fe_ptr dst, fe_srcptr src, field_srcptr k)
Set dst <- 4 * src.
Definition: mphell-field.h:833
ec_curve::type
ec_type type
Definition: mphell-curve.h:145
field_t::bit_size
uint16_t bit_size
Definition: mphell-field.h:95
weierstrass_point_set_aff_str
void weierstrass_point_set_aff_str(ec_point_ptr P, const char *str_x, const char *str_y, const bool is_reduced, const uint8_t base, field_srcptr k, uint8_t stack)
Set dest to the affine point (str_x,str_y)
Definition: mphell-weierstrass.c:432
field_elt_mul8
static void field_elt_mul8(fe_ptr dst, fe_srcptr src, field_srcptr k)
Set dst <- 8 * src.
Definition: mphell-field.h:859
number_log2
uint16_t number_log2(number_srcptr src)
Calculate log2(src), which is the binary size of src.
Definition: mphell-number.c:257
weierstrass_Zmontgomery_Kim
void weierstrass_Zmontgomery_Kim(ec_point_ptr P3, number_srcptr n, ec_point_srcptr P1, ec_curve_srcptr E, uint8_t stack)
Perform the Montgomery ladder, taken from Kim et al's 2017 work, compute P3=[n]P1 it has the drawback...
Definition: mphell-weierstrass.c:1757
weierstrass_point_add_projective_unified
void weierstrass_point_add_projective_unified(ec_point_ptr P3, ec_point_srcptr P1, ec_point_srcptr P2, ec_curve_srcptr E, uint8_t stack)
Set P3 to P1 + P2 using projective coordinate.
Definition: mphell-weierstrass.c:1215
number_to_bit_string
void number_to_bit_string(char *str, number_srcptr src)
Converts src (must be positive) to a bit string.
Definition: mphell-number.c:665
field_t
Define a field.
Definition: mphell-field.h:90
ec_point
Define an elliptic curve point.
Definition: mphell-curve.h:103
weierstrass_point_TPLU
void weierstrass_point_TPLU(ec_point_ptr P3, ec_point_ptr P4, ec_point_srcptr P1, ec_curve_srcptr E, uint8_t stack)
Co-Z point tripling with update: Set P3 to 3*P1 and P4 such that P4 = P1 and Z4 = Z3.
Definition: mphell-weierstrass.c:1001
ec_curve::ec_spec1
bool ec_spec1
Definition: mphell-curve.h:152
hex2bin
uint32_t hex2bin(const char *in, unsigned char *out)
Convert an hexadecimal string into a binary string.
Definition: mphell-util.c:111
ec_point::t
field_elt t
Definition: mphell-curve.h:108
field_elt_inc
static void field_elt_inc(fe_ptr dst, fe_srcptr src, field_srcptr k)
Set dst <- src + 1.
Definition: mphell-field.h:535
weierstrass_point_random
void weierstrass_point_random(ec_point_ptr P, ec_curve_srcptr E, uint8_t stack)
Set P to a random point on E.
Definition: mphell-weierstrass.c:511
bits_to_nblock
uint8_t bits_to_nblock(const uint16_t nbits)
Return the number of blocks required to store a nbits number.
Definition: mphell-util.c:29
field_elt_sqrt
void field_elt_sqrt(fe_ptr dst, fe_srcptr src, field_srcptr k, uint8_t stack)
Set dst <- src^(1/2)
Definition: mphell-field.c:1025
ec_curve::f
ec_formula f
Definition: mphell-curve.h:146
weierstrass_compute_disc
void weierstrass_compute_disc(ec_curve E, uint8_t stack)
Set the discriminant of E: disc = -16(4a^3 + 27b^2)
Definition: mphell-weierstrass.c:70
ec_curve::b
field_elt b
Definition: mphell-curve.h:144
weierstrass_point_DBLU
void weierstrass_point_DBLU(ec_point_ptr P3, ec_point_ptr P4, ec_point_srcptr P1, ec_curve_srcptr E, uint8_t stack)
Co-Z point doubling with update: Set P3 to 2*P1 and P4 such that P1 = P4 and Z4 = Z3 and assume that ...
Definition: mphell-weierstrass.c:940
field
field_t field[1]
Address of a field structure.
Definition: mphell-field.h:110
field_elt_div
void field_elt_div(fe_ptr dst, fe_srcptr src1, fe_srcptr src2, field_srcptr k, uint8_t stack)
Set dst <- src1 / src2.
Definition: mphell-field.c:1193
field_t::size
uint8_t size
Definition: mphell-field.h:94
field_elt_mul3
static void field_elt_mul3(fe_ptr dst, fe_srcptr src, field_srcptr k, uint8_t stack)
Set dst <- 3 * src.
Definition: mphell-field.h:886
weierstrass_point_add_projective_dedicated
void weierstrass_point_add_projective_dedicated(ec_point_ptr P3, ec_point_srcptr P1, ec_point_srcptr P2, ec_curve_srcptr E, uint8_t stack)
Set P3 to P1 + P2 using projective coordinate.
Definition: mphell-weierstrass.c:1121
field_elt_isone
bool field_elt_isone(fe_srcptr src, field_srcptr k)
Test if src is one.
Definition: mphell-field.c:774
field_elt_cube_root
void field_elt_cube_root(fe_ptr dst, fe_srcptr src, field_srcptr k, uint8_t stack)
Set dst <- src^(1/3)
Definition: mphell-field.c:1046
number_random1
void number_random1(number_ptr dst, number_srcptr bound, uint8_t stack)
Set dst to a random number_ptr between 0 and bound, the random process is chosen at the MPHELL initia...
Definition: mphell-number.c:230
ec_curve::disc
field_elt disc
Definition: mphell-curve.h:150
weierstrass_point_add_unified
void weierstrass_point_add_unified(ec_point_ptr P3, ec_point_srcptr P1, ec_point_srcptr P2, ec_curve_srcptr E, uint8_t stack)
Set P3 to P1 + P2, using unified formulae (protection against SPA)
Definition: mphell-weierstrass.c:1951
weierstrass_point_set_neutral
void weierstrass_point_set_neutral(ec_point_ptr dst, ec_curve_srcptr E, uint8_t stack)
Set dst to the neutral element: (0,1,0) for projective coordinates and (1,1,0) for jacobian coordinat...
Definition: mphell-weierstrass.c:397
ec_point_relax_pool_elt
static void ec_point_relax_pool_elt(ec_point_ptr P, field_ptr k, uint8_t stack)
Relax an initialised point from the pool.
Definition: mphell-curve.h:218
weierstrass_belongs
bool weierstrass_belongs(ec_point_srcptr P, ec_curve_srcptr E, uint8_t stack)
Test if P belongs to E.
Definition: mphell-weierstrass.c:442
weierstrass_point_get_x_affine
void weierstrass_point_get_x_affine(field_elt x, ec_point_ptr P, ec_curve_srcptr E, uint8_t stack)
Convert P->x to its affine representation.
Definition: mphell-weierstrass.c:578
weierstrass_point_get_y_affine
void weierstrass_point_get_y_affine(field_elt y, ec_point_ptr P, ec_curve_srcptr E, uint8_t stack)
Convert P->y to its affine representation.
Definition: mphell-weierstrass.c:604
field_elt_set_one
void field_elt_set_one(fe_ptr dst, field_srcptr k)
Set dst to one (or its Montgomery form if Montgomery arithmetic is used)
Definition: mphell-field.c:376
mphell-curve.h
Declaration of ECC functions.
field_elt_copy
void field_elt_copy(fe_ptr dst, fe_srcptr src, field_srcptr k)
Copy src into dst, src and dst must belong to the same field.
Definition: mphell-field.c:318
field_create
void field_create(field_ptr k, const char *id, uint8_t stack, const uint32_t n,...)
Initialize the different fields of the structure pointed by k.
Definition: mphell-field.c:76
weierstrass_point_set_aff
void weierstrass_point_set_aff(ec_point_ptr P, fe_srcptr x, fe_srcptr y, field_srcptr k)
Set dest to the affine point (x, y)
Definition: mphell-weierstrass.c:423
weierstrass_point_is_neutral
bool weierstrass_point_is_neutral(ec_point_srcptr P, ec_curve_srcptr E, uint8_t stack)
Test if P is the neutral element.
Definition: mphell-weierstrass.c:633
field_elt_set_fp_elts
void field_elt_set_fp_elts(fe_ptr dst, field_srcptr k, const uint32_t n,...)
Set dst to src(s)
Definition: mphell-field.c:460
field_get_size
void field_get_size(number_ptr c, field_srcptr k)
Get the size of the field "k".
Definition: mphell-field.c:220
ec_point_get_pool_elt
static void ec_point_get_pool_elt(ec_point_ptr P, field_ptr k, uint8_t stack)
Get an initialised point from the pool.
Definition: mphell-curve.h:202
weierstrass_point_of_order_2
void weierstrass_point_of_order_2(ec_point_ptr dst, ec_curve_srcptr E, uint8_t stack)
Set dst to one of the point of order 2 of the curve E assuming that at least one exist.
Definition: mphell-weierstrass.c:2019
field_elt_issquare
bool field_elt_issquare(fe_srcptr src, field_srcptr k, uint8_t stack)
Test if src is a square using the Lengendre symbol.
Definition: mphell-field.c:921
weierstrass_point_are_equal
bool weierstrass_point_are_equal(ec_point_srcptr P1, ec_point_srcptr P2, ec_curve_srcptr E, uint8_t stack)
Test if P1 and P2 are equal on E (BUT do not test if they belong to the curve)
Definition: mphell-weierstrass.c:677
fe_srcptr
const fp_elt * fe_srcptr
Pointer on a field element, the field element cannot be modified through this pointer.
Definition: mphell-field.h:51
weierstrass_point_add_ZADDU
void weierstrass_point_add_ZADDU(ec_point_ptr P3, ec_point_ptr P1, ec_point_srcptr P2, ec_curve_srcptr E, uint8_t stack)
Co-Z point addition with update: Set P3 = (X3,Y3,Z3) to P1 + P2 using Co-Z addition and update P1 suc...
Definition: mphell-weierstrass.c:775
field_t::param
void * param
Definition: mphell-field.h:92
field_elt_ispower_ui
int8_t field_elt_ispower_ui(fe_srcptr src, const block n, field_srcptr k, uint8_t stack)
Test if src is a n-power in src->k.
Definition: mphell-field.c:940
ec_point::z
field_elt z
Definition: mphell-curve.h:107
field_elt_get_fp_elt
void field_elt_get_fp_elt(fe_ptr dst, fe_srcptr src, uint8_t pos, field_srcptr k)
Get the field_elt in position 1, 2 or 3 of the src element. Rmq: if src element is in FP,...
Definition: mphell-field.c:607
field_elt_cmp
int8_t field_elt_cmp(fe_srcptr src1, fe_srcptr src2, field_srcptr k)
Compare src1 and src2.
Definition: mphell-field.c:732
field_alloc
void field_alloc(field_ptr k, const field_type type, const uint8_t size, field_ptr base)
Allocates space for the different fields of the structure pointed by k.
Definition: mphell-field.c:37
weierstrass_point_dbl_jacobian_dedicated
void weierstrass_point_dbl_jacobian_dedicated(ec_point_ptr P3, ec_point_srcptr P1, ec_curve_srcptr E, uint8_t stack)
Set P3 to 2 P1 using jacobian coordinate with the 2007 Bernstein/Lange method.
Definition: mphell-weierstrass.c:1339
number_tmp_free
void number_tmp_free(number *t, const uint8_t size, uint8_t stack)
Free a temporary number.
Definition: mphell-number.c:45
weierstrass_point_add_jacobian_dedicated
void weierstrass_point_add_jacobian_dedicated(ec_point_ptr P3, ec_point_srcptr P1, ec_point_srcptr P2, ec_curve_srcptr E, uint8_t stack)
Set P3 to P1 + P2 using jacobian coordinate with the 2007 Bernstein/Lange method.
Definition: mphell-weierstrass.c:1409
fe_ptr
fp_elt * fe_ptr
Pointer on a field element.
Definition: mphell-field.h:45
field_elt_inv
void field_elt_inv(fe_ptr dst, fe_srcptr src, field_srcptr k, uint8_t stack)
Set dst <- src^(-1)
Definition: mphell-field.c:1088
ec_point::x
field_elt x
Definition: mphell-curve.h:105
weierstrass_points_of_order_2
void weierstrass_points_of_order_2(ec_point_ptr dst1, ec_point_ptr dst2, ec_point_ptr dst3, ec_curve_srcptr E, uint8_t stack)
Set dst1, dst2, dst3 to the points of order 2 of the curve E assuming they are different otherwise th...
Definition: mphell-weierstrass.c:2166
ec_point_copy
void ec_point_copy(ec_point_ptr P3, ec_point_srcptr P, field_srcptr k)
Copy P into P3.
Definition: mphell-curve.c:709
field_elt_mul2
static void field_elt_mul2(fe_ptr dst, fe_srcptr src, field_srcptr k)
Set dst <- 2 * src.
Definition: mphell-field.h:807
number_dec
void number_dec(number_ptr dst, number_srcptr src)
Set dst to src - 1 if src - 1 fit in dst.
Definition: mphell-number.c:1383
ec_curve::k
field_ptr k
Definition: mphell-curve.h:142
field_elt_pow_number
void field_elt_pow_number(fe_ptr dst, fe_srcptr src, number_srcptr n, field_srcptr k, uint8_t stack)
Set dst <- src^n.
Definition: mphell-field.c:902
number_set_str
void number_set_str(number_ptr dst, const char *str, const uint8_t base)
Set dst to str.
Definition: mphell-number.c:299
number_tmp_alloc
void number_tmp_alloc(number *t, const uint8_t size, uint8_t stack)
Allocate a temporary number.
Definition: mphell-number.c:31
field_elt_neg
static void field_elt_neg(fe_ptr dst, fe_srcptr src, field_srcptr k)
Set dst <- (-src)
Definition: mphell-field.h:695
weierstrass_point_norm
void weierstrass_point_norm(ec_point_ptr P, ec_curve_srcptr E, uint8_t stack)
Set P in affine coordinates.
Definition: mphell-weierstrass.c:537
number_cmp
int8_t number_cmp(number_srcptr src1, number_srcptr src2)
Compare src1 and src2.
Definition: mphell-number.c:966
weierstrass_point_dbl_dedicated
void weierstrass_point_dbl_dedicated(ec_point_ptr P3, ec_point_srcptr P1, ec_curve_srcptr E, uint8_t stack)
Set P3 to 2 * P1, using dedicated formulae (not protected against SPA, but faster)
Definition: mphell-weierstrass.c:1981
field_elt_pow_ui
void field_elt_pow_ui(fe_ptr dst, fe_srcptr src, const block n, field_srcptr k, uint8_t stack)
Set dst <- src^n.
Definition: mphell-field.c:883
field_free
void field_free(field_ptr k)
Free the space of the field informations structure.
Definition: mphell-field.c:183
field_find_nonsquare
void field_find_nonsquare(fe_ptr dst, field_ptr k, uint8_t stack)
Look for a random non square element in k.
Definition: mphell-field.c:982
ec_curve
Define an elliptic curve.
Definition: mphell-curve.h:139
weierstrass_point_dbl_projective_dedicated
void weierstrass_point_dbl_projective_dedicated(ec_point_ptr P3, ec_point_srcptr P1, ec_curve_srcptr E, uint8_t stack)
Set P3 to 2 P1 using projective coordinate.
Definition: mphell-weierstrass.c:1020
field_elt_set_str
void field_elt_set_str(fe_ptr dst, const char *str, const uint8_t base, const bool isreduced, field_srcptr k, uint8_t stack)
Set dst to str, if Montgomery arithmetic is used, is_reduced == false -> transform dst into its Montg...
Definition: mphell-field.c:505
weierstrass_Zjoye_mul
void weierstrass_Zjoye_mul(ec_point_ptr P3, number_srcptr n, ec_point_srcptr P1, ec_curve_srcptr E, uint8_t stack)
Set P3 to n * P1 using Joye’s double-add algorithm with Co-Z addition formula.The formulae are not co...
Definition: mphell-weierstrass.c:1843
field_elt_sqr
static void field_elt_sqr(fe_ptr dst, fe_srcptr src, field_srcptr k, uint8_t stack)
Set dst <- src^2.
Definition: mphell-field.h:913
fp_param_t
Primary field parameters.
mphell-drbg_internal.h
Declaration of the Deterministic Random Bit Generator internal functions.
weierstrass_point_add_ZDAU
void weierstrass_point_add_ZDAU(ec_point_ptr P3, ec_point_srcptr P1, ec_point_ptr P2, ec_curve_srcptr E, uint8_t stack)
Co-Z point doubling-addition with update: Set P3 to 2*P1 + P2 and update P2 such that Z2 = Z3.
Definition: mphell-weierstrass.c:866
field_elt_set_ui
void field_elt_set_ui(fe_ptr dst, const block src, const bool isreduced, field_srcptr k, uint8_t stack)
Set dst to src, if Montgomery arithmetic is used, is_reduced == false -> transform dst into its Montg...
Definition: mphell-field.c:395
weierstrass_Zmontgomery_ladder
void weierstrass_Zmontgomery_ladder(ec_point_ptr P3, number_srcptr n, ec_point_srcptr P1, ec_curve_srcptr E, uint8_t stack)
Set P3 to n * P1 using Montgomery ladder with Co-Z addition formula.
Definition: mphell-weierstrass.c:1496
field_elt_sub
static void field_elt_sub(fe_ptr dst, fe_srcptr src1, fe_srcptr src2, field_srcptr k)
Set dst <- src1 - src2.
Definition: mphell-field.h:642
field_elt_dec
static void field_elt_dec(fe_ptr dst, fe_srcptr src, field_srcptr k)
Set dst <- src - 1.
Definition: mphell-field.h:615
field_elt_relax_pool_elt
static void field_elt_relax_pool_elt(field_elt *dst, field_ptr k, uint8_t stack)
Relax an initialised field element from the pool.
Definition: mphell-field.h:167
field_t::type
field_type type
Definition: mphell-field.h:93
field_elt_add
static void field_elt_add(fe_ptr dst, fe_srcptr src1, fe_srcptr src2, field_srcptr k)
Set dst <- src1 + src2.
Definition: mphell-field.h:562
field_elt_get_pool_elt
static void field_elt_get_pool_elt(field_elt *dst, field_ptr k, uint8_t stack)
Get an initialised field element from the pool.
Definition: mphell-field.h:134
fp2_param_t
Quadratic extension field structure.
Definition: mphell-fp2.h:63
number_str
void number_str(char **str, number_srcptr src, const uint8_t base)
Converts src to string format in base specified by base.
Definition: mphell-number.c:444
weierstrass_point_add_dedicated
void weierstrass_point_add_dedicated(ec_point_ptr P3, ec_point_srcptr P1, ec_point_srcptr P2, ec_curve_srcptr E, uint8_t stack)
Set P3 to P1 + P2, using dedicated formulae (not protected against SPA, but faster)
Definition: mphell-weierstrass.c:1921
weierstrass_curve_random_generation
void weierstrass_curve_random_generation(fe_ptr a, fe_ptr b, char *seed_res, field_srcptr k, uint8_t stack)
Generate a 160 bits seed and coefficients a and b defining a Weiestrass elliptic curve....
Definition: mphell-weierstrass.c:227
field_elt_random
void field_elt_random(fe_ptr dst, field_srcptr k, uint8_t stack)
Set dst to a random element of k, the random process is chosen at the MHELL initialisation.
Definition: mphell-field.c:525
field_elt_set_number
void field_elt_set_number(fe_ptr dst, const bool isreduced, field_srcptr k, uint8_t stack, const uint32_t n,...)
Set dst to src, if Montgomery arithmetic is used, is_reduced == false -> transform dst into its Montg...
Definition: mphell-field.c:415
ec_curve::D
field_elt D
Definition: mphell-curve.h:151
Generated by   doxygen 1.8.15