Page MenuHomePhabricator
Differential D7658 Diff 24016 src/secp256k1/src/group_impl.h

Changeset View

Standalone View

View Options

src/secp256k1/src/group_impl.h

/********************************************************************** /**********************************************************************
* Copyright (c) 2013, 2014 Pieter Wuille * * Copyright (c) 2013, 2014 Pieter Wuille *
* Distributed under the MIT software license, see the accompanying * * Distributed under the MIT software license, see the accompanying *
* file COPYING or http://www.opensource.org/licenses/mit-license.php.* * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
**********************************************************************/ **********************************************************************/
#ifndef SECP256K1_GROUP_IMPL_H #ifndef SECP256K1_GROUP_IMPL_H
#define SECP256K1_GROUP_IMPL_H #define SECP256K1_GROUP_IMPL_H
#include "num.h" #include "num.h"
#include "field.h" #include "field.h"
#include "group.h" #include "group.h"
/* These points can be generated in sage as follows: /* These points can be generated in sage as follows:
* *
* 0. Setup a worksheet with the following parameters. * 0. Setup a worksheet with the following parameters.
* b = 4 # whatever CURVE_B will be set to * b = 4 # whatever secp256k1_fe_const_b will be set to
* F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F) * F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
* C = EllipticCurve ([F (0), F (b)]) * C = EllipticCurve ([F (0), F (b)])
* *
* 1. Determine all the small orders available to you. (If there are * 1. Determine all the small orders available to you. (If there are
* no satisfactory ones, go back and change b.) * no satisfactory ones, go back and change b.)
* print C.order().factor(limit=1000) * print C.order().factor(limit=1000)
* *
* 2. Choose an order as one of the prime factors listed in the above step. * 2. Choose an order as one of the prime factors listed in the above step.
Show All 14 Lines
# if EXHAUSTIVE_TEST_ORDER == 199 # if EXHAUSTIVE_TEST_ORDER == 199
static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_GE_CONST( static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_GE_CONST(
0xFA7CC9A7, 0x0737F2DB, 0xA749DD39, 0x2B4FB069, 0xFA7CC9A7, 0x0737F2DB, 0xA749DD39, 0x2B4FB069,
0x3B017A7D, 0xA808C2F1, 0xFB12940C, 0x9EA66C18, 0x3B017A7D, 0xA808C2F1, 0xFB12940C, 0x9EA66C18,
0x78AC123A, 0x5ED8AEF3, 0x8732BC91, 0x1F3A2868, 0x78AC123A, 0x5ED8AEF3, 0x8732BC91, 0x1F3A2868,
0x48DF246C, 0x808DAE72, 0xCFE52572, 0x7F0501ED 0x48DF246C, 0x808DAE72, 0xCFE52572, 0x7F0501ED
); );
static const int CURVE_B = 4; static const secp256k1_fe secp256k1_fe_const_b = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 4);
# elif EXHAUSTIVE_TEST_ORDER == 13 # elif EXHAUSTIVE_TEST_ORDER == 13
static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_GE_CONST( static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_GE_CONST(
0xedc60018, 0xa51a786b, 0x2ea91f4d, 0x4c9416c0, 0xedc60018, 0xa51a786b, 0x2ea91f4d, 0x4c9416c0,
0x9de54c3b, 0xa1316554, 0x6cf4345c, 0x7277ef15, 0x9de54c3b, 0xa1316554, 0x6cf4345c, 0x7277ef15,
0x54cb1b6b, 0xdc8c1273, 0x087844ea, 0x43f4603e, 0x54cb1b6b, 0xdc8c1273, 0x087844ea, 0x43f4603e,
0x0eaf9a43, 0xf6effe55, 0x939f806d, 0x37adf8ac 0x0eaf9a43, 0xf6effe55, 0x939f806d, 0x37adf8ac
); );
static const int CURVE_B = 2;
static const secp256k1_fe secp256k1_fe_const_b = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 2);
# else # else
# error No known generator for the specified exhaustive test group order. # error No known generator for the specified exhaustive test group order.
# endif # endif
#else #else
/** Generator for secp256k1, value 'g' defined in /** Generator for secp256k1, value 'g' defined in
* "Standards for Efficient Cryptography" (SEC2) 2.7.1. * "Standards for Efficient Cryptography" (SEC2) 2.7.1.
*/ */
static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_GE_CONST( static const secp256k1_ge secp256k1_ge_const_g = SECP256K1_GE_CONST(
0x79BE667EUL, 0xF9DCBBACUL, 0x55A06295UL, 0xCE870B07UL, 0x79BE667EUL, 0xF9DCBBACUL, 0x55A06295UL, 0xCE870B07UL,
0x029BFCDBUL, 0x2DCE28D9UL, 0x59F2815BUL, 0x16F81798UL, 0x029BFCDBUL, 0x2DCE28D9UL, 0x59F2815BUL, 0x16F81798UL,
0x483ADA77UL, 0x26A3C465UL, 0x5DA4FBFCUL, 0x0E1108A8UL, 0x483ADA77UL, 0x26A3C465UL, 0x5DA4FBFCUL, 0x0E1108A8UL,
0xFD17B448UL, 0xA6855419UL, 0x9C47D08FUL, 0xFB10D4B8UL 0xFD17B448UL, 0xA6855419UL, 0x9C47D08FUL, 0xFB10D4B8UL
); );
static const int CURVE_B = 7; static const secp256k1_fe secp256k1_fe_const_b = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 7);
#endif #endif
static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi) { static void secp256k1_ge_set_gej_zinv(secp256k1_ge *r, const secp256k1_gej *a, const secp256k1_fe *zi) {
secp256k1_fe zi2; secp256k1_fe zi2;
secp256k1_fe zi3; secp256k1_fe zi3;
secp256k1_fe_sqr(&zi2, zi); secp256k1_fe_sqr(&zi2, zi);
secp256k1_fe_mul(&zi3, &zi2, zi); secp256k1_fe_mul(&zi3, &zi2, zi);
secp256k1_fe_mul(&r->x, &a->x, &zi2); secp256k1_fe_mul(&r->x, &a->x, &zi2);
▲ Show 20 Lines • Show All 134 Lines • ▼ Show 20 Lines
static void secp256k1_ge_clear(secp256k1_ge *r) { static void secp256k1_ge_clear(secp256k1_ge *r) {
r->infinity = 0; r->infinity = 0;
secp256k1_fe_clear(&r->x); secp256k1_fe_clear(&r->x);
secp256k1_fe_clear(&r->y); secp256k1_fe_clear(&r->y);
} }
static int secp256k1_ge_set_xquad(secp256k1_ge *r, const secp256k1_fe *x) { static int secp256k1_ge_set_xquad(secp256k1_ge *r, const secp256k1_fe *x) {
secp256k1_fe x2, x3, c; secp256k1_fe x2, x3;
r->x = *x; r->x = *x;
secp256k1_fe_sqr(&x2, x); secp256k1_fe_sqr(&x2, x);
secp256k1_fe_mul(&x3, x, &x2); secp256k1_fe_mul(&x3, x, &x2);
r->infinity = 0; r->infinity = 0;
secp256k1_fe_set_int(&c, CURVE_B); secp256k1_fe_add(&x3, &secp256k1_fe_const_b);
secp256k1_fe_add(&c, &x3); return secp256k1_fe_sqrt(&r->y, &x3);
return secp256k1_fe_sqrt(&r->y, &c);
} }
static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd) { static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd) {
if (!secp256k1_ge_set_xquad(r, x)) { if (!secp256k1_ge_set_xquad(r, x)) {
return 0; return 0;
} }
secp256k1_fe_normalize_var(&r->y); secp256k1_fe_normalize_var(&r->y);
if (secp256k1_fe_is_odd(&r->y) != odd) { if (secp256k1_fe_is_odd(&r->y) != odd) {
Show All 27 Linesstatic void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a) {
secp256k1_fe_negate(&r->y, &r->y, 1); secp256k1_fe_negate(&r->y, &r->y, 1);
} }
static int secp256k1_gej_is_infinity(const secp256k1_gej *a) { static int secp256k1_gej_is_infinity(const secp256k1_gej *a) {
return a->infinity; return a->infinity;
} }
static int secp256k1_ge_is_valid_var(const secp256k1_ge *a) { static int secp256k1_ge_is_valid_var(const secp256k1_ge *a) {
secp256k1_fe y2, x3, c; secp256k1_fe y2, x3;
if (a->infinity) { if (a->infinity) {
return 0; return 0;
} }
/* y^2 = x^3 + 7 */ /* y^2 = x^3 + 7 */
secp256k1_fe_sqr(&y2, &a->y); secp256k1_fe_sqr(&y2, &a->y);
secp256k1_fe_sqr(&x3, &a->x); secp256k1_fe_mul(&x3, &x3, &a->x); secp256k1_fe_sqr(&x3, &a->x); secp256k1_fe_mul(&x3, &x3, &a->x);
secp256k1_fe_set_int(&c, CURVE_B); secp256k1_fe_add(&x3, &secp256k1_fe_const_b);
secp256k1_fe_add(&x3, &c);
secp256k1_fe_normalize_weak(&x3); secp256k1_fe_normalize_weak(&x3);
return secp256k1_fe_equal_var(&y2, &x3); return secp256k1_fe_equal_var(&y2, &x3);
} }
static SECP256K1_INLINE void secp256k1_gej_double(secp256k1_gej *r, const secp256k1_gej *a) { static SECP256K1_INLINE void secp256k1_gej_double(secp256k1_gej *r, const secp256k1_gej *a) {
/* Operations: 3 mul, 4 sqr, 0 normalize, 12 mul_int/add/negate. /* Operations: 3 mul, 4 sqr, 0 normalize, 12 mul_int/add/negate.
* *
* Note that there is an implementation described at * Note that there is an implementation described at
▲ Show 20 Lines • Show All 398 Lines • Show Last 20 Lines