Bitcoin Core  24.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 
13 #define SECP256K1_G_ORDER_13 SECP256K1_GE_CONST(\
14  0xc3459c3d, 0x35326167, 0xcd86cce8, 0x07a2417f,\
15  0x5b8bd567, 0xde8538ee, 0x0d507b0c, 0xd128f5bb,\
16  0x8e467fec, 0xcd30000a, 0x6cc1184e, 0x25d382c2,\
17  0xa2f4494e, 0x2fbe9abc, 0x8b64abac, 0xd005fb24\
18 )
19 #define SECP256K1_G_ORDER_199 SECP256K1_GE_CONST(\
20  0x226e653f, 0xc8df7744, 0x9bacbf12, 0x7d1dcbf9,\
21  0x87f05b2a, 0xe7edbd28, 0x1f564575, 0xc48dcf18,\
22  0xa13872c2, 0xe933bb17, 0x5d9ffd5b, 0xb5b6e10c,\
23  0x57fe3c00, 0xbaaaa15a, 0xe003ec3e, 0x9c269bae\
24 )
28 #define SECP256K1_G SECP256K1_GE_CONST(\
29  0x79BE667EUL, 0xF9DCBBACUL, 0x55A06295UL, 0xCE870B07UL,\
30  0x029BFCDBUL, 0x2DCE28D9UL, 0x59F2815BUL, 0x16F81798UL,\
31  0x483ADA77UL, 0x26A3C465UL, 0x5DA4FBFCUL, 0x0E1108A8UL,\
32  0xFD17B448UL, 0xA6855419UL, 0x9C47D08FUL, 0xFB10D4B8UL\
33 )
34 /* These exhaustive group test orders and generators are chosen such that:
35  * - The field size is equal to that of secp256k1, so field code is the same.
36  * - The curve equation is of the form y^2=x^3+B for some constant B.
37  * - The subgroup has a generator 2*P, where P.x=1.
38  * - The subgroup has size less than 1000 to permit exhaustive testing.
39  * - The subgroup admits an endomorphism of the form lambda*(x,y) == (beta*x,y).
40  *
41  * These parameters are generated using sage/gen_exhaustive_groups.sage.
42  */
43 #if defined(EXHAUSTIVE_TEST_ORDER)
44 # if EXHAUSTIVE_TEST_ORDER == 13
46 
48  0x3d3486b2, 0x159a9ca5, 0xc75638be, 0xb23a69bc,
49  0x946a45ab, 0x24801247, 0xb4ed2b8e, 0x26b6a417
50 );
51 # elif EXHAUSTIVE_TEST_ORDER == 199
53 
55  0x2cca28fa, 0xfc614b80, 0x2a3db42b, 0x00ba00b1,
56  0xbea8d943, 0xdace9ab2, 0x9536daea, 0x0074defb
57 );
58 # else
59 # error No known generator for the specified exhaustive test group order.
60 # endif
61 #else
63 
64 static const secp256k1_fe secp256k1_fe_const_b = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 7);
65 #endif
66 
67 static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi) {
68  secp256k1_fe zi2;
69  secp256k1_fe zi3;
71  secp256k1_fe_sqr(&zi2, zi);
72  secp256k1_fe_mul(&zi3, &zi2, zi);
73  secp256k1_fe_mul(&r->x, &a->x, &zi2);
74  secp256k1_fe_mul(&r->y, &a->y, &zi3);
75  r->infinity = a->infinity;
76 }
77 
78 static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y) {
79  r->infinity = 0;
80  r->x = *x;
81  r->y = *y;
82 }
83 
84 static int secp256k1_ge_is_infinity(const secp256k1_ge *a) {
85  return a->infinity;
86 }
87 
88 static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a) {
89  *r = *a;
91  secp256k1_fe_negate(&r->y, &r->y, 1);
92 }
93 
95  secp256k1_fe z2, z3;
96  r->infinity = a->infinity;
97  secp256k1_fe_inv(&a->z, &a->z);
98  secp256k1_fe_sqr(&z2, &a->z);
99  secp256k1_fe_mul(&z3, &a->z, &z2);
100  secp256k1_fe_mul(&a->x, &a->x, &z2);
101  secp256k1_fe_mul(&a->y, &a->y, &z3);
102  secp256k1_fe_set_int(&a->z, 1);
103  r->x = a->x;
104  r->y = a->y;
105 }
106 
108  secp256k1_fe z2, z3;
109  if (a->infinity) {
111  return;
112  }
113  secp256k1_fe_inv_var(&a->z, &a->z);
114  secp256k1_fe_sqr(&z2, &a->z);
115  secp256k1_fe_mul(&z3, &a->z, &z2);
116  secp256k1_fe_mul(&a->x, &a->x, &z2);
117  secp256k1_fe_mul(&a->y, &a->y, &z3);
118  secp256k1_fe_set_int(&a->z, 1);
119  secp256k1_ge_set_xy(r, &a->x, &a->y);
120 }
121 
122 static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len) {
123  secp256k1_fe u;
124  size_t i;
125  size_t last_i = SIZE_MAX;
126 
127  for (i = 0; i < len; i++) {
128  if (a[i].infinity) {
130  } else {
131  /* Use destination's x coordinates as scratch space */
132  if (last_i == SIZE_MAX) {
133  r[i].x = a[i].z;
134  } else {
135  secp256k1_fe_mul(&r[i].x, &r[last_i].x, &a[i].z);
136  }
137  last_i = i;
138  }
139  }
140  if (last_i == SIZE_MAX) {
141  return;
142  }
143  secp256k1_fe_inv_var(&u, &r[last_i].x);
144 
145  i = last_i;
146  while (i > 0) {
147  i--;
148  if (!a[i].infinity) {
149  secp256k1_fe_mul(&r[last_i].x, &r[i].x, &u);
150  secp256k1_fe_mul(&u, &u, &a[last_i].z);
151  last_i = i;
152  }
153  }
154  VERIFY_CHECK(!a[last_i].infinity);
155  r[last_i].x = u;
156 
157  for (i = 0; i < len; i++) {
158  if (!a[i].infinity) {
159  secp256k1_ge_set_gej_zinv(&r[i], &a[i], &r[i].x);
160  }
161  }
162 }
163 
164 static void secp256k1_ge_table_set_globalz(size_t len, secp256k1_ge *a, const secp256k1_fe *zr) {
165  size_t i = len - 1;
166  secp256k1_fe zs;
167 
168  if (len > 0) {
169  /* Ensure all y values are in weak normal form for fast negation of points */
171  zs = zr[i];
172 
173  /* Work our way backwards, using the z-ratios to scale the x/y values. */
174  while (i > 0) {
175  secp256k1_gej tmpa;
176  if (i != len - 1) {
177  secp256k1_fe_mul(&zs, &zs, &zr[i]);
178  }
179  i--;
180  tmpa.x = a[i].x;
181  tmpa.y = a[i].y;
182  tmpa.infinity = 0;
183  secp256k1_ge_set_gej_zinv(&a[i], &tmpa, &zs);
184  }
185  }
186 }
187 
189  r->infinity = 1;
190  secp256k1_fe_clear(&r->x);
191  secp256k1_fe_clear(&r->y);
192  secp256k1_fe_clear(&r->z);
193 }
194 
196  r->infinity = 1;
197  secp256k1_fe_clear(&r->x);
198  secp256k1_fe_clear(&r->y);
199 }
200 
202  r->infinity = 0;
203  secp256k1_fe_clear(&r->x);
204  secp256k1_fe_clear(&r->y);
205  secp256k1_fe_clear(&r->z);
206 }
207 
209  r->infinity = 0;
210  secp256k1_fe_clear(&r->x);
211  secp256k1_fe_clear(&r->y);
212 }
213 
214 static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd) {
215  secp256k1_fe x2, x3;
216  r->x = *x;
217  secp256k1_fe_sqr(&x2, x);
218  secp256k1_fe_mul(&x3, x, &x2);
219  r->infinity = 0;
221  if (!secp256k1_fe_sqrt(&r->y, &x3)) {
222  return 0;
223  }
225  if (secp256k1_fe_is_odd(&r->y) != odd) {
226  secp256k1_fe_negate(&r->y, &r->y, 1);
227  }
228  return 1;
229 
230 }
231 
233  r->infinity = a->infinity;
234  r->x = a->x;
235  r->y = a->y;
236  secp256k1_fe_set_int(&r->z, 1);
237 }
238 
239 static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a) {
240  secp256k1_fe r, r2;
241  VERIFY_CHECK(!a->infinity);
242  secp256k1_fe_sqr(&r, &a->z); secp256k1_fe_mul(&r, &r, x);
243  r2 = a->x; secp256k1_fe_normalize_weak(&r2);
244  return secp256k1_fe_equal_var(&r, &r2);
245 }
246 
247 static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a) {
248  r->infinity = a->infinity;
249  r->x = a->x;
250  r->y = a->y;
251  r->z = a->z;
253  secp256k1_fe_negate(&r->y, &r->y, 1);
254 }
255 
257  return a->infinity;
258 }
259 
261  secp256k1_fe y2, x3;
262  if (a->infinity) {
263  return 0;
264  }
265  /* y^2 = x^3 + 7 */
266  secp256k1_fe_sqr(&y2, &a->y);
267  secp256k1_fe_sqr(&x3, &a->x); secp256k1_fe_mul(&x3, &x3, &a->x);
270  return secp256k1_fe_equal_var(&y2, &x3);
271 }
272 
274  /* Operations: 3 mul, 4 sqr, 8 add/half/mul_int/negate */
275  secp256k1_fe l, s, t;
276 
277  r->infinity = a->infinity;
278 
279  /* Formula used:
280  * L = (3/2) * X1^2
281  * S = Y1^2
282  * T = -X1*S
283  * X3 = L^2 + 2*T
284  * Y3 = -(L*(X3 + T) + S^2)
285  * Z3 = Y1*Z1
286  */
287 
288  secp256k1_fe_mul(&r->z, &a->z, &a->y); /* Z3 = Y1*Z1 (1) */
289  secp256k1_fe_sqr(&s, &a->y); /* S = Y1^2 (1) */
290  secp256k1_fe_sqr(&l, &a->x); /* L = X1^2 (1) */
291  secp256k1_fe_mul_int(&l, 3); /* L = 3*X1^2 (3) */
292  secp256k1_fe_half(&l); /* L = 3/2*X1^2 (2) */
293  secp256k1_fe_negate(&t, &s, 1); /* T = -S (2) */
294  secp256k1_fe_mul(&t, &t, &a->x); /* T = -X1*S (1) */
295  secp256k1_fe_sqr(&r->x, &l); /* X3 = L^2 (1) */
296  secp256k1_fe_add(&r->x, &t); /* X3 = L^2 + T (2) */
297  secp256k1_fe_add(&r->x, &t); /* X3 = L^2 + 2*T (3) */
298  secp256k1_fe_sqr(&s, &s); /* S' = S^2 (1) */
299  secp256k1_fe_add(&t, &r->x); /* T' = X3 + T (4) */
300  secp256k1_fe_mul(&r->y, &t, &l); /* Y3 = L*(X3 + T) (1) */
301  secp256k1_fe_add(&r->y, &s); /* Y3 = L*(X3 + T) + S^2 (2) */
302  secp256k1_fe_negate(&r->y, &r->y, 2); /* Y3 = -(L*(X3 + T) + S^2) (3) */
303 }
304 
316  if (a->infinity) {
318  if (rzr != NULL) {
319  secp256k1_fe_set_int(rzr, 1);
320  }
321  return;
322  }
323 
324  if (rzr != NULL) {
325  *rzr = a->y;
327  }
328 
329  secp256k1_gej_double(r, a);
330 }
331 
333  /* 12 mul, 4 sqr, 11 add/negate/normalizes_to_zero (ignoring special cases) */
334  secp256k1_fe z22, z12, u1, u2, s1, s2, h, i, h2, h3, t;
335 
336  if (a->infinity) {
337  VERIFY_CHECK(rzr == NULL);
338  *r = *b;
339  return;
340  }
341  if (b->infinity) {
342  if (rzr != NULL) {
343  secp256k1_fe_set_int(rzr, 1);
344  }
345  *r = *a;
346  return;
347  }
348 
349  secp256k1_fe_sqr(&z22, &b->z);
350  secp256k1_fe_sqr(&z12, &a->z);
351  secp256k1_fe_mul(&u1, &a->x, &z22);
352  secp256k1_fe_mul(&u2, &b->x, &z12);
353  secp256k1_fe_mul(&s1, &a->y, &z22); secp256k1_fe_mul(&s1, &s1, &b->z);
354  secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z);
355  secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
356  secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1);
359  secp256k1_gej_double_var(r, a, rzr);
360  } else {
361  if (rzr != NULL) {
362  secp256k1_fe_set_int(rzr, 0);
363  }
365  }
366  return;
367  }
368 
369  r->infinity = 0;
370  secp256k1_fe_mul(&t, &h, &b->z);
371  if (rzr != NULL) {
372  *rzr = t;
373  }
374  secp256k1_fe_mul(&r->z, &a->z, &t);
375 
376  secp256k1_fe_sqr(&h2, &h);
377  secp256k1_fe_negate(&h2, &h2, 1);
378  secp256k1_fe_mul(&h3, &h2, &h);
379  secp256k1_fe_mul(&t, &u1, &h2);
380 
381  secp256k1_fe_sqr(&r->x, &i);
382  secp256k1_fe_add(&r->x, &h3);
383  secp256k1_fe_add(&r->x, &t);
384  secp256k1_fe_add(&r->x, &t);
385 
386  secp256k1_fe_add(&t, &r->x);
387  secp256k1_fe_mul(&r->y, &t, &i);
388  secp256k1_fe_mul(&h3, &h3, &s1);
389  secp256k1_fe_add(&r->y, &h3);
390 }
391 
393  /* 8 mul, 3 sqr, 13 add/negate/normalize_weak/normalizes_to_zero (ignoring special cases) */
394  secp256k1_fe z12, u1, u2, s1, s2, h, i, h2, h3, t;
395  if (a->infinity) {
396  VERIFY_CHECK(rzr == NULL);
397  secp256k1_gej_set_ge(r, b);
398  return;
399  }
400  if (b->infinity) {
401  if (rzr != NULL) {
402  secp256k1_fe_set_int(rzr, 1);
403  }
404  *r = *a;
405  return;
406  }
407 
408  secp256k1_fe_sqr(&z12, &a->z);
409  u1 = a->x; secp256k1_fe_normalize_weak(&u1);
410  secp256k1_fe_mul(&u2, &b->x, &z12);
411  s1 = a->y; secp256k1_fe_normalize_weak(&s1);
412  secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z);
413  secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
414  secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1);
417  secp256k1_gej_double_var(r, a, rzr);
418  } else {
419  if (rzr != NULL) {
420  secp256k1_fe_set_int(rzr, 0);
421  }
423  }
424  return;
425  }
426 
427  r->infinity = 0;
428  if (rzr != NULL) {
429  *rzr = h;
430  }
431  secp256k1_fe_mul(&r->z, &a->z, &h);
432 
433  secp256k1_fe_sqr(&h2, &h);
434  secp256k1_fe_negate(&h2, &h2, 1);
435  secp256k1_fe_mul(&h3, &h2, &h);
436  secp256k1_fe_mul(&t, &u1, &h2);
437 
438  secp256k1_fe_sqr(&r->x, &i);
439  secp256k1_fe_add(&r->x, &h3);
440  secp256k1_fe_add(&r->x, &t);
441  secp256k1_fe_add(&r->x, &t);
442 
443  secp256k1_fe_add(&t, &r->x);
444  secp256k1_fe_mul(&r->y, &t, &i);
445  secp256k1_fe_mul(&h3, &h3, &s1);
446  secp256k1_fe_add(&r->y, &h3);
447 }
448 
449 static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, const secp256k1_fe *bzinv) {
450  /* 9 mul, 3 sqr, 13 add/negate/normalize_weak/normalizes_to_zero (ignoring special cases) */
451  secp256k1_fe az, z12, u1, u2, s1, s2, h, i, h2, h3, t;
452 
453  if (a->infinity) {
454  secp256k1_fe bzinv2, bzinv3;
455  r->infinity = b->infinity;
456  secp256k1_fe_sqr(&bzinv2, bzinv);
457  secp256k1_fe_mul(&bzinv3, &bzinv2, bzinv);
458  secp256k1_fe_mul(&r->x, &b->x, &bzinv2);
459  secp256k1_fe_mul(&r->y, &b->y, &bzinv3);
460  secp256k1_fe_set_int(&r->z, 1);
461  return;
462  }
463  if (b->infinity) {
464  *r = *a;
465  return;
466  }
467 
476  secp256k1_fe_mul(&az, &a->z, bzinv);
477 
478  secp256k1_fe_sqr(&z12, &az);
479  u1 = a->x; secp256k1_fe_normalize_weak(&u1);
480  secp256k1_fe_mul(&u2, &b->x, &z12);
481  s1 = a->y; secp256k1_fe_normalize_weak(&s1);
482  secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &az);
483  secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
484  secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1);
487  secp256k1_gej_double_var(r, a, NULL);
488  } else {
490  }
491  return;
492  }
493 
494  r->infinity = 0;
495  secp256k1_fe_mul(&r->z, &a->z, &h);
496 
497  secp256k1_fe_sqr(&h2, &h);
498  secp256k1_fe_negate(&h2, &h2, 1);
499  secp256k1_fe_mul(&h3, &h2, &h);
500  secp256k1_fe_mul(&t, &u1, &h2);
501 
502  secp256k1_fe_sqr(&r->x, &i);
503  secp256k1_fe_add(&r->x, &h3);
504  secp256k1_fe_add(&r->x, &t);
505  secp256k1_fe_add(&r->x, &t);
506 
507  secp256k1_fe_add(&t, &r->x);
508  secp256k1_fe_mul(&r->y, &t, &i);
509  secp256k1_fe_mul(&h3, &h3, &s1);
510  secp256k1_fe_add(&r->y, &h3);
511 }
512 
513 
514 static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b) {
515  /* Operations: 7 mul, 5 sqr, 24 add/cmov/half/mul_int/negate/normalize_weak/normalizes_to_zero */
516  secp256k1_fe zz, u1, u2, s1, s2, t, tt, m, n, q, rr;
517  secp256k1_fe m_alt, rr_alt;
518  int infinity, degenerate;
519  VERIFY_CHECK(!b->infinity);
520  VERIFY_CHECK(a->infinity == 0 || a->infinity == 1);
521 
572  secp256k1_fe_sqr(&zz, &a->z); /* z = Z1^2 */
573  u1 = a->x; secp256k1_fe_normalize_weak(&u1); /* u1 = U1 = X1*Z2^2 (1) */
574  secp256k1_fe_mul(&u2, &b->x, &zz); /* u2 = U2 = X2*Z1^2 (1) */
575  s1 = a->y; secp256k1_fe_normalize_weak(&s1); /* s1 = S1 = Y1*Z2^3 (1) */
576  secp256k1_fe_mul(&s2, &b->y, &zz); /* s2 = Y2*Z1^2 (1) */
577  secp256k1_fe_mul(&s2, &s2, &a->z); /* s2 = S2 = Y2*Z1^3 (1) */
578  t = u1; secp256k1_fe_add(&t, &u2); /* t = T = U1+U2 (2) */
579  m = s1; secp256k1_fe_add(&m, &s2); /* m = M = S1+S2 (2) */
580  secp256k1_fe_sqr(&rr, &t); /* rr = T^2 (1) */
581  secp256k1_fe_negate(&m_alt, &u2, 1); /* Malt = -X2*Z1^2 */
582  secp256k1_fe_mul(&tt, &u1, &m_alt); /* tt = -U1*U2 (2) */
583  secp256k1_fe_add(&rr, &tt); /* rr = R = T^2-U1*U2 (3) */
586  degenerate = secp256k1_fe_normalizes_to_zero(&m) &
588  /* This only occurs when y1 == -y2 and x1^3 == x2^3, but x1 != x2.
589  * This means either x1 == beta*x2 or beta*x1 == x2, where beta is
590  * a nontrivial cube root of one. In either case, an alternate
591  * non-indeterminate expression for lambda is (y1 - y2)/(x1 - x2),
592  * so we set R/M equal to this. */
593  rr_alt = s1;
594  secp256k1_fe_mul_int(&rr_alt, 2); /* rr = Y1*Z2^3 - Y2*Z1^3 (2) */
595  secp256k1_fe_add(&m_alt, &u1); /* Malt = X1*Z2^2 - X2*Z1^2 */
596 
597  secp256k1_fe_cmov(&rr_alt, &rr, !degenerate);
598  secp256k1_fe_cmov(&m_alt, &m, !degenerate);
599  /* Now Ralt / Malt = lambda and is guaranteed not to be 0/0.
600  * From here on out Ralt and Malt represent the numerator
601  * and denominator of lambda; R and M represent the explicit
602  * expressions x1^2 + x2^2 + x1x2 and y1 + y2. */
603  secp256k1_fe_sqr(&n, &m_alt); /* n = Malt^2 (1) */
604  secp256k1_fe_negate(&q, &t, 2); /* q = -T (3) */
605  secp256k1_fe_mul(&q, &q, &n); /* q = Q = -T*Malt^2 (1) */
606  /* These two lines use the observation that either M == Malt or M == 0,
607  * so M^3 * Malt is either Malt^4 (which is computed by squaring), or
608  * zero (which is "computed" by cmov). So the cost is one squaring
609  * versus two multiplications. */
610  secp256k1_fe_sqr(&n, &n);
611  secp256k1_fe_cmov(&n, &m, degenerate); /* n = M^3 * Malt (2) */
612  secp256k1_fe_sqr(&t, &rr_alt); /* t = Ralt^2 (1) */
613  secp256k1_fe_mul(&r->z, &a->z, &m_alt); /* r->z = Z3 = Malt*Z (1) */
614  infinity = secp256k1_fe_normalizes_to_zero(&r->z) & ~a->infinity;
615  secp256k1_fe_add(&t, &q); /* t = Ralt^2 + Q (2) */
616  r->x = t; /* r->x = X3 = Ralt^2 + Q (2) */
617  secp256k1_fe_mul_int(&t, 2); /* t = 2*X3 (4) */
618  secp256k1_fe_add(&t, &q); /* t = 2*X3 + Q (5) */
619  secp256k1_fe_mul(&t, &t, &rr_alt); /* t = Ralt*(2*X3 + Q) (1) */
620  secp256k1_fe_add(&t, &n); /* t = Ralt*(2*X3 + Q) + M^3*Malt (3) */
621  secp256k1_fe_negate(&r->y, &t, 3); /* r->y = -(Ralt*(2*X3 + Q) + M^3*Malt) (4) */
622  secp256k1_fe_half(&r->y); /* r->y = Y3 = -(Ralt*(2*X3 + Q) + M^3*Malt)/2 (3) */
623 
625  secp256k1_fe_cmov(&r->x, &b->x, a->infinity);
626  secp256k1_fe_cmov(&r->y, &b->y, a->infinity);
628  r->infinity = infinity;
629 }
630 
632  /* Operations: 4 mul, 1 sqr */
633  secp256k1_fe zz;
635  secp256k1_fe_sqr(&zz, s);
636  secp256k1_fe_mul(&r->x, &r->x, &zz); /* r->x *= s^2 */
637  secp256k1_fe_mul(&r->y, &r->y, &zz);
638  secp256k1_fe_mul(&r->y, &r->y, s); /* r->y *= s^3 */
639  secp256k1_fe_mul(&r->z, &r->z, s); /* r->z *= s */
640 }
641 
643  secp256k1_fe x, y;
644  VERIFY_CHECK(!a->infinity);
645  x = a->x;
647  y = a->y;
649  secp256k1_fe_to_storage(&r->x, &x);
650  secp256k1_fe_to_storage(&r->y, &y);
651 }
652 
654  secp256k1_fe_from_storage(&r->x, &a->x);
655  secp256k1_fe_from_storage(&r->y, &a->y);
656  r->infinity = 0;
657 }
658 
659 static SECP256K1_INLINE void secp256k1_gej_cmov(secp256k1_gej *r, const secp256k1_gej *a, int flag) {
660  secp256k1_fe_cmov(&r->x, &a->x, flag);
661  secp256k1_fe_cmov(&r->y, &a->y, flag);
662  secp256k1_fe_cmov(&r->z, &a->z, flag);
663 
664  r->infinity ^= (r->infinity ^ a->infinity) & flag;
665 }
666 
668  secp256k1_fe_storage_cmov(&r->x, &a->x, flag);
669  secp256k1_fe_storage_cmov(&r->y, &a->y, flag);
670 }
671 
673  *r = *a;
675 }
676 
678 #ifdef EXHAUSTIVE_TEST_ORDER
679  secp256k1_gej out;
680  int i;
681 
682  /* A very simple EC multiplication ladder that avoids a dependency on ecmult. */
684  for (i = 0; i < 32; ++i) {
685  secp256k1_gej_double_var(&out, &out, NULL);
686  if ((((uint32_t)EXHAUSTIVE_TEST_ORDER) >> (31 - i)) & 1) {
687  secp256k1_gej_add_ge_var(&out, &out, ge, NULL);
688  }
689  }
690  return secp256k1_gej_is_infinity(&out);
691 #else
692  (void)ge;
693  /* The real secp256k1 group has cofactor 1, so the subgroup is the entire curve. */
694  return 1;
695 #endif
696 }
697 
698 #endif /* SECP256K1_GROUP_IMPL_H */
static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *a)
Potentially faster version of secp256k1_fe_inv, without constant-time guarantee.
static int secp256k1_fe_normalizes_to_zero_var(const secp256k1_fe *r)
Verify whether a field element represents zero i.e.
static void secp256k1_fe_normalize_weak(secp256k1_fe *r)
Weakly normalize a field element: reduce its magnitude to 1, but don't fully normalize.
static int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b)
Same as secp256k1_fe_equal, but may be variable time.
static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a)
If a has a square root, it is computed in r and 1 is returned.
static void secp256k1_fe_normalize_var(secp256k1_fe *r)
Normalize a field element, without constant-time guarantee.
static void secp256k1_fe_clear(secp256k1_fe *a)
Sets a field element equal to zero, initializing all fields.
static void secp256k1_fe_inv(secp256k1_fe *r, const secp256k1_fe *a)
Sets a field element to be the (modular) inverse of another.
static void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag)
If flag is true, set *r equal to *a; otherwise leave it.
static void secp256k1_fe_mul_int(secp256k1_fe *r, int a)
Multiplies the passed field element with a small integer constant.
static void secp256k1_fe_negate(secp256k1_fe *r, const secp256k1_fe *a, int m)
Set a field element equal to the additive inverse of another.
static int secp256k1_fe_is_odd(const secp256k1_fe *a)
Check the "oddness" of a field element.
static const secp256k1_fe secp256k1_const_beta
Definition: field.h:36
static void secp256k1_fe_set_int(secp256k1_fe *r, int a)
Set a field element equal to a small (not greater than 0x7FFF), non-negative integer.
static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp256k1_fe *SECP256K1_RESTRICT b)
Sets a field element to be the product of two others.
static int secp256k1_fe_is_zero(const secp256k1_fe *a)
Verify whether a field element is zero.
static void secp256k1_fe_from_storage(secp256k1_fe *r, const secp256k1_fe_storage *a)
Convert a field element back from the storage type.
static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a)
Sets a field element to be the square of another.
static const secp256k1_fe secp256k1_fe_one
Field element module.
Definition: field.h:35
static int secp256k1_fe_normalizes_to_zero(const secp256k1_fe *r)
Verify whether a field element represents zero i.e.
static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a)
Adds a field element to another.
static void secp256k1_fe_normalize(secp256k1_fe *r)
Normalize a field element.
static void secp256k1_fe_half(secp256k1_fe *r)
Halves the value of a field element modulo the field prime.
static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe *a)
Convert a field element to the storage type.
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_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
Definition: field_10x26.h:40
static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr)
Definition: group_impl.h:305
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:449
#define SECP256K1_G_ORDER_13
Definition: group_impl.h:13
static void secp256k1_gej_clear(secp256k1_gej *r)
Definition: group_impl.h:201
static void secp256k1_ge_mul_lambda(secp256k1_ge *r, const secp256k1_ge *a)
Definition: group_impl.h:672
static void secp256k1_gej_set_infinity(secp256k1_gej *r)
Definition: group_impl.h:188
static int secp256k1_gej_is_infinity(const secp256k1_gej *a)
Definition: group_impl.h:256
static void secp256k1_ge_clear(secp256k1_ge *r)
Definition: group_impl.h:208
static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y)
Definition: group_impl.h:78
static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd)
Definition: group_impl.h:214
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:392
static SECP256K1_INLINE void secp256k1_gej_cmov(secp256k1_gej *r, const secp256k1_gej *a, int flag)
Definition: group_impl.h:659
static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b)
Definition: group_impl.h:514
#define SECP256K1_G
Generator for secp256k1, value 'g' defined in "Standards for Efficient Cryptography" (SEC2) 2....
Definition: group_impl.h:28
static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi)
Definition: group_impl.h:67
static int secp256k1_ge_is_valid_var(const secp256k1_ge *a)
Definition: group_impl.h:260
static void secp256k1_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storage *a)
Definition: group_impl.h:653
static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr)
Definition: group_impl.h:332
static void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *s)
Definition: group_impl.h:631
static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a)
Definition: group_impl.h:239
static void secp256k1_ge_set_gej(secp256k1_ge *r, secp256k1_gej *a)
Definition: group_impl.h:94
static int secp256k1_ge_is_in_correct_subgroup(const secp256k1_ge *ge)
Definition: group_impl.h:677
static void secp256k1_ge_table_set_globalz(size_t len, secp256k1_ge *a, const secp256k1_fe *zr)
Definition: group_impl.h:164
static const secp256k1_fe secp256k1_fe_const_b
Definition: group_impl.h:64
static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a)
Definition: group_impl.h:88
static const secp256k1_ge secp256k1_ge_const_g
Definition: group_impl.h:62
static int secp256k1_ge_is_infinity(const secp256k1_ge *a)
Definition: group_impl.h:84
static void secp256k1_ge_set_infinity(secp256k1_ge *r)
Definition: group_impl.h:195
static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len)
Definition: group_impl.h:122
static void secp256k1_gej_set_ge(secp256k1_gej *r, const secp256k1_ge *a)
Definition: group_impl.h:232
static void secp256k1_ge_to_storage(secp256k1_ge_storage *r, const secp256k1_ge *a)
Definition: group_impl.h:642
static SECP256K1_INLINE void secp256k1_ge_storage_cmov(secp256k1_ge_storage *r, const secp256k1_ge_storage *a, int flag)
Definition: group_impl.h:667
#define SECP256K1_G_ORDER_199
Definition: group_impl.h:19
static void secp256k1_ge_set_gej_var(secp256k1_ge *r, secp256k1_gej *a)
Definition: group_impl.h:107
static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a)
Definition: group_impl.h:247
static SECP256K1_INLINE void secp256k1_gej_double(secp256k1_gej *r, const secp256k1_gej *a)
Definition: group_impl.h:273
#define VERIFY_CHECK(cond)
Definition: util.h:95
#define SECP256K1_INLINE
Definition: secp256k1.h:127
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