7 #ifndef SECP256K1_GROUP_IMPL_H 8 #define SECP256K1_GROUP_IMPL_H 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\ 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\ 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\ 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\ 48 #if defined(EXHAUSTIVE_TEST_ORDER) 49 # if EXHAUSTIVE_TEST_ORDER == 7 54 # elif EXHAUSTIVE_TEST_ORDER == 13 59 # elif EXHAUSTIVE_TEST_ORDER == 199 65 # error No known generator for the specified exhaustive test group order. 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);
100 secp256k1_fe_normalize_weak(&r->
y);
101 secp256k1_fe_negate(&r->
y, &r->
y, 1);
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);
120 secp256k1_ge_set_infinity(r);
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);
137 for (i = 0; i < len; i++) {
139 secp256k1_ge_set_infinity(&r[i]);
145 secp256k1_fe_mul(&r[i].x, &r[last_i].x, &
a[i].z);
153 secp256k1_fe_inv_var(&u, &r[last_i].x);
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);
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);
180 secp256k1_fe_normalize_weak(&
a[i].y);
187 secp256k1_fe_mul(&zs, &zs, &zr[i]);
193 secp256k1_ge_set_gej_zinv(&
a[i], &tmpa, &zs);
200 secp256k1_fe_clear(&r->
x);
201 secp256k1_fe_clear(&r->
y);
202 secp256k1_fe_clear(&r->
z);
205 static void secp256k1_ge_set_infinity(
secp256k1_ge *r) {
207 secp256k1_fe_clear(&r->
x);
208 secp256k1_fe_clear(&r->
y);
213 secp256k1_fe_clear(&r->
x);
214 secp256k1_fe_clear(&r->
y);
215 secp256k1_fe_clear(&r->
z);
220 secp256k1_fe_clear(&r->
x);
221 secp256k1_fe_clear(&r->
y);
227 secp256k1_fe_sqr(&x2, x);
228 secp256k1_fe_mul(&x3, x, &x2);
230 secp256k1_fe_add(&x3, &secp256k1_fe_const_b);
231 if (!secp256k1_fe_sqrt(&r->
y, &x3)) {
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);
246 secp256k1_fe_set_int(&r->
z, 1);
251 secp256k1_gej_neg(&tmp,
a);
252 secp256k1_gej_add_var(&tmp, &tmp, b, NULL);
253 return secp256k1_gej_is_infinity(&tmp);
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);
269 secp256k1_fe_normalize_weak(&r->
y);
270 secp256k1_fe_negate(&r->
y, &r->
y, 1);
277 static int secp256k1_ge_is_valid_var(
const secp256k1_ge *
a) {
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);
305 secp256k1_fe_mul(&r->
z, &
a->z, &
a->y);
306 secp256k1_fe_sqr(&s, &
a->y);
307 secp256k1_fe_sqr(&l, &
a->x);
308 secp256k1_fe_mul_int(&l, 3);
309 secp256k1_fe_half(&l);
310 secp256k1_fe_negate(&t, &s, 1);
311 secp256k1_fe_mul(&t, &t, &
a->x);
312 secp256k1_fe_sqr(&r->
x, &l);
313 secp256k1_fe_add(&r->
x, &t);
314 secp256k1_fe_add(&r->
x, &t);
315 secp256k1_fe_sqr(&s, &s);
316 secp256k1_fe_add(&t, &r->
x);
317 secp256k1_fe_mul(&r->
y, &t, &l);
318 secp256k1_fe_add(&r->
y, &s);
319 secp256k1_fe_negate(&r->
y, &r->
y, 2);
334 secp256k1_gej_set_infinity(r);
336 secp256k1_fe_set_int(rzr, 1);
343 secp256k1_fe_normalize_weak(rzr);
346 secp256k1_gej_double(r,
a);
351 secp256k1_fe z22, z12, u1, u2, s1, s2, h, i, h2, h3, t;
360 secp256k1_fe_set_int(rzr, 1);
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);
379 secp256k1_fe_set_int(rzr, 0);
381 secp256k1_gej_set_infinity(r);
387 secp256k1_fe_mul(&t, &h, &b->
z);
391 secp256k1_fe_mul(&r->
z, &
a->z, &t);
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);
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);
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);
414 secp256k1_gej_set_ge(r, b);
419 secp256k1_fe_set_int(rzr, 1);
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);
437 secp256k1_fe_set_int(rzr, 0);
439 secp256k1_gej_set_infinity(r);
448 secp256k1_fe_mul(&r->
z, &
a->z, &h);
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);
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);
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);
468 secp256k1_fe az, z12, u1, u2, s1, s2, h, i, h2, h3, t;
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);
493 secp256k1_fe_mul(&az, &
a->z, bzinv);
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);
506 secp256k1_gej_set_infinity(r);
512 secp256k1_fe_mul(&r->
z, &
a->z, &h);
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);
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);
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);
533 secp256k1_fe zz, u1, u2, s1, s2, t, tt, m, n, q, rr;
535 int infinity, degenerate;
589 secp256k1_fe_sqr(&zz, &
a->z);
590 u1 =
a->x; secp256k1_fe_normalize_weak(&u1);
591 secp256k1_fe_mul(&u2, &b->
x, &zz);
592 s1 =
a->y; secp256k1_fe_normalize_weak(&s1);
593 secp256k1_fe_mul(&s2, &b->
y, &zz);
594 secp256k1_fe_mul(&s2, &s2, &
a->z);
595 t = u1; secp256k1_fe_add(&t, &u2);
596 m = s1; secp256k1_fe_add(&m, &s2);
597 secp256k1_fe_sqr(&rr, &t);
598 secp256k1_fe_negate(&m_alt, &u2, 1);
599 secp256k1_fe_mul(&tt, &u1, &m_alt);
600 secp256k1_fe_add(&rr, &tt);
603 degenerate = secp256k1_fe_normalizes_to_zero(&m) &
604 secp256k1_fe_normalizes_to_zero(&rr);
611 secp256k1_fe_mul_int(&rr_alt, 2);
612 secp256k1_fe_add(&m_alt, &u1);
614 secp256k1_fe_cmov(&rr_alt, &rr, !degenerate);
615 secp256k1_fe_cmov(&m_alt, &m, !degenerate);
620 secp256k1_fe_sqr(&n, &m_alt);
621 secp256k1_fe_negate(&q, &t, 2);
622 secp256k1_fe_mul(&q, &q, &n);
627 secp256k1_fe_sqr(&n, &n);
628 secp256k1_fe_cmov(&n, &m, degenerate);
629 secp256k1_fe_sqr(&t, &rr_alt);
630 secp256k1_fe_mul(&r->
z, &
a->z, &m_alt);
631 infinity = secp256k1_fe_normalizes_to_zero(&r->
z) & ~
a->infinity;
632 secp256k1_fe_add(&t, &q);
634 secp256k1_fe_mul_int(&t, 2);
635 secp256k1_fe_add(&t, &q);
636 secp256k1_fe_mul(&t, &t, &rr_alt);
637 secp256k1_fe_add(&t, &n);
638 secp256k1_fe_negate(&r->
y, &t, 3);
639 secp256k1_fe_half(&r->
y);
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);
652 secp256k1_fe_sqr(&zz, s);
653 secp256k1_fe_mul(&r->
x, &r->
x, &zz);
654 secp256k1_fe_mul(&r->
y, &r->
y, &zz);
655 secp256k1_fe_mul(&r->
y, &r->
y, s);
656 secp256k1_fe_mul(&r->
z, &r->
z, s);
663 secp256k1_fe_normalize(&x);
665 secp256k1_fe_normalize(&y);
666 secp256k1_fe_to_storage(&r->
x, &x);
667 secp256k1_fe_to_storage(&r->
y, &y);
671 secp256k1_fe_from_storage(&r->
x, &
a->x);
672 secp256k1_fe_from_storage(&r->
y, &
a->y);
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);
685 secp256k1_fe_storage_cmov(&r->
x, &
a->x, flag);
686 secp256k1_fe_storage_cmov(&r->
y, &
a->y, flag);
691 secp256k1_fe_mul(&r->
x, &r->
x, &secp256k1_const_beta);
694 static int secp256k1_ge_is_in_correct_subgroup(
const secp256k1_ge* ge) {
695 #ifdef EXHAUSTIVE_TEST_ORDER 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);
707 return secp256k1_gej_is_infinity(&out);
#define VERIFY_CHECK(cond)
#define SECP256K1_G_ORDER_199
#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
#define SECP256K1_G_ORDER_7
#define SECP256K1_G_ORDER_13
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a