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