Changeset View
Changeset View
Standalone View
Standalone View
src/secp256k1/src/field_impl.h
Show First 20 Lines • Show All 130 Lines • ▼ Show 20 Lines | static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a) { | ||||
secp256k1_fe_sqr(r, &t1); | secp256k1_fe_sqr(r, &t1); | ||||
/* Check that a square root was actually calculated */ | /* Check that a square root was actually calculated */ | ||||
secp256k1_fe_sqr(&t1, r); | secp256k1_fe_sqr(&t1, r); | ||||
return secp256k1_fe_equal(&t1, a); | return secp256k1_fe_equal(&t1, a); | ||||
} | } | ||||
static void secp256k1_fe_inv(secp256k1_fe *r, const secp256k1_fe *a) { | |||||
secp256k1_fe x2, x3, x6, x9, x11, x22, x44, x88, x176, x220, x223, t1; | |||||
int j; | |||||
/** The binary representation of (p - 2) has 5 blocks of 1s, with lengths in | |||||
* { 1, 2, 22, 223 }. Use an addition chain to calculate 2^n - 1 for each block: | |||||
* [1], [2], 3, 6, 9, 11, [22], 44, 88, 176, 220, [223] | |||||
*/ | |||||
secp256k1_fe_sqr(&x2, a); | |||||
secp256k1_fe_mul(&x2, &x2, a); | |||||
secp256k1_fe_sqr(&x3, &x2); | |||||
secp256k1_fe_mul(&x3, &x3, a); | |||||
x6 = x3; | |||||
for (j=0; j<3; j++) { | |||||
secp256k1_fe_sqr(&x6, &x6); | |||||
} | |||||
secp256k1_fe_mul(&x6, &x6, &x3); | |||||
x9 = x6; | |||||
for (j=0; j<3; j++) { | |||||
secp256k1_fe_sqr(&x9, &x9); | |||||
} | |||||
secp256k1_fe_mul(&x9, &x9, &x3); | |||||
x11 = x9; | |||||
for (j=0; j<2; j++) { | |||||
secp256k1_fe_sqr(&x11, &x11); | |||||
} | |||||
secp256k1_fe_mul(&x11, &x11, &x2); | |||||
x22 = x11; | |||||
for (j=0; j<11; j++) { | |||||
secp256k1_fe_sqr(&x22, &x22); | |||||
} | |||||
secp256k1_fe_mul(&x22, &x22, &x11); | |||||
x44 = x22; | |||||
for (j=0; j<22; j++) { | |||||
secp256k1_fe_sqr(&x44, &x44); | |||||
} | |||||
secp256k1_fe_mul(&x44, &x44, &x22); | |||||
x88 = x44; | |||||
for (j=0; j<44; j++) { | |||||
secp256k1_fe_sqr(&x88, &x88); | |||||
} | |||||
secp256k1_fe_mul(&x88, &x88, &x44); | |||||
x176 = x88; | |||||
for (j=0; j<88; j++) { | |||||
secp256k1_fe_sqr(&x176, &x176); | |||||
} | |||||
secp256k1_fe_mul(&x176, &x176, &x88); | |||||
x220 = x176; | |||||
for (j=0; j<44; j++) { | |||||
secp256k1_fe_sqr(&x220, &x220); | |||||
} | |||||
secp256k1_fe_mul(&x220, &x220, &x44); | |||||
x223 = x220; | |||||
for (j=0; j<3; j++) { | |||||
secp256k1_fe_sqr(&x223, &x223); | |||||
} | |||||
secp256k1_fe_mul(&x223, &x223, &x3); | |||||
/* The final result is then assembled using a sliding window over the blocks. */ | |||||
t1 = x223; | |||||
for (j=0; j<23; j++) { | |||||
secp256k1_fe_sqr(&t1, &t1); | |||||
} | |||||
secp256k1_fe_mul(&t1, &t1, &x22); | |||||
for (j=0; j<5; j++) { | |||||
secp256k1_fe_sqr(&t1, &t1); | |||||
} | |||||
secp256k1_fe_mul(&t1, &t1, a); | |||||
for (j=0; j<3; j++) { | |||||
secp256k1_fe_sqr(&t1, &t1); | |||||
} | |||||
secp256k1_fe_mul(&t1, &t1, &x2); | |||||
for (j=0; j<2; j++) { | |||||
secp256k1_fe_sqr(&t1, &t1); | |||||
} | |||||
secp256k1_fe_mul(r, a, &t1); | |||||
} | |||||
static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *a) { | |||||
#if defined(USE_FIELD_INV_BUILTIN) | |||||
secp256k1_fe_inv(r, a); | |||||
#elif defined(USE_FIELD_INV_NUM) | |||||
secp256k1_num n, m; | |||||
static const secp256k1_fe negone = SECP256K1_FE_CONST( | |||||
0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, | |||||
0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL, 0xFFFFFC2EUL | |||||
); | |||||
/* secp256k1 field prime, value p defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */ | |||||
static const unsigned char prime[32] = { | |||||
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF, | |||||
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF, | |||||
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF, | |||||
0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFC,0x2F | |||||
}; | |||||
unsigned char b[32]; | |||||
int res; | |||||
secp256k1_fe c = *a; | |||||
secp256k1_fe_normalize_var(&c); | |||||
secp256k1_fe_get_b32(b, &c); | |||||
secp256k1_num_set_bin(&n, b, 32); | |||||
secp256k1_num_set_bin(&m, prime, 32); | |||||
secp256k1_num_mod_inverse(&n, &n, &m); | |||||
secp256k1_num_get_bin(b, 32, &n); | |||||
res = secp256k1_fe_set_b32(r, b); | |||||
(void)res; | |||||
VERIFY_CHECK(res); | |||||
/* Verify the result is the (unique) valid inverse using non-GMP code. */ | |||||
secp256k1_fe_mul(&c, &c, r); | |||||
secp256k1_fe_add(&c, &negone); | |||||
CHECK(secp256k1_fe_normalizes_to_zero_var(&c)); | |||||
#else | |||||
#error "Please select field inverse implementation" | |||||
#endif | |||||
} | |||||
static int secp256k1_fe_is_quad_var(const secp256k1_fe *a) { | static int secp256k1_fe_is_quad_var(const secp256k1_fe *a) { | ||||
#ifndef USE_NUM_NONE | #ifndef USE_NUM_NONE | ||||
unsigned char b[32]; | unsigned char b[32]; | ||||
secp256k1_num n; | secp256k1_num n; | ||||
secp256k1_num m; | secp256k1_num m; | ||||
/* secp256k1 field prime, value p defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */ | /* secp256k1 field prime, value p defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */ | ||||
static const unsigned char prime[32] = { | static const unsigned char prime[32] = { | ||||
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF, | 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF, | ||||
Show All 20 Lines |