MPHELL  4.0.0
mphell-jacobi.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 #include "mphell-curve.h"
27 
28 
29 /************************************SETTERS**********************************/
30 
31 void
32 jacobi_quartic_compute_disc(ec_curve E, uint8_t stack)
33 {
34  field_t *k = E->k;
35  field_elt t2, t1;
36  field_elt_get_pool_elt(&t2, k, stack);
37  field_elt_get_pool_elt(&t1, k, stack);
38 
39  field_elt_sqr(t1, E->a, k, stack); /* t1 = a^2 */
40  field_elt_set_one(t2, k); /* t2 = 1 */
41  field_elt_sub(t1, t1, t2, k); /* t1 = a^2 - 1 */
42  field_elt_sqr(t1, t1, k, stack); /* t1 = (a^2 -1)^2 */
43  field_elt_copy(E->D, t1, k); /* D = (a^2 -1)^2 */
44  field_elt_set_ui(t2, 256, false, k, stack);
45  field_elt_mul(E->disc, t1, t2, k, stack); /* disc = (2^8).(a^2 - 1)^2 */
46 
47  field_elt_relax_pool_elt(&t1, k, stack);
48  field_elt_relax_pool_elt(&t2, k, stack);
49 }
50 
51 #include "mphell-drbg_internal.h"
52 #include "mphell-sha1.h"
53 
54 bool jacobi_quartic_verify_random_generation(ec_curve E, const char * seed, uint8_t stack)
55 {
56  /* Source : Working Draft AMERICAN NATIONAL STANDARD X9.62-1998, section A.3.4.2 */
57  field_t *k = E->k;
58 
59  field_elt r1;
60  field_elt_get_pool_elt(&r1, k, stack);
61 
62  number tmp;
63  number_tmp_alloc(&tmp, k->size, stack);
64 
65  /* t = log2(p) */
66  uint16_t t;
67  switch(k->type)
68  {
69  case FP:
70  t = number_log2(((fp_param)k->param)->p);
71  break;
72  case FP2:
73  case FP3:
74  t = number_log2(((fp_param)((fp2_param)k->param)->base)->p);
75  break;
76  default:
77  return false;
78  }
79  /* s = (t-1) / 160 */
80  uint16_t s = (t-1)/160;
81  /* h = t - 160*s */
82  uint16_t h = t - (160*s);
83  h --; /* set the leftmost bit of c0 to 0 */
84  uint16_t hbytes = (h / 8) + (h%8 != 0);
85 
86  /* Alloc W' */
87 
88  uint8_t * Wprime = calloc(s*20+hbytes, sizeof(uint8_t));
89 
90  /* Step 1 and 2, compute W0: */
91 
92  uint8_t H[20];
93  uint8_t seed_bin[20];
94  /* Convert hexadecimal seed into binary seed */
95  hex2bin(seed, seed_bin);
96  sha1(H, seed_bin, 160);
97  /* c0 = h rightmost bits of H */
98  memcpy(Wprime, H+(20-hbytes), hbytes);
99  uint8_t mask;
100  switch (h%8)
101  {
102  case 0:
103  mask = 0xff;
104  break;
105  case 1:
106  mask = 0x1;
107  break;
108  case 2:
109  mask = 0x3;
110  break;
111  case 3:
112  mask = 0x7;
113  break;
114  case 4:
115  mask = 0xf;
116  break;
117  case 5:
118  mask = 0x1f;
119  break;
120  case 6:
121  mask = 0x3f;
122  break;
123  case 7:
124  mask = 0x7f;
125  break;
126  }
127 
128  Wprime[0]&=mask;
129 
130  /* Step 2 : done with h--*/
131 
132  /* Step 3 and 4 : */
133 
134  uint16_t i;
135  for (i=0; i<s; i++)
136  {
137  drbg_incr_data(seed_bin, 20);
138  sha1(H, seed_bin, 160);
139  memcpy(Wprime+i*20+hbytes, H, 20);
140  }
141 
142  /* Step 5 : Transform Wprime into a field element */
143 
144  /* Convert binary hash into hexadecimal string */
145  unsigned char Wprime_hex[2*(s*20+hbytes)+1];
146  bin2hex(Wprime, s*20+hbytes, Wprime_hex);
147  switch(k->type)
148  {
149  case FP:
150  field_elt_set_str(r1, (const char *)Wprime_hex, 16, false, k, stack);
151  break;
152  case FP2:
153  case FP3:
154  number_set_str(tmp, (const char *)Wprime_hex, 16);
155  field_elt_set_number(r1, false, k, stack, 1, tmp);
156  break;
157  default:
158  field_elt_set_one(r1, k);
159  }
160 
161  /* Step 6 : Accept or reject */
162 
163  int8_t res = field_elt_cmp(r1, E->a, k);
164 
165  number_tmp_free(&tmp, k->size, stack);
166  field_elt_relax_pool_elt(&r1, k, stack);
167  free(Wprime);
168 
169  return (res == 0);
170 }
171 
172 void jacobi_quartic_curve_random_generation(fe_ptr a, char * seed_res, field_srcptr k, uint8_t stack)
173 {
174  /* Source : Working Draft AMERICAN NATIONAL STANDARD X9.62-1998, section A.3.3.2 */
175  bool test;
176  number seed;
177  number bound_h;
178  number bound_l;
179  number_tmp_alloc(&seed, bits_to_nblock(160), stack);
180  number_tmp_alloc(&bound_h, bits_to_nblock(160), stack);
181  number_tmp_alloc(&bound_l, bits_to_nblock(160), stack);
182  number_set_str(bound_h, "ffffffffffffffffffffffffffffffffffffffff", 16); /* 2^161 - 1 */
183  number_set_str(bound_l, "1000000000000000000000000000000000000000", 16); /* 2^160 */
184 
185  field_elt r1;
186  field_elt_get_pool_elt(&r1, (field_ptr)k, stack);
187 
188  number tmp;
189  number_tmp_alloc(&tmp, k->size, stack);
190 
191  char * seed_hex;
192 
193  /* t = log2(p) */
194  uint16_t t;
195  switch(k->type)
196  {
197  case FP:
198  t = number_log2(((fp_param)k->param)->p);
199  break;
200  case FP2:
201  case FP3:
202  t = number_log2(((fp_param)((fp2_param)k->param)->base)->p);
203  break;
204  default:
205  t = 0;
206  }
207  /* s = (t-1) / 160 */
208  uint16_t s = (t-1)/160;
209  /* h = t - 160*s */
210  uint16_t h = t - (160*s);
211  h --; /* set the leftmost bit of c0 to 0 */
212  uint16_t hbytes = (h / 8) + (h%8 != 0);
213 
214  /* Alloc W' */
215  uint8_t * Wprime = calloc(s*20+hbytes, sizeof(uint8_t));
216 
217  do
218  {
219  /* Step 1 : Choose an arbitrary bit string SEED of bit length at least 160 bits */
220  do
221  {
222  number_random1(seed, bound_h, stack);
223  }
224  while(number_cmp(seed, bound_l)<0);
225 
226  number_str(&seed_hex, seed, 16);
227 
228  /* Step 2 and 3, compute W0 : */
229 
230  uint8_t H[20];
231  uint8_t seed_bin[20];
232  /* Convert hexadecimal seed into binary seed */
233  hex2bin(seed_hex, seed_bin);
234  sha1(H, seed_bin, 160);
235  /* c0 = h rightmost bits of H */
236  memcpy(Wprime, H+(20-hbytes), hbytes);
237  uint8_t mask;
238  switch (h%8)
239  {
240  case 0:
241  mask = 0xff;
242  break;
243  case 1:
244  mask = 0x1;
245  break;
246  case 2:
247  mask = 0x3;
248  break;
249  case 3:
250  mask = 0x7;
251  break;
252  case 4:
253  mask = 0xf;
254  break;
255  case 5:
256  mask = 0x1f;
257  break;
258  case 6:
259  mask = 0x3f;
260  break;
261  case 7:
262  mask = 0x7f;
263  break;
264  }
265 
266  Wprime[0]&=mask;
267 
268  /* Step 4 and 5 : */
269 
270  uint16_t i;
271  for (i=0; i<s; i++)
272  {
273  drbg_incr_data(seed_bin, 20);
274  sha1(H, seed_bin, 160);
275  memcpy(Wprime+i*20+hbytes, H, 20);
276  }
277 
278  /* Convert binary hash into hexadecimal string */
279  unsigned char Wprime_hex[2*(s*20+hbytes)+1];
280  bin2hex(Wprime, s*20+hbytes, Wprime_hex);
281 
282  /* Step 6 : Transform Wprime into a field element */
283 
284  switch(k->type)
285  {
286  case FP:
287  field_elt_set_str(r1, (const char *)Wprime_hex, 16, false, k, stack);
288  break;
289  case FP2:
290  case FP3:
291  number_set_str(tmp, (const char *)Wprime_hex, 16);
292  field_elt_set_number(r1, false, k, stack, 1, tmp);
293  break;
294  default:
295  field_elt_set_one(r1, k);
296  }
297 
298  /* Step 7: Choose a = r1 */
299 
300  field_elt_copy(a, r1, k);
301 
302  test = field_elt_isone(a, k);
303  if (test)
304  {
305  free(seed_hex);
306  }
307  }
308  /* Step 8: verifie that the curve is elliptic */
309  while(test);
310 
311  strcpy(seed_res, seed_hex);
312 
313  number_tmp_free(&tmp, k->size, stack);
314  field_elt_relax_pool_elt(&r1, (field_ptr)k, stack);
315  number_tmp_free(&seed, bits_to_nblock(160), stack);
316  number_tmp_free(&bound_h, bits_to_nblock(160), stack);
317  number_tmp_free(&bound_l, bits_to_nblock(160), stack);
318  free(seed_hex);
319  free(Wprime);
320 }
321 
322 void
323 jacobi_quartic_point_set_neutral (ec_point_ptr dst, ec_curve_srcptr E, uint8_t stack)
324 {
325  field_t * k = E->k;
326  field_elt_set_ui(dst->x, 0, true, k, stack);
327  field_elt_set_one(dst->y, k);
328  field_elt_set_ui(dst->t, 0, true, k, stack);
329  field_elt_set_one(dst->z, k);
330 }
331 
332 void
333 jacobi_quartic_point_set_aff (ec_point_ptr P, fe_srcptr x, fe_srcptr y, field_srcptr k, uint8_t stack)
334 {
335  field_elt_copy(P->x, x, k);
336  field_elt_copy(P->y, y, k);
337  field_elt_sqr(P->t, P->x, k, stack);
338  field_elt_set_one(P->z, k);
339 }
340 
341 void
342 jacobi_quartic_point_set_aff_str (ec_point_ptr P, const char *str_x, const char *str_y,
343  const bool is_reduced, const uint8_t base, field_srcptr k, uint8_t stack)
344 {
345  field_elt_set_str(P->x, str_x, base, is_reduced, k, stack);
346  field_elt_set_str(P->y, str_y, base, is_reduced, k, stack);
347  field_elt_sqr(P->t, P->x, k, stack);
348  field_elt_set_one(P->z, k);
349 }
350 
351 bool
352 jacobi_quartic_belongs (ec_point_srcptr P, ec_curve_srcptr E, uint8_t stack)
353 {
354  /* P = (X, Y, T, Z) */
355  /* E: y^2 = z^2 + 2ax^2 + t^2; x^2 = zt; a != 1 (this is for the discriminant) */
356 
357  field_elt f, g, h, u;
358  field_t *k = E->k;
359 
360  field_elt_get_pool_elt(&f, k, stack);
361  field_elt_get_pool_elt(&g, k, stack);
362  field_elt_get_pool_elt(&h, k, stack);
363  field_elt_get_pool_elt(&u, k, stack);
364 
365  field_elt_sqr(f, P->z, k, stack); /* f = Z^2 */
366  field_elt_sqr(g, P->t, k, stack); /* g = T^2 */
367  field_elt_add(h, f, g, k); /* h = Z^2 + T^2 */
368 
369  field_elt_add(f, P->z, P->t, k); /* f = Z + T */
370  field_elt_sqr(g, f, k, stack); /* g = (Z+T)^2 */
371  field_elt_sub(f, g, h, k); /* f = 2.Z.T */
372 
373  field_elt_sqr(u, P->x, k, stack); /* u = X^2 */
374  field_elt_add(g, u, u, k); /* g = 2.X^2 */
375 
376  if (field_elt_cmp(f, g, k) != 0) /* 2*x^2 ?= 2*z*t */
377  {
378  field_elt_relax_pool_elt(&f, k, stack);
379  field_elt_relax_pool_elt(&g, k, stack);
380  field_elt_relax_pool_elt(&h, k, stack);
381  field_elt_relax_pool_elt(&u, k, stack);
382  return false;
383  }
384 
385  field_elt_mul(g, g, E->a, k, stack); /* g = 2.a.X^2 */
386  field_elt_add(f, h, g, k); /* f = Z^2 + 2.a.X^2 + T^2 */
387  field_elt_sqr(h, P->y, k, stack); /* h = Y^2 */
388 
389  if (field_elt_cmp(h, f, k) != 0)
390  {
391  field_elt_relax_pool_elt(&f, k, stack);
392  field_elt_relax_pool_elt(&g, k, stack);
393  field_elt_relax_pool_elt(&h, k, stack);
394  field_elt_relax_pool_elt(&u, k, stack);
395  return false;
396  }
397 
398  field_elt_relax_pool_elt(&f, k, stack);
399  field_elt_relax_pool_elt(&g, k, stack);
400  field_elt_relax_pool_elt(&h, k, stack);
401  field_elt_relax_pool_elt(&u, k, stack);
402 
403  return true;
404 }
405 
406 void
407 jacobi_quartic_point_random (ec_point_ptr P, ec_curve_srcptr E, uint8_t stack)
408 {
409  field_elt f, g;
410  field_t *k = E->k;
411 
412  field_elt_get_pool_elt(&f, k, stack);
413  field_elt_get_pool_elt(&g, k, stack);
414 
415  do {
416  field_elt_random(P->x, k, stack);
417  field_elt_sqr(P->z, P->x, k, stack);
418  field_elt_mul(g, P->z, E->a, k, stack);
419  field_elt_add(g, g, g, k); /* g = 2*a*x^2 */
420  field_elt_inc(f, g, k);
421  field_elt_sqr(g, P->z, k, stack);
422  field_elt_add(g, g, f, k); /* g = z^2 + 2a x^2 + 1 */
423  } while (!field_elt_issquare(g, k, stack));
424  field_elt_sqrt(f, g, k, stack);
425 
426 
427  field_elt_copy(P->y, f, k);
428  field_elt_copy(P->t, P->z, k);
429  field_elt_set_one(P->z,k);
430 
431  field_elt_relax_pool_elt(&f, k, stack);
432  field_elt_relax_pool_elt(&g, k, stack);
433 }
434 
435 void
436 jacobi_quartic_point_norm (ec_point_ptr P, ec_curve_srcptr E, uint8_t stack)
437 {
438  field_t *k = E->k;
439  field_elt u;
440  field_elt_get_pool_elt(&u, k, stack);
441 
442  field_elt_inv(u, P->z, k, stack);
443  field_elt_mul(P->x, P->x, u, k, stack);
444  field_elt_mul(P->y, P->y, u, k, stack);
445  field_elt_sqr(P->t, P->x, k, stack);
446  field_elt_set_one(P->z, k);
447 
448  field_elt_relax_pool_elt(&u, k, stack);
449 }
450 
451 void
452 jacobi_quartic_point_get_x_affine (field_elt x, ec_point_ptr P, ec_curve_srcptr E, uint8_t stack)
453 {
454  field_t *k = E->k;
455  field_elt u;
456  field_elt_get_pool_elt(&u, k, stack);
457 
458  field_elt_inv(u, P->z, k, stack);
459  field_elt_mul(x, P->x, u, k, stack);
460 
461  field_elt_relax_pool_elt(&u, k, stack);
462 }
463 
464 void
465 jacobi_quartic_point_get_y_affine (field_elt y, ec_point_ptr P, ec_curve_srcptr E, uint8_t stack)
466 {
467  field_t *k = E->k;
468  field_elt u;
469  field_elt_get_pool_elt(&u, k, stack);
470 
471  field_elt_inv(u, P->z, k, stack);
472  field_elt_mul(y, P->y, u, k, stack);
473 
474  field_elt_relax_pool_elt(&u, k, stack);
475 }
476 
477 /*******************************COMPARISON************************************/
478 
479 bool
480 jacobi_quartic_point_is_neutral (ec_point_srcptr P, ec_curve_srcptr E)
481 {
482  field_t *k = E->k;
483  return (field_elt_iszero(P->x, k) && field_elt_iszero(P->t, k) &&
484  (field_elt_cmp(P->y, P->z, k) == 0));
485 }
486 
487 bool
488 jacobi_quartic_point_are_equal (ec_point_srcptr P1, ec_point_srcptr P2,
489  ec_curve_srcptr E, uint8_t stack)
490 {
491  field_elt u, v;
492  field_t *k = E->k;
493 
494  if (field_elt_iszero(P1->t, k))
495  {
496  if (!field_elt_iszero(P2->t, k))
497  {
498  return false;
499  }
500  if (field_elt_iszero(P1->y, k))
501  {
502 
503  return field_elt_iszero(P2->y, k);
504  }
505 
506  field_elt_get_pool_elt(&u, k, stack);
507  field_elt_get_pool_elt(&v, k, stack);
508 
509  MPHELL_ASSERT_ALWAYS( field_elt_cmp(P1->x, P1->t, k)==0, "The point P1 is not a point in a system of Extended Homogenous Projective coordinates"); /* In this case x should be equals to 0 */
510  MPHELL_ASSERT_ALWAYS( field_elt_cmp(P2->x, P2->t, k)==0, "The point P2 is not a point in a system of Extended Homogenous Projective coordinates"); /* In this case x should be equals to 0 */
511 
512  field_elt_mul(u, P1->z, P2->y, k, stack);
513  field_elt_mul(v, P1->y, P2->z, k, stack);
514  bool res = (field_elt_cmp(u, v, k) == 0);
515 
516  field_elt_relax_pool_elt(&u, k, stack);
517  field_elt_relax_pool_elt(&v, k, stack);
518  return res;
519  }
520  else
521  {
522  field_elt_get_pool_elt(&u, k, stack);
523  field_elt_get_pool_elt(&v, k, stack);
524 
525  field_elt_mul(u, P1->x, P2->t, k, stack);
526  field_elt_mul(v, P1->t, P2->x, k, stack);
527  if (field_elt_cmp(u, v, k) != 0)
528  {
529  field_elt_relax_pool_elt(&u, k, stack);
530  field_elt_relax_pool_elt(&v, k, stack);
531  return false;
532  }
533  field_elt_mul(u, P1->y, P2->t, k, stack);
534  field_elt_mul(v, P1->t, P2->y, k, stack);
535  bool res = (field_elt_cmp(u, v, k) == 0);
536 
537  field_elt_sqr(u,P1->x, k, stack);
538  field_elt_mul(v,P1->t,P1->z, k, stack);
539  MPHELL_ASSERT_ALWAYS( field_elt_cmp(u, v, k)==0, "The point P1 is not a point in a system of Extended Homogenous Projective coordinates");
540  field_elt_sqr(v,P2->x, k, stack);
541  field_elt_mul(u,P2->t,P2->z, k, stack);
542  MPHELL_ASSERT_ALWAYS( field_elt_cmp(u, v, k)==0, "The point P2 is not a point in a system of Extended Homogenous Projective coordinates");
543 
544  field_elt_relax_pool_elt(&u, k, stack);
545  field_elt_relax_pool_elt(&v, k, stack);
546  return res;
547  }
548 }
549 
550 /*******************************OPERATIONS************************************/
551 
552 void
553 jacobi_quartic_point_neg (ec_point_ptr P3, ec_point_srcptr P1, ec_curve_srcptr E)
554 {
555  field_t *k = E->k;
556  field_elt_neg(P3->x, P1->x, k);
557  field_elt_copy(P3->y, P1->y, k);
558  field_elt_copy(P3->z, P1->z, k);
559  field_elt_copy(P3->t, P1->t, k);
560 }
561 
562 /* UNIFIED => Resistant to SPA */
563 
564 void
565 jacobi_quartic_point_add_unified (ec_point_ptr P3, ec_point_srcptr P1, ec_point_srcptr P2, ec_curve_srcptr E, uint8_t stack)
566 {
567  /* P1 = (X1, Y1, T1, Z1) */
568  /* P2 = (X2, Y2, T2, Z2) */
569  /* P3 = (X3, Y3, T3, Z3) */
570  /* E: y^2 = z^2 + 2ax^2 + t^2; x^2 = zt; a != 1 */
571  /*
572  These formulas are derived from the paper [HKCD09] "Jacobi Quartic Curves Revisited"
573  written by Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter and Ed Dawson published in
574  Australasian Conference on Information Security and Privacy 2009 (pp. 452-468).
575  Springer, Berlin, Heidelberg
576  Costs 8 Mul 2 Sqr 1 *a 13 Add 1*2
577  */
578 
579  field_t *k = E->k;
580 
581  if(jacobi_quartic_point_is_neutral(P1, E))
582  {
583  ec_point_copy(P3, P2, k);
584  }
585  else if(jacobi_quartic_point_is_neutral(P2, E))
586  {
587  ec_point_copy(P3, P1, k);
588  }
589  else
590  {
591  field_elt x, y, z, t;
592  field_elt f, g, h;
593  field_elt u3, v3;
594 
595  field_elt_get_pool_elt(&x, k, stack);
596  field_elt_get_pool_elt(&y, k, stack);
597  field_elt_get_pool_elt(&z, k, stack);
598  field_elt_get_pool_elt(&t, k, stack);
599 
600  field_elt_get_pool_elt(&f, k, stack);
601  field_elt_get_pool_elt(&g, k, stack);
602  field_elt_get_pool_elt(&h, k, stack);
603 
604  field_elt_get_pool_elt(&u3, k, stack);
605  field_elt_get_pool_elt(&v3, k, stack);
606 
607  field_elt_add(z, P1->x, P1->y, k); /* z = X1 + Y1 */
608  field_elt_add(t, P2->x, P2->y, k); /* t = X2 + Y2 */
609  field_elt_mul(v3, z, t, k, stack); /* v3 = (X1+Y1).(X2+Y2) */
610  field_elt_mul(x, P1->x, P2->x, k, stack); /* x = X1.X2 */
611  field_elt_mul(y, P1->y, P2->y, k, stack); /* y = Y1.Y2 */
612  field_elt_sub(v3, v3, x, k); /* v3 = (X1+Y1).(X2+Y2) - X1.X2 */
613  field_elt_sub(v3, v3, y, k); /* v3 = (X1+Y1).(X2+Y2) - X1.X2 - Y1.Y2 = X1.Y2 + X2.Y1 */
614 
615  field_elt_mul(z, P1->z, P2->z, k, stack); /* z = Z1.Z2 */
616  field_elt_mul(t, P1->t, P2->t, k, stack); /* t = T1.T2 */
617  field_elt_sub(u3, z, t, k); /* u3 = Z1.Z2 - T1.T2 */
618 
619  field_elt_add(z,z,t, k); /* z = Z1.Z2 + T1.T2 */
620 
621  field_elt_add(f, P1->z, P1->t, k); /* f = Z1 + T1 */
622  field_elt_add(g, P2->z, P2->t, k); /* g = Z2 + T2 */
623  field_elt_mul(h, f, g, k, stack); /* h = (Z1+T1).(Z2+T2) */
624  field_elt_sub(h,h,z, k); /* h = (Z1+T1).(Z2+T2) - Z1.Z2 - T1.T2 = Z1.T2 + Z2.T1 */
625 
626  field_elt_add(f, h, y, k); /* f = Z1.T2 + Z2.T1 + Y1.Y2 */
627  field_elt_mul2(y, x, k); /* y = 2.X1.X2 */
628  field_elt_mul(h, y, E->a, k, stack); /* h = 2.X1.X2.a */
629  field_elt_add(g, f, h, k); /* g = Z1.T2 + Z2.T1 + Y1.Y2 + 2.X1.X2.a */
630 
631  field_elt_add(f, y, z, k); /* f = 2.X1.X2 + Z1.Z2 + T1.T2 */
632  field_elt_mul(y, f, g, k, stack); /* y = (2.X1.X2 + Z1.Z2 + T1.T2).(Z1.T2 + Z2.T1 + Y1.Y2 + 2.X1.X2.a) */
633 
634  field_elt_sqr(P3->t, v3, k, stack); /* T3 = (X1.Y2 + X2.Y1)^2 */
635  field_elt_sqr(P3->z, u3, k, stack); /* Z3 = (Z1.Z2 - T1.T2)^2 */
636  field_elt_mul(P3->x, u3, v3, k, stack); /* X3 = (Z1.Z2 - T1.T2)*(X1.Y2 + X2.Y1) */
637  field_elt_sub(P3->y, y, P3->t, k); /* Y3 = (2.X1.X2 + Z1.Z2 + T1.T2).(Z1.T2 + Z2.T1 + Y1.Y2 + 2.X1.X2.a) - (X1.Y2 + X2.Y1)^2 */
638 
639  field_elt_relax_pool_elt(&x, k, stack);
640  field_elt_relax_pool_elt(&y, k, stack);
641  field_elt_relax_pool_elt(&z, k, stack);
642  field_elt_relax_pool_elt(&t, k, stack);
643 
644  field_elt_relax_pool_elt(&f, k, stack);
645  field_elt_relax_pool_elt(&g, k, stack);
646  field_elt_relax_pool_elt(&h, k, stack);
647 
648  field_elt_relax_pool_elt(&u3, k, stack);
649  field_elt_relax_pool_elt(&v3, k, stack);
650  }
651 }
652 
653 
654 /* DEDICATED => Not resistant to SPA, but faster
655  * Only the doubling is implemented as dedicated because the dedicated addition is not faster than the unified addition
656  */
657 
658 void
659 jacobi_quartic_point_dbl_dedicated (ec_point_ptr P3, ec_point_srcptr P1, ec_curve_srcptr E, uint8_t stack)
660 {
661  /* P1 = (X1, Y1, T1, Z1) */
662  /* P3 = (X3, Y3, T3, Z3) */
663  /* E: y^2 = z^2 + 2ax^2 + t^2; x^2 = zt; a != 1 */
664 
665  /* X3 = 2.X1.Y1(2.Z1^2 + 2.a.X1^2 - Y1^2) */
666  /* Y3 = 2.Y1^2(Y1^2 - 2.a.X1^2) - (2.Z1^2 + 2.a.X1^2 - Y1^2)^2 */
667  /* Z3 = (2.Z1^2 + 2.a.X1^2 - Y1^2)^2 */
668  /* T3 = (2X1.Y1)^2 */
669 
670  /*
671  These formulas are derived from the paper [HKCD09,ยง3.1]
672  Costs 3 Mul, 5 Sqr, 1 *a, 3 Add, 4*2 */
673 
674  field_elt x12, y12, z12, x1y1, f1, f2, temp1;
675  field_t *k = E->k;
676 
677  field_elt_get_pool_elt(&x12, k, stack);
678  field_elt_get_pool_elt(&y12, k, stack);
679  field_elt_get_pool_elt(&z12, k, stack);
680  field_elt_get_pool_elt(&x1y1, k, stack);
681  field_elt_get_pool_elt(&f1, k, stack);
682  field_elt_get_pool_elt(&f2, k, stack);
683  field_elt_get_pool_elt(&temp1, k, stack);
684 
685  field_elt_sqr(x12, P1->x, k, stack); /* x12 = X1^2 */
686  field_elt_sqr(y12, P1->y, k, stack); /* y12 = Y1^2 */
687  field_elt_sqr(z12, P1->z, k, stack); /* z12 = Z1^2 */
688  field_elt_mul(x1y1, P1->x, P1->y, k, stack); /* x1y1 = X1.Y1 */
689  field_elt_mul2(x1y1, x1y1, k); /* x1y1 = 2.X1.Y1 */
690 
691  field_elt_mul(f1, E->a, x12, k, stack); /* f1 = a.X1^2 */
692  field_elt_mul2(f1, f1, k); /* f1 = 2.a.X1^2 */
693  field_elt_sub(f1, f1, y12, k); /* f1 = 2.a.X1^2 - Y1^2 */
694 
695  field_elt_neg(f2, f1, k); /* f2 = Y1^2 - 2.a.X1^2 */
696 
697  field_elt_mul2(temp1, z12, k); /* temp1 = 2.Z1^2 */
698  field_elt_add(f1, f1, temp1, k); /* f1 = 2.Z1^2 + 2.a.X1^2 - Y1^2 */
699 
700  field_elt_mul(P3->x, x1y1, f1, k, stack); /* X3 = 2.X1.Y1(2.Z1^2 + 2.a.X1^2 - Y1^2) */
701 
702  field_elt_sqr(P3->z, f1, k, stack); /* Z3 = (2.Z1^2 + 2.a.X1^2 - Y1^2)^2 */
703 
704  field_elt_mul2(temp1, y12, k); /* temp1 = 2.Y1^2 */
705  field_elt_mul(P3->y, temp1, f2, k, stack); /* Y3 = 2.Y1^2(Y1^2 - 2.a.X1^2) */
706  field_elt_sub(P3->y, P3->y, P3->z, k); /* Y3 = 2.Y1^2(Y1^2 - 2.a.X1^2) - (2.Z1^2 + 2.a.X1^2 - Y1^2)^2 */
707 
708  field_elt_sqr(P3->t, x1y1, k, stack); /* T3 = (2X1.Y1)^2 */
709 
710  field_elt_relax_pool_elt(&x12, k, stack);
711  field_elt_relax_pool_elt(&y12, k, stack);
712  field_elt_relax_pool_elt(&z12, k, stack);
713  field_elt_relax_pool_elt(&x1y1, k, stack);
714  field_elt_relax_pool_elt(&f1, k, stack);
715  field_elt_relax_pool_elt(&f2, k, stack);
716  field_elt_relax_pool_elt(&temp1, k, stack);
717 }
field_elt
fp_elt * field_elt
Generic field element.
Definition: mphell-field.h:39
ec_point::y
field_elt y
Definition: mphell-curve.h:106
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.
number_log2
uint16_t number_log2(number_srcptr src)
Calculate log2(src), which is the binary size of src.
Definition: mphell-number.c:257
field_t
Define a field.
Definition: mphell-field.h:90
ec_point
Define an elliptic curve point.
Definition: mphell-curve.h:103
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
jacobi_quartic_point_set_neutral
void jacobi_quartic_point_set_neutral(ec_point_ptr dst, ec_curve_srcptr E, uint8_t stack)
Set dst to the neutral element: (0,1,0,1).
Definition: mphell-jacobi.c:323
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
field_t::size
uint8_t size
Definition: mphell-field.h:94
jacobi_quartic_point_get_y_affine
void jacobi_quartic_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-jacobi.c:465
jacobi_quartic_point_are_equal
bool jacobi_quartic_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.
Definition: mphell-jacobi.c:488
field_elt_isone
bool field_elt_isone(fe_srcptr src, field_srcptr k)
Test if src is one.
Definition: mphell-field.c:774
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
jacobi_quartic_point_is_neutral
bool jacobi_quartic_point_is_neutral(ec_point_srcptr P, ec_curve_srcptr E)
Test if P is the neutral element.
Definition: mphell-jacobi.c:480
ec_curve::disc
field_elt disc
Definition: mphell-curve.h:150
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
jacobi_quartic_point_dbl_dedicated
void jacobi_quartic_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-jacobi.c:659
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
jacobi_quartic_point_set_aff_str
void jacobi_quartic_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-jacobi.c:342
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
field_t::param
void * param
Definition: mphell-field.h:92
jacobi_quartic_compute_disc
void jacobi_quartic_compute_disc(ec_curve E, uint8_t stack)
Set the discriminant of E: disc = (2^8).(a^2 - 1)^2.
Definition: mphell-jacobi.c:32
ec_point::z
field_elt z
Definition: mphell-curve.h:107
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
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
jacobi_quartic_point_norm
void jacobi_quartic_point_norm(ec_point_ptr P, ec_curve_srcptr E, uint8_t stack)
Convert a point in extented projective coordinate (X,Y,T,Z) to an affine point (x,...
Definition: mphell-jacobi.c:436
jacobi_quartic_point_set_aff
void jacobi_quartic_point_set_aff(ec_point_ptr P, fe_srcptr x, fe_srcptr y, field_srcptr k, uint8_t stack)
Set dest to the affine point (x,y)
Definition: mphell-jacobi.c:333
jacobi_quartic_point_random
void jacobi_quartic_point_random(ec_point_ptr P, ec_curve_srcptr E, uint8_t stack)
Create a random point P on the elliptic curve E.
Definition: mphell-jacobi.c:407
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
jacobi_quartic_belongs
bool jacobi_quartic_belongs(ec_point_srcptr P, ec_curve_srcptr E, uint8_t stack)
Test if P belongs to E.
Definition: mphell-jacobi.c:352
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
jacobi_quartic_curve_random_generation
void jacobi_quartic_curve_random_generation(fe_ptr a, 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-jacobi.c:172
ec_curve::k
field_ptr k
Definition: mphell-curve.h:142
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
number_cmp
int8_t number_cmp(number_srcptr src1, number_srcptr src2)
Compare src1 and src2.
Definition: mphell-number.c:966
ec_curve
Define an elliptic curve.
Definition: mphell-curve.h:139
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
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
jacobi_quartic_verify_random_generation
bool jacobi_quartic_verify_random_generation(ec_curve E, const char *seed, uint8_t stack)
Test if E if generated from the seed "seed".
Definition: mphell-jacobi.c:54
fp_param_t
Primary field parameters.
mphell-drbg_internal.h
Declaration of the Deterministic Random Bit Generator internal functions.
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
jacobi_quartic_point_add_unified
void jacobi_quartic_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 extended projective coordinate (T=(X^2)/Z), and unified formulae (protection ...
Definition: mphell-jacobi.c:565
jacobi_quartic_point_neg
void jacobi_quartic_point_neg(ec_point_ptr P3, ec_point_srcptr P1, ec_curve_srcptr E)
Set P3 to -P1.
Definition: mphell-jacobi.c:553
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_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
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
jacobi_quartic_point_get_x_affine
void jacobi_quartic_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-jacobi.c:452
ec_curve::D
field_elt D
Definition: mphell-curve.h:151
Generated by   doxygen 1.8.15