Changeset View
Changeset View
Standalone View
Standalone View
src/secp256k1/src/modinv32_impl.h
Show All 14 Lines | |||||
/* This file implements modular inversion based on the paper "Fast constant-time gcd computation and | /* This file implements modular inversion based on the paper "Fast constant-time gcd computation and | ||||
* modular inversion" by Daniel J. Bernstein and Bo-Yin Yang. | * modular inversion" by Daniel J. Bernstein and Bo-Yin Yang. | ||||
* | * | ||||
* For an explanation of the algorithm, see doc/safegcd_implementation.md. This file contains an | * For an explanation of the algorithm, see doc/safegcd_implementation.md. This file contains an | ||||
* implementation for N=30, using 30-bit signed limbs represented as int32_t. | * implementation for N=30, using 30-bit signed limbs represented as int32_t. | ||||
*/ | */ | ||||
#ifdef VERIFY | |||||
static const secp256k1_modinv32_signed30 SECP256K1_SIGNED30_ONE = {{1}}; | |||||
/* Compute a*factor and put it in r. All but the top limb in r will be in range [0,2^30). */ | |||||
static void secp256k1_modinv32_mul_30(secp256k1_modinv32_signed30 *r, const secp256k1_modinv32_signed30 *a, int32_t factor) { | |||||
const int32_t M30 = (int32_t)(UINT32_MAX >> 2); | |||||
int64_t c = 0; | |||||
int i; | |||||
for (i = 0; i < 8; ++i) { | |||||
c += (int64_t)a->v[i] * factor; | |||||
r->v[i] = (int32_t)c & M30; c >>= 30; | |||||
} | |||||
c += (int64_t)a->v[8] * factor; | |||||
VERIFY_CHECK(c == (int32_t)c); | |||||
r->v[8] = (int32_t)c; | |||||
} | |||||
/* Return -1 for a<b*factor, 0 for a==b*factor, 1 for a>b*factor. */ | |||||
static int secp256k1_modinv32_mul_cmp_30(const secp256k1_modinv32_signed30 *a, const secp256k1_modinv32_signed30 *b, int32_t factor) { | |||||
int i; | |||||
secp256k1_modinv32_signed30 am, bm; | |||||
secp256k1_modinv32_mul_30(&am, a, 1); /* Normalize all but the top limb of a. */ | |||||
secp256k1_modinv32_mul_30(&bm, b, factor); | |||||
for (i = 0; i < 8; ++i) { | |||||
/* Verify that all but the top limb of a and b are normalized. */ | |||||
VERIFY_CHECK(am.v[i] >> 30 == 0); | |||||
VERIFY_CHECK(bm.v[i] >> 30 == 0); | |||||
} | |||||
for (i = 8; i >= 0; --i) { | |||||
if (am.v[i] < bm.v[i]) return -1; | |||||
if (am.v[i] > bm.v[i]) return 1; | |||||
} | |||||
return 0; | |||||
} | |||||
#endif | |||||
/* Take as input a signed30 number in range (-2*modulus,modulus), and add a multiple of the modulus | /* Take as input a signed30 number in range (-2*modulus,modulus), and add a multiple of the modulus | ||||
* to it to bring it to range [0,modulus). If sign < 0, the input will also be negated in the | * to it to bring it to range [0,modulus). If sign < 0, the input will also be negated in the | ||||
* process. The input must have limbs in range (-2^30,2^30). The output will have limbs in range | * process. The input must have limbs in range (-2^30,2^30). The output will have limbs in range | ||||
* [0,2^30). */ | * [0,2^30). */ | ||||
static void secp256k1_modinv32_normalize_30(secp256k1_modinv32_signed30 *r, int32_t sign, const secp256k1_modinv32_modinfo *modinfo) { | static void secp256k1_modinv32_normalize_30(secp256k1_modinv32_signed30 *r, int32_t sign, const secp256k1_modinv32_modinfo *modinfo) { | ||||
const int32_t M30 = (int32_t)(UINT32_MAX >> 2); | const int32_t M30 = (int32_t)(UINT32_MAX >> 2); | ||||
int32_t r0 = r->v[0], r1 = r->v[1], r2 = r->v[2], r3 = r->v[3], r4 = r->v[4], | int32_t r0 = r->v[0], r1 = r->v[1], r2 = r->v[2], r3 = r->v[3], r4 = r->v[4], | ||||
r5 = r->v[5], r6 = r->v[6], r7 = r->v[7], r8 = r->v[8]; | r5 = r->v[5], r6 = r->v[6], r7 = r->v[7], r8 = r->v[8]; | ||||
int32_t cond_add, cond_negate; | int32_t cond_add, cond_negate; | ||||
#ifdef VERIFY | |||||
/* Verify that all limbs are in range (-2^30,2^30). */ | |||||
int i; | |||||
for (i = 0; i < 9; ++i) { | |||||
VERIFY_CHECK(r->v[i] >= -M30); | |||||
VERIFY_CHECK(r->v[i] <= M30); | |||||
} | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(r, &modinfo->modulus, -2) > 0); /* r > -2*modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(r, &modinfo->modulus, 1) < 0); /* r < modulus */ | |||||
#endif | |||||
/* In a first step, add the modulus if the input is negative, and then negate if requested. | /* In a first step, add the modulus if the input is negative, and then negate if requested. | ||||
* This brings r from range (-2*modulus,modulus) to range (-modulus,modulus). As all input | * This brings r from range (-2*modulus,modulus) to range (-modulus,modulus). As all input | ||||
* limbs are in range (-2^30,2^30), this cannot overflow an int32_t. Note that the right | * limbs are in range (-2^30,2^30), this cannot overflow an int32_t. Note that the right | ||||
* shifts below are signed sign-extending shifts (see assumptions.h for tests that that is | * shifts below are signed sign-extending shifts (see assumptions.h for tests that that is | ||||
* indeed the behavior of the right shift operator). */ | * indeed the behavior of the right shift operator). */ | ||||
cond_add = r8 >> 31; | cond_add = r8 >> 31; | ||||
r0 += modinfo->modulus.v[0] & cond_add; | r0 += modinfo->modulus.v[0] & cond_add; | ||||
r1 += modinfo->modulus.v[1] & cond_add; | r1 += modinfo->modulus.v[1] & cond_add; | ||||
▲ Show 20 Lines • Show All 50 Lines • ▼ Show 20 Lines | #endif | ||||
r->v[1] = r1; | r->v[1] = r1; | ||||
r->v[2] = r2; | r->v[2] = r2; | ||||
r->v[3] = r3; | r->v[3] = r3; | ||||
r->v[4] = r4; | r->v[4] = r4; | ||||
r->v[5] = r5; | r->v[5] = r5; | ||||
r->v[6] = r6; | r->v[6] = r6; | ||||
r->v[7] = r7; | r->v[7] = r7; | ||||
r->v[8] = r8; | r->v[8] = r8; | ||||
#ifdef VERIFY | |||||
VERIFY_CHECK(r0 >> 30 == 0); | |||||
VERIFY_CHECK(r1 >> 30 == 0); | |||||
VERIFY_CHECK(r2 >> 30 == 0); | |||||
VERIFY_CHECK(r3 >> 30 == 0); | |||||
VERIFY_CHECK(r4 >> 30 == 0); | |||||
VERIFY_CHECK(r5 >> 30 == 0); | |||||
VERIFY_CHECK(r6 >> 30 == 0); | |||||
VERIFY_CHECK(r7 >> 30 == 0); | |||||
VERIFY_CHECK(r8 >> 30 == 0); | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(r, &modinfo->modulus, 0) >= 0); /* r >= 0 */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(r, &modinfo->modulus, 1) < 0); /* r < modulus */ | |||||
#endif | |||||
} | } | ||||
/* Data type for transition matrices (see section 3 of explanation). | /* Data type for transition matrices (see section 3 of explanation). | ||||
* | * | ||||
* t = [ u v ] | * t = [ u v ] | ||||
* [ q r ] | * [ q r ] | ||||
*/ | */ | ||||
typedef struct { | typedef struct { | ||||
▲ Show 20 Lines • Show All 43 Lines • ▼ Show 20 Lines | for (i = 0; i < 30; ++i) { | ||||
/* Conditionally add g,q,r to f,u,v. */ | /* Conditionally add g,q,r to f,u,v. */ | ||||
f += g & c1; | f += g & c1; | ||||
u += q & c1; | u += q & c1; | ||||
v += r & c1; | v += r & c1; | ||||
/* Shifts */ | /* Shifts */ | ||||
g >>= 1; | g >>= 1; | ||||
u <<= 1; | u <<= 1; | ||||
v <<= 1; | v <<= 1; | ||||
/* Bounds on eta that follow from the bounds on iteration count (max 25*30 divsteps). */ | |||||
VERIFY_CHECK(eta >= -751 && eta <= 751); | |||||
} | } | ||||
/* Return data in t and return value. */ | /* Return data in t and return value. */ | ||||
t->u = (int32_t)u; | t->u = (int32_t)u; | ||||
t->v = (int32_t)v; | t->v = (int32_t)v; | ||||
t->q = (int32_t)q; | t->q = (int32_t)q; | ||||
t->r = (int32_t)r; | t->r = (int32_t)r; | ||||
/* The determinant of t must be a power of two. This guarantees that multiplication with t | |||||
* does not change the gcd of f and g, apart from adding a power-of-2 factor to it (which | |||||
* will be divided out again). As each divstep's individual matrix has determinant 2, the | |||||
* aggregate of 30 of them will have determinant 2^30. */ | |||||
VERIFY_CHECK((int64_t)t->u * t->r - (int64_t)t->v * t->q == ((int64_t)1) << 30); | |||||
return eta; | return eta; | ||||
} | } | ||||
/* Compute the transition matrix and eta for 30 divsteps (variable time). | /* Compute the transition matrix and eta for 30 divsteps (variable time). | ||||
* | * | ||||
* Input: eta: initial eta | * Input: eta: initial eta | ||||
* f0: bottom limb of initial f | * f0: bottom limb of initial f | ||||
* g0: bottom limb of initial g | * g0: bottom limb of initial g | ||||
Show All 34 Lines | for (;;) { | ||||
eta -= zeros; | eta -= zeros; | ||||
i -= zeros; | i -= zeros; | ||||
/* We're done once we've done 30 divsteps. */ | /* We're done once we've done 30 divsteps. */ | ||||
if (i == 0) break; | if (i == 0) break; | ||||
VERIFY_CHECK((f & 1) == 1); | VERIFY_CHECK((f & 1) == 1); | ||||
VERIFY_CHECK((g & 1) == 1); | VERIFY_CHECK((g & 1) == 1); | ||||
VERIFY_CHECK((u * f0 + v * g0) == f << (30 - i)); | VERIFY_CHECK((u * f0 + v * g0) == f << (30 - i)); | ||||
VERIFY_CHECK((q * f0 + r * g0) == g << (30 - i)); | VERIFY_CHECK((q * f0 + r * g0) == g << (30 - i)); | ||||
/* Bounds on eta that follow from the bounds on iteration count (max 25*30 divsteps). */ | |||||
VERIFY_CHECK(eta >= -751 && eta <= 751); | |||||
/* If eta is negative, negate it and replace f,g with g,-f. */ | /* If eta is negative, negate it and replace f,g with g,-f. */ | ||||
if (eta < 0) { | if (eta < 0) { | ||||
uint32_t tmp; | uint32_t tmp; | ||||
eta = -eta; | eta = -eta; | ||||
tmp = f; f = g; g = -tmp; | tmp = f; f = g; g = -tmp; | ||||
tmp = u; u = q; q = -tmp; | tmp = u; u = q; q = -tmp; | ||||
tmp = v; v = r; r = -tmp; | tmp = v; v = r; r = -tmp; | ||||
} | } | ||||
/* eta is now >= 0. In what follows we're going to cancel out the bottom bits of g. No more | /* eta is now >= 0. In what follows we're going to cancel out the bottom bits of g. No more | ||||
* than i can be cancelled out (as we'd be done before that point), and no more than eta+1 | * than i can be cancelled out (as we'd be done before that point), and no more than eta+1 | ||||
* can be done as its sign will flip once that happens. */ | * can be done as its sign will flip once that happens. */ | ||||
limit = ((int)eta + 1) > i ? i : ((int)eta + 1); | limit = ((int)eta + 1) > i ? i : ((int)eta + 1); | ||||
/* m is a mask for the bottom min(limit, 8) bits (our table only supports 8 bits). */ | /* m is a mask for the bottom min(limit, 8) bits (our table only supports 8 bits). */ | ||||
VERIFY_CHECK(limit > 0 && limit <= 30); | |||||
m = (UINT32_MAX >> (32 - limit)) & 255U; | m = (UINT32_MAX >> (32 - limit)) & 255U; | ||||
/* Find what multiple of f must be added to g to cancel its bottom min(limit, 8) bits. */ | /* Find what multiple of f must be added to g to cancel its bottom min(limit, 8) bits. */ | ||||
w = (g * inv256[(f >> 1) & 127]) & m; | w = (g * inv256[(f >> 1) & 127]) & m; | ||||
/* Do so. */ | /* Do so. */ | ||||
g += f * w; | g += f * w; | ||||
q += u * w; | q += u * w; | ||||
r += v * w; | r += v * w; | ||||
VERIFY_CHECK((g & m) == 0); | VERIFY_CHECK((g & m) == 0); | ||||
} | } | ||||
/* Return data in t and return value. */ | /* Return data in t and return value. */ | ||||
t->u = (int32_t)u; | t->u = (int32_t)u; | ||||
t->v = (int32_t)v; | t->v = (int32_t)v; | ||||
t->q = (int32_t)q; | t->q = (int32_t)q; | ||||
t->r = (int32_t)r; | t->r = (int32_t)r; | ||||
/* The determinant of t must be a power of two. This guarantees that multiplication with t | |||||
* does not change the gcd of f and g, apart from adding a power-of-2 factor to it (which | |||||
* will be divided out again). As each divstep's individual matrix has determinant 2, the | |||||
* aggregate of 30 of them will have determinant 2^30. */ | |||||
VERIFY_CHECK((int64_t)t->u * t->r - (int64_t)t->v * t->q == ((int64_t)1) << 30); | |||||
return eta; | return eta; | ||||
} | } | ||||
/* Compute (t/2^30) * [d, e] mod modulus, where t is a transition matrix for 30 divsteps. | /* Compute (t/2^30) * [d, e] mod modulus, where t is a transition matrix for 30 divsteps. | ||||
* | * | ||||
* On input and output, d and e are in range (-2*modulus,modulus). All output limbs will be in range | * On input and output, d and e are in range (-2*modulus,modulus). All output limbs will be in range | ||||
* (-2^30,2^30). | * (-2^30,2^30). | ||||
* | * | ||||
* This implements the update_de function from the explanation. | * This implements the update_de function from the explanation. | ||||
*/ | */ | ||||
static void secp256k1_modinv32_update_de_30(secp256k1_modinv32_signed30 *d, secp256k1_modinv32_signed30 *e, const secp256k1_modinv32_trans2x2 *t, const secp256k1_modinv32_modinfo* modinfo) { | static void secp256k1_modinv32_update_de_30(secp256k1_modinv32_signed30 *d, secp256k1_modinv32_signed30 *e, const secp256k1_modinv32_trans2x2 *t, const secp256k1_modinv32_modinfo* modinfo) { | ||||
const int32_t M30 = (int32_t)(UINT32_MAX >> 2); | const int32_t M30 = (int32_t)(UINT32_MAX >> 2); | ||||
const int32_t u = t->u, v = t->v, q = t->q, r = t->r; | const int32_t u = t->u, v = t->v, q = t->q, r = t->r; | ||||
int32_t di, ei, md, me, sd, se; | int32_t di, ei, md, me, sd, se; | ||||
int64_t cd, ce; | int64_t cd, ce; | ||||
int i; | int i; | ||||
#ifdef VERIFY | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(d, &modinfo->modulus, -2) > 0); /* d > -2*modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(d, &modinfo->modulus, 1) < 0); /* d < modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(e, &modinfo->modulus, -2) > 0); /* e > -2*modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(e, &modinfo->modulus, 1) < 0); /* e < modulus */ | |||||
VERIFY_CHECK((labs(u) + labs(v)) >= 0); /* |u|+|v| doesn't overflow */ | |||||
VERIFY_CHECK((labs(q) + labs(r)) >= 0); /* |q|+|r| doesn't overflow */ | |||||
VERIFY_CHECK((labs(u) + labs(v)) <= M30 + 1); /* |u|+|v| <= 2^30 */ | |||||
VERIFY_CHECK((labs(q) + labs(r)) <= M30 + 1); /* |q|+|r| <= 2^30 */ | |||||
#endif | |||||
/* [md,me] start as zero; plus [u,q] if d is negative; plus [v,r] if e is negative. */ | /* [md,me] start as zero; plus [u,q] if d is negative; plus [v,r] if e is negative. */ | ||||
sd = d->v[8] >> 31; | sd = d->v[8] >> 31; | ||||
se = e->v[8] >> 31; | se = e->v[8] >> 31; | ||||
md = (u & sd) + (v & se); | md = (u & sd) + (v & se); | ||||
me = (q & sd) + (r & se); | me = (q & sd) + (r & se); | ||||
/* Begin computing t*[d,e]. */ | /* Begin computing t*[d,e]. */ | ||||
di = d->v[0]; | di = d->v[0]; | ||||
ei = e->v[0]; | ei = e->v[0]; | ||||
Show All 18 Lines | for (i = 1; i < 9; ++i) { | ||||
cd += (int64_t)modinfo->modulus.v[i] * md; | cd += (int64_t)modinfo->modulus.v[i] * md; | ||||
ce += (int64_t)modinfo->modulus.v[i] * me; | ce += (int64_t)modinfo->modulus.v[i] * me; | ||||
d->v[i - 1] = (int32_t)cd & M30; cd >>= 30; | d->v[i - 1] = (int32_t)cd & M30; cd >>= 30; | ||||
e->v[i - 1] = (int32_t)ce & M30; ce >>= 30; | e->v[i - 1] = (int32_t)ce & M30; ce >>= 30; | ||||
} | } | ||||
/* What remains is limb 9 of t*[d,e]+modulus*[md,me]; store it as output limb 8. */ | /* What remains is limb 9 of t*[d,e]+modulus*[md,me]; store it as output limb 8. */ | ||||
d->v[8] = (int32_t)cd; | d->v[8] = (int32_t)cd; | ||||
e->v[8] = (int32_t)ce; | e->v[8] = (int32_t)ce; | ||||
#ifdef VERIFY | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(d, &modinfo->modulus, -2) > 0); /* d > -2*modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(d, &modinfo->modulus, 1) < 0); /* d < modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(e, &modinfo->modulus, -2) > 0); /* e > -2*modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(e, &modinfo->modulus, 1) < 0); /* e < modulus */ | |||||
#endif | |||||
} | } | ||||
/* Compute (t/2^30) * [f, g], where t is a transition matrix for 30 divsteps. | /* Compute (t/2^30) * [f, g], where t is a transition matrix for 30 divsteps. | ||||
* | * | ||||
* This implements the update_fg function from the explanation. | * This implements the update_fg function from the explanation. | ||||
*/ | */ | ||||
static void secp256k1_modinv32_update_fg_30(secp256k1_modinv32_signed30 *f, secp256k1_modinv32_signed30 *g, const secp256k1_modinv32_trans2x2 *t) { | static void secp256k1_modinv32_update_fg_30(secp256k1_modinv32_signed30 *f, secp256k1_modinv32_signed30 *g, const secp256k1_modinv32_trans2x2 *t) { | ||||
const int32_t M30 = (int32_t)(UINT32_MAX >> 2); | const int32_t M30 = (int32_t)(UINT32_MAX >> 2); | ||||
Show All 37 Lines | static void secp256k1_modinv32(secp256k1_modinv32_signed30 *x, const secp256k1_modinv32_modinfo *modinfo) { | ||||
/* Do 25 iterations of 30 divsteps each = 750 divsteps. 724 suffices for 256-bit inputs. */ | /* Do 25 iterations of 30 divsteps each = 750 divsteps. 724 suffices for 256-bit inputs. */ | ||||
for (i = 0; i < 25; ++i) { | for (i = 0; i < 25; ++i) { | ||||
/* Compute transition matrix and new eta after 30 divsteps. */ | /* Compute transition matrix and new eta after 30 divsteps. */ | ||||
secp256k1_modinv32_trans2x2 t; | secp256k1_modinv32_trans2x2 t; | ||||
eta = secp256k1_modinv32_divsteps_30(eta, f.v[0], g.v[0], &t); | eta = secp256k1_modinv32_divsteps_30(eta, f.v[0], g.v[0], &t); | ||||
/* Update d,e using that transition matrix. */ | /* Update d,e using that transition matrix. */ | ||||
secp256k1_modinv32_update_de_30(&d, &e, &t, modinfo); | secp256k1_modinv32_update_de_30(&d, &e, &t, modinfo); | ||||
/* Update f,g using that transition matrix. */ | /* Update f,g using that transition matrix. */ | ||||
#ifdef VERIFY | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, -1) > 0); /* f > -modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, 1) <= 0); /* f <= modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &modinfo->modulus, -1) > 0); /* g > -modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &modinfo->modulus, 1) < 0); /* g < modulus */ | |||||
#endif | |||||
secp256k1_modinv32_update_fg_30(&f, &g, &t); | secp256k1_modinv32_update_fg_30(&f, &g, &t); | ||||
#ifdef VERIFY | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, -1) > 0); /* f > -modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, 1) <= 0); /* f <= modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &modinfo->modulus, -1) > 0); /* g > -modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &modinfo->modulus, 1) < 0); /* g < modulus */ | |||||
#endif | |||||
} | } | ||||
/* At this point sufficient iterations have been performed that g must have reached 0 | /* At this point sufficient iterations have been performed that g must have reached 0 | ||||
* and (if g was not originally 0) f must now equal +/- GCD of the initial f, g | * and (if g was not originally 0) f must now equal +/- GCD of the initial f, g | ||||
* values i.e. +/- 1, and d now contains +/- the modular inverse. */ | * values i.e. +/- 1, and d now contains +/- the modular inverse. */ | ||||
VERIFY_CHECK((g.v[0] | g.v[1] | g.v[2] | g.v[3] | g.v[4] | g.v[5] | g.v[6] | g.v[7] | g.v[8]) == 0); | #ifdef VERIFY | ||||
/* g == 0 */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &SECP256K1_SIGNED30_ONE, 0) == 0); | |||||
/* |f| == 1, or (x == 0 and d == 0 and |f|=modulus) */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &SECP256K1_SIGNED30_ONE, -1) == 0 || | |||||
secp256k1_modinv32_mul_cmp_30(&f, &SECP256K1_SIGNED30_ONE, 1) == 0 || | |||||
(secp256k1_modinv32_mul_cmp_30(x, &SECP256K1_SIGNED30_ONE, 0) == 0 && | |||||
secp256k1_modinv32_mul_cmp_30(&d, &SECP256K1_SIGNED30_ONE, 0) == 0 && | |||||
(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, 1) == 0 || | |||||
secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, -1) == 0))); | |||||
#endif | |||||
/* Optionally negate d, normalize to [0,modulus), and return it. */ | /* Optionally negate d, normalize to [0,modulus), and return it. */ | ||||
secp256k1_modinv32_normalize_30(&d, f.v[8], modinfo); | secp256k1_modinv32_normalize_30(&d, f.v[8], modinfo); | ||||
*x = d; | *x = d; | ||||
} | } | ||||
/* Compute the inverse of x modulo modinfo->modulus, and replace x with it (variable time). */ | /* Compute the inverse of x modulo modinfo->modulus, and replace x with it (variable time). */ | ||||
static void secp256k1_modinv32_var(secp256k1_modinv32_signed30 *x, const secp256k1_modinv32_modinfo *modinfo) { | static void secp256k1_modinv32_var(secp256k1_modinv32_signed30 *x, const secp256k1_modinv32_modinfo *modinfo) { | ||||
/* Start with d=0, e=1, f=modulus, g=x, eta=-1. */ | /* Start with d=0, e=1, f=modulus, g=x, eta=-1. */ | ||||
secp256k1_modinv32_signed30 d = {{0, 0, 0, 0, 0, 0, 0, 0, 0}}; | secp256k1_modinv32_signed30 d = {{0, 0, 0, 0, 0, 0, 0, 0, 0}}; | ||||
secp256k1_modinv32_signed30 e = {{1, 0, 0, 0, 0, 0, 0, 0, 0}}; | secp256k1_modinv32_signed30 e = {{1, 0, 0, 0, 0, 0, 0, 0, 0}}; | ||||
secp256k1_modinv32_signed30 f = modinfo->modulus; | secp256k1_modinv32_signed30 f = modinfo->modulus; | ||||
secp256k1_modinv32_signed30 g = *x; | secp256k1_modinv32_signed30 g = *x; | ||||
#ifdef VERIFY | |||||
int i = 0; | |||||
#endif | |||||
int j; | int j; | ||||
int32_t eta = -1; | int32_t eta = -1; | ||||
int32_t cond; | int32_t cond; | ||||
/* Do iterations of 30 divsteps each until g=0. */ | /* Do iterations of 30 divsteps each until g=0. */ | ||||
while (1) { | while (1) { | ||||
/* Compute transition matrix and new eta after 30 divsteps. */ | /* Compute transition matrix and new eta after 30 divsteps. */ | ||||
secp256k1_modinv32_trans2x2 t; | secp256k1_modinv32_trans2x2 t; | ||||
eta = secp256k1_modinv32_divsteps_30_var(eta, f.v[0], g.v[0], &t); | eta = secp256k1_modinv32_divsteps_30_var(eta, f.v[0], g.v[0], &t); | ||||
/* Update d,e using that transition matrix. */ | /* Update d,e using that transition matrix. */ | ||||
secp256k1_modinv32_update_de_30(&d, &e, &t, modinfo); | secp256k1_modinv32_update_de_30(&d, &e, &t, modinfo); | ||||
/* Update f,g using that transition matrix. */ | /* Update f,g using that transition matrix. */ | ||||
#ifdef VERIFY | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, -1) > 0); /* f > -modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, 1) <= 0); /* f <= modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &modinfo->modulus, -1) > 0); /* g > -modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &modinfo->modulus, 1) < 0); /* g < modulus */ | |||||
#endif | |||||
secp256k1_modinv32_update_fg_30(&f, &g, &t); | secp256k1_modinv32_update_fg_30(&f, &g, &t); | ||||
/* If the bottom limb of g is 0, there is a chance g=0. */ | /* If the bottom limb of g is 0, there is a chance g=0. */ | ||||
if (g.v[0] == 0) { | if (g.v[0] == 0) { | ||||
cond = 0; | cond = 0; | ||||
/* Check if the other limbs are also 0. */ | /* Check if the other limbs are also 0. */ | ||||
for (j = 1; j < 9; ++j) { | for (j = 1; j < 9; ++j) { | ||||
cond |= g.v[j]; | cond |= g.v[j]; | ||||
} | } | ||||
/* If so, we're done. */ | /* If so, we're done. */ | ||||
if (cond == 0) break; | if (cond == 0) break; | ||||
} | } | ||||
#ifdef VERIFY | |||||
VERIFY_CHECK(++i < 25); /* We should never need more than 25*30 = 750 divsteps */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, -1) > 0); /* f > -modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, 1) <= 0); /* f <= modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &modinfo->modulus, -1) > 0); /* g > -modulus */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &modinfo->modulus, 1) < 0); /* g < modulus */ | |||||
#endif | |||||
} | } | ||||
/* At this point g is 0 and (if g was not originally 0) f must now equal +/- GCD of | /* At this point g is 0 and (if g was not originally 0) f must now equal +/- GCD of | ||||
* the initial f, g values i.e. +/- 1, and d now contains +/- the modular inverse. */ | * the initial f, g values i.e. +/- 1, and d now contains +/- the modular inverse. */ | ||||
#ifdef VERIFY | |||||
/* g == 0 */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &SECP256K1_SIGNED30_ONE, 0) == 0); | |||||
/* |f| == 1, or (x == 0 and d == 0 and |f|=modulus) */ | |||||
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &SECP256K1_SIGNED30_ONE, -1) == 0 || | |||||
secp256k1_modinv32_mul_cmp_30(&f, &SECP256K1_SIGNED30_ONE, 1) == 0 || | |||||
(secp256k1_modinv32_mul_cmp_30(x, &SECP256K1_SIGNED30_ONE, 0) == 0 && | |||||
secp256k1_modinv32_mul_cmp_30(&d, &SECP256K1_SIGNED30_ONE, 0) == 0 && | |||||
(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, 1) == 0 || | |||||
secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, -1) == 0))); | |||||
#endif | |||||
/* Optionally negate d, normalize to [0,modulus), and return it. */ | /* Optionally negate d, normalize to [0,modulus), and return it. */ | ||||
secp256k1_modinv32_normalize_30(&d, f.v[8], modinfo); | secp256k1_modinv32_normalize_30(&d, f.v[8], modinfo); | ||||
*x = d; | *x = d; | ||||
} | } | ||||
#endif /* SECP256K1_MODINV32_IMPL_H */ | #endif /* SECP256K1_MODINV32_IMPL_H */ |