Bitcoin Core  0.19.99
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 http://www.opensource.org/licenses/mit-license.php.*
5  **********************************************************************/
6 
7 #ifndef SECP256K1_GROUP_IMPL_H
8 #define SECP256K1_GROUP_IMPL_H
9 
10 #include "num.h"
11 #include "field.h"
12 #include "group.h"
13 
14 /* These points can be generated in sage as follows:
15  *
16  * 0. Setup a worksheet with the following parameters.
17  * b = 4 # whatever CURVE_B will be set to
18  * F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
19  * C = EllipticCurve ([F (0), F (b)])
20  *
21  * 1. Determine all the small orders available to you. (If there are
22  * no satisfactory ones, go back and change b.)
23  * print C.order().factor(limit=1000)
24  *
25  * 2. Choose an order as one of the prime factors listed in the above step.
26  * (You can also multiply some to get a composite order, though the
27  * tests will crash trying to invert scalars during signing.) We take a
28  * random point and scale it to drop its order to the desired value.
29  * There is some probability this won't work; just try again.
30  * order = 199
31  * P = C.random_point()
32  * P = (int(P.order()) / int(order)) * P
33  * assert(P.order() == order)
34  *
35  * 3. Print the values. You'll need to use a vim macro or something to
36  * split the hex output into 4-byte chunks.
37  * print "%x %x" % P.xy()
38  */
39 #if defined(EXHAUSTIVE_TEST_ORDER)
40 # if EXHAUSTIVE_TEST_ORDER == 199
42  0xFA7CC9A7, 0x0737F2DB, 0xA749DD39, 0x2B4FB069,
43  0x3B017A7D, 0xA808C2F1, 0xFB12940C, 0x9EA66C18,
44  0x78AC123A, 0x5ED8AEF3, 0x8732BC91, 0x1F3A2868,
45  0x48DF246C, 0x808DAE72, 0xCFE52572, 0x7F0501ED
46 );
47 
48 static const int CURVE_B = 4;
49 # elif EXHAUSTIVE_TEST_ORDER == 13
50 static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_GE_CONST(
51  0xedc60018, 0xa51a786b, 0x2ea91f4d, 0x4c9416c0,
52  0x9de54c3b, 0xa1316554, 0x6cf4345c, 0x7277ef15,
53  0x54cb1b6b, 0xdc8c1273, 0x087844ea, 0x43f4603e,
54  0x0eaf9a43, 0xf6effe55, 0x939f806d, 0x37adf8ac
55 );
56 static const int CURVE_B = 2;
57 # else
58 # error No known generator for the specified exhaustive test group order.
59 # endif
60 #else
61 
64 static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_GE_CONST(
65  0x79BE667EUL, 0xF9DCBBACUL, 0x55A06295UL, 0xCE870B07UL,
66  0x029BFCDBUL, 0x2DCE28D9UL, 0x59F2815BUL, 0x16F81798UL,
67  0x483ADA77UL, 0x26A3C465UL, 0x5DA4FBFCUL, 0x0E1108A8UL,
68  0xFD17B448UL, 0xA6855419UL, 0x9C47D08FUL, 0xFB10D4B8UL
69 );
70 
71 static const int CURVE_B = 7;
72 #endif
73 
74 static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi) {
75  secp256k1_fe zi2;
76  secp256k1_fe zi3;
77  secp256k1_fe_sqr(&zi2, zi);
78  secp256k1_fe_mul(&zi3, &zi2, zi);
79  secp256k1_fe_mul(&r->x, &a->x, &zi2);
80  secp256k1_fe_mul(&r->y, &a->y, &zi3);
81  r->infinity = a->infinity;
82 }
83 
84 static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y) {
85  r->infinity = 0;
86  r->x = *x;
87  r->y = *y;
88 }
89 
90 static int secp256k1_ge_is_infinity(const secp256k1_ge *a) {
91  return a->infinity;
92 }
93 
94 static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a) {
95  *r = *a;
97  secp256k1_fe_negate(&r->y, &r->y, 1);
98 }
99 
101  secp256k1_fe z2, z3;
102  r->infinity = a->infinity;
103  secp256k1_fe_inv(&a->z, &a->z);
104  secp256k1_fe_sqr(&z2, &a->z);
105  secp256k1_fe_mul(&z3, &a->z, &z2);
106  secp256k1_fe_mul(&a->x, &a->x, &z2);
107  secp256k1_fe_mul(&a->y, &a->y, &z3);
108  secp256k1_fe_set_int(&a->z, 1);
109  r->x = a->x;
110  r->y = a->y;
111 }
112 
114  secp256k1_fe z2, z3;
115  r->infinity = a->infinity;
116  if (a->infinity) {
117  return;
118  }
119  secp256k1_fe_inv_var(&a->z, &a->z);
120  secp256k1_fe_sqr(&z2, &a->z);
121  secp256k1_fe_mul(&z3, &a->z, &z2);
122  secp256k1_fe_mul(&a->x, &a->x, &z2);
123  secp256k1_fe_mul(&a->y, &a->y, &z3);
124  secp256k1_fe_set_int(&a->z, 1);
125  r->x = a->x;
126  r->y = a->y;
127 }
128 
129 static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len) {
130  secp256k1_fe u;
131  size_t i;
132  size_t last_i = SIZE_MAX;
133 
134  for (i = 0; i < len; i++) {
135  if (!a[i].infinity) {
136  /* Use destination's x coordinates as scratch space */
137  if (last_i == SIZE_MAX) {
138  r[i].x = a[i].z;
139  } else {
140  secp256k1_fe_mul(&r[i].x, &r[last_i].x, &a[i].z);
141  }
142  last_i = i;
143  }
144  }
145  if (last_i == SIZE_MAX) {
146  return;
147  }
148  secp256k1_fe_inv_var(&u, &r[last_i].x);
149 
150  i = last_i;
151  while (i > 0) {
152  i--;
153  if (!a[i].infinity) {
154  secp256k1_fe_mul(&r[last_i].x, &r[i].x, &u);
155  secp256k1_fe_mul(&u, &u, &a[last_i].z);
156  last_i = i;
157  }
158  }
159  VERIFY_CHECK(!a[last_i].infinity);
160  r[last_i].x = u;
161 
162  for (i = 0; i < len; i++) {
163  r[i].infinity = a[i].infinity;
164  if (!a[i].infinity) {
165  secp256k1_ge_set_gej_zinv(&r[i], &a[i], &r[i].x);
166  }
167  }
168 }
169 
170 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) {
171  size_t i = len - 1;
172  secp256k1_fe zs;
173 
174  if (len > 0) {
175  /* The z of the final point gives us the "global Z" for the table. */
176  r[i].x = a[i].x;
177  r[i].y = a[i].y;
178  /* Ensure all y values are in weak normal form for fast negation of points */
180  *globalz = a[i].z;
181  r[i].infinity = 0;
182  zs = zr[i];
183 
184  /* Work our way backwards, using the z-ratios to scale the x/y values. */
185  while (i > 0) {
186  if (i != len - 1) {
187  secp256k1_fe_mul(&zs, &zs, &zr[i]);
188  }
189  i--;
190  secp256k1_ge_set_gej_zinv(&r[i], &a[i], &zs);
191  }
192  }
193 }
194 
196  r->infinity = 1;
197  secp256k1_fe_clear(&r->x);
198  secp256k1_fe_clear(&r->y);
199  secp256k1_fe_clear(&r->z);
200 }
201 
203  r->infinity = 1;
204  secp256k1_fe_clear(&r->x);
205  secp256k1_fe_clear(&r->y);
206 }
207 
209  r->infinity = 0;
210  secp256k1_fe_clear(&r->x);
211  secp256k1_fe_clear(&r->y);
212  secp256k1_fe_clear(&r->z);
213 }
214 
216  r->infinity = 0;
217  secp256k1_fe_clear(&r->x);
218  secp256k1_fe_clear(&r->y);
219 }
220 
222  secp256k1_fe x2, x3, c;
223  r->x = *x;
224  secp256k1_fe_sqr(&x2, x);
225  secp256k1_fe_mul(&x3, x, &x2);
226  r->infinity = 0;
228  secp256k1_fe_add(&c, &x3);
229  return secp256k1_fe_sqrt(&r->y, &c);
230 }
231 
232 static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd) {
233  if (!secp256k1_ge_set_xquad(r, x)) {
234  return 0;
235  }
237  if (secp256k1_fe_is_odd(&r->y) != odd) {
238  secp256k1_fe_negate(&r->y, &r->y, 1);
239  }
240  return 1;
241 
242 }
243 
245  r->infinity = a->infinity;
246  r->x = a->x;
247  r->y = a->y;
248  secp256k1_fe_set_int(&r->z, 1);
249 }
250 
251 static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a) {
252  secp256k1_fe r, r2;
253  VERIFY_CHECK(!a->infinity);
254  secp256k1_fe_sqr(&r, &a->z); secp256k1_fe_mul(&r, &r, x);
255  r2 = a->x; secp256k1_fe_normalize_weak(&r2);
256  return secp256k1_fe_equal_var(&r, &r2);
257 }
258 
259 static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a) {
260  r->infinity = a->infinity;
261  r->x = a->x;
262  r->y = a->y;
263  r->z = a->z;
265  secp256k1_fe_negate(&r->y, &r->y, 1);
266 }
267 
269  return a->infinity;
270 }
271 
273  secp256k1_fe y2, x3, z2, z6;
274  if (a->infinity) {
275  return 0;
276  }
282  secp256k1_fe_sqr(&y2, &a->y);
283  secp256k1_fe_sqr(&x3, &a->x); secp256k1_fe_mul(&x3, &x3, &a->x);
284  secp256k1_fe_sqr(&z2, &a->z);
285  secp256k1_fe_sqr(&z6, &z2); secp256k1_fe_mul(&z6, &z6, &z2);
287  secp256k1_fe_add(&x3, &z6);
289  return secp256k1_fe_equal_var(&y2, &x3);
290 }
291 
293  secp256k1_fe y2, x3, c;
294  if (a->infinity) {
295  return 0;
296  }
297  /* y^2 = x^3 + 7 */
298  secp256k1_fe_sqr(&y2, &a->y);
299  secp256k1_fe_sqr(&x3, &a->x); secp256k1_fe_mul(&x3, &x3, &a->x);
301  secp256k1_fe_add(&x3, &c);
303  return secp256k1_fe_equal_var(&y2, &x3);
304 }
305 
307  /* Operations: 3 mul, 4 sqr, 0 normalize, 12 mul_int/add/negate.
308  *
309  * Note that there is an implementation described at
310  * https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l
311  * which trades a multiply for a square, but in practice this is actually slower,
312  * mainly because it requires more normalizations.
313  */
314  secp256k1_fe t1,t2,t3,t4;
325  r->infinity = a->infinity;
326  if (r->infinity) {
327  if (rzr != NULL) {
328  secp256k1_fe_set_int(rzr, 1);
329  }
330  return;
331  }
332 
333  if (rzr != NULL) {
334  *rzr = a->y;
336  secp256k1_fe_mul_int(rzr, 2);
337  }
338 
339  secp256k1_fe_mul(&r->z, &a->z, &a->y);
340  secp256k1_fe_mul_int(&r->z, 2); /* Z' = 2*Y*Z (2) */
341  secp256k1_fe_sqr(&t1, &a->x);
342  secp256k1_fe_mul_int(&t1, 3); /* T1 = 3*X^2 (3) */
343  secp256k1_fe_sqr(&t2, &t1); /* T2 = 9*X^4 (1) */
344  secp256k1_fe_sqr(&t3, &a->y);
345  secp256k1_fe_mul_int(&t3, 2); /* T3 = 2*Y^2 (2) */
346  secp256k1_fe_sqr(&t4, &t3);
347  secp256k1_fe_mul_int(&t4, 2); /* T4 = 8*Y^4 (2) */
348  secp256k1_fe_mul(&t3, &t3, &a->x); /* T3 = 2*X*Y^2 (1) */
349  r->x = t3;
350  secp256k1_fe_mul_int(&r->x, 4); /* X' = 8*X*Y^2 (4) */
351  secp256k1_fe_negate(&r->x, &r->x, 4); /* X' = -8*X*Y^2 (5) */
352  secp256k1_fe_add(&r->x, &t2); /* X' = 9*X^4 - 8*X*Y^2 (6) */
353  secp256k1_fe_negate(&t2, &t2, 1); /* T2 = -9*X^4 (2) */
354  secp256k1_fe_mul_int(&t3, 6); /* T3 = 12*X*Y^2 (6) */
355  secp256k1_fe_add(&t3, &t2); /* T3 = 12*X*Y^2 - 9*X^4 (8) */
356  secp256k1_fe_mul(&r->y, &t1, &t3); /* Y' = 36*X^3*Y^2 - 27*X^6 (1) */
357  secp256k1_fe_negate(&t2, &t4, 2); /* T2 = -8*Y^4 (3) */
358  secp256k1_fe_add(&r->y, &t2); /* Y' = 36*X^3*Y^2 - 27*X^6 - 8*Y^4 (4) */
359 }
360 
363  secp256k1_gej_double_var(r, a, rzr);
364 }
365 
367  /* Operations: 12 mul, 4 sqr, 2 normalize, 12 mul_int/add/negate */
368  secp256k1_fe z22, z12, u1, u2, s1, s2, h, i, i2, h2, h3, t;
369 
370  if (a->infinity) {
371  VERIFY_CHECK(rzr == NULL);
372  *r = *b;
373  return;
374  }
375 
376  if (b->infinity) {
377  if (rzr != NULL) {
378  secp256k1_fe_set_int(rzr, 1);
379  }
380  *r = *a;
381  return;
382  }
383 
384  r->infinity = 0;
385  secp256k1_fe_sqr(&z22, &b->z);
386  secp256k1_fe_sqr(&z12, &a->z);
387  secp256k1_fe_mul(&u1, &a->x, &z22);
388  secp256k1_fe_mul(&u2, &b->x, &z12);
389  secp256k1_fe_mul(&s1, &a->y, &z22); secp256k1_fe_mul(&s1, &s1, &b->z);
390  secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z);
391  secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
392  secp256k1_fe_negate(&i, &s1, 1); secp256k1_fe_add(&i, &s2);
395  secp256k1_gej_double_var(r, a, rzr);
396  } else {
397  if (rzr != NULL) {
398  secp256k1_fe_set_int(rzr, 0);
399  }
400  r->infinity = 1;
401  }
402  return;
403  }
404  secp256k1_fe_sqr(&i2, &i);
405  secp256k1_fe_sqr(&h2, &h);
406  secp256k1_fe_mul(&h3, &h, &h2);
407  secp256k1_fe_mul(&h, &h, &b->z);
408  if (rzr != NULL) {
409  *rzr = h;
410  }
411  secp256k1_fe_mul(&r->z, &a->z, &h);
412  secp256k1_fe_mul(&t, &u1, &h2);
413  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);
414  secp256k1_fe_negate(&r->y, &r->x, 5); secp256k1_fe_add(&r->y, &t); secp256k1_fe_mul(&r->y, &r->y, &i);
415  secp256k1_fe_mul(&h3, &h3, &s1); secp256k1_fe_negate(&h3, &h3, 1);
416  secp256k1_fe_add(&r->y, &h3);
417 }
418 
420  /* 8 mul, 3 sqr, 4 normalize, 12 mul_int/add/negate */
421  secp256k1_fe z12, u1, u2, s1, s2, h, i, i2, h2, h3, t;
422  if (a->infinity) {
423  VERIFY_CHECK(rzr == NULL);
424  secp256k1_gej_set_ge(r, b);
425  return;
426  }
427  if (b->infinity) {
428  if (rzr != NULL) {
429  secp256k1_fe_set_int(rzr, 1);
430  }
431  *r = *a;
432  return;
433  }
434  r->infinity = 0;
435 
436  secp256k1_fe_sqr(&z12, &a->z);
437  u1 = a->x; secp256k1_fe_normalize_weak(&u1);
438  secp256k1_fe_mul(&u2, &b->x, &z12);
439  s1 = a->y; secp256k1_fe_normalize_weak(&s1);
440  secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z);
441  secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
442  secp256k1_fe_negate(&i, &s1, 1); secp256k1_fe_add(&i, &s2);
445  secp256k1_gej_double_var(r, a, rzr);
446  } else {
447  if (rzr != NULL) {
448  secp256k1_fe_set_int(rzr, 0);
449  }
450  r->infinity = 1;
451  }
452  return;
453  }
454  secp256k1_fe_sqr(&i2, &i);
455  secp256k1_fe_sqr(&h2, &h);
456  secp256k1_fe_mul(&h3, &h, &h2);
457  if (rzr != NULL) {
458  *rzr = h;
459  }
460  secp256k1_fe_mul(&r->z, &a->z, &h);
461  secp256k1_fe_mul(&t, &u1, &h2);
462  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);
463  secp256k1_fe_negate(&r->y, &r->x, 5); secp256k1_fe_add(&r->y, &t); secp256k1_fe_mul(&r->y, &r->y, &i);
464  secp256k1_fe_mul(&h3, &h3, &s1); secp256k1_fe_negate(&h3, &h3, 1);
465  secp256k1_fe_add(&r->y, &h3);
466 }
467 
468 static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, const secp256k1_fe *bzinv) {
469  /* 9 mul, 3 sqr, 4 normalize, 12 mul_int/add/negate */
470  secp256k1_fe az, z12, u1, u2, s1, s2, h, i, i2, h2, h3, t;
471 
472  if (b->infinity) {
473  *r = *a;
474  return;
475  }
476  if (a->infinity) {
477  secp256k1_fe bzinv2, bzinv3;
478  r->infinity = b->infinity;
479  secp256k1_fe_sqr(&bzinv2, bzinv);
480  secp256k1_fe_mul(&bzinv3, &bzinv2, bzinv);
481  secp256k1_fe_mul(&r->x, &b->x, &bzinv2);
482  secp256k1_fe_mul(&r->y, &b->y, &bzinv3);
483  secp256k1_fe_set_int(&r->z, 1);
484  return;
485  }
486  r->infinity = 0;
487 
496  secp256k1_fe_mul(&az, &a->z, bzinv);
497 
498  secp256k1_fe_sqr(&z12, &az);
499  u1 = a->x; secp256k1_fe_normalize_weak(&u1);
500  secp256k1_fe_mul(&u2, &b->x, &z12);
501  s1 = a->y; secp256k1_fe_normalize_weak(&s1);
502  secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &az);
503  secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
504  secp256k1_fe_negate(&i, &s1, 1); secp256k1_fe_add(&i, &s2);
507  secp256k1_gej_double_var(r, a, NULL);
508  } else {
509  r->infinity = 1;
510  }
511  return;
512  }
513  secp256k1_fe_sqr(&i2, &i);
514  secp256k1_fe_sqr(&h2, &h);
515  secp256k1_fe_mul(&h3, &h, &h2);
516  r->z = a->z; secp256k1_fe_mul(&r->z, &r->z, &h);
517  secp256k1_fe_mul(&t, &u1, &h2);
518  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);
519  secp256k1_fe_negate(&r->y, &r->x, 5); secp256k1_fe_add(&r->y, &t); secp256k1_fe_mul(&r->y, &r->y, &i);
520  secp256k1_fe_mul(&h3, &h3, &s1); secp256k1_fe_negate(&h3, &h3, 1);
521  secp256k1_fe_add(&r->y, &h3);
522 }
523 
524 
525 static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b) {
526  /* Operations: 7 mul, 5 sqr, 4 normalize, 21 mul_int/add/negate/cmov */
527  static const secp256k1_fe fe_1 = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1);
528  secp256k1_fe zz, u1, u2, s1, s2, t, tt, m, n, q, rr;
529  secp256k1_fe m_alt, rr_alt;
530  int infinity, degenerate;
531  VERIFY_CHECK(!b->infinity);
532  VERIFY_CHECK(a->infinity == 0 || a->infinity == 1);
533 
584  secp256k1_fe_sqr(&zz, &a->z); /* z = Z1^2 */
585  u1 = a->x; secp256k1_fe_normalize_weak(&u1); /* u1 = U1 = X1*Z2^2 (1) */
586  secp256k1_fe_mul(&u2, &b->x, &zz); /* u2 = U2 = X2*Z1^2 (1) */
587  s1 = a->y; secp256k1_fe_normalize_weak(&s1); /* s1 = S1 = Y1*Z2^3 (1) */
588  secp256k1_fe_mul(&s2, &b->y, &zz); /* s2 = Y2*Z1^2 (1) */
589  secp256k1_fe_mul(&s2, &s2, &a->z); /* s2 = S2 = Y2*Z1^3 (1) */
590  t = u1; secp256k1_fe_add(&t, &u2); /* t = T = U1+U2 (2) */
591  m = s1; secp256k1_fe_add(&m, &s2); /* m = M = S1+S2 (2) */
592  secp256k1_fe_sqr(&rr, &t); /* rr = T^2 (1) */
593  secp256k1_fe_negate(&m_alt, &u2, 1); /* Malt = -X2*Z1^2 */
594  secp256k1_fe_mul(&tt, &u1, &m_alt); /* tt = -U1*U2 (2) */
595  secp256k1_fe_add(&rr, &tt); /* rr = R = T^2-U1*U2 (3) */
598  degenerate = secp256k1_fe_normalizes_to_zero(&m) &
600  /* This only occurs when y1 == -y2 and x1^3 == x2^3, but x1 != x2.
601  * This means either x1 == beta*x2 or beta*x1 == x2, where beta is
602  * a nontrivial cube root of one. In either case, an alternate
603  * non-indeterminate expression for lambda is (y1 - y2)/(x1 - x2),
604  * so we set R/M equal to this. */
605  rr_alt = s1;
606  secp256k1_fe_mul_int(&rr_alt, 2); /* rr = Y1*Z2^3 - Y2*Z1^3 (2) */
607  secp256k1_fe_add(&m_alt, &u1); /* Malt = X1*Z2^2 - X2*Z1^2 */
608 
609  secp256k1_fe_cmov(&rr_alt, &rr, !degenerate);
610  secp256k1_fe_cmov(&m_alt, &m, !degenerate);
611  /* Now Ralt / Malt = lambda and is guaranteed not to be 0/0.
612  * From here on out Ralt and Malt represent the numerator
613  * and denominator of lambda; R and M represent the explicit
614  * expressions x1^2 + x2^2 + x1x2 and y1 + y2. */
615  secp256k1_fe_sqr(&n, &m_alt); /* n = Malt^2 (1) */
616  secp256k1_fe_mul(&q, &n, &t); /* q = Q = T*Malt^2 (1) */
617  /* These two lines use the observation that either M == Malt or M == 0,
618  * so M^3 * Malt is either Malt^4 (which is computed by squaring), or
619  * zero (which is "computed" by cmov). So the cost is one squaring
620  * versus two multiplications. */
621  secp256k1_fe_sqr(&n, &n);
622  secp256k1_fe_cmov(&n, &m, degenerate); /* n = M^3 * Malt (2) */
623  secp256k1_fe_sqr(&t, &rr_alt); /* t = Ralt^2 (1) */
624  secp256k1_fe_mul(&r->z, &a->z, &m_alt); /* r->z = Malt*Z (1) */
625  infinity = secp256k1_fe_normalizes_to_zero(&r->z) * (1 - a->infinity);
626  secp256k1_fe_mul_int(&r->z, 2); /* r->z = Z3 = 2*Malt*Z (2) */
627  secp256k1_fe_negate(&q, &q, 1); /* q = -Q (2) */
628  secp256k1_fe_add(&t, &q); /* t = Ralt^2-Q (3) */
630  r->x = t; /* r->x = Ralt^2-Q (1) */
631  secp256k1_fe_mul_int(&t, 2); /* t = 2*x3 (2) */
632  secp256k1_fe_add(&t, &q); /* t = 2*x3 - Q: (4) */
633  secp256k1_fe_mul(&t, &t, &rr_alt); /* t = Ralt*(2*x3 - Q) (1) */
634  secp256k1_fe_add(&t, &n); /* t = Ralt*(2*x3 - Q) + M^3*Malt (3) */
635  secp256k1_fe_negate(&r->y, &t, 3); /* r->y = Ralt*(Q - 2x3) - M^3*Malt (4) */
637  secp256k1_fe_mul_int(&r->x, 4); /* r->x = X3 = 4*(Ralt^2-Q) */
638  secp256k1_fe_mul_int(&r->y, 4); /* r->y = Y3 = 4*Ralt*(Q - 2x3) - 4*M^3*Malt (4) */
639 
641  secp256k1_fe_cmov(&r->x, &b->x, a->infinity);
642  secp256k1_fe_cmov(&r->y, &b->y, a->infinity);
643  secp256k1_fe_cmov(&r->z, &fe_1, a->infinity);
644  r->infinity = infinity;
645 }
646 
648  /* Operations: 4 mul, 1 sqr */
649  secp256k1_fe zz;
651  secp256k1_fe_sqr(&zz, s);
652  secp256k1_fe_mul(&r->x, &r->x, &zz); /* r->x *= s^2 */
653  secp256k1_fe_mul(&r->y, &r->y, &zz);
654  secp256k1_fe_mul(&r->y, &r->y, s); /* r->y *= s^3 */
655  secp256k1_fe_mul(&r->z, &r->z, s); /* r->z *= s */
656 }
657 
659  secp256k1_fe x, y;
660  VERIFY_CHECK(!a->infinity);
661  x = a->x;
663  y = a->y;
665  secp256k1_fe_to_storage(&r->x, &x);
666  secp256k1_fe_to_storage(&r->y, &y);
667 }
668 
670  secp256k1_fe_from_storage(&r->x, &a->x);
671  secp256k1_fe_from_storage(&r->y, &a->y);
672  r->infinity = 0;
673 }
674 
676  secp256k1_fe_storage_cmov(&r->x, &a->x, flag);
677  secp256k1_fe_storage_cmov(&r->y, &a->y, flag);
678 }
679 
680 #ifdef USE_ENDOMORPHISM
681 static void secp256k1_ge_mul_lambda(secp256k1_ge *r, const secp256k1_ge *a) {
682  static const secp256k1_fe beta = SECP256K1_FE_CONST(
683  0x7ae96a2bul, 0x657c0710ul, 0x6e64479eul, 0xac3434e9ul,
684  0x9cf04975ul, 0x12f58995ul, 0xc1396c28ul, 0x719501eeul
685  );
686  *r = *a;
687  secp256k1_fe_mul(&r->x, &r->x, &beta);
688 }
689 #endif
690 
692  secp256k1_fe yz;
693 
694  if (a->infinity) {
695  return 0;
696  }
697 
698  /* We rely on the fact that the Jacobi symbol of 1 / a->z^3 is the same as
699  * that of a->z. Thus a->y / a->z^3 is a quadratic residue iff a->y * a->z
700  is */
701  secp256k1_fe_mul(&yz, &a->y, &a->z);
702  return secp256k1_fe_is_quad_var(&yz);
703 }
704 
705 #endif /* SECP256K1_GROUP_IMPL_H */
#define VERIFY_CHECK(cond)
Definition: util.h:67
static int secp256k1_fe_is_zero(const secp256k1_fe *a)
Verify whether a field element is zero.
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 void secp256k1_fe_normalize_var(secp256k1_fe *r)
Normalize a field element, without constant-time guarantee.
secp256k1_fe x
Definition: group.h:25
static void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *s)
Definition: group_impl.h:647
static void secp256k1_ge_set_gej_var(secp256k1_ge *r, secp256k1_gej *a)
Definition: group_impl.h:113
static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a)
Definition: group_impl.h:94
static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr)
Definition: group_impl.h:306
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 void secp256k1_fe_from_storage(secp256k1_fe *r, const secp256k1_fe_storage *a)
Convert a field element back from the storage type.
static SECP256K1_INLINE void secp256k1_gej_double_nonzero(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr)
Definition: group_impl.h:361
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:419
static void secp256k1_gej_clear(secp256k1_gej *r)
Definition: group_impl.h:208
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.
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_storage y
Definition: group.h:36
static void secp256k1_ge_set_gej(secp256k1_ge *r, secp256k1_gej *a)
Definition: group_impl.h:100
A group element of the secp256k1 curve, in jacobian coordinates.
Definition: group.h:24
static void secp256k1_fe_set_int(secp256k1_fe *r, int a)
Set a field element equal to a small integer.
static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe *a)
Convert a field element to the storage type.
static int secp256k1_gej_has_quad_y_var(const secp256k1_gej *a)
Definition: group_impl.h:691
#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
Definition: field_10x26.h:40
static void secp256k1_fe_clear(secp256k1_fe *a)
Sets a field element equal to zero, initializing all fields.
static int secp256k1_gej_is_valid_var(const secp256k1_gej *a)
Definition: group_impl.h:272
static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a)
Adds a field element to another.
static void secp256k1_fe_mul_int(secp256k1_fe *r, int a)
Multiplies the passed field element with a small integer constant.
static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b)
Definition: group_impl.h:525
static int secp256k1_ge_is_infinity(const secp256k1_ge *a)
Definition: group_impl.h:90
static int secp256k1_fe_is_odd(const secp256k1_fe *a)
Check the "oddness" of a field element.
static void secp256k1_gej_set_ge(secp256k1_gej *r, const secp256k1_ge *a)
Definition: group_impl.h:244
static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a)
Definition: group_impl.h:251
static const secp256k1_ge secp256k1_ge_const_g
Generator for secp256k1, value &#39;g&#39; defined in "Standards for Efficient Cryptography" (SEC2) 2...
Definition: group_impl.h:64
static void secp256k1_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storage *a)
Definition: group_impl.h:669
static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y)
Definition: group_impl.h:84
static void secp256k1_gej_set_infinity(secp256k1_gej *r)
Definition: group_impl.h:195
static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a)
Definition: group_impl.h:259
#define SECP256K1_INLINE
Definition: secp256k1.h:123
static const int CURVE_B
Definition: group_impl.h:71
int infinity
Definition: group.h:28
static int secp256k1_ge_set_xquad(secp256k1_ge *r, const secp256k1_fe *x)
Definition: group_impl.h:221
secp256k1_fe_storage x
Definition: group.h:35
static int secp256k1_fe_is_quad_var(const secp256k1_fe *a)
Checks whether a field element is a quadratic residue.
static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len)
Definition: group_impl.h:129
static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd)
Definition: group_impl.h:232
A group element of the secp256k1 curve, in affine coordinates.
Definition: group.h:14
secp256k1_fe x
Definition: group.h:15
static void secp256k1_fe_normalize_weak(secp256k1_fe *r)
Weakly normalize a field element: reduce it magnitude to 1, but don&#39;t fully normalize.
static int secp256k1_fe_normalizes_to_zero(secp256k1_fe *r)
Verify whether a field element represents zero i.e.
int infinity
Definition: group.h:17
static void secp256k1_ge_set_infinity(secp256k1_ge *r)
Definition: group_impl.h:202
static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a)
Sets a field element to be the square of another.
#define SECP256K1_GE_CONST(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)
Definition: group.h:20
static SECP256K1_INLINE void secp256k1_ge_storage_cmov(secp256k1_ge_storage *r, const secp256k1_ge_storage *a, int flag)
Definition: group_impl.h:675
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:468
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 void secp256k1_ge_to_storage(secp256k1_ge_storage *r, const secp256k1_ge *a)
Definition: group_impl.h:658
static int secp256k1_gej_is_infinity(const secp256k1_gej *a)
Definition: group_impl.h:268
static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi)
Definition: group_impl.h:74
secp256k1_fe z
Definition: group.h:27
static void secp256k1_fe_normalize(secp256k1_fe *r)
Field element module.
static int secp256k1_ge_is_valid_var(const secp256k1_ge *a)
Definition: group_impl.h:292
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:170
secp256k1_fe y
Definition: group.h:26
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 y
Definition: group.h:16
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 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_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr)
Definition: group_impl.h:366
static void secp256k1_ge_clear(secp256k1_ge *r)
Definition: group_impl.h:215
static int secp256k1_fe_normalizes_to_zero_var(secp256k1_fe *r)
Verify whether a field element represents zero i.e.