Page MenuHomePhabricator
Differential D19816 Diff 58993 src/secp256k1/src/tests.c

Changeset View

Standalone View

View Options

src/secp256k1/src/tests.c

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 1,016 Lines • ▼ Show 20 Linesstatic void test_modinv32_uint16(uint16_t* out, const uint16_t* in, const uint16_t* mod) {
uint16_t tmp[16]; uint16_t tmp[16];
secp256k1_modinv32_signed30 x; secp256k1_modinv32_signed30 x;
secp256k1_modinv32_modinfo m; secp256k1_modinv32_modinfo m;
int i, vartime, nonzero; int i, vartime, nonzero;
uint16_to_signed30(&x, in); uint16_to_signed30(&x, in);
nonzero = (x.v[0] | x.v[1] | x.v[2] | x.v[3] | x.v[4] | x.v[5] | x.v[6] | x.v[7] | x.v[8]) != 0; nonzero = (x.v[0] | x.v[1] | x.v[2] | x.v[3] | x.v[4] | x.v[5] | x.v[6] | x.v[7] | x.v[8]) != 0;
uint16_to_signed30(&m.modulus, mod); uint16_to_signed30(&m.modulus, mod);
mutate_sign_signed30(&m.modulus);
/* compute 1/modulus mod 2^30 */ /* compute 1/modulus mod 2^30 */
m.modulus_inv30 = modinv2p64(m.modulus.v[0]) & 0x3fffffff; m.modulus_inv30 = modinv2p64(m.modulus.v[0]) & 0x3fffffff;
CHECK(((m.modulus_inv30 * m.modulus.v[0]) & 0x3fffffff) == 1); CHECK(((m.modulus_inv30 * m.modulus.v[0]) & 0x3fffffff) == 1);
/* Test secp256k1_jacobi32_maybe_var. */
if (nonzero) {
int jac;
uint16_t sqr[16], negone[16];
mulmod256(sqr, in, in, mod);
uint16_to_signed30(&x, sqr);
/* Compute jacobi symbol of in^2, which must be 1 (or uncomputable). */
jac = secp256k1_jacobi32_maybe_var(&x, &m);
CHECK(jac == 0 || jac == 1);
/* Then compute the jacobi symbol of -(in^2). x and -x have opposite
* jacobi symbols if and only if (mod % 4) == 3. */
negone[0] = mod[0] - 1;
for (i = 1; i < 16; ++i) negone[i] = mod[i];
mulmod256(sqr, sqr, negone, mod);
uint16_to_signed30(&x, sqr);
jac = secp256k1_jacobi32_maybe_var(&x, &m);
CHECK(jac == 0 || jac == 1 - (mod[0] & 2));
}
uint16_to_signed30(&x, in);
mutate_sign_signed30(&m.modulus);
for (vartime = 0; vartime < 2; ++vartime) { for (vartime = 0; vartime < 2; ++vartime) {
/* compute inverse */ /* compute inverse */
(vartime ? secp256k1_modinv32_var : secp256k1_modinv32)(&x, &m); (vartime ? secp256k1_modinv32_var : secp256k1_modinv32)(&x, &m);
/* produce output */ /* produce output */
signed30_to_uint16(out, &x); signed30_to_uint16(out, &x);
/* check if the inverse times the input is 1 (mod m), unless x is 0. */ /* check if the inverse times the input is 1 (mod m), unless x is 0. */
▲ Show 20 Lines • Show All 51 Lines • ▼ Show 20 Linesstatic void test_modinv64_uint16(uint16_t* out, const uint16_t* in, const uint16_t* mod) {
uint16_t tmp[16]; uint16_t tmp[16];
secp256k1_modinv64_signed62 x; secp256k1_modinv64_signed62 x;
secp256k1_modinv64_modinfo m; secp256k1_modinv64_modinfo m;
int i, vartime, nonzero; int i, vartime, nonzero;
uint16_to_signed62(&x, in); uint16_to_signed62(&x, in);
nonzero = (x.v[0] | x.v[1] | x.v[2] | x.v[3] | x.v[4]) != 0; nonzero = (x.v[0] | x.v[1] | x.v[2] | x.v[3] | x.v[4]) != 0;
uint16_to_signed62(&m.modulus, mod); uint16_to_signed62(&m.modulus, mod);
mutate_sign_signed62(&m.modulus);
/* compute 1/modulus mod 2^62 */ /* compute 1/modulus mod 2^62 */
m.modulus_inv62 = modinv2p64(m.modulus.v[0]) & M62; m.modulus_inv62 = modinv2p64(m.modulus.v[0]) & M62;
CHECK(((m.modulus_inv62 * m.modulus.v[0]) & M62) == 1); CHECK(((m.modulus_inv62 * m.modulus.v[0]) & M62) == 1);
/* Test secp256k1_jacobi64_maybe_var. */
if (nonzero) {
int jac;
uint16_t sqr[16], negone[16];
mulmod256(sqr, in, in, mod);
uint16_to_signed62(&x, sqr);
/* Compute jacobi symbol of in^2, which must be 1 (or uncomputable). */
jac = secp256k1_jacobi64_maybe_var(&x, &m);
CHECK(jac == 0 || jac == 1);
/* Then compute the jacobi symbol of -(in^2). x and -x have opposite
* jacobi symbols if and only if (mod % 4) == 3. */
negone[0] = mod[0] - 1;
for (i = 1; i < 16; ++i) negone[i] = mod[i];
mulmod256(sqr, sqr, negone, mod);
uint16_to_signed62(&x, sqr);
jac = secp256k1_jacobi64_maybe_var(&x, &m);
CHECK(jac == 0 || jac == 1 - (mod[0] & 2));
}
uint16_to_signed62(&x, in);
mutate_sign_signed62(&m.modulus);
for (vartime = 0; vartime < 2; ++vartime) { for (vartime = 0; vartime < 2; ++vartime) {
/* compute inverse */ /* compute inverse */
(vartime ? secp256k1_modinv64_var : secp256k1_modinv64)(&x, &m); (vartime ? secp256k1_modinv64_var : secp256k1_modinv64)(&x, &m);
/* produce output */ /* produce output */
signed62_to_uint16(out, &x); signed62_to_uint16(out, &x);
/* check if the inverse times the input is 1 (mod m), unless x is 0. */ /* check if the inverse times the input is 1 (mod m), unless x is 0. */
▲ Show 20 Lines • Show All 905 Lines • ▼ Show 20 Lines /* test secp256k1_i128_eq_var */
v1c ^= (((uint64_t)1) << (ub & 63)); v1c ^= (((uint64_t)1) << (ub & 63));
} else { } else {
v0c ^= (((uint64_t)1) << (ub & 63)); v0c ^= (((uint64_t)1) << (ub & 63));
} }
secp256k1_i128_load(&swz, v1c, v0c); secp256k1_i128_load(&swz, v1c, v0c);
} }
CHECK(secp256k1_i128_eq_var(&swa, &swz) == expect); CHECK(secp256k1_i128_eq_var(&swa, &swz) == expect);
} }
/* test secp256k1_i128_check_pow2 */ /* test secp256k1_i128_check_pow2 (sign == 1) */
{ {
int expect = (uc & 1); int expect = (uc & 1);
int pos = ub % 127; int pos = ub % 127;
if (expect) { if (expect) {
/* If expect==1, set swz to exactly (2 << pos). */ /* If expect==1, set swz to exactly 2^pos. */
uint64_t hi = 0; uint64_t hi = 0;
uint64_t lo = 0; uint64_t lo = 0;
if (pos & 64) { if (pos >= 64) {
hi = (((uint64_t)1) << (pos & 63)); hi = (((uint64_t)1) << (pos & 63));
} else { } else {
lo = (((uint64_t)1) << (pos & 63)); lo = (((uint64_t)1) << (pos & 63));
} }
secp256k1_i128_load(&swz, hi, lo); secp256k1_i128_load(&swz, hi, lo);
} else { } else {
/* If expect==0, set swz = swa, but update expect=1 if swa happens to equal (2 << pos). */ /* If expect==0, set swz = swa, but update expect=1 if swa happens to equal 2^pos. */
if (pos & 64) { if (pos >= 64) {
if ((v[1] == (((uint64_t)1) << (pos & 63))) && v[0] == 0) expect = 1; if ((v[1] == (((uint64_t)1) << (pos & 63))) && v[0] == 0) expect = 1;
} else { } else {
if ((v[0] == (((uint64_t)1) << (pos & 63))) && v[1] == 0) expect = 1; if ((v[0] == (((uint64_t)1) << (pos & 63))) && v[1] == 0) expect = 1;
} }
swz = swa; swz = swa;
} }
CHECK(secp256k1_i128_check_pow2(&swz, pos) == expect); CHECK(secp256k1_i128_check_pow2(&swz, pos, 1) == expect);
}
/* test secp256k1_i128_check_pow2 (sign == -1) */
{
int expect = (uc & 1);
int pos = ub % 127;
if (expect) {
/* If expect==1, set swz to exactly -2^pos. */
uint64_t hi = ~(uint64_t)0;
uint64_t lo = ~(uint64_t)0;
if (pos >= 64) {
hi <<= (pos & 63);
lo = 0;
} else {
lo <<= (pos & 63);
}
secp256k1_i128_load(&swz, hi, lo);
} else {
/* If expect==0, set swz = swa, but update expect=1 if swa happens to equal -2^pos. */
if (pos >= 64) {
if ((v[1] == ((~(uint64_t)0) << (pos & 63))) && v[0] == 0) expect = 1;
} else {
if ((v[0] == ((~(uint64_t)0) << (pos & 63))) && v[1] == ~(uint64_t)0) expect = 1;
}
swz = swa;
}
CHECK(secp256k1_i128_check_pow2(&swz, pos, -1) == expect);
} }
} }
static void run_int128_tests(void) { static void run_int128_tests(void) {
{ /* secp256k1_u128_accum_mul */ { /* secp256k1_u128_accum_mul */
secp256k1_uint128 res; secp256k1_uint128 res;
/* Check secp256k1_u128_accum_mul overflow */ /* Check secp256k1_u128_accum_mul overflow */
▲ Show 20 Lines • Show All 1,171 Lines • ▼ Show 20 Linesstatic void run_sqrt(void) {
/* Consistency checks for large random values */ /* Consistency checks for large random values */
for (i = 0; i < 10; i++) { for (i = 0; i < 10; i++) {
int j; int j;
random_fe_non_square(&ns); random_fe_non_square(&ns);
for (j = 0; j < COUNT; j++) { for (j = 0; j < COUNT; j++) {
random_fe(&x); random_fe(&x);
secp256k1_fe_sqr(&s, &x); secp256k1_fe_sqr(&s, &x);
CHECK(secp256k1_fe_is_square_var(&s));
test_sqrt(&s, &x); test_sqrt(&s, &x);
secp256k1_fe_negate(&t, &s, 1); secp256k1_fe_negate(&t, &s, 1);
CHECK(!secp256k1_fe_is_square_var(&t));
test_sqrt(&t, NULL); test_sqrt(&t, NULL);
secp256k1_fe_mul(&t, &s, &ns); secp256k1_fe_mul(&t, &s, &ns);
test_sqrt(&t, NULL); test_sqrt(&t, NULL);
} }
} }
} }
/***** FIELD/SCALAR INVERSE TESTS *****/ /***** FIELD/SCALAR INVERSE TESTS *****/
▲ Show 20 Lines • Show All 4,392 Lines • Show Last 20 Lines