Bitcoin Core 29.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 <string.h>
11
12#include "field.h"
13#include "group.h"
14#include "util.h"
15
16/* Begin of section generated by sage/gen_exhaustive_groups.sage. */
17#define SECP256K1_G_ORDER_7 SECP256K1_GE_CONST(\
18 0x66625d13, 0x317ffe44, 0x63d32cff, 0x1ca02b9b,\
19 0xe5c6d070, 0x50b4b05e, 0x81cc30db, 0xf5166f0a,\
20 0x1e60e897, 0xa7c00c7c, 0x2df53eb6, 0x98274ff4,\
21 0x64252f42, 0x8ca44e17, 0x3b25418c, 0xff4ab0cf\
22)
23#define SECP256K1_G_ORDER_13 SECP256K1_GE_CONST(\
24 0xa2482ff8, 0x4bf34edf, 0xa51262fd, 0xe57921db,\
25 0xe0dd2cb7, 0xa5914790, 0xbc71631f, 0xc09704fb,\
26 0x942536cb, 0xa3e49492, 0x3a701cc3, 0xee3e443f,\
27 0xdf182aa9, 0x15b8aa6a, 0x166d3b19, 0xba84b045\
28)
29#define SECP256K1_G_ORDER_199 SECP256K1_GE_CONST(\
30 0x7fb07b5c, 0xd07c3bda, 0x553902e2, 0x7a87ea2c,\
31 0x35108a7f, 0x051f41e5, 0xb76abad5, 0x1f2703ad,\
32 0x0a251539, 0x5b4c4438, 0x952a634f, 0xac10dd4d,\
33 0x6d6f4745, 0x98990c27, 0x3a4f3116, 0xd32ff969\
34)
38#define SECP256K1_G SECP256K1_GE_CONST(\
39 0x79be667e, 0xf9dcbbac, 0x55a06295, 0xce870b07,\
40 0x029bfcdb, 0x2dce28d9, 0x59f2815b, 0x16f81798,\
41 0x483ada77, 0x26a3c465, 0x5da4fbfc, 0x0e1108a8,\
42 0xfd17b448, 0xa6855419, 0x9c47d08f, 0xfb10d4b8\
43)
44/* These exhaustive group test orders and generators are chosen such that:
45 * - The field size is equal to that of secp256k1, so field code is the same.
46 * - The curve equation is of the form y^2=x^3+B for some small constant B.
47 * - The subgroup has a generator 2*P, where P.x is as small as possible.
48 * - The subgroup has size less than 1000 to permit exhaustive testing.
49 * - The subgroup admits an endomorphism of the form lambda*(x,y) == (beta*x,y).
50 */
51#if defined(EXHAUSTIVE_TEST_ORDER)
52# if EXHAUSTIVE_TEST_ORDER == 7
53
55#define SECP256K1_B 6
56
57# elif EXHAUSTIVE_TEST_ORDER == 13
58
60#define SECP256K1_B 2
61
62# elif EXHAUSTIVE_TEST_ORDER == 199
63
65#define SECP256K1_B 4
66
67# else
68# error No known generator for the specified exhaustive test group order.
69# endif
70#else
71
73#define SECP256K1_B 7
74
75#endif
76/* End of section generated by sage/gen_exhaustive_groups.sage. */
77
78static void secp256k1_ge_verify(const secp256k1_ge *a) {
83 VERIFY_CHECK(a->infinity == 0 || a->infinity == 1);
84 (void)a;
85}
86
87static void secp256k1_gej_verify(const secp256k1_gej *a) {
94 VERIFY_CHECK(a->infinity == 0 || a->infinity == 1);
95 (void)a;
96}
97
98/* Set r to the affine coordinates of Jacobian point (a.x, a.y, 1/zi). */
100 secp256k1_fe zi2;
101 secp256k1_fe zi3;
105
106 secp256k1_fe_sqr(&zi2, zi);
107 secp256k1_fe_mul(&zi3, &zi2, zi);
108 secp256k1_fe_mul(&r->x, &a->x, &zi2);
109 secp256k1_fe_mul(&r->y, &a->y, &zi3);
110 r->infinity = a->infinity;
111
113}
114
115/* Set r to the affine coordinates of Jacobian point (a.x, a.y, 1/zi). */
117 secp256k1_fe zi2;
118 secp256k1_fe zi3;
122
123 secp256k1_fe_sqr(&zi2, zi);
124 secp256k1_fe_mul(&zi3, &zi2, zi);
125 secp256k1_fe_mul(&r->x, &a->x, &zi2);
126 secp256k1_fe_mul(&r->y, &a->y, &zi3);
127 r->infinity = a->infinity;
128
130}
131
132static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y) {
135
136 r->infinity = 0;
137 r->x = *x;
138 r->y = *y;
139
141}
142
145
146 return a->infinity;
147}
148
149static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a) {
151
152 *r = *a;
154 secp256k1_fe_negate(&r->y, &r->y, 1);
155
157}
158
160 secp256k1_fe z2, z3;
162
163 r->infinity = a->infinity;
164 secp256k1_fe_inv(&a->z, &a->z);
165 secp256k1_fe_sqr(&z2, &a->z);
166 secp256k1_fe_mul(&z3, &a->z, &z2);
167 secp256k1_fe_mul(&a->x, &a->x, &z2);
168 secp256k1_fe_mul(&a->y, &a->y, &z3);
169 secp256k1_fe_set_int(&a->z, 1);
170 r->x = a->x;
171 r->y = a->y;
172
175}
176
178 secp256k1_fe z2, z3;
180
183 return;
184 }
185 r->infinity = 0;
186 secp256k1_fe_inv_var(&a->z, &a->z);
187 secp256k1_fe_sqr(&z2, &a->z);
188 secp256k1_fe_mul(&z3, &a->z, &z2);
189 secp256k1_fe_mul(&a->x, &a->x, &z2);
190 secp256k1_fe_mul(&a->y, &a->y, &z3);
191 secp256k1_fe_set_int(&a->z, 1);
192 secp256k1_ge_set_xy(r, &a->x, &a->y);
193
196}
197
198static void secp256k1_ge_set_all_gej(secp256k1_ge *r, const secp256k1_gej *a, size_t len) {
199 secp256k1_fe u;
200 size_t i;
201#ifdef VERIFY
202 for (i = 0; i < len; i++) {
205 }
206#endif
207
208 if (len == 0) {
209 return;
210 }
211
212 /* Use destination's x coordinates as scratch space */
213 r[0].x = a[0].z;
214 for (i = 1; i < len; i++) {
215 secp256k1_fe_mul(&r[i].x, &r[i - 1].x, &a[i].z);
216 }
217 secp256k1_fe_inv(&u, &r[len - 1].x);
218
219 for (i = len - 1; i > 0; i--) {
220 secp256k1_fe_mul(&r[i].x, &r[i - 1].x, &u);
221 secp256k1_fe_mul(&u, &u, &a[i].z);
222 }
223 r[0].x = u;
224
225 for (i = 0; i < len; i++) {
226 secp256k1_ge_set_gej_zinv(&r[i], &a[i], &r[i].x);
227 }
228
229#ifdef VERIFY
230 for (i = 0; i < len; i++) {
231 SECP256K1_GE_VERIFY(&r[i]);
232 }
233#endif
234}
235
236static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len) {
237 secp256k1_fe u;
238 size_t i;
239 size_t last_i = SIZE_MAX;
240#ifdef VERIFY
241 for (i = 0; i < len; i++) {
243 }
244#endif
245
246 for (i = 0; i < len; i++) {
247 if (a[i].infinity) {
249 } else {
250 /* Use destination's x coordinates as scratch space */
251 if (last_i == SIZE_MAX) {
252 r[i].x = a[i].z;
253 } else {
254 secp256k1_fe_mul(&r[i].x, &r[last_i].x, &a[i].z);
255 }
256 last_i = i;
257 }
258 }
259 if (last_i == SIZE_MAX) {
260 return;
261 }
262 secp256k1_fe_inv_var(&u, &r[last_i].x);
263
264 i = last_i;
265 while (i > 0) {
266 i--;
267 if (!a[i].infinity) {
268 secp256k1_fe_mul(&r[last_i].x, &r[i].x, &u);
269 secp256k1_fe_mul(&u, &u, &a[last_i].z);
270 last_i = i;
271 }
272 }
273 VERIFY_CHECK(!a[last_i].infinity);
274 r[last_i].x = u;
275
276 for (i = 0; i < len; i++) {
277 if (!a[i].infinity) {
278 secp256k1_ge_set_gej_zinv(&r[i], &a[i], &r[i].x);
279 }
280 }
281
282#ifdef VERIFY
283 for (i = 0; i < len; i++) {
284 SECP256K1_GE_VERIFY(&r[i]);
285 }
286#endif
287}
288
289static void secp256k1_ge_table_set_globalz(size_t len, secp256k1_ge *a, const secp256k1_fe *zr) {
290 size_t i;
291 secp256k1_fe zs;
292#ifdef VERIFY
293 for (i = 0; i < len; i++) {
294 SECP256K1_GE_VERIFY(&a[i]);
295 SECP256K1_FE_VERIFY(&zr[i]);
296 }
297#endif
298
299 if (len > 0) {
300 i = len - 1;
301 /* Ensure all y values are in weak normal form for fast negation of points */
303 zs = zr[i];
304
305 /* Work our way backwards, using the z-ratios to scale the x/y values. */
306 while (i > 0) {
307 if (i != len - 1) {
308 secp256k1_fe_mul(&zs, &zs, &zr[i]);
309 }
310 i--;
311 secp256k1_ge_set_ge_zinv(&a[i], &a[i], &zs);
312 }
313 }
314
315#ifdef VERIFY
316 for (i = 0; i < len; i++) {
317 SECP256K1_GE_VERIFY(&a[i]);
318 }
319#endif
320}
321
323 r->infinity = 1;
324 secp256k1_fe_set_int(&r->x, 0);
325 secp256k1_fe_set_int(&r->y, 0);
326 secp256k1_fe_set_int(&r->z, 0);
327
329}
330
332 r->infinity = 1;
333 secp256k1_fe_set_int(&r->x, 0);
334 secp256k1_fe_set_int(&r->y, 0);
335
337}
338
341}
342
345}
346
347static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd) {
348 secp256k1_fe x2, x3;
349 int ret;
351
352 r->x = *x;
353 secp256k1_fe_sqr(&x2, x);
354 secp256k1_fe_mul(&x3, x, &x2);
355 r->infinity = 0;
357 ret = secp256k1_fe_sqrt(&r->y, &x3);
359 if (secp256k1_fe_is_odd(&r->y) != odd) {
360 secp256k1_fe_negate(&r->y, &r->y, 1);
361 }
362
364 return ret;
365}
366
369
370 r->infinity = a->infinity;
371 r->x = a->x;
372 r->y = a->y;
373 secp256k1_fe_set_int(&r->z, 1);
374
376}
377
378static int secp256k1_gej_eq_var(const secp256k1_gej *a, const secp256k1_gej *b) {
379 secp256k1_gej tmp;
382
383 secp256k1_gej_neg(&tmp, a);
384 secp256k1_gej_add_var(&tmp, &tmp, b, NULL);
385 return secp256k1_gej_is_infinity(&tmp);
386}
387
388static int secp256k1_gej_eq_ge_var(const secp256k1_gej *a, const secp256k1_ge *b) {
389 secp256k1_gej tmp;
392
393 secp256k1_gej_neg(&tmp, a);
394 secp256k1_gej_add_ge_var(&tmp, &tmp, b, NULL);
395 return secp256k1_gej_is_infinity(&tmp);
396}
397
398static int secp256k1_ge_eq_var(const secp256k1_ge *a, const secp256k1_ge *b) {
399 secp256k1_fe tmp;
402
403 if (a->infinity != b->infinity) return 0;
404 if (a->infinity) return 1;
405
406 tmp = a->x;
408 if (!secp256k1_fe_equal(&tmp, &b->x)) return 0;
409
410 tmp = a->y;
412 if (!secp256k1_fe_equal(&tmp, &b->y)) return 0;
413
414 return 1;
415}
416
417static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a) {
418 secp256k1_fe r;
422
423 secp256k1_fe_sqr(&r, &a->z); secp256k1_fe_mul(&r, &r, x);
424 return secp256k1_fe_equal(&r, &a->x);
425}
426
429
430 r->infinity = a->infinity;
431 r->x = a->x;
432 r->y = a->y;
433 r->z = a->z;
435 secp256k1_fe_negate(&r->y, &r->y, 1);
436
438}
439
442
443 return a->infinity;
444}
445
447 secp256k1_fe y2, x3;
449
450 if (a->infinity) {
451 return 0;
452 }
453 /* y^2 = x^3 + 7 */
454 secp256k1_fe_sqr(&y2, &a->y);
455 secp256k1_fe_sqr(&x3, &a->x); secp256k1_fe_mul(&x3, &x3, &a->x);
457 return secp256k1_fe_equal(&y2, &x3);
458}
459
461 /* Operations: 3 mul, 4 sqr, 8 add/half/mul_int/negate */
462 secp256k1_fe l, s, t;
464
465 r->infinity = a->infinity;
466
467 /* Formula used:
468 * L = (3/2) * X1^2
469 * S = Y1^2
470 * T = -X1*S
471 * X3 = L^2 + 2*T
472 * Y3 = -(L*(X3 + T) + S^2)
473 * Z3 = Y1*Z1
474 */
475
476 secp256k1_fe_mul(&r->z, &a->z, &a->y); /* Z3 = Y1*Z1 (1) */
477 secp256k1_fe_sqr(&s, &a->y); /* S = Y1^2 (1) */
478 secp256k1_fe_sqr(&l, &a->x); /* L = X1^2 (1) */
479 secp256k1_fe_mul_int(&l, 3); /* L = 3*X1^2 (3) */
480 secp256k1_fe_half(&l); /* L = 3/2*X1^2 (2) */
481 secp256k1_fe_negate(&t, &s, 1); /* T = -S (2) */
482 secp256k1_fe_mul(&t, &t, &a->x); /* T = -X1*S (1) */
483 secp256k1_fe_sqr(&r->x, &l); /* X3 = L^2 (1) */
484 secp256k1_fe_add(&r->x, &t); /* X3 = L^2 + T (2) */
485 secp256k1_fe_add(&r->x, &t); /* X3 = L^2 + 2*T (3) */
486 secp256k1_fe_sqr(&s, &s); /* S' = S^2 (1) */
487 secp256k1_fe_add(&t, &r->x); /* T' = X3 + T (4) */
488 secp256k1_fe_mul(&r->y, &t, &l); /* Y3 = L*(X3 + T) (1) */
489 secp256k1_fe_add(&r->y, &s); /* Y3 = L*(X3 + T) + S^2 (2) */
490 secp256k1_fe_negate(&r->y, &r->y, 2); /* Y3 = -(L*(X3 + T) + S^2) (3) */
491
493}
494
497
508 if (a->infinity) {
510 if (rzr != NULL) {
511 secp256k1_fe_set_int(rzr, 1);
512 }
513 return;
514 }
515
516 if (rzr != NULL) {
517 *rzr = a->y;
519 }
520
522
524}
525
527 /* 12 mul, 4 sqr, 11 add/negate/normalizes_to_zero (ignoring special cases) */
528 secp256k1_fe z22, z12, u1, u2, s1, s2, h, i, h2, h3, t;
531
532 if (a->infinity) {
533 VERIFY_CHECK(rzr == NULL);
534 *r = *b;
535 return;
536 }
537 if (b->infinity) {
538 if (rzr != NULL) {
539 secp256k1_fe_set_int(rzr, 1);
540 }
541 *r = *a;
542 return;
543 }
544
545 secp256k1_fe_sqr(&z22, &b->z);
546 secp256k1_fe_sqr(&z12, &a->z);
547 secp256k1_fe_mul(&u1, &a->x, &z22);
548 secp256k1_fe_mul(&u2, &b->x, &z12);
549 secp256k1_fe_mul(&s1, &a->y, &z22); secp256k1_fe_mul(&s1, &s1, &b->z);
550 secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z);
551 secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2);
552 secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1);
555 secp256k1_gej_double_var(r, a, rzr);
556 } else {
557 if (rzr != NULL) {
558 secp256k1_fe_set_int(rzr, 0);
559 }
561 }
562 return;
563 }
564
565 r->infinity = 0;
566 secp256k1_fe_mul(&t, &h, &b->z);
567 if (rzr != NULL) {
568 *rzr = t;
569 }
570 secp256k1_fe_mul(&r->z, &a->z, &t);
571
572 secp256k1_fe_sqr(&h2, &h);
573 secp256k1_fe_negate(&h2, &h2, 1);
574 secp256k1_fe_mul(&h3, &h2, &h);
575 secp256k1_fe_mul(&t, &u1, &h2);
576
577 secp256k1_fe_sqr(&r->x, &i);
578 secp256k1_fe_add(&r->x, &h3);
579 secp256k1_fe_add(&r->x, &t);
580 secp256k1_fe_add(&r->x, &t);
581
582 secp256k1_fe_add(&t, &r->x);
583 secp256k1_fe_mul(&r->y, &t, &i);
584 secp256k1_fe_mul(&h3, &h3, &s1);
585 secp256k1_fe_add(&r->y, &h3);
586
588}
589
591 /* Operations: 8 mul, 3 sqr, 11 add/negate/normalizes_to_zero (ignoring special cases) */
592 secp256k1_fe z12, u1, u2, s1, s2, h, i, h2, h3, t;
595
596 if (a->infinity) {
597 VERIFY_CHECK(rzr == NULL);
599 return;
600 }
601 if (b->infinity) {
602 if (rzr != NULL) {
603 secp256k1_fe_set_int(rzr, 1);
604 }
605 *r = *a;
606 return;
607 }
608
609 secp256k1_fe_sqr(&z12, &a->z);
610 u1 = a->x;
611 secp256k1_fe_mul(&u2, &b->x, &z12);
612 s1 = a->y;
613 secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &a->z);
615 secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1);
618 secp256k1_gej_double_var(r, a, rzr);
619 } else {
620 if (rzr != NULL) {
621 secp256k1_fe_set_int(rzr, 0);
622 }
624 }
625 return;
626 }
627
628 r->infinity = 0;
629 if (rzr != NULL) {
630 *rzr = h;
631 }
632 secp256k1_fe_mul(&r->z, &a->z, &h);
633
634 secp256k1_fe_sqr(&h2, &h);
635 secp256k1_fe_negate(&h2, &h2, 1);
636 secp256k1_fe_mul(&h3, &h2, &h);
637 secp256k1_fe_mul(&t, &u1, &h2);
638
639 secp256k1_fe_sqr(&r->x, &i);
640 secp256k1_fe_add(&r->x, &h3);
641 secp256k1_fe_add(&r->x, &t);
642 secp256k1_fe_add(&r->x, &t);
643
644 secp256k1_fe_add(&t, &r->x);
645 secp256k1_fe_mul(&r->y, &t, &i);
646 secp256k1_fe_mul(&h3, &h3, &s1);
647 secp256k1_fe_add(&r->y, &h3);
648
650 if (rzr != NULL) SECP256K1_FE_VERIFY(rzr);
651}
652
653static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, const secp256k1_fe *bzinv) {
654 /* Operations: 9 mul, 3 sqr, 11 add/negate/normalizes_to_zero (ignoring special cases) */
655 secp256k1_fe az, z12, u1, u2, s1, s2, h, i, h2, h3, t;
658 SECP256K1_FE_VERIFY(bzinv);
659
660 if (a->infinity) {
661 secp256k1_fe bzinv2, bzinv3;
662 r->infinity = b->infinity;
663 secp256k1_fe_sqr(&bzinv2, bzinv);
664 secp256k1_fe_mul(&bzinv3, &bzinv2, bzinv);
665 secp256k1_fe_mul(&r->x, &b->x, &bzinv2);
666 secp256k1_fe_mul(&r->y, &b->y, &bzinv3);
667 secp256k1_fe_set_int(&r->z, 1);
669 return;
670 }
671 if (b->infinity) {
672 *r = *a;
673 return;
674 }
675
684 secp256k1_fe_mul(&az, &a->z, bzinv);
685
686 secp256k1_fe_sqr(&z12, &az);
687 u1 = a->x;
688 secp256k1_fe_mul(&u2, &b->x, &z12);
689 s1 = a->y;
690 secp256k1_fe_mul(&s2, &b->y, &z12); secp256k1_fe_mul(&s2, &s2, &az);
692 secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1);
695 secp256k1_gej_double_var(r, a, NULL);
696 } else {
698 }
699 return;
700 }
701
702 r->infinity = 0;
703 secp256k1_fe_mul(&r->z, &a->z, &h);
704
705 secp256k1_fe_sqr(&h2, &h);
706 secp256k1_fe_negate(&h2, &h2, 1);
707 secp256k1_fe_mul(&h3, &h2, &h);
708 secp256k1_fe_mul(&t, &u1, &h2);
709
710 secp256k1_fe_sqr(&r->x, &i);
711 secp256k1_fe_add(&r->x, &h3);
712 secp256k1_fe_add(&r->x, &t);
713 secp256k1_fe_add(&r->x, &t);
714
715 secp256k1_fe_add(&t, &r->x);
716 secp256k1_fe_mul(&r->y, &t, &i);
717 secp256k1_fe_mul(&h3, &h3, &s1);
718 secp256k1_fe_add(&r->y, &h3);
719
721}
722
723
725 /* Operations: 7 mul, 5 sqr, 21 add/cmov/half/mul_int/negate/normalizes_to_zero */
726 secp256k1_fe zz, u1, u2, s1, s2, t, tt, m, n, q, rr;
727 secp256k1_fe m_alt, rr_alt;
728 int degenerate;
732
733 /* In:
734 * Eric Brier and Marc Joye, Weierstrass Elliptic Curves and Side-Channel Attacks.
735 * In D. Naccache and P. Paillier, Eds., Public Key Cryptography, vol. 2274 of Lecture Notes in Computer Science, pages 335-345. Springer-Verlag, 2002.
736 * we find as solution for a unified addition/doubling formula:
737 * lambda = ((x1 + x2)^2 - x1 * x2 + a) / (y1 + y2), with a = 0 for secp256k1's curve equation.
738 * x3 = lambda^2 - (x1 + x2)
739 * 2*y3 = lambda * (x1 + x2 - 2 * x3) - (y1 + y2).
740 *
741 * Substituting x_i = Xi / Zi^2 and yi = Yi / Zi^3, for i=1,2,3, gives:
742 * U1 = X1*Z2^2, U2 = X2*Z1^2
743 * S1 = Y1*Z2^3, S2 = Y2*Z1^3
744 * Z = Z1*Z2
745 * T = U1+U2
746 * M = S1+S2
747 * Q = -T*M^2
748 * R = T^2-U1*U2
749 * X3 = R^2+Q
750 * Y3 = -(R*(2*X3+Q)+M^4)/2
751 * Z3 = M*Z
752 * (Note that the paper uses xi = Xi / Zi and yi = Yi / Zi instead.)
753 *
754 * This formula has the benefit of being the same for both addition
755 * of distinct points and doubling. However, it breaks down in the
756 * case that either point is infinity, or that y1 = -y2. We handle
757 * these cases in the following ways:
758 *
759 * - If b is infinity we simply bail by means of a VERIFY_CHECK.
760 *
761 * - If a is infinity, we detect this, and at the end of the
762 * computation replace the result (which will be meaningless,
763 * but we compute to be constant-time) with b.x : b.y : 1.
764 *
765 * - If a = -b, we have y1 = -y2, which is a degenerate case.
766 * But here the answer is infinity, so we simply set the
767 * infinity flag of the result, overriding the computed values
768 * without even needing to cmov.
769 *
770 * - If y1 = -y2 but x1 != x2, which does occur thanks to certain
771 * properties of our curve (specifically, 1 has nontrivial cube
772 * roots in our field, and the curve equation has no x coefficient)
773 * then the answer is not infinity but also not given by the above
774 * equation. In this case, we cmov in place an alternate expression
775 * for lambda. Specifically (y1 - y2)/(x1 - x2). Where both these
776 * expressions for lambda are defined, they are equal, and can be
777 * obtained from each other by multiplication by (y1 + y2)/(y1 + y2)
778 * then substitution of x^3 + 7 for y^2 (using the curve equation).
779 * For all pairs of nonzero points (a, b) at least one is defined,
780 * so this covers everything.
781 */
782
783 secp256k1_fe_sqr(&zz, &a->z); /* z = Z1^2 */
784 u1 = a->x; /* u1 = U1 = X1*Z2^2 (GEJ_X_M) */
785 secp256k1_fe_mul(&u2, &b->x, &zz); /* u2 = U2 = X2*Z1^2 (1) */
786 s1 = a->y; /* s1 = S1 = Y1*Z2^3 (GEJ_Y_M) */
787 secp256k1_fe_mul(&s2, &b->y, &zz); /* s2 = Y2*Z1^2 (1) */
788 secp256k1_fe_mul(&s2, &s2, &a->z); /* s2 = S2 = Y2*Z1^3 (1) */
789 t = u1; secp256k1_fe_add(&t, &u2); /* t = T = U1+U2 (GEJ_X_M+1) */
790 m = s1; secp256k1_fe_add(&m, &s2); /* m = M = S1+S2 (GEJ_Y_M+1) */
791 secp256k1_fe_sqr(&rr, &t); /* rr = T^2 (1) */
792 secp256k1_fe_negate(&m_alt, &u2, 1); /* Malt = -X2*Z1^2 (2) */
793 secp256k1_fe_mul(&tt, &u1, &m_alt); /* tt = -U1*U2 (1) */
794 secp256k1_fe_add(&rr, &tt); /* rr = R = T^2-U1*U2 (2) */
795 /* If lambda = R/M = R/0 we have a problem (except in the "trivial"
796 * case that Z = z1z2 = 0, and this is special-cased later on). */
797 degenerate = secp256k1_fe_normalizes_to_zero(&m);
798 /* This only occurs when y1 == -y2 and x1^3 == x2^3, but x1 != x2.
799 * This means either x1 == beta*x2 or beta*x1 == x2, where beta is
800 * a nontrivial cube root of one. In either case, an alternate
801 * non-indeterminate expression for lambda is (y1 - y2)/(x1 - x2),
802 * so we set R/M equal to this. */
803 rr_alt = s1;
804 secp256k1_fe_mul_int(&rr_alt, 2); /* rr_alt = Y1*Z2^3 - Y2*Z1^3 (GEJ_Y_M*2) */
805 secp256k1_fe_add(&m_alt, &u1); /* Malt = X1*Z2^2 - X2*Z1^2 (GEJ_X_M+2) */
806
807 secp256k1_fe_cmov(&rr_alt, &rr, !degenerate); /* rr_alt (GEJ_Y_M*2) */
808 secp256k1_fe_cmov(&m_alt, &m, !degenerate); /* m_alt (GEJ_X_M+2) */
809 /* Now Ralt / Malt = lambda and is guaranteed not to be Ralt / 0.
810 * From here on out Ralt and Malt represent the numerator
811 * and denominator of lambda; R and M represent the explicit
812 * expressions x1^2 + x2^2 + x1x2 and y1 + y2. */
813 secp256k1_fe_sqr(&n, &m_alt); /* n = Malt^2 (1) */
815 SECP256K1_GEJ_X_MAGNITUDE_MAX + 1); /* q = -T (GEJ_X_M+2) */
816 secp256k1_fe_mul(&q, &q, &n); /* q = Q = -T*Malt^2 (1) */
817 /* These two lines use the observation that either M == Malt or M == 0,
818 * so M^3 * Malt is either Malt^4 (which is computed by squaring), or
819 * zero (which is "computed" by cmov). So the cost is one squaring
820 * versus two multiplications. */
821 secp256k1_fe_sqr(&n, &n); /* n = Malt^4 (1) */
822 secp256k1_fe_cmov(&n, &m, degenerate); /* n = M^3 * Malt (GEJ_Y_M+1) */
823 secp256k1_fe_sqr(&t, &rr_alt); /* t = Ralt^2 (1) */
824 secp256k1_fe_mul(&r->z, &a->z, &m_alt); /* r->z = Z3 = Malt*Z (1) */
825 secp256k1_fe_add(&t, &q); /* t = Ralt^2 + Q (2) */
826 r->x = t; /* r->x = X3 = Ralt^2 + Q (2) */
827 secp256k1_fe_mul_int(&t, 2); /* t = 2*X3 (4) */
828 secp256k1_fe_add(&t, &q); /* t = 2*X3 + Q (5) */
829 secp256k1_fe_mul(&t, &t, &rr_alt); /* t = Ralt*(2*X3 + Q) (1) */
830 secp256k1_fe_add(&t, &n); /* t = Ralt*(2*X3 + Q) + M^3*Malt (GEJ_Y_M+2) */
831 secp256k1_fe_negate(&r->y, &t,
832 SECP256K1_GEJ_Y_MAGNITUDE_MAX + 2); /* r->y = -(Ralt*(2*X3 + Q) + M^3*Malt) (GEJ_Y_M+3) */
833 secp256k1_fe_half(&r->y); /* r->y = Y3 = -(Ralt*(2*X3 + Q) + M^3*Malt)/2 ((GEJ_Y_M+3)/2 + 1) */
834
835 /* In case a->infinity == 1, replace r with (b->x, b->y, 1). */
836 secp256k1_fe_cmov(&r->x, &b->x, a->infinity);
837 secp256k1_fe_cmov(&r->y, &b->y, a->infinity);
839
840 /* Set r->infinity if r->z is 0.
841 *
842 * If a->infinity is set, then r->infinity = (r->z == 0) = (1 == 0) = false,
843 * which is correct because the function assumes that b is not infinity.
844 *
845 * Now assume !a->infinity. This implies Z = Z1 != 0.
846 *
847 * Case y1 = -y2:
848 * In this case we could have a = -b, namely if x1 = x2.
849 * We have degenerate = true, r->z = (x1 - x2) * Z.
850 * Then r->infinity = ((x1 - x2)Z == 0) = (x1 == x2) = (a == -b).
851 *
852 * Case y1 != -y2:
853 * In this case, we can't have a = -b.
854 * We have degenerate = false, r->z = (y1 + y2) * Z.
855 * Then r->infinity = ((y1 + y2)Z == 0) = (y1 == -y2) = false. */
857
859}
860
862 /* Operations: 4 mul, 1 sqr */
863 secp256k1_fe zz;
867
868 secp256k1_fe_sqr(&zz, s);
869 secp256k1_fe_mul(&r->x, &r->x, &zz); /* r->x *= s^2 */
870 secp256k1_fe_mul(&r->y, &r->y, &zz);
871 secp256k1_fe_mul(&r->y, &r->y, s); /* r->y *= s^3 */
872 secp256k1_fe_mul(&r->z, &r->z, s); /* r->z *= s */
873
875}
876
878 secp256k1_fe x, y;
881
882 x = a->x;
884 y = a->y;
886 secp256k1_fe_to_storage(&r->x, &x);
887 secp256k1_fe_to_storage(&r->y, &y);
888}
889
891 secp256k1_fe_from_storage(&r->x, &a->x);
892 secp256k1_fe_from_storage(&r->y, &a->y);
893 r->infinity = 0;
894
896}
897
901
902 secp256k1_fe_cmov(&r->x, &a->x, flag);
903 secp256k1_fe_cmov(&r->y, &a->y, flag);
904 secp256k1_fe_cmov(&r->z, &a->z, flag);
905 r->infinity ^= (r->infinity ^ a->infinity) & flag;
906
908}
909
911 secp256k1_fe_storage_cmov(&r->x, &a->x, flag);
912 secp256k1_fe_storage_cmov(&r->y, &a->y, flag);
913}
914
917
918 *r = *a;
920
922}
923
925#ifdef EXHAUSTIVE_TEST_ORDER
927 int i;
929
930 /* A very simple EC multiplication ladder that avoids a dependency on ecmult. */
932 for (i = 0; i < 32; ++i) {
934 if ((((uint32_t)EXHAUSTIVE_TEST_ORDER) >> (31 - i)) & 1) {
935 secp256k1_gej_add_ge_var(&out, &out, ge, NULL);
936 }
937 }
939#else
941
942 (void)ge;
943 /* The real secp256k1 group has cofactor 1, so the subgroup is the entire curve. */
944 return 1;
945#endif
946}
947
949 secp256k1_fe c;
950 secp256k1_fe_sqr(&c, x);
951 secp256k1_fe_mul(&c, &c, x);
954}
955
957 /* We want to determine whether (xn/xd) is on the curve.
958 *
959 * (xn/xd)^3 + 7 is square <=> xd*xn^3 + 7*xd^4 is square (multiplying by xd^4, a square).
960 */
961 secp256k1_fe r, t;
963
964 secp256k1_fe_mul(&r, xd, xn); /* r = xd*xn */
965 secp256k1_fe_sqr(&t, xn); /* t = xn^2 */
966 secp256k1_fe_mul(&r, &r, &t); /* r = xd*xn^3 */
967 secp256k1_fe_sqr(&t, xd); /* t = xd^2 */
968 secp256k1_fe_sqr(&t, &t); /* t = xd^4 */
970 secp256k1_fe_mul_int(&t, SECP256K1_B); /* t = 7*xd^4 */
971 secp256k1_fe_add(&r, &t); /* r = xd*xn^3 + 7*xd^4 */
973}
974
975static void secp256k1_ge_to_bytes(unsigned char *buf, const secp256k1_ge *a) {
977
978 /* We require that the secp256k1_ge_storage type is exactly 64 bytes.
979 * This is formally not guaranteed by the C standard, but should hold on any
980 * sane compiler in the real world. */
981 STATIC_ASSERT(sizeof(secp256k1_ge_storage) == 64);
984 memcpy(buf, &s, 64);
985}
986
987static void secp256k1_ge_from_bytes(secp256k1_ge *r, const unsigned char *buf) {
989
990 STATIC_ASSERT(sizeof(secp256k1_ge_storage) == 64);
991 memcpy(&s, buf, 64);
993}
994
995static void secp256k1_ge_to_bytes_ext(unsigned char *data, const secp256k1_ge *ge) {
996 if (secp256k1_ge_is_infinity(ge)) {
997 memset(data, 0, 64);
998 } else {
1000 }
1001}
1002
1003static void secp256k1_ge_from_bytes_ext(secp256k1_ge *ge, const unsigned char *data) {
1004 static const unsigned char zeros[64] = { 0 };
1005 if (secp256k1_memcmp_var(data, zeros, sizeof(zeros)) == 0) {
1007 } else {
1009 }
1010}
1011
1012#endif /* SECP256K1_GROUP_IMPL_H */
int ret
#define secp256k1_fe_cmov
Definition: field.h:95
#define secp256k1_fe_negate(r, a, m)
Negate a field element.
Definition: field.h:211
#define secp256k1_fe_mul_int(r, a)
Multiply a field element with a small integer.
Definition: field.h:233
#define secp256k1_fe_normalizes_to_zero_var
Definition: field.h:82
#define secp256k1_fe_normalize_weak
Definition: field.h:79
static const secp256k1_fe secp256k1_const_beta
Definition: field.h:69
#define secp256k1_fe_is_odd
Definition: field.h:85
#define SECP256K1_FE_VERIFY_MAGNITUDE(a, m)
Definition: field.h:348
#define secp256k1_fe_mul
Definition: field.h:93
static const secp256k1_fe secp256k1_fe_one
Definition: field.h:68
static int secp256k1_fe_sqrt(secp256k1_fe *SECP256K1_RESTRICT r, const secp256k1_fe *SECP256K1_RESTRICT a)
Compute a square root of a field element.
#define secp256k1_fe_add
Definition: field.h:92
#define secp256k1_fe_normalize_var
Definition: field.h:80
#define secp256k1_fe_half
Definition: field.h:101
#define secp256k1_fe_to_storage
Definition: field.h:96
#define secp256k1_fe_inv_var
Definition: field.h:99
#define SECP256K1_FE_VERIFY(a)
Definition: field.h:344
#define secp256k1_fe_is_square_var
Definition: field.h:103
#define secp256k1_fe_from_storage
Definition: field.h:97
#define secp256k1_fe_normalizes_to_zero
Definition: field.h:81
#define secp256k1_fe_inv
Definition: field.h:98
#define secp256k1_fe_sqr
Definition: field.h:94
#define secp256k1_fe_normalize
Definition: field.h:78
static int secp256k1_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b)
Determine whether two field elements are equal.
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_add_int
Definition: field.h:102
#define secp256k1_fe_set_int
Definition: field.h:83
#define SECP256K1_GE_X_MAGNITUDE_MAX
Maximum allowed magnitudes for group element coordinates in affine (x, y) and jacobian (x,...
Definition: group.h:49
#define SECP256K1_GEJ_VERIFY(a)
Definition: group.h:214
#define SECP256K1_GEJ_Y_MAGNITUDE_MAX
Definition: group.h:52
#define SECP256K1_GE_Y_MAGNITUDE_MAX
Definition: group.h:50
#define SECP256K1_GEJ_Z_MAGNITUDE_MAX
Definition: group.h:53
#define SECP256K1_GE_VERIFY(a)
Definition: group.h:210
#define SECP256K1_GEJ_X_MAGNITUDE_MAX
Definition: group.h:51
static int secp256k1_gej_eq_var(const secp256k1_gej *a, const secp256k1_gej *b)
Definition: group_impl.h:378
static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr)
Definition: group_impl.h:495
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:653
#define SECP256K1_G_ORDER_13
Definition: group_impl.h:23
static void secp256k1_gej_clear(secp256k1_gej *r)
Definition: group_impl.h:339
static void secp256k1_ge_mul_lambda(secp256k1_ge *r, const secp256k1_ge *a)
Definition: group_impl.h:915
static void secp256k1_gej_set_infinity(secp256k1_gej *r)
Definition: group_impl.h:322
static int secp256k1_gej_is_infinity(const secp256k1_gej *a)
Definition: group_impl.h:440
static void secp256k1_ge_clear(secp256k1_ge *r)
Definition: group_impl.h:343
static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y)
Definition: group_impl.h:132
static void secp256k1_gej_verify(const secp256k1_gej *a)
Definition: group_impl.h:87
static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd)
Definition: group_impl.h:347
static void secp256k1_ge_verify(const secp256k1_ge *a)
Definition: group_impl.h:78
static int secp256k1_ge_eq_var(const secp256k1_ge *a, const secp256k1_ge *b)
Definition: group_impl.h:398
static int secp256k1_ge_x_on_curve_var(const secp256k1_fe *x)
Definition: group_impl.h:948
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:590
static void secp256k1_ge_to_bytes_ext(unsigned char *data, const secp256k1_ge *ge)
Definition: group_impl.h:995
static SECP256K1_INLINE void secp256k1_gej_cmov(secp256k1_gej *r, const secp256k1_gej *a, int flag)
Definition: group_impl.h:898
static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b)
Definition: group_impl.h:724
#define SECP256K1_G
Generator for secp256k1, value 'g' defined in "Standards for Efficient Cryptography" (SEC2) 2....
Definition: group_impl.h:38
static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi)
Definition: group_impl.h:99
#define SECP256K1_B
Definition: group_impl.h:73
static int secp256k1_gej_eq_ge_var(const secp256k1_gej *a, const secp256k1_ge *b)
Definition: group_impl.h:388
static int secp256k1_ge_is_valid_var(const secp256k1_ge *a)
Definition: group_impl.h:446
static void secp256k1_ge_from_bytes_ext(secp256k1_ge *ge, const unsigned char *data)
Definition: group_impl.h:1003
static void secp256k1_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storage *a)
Definition: group_impl.h:890
static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr)
Definition: group_impl.h:526
static int secp256k1_ge_x_frac_on_curve_var(const secp256k1_fe *xn, const secp256k1_fe *xd)
Definition: group_impl.h:956
static void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *s)
Definition: group_impl.h:861
static void secp256k1_ge_set_ge_zinv(secp256k1_ge *r, const secp256k1_ge *a, const secp256k1_fe *zi)
Definition: group_impl.h:116
static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a)
Definition: group_impl.h:417
#define SECP256K1_G_ORDER_7
Definition: group_impl.h:17
static void secp256k1_ge_set_gej(secp256k1_ge *r, secp256k1_gej *a)
Definition: group_impl.h:159
static int secp256k1_ge_is_in_correct_subgroup(const secp256k1_ge *ge)
Definition: group_impl.h:924
static void secp256k1_ge_table_set_globalz(size_t len, secp256k1_ge *a, const secp256k1_fe *zr)
Definition: group_impl.h:289
static void secp256k1_ge_neg(secp256k1_ge *r, const secp256k1_ge *a)
Definition: group_impl.h:149
static const secp256k1_ge secp256k1_ge_const_g
Definition: group_impl.h:72
static void secp256k1_ge_set_all_gej(secp256k1_ge *r, const secp256k1_gej *a, size_t len)
Definition: group_impl.h:198
static int secp256k1_ge_is_infinity(const secp256k1_ge *a)
Definition: group_impl.h:143
static void secp256k1_ge_set_infinity(secp256k1_ge *r)
Definition: group_impl.h:331
static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len)
Definition: group_impl.h:236
static void secp256k1_gej_set_ge(secp256k1_gej *r, const secp256k1_ge *a)
Definition: group_impl.h:367
static void secp256k1_ge_to_storage(secp256k1_ge_storage *r, const secp256k1_ge *a)
Definition: group_impl.h:877
static void secp256k1_ge_to_bytes(unsigned char *buf, const secp256k1_ge *a)
Definition: group_impl.h:975
static SECP256K1_INLINE void secp256k1_ge_storage_cmov(secp256k1_ge_storage *r, const secp256k1_ge_storage *a, int flag)
Definition: group_impl.h:910
#define SECP256K1_G_ORDER_199
Definition: group_impl.h:29
static void secp256k1_ge_set_gej_var(secp256k1_ge *r, secp256k1_gej *a)
Definition: group_impl.h:177
static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a)
Definition: group_impl.h:427
static void secp256k1_ge_from_bytes(secp256k1_ge *r, const unsigned char *buf)
Definition: group_impl.h:987
static SECP256K1_INLINE void secp256k1_gej_double(secp256k1_gej *r, const secp256k1_gej *a)
Definition: group_impl.h:460
static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n)
Semantics like memcmp.
Definition: util.h:255
#define SECP256K1_INLINE
Definition: util.h:54
#define STATIC_ASSERT(expr)
Assert statically that expr is true.
Definition: util.h:64
static SECP256K1_INLINE void secp256k1_memclear(void *ptr, size_t len)
Definition: util.h:223
#define VERIFY_CHECK(cond)
Definition: util.h:159
This field implementation represents the value as 10 uint32_t limbs in base 2^26.
Definition: field_10x26.h:14
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