Bitcoin Core  27.99.0
P2P Digital Currency
group_impl.h
Go to the documentation of this file.
1 /***********************************************************************
2  * Copyright (c) 2013, 2014 Pieter Wuille *
3  * Distributed under the MIT software license, see the accompanying *
4  * file COPYING or https://www.opensource.org/licenses/mit-license.php.*
5  ***********************************************************************/
6 
7 #ifndef SECP256K1_GROUP_IMPL_H
8 #define SECP256K1_GROUP_IMPL_H
9 
10 #include "field.h"
11 #include "group.h"
12 #include "util.h"
13 
14 /* Begin of section generated by sage/gen_exhaustive_groups.sage. */
15 #define SECP256K1_G_ORDER_7 SECP256K1_GE_CONST(\
16  0x66625d13, 0x317ffe44, 0x63d32cff, 0x1ca02b9b,\
17  0xe5c6d070, 0x50b4b05e, 0x81cc30db, 0xf5166f0a,\
18  0x1e60e897, 0xa7c00c7c, 0x2df53eb6, 0x98274ff4,\
19  0x64252f42, 0x8ca44e17, 0x3b25418c, 0xff4ab0cf\
20 )
21 #define SECP256K1_G_ORDER_13 SECP256K1_GE_CONST(\
22  0xa2482ff8, 0x4bf34edf, 0xa51262fd, 0xe57921db,\
23  0xe0dd2cb7, 0xa5914790, 0xbc71631f, 0xc09704fb,\
24  0x942536cb, 0xa3e49492, 0x3a701cc3, 0xee3e443f,\
25  0xdf182aa9, 0x15b8aa6a, 0x166d3b19, 0xba84b045\
26 )
27 #define SECP256K1_G_ORDER_199 SECP256K1_GE_CONST(\
28  0x7fb07b5c, 0xd07c3bda, 0x553902e2, 0x7a87ea2c,\
29  0x35108a7f, 0x051f41e5, 0xb76abad5, 0x1f2703ad,\
30  0x0a251539, 0x5b4c4438, 0x952a634f, 0xac10dd4d,\
31  0x6d6f4745, 0x98990c27, 0x3a4f3116, 0xd32ff969\
32 )
36 #define SECP256K1_G SECP256K1_GE_CONST(\
37  0x79be667e, 0xf9dcbbac, 0x55a06295, 0xce870b07,\
38  0x029bfcdb, 0x2dce28d9, 0x59f2815b, 0x16f81798,\
39  0x483ada77, 0x26a3c465, 0x5da4fbfc, 0x0e1108a8,\
40  0xfd17b448, 0xa6855419, 0x9c47d08f, 0xfb10d4b8\
41 )
42 /* These exhaustive group test orders and generators are chosen such that:
43  * - The field size is equal to that of secp256k1, so field code is the same.
44  * - The curve equation is of the form y^2=x^3+B for some small constant B.
45  * - The subgroup has a generator 2*P, where P.x is as small as possible.
46  * - The subgroup has size less than 1000 to permit exhaustive testing.
47  * - The subgroup admits an endomorphism of the form lambda*(x,y) == (beta*x,y).
48  */
49 #if defined(EXHAUSTIVE_TEST_ORDER)
50 # if EXHAUSTIVE_TEST_ORDER == 7
51 
53 #define SECP256K1_B 6
54 
55 # elif EXHAUSTIVE_TEST_ORDER == 13
56 
58 #define SECP256K1_B 2
59 
60 # elif EXHAUSTIVE_TEST_ORDER == 199
61 
63 #define SECP256K1_B 4
64 
65 # else
66 # error No known generator for the specified exhaustive test group order.
67 # endif
68 #else
69 
71 #define SECP256K1_B 7
72 
73 #endif
74 /* End of section generated by sage/gen_exhaustive_groups.sage. */
75 
76 static void secp256k1_ge_verify(const secp256k1_ge *a) {
81  VERIFY_CHECK(a->infinity == 0 || a->infinity == 1);
82  (void)a;
83 }
84 
85 static void secp256k1_gej_verify(const secp256k1_gej *a) {
92  VERIFY_CHECK(a->infinity == 0 || a->infinity == 1);
93  (void)a;
94 }
95 
96 /* Set r to the affine coordinates of Jacobian point (a.x, a.y, 1/zi). */
97 static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi) {
98  secp256k1_fe zi2;
99  secp256k1_fe zi3;
102  VERIFY_CHECK(!a->infinity);
103 
104  secp256k1_fe_sqr(&zi2, zi);
105  secp256k1_fe_mul(&zi3, &zi2, zi);
106  secp256k1_fe_mul(&r->x, &a->x, &zi2);
107  secp256k1_fe_mul(&r->y, &a->y, &zi3);
108  r->infinity = a->infinity;
109 
111 }
112 
113 /* Set r to the affine coordinates of Jacobian point (a.x, a.y, 1/zi). */
114 static void secp256k1_ge_set_ge_zinv(secp256k1_ge *r, const secp256k1_ge *a, const secp256k1_fe *zi) {
115  secp256k1_fe zi2;
116  secp256k1_fe zi3;
119  VERIFY_CHECK(!a->infinity);
120 
121  secp256k1_fe_sqr(&zi2, zi);
122  secp256k1_fe_mul(&zi3, &zi2, zi);
123  secp256k1_fe_mul(&r->x, &a->x, &zi2);
124  secp256k1_fe_mul(&r->y, &a->y, &zi3);
125  r->infinity = a->infinity;
126 
128 }
129 
130 static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y) {
133 
134  r->infinity = 0;
135  r->x = *x;
136  r->y = *y;
137 
139 }
140 
143 
144  return a->infinity;
145 }
146 
147 static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a) {
149 
150  *r = *a;
152  secp256k1_fe_negate(&r->y, &r->y, 1);
153 
155 }
156 
158  secp256k1_fe z2, z3;
160 
161  r->infinity = a->infinity;
162  secp256k1_fe_inv(&a->z, &a->z);
163  secp256k1_fe_sqr(&z2, &a->z);
164  secp256k1_fe_mul(&z3, &a->z, &z2);
165  secp256k1_fe_mul(&a->x, &a->x, &z2);
166  secp256k1_fe_mul(&a->y, &a->y, &z3);
167  secp256k1_fe_set_int(&a->z, 1);
168  r->x = a->x;
169  r->y = a->y;
170 
173 }
174 
176  secp256k1_fe z2, z3;
178 
179  if (secp256k1_gej_is_infinity(a)) {
181  return;
182  }
183  r->infinity = 0;
184  secp256k1_fe_inv_var(&a->z, &a->z);
185  secp256k1_fe_sqr(&z2, &a->z);
186  secp256k1_fe_mul(&z3, &a->z, &z2);
187  secp256k1_fe_mul(&a->x, &a->x, &z2);
188  secp256k1_fe_mul(&a->y, &a->y, &z3);
189  secp256k1_fe_set_int(&a->z, 1);
190  secp256k1_ge_set_xy(r, &a->x, &a->y);
191 
194 }
195 
196 static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len) {
197  secp256k1_fe u;
198  size_t i;
199  size_t last_i = SIZE_MAX;
200 #ifdef VERIFY
201  for (i = 0; i < len; i++) {
202  SECP256K1_GEJ_VERIFY(&a[i]);
203  }
204 #endif
205 
206  for (i = 0; i < len; i++) {
207  if (a[i].infinity) {
209  } else {
210  /* Use destination's x coordinates as scratch space */
211  if (last_i == SIZE_MAX) {
212  r[i].x = a[i].z;
213  } else {
214  secp256k1_fe_mul(&r[i].x, &r[last_i].x, &a[i].z);
215  }
216  last_i = i;
217  }
218  }
219  if (last_i == SIZE_MAX) {
220  return;
221  }
222  secp256k1_fe_inv_var(&u, &r[last_i].x);
223 
224  i = last_i;
225  while (i > 0) {
226  i--;
227  if (!a[i].infinity) {
228  secp256k1_fe_mul(&r[last_i].x, &r[i].x, &u);
229  secp256k1_fe_mul(&u, &u, &a[last_i].z);
230  last_i = i;
231  }
232  }
233  VERIFY_CHECK(!a[last_i].infinity);
234  r[last_i].x = u;
235 
236  for (i = 0; i < len; i++) {
237  if (!a[i].infinity) {
238  secp256k1_ge_set_gej_zinv(&r[i], &a[i], &r[i].x);
239  }
240  }
241 
242 #ifdef VERIFY
243  for (i = 0; i < len; i++) {
244  SECP256K1_GE_VERIFY(&r[i]);
245  }
246 #endif
247 }
248 
249 static void secp256k1_ge_table_set_globalz(size_t len, secp256k1_ge *a, const secp256k1_fe *zr) {
250  size_t i;
251  secp256k1_fe zs;
252 #ifdef VERIFY
253  for (i = 0; i < len; i++) {
254  SECP256K1_GE_VERIFY(&a[i]);
255  SECP256K1_FE_VERIFY(&zr[i]);
256  }
257 #endif
258 
259  if (len > 0) {
260  i = len - 1;
261  /* Ensure all y values are in weak normal form for fast negation of points */
263  zs = zr[i];
264 
265  /* Work our way backwards, using the z-ratios to scale the x/y values. */
266  while (i > 0) {
267  if (i != len - 1) {
268  secp256k1_fe_mul(&zs, &zs, &zr[i]);
269  }
270  i--;
271  secp256k1_ge_set_ge_zinv(&a[i], &a[i], &zs);
272  }
273  }
274 
275 #ifdef VERIFY
276  for (i = 0; i < len; i++) {
277  SECP256K1_GE_VERIFY(&a[i]);
278  }
279 #endif
280 }
281 
283  r->infinity = 1;
284  secp256k1_fe_clear(&r->x);
285  secp256k1_fe_clear(&r->y);
286  secp256k1_fe_clear(&r->z);
287 
289 }
290 
292  r->infinity = 1;
293  secp256k1_fe_clear(&r->x);
294  secp256k1_fe_clear(&r->y);
295 
297 }
298 
300  r->infinity = 0;
301  secp256k1_fe_clear(&r->x);
302  secp256k1_fe_clear(&r->y);
303  secp256k1_fe_clear(&r->z);
304 
306 }
307 
309  r->infinity = 0;
310  secp256k1_fe_clear(&r->x);
311  secp256k1_fe_clear(&r->y);
312 
314 }
315 
316 static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd) {
317  secp256k1_fe x2, x3;
318  int ret;
320 
321  r->x = *x;
322  secp256k1_fe_sqr(&x2, x);
323  secp256k1_fe_mul(&x3, x, &x2);
324  r->infinity = 0;
326  ret = secp256k1_fe_sqrt(&r->y, &x3);
328  if (secp256k1_fe_is_odd(&r->y) != odd) {
329  secp256k1_fe_negate(&r->y, &r->y, 1);
330  }
331 
333  return ret;
334 }
335 
338 
339  r->infinity = a->infinity;
340  r->x = a->x;
341  r->y = a->y;
342  secp256k1_fe_set_int(&r->z, 1);
343 
345 }
346 
347 static int secp256k1_gej_eq_var(const secp256k1_gej *a, const secp256k1_gej *b) {
348  secp256k1_gej tmp;
351 
352  secp256k1_gej_neg(&tmp, a);
353  secp256k1_gej_add_var(&tmp, &tmp, b, NULL);
354  return secp256k1_gej_is_infinity(&tmp);
355 }
356 
357 static int secp256k1_gej_eq_ge_var(const secp256k1_gej *a, const secp256k1_ge *b) {
358  secp256k1_gej tmp;
361 
362  secp256k1_gej_neg(&tmp, a);
363  secp256k1_gej_add_ge_var(&tmp, &tmp, b, NULL);
364  return secp256k1_gej_is_infinity(&tmp);
365 }
366 
367 static int secp256k1_ge_eq_var(const secp256k1_ge *a, const secp256k1_ge *b) {
368  secp256k1_fe tmp;
371 
372  if (a->infinity != b->infinity) return 0;
373  if (a->infinity) return 1;
374 
375  tmp = a->x;
377  if (!secp256k1_fe_equal(&tmp, &b->x)) return 0;
378 
379  tmp = a->y;
381  if (!secp256k1_fe_equal(&tmp, &b->y)) return 0;
382 
383  return 1;
384 }
385 
386 static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a) {
387  secp256k1_fe r;
390  VERIFY_CHECK(!a->infinity);
391 
392  secp256k1_fe_sqr(&r, &a->z); secp256k1_fe_mul(&r, &r, x);
393  return secp256k1_fe_equal(&r, &a->x);
394 }
395 
396 static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a) {
398 
399  r->infinity = a->infinity;
400  r->x = a->x;
401  r->y = a->y;
402  r->z = a->z;
404  secp256k1_fe_negate(&r->y, &r->y, 1);
405 
407 }
408 
411 
412  return a->infinity;
413 }
414 
416  secp256k1_fe y2, x3;
418 
419  if (a->infinity) {
420  return 0;
421  }
422  /* y^2 = x^3 + 7 */
423  secp256k1_fe_sqr(&y2, &a->y);
424  secp256k1_fe_sqr(&x3, &a->x); secp256k1_fe_mul(&x3, &x3, &a->x);
426  return secp256k1_fe_equal(&y2, &x3);
427 }
428 
430  /* Operations: 3 mul, 4 sqr, 8 add/half/mul_int/negate */
431  secp256k1_fe l, s, t;
433 
434  r->infinity = a->infinity;
435 
436  /* Formula used:
437  * L = (3/2) * X1^2
438  * S = Y1^2
439  * T = -X1*S
440  * X3 = L^2 + 2*T
441  * Y3 = -(L*(X3 + T) + S^2)
442  * Z3 = Y1*Z1
443  */
444 
445  secp256k1_fe_mul(&r->z, &a->z, &a->y); /* Z3 = Y1*Z1 (1) */
446  secp256k1_fe_sqr(&s, &a->y); /* S = Y1^2 (1) */
447  secp256k1_fe_sqr(&l, &a->x); /* L = X1^2 (1) */
448  secp256k1_fe_mul_int(&l, 3); /* L = 3*X1^2 (3) */
449  secp256k1_fe_half(&l); /* L = 3/2*X1^2 (2) */
450  secp256k1_fe_negate(&t, &s, 1); /* T = -S (2) */
451  secp256k1_fe_mul(&t, &t, &a->x); /* T = -X1*S (1) */
452  secp256k1_fe_sqr(&r->x, &l); /* X3 = L^2 (1) */
453  secp256k1_fe_add(&r->x, &t); /* X3 = L^2 + T (2) */
454  secp256k1_fe_add(&r->x, &t); /* X3 = L^2 + 2*T (3) */
455  secp256k1_fe_sqr(&s, &s); /* S' = S^2 (1) */
456  secp256k1_fe_add(&t, &r->x); /* T' = X3 + T (4) */
457  secp256k1_fe_mul(&r->y, &t, &l); /* Y3 = L*(X3 + T) (1) */
458  secp256k1_fe_add(&r->y, &s); /* Y3 = L*(X3 + T) + S^2 (2) */
459  secp256k1_fe_negate(&r->y, &r->y, 2); /* Y3 = -(L*(X3 + T) + S^2) (3) */
460 
462 }
463 
466 
477  if (a->infinity) {
479  if (rzr != NULL) {
480  secp256k1_fe_set_int(rzr, 1);
481  }
482  return;
483  }
484 
485  if (rzr != NULL) {
486  *rzr = a->y;
488  }
489 
490  secp256k1_gej_double(r, a);
491 
493 }
494 
496  /* 12 mul, 4 sqr, 11 add/negate/normalizes_to_zero (ignoring special cases) */
497  secp256k1_fe z22, z12, u1, u2, s1, s2, h, i, h2, h3, t;
500 
501  if (a->infinity) {
502  VERIFY_CHECK(rzr == NULL);
503  *r = *b;
504  return;
505  }
506  if (b->infinity) {
507  if (rzr != NULL) {
508  secp256k1_fe_set_int(rzr, 1);
509  }
510  *r = *a;
511  return;
512  }
513 
514  secp256k1_fe_sqr(&z22, &b->z);
515  secp256k1_fe_sqr(&z12, &a->z);
516  secp256k1_fe_mul(&u1, &a->x, &z22);
517  secp256k1_fe_mul(&u2, &b->x, &z12);
518  secp256k1_fe_mul(&s1, &a->y, &z22); secp256k1_fe_mul(&s1, &s1, &b->z);
519  secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z);
520  secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
521  secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1);
524  secp256k1_gej_double_var(r, a, rzr);
525  } else {
526  if (rzr != NULL) {
527  secp256k1_fe_set_int(rzr, 0);
528  }
530  }
531  return;
532  }
533 
534  r->infinity = 0;
535  secp256k1_fe_mul(&t, &h, &b->z);
536  if (rzr != NULL) {
537  *rzr = t;
538  }
539  secp256k1_fe_mul(&r->z, &a->z, &t);
540 
541  secp256k1_fe_sqr(&h2, &h);
542  secp256k1_fe_negate(&h2, &h2, 1);
543  secp256k1_fe_mul(&h3, &h2, &h);
544  secp256k1_fe_mul(&t, &u1, &h2);
545 
546  secp256k1_fe_sqr(&r->x, &i);
547  secp256k1_fe_add(&r->x, &h3);
548  secp256k1_fe_add(&r->x, &t);
549  secp256k1_fe_add(&r->x, &t);
550 
551  secp256k1_fe_add(&t, &r->x);
552  secp256k1_fe_mul(&r->y, &t, &i);
553  secp256k1_fe_mul(&h3, &h3, &s1);
554  secp256k1_fe_add(&r->y, &h3);
555 
557 }
558 
560  /* Operations: 8 mul, 3 sqr, 11 add/negate/normalizes_to_zero (ignoring special cases) */
561  secp256k1_fe z12, u1, u2, s1, s2, h, i, h2, h3, t;
564 
565  if (a->infinity) {
566  VERIFY_CHECK(rzr == NULL);
567  secp256k1_gej_set_ge(r, b);
568  return;
569  }
570  if (b->infinity) {
571  if (rzr != NULL) {
572  secp256k1_fe_set_int(rzr, 1);
573  }
574  *r = *a;
575  return;
576  }
577 
578  secp256k1_fe_sqr(&z12, &a->z);
579  u1 = a->x;
580  secp256k1_fe_mul(&u2, &b->x, &z12);
581  s1 = a->y;
582  secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z);
584  secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1);
587  secp256k1_gej_double_var(r, a, rzr);
588  } else {
589  if (rzr != NULL) {
590  secp256k1_fe_set_int(rzr, 0);
591  }
593  }
594  return;
595  }
596 
597  r->infinity = 0;
598  if (rzr != NULL) {
599  *rzr = h;
600  }
601  secp256k1_fe_mul(&r->z, &a->z, &h);
602 
603  secp256k1_fe_sqr(&h2, &h);
604  secp256k1_fe_negate(&h2, &h2, 1);
605  secp256k1_fe_mul(&h3, &h2, &h);
606  secp256k1_fe_mul(&t, &u1, &h2);
607 
608  secp256k1_fe_sqr(&r->x, &i);
609  secp256k1_fe_add(&r->x, &h3);
610  secp256k1_fe_add(&r->x, &t);
611  secp256k1_fe_add(&r->x, &t);
612 
613  secp256k1_fe_add(&t, &r->x);
614  secp256k1_fe_mul(&r->y, &t, &i);
615  secp256k1_fe_mul(&h3, &h3, &s1);
616  secp256k1_fe_add(&r->y, &h3);
617 
619  if (rzr != NULL) SECP256K1_FE_VERIFY(rzr);
620 }
621 
622 static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, const secp256k1_fe *bzinv) {
623  /* Operations: 9 mul, 3 sqr, 11 add/negate/normalizes_to_zero (ignoring special cases) */
624  secp256k1_fe az, z12, u1, u2, s1, s2, h, i, h2, h3, t;
627  SECP256K1_FE_VERIFY(bzinv);
628 
629  if (a->infinity) {
630  secp256k1_fe bzinv2, bzinv3;
631  r->infinity = b->infinity;
632  secp256k1_fe_sqr(&bzinv2, bzinv);
633  secp256k1_fe_mul(&bzinv3, &bzinv2, bzinv);
634  secp256k1_fe_mul(&r->x, &b->x, &bzinv2);
635  secp256k1_fe_mul(&r->y, &b->y, &bzinv3);
636  secp256k1_fe_set_int(&r->z, 1);
638  return;
639  }
640  if (b->infinity) {
641  *r = *a;
642  return;
643  }
644 
653  secp256k1_fe_mul(&az, &a->z, bzinv);
654 
655  secp256k1_fe_sqr(&z12, &az);
656  u1 = a->x;
657  secp256k1_fe_mul(&u2, &b->x, &z12);
658  s1 = a->y;
659  secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &az);
661  secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1);
664  secp256k1_gej_double_var(r, a, NULL);
665  } else {
667  }
668  return;
669  }
670 
671  r->infinity = 0;
672  secp256k1_fe_mul(&r->z, &a->z, &h);
673 
674  secp256k1_fe_sqr(&h2, &h);
675  secp256k1_fe_negate(&h2, &h2, 1);
676  secp256k1_fe_mul(&h3, &h2, &h);
677  secp256k1_fe_mul(&t, &u1, &h2);
678 
679  secp256k1_fe_sqr(&r->x, &i);
680  secp256k1_fe_add(&r->x, &h3);
681  secp256k1_fe_add(&r->x, &t);
682  secp256k1_fe_add(&r->x, &t);
683 
684  secp256k1_fe_add(&t, &r->x);
685  secp256k1_fe_mul(&r->y, &t, &i);
686  secp256k1_fe_mul(&h3, &h3, &s1);
687  secp256k1_fe_add(&r->y, &h3);
688 
690 }
691 
692 
693 static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b) {
694  /* Operations: 7 mul, 5 sqr, 21 add/cmov/half/mul_int/negate/normalizes_to_zero */
695  secp256k1_fe zz, u1, u2, s1, s2, t, tt, m, n, q, rr;
696  secp256k1_fe m_alt, rr_alt;
697  int degenerate;
700  VERIFY_CHECK(!b->infinity);
701 
702  /* In:
703  * Eric Brier and Marc Joye, Weierstrass Elliptic Curves and Side-Channel Attacks.
704  * In D. Naccache and P. Paillier, Eds., Public Key Cryptography, vol. 2274 of Lecture Notes in Computer Science, pages 335-345. Springer-Verlag, 2002.
705  * we find as solution for a unified addition/doubling formula:
706  * lambda = ((x1 + x2)^2 - x1 * x2 + a) / (y1 + y2), with a = 0 for secp256k1's curve equation.
707  * x3 = lambda^2 - (x1 + x2)
708  * 2*y3 = lambda * (x1 + x2 - 2 * x3) - (y1 + y2).
709  *
710  * Substituting x_i = Xi / Zi^2 and yi = Yi / Zi^3, for i=1,2,3, gives:
711  * U1 = X1*Z2^2, U2 = X2*Z1^2
712  * S1 = Y1*Z2^3, S2 = Y2*Z1^3
713  * Z = Z1*Z2
714  * T = U1+U2
715  * M = S1+S2
716  * Q = -T*M^2
717  * R = T^2-U1*U2
718  * X3 = R^2+Q
719  * Y3 = -(R*(2*X3+Q)+M^4)/2
720  * Z3 = M*Z
721  * (Note that the paper uses xi = Xi / Zi and yi = Yi / Zi instead.)
722  *
723  * This formula has the benefit of being the same for both addition
724  * of distinct points and doubling. However, it breaks down in the
725  * case that either point is infinity, or that y1 = -y2. We handle
726  * these cases in the following ways:
727  *
728  * - If b is infinity we simply bail by means of a VERIFY_CHECK.
729  *
730  * - If a is infinity, we detect this, and at the end of the
731  * computation replace the result (which will be meaningless,
732  * but we compute to be constant-time) with b.x : b.y : 1.
733  *
734  * - If a = -b, we have y1 = -y2, which is a degenerate case.
735  * But here the answer is infinity, so we simply set the
736  * infinity flag of the result, overriding the computed values
737  * without even needing to cmov.
738  *
739  * - If y1 = -y2 but x1 != x2, which does occur thanks to certain
740  * properties of our curve (specifically, 1 has nontrivial cube
741  * roots in our field, and the curve equation has no x coefficient)
742  * then the answer is not infinity but also not given by the above
743  * equation. In this case, we cmov in place an alternate expression
744  * for lambda. Specifically (y1 - y2)/(x1 - x2). Where both these
745  * expressions for lambda are defined, they are equal, and can be
746  * obtained from each other by multiplication by (y1 + y2)/(y1 + y2)
747  * then substitution of x^3 + 7 for y^2 (using the curve equation).
748  * For all pairs of nonzero points (a, b) at least one is defined,
749  * so this covers everything.
750  */
751 
752  secp256k1_fe_sqr(&zz, &a->z); /* z = Z1^2 */
753  u1 = a->x; /* u1 = U1 = X1*Z2^2 (GEJ_X_M) */
754  secp256k1_fe_mul(&u2, &b->x, &zz); /* u2 = U2 = X2*Z1^2 (1) */
755  s1 = a->y; /* s1 = S1 = Y1*Z2^3 (GEJ_Y_M) */
756  secp256k1_fe_mul(&s2, &b->y, &zz); /* s2 = Y2*Z1^2 (1) */
757  secp256k1_fe_mul(&s2, &s2, &a->z); /* s2 = S2 = Y2*Z1^3 (1) */
758  t = u1; secp256k1_fe_add(&t, &u2); /* t = T = U1+U2 (GEJ_X_M+1) */
759  m = s1; secp256k1_fe_add(&m, &s2); /* m = M = S1+S2 (GEJ_Y_M+1) */
760  secp256k1_fe_sqr(&rr, &t); /* rr = T^2 (1) */
761  secp256k1_fe_negate(&m_alt, &u2, 1); /* Malt = -X2*Z1^2 (2) */
762  secp256k1_fe_mul(&tt, &u1, &m_alt); /* tt = -U1*U2 (1) */
763  secp256k1_fe_add(&rr, &tt); /* rr = R = T^2-U1*U2 (2) */
764  /* If lambda = R/M = R/0 we have a problem (except in the "trivial"
765  * case that Z = z1z2 = 0, and this is special-cased later on). */
766  degenerate = secp256k1_fe_normalizes_to_zero(&m);
767  /* This only occurs when y1 == -y2 and x1^3 == x2^3, but x1 != x2.
768  * This means either x1 == beta*x2 or beta*x1 == x2, where beta is
769  * a nontrivial cube root of one. In either case, an alternate
770  * non-indeterminate expression for lambda is (y1 - y2)/(x1 - x2),
771  * so we set R/M equal to this. */
772  rr_alt = s1;
773  secp256k1_fe_mul_int(&rr_alt, 2); /* rr_alt = Y1*Z2^3 - Y2*Z1^3 (GEJ_Y_M*2) */
774  secp256k1_fe_add(&m_alt, &u1); /* Malt = X1*Z2^2 - X2*Z1^2 (GEJ_X_M+2) */
775 
776  secp256k1_fe_cmov(&rr_alt, &rr, !degenerate); /* rr_alt (GEJ_Y_M*2) */
777  secp256k1_fe_cmov(&m_alt, &m, !degenerate); /* m_alt (GEJ_X_M+2) */
778  /* Now Ralt / Malt = lambda and is guaranteed not to be Ralt / 0.
779  * From here on out Ralt and Malt represent the numerator
780  * and denominator of lambda; R and M represent the explicit
781  * expressions x1^2 + x2^2 + x1x2 and y1 + y2. */
782  secp256k1_fe_sqr(&n, &m_alt); /* n = Malt^2 (1) */
783  secp256k1_fe_negate(&q, &t,
784  SECP256K1_GEJ_X_MAGNITUDE_MAX + 1); /* q = -T (GEJ_X_M+2) */
785  secp256k1_fe_mul(&q, &q, &n); /* q = Q = -T*Malt^2 (1) */
786  /* These two lines use the observation that either M == Malt or M == 0,
787  * so M^3 * Malt is either Malt^4 (which is computed by squaring), or
788  * zero (which is "computed" by cmov). So the cost is one squaring
789  * versus two multiplications. */
790  secp256k1_fe_sqr(&n, &n); /* n = Malt^4 (1) */
791  secp256k1_fe_cmov(&n, &m, degenerate); /* n = M^3 * Malt (GEJ_Y_M+1) */
792  secp256k1_fe_sqr(&t, &rr_alt); /* t = Ralt^2 (1) */
793  secp256k1_fe_mul(&r->z, &a->z, &m_alt); /* r->z = Z3 = Malt*Z (1) */
794  secp256k1_fe_add(&t, &q); /* t = Ralt^2 + Q (2) */
795  r->x = t; /* r->x = X3 = Ralt^2 + Q (2) */
796  secp256k1_fe_mul_int(&t, 2); /* t = 2*X3 (4) */
797  secp256k1_fe_add(&t, &q); /* t = 2*X3 + Q (5) */
798  secp256k1_fe_mul(&t, &t, &rr_alt); /* t = Ralt*(2*X3 + Q) (1) */
799  secp256k1_fe_add(&t, &n); /* t = Ralt*(2*X3 + Q) + M^3*Malt (GEJ_Y_M+2) */
800  secp256k1_fe_negate(&r->y, &t,
801  SECP256K1_GEJ_Y_MAGNITUDE_MAX + 2); /* r->y = -(Ralt*(2*X3 + Q) + M^3*Malt) (GEJ_Y_M+3) */
802  secp256k1_fe_half(&r->y); /* r->y = Y3 = -(Ralt*(2*X3 + Q) + M^3*Malt)/2 ((GEJ_Y_M+3)/2 + 1) */
803 
804  /* In case a->infinity == 1, replace r with (b->x, b->y, 1). */
805  secp256k1_fe_cmov(&r->x, &b->x, a->infinity);
806  secp256k1_fe_cmov(&r->y, &b->y, a->infinity);
808 
809  /* Set r->infinity if r->z is 0.
810  *
811  * If a->infinity is set, then r->infinity = (r->z == 0) = (1 == 0) = false,
812  * which is correct because the function assumes that b is not infinity.
813  *
814  * Now assume !a->infinity. This implies Z = Z1 != 0.
815  *
816  * Case y1 = -y2:
817  * In this case we could have a = -b, namely if x1 = x2.
818  * We have degenerate = true, r->z = (x1 - x2) * Z.
819  * Then r->infinity = ((x1 - x2)Z == 0) = (x1 == x2) = (a == -b).
820  *
821  * Case y1 != -y2:
822  * In this case, we can't have a = -b.
823  * We have degenerate = false, r->z = (y1 + y2) * Z.
824  * Then r->infinity = ((y1 + y2)Z == 0) = (y1 == -y2) = false. */
826 
828 }
829 
831  /* Operations: 4 mul, 1 sqr */
832  secp256k1_fe zz;
836 
837  secp256k1_fe_sqr(&zz, s);
838  secp256k1_fe_mul(&r->x, &r->x, &zz); /* r->x *= s^2 */
839  secp256k1_fe_mul(&r->y, &r->y, &zz);
840  secp256k1_fe_mul(&r->y, &r->y, s); /* r->y *= s^3 */
841  secp256k1_fe_mul(&r->z, &r->z, s); /* r->z *= s */
842 
844 }
845 
847  secp256k1_fe x, y;
849  VERIFY_CHECK(!a->infinity);
850 
851  x = a->x;
853  y = a->y;
855  secp256k1_fe_to_storage(&r->x, &x);
856  secp256k1_fe_to_storage(&r->y, &y);
857 }
858 
860  secp256k1_fe_from_storage(&r->x, &a->x);
861  secp256k1_fe_from_storage(&r->y, &a->y);
862  r->infinity = 0;
863 
865 }
866 
867 static SECP256K1_INLINE void secp256k1_gej_cmov(secp256k1_gej *r, const secp256k1_gej *a, int flag) {
870 
871  secp256k1_fe_cmov(&r->x, &a->x, flag);
872  secp256k1_fe_cmov(&r->y, &a->y, flag);
873  secp256k1_fe_cmov(&r->z, &a->z, flag);
874  r->infinity ^= (r->infinity ^ a->infinity) & flag;
875 
877 }
878 
880  secp256k1_fe_storage_cmov(&r->x, &a->x, flag);
881  secp256k1_fe_storage_cmov(&r->y, &a->y, flag);
882 }
883 
886 
887  *r = *a;
889 
891 }
892 
894 #ifdef EXHAUSTIVE_TEST_ORDER
896  int i;
898 
899  /* A very simple EC multiplication ladder that avoids a dependency on ecmult. */
901  for (i = 0; i < 32; ++i) {
902  secp256k1_gej_double_var(&out, &out, NULL);
903  if ((((uint32_t)EXHAUSTIVE_TEST_ORDER) >> (31 - i)) & 1) {
904  secp256k1_gej_add_ge_var(&out, &out, ge, NULL);
905  }
906  }
908 #else
910 
911  (void)ge;
912  /* The real secp256k1 group has cofactor 1, so the subgroup is the entire curve. */
913  return 1;
914 #endif
915 }
916 
918  secp256k1_fe c;
919  secp256k1_fe_sqr(&c, x);
920  secp256k1_fe_mul(&c, &c, x);
922  return secp256k1_fe_is_square_var(&c);
923 }
924 
926  /* We want to determine whether (xn/xd) is on the curve.
927  *
928  * (xn/xd)^3 + 7 is square <=> xd*xn^3 + 7*xd^4 is square (multiplying by xd^4, a square).
929  */
930  secp256k1_fe r, t;
932 
933  secp256k1_fe_mul(&r, xd, xn); /* r = xd*xn */
934  secp256k1_fe_sqr(&t, xn); /* t = xn^2 */
935  secp256k1_fe_mul(&r, &r, &t); /* r = xd*xn^3 */
936  secp256k1_fe_sqr(&t, xd); /* t = xd^2 */
937  secp256k1_fe_sqr(&t, &t); /* t = xd^4 */
938  VERIFY_CHECK(SECP256K1_B <= 31);
939  secp256k1_fe_mul_int(&t, SECP256K1_B); /* t = 7*xd^4 */
940  secp256k1_fe_add(&r, &t); /* r = xd*xn^3 + 7*xd^4 */
941  return secp256k1_fe_is_square_var(&r);
942 }
943 
944 #endif /* SECP256K1_GROUP_IMPL_H */
int ret
#define secp256k1_fe_cmov
Definition: field.h:96
#define secp256k1_fe_negate(r, a, m)
Negate a field element.
Definition: field.h:216
#define secp256k1_fe_mul_int(r, a)
Multiply a field element with a small integer.
Definition: field.h:238
#define secp256k1_fe_normalizes_to_zero_var
Definition: field.h:82
#define secp256k1_fe_normalize_weak
Definition: field.h:79
static const secp256k1_fe secp256k1_const_beta
Definition: field.h:69
#define secp256k1_fe_is_odd
Definition: field.h:86
#define SECP256K1_FE_VERIFY_MAGNITUDE(a, m)
Definition: field.h:353
#define secp256k1_fe_mul
Definition: field.h:94
static const secp256k1_fe secp256k1_fe_one
Definition: field.h:68
static int secp256k1_fe_sqrt(secp256k1_fe *SECP256K1_RESTRICT r, const secp256k1_fe *SECP256K1_RESTRICT a)
Compute a square root of a field element.
#define secp256k1_fe_add
Definition: field.h:93
#define secp256k1_fe_clear
Definition: field.h:84
#define secp256k1_fe_normalize_var
Definition: field.h:80
#define secp256k1_fe_half
Definition: field.h:102
#define secp256k1_fe_to_storage
Definition: field.h:97
#define secp256k1_fe_inv_var
Definition: field.h:100
#define SECP256K1_FE_VERIFY(a)
Definition: field.h:349
#define secp256k1_fe_is_square_var
Definition: field.h:104
#define secp256k1_fe_from_storage
Definition: field.h:98
#define secp256k1_fe_normalizes_to_zero
Definition: field.h:81
#define secp256k1_fe_inv
Definition: field.h:99
#define secp256k1_fe_sqr
Definition: field.h:95
#define secp256k1_fe_normalize
Definition: field.h:78
static int secp256k1_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b)
Determine whether two field elements are equal.
static void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_fe_storage *a, int flag)
If flag is true, set *r equal to *a; otherwise leave it.
#define secp256k1_fe_add_int
Definition: field.h:103
#define secp256k1_fe_set_int
Definition: field.h:83
#define SECP256K1_GE_X_MAGNITUDE_MAX
Maximum allowed magnitudes for group element coordinates in affine (x, y) and jacobian (x,...
Definition: group.h:49
#define SECP256K1_GEJ_VERIFY(a)
Definition: group.h:194
#define SECP256K1_GEJ_Y_MAGNITUDE_MAX
Definition: group.h:52
#define SECP256K1_GE_Y_MAGNITUDE_MAX
Definition: group.h:50
#define SECP256K1_GEJ_Z_MAGNITUDE_MAX
Definition: group.h:53
#define SECP256K1_GE_VERIFY(a)
Definition: group.h:190
#define SECP256K1_GEJ_X_MAGNITUDE_MAX
Definition: group.h:51
static int secp256k1_gej_eq_var(const secp256k1_gej *a, const secp256k1_gej *b)
Definition: group_impl.h:347
static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr)
Definition: group_impl.h:464
static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, const secp256k1_fe *bzinv)
Definition: group_impl.h:622
#define SECP256K1_G_ORDER_13
Definition: group_impl.h:21
static void secp256k1_gej_clear(secp256k1_gej *r)
Definition: group_impl.h:299
static void secp256k1_ge_mul_lambda(secp256k1_ge *r, const secp256k1_ge *a)
Definition: group_impl.h:884
static void secp256k1_gej_set_infinity(secp256k1_gej *r)
Definition: group_impl.h:282
static int secp256k1_gej_is_infinity(const secp256k1_gej *a)
Definition: group_impl.h:409
static void secp256k1_ge_clear(secp256k1_ge *r)
Definition: group_impl.h:308
static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y)
Definition: group_impl.h:130
static void secp256k1_gej_verify(const secp256k1_gej *a)
Definition: group_impl.h:85
static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd)
Definition: group_impl.h:316
static void secp256k1_ge_verify(const secp256k1_ge *a)
Definition: group_impl.h:76
static int secp256k1_ge_eq_var(const secp256k1_ge *a, const secp256k1_ge *b)
Definition: group_impl.h:367
static int secp256k1_ge_x_on_curve_var(const secp256k1_fe *x)
Definition: group_impl.h:917
static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, secp256k1_fe *rzr)
Definition: group_impl.h:559
static SECP256K1_INLINE void secp256k1_gej_cmov(secp256k1_gej *r, const secp256k1_gej *a, int flag)
Definition: group_impl.h:867
static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b)
Definition: group_impl.h:693
#define SECP256K1_G
Generator for secp256k1, value 'g' defined in "Standards for Efficient Cryptography" (SEC2) 2....
Definition: group_impl.h:36
static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi)
Definition: group_impl.h:97
#define SECP256K1_B
Definition: group_impl.h:71
static int secp256k1_gej_eq_ge_var(const secp256k1_gej *a, const secp256k1_ge *b)
Definition: group_impl.h:357
static int secp256k1_ge_is_valid_var(const secp256k1_ge *a)
Definition: group_impl.h:415
static void secp256k1_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storage *a)
Definition: group_impl.h:859
static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr)
Definition: group_impl.h:495
static int secp256k1_ge_x_frac_on_curve_var(const secp256k1_fe *xn, const secp256k1_fe *xd)
Definition: group_impl.h:925
static void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *s)
Definition: group_impl.h:830
static void secp256k1_ge_set_ge_zinv(secp256k1_ge *r, const secp256k1_ge *a, const secp256k1_fe *zi)
Definition: group_impl.h:114
static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a)
Definition: group_impl.h:386
#define SECP256K1_G_ORDER_7
Definition: group_impl.h:15
static void secp256k1_ge_set_gej(secp256k1_ge *r, secp256k1_gej *a)
Definition: group_impl.h:157
static int secp256k1_ge_is_in_correct_subgroup(const secp256k1_ge *ge)
Definition: group_impl.h:893
static void secp256k1_ge_table_set_globalz(size_t len, secp256k1_ge *a, const secp256k1_fe *zr)
Definition: group_impl.h:249
static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a)
Definition: group_impl.h:147
static const secp256k1_ge secp256k1_ge_const_g
Definition: group_impl.h:70
static int secp256k1_ge_is_infinity(const secp256k1_ge *a)
Definition: group_impl.h:141
static void secp256k1_ge_set_infinity(secp256k1_ge *r)
Definition: group_impl.h:291
static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len)
Definition: group_impl.h:196
static void secp256k1_gej_set_ge(secp256k1_gej *r, const secp256k1_ge *a)
Definition: group_impl.h:336
static void secp256k1_ge_to_storage(secp256k1_ge_storage *r, const secp256k1_ge *a)
Definition: group_impl.h:846
static SECP256K1_INLINE void secp256k1_ge_storage_cmov(secp256k1_ge_storage *r, const secp256k1_ge_storage *a, int flag)
Definition: group_impl.h:879
#define SECP256K1_G_ORDER_199
Definition: group_impl.h:27
static void secp256k1_ge_set_gej_var(secp256k1_ge *r, secp256k1_gej *a)
Definition: group_impl.h:175
static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a)
Definition: group_impl.h:396
static SECP256K1_INLINE void secp256k1_gej_double(secp256k1_gej *r, const secp256k1_gej *a)
Definition: group_impl.h:429
#define SECP256K1_INLINE
Definition: util.h:48
#define VERIFY_CHECK(cond)
Definition: util.h:139
This field implementation represents the value as 10 uint32_t limbs in base 2^26.
Definition: field_10x26.h:14
secp256k1_fe_storage x
Definition: group.h:39
secp256k1_fe_storage y
Definition: group.h:40
A group element in affine coordinates on the secp256k1 curve, or occasionally on an isomorphic curve ...
Definition: group.h:16
int infinity
Definition: group.h:19
secp256k1_fe x
Definition: group.h:17
secp256k1_fe y
Definition: group.h:18
A group element of the secp256k1 curve, in jacobian coordinates.
Definition: group.h:28
secp256k1_fe y
Definition: group.h:30
secp256k1_fe x
Definition: group.h:29
int infinity
Definition: group.h:32
secp256k1_fe z
Definition: group.h:31
#define EXHAUSTIVE_TEST_ORDER