Page MenuHomePhabricator
Differential D9411 Diff 28164 src/secp256k1/src/modinv32_impl.h

Changeset View

Standalone View

View Options

src/secp256k1/src/modinv32_impl.h

Show All 18 Lines
* 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 #ifdef VERIFY
static const secp256k1_modinv32_signed30 SECP256K1_SIGNED30_ONE = {{1}}; 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). */ /* 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) { static void secp256k1_modinv32_mul_30(secp256k1_modinv32_signed30 *r, const secp256k1_modinv32_signed30 *a, int alen, int32_t factor) {
const int32_t M30 = (int32_t)(UINT32_MAX >> 2); const int32_t M30 = (int32_t)(UINT32_MAX >> 2);
int64_t c = 0; int64_t c = 0;
int i; int i;
for (i = 0; i < 8; ++i) { for (i = 0; i < 8; ++i) {
c += (int64_t)a->v[i] * factor; if (i < alen) c += (int64_t)a->v[i] * factor;
r->v[i] = (int32_t)c & M30; c >>= 30; r->v[i] = (int32_t)c & M30; c >>= 30;
} }
c += (int64_t)a->v[8] * factor; if (8 < alen) c += (int64_t)a->v[8] * factor;
VERIFY_CHECK(c == (int32_t)c); VERIFY_CHECK(c == (int32_t)c);
r->v[8] = (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. */ /* Return -1 for a<b*factor, 0 for a==b*factor, 1 for a>b*factor. A consists of alen limbs; b has 9. */
static int secp256k1_modinv32_mul_cmp_30(const secp256k1_modinv32_signed30 *a, const secp256k1_modinv32_signed30 *b, int32_t factor) { static int secp256k1_modinv32_mul_cmp_30(const secp256k1_modinv32_signed30 *a, int alen, const secp256k1_modinv32_signed30 *b, int32_t factor) {
int i; int i;
secp256k1_modinv32_signed30 am, bm; secp256k1_modinv32_signed30 am, bm;
secp256k1_modinv32_mul_30(&am, a, 1); /* Normalize all but the top limb of a. */ secp256k1_modinv32_mul_30(&am, a, alen, 1); /* Normalize all but the top limb of a. */
secp256k1_modinv32_mul_30(&bm, b, factor); secp256k1_modinv32_mul_30(&bm, b, 9, factor);
for (i = 0; i < 8; ++i) { for (i = 0; i < 8; ++i) {
/* Verify that all but the top limb of a and b are normalized. */ /* Verify that all but the top limb of a and b are normalized. */
VERIFY_CHECK(am.v[i] >> 30 == 0); VERIFY_CHECK(am.v[i] >> 30 == 0);
VERIFY_CHECK(bm.v[i] >> 30 == 0); VERIFY_CHECK(bm.v[i] >> 30 == 0);
} }
for (i = 8; i >= 0; --i) { for (i = 8; i >= 0; --i) {
if (am.v[i] < bm.v[i]) return -1; if (am.v[i] < bm.v[i]) return -1;
if (am.v[i] > bm.v[i]) return 1; if (am.v[i] > bm.v[i]) return 1;
Show All 14 Lines
#ifdef VERIFY #ifdef VERIFY
/* Verify that all limbs are in range (-2^30,2^30). */ /* Verify that all limbs are in range (-2^30,2^30). */
int i; int i;
for (i = 0; i < 9; ++i) { for (i = 0; i < 9; ++i) {
VERIFY_CHECK(r->v[i] >= -M30); VERIFY_CHECK(r->v[i] >= -M30);
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, 9, &modinfo->modulus, -2) > 0); /* r > -2*modulus */
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(r, &modinfo->modulus, 1) < 0); /* r < modulus */ VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(r, 9, &modinfo->modulus, 1) < 0); /* r < modulus */
#endif #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;
▲ Show 20 Lines • Show All 63 Lines • ▼ Show 20 Lines#ifdef VERIFY
VERIFY_CHECK(r1 >> 30 == 0); VERIFY_CHECK(r1 >> 30 == 0);
VERIFY_CHECK(r2 >> 30 == 0); VERIFY_CHECK(r2 >> 30 == 0);
VERIFY_CHECK(r3 >> 30 == 0); VERIFY_CHECK(r3 >> 30 == 0);
VERIFY_CHECK(r4 >> 30 == 0); VERIFY_CHECK(r4 >> 30 == 0);
VERIFY_CHECK(r5 >> 30 == 0); VERIFY_CHECK(r5 >> 30 == 0);
VERIFY_CHECK(r6 >> 30 == 0); VERIFY_CHECK(r6 >> 30 == 0);
VERIFY_CHECK(r7 >> 30 == 0); VERIFY_CHECK(r7 >> 30 == 0);
VERIFY_CHECK(r8 >> 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, 9, &modinfo->modulus, 0) >= 0); /* r >= 0 */
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(r, &modinfo->modulus, 1) < 0); /* r < modulus */ VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(r, 9, &modinfo->modulus, 1) < 0); /* r < modulus */
#endif #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 ]
*/ */
▲ Show 20 Lines • Show All 159 Lines • ▼ Show 20 Lines
*/ */
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 #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, 9, &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(d, 9, &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, 9, &modinfo->modulus, -2) > 0); /* e > -2*modulus */
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(e, &modinfo->modulus, 1) < 0); /* e < modulus */ VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(e, 9, &modinfo->modulus, 1) < 0); /* e < modulus */
VERIFY_CHECK((labs(u) + labs(v)) >= 0); /* |u|+|v| doesn't overflow */ 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(q) + labs(r)) >= 0); /* |q|+|r| doesn't overflow */
VERIFY_CHECK((labs(u) + labs(v)) <= M30 + 1); /* |u|+|v| <= 2^30 */ VERIFY_CHECK((labs(u) + labs(v)) <= M30 + 1); /* |u|+|v| <= 2^30 */
VERIFY_CHECK((labs(q) + labs(r)) <= M30 + 1); /* |q|+|r| <= 2^30 */ VERIFY_CHECK((labs(q) + labs(r)) <= M30 + 1); /* |q|+|r| <= 2^30 */
#endif #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;
Show All 24 Lines for (i = 1; i < 9; ++i) {
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 #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, 9, &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(d, 9, &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, 9, &modinfo->modulus, -2) > 0); /* e > -2*modulus */
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(e, &modinfo->modulus, 1) < 0); /* e < modulus */ VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(e, 9, &modinfo->modulus, 1) < 0); /* e < modulus */
#endif #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) {
Show All 20 Lines for (i = 1; i < 9; ++i) {
f->v[i - 1] = (int32_t)cf & M30; cf >>= 30; f->v[i - 1] = (int32_t)cf & M30; cf >>= 30;
g->v[i - 1] = (int32_t)cg & M30; cg >>= 30; g->v[i - 1] = (int32_t)cg & M30; cg >>= 30;
} }
/* What remains is limb 9 of t*[f,g]; store it as output limb 8. */ /* What remains is limb 9 of t*[f,g]; store it as output limb 8. */
f->v[8] = (int32_t)cf; f->v[8] = (int32_t)cf;
g->v[8] = (int32_t)cg; g->v[8] = (int32_t)cg;
} }
/* Compute (t/2^30) * [f, g], where t is a transition matrix for 30 divsteps.
*
* Version that operates on a variable number of limbs in f and g.
*
* This implements the update_fg function from the explanation in modinv64_impl.h.
*/
static void secp256k1_modinv32_update_fg_30_var(int len, 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 u = t->u, v = t->v, q = t->q, r = t->r;
int32_t fi, gi;
int64_t cf, cg;
int i;
VERIFY_CHECK(len > 0);
/* Start computing t*[f,g]. */
fi = f->v[0];
gi = g->v[0];
cf = (int64_t)u * fi + (int64_t)v * gi;
cg = (int64_t)q * fi + (int64_t)r * gi;
/* Verify that the bottom 62 bits of the result are zero, and then throw them away. */
VERIFY_CHECK(((int32_t)cf & M30) == 0); cf >>= 30;
VERIFY_CHECK(((int32_t)cg & M30) == 0); cg >>= 30;
/* Now iteratively compute limb i=1..len of t*[f,g], and store them in output limb i-1 (shifting
* down by 30 bits). */
for (i = 1; i < len; ++i) {
fi = f->v[i];
gi = g->v[i];
cf += (int64_t)u * fi + (int64_t)v * gi;
cg += (int64_t)q * fi + (int64_t)r * gi;
f->v[i - 1] = (int32_t)cf & M30; cf >>= 30;
g->v[i - 1] = (int32_t)cg & M30; cg >>= 30;
}
/* What remains is limb (len) of t*[f,g]; store it as output limb (len-1). */
f->v[len - 1] = (int32_t)cf;
g->v[len - 1] = (int32_t)cg;
}
/* Compute the inverse of x modulo modinfo->modulus, and replace x with it (constant time in x). */ /* Compute the inverse of x modulo modinfo->modulus, and replace x with it (constant time in x). */
static void secp256k1_modinv32(secp256k1_modinv32_signed30 *x, const secp256k1_modinv32_modinfo *modinfo) { static void secp256k1_modinv32(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}}; secp256k1_modinv32_signed30 d = {{0}};
secp256k1_modinv32_signed30 e = {{1}}; secp256k1_modinv32_signed30 e = {{1}};
secp256k1_modinv32_signed30 f = modinfo->modulus; secp256k1_modinv32_signed30 f = modinfo->modulus;
secp256k1_modinv32_signed30 g = *x; secp256k1_modinv32_signed30 g = *x;
int i; int i;
int32_t eta = -1; int32_t eta = -1;
/* 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 #ifdef VERIFY
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, -1) > 0); /* f > -modulus */ VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, 9, &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(&f, 9, &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, 9, &modinfo->modulus, -1) > 0); /* g > -modulus */
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &modinfo->modulus, 1) < 0); /* g < modulus */ VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, 9, &modinfo->modulus, 1) < 0); /* g < modulus */
#endif #endif
secp256k1_modinv32_update_fg_30(&f, &g, &t); secp256k1_modinv32_update_fg_30(&f, &g, &t);
#ifdef VERIFY #ifdef VERIFY
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, -1) > 0); /* f > -modulus */ VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, 9, &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(&f, 9, &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, 9, &modinfo->modulus, -1) > 0); /* g > -modulus */
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &modinfo->modulus, 1) < 0); /* g < modulus */ VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, 9, &modinfo->modulus, 1) < 0); /* g < modulus */
#endif #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. */
#ifdef VERIFY #ifdef VERIFY
/* g == 0 */ /* g == 0 */
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &SECP256K1_SIGNED30_ONE, 0) == 0); VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, 9, &SECP256K1_SIGNED30_ONE, 0) == 0);
/* |f| == 1, or (x == 0 and d == 0 and |f|=modulus) */ /* |f| == 1, or (x == 0 and d == 0 and |f|=modulus) */
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &SECP256K1_SIGNED30_ONE, -1) == 0 || VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, 9, &SECP256K1_SIGNED30_ONE, -1) == 0 ||
secp256k1_modinv32_mul_cmp_30(&f, &SECP256K1_SIGNED30_ONE, 1) == 0 || secp256k1_modinv32_mul_cmp_30(&f, 9, &SECP256K1_SIGNED30_ONE, 1) == 0 ||
(secp256k1_modinv32_mul_cmp_30(x, &SECP256K1_SIGNED30_ONE, 0) == 0 && (secp256k1_modinv32_mul_cmp_30(x, 9, &SECP256K1_SIGNED30_ONE, 0) == 0 &&
secp256k1_modinv32_mul_cmp_30(&d, &SECP256K1_SIGNED30_ONE, 0) == 0 && secp256k1_modinv32_mul_cmp_30(&d, 9, &SECP256K1_SIGNED30_ONE, 0) == 0 &&
(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, 1) == 0 || (secp256k1_modinv32_mul_cmp_30(&f, 9, &modinfo->modulus, 1) == 0 ||
secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, -1) == 0))); secp256k1_modinv32_mul_cmp_30(&f, 9, &modinfo->modulus, -1) == 0)));
#endif #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 #ifdef VERIFY
int i = 0; int i = 0;
#endif #endif
int j; int j, len = 9;
int32_t eta = -1; int32_t eta = -1;
int32_t cond; int32_t cond, fn, gn;
/* 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 #ifdef VERIFY
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, -1) > 0); /* f > -modulus */ VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, len, &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(&f, len, &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, len, &modinfo->modulus, -1) > 0); /* g > -modulus */
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &modinfo->modulus, 1) < 0); /* g < modulus */ VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, len, &modinfo->modulus, 1) < 0); /* g < modulus */
#endif #endif
secp256k1_modinv32_update_fg_30(&f, &g, &t); secp256k1_modinv32_update_fg_30_var(len, &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 all other limbs are also 0. */
for (j = 1; j < 9; ++j) { for (j = 1; j < len; ++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;
} }
/* Determine if len>1 and limb (len-1) of both f and g is 0 or -1. */
fn = f.v[len - 1];
gn = g.v[len - 1];
cond = ((int32_t)len - 2) >> 31;
cond |= fn ^ (fn >> 31);
cond |= gn ^ (gn >> 31);
/* If so, reduce length, propagating the sign of f and g's top limb into the one below. */
if (cond == 0) {
f.v[len - 2] |= (uint32_t)fn << 30;
g.v[len - 2] |= (uint32_t)gn << 30;
--len;
}
#ifdef VERIFY #ifdef VERIFY
VERIFY_CHECK(++i < 25); /* We should never need more than 25*30 = 750 divsteps */ 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, len, &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(&f, len, &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, len, &modinfo->modulus, -1) > 0); /* g > -modulus */
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &modinfo->modulus, 1) < 0); /* g < modulus */ VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, len, &modinfo->modulus, 1) < 0); /* g < modulus */
#endif #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 #ifdef VERIFY
/* g == 0 */ /* g == 0 */
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, &SECP256K1_SIGNED30_ONE, 0) == 0); VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&g, len, &SECP256K1_SIGNED30_ONE, 0) == 0);
/* |f| == 1, or (x == 0 and d == 0 and |f|=modulus) */ /* |f| == 1, or (x == 0 and d == 0 and |f|=modulus) */
VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, &SECP256K1_SIGNED30_ONE, -1) == 0 || VERIFY_CHECK(secp256k1_modinv32_mul_cmp_30(&f, len, &SECP256K1_SIGNED30_ONE, -1) == 0 ||
secp256k1_modinv32_mul_cmp_30(&f, &SECP256K1_SIGNED30_ONE, 1) == 0 || secp256k1_modinv32_mul_cmp_30(&f, len, &SECP256K1_SIGNED30_ONE, 1) == 0 ||
(secp256k1_modinv32_mul_cmp_30(x, &SECP256K1_SIGNED30_ONE, 0) == 0 && (secp256k1_modinv32_mul_cmp_30(x, 9, &SECP256K1_SIGNED30_ONE, 0) == 0 &&
secp256k1_modinv32_mul_cmp_30(&d, &SECP256K1_SIGNED30_ONE, 0) == 0 && secp256k1_modinv32_mul_cmp_30(&d, 9, &SECP256K1_SIGNED30_ONE, 0) == 0 &&
(secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, 1) == 0 || (secp256k1_modinv32_mul_cmp_30(&f, len, &modinfo->modulus, 1) == 0 ||
secp256k1_modinv32_mul_cmp_30(&f, &modinfo->modulus, -1) == 0))); secp256k1_modinv32_mul_cmp_30(&f, len, &modinfo->modulus, -1) == 0)));
#endif #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[len - 1], modinfo);
*x = d; *x = d;
} }
#endif /* SECP256K1_MODINV32_IMPL_H */ #endif /* SECP256K1_MODINV32_IMPL_H */