Electroneum
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 /* Begin of section generated by sage/gen_exhaustive_groups.sage. */
14 #define SECP256K1_G_ORDER_7 SECP256K1_GE_CONST(\
15  0x66625d13, 0x317ffe44, 0x63d32cff, 0x1ca02b9b,\
16  0xe5c6d070, 0x50b4b05e, 0x81cc30db, 0xf5166f0a,\
17  0x1e60e897, 0xa7c00c7c, 0x2df53eb6, 0x98274ff4,\
18  0x64252f42, 0x8ca44e17, 0x3b25418c, 0xff4ab0cf\
19 )
20 #define SECP256K1_G_ORDER_13 SECP256K1_GE_CONST(\
21  0xa2482ff8, 0x4bf34edf, 0xa51262fd, 0xe57921db,\
22  0xe0dd2cb7, 0xa5914790, 0xbc71631f, 0xc09704fb,\
23  0x942536cb, 0xa3e49492, 0x3a701cc3, 0xee3e443f,\
24  0xdf182aa9, 0x15b8aa6a, 0x166d3b19, 0xba84b045\
25 )
26 #define SECP256K1_G_ORDER_199 SECP256K1_GE_CONST(\
27  0x7fb07b5c, 0xd07c3bda, 0x553902e2, 0x7a87ea2c,\
28  0x35108a7f, 0x051f41e5, 0xb76abad5, 0x1f2703ad,\
29  0x0a251539, 0x5b4c4438, 0x952a634f, 0xac10dd4d,\
30  0x6d6f4745, 0x98990c27, 0x3a4f3116, 0xd32ff969\
31 )
32 
35 #define SECP256K1_G SECP256K1_GE_CONST(\
36  0x79be667e, 0xf9dcbbac, 0x55a06295, 0xce870b07,\
37  0x029bfcdb, 0x2dce28d9, 0x59f2815b, 0x16f81798,\
38  0x483ada77, 0x26a3c465, 0x5da4fbfc, 0x0e1108a8,\
39  0xfd17b448, 0xa6855419, 0x9c47d08f, 0xfb10d4b8\
40 )
41 /* These exhaustive group test orders and generators are chosen such that:
42  * - The field size is equal to that of secp256k1, so field code is the same.
43  * - The curve equation is of the form y^2=x^3+B for some small constant B.
44  * - The subgroup has a generator 2*P, where P.x is as small as possible.
45  * - The subgroup has size less than 1000 to permit exhaustive testing.
46  * - The subgroup admits an endomorphism of the form lambda*(x,y) == (beta*x,y).
47  */
48 #if defined(EXHAUSTIVE_TEST_ORDER)
49 # if EXHAUSTIVE_TEST_ORDER == 7
50 
51 static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_G_ORDER_7;
52 #define SECP256K1_B 6
53 
54 # elif EXHAUSTIVE_TEST_ORDER == 13
55 
56 static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_G_ORDER_13;
57 #define SECP256K1_B 2
58 
59 # elif EXHAUSTIVE_TEST_ORDER == 199
60 
61 static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_G_ORDER_199;
62 #define SECP256K1_B 4
63 
64 # else
65 # error No known generator for the specified exhaustive test group order.
66 # endif
67 #else
68 
69 static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_G;
70 #define SECP256K1_B 7
71 
72 #endif
73 /* End of section generated by sage/gen_exhaustive_groups.sage. */
74 
75 static const secp256k1_fe secp256k1_fe_const_b = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, SECP256K1_B);
76 
77 static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi) {
78  secp256k1_fe zi2;
79  secp256k1_fe zi3;
80  VERIFY_CHECK(!a->infinity);
81  secp256k1_fe_sqr(&zi2, zi);
82  secp256k1_fe_mul(&zi3, &zi2, zi);
83  secp256k1_fe_mul(&r->x, &a->x, &zi2);
84  secp256k1_fe_mul(&r->y, &a->y, &zi3);
85  r->infinity = a->infinity;
86 }
87 
88 static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y) {
89  r->infinity = 0;
90  r->x = *x;
91  r->y = *y;
92 }
93 
94 static int secp256k1_ge_is_infinity(const secp256k1_ge *a) {
95  return a->infinity;
96 }
97 
98 static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a) {
99  *r = *a;
100  secp256k1_fe_normalize_weak(&r->y);
101  secp256k1_fe_negate(&r->y, &r->y, 1);
102 }
103 
104 static void secp256k1_ge_set_gej(secp256k1_ge *r, secp256k1_gej *a) {
105  secp256k1_fe z2, z3;
106  r->infinity = a->infinity;
107  secp256k1_fe_inv(&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_gej_var(secp256k1_ge *r, secp256k1_gej *a) {
118  secp256k1_fe z2, z3;
119  if (a->infinity) {
120  secp256k1_ge_set_infinity(r);
121  return;
122  }
123  secp256k1_fe_inv_var(&a->z, &a->z);
124  secp256k1_fe_sqr(&z2, &a->z);
125  secp256k1_fe_mul(&z3, &a->z, &z2);
126  secp256k1_fe_mul(&a->x, &a->x, &z2);
127  secp256k1_fe_mul(&a->y, &a->y, &z3);
128  secp256k1_fe_set_int(&a->z, 1);
129  secp256k1_ge_set_xy(r, &a->x, &a->y);
130 }
131 
132 static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len) {
133  secp256k1_fe u;
134  size_t i;
135  size_t last_i = SIZE_MAX;
136 
137  for (i = 0; i < len; i++) {
138  if (a[i].infinity) {
139  secp256k1_ge_set_infinity(&r[i]);
140  } else {
141  /* Use destination's x coordinates as scratch space */
142  if (last_i == SIZE_MAX) {
143  r[i].x = a[i].z;
144  } else {
145  secp256k1_fe_mul(&r[i].x, &r[last_i].x, &a[i].z);
146  }
147  last_i = i;
148  }
149  }
150  if (last_i == SIZE_MAX) {
151  return;
152  }
153  secp256k1_fe_inv_var(&u, &r[last_i].x);
154 
155  i = last_i;
156  while (i > 0) {
157  i--;
158  if (!a[i].infinity) {
159  secp256k1_fe_mul(&r[last_i].x, &r[i].x, &u);
160  secp256k1_fe_mul(&u, &u, &a[last_i].z);
161  last_i = i;
162  }
163  }
164  VERIFY_CHECK(!a[last_i].infinity);
165  r[last_i].x = u;
166 
167  for (i = 0; i < len; i++) {
168  if (!a[i].infinity) {
169  secp256k1_ge_set_gej_zinv(&r[i], &a[i], &r[i].x);
170  }
171  }
172 }
173 
174 static void secp256k1_ge_table_set_globalz(size_t len, secp256k1_ge *a, const secp256k1_fe *zr) {
175  size_t i = len - 1;
176  secp256k1_fe zs;
177 
178  if (len > 0) {
179  /* Ensure all y values are in weak normal form for fast negation of points */
180  secp256k1_fe_normalize_weak(&a[i].y);
181  zs = zr[i];
182 
183  /* Work our way backwards, using the z-ratios to scale the x/y values. */
184  while (i > 0) {
185  secp256k1_gej tmpa;
186  if (i != len - 1) {
187  secp256k1_fe_mul(&zs, &zs, &zr[i]);
188  }
189  i--;
190  tmpa.x = a[i].x;
191  tmpa.y = a[i].y;
192  tmpa.infinity = 0;
193  secp256k1_ge_set_gej_zinv(&a[i], &tmpa, &zs);
194  }
195  }
196 }
197 
198 static void secp256k1_gej_set_infinity(secp256k1_gej *r) {
199  r->infinity = 1;
200  secp256k1_fe_clear(&r->x);
201  secp256k1_fe_clear(&r->y);
202  secp256k1_fe_clear(&r->z);
203 }
204 
205 static void secp256k1_ge_set_infinity(secp256k1_ge *r) {
206  r->infinity = 1;
207  secp256k1_fe_clear(&r->x);
208  secp256k1_fe_clear(&r->y);
209 }
210 
211 static void secp256k1_gej_clear(secp256k1_gej *r) {
212  r->infinity = 0;
213  secp256k1_fe_clear(&r->x);
214  secp256k1_fe_clear(&r->y);
215  secp256k1_fe_clear(&r->z);
216 }
217 
218 static void secp256k1_ge_clear(secp256k1_ge *r) {
219  r->infinity = 0;
220  secp256k1_fe_clear(&r->x);
221  secp256k1_fe_clear(&r->y);
222 }
223 
224 static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd) {
225  secp256k1_fe x2, x3;
226  r->x = *x;
227  secp256k1_fe_sqr(&x2, x);
228  secp256k1_fe_mul(&x3, x, &x2);
229  r->infinity = 0;
230  secp256k1_fe_add(&x3, &secp256k1_fe_const_b);
231  if (!secp256k1_fe_sqrt(&r->y, &x3)) {
232  return 0;
233  }
234  secp256k1_fe_normalize_var(&r->y);
235  if (secp256k1_fe_is_odd(&r->y) != odd) {
236  secp256k1_fe_negate(&r->y, &r->y, 1);
237  }
238  return 1;
239 
240 }
241 
242 static void secp256k1_gej_set_ge(secp256k1_gej *r, const secp256k1_ge *a) {
243  r->infinity = a->infinity;
244  r->x = a->x;
245  r->y = a->y;
246  secp256k1_fe_set_int(&r->z, 1);
247 }
248 
249 static int secp256k1_gej_eq_var(const secp256k1_gej *a, const secp256k1_gej *b) {
250  secp256k1_gej tmp;
251  secp256k1_gej_neg(&tmp, a);
252  secp256k1_gej_add_var(&tmp, &tmp, b, NULL);
253  return secp256k1_gej_is_infinity(&tmp);
254 }
255 
256 static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a) {
257  secp256k1_fe r, r2;
258  VERIFY_CHECK(!a->infinity);
259  secp256k1_fe_sqr(&r, &a->z); secp256k1_fe_mul(&r, &r, x);
260  r2 = a->x; secp256k1_fe_normalize_weak(&r2);
261  return secp256k1_fe_equal_var(&r, &r2);
262 }
263 
264 static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a) {
265  r->infinity = a->infinity;
266  r->x = a->x;
267  r->y = a->y;
268  r->z = a->z;
269  secp256k1_fe_normalize_weak(&r->y);
270  secp256k1_fe_negate(&r->y, &r->y, 1);
271 }
272 
273 static int secp256k1_gej_is_infinity(const secp256k1_gej *a) {
274  return a->infinity;
275 }
276 
277 static int secp256k1_ge_is_valid_var(const secp256k1_ge *a) {
278  secp256k1_fe y2, x3;
279  if (a->infinity) {
280  return 0;
281  }
282  /* y^2 = x^3 + 7 */
283  secp256k1_fe_sqr(&y2, &a->y);
284  secp256k1_fe_sqr(&x3, &a->x); secp256k1_fe_mul(&x3, &x3, &a->x);
285  secp256k1_fe_add(&x3, &secp256k1_fe_const_b);
286  secp256k1_fe_normalize_weak(&x3);
287  return secp256k1_fe_equal_var(&y2, &x3);
288 }
289 
290 static SECP256K1_INLINE void secp256k1_gej_double(secp256k1_gej *r, const secp256k1_gej *a) {
291  /* Operations: 3 mul, 4 sqr, 8 add/half/mul_int/negate */
292  secp256k1_fe l, s, t;
293 
294  r->infinity = a->infinity;
295 
296  /* Formula used:
297  * L = (3/2) * X1^2
298  * S = Y1^2
299  * T = -X1*S
300  * X3 = L^2 + 2*T
301  * Y3 = -(L*(X3 + T) + S^2)
302  * Z3 = Y1*Z1
303  */
304 
305  secp256k1_fe_mul(&r->z, &a->z, &a->y); /* Z3 = Y1*Z1 (1) */
306  secp256k1_fe_sqr(&s, &a->y); /* S = Y1^2 (1) */
307  secp256k1_fe_sqr(&l, &a->x); /* L = X1^2 (1) */
308  secp256k1_fe_mul_int(&l, 3); /* L = 3*X1^2 (3) */
309  secp256k1_fe_half(&l); /* L = 3/2*X1^2 (2) */
310  secp256k1_fe_negate(&t, &s, 1); /* T = -S (2) */
311  secp256k1_fe_mul(&t, &t, &a->x); /* T = -X1*S (1) */
312  secp256k1_fe_sqr(&r->x, &l); /* X3 = L^2 (1) */
313  secp256k1_fe_add(&r->x, &t); /* X3 = L^2 + T (2) */
314  secp256k1_fe_add(&r->x, &t); /* X3 = L^2 + 2*T (3) */
315  secp256k1_fe_sqr(&s, &s); /* S' = S^2 (1) */
316  secp256k1_fe_add(&t, &r->x); /* T' = X3 + T (4) */
317  secp256k1_fe_mul(&r->y, &t, &l); /* Y3 = L*(X3 + T) (1) */
318  secp256k1_fe_add(&r->y, &s); /* Y3 = L*(X3 + T) + S^2 (2) */
319  secp256k1_fe_negate(&r->y, &r->y, 2); /* Y3 = -(L*(X3 + T) + S^2) (3) */
320 }
321 
322 static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr) {
333  if (a->infinity) {
334  secp256k1_gej_set_infinity(r);
335  if (rzr != NULL) {
336  secp256k1_fe_set_int(rzr, 1);
337  }
338  return;
339  }
340 
341  if (rzr != NULL) {
342  *rzr = a->y;
343  secp256k1_fe_normalize_weak(rzr);
344  }
345 
346  secp256k1_gej_double(r, a);
347 }
348 
349 static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr) {
350  /* 12 mul, 4 sqr, 11 add/negate/normalizes_to_zero (ignoring special cases) */
351  secp256k1_fe z22, z12, u1, u2, s1, s2, h, i, h2, h3, t;
352 
353  if (a->infinity) {
354  VERIFY_CHECK(rzr == NULL);
355  *r = *b;
356  return;
357  }
358  if (b->infinity) {
359  if (rzr != NULL) {
360  secp256k1_fe_set_int(rzr, 1);
361  }
362  *r = *a;
363  return;
364  }
365 
366  secp256k1_fe_sqr(&z22, &b->z);
367  secp256k1_fe_sqr(&z12, &a->z);
368  secp256k1_fe_mul(&u1, &a->x, &z22);
369  secp256k1_fe_mul(&u2, &b->x, &z12);
370  secp256k1_fe_mul(&s1, &a->y, &z22); secp256k1_fe_mul(&s1, &s1, &b->z);
371  secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z);
372  secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
373  secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1);
374  if (secp256k1_fe_normalizes_to_zero_var(&h)) {
375  if (secp256k1_fe_normalizes_to_zero_var(&i)) {
376  secp256k1_gej_double_var(r, a, rzr);
377  } else {
378  if (rzr != NULL) {
379  secp256k1_fe_set_int(rzr, 0);
380  }
381  secp256k1_gej_set_infinity(r);
382  }
383  return;
384  }
385 
386  r->infinity = 0;
387  secp256k1_fe_mul(&t, &h, &b->z);
388  if (rzr != NULL) {
389  *rzr = t;
390  }
391  secp256k1_fe_mul(&r->z, &a->z, &t);
392 
393  secp256k1_fe_sqr(&h2, &h);
394  secp256k1_fe_negate(&h2, &h2, 1);
395  secp256k1_fe_mul(&h3, &h2, &h);
396  secp256k1_fe_mul(&t, &u1, &h2);
397 
398  secp256k1_fe_sqr(&r->x, &i);
399  secp256k1_fe_add(&r->x, &h3);
400  secp256k1_fe_add(&r->x, &t);
401  secp256k1_fe_add(&r->x, &t);
402 
403  secp256k1_fe_add(&t, &r->x);
404  secp256k1_fe_mul(&r->y, &t, &i);
405  secp256k1_fe_mul(&h3, &h3, &s1);
406  secp256k1_fe_add(&r->y, &h3);
407 }
408 
409 static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, secp256k1_fe *rzr) {
410  /* 8 mul, 3 sqr, 13 add/negate/normalize_weak/normalizes_to_zero (ignoring special cases) */
411  secp256k1_fe z12, u1, u2, s1, s2, h, i, h2, h3, t;
412  if (a->infinity) {
413  VERIFY_CHECK(rzr == NULL);
414  secp256k1_gej_set_ge(r, b);
415  return;
416  }
417  if (b->infinity) {
418  if (rzr != NULL) {
419  secp256k1_fe_set_int(rzr, 1);
420  }
421  *r = *a;
422  return;
423  }
424 
425  secp256k1_fe_sqr(&z12, &a->z);
426  u1 = a->x; secp256k1_fe_normalize_weak(&u1);
427  secp256k1_fe_mul(&u2, &b->x, &z12);
428  s1 = a->y; secp256k1_fe_normalize_weak(&s1);
429  secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z);
430  secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
431  secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1);
432  if (secp256k1_fe_normalizes_to_zero_var(&h)) {
433  if (secp256k1_fe_normalizes_to_zero_var(&i)) {
434  secp256k1_gej_double_var(r, a, rzr);
435  } else {
436  if (rzr != NULL) {
437  secp256k1_fe_set_int(rzr, 0);
438  }
439  secp256k1_gej_set_infinity(r);
440  }
441  return;
442  }
443 
444  r->infinity = 0;
445  if (rzr != NULL) {
446  *rzr = h;
447  }
448  secp256k1_fe_mul(&r->z, &a->z, &h);
449 
450  secp256k1_fe_sqr(&h2, &h);
451  secp256k1_fe_negate(&h2, &h2, 1);
452  secp256k1_fe_mul(&h3, &h2, &h);
453  secp256k1_fe_mul(&t, &u1, &h2);
454 
455  secp256k1_fe_sqr(&r->x, &i);
456  secp256k1_fe_add(&r->x, &h3);
457  secp256k1_fe_add(&r->x, &t);
458  secp256k1_fe_add(&r->x, &t);
459 
460  secp256k1_fe_add(&t, &r->x);
461  secp256k1_fe_mul(&r->y, &t, &i);
462  secp256k1_fe_mul(&h3, &h3, &s1);
463  secp256k1_fe_add(&r->y, &h3);
464 }
465 
466 static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, const secp256k1_fe *bzinv) {
467  /* 9 mul, 3 sqr, 13 add/negate/normalize_weak/normalizes_to_zero (ignoring special cases) */
468  secp256k1_fe az, z12, u1, u2, s1, s2, h, i, h2, h3, t;
469 
470  if (a->infinity) {
471  secp256k1_fe bzinv2, bzinv3;
472  r->infinity = b->infinity;
473  secp256k1_fe_sqr(&bzinv2, bzinv);
474  secp256k1_fe_mul(&bzinv3, &bzinv2, bzinv);
475  secp256k1_fe_mul(&r->x, &b->x, &bzinv2);
476  secp256k1_fe_mul(&r->y, &b->y, &bzinv3);
477  secp256k1_fe_set_int(&r->z, 1);
478  return;
479  }
480  if (b->infinity) {
481  *r = *a;
482  return;
483  }
484 
493  secp256k1_fe_mul(&az, &a->z, bzinv);
494 
495  secp256k1_fe_sqr(&z12, &az);
496  u1 = a->x; secp256k1_fe_normalize_weak(&u1);
497  secp256k1_fe_mul(&u2, &b->x, &z12);
498  s1 = a->y; secp256k1_fe_normalize_weak(&s1);
499  secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &az);
500  secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
501  secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1);
502  if (secp256k1_fe_normalizes_to_zero_var(&h)) {
503  if (secp256k1_fe_normalizes_to_zero_var(&i)) {
504  secp256k1_gej_double_var(r, a, NULL);
505  } else {
506  secp256k1_gej_set_infinity(r);
507  }
508  return;
509  }
510 
511  r->infinity = 0;
512  secp256k1_fe_mul(&r->z, &a->z, &h);
513 
514  secp256k1_fe_sqr(&h2, &h);
515  secp256k1_fe_negate(&h2, &h2, 1);
516  secp256k1_fe_mul(&h3, &h2, &h);
517  secp256k1_fe_mul(&t, &u1, &h2);
518 
519  secp256k1_fe_sqr(&r->x, &i);
520  secp256k1_fe_add(&r->x, &h3);
521  secp256k1_fe_add(&r->x, &t);
522  secp256k1_fe_add(&r->x, &t);
523 
524  secp256k1_fe_add(&t, &r->x);
525  secp256k1_fe_mul(&r->y, &t, &i);
526  secp256k1_fe_mul(&h3, &h3, &s1);
527  secp256k1_fe_add(&r->y, &h3);
528 }
529 
530 
531 static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b) {
532  /* Operations: 7 mul, 5 sqr, 24 add/cmov/half/mul_int/negate/normalize_weak/normalizes_to_zero */
533  secp256k1_fe zz, u1, u2, s1, s2, t, tt, m, n, q, rr;
534  secp256k1_fe m_alt, rr_alt;
535  int infinity, degenerate;
536  VERIFY_CHECK(!b->infinity);
537  VERIFY_CHECK(a->infinity == 0 || a->infinity == 1);
538 
589  secp256k1_fe_sqr(&zz, &a->z); /* z = Z1^2 */
590  u1 = a->x; secp256k1_fe_normalize_weak(&u1); /* u1 = U1 = X1*Z2^2 (1) */
591  secp256k1_fe_mul(&u2, &b->x, &zz); /* u2 = U2 = X2*Z1^2 (1) */
592  s1 = a->y; secp256k1_fe_normalize_weak(&s1); /* s1 = S1 = Y1*Z2^3 (1) */
593  secp256k1_fe_mul(&s2, &b->y, &zz); /* s2 = Y2*Z1^2 (1) */
594  secp256k1_fe_mul(&s2, &s2, &a->z); /* s2 = S2 = Y2*Z1^3 (1) */
595  t = u1; secp256k1_fe_add(&t, &u2); /* t = T = U1+U2 (2) */
596  m = s1; secp256k1_fe_add(&m, &s2); /* m = M = S1+S2 (2) */
597  secp256k1_fe_sqr(&rr, &t); /* rr = T^2 (1) */
598  secp256k1_fe_negate(&m_alt, &u2, 1); /* Malt = -X2*Z1^2 */
599  secp256k1_fe_mul(&tt, &u1, &m_alt); /* tt = -U1*U2 (2) */
600  secp256k1_fe_add(&rr, &tt); /* rr = R = T^2-U1*U2 (3) */
603  degenerate = secp256k1_fe_normalizes_to_zero(&m) &
604  secp256k1_fe_normalizes_to_zero(&rr);
605  /* This only occurs when y1 == -y2 and x1^3 == x2^3, but x1 != x2.
606  * This means either x1 == beta*x2 or beta*x1 == x2, where beta is
607  * a nontrivial cube root of one. In either case, an alternate
608  * non-indeterminate expression for lambda is (y1 - y2)/(x1 - x2),
609  * so we set R/M equal to this. */
610  rr_alt = s1;
611  secp256k1_fe_mul_int(&rr_alt, 2); /* rr = Y1*Z2^3 - Y2*Z1^3 (2) */
612  secp256k1_fe_add(&m_alt, &u1); /* Malt = X1*Z2^2 - X2*Z1^2 */
613 
614  secp256k1_fe_cmov(&rr_alt, &rr, !degenerate);
615  secp256k1_fe_cmov(&m_alt, &m, !degenerate);
616  /* Now Ralt / Malt = lambda and is guaranteed not to be 0/0.
617  * From here on out Ralt and Malt represent the numerator
618  * and denominator of lambda; R and M represent the explicit
619  * expressions x1^2 + x2^2 + x1x2 and y1 + y2. */
620  secp256k1_fe_sqr(&n, &m_alt); /* n = Malt^2 (1) */
621  secp256k1_fe_negate(&q, &t, 2); /* q = -T (3) */
622  secp256k1_fe_mul(&q, &q, &n); /* q = Q = -T*Malt^2 (1) */
623  /* These two lines use the observation that either M == Malt or M == 0,
624  * so M^3 * Malt is either Malt^4 (which is computed by squaring), or
625  * zero (which is "computed" by cmov). So the cost is one squaring
626  * versus two multiplications. */
627  secp256k1_fe_sqr(&n, &n);
628  secp256k1_fe_cmov(&n, &m, degenerate); /* n = M^3 * Malt (2) */
629  secp256k1_fe_sqr(&t, &rr_alt); /* t = Ralt^2 (1) */
630  secp256k1_fe_mul(&r->z, &a->z, &m_alt); /* r->z = Z3 = Malt*Z (1) */
631  infinity = secp256k1_fe_normalizes_to_zero(&r->z) & ~a->infinity;
632  secp256k1_fe_add(&t, &q); /* t = Ralt^2 + Q (2) */
633  r->x = t; /* r->x = X3 = Ralt^2 + Q (2) */
634  secp256k1_fe_mul_int(&t, 2); /* t = 2*X3 (4) */
635  secp256k1_fe_add(&t, &q); /* t = 2*X3 + Q (5) */
636  secp256k1_fe_mul(&t, &t, &rr_alt); /* t = Ralt*(2*X3 + Q) (1) */
637  secp256k1_fe_add(&t, &n); /* t = Ralt*(2*X3 + Q) + M^3*Malt (3) */
638  secp256k1_fe_negate(&r->y, &t, 3); /* r->y = -(Ralt*(2*X3 + Q) + M^3*Malt) (4) */
639  secp256k1_fe_half(&r->y); /* r->y = Y3 = -(Ralt*(2*X3 + Q) + M^3*Malt)/2 (3) */
640 
642  secp256k1_fe_cmov(&r->x, &b->x, a->infinity);
643  secp256k1_fe_cmov(&r->y, &b->y, a->infinity);
644  secp256k1_fe_cmov(&r->z, &secp256k1_fe_one, a->infinity);
645  r->infinity = infinity;
646 }
647 
648 static void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *s) {
649  /* Operations: 4 mul, 1 sqr */
650  secp256k1_fe zz;
651  VERIFY_CHECK(!secp256k1_fe_is_zero(s));
652  secp256k1_fe_sqr(&zz, s);
653  secp256k1_fe_mul(&r->x, &r->x, &zz); /* r->x *= s^2 */
654  secp256k1_fe_mul(&r->y, &r->y, &zz);
655  secp256k1_fe_mul(&r->y, &r->y, s); /* r->y *= s^3 */
656  secp256k1_fe_mul(&r->z, &r->z, s); /* r->z *= s */
657 }
658 
659 static void secp256k1_ge_to_storage(secp256k1_ge_storage *r, const secp256k1_ge *a) {
660  secp256k1_fe x, y;
661  VERIFY_CHECK(!a->infinity);
662  x = a->x;
663  secp256k1_fe_normalize(&x);
664  y = a->y;
665  secp256k1_fe_normalize(&y);
666  secp256k1_fe_to_storage(&r->x, &x);
667  secp256k1_fe_to_storage(&r->y, &y);
668 }
669 
670 static void secp256k1_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storage *a) {
671  secp256k1_fe_from_storage(&r->x, &a->x);
672  secp256k1_fe_from_storage(&r->y, &a->y);
673  r->infinity = 0;
674 }
675 
676 static SECP256K1_INLINE void secp256k1_gej_cmov(secp256k1_gej *r, const secp256k1_gej *a, int flag) {
677  secp256k1_fe_cmov(&r->x, &a->x, flag);
678  secp256k1_fe_cmov(&r->y, &a->y, flag);
679  secp256k1_fe_cmov(&r->z, &a->z, flag);
680 
681  r->infinity ^= (r->infinity ^ a->infinity) & flag;
682 }
683 
684 static SECP256K1_INLINE void secp256k1_ge_storage_cmov(secp256k1_ge_storage *r, const secp256k1_ge_storage *a, int flag) {
685  secp256k1_fe_storage_cmov(&r->x, &a->x, flag);
686  secp256k1_fe_storage_cmov(&r->y, &a->y, flag);
687 }
688 
689 static void secp256k1_ge_mul_lambda(secp256k1_ge *r, const secp256k1_ge *a) {
690  *r = *a;
691  secp256k1_fe_mul(&r->x, &r->x, &secp256k1_const_beta);
692 }
693 
694 static int secp256k1_ge_is_in_correct_subgroup(const secp256k1_ge* ge) {
695 #ifdef EXHAUSTIVE_TEST_ORDER
697  int i;
698 
699  /* A very simple EC multiplication ladder that avoids a dependency on ecmult. */
700  secp256k1_gej_set_infinity(&out);
701  for (i = 0; i < 32; ++i) {
702  secp256k1_gej_double_var(&out, &out, NULL);
703  if ((((uint32_t)EXHAUSTIVE_TEST_ORDER) >> (31 - i)) & 1) {
704  secp256k1_gej_add_ge_var(&out, &out, ge, NULL);
705  }
706  }
707  return secp256k1_gej_is_infinity(&out);
708 #else
709  (void)ge;
710  /* The real secp256k1 group has cofactor 1, so the subgroup is the entire curve. */
711  return 1;
712 #endif
713 }
714 
715 #endif /* SECP256K1_GROUP_IMPL_H */
#define VERIFY_CHECK(cond)
Definition: util.h:96
#define SECP256K1_G_ORDER_199
Definition: group_impl.h:26
secp256k1_fe x
Definition: group.h:29
#define SECP256K1_G
Definition: group_impl.h:35
secp256k1_fe_storage y
Definition: group.h:40
#define SECP256K1_B
Definition: group_impl.h:70
#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
Definition: field_10x26.h:40
#define SECP256K1_INLINE
Definition: secp256k1.h:131
unsigned int uint32_t
Definition: stdint.h:126
int infinity
Definition: group.h:32
secp256k1_fe_storage x
Definition: group.h:39
secp256k1_fe x
Definition: group.h:17
#define SECP256K1_G_ORDER_7
Definition: group_impl.h:14
int infinity
Definition: group.h:19
#define SECP256K1_G_ORDER_13
Definition: group_impl.h:20
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
#define SIZE_MAX
Definition: stdint.h:252
secp256k1_fe z
Definition: group.h:31
secp256k1_fe y
Definition: group.h:30
secp256k1_fe y
Definition: group.h:18