Page MenuHomePhabricator
Differential D7660 Diff 24019 src/secp256k1/src/tests_exhaustive.c

Changeset View

Standalone View

View Options

src/secp256k1/src/tests_exhaustive.c

Show First 20 Lines • Show All 209 Lines • ▼ Show 20 Lines for (i = 0; i < EXHAUSTIVE_TEST_ORDER; i++) {
} }
} }
} }
} }
} }
secp256k1_scratch_destroy(&ctx->error_callback, scratch); secp256k1_scratch_destroy(&ctx->error_callback, scratch);
} }
void r_from_k(secp256k1_scalar *r, const secp256k1_ge *group, int k) { void r_from_k(secp256k1_scalar *r, const secp256k1_ge *group, int k, int* overflow) {
secp256k1_fe x; secp256k1_fe x;
unsigned char x_bin[32]; unsigned char x_bin[32];
k %= EXHAUSTIVE_TEST_ORDER; k %= EXHAUSTIVE_TEST_ORDER;
x = group[k].x; x = group[k].x;
secp256k1_fe_normalize(&x); secp256k1_fe_normalize(&x);
secp256k1_fe_get_b32(x_bin, &x); secp256k1_fe_get_b32(x_bin, &x);
secp256k1_scalar_set_b32(r, x_bin, NULL); secp256k1_scalar_set_b32(r, x_bin, overflow);
} }
void test_exhaustive_verify(const secp256k1_context *ctx, const secp256k1_ge *group) { void test_exhaustive_verify(const secp256k1_context *ctx, const secp256k1_ge *group) {
int s, r, msg, key; int s, r, msg, key;
for (s = 1; s < EXHAUSTIVE_TEST_ORDER; s++) { for (s = 1; s < EXHAUSTIVE_TEST_ORDER; s++) {
for (r = 1; r < EXHAUSTIVE_TEST_ORDER; r++) { for (r = 1; r < EXHAUSTIVE_TEST_ORDER; r++) {
for (msg = 1; msg < EXHAUSTIVE_TEST_ORDER; msg++) { for (msg = 1; msg < EXHAUSTIVE_TEST_ORDER; msg++) {
for (key = 1; key < EXHAUSTIVE_TEST_ORDER; key++) { for (key = 1; key < EXHAUSTIVE_TEST_ORDER; key++) {
Show All 11 Lines for (s = 1; s < EXHAUSTIVE_TEST_ORDER; s++) {
secp256k1_scalar_set_int(&sk_s, key); secp256k1_scalar_set_int(&sk_s, key);
/* Verify by hand */ /* Verify by hand */
/* Run through every k value that gives us this r and check that *one* works. /* Run through every k value that gives us this r and check that *one* works.
* Note there could be none, there could be multiple, ECDSA is weird. */ * Note there could be none, there could be multiple, ECDSA is weird. */
should_verify = 0; should_verify = 0;
for (k = 0; k < EXHAUSTIVE_TEST_ORDER; k++) { for (k = 0; k < EXHAUSTIVE_TEST_ORDER; k++) {
secp256k1_scalar check_x_s; secp256k1_scalar check_x_s;
r_from_k(&check_x_s, group, k); r_from_k(&check_x_s, group, k, NULL);
if (r_s == check_x_s) { if (r_s == check_x_s) {
secp256k1_scalar_set_int(&s_times_k_s, k); secp256k1_scalar_set_int(&s_times_k_s, k);
secp256k1_scalar_mul(&s_times_k_s, &s_times_k_s, &s_s); secp256k1_scalar_mul(&s_times_k_s, &s_times_k_s, &s_s);
secp256k1_scalar_mul(&msg_plus_r_times_sk_s, &r_s, &sk_s); secp256k1_scalar_mul(&msg_plus_r_times_sk_s, &r_s, &sk_s);
secp256k1_scalar_add(&msg_plus_r_times_sk_s, &msg_plus_r_times_sk_s, &msg_s); secp256k1_scalar_add(&msg_plus_r_times_sk_s, &msg_plus_r_times_sk_s, &msg_s);
should_verify |= secp256k1_scalar_eq(&s_times_k_s, &msg_plus_r_times_sk_s); should_verify |= secp256k1_scalar_eq(&s_times_k_s, &msg_plus_r_times_sk_s);
} }
} }
Show All 30 Lines for (i = 1; i < EXHAUSTIVE_TEST_ORDER; i++) { /* message */
secp256k1_scalar_get_b32(msg32, &msg); secp256k1_scalar_get_b32(msg32, &msg);
secp256k1_ecdsa_sign(ctx, &sig, msg32, sk32, secp256k1_nonce_function_smallint, &k); secp256k1_ecdsa_sign(ctx, &sig, msg32, sk32, secp256k1_nonce_function_smallint, &k);
secp256k1_ecdsa_signature_load(ctx, &r, &s, &sig); secp256k1_ecdsa_signature_load(ctx, &r, &s, &sig);
/* Note that we compute expected_r *after* signing -- this is important /* Note that we compute expected_r *after* signing -- this is important
* because our nonce-computing function function might change k during * because our nonce-computing function function might change k during
* signing. */ * signing. */
r_from_k(&expected_r, group, k); r_from_k(&expected_r, group, k, NULL);
CHECK(r == expected_r); CHECK(r == expected_r);
CHECK((k * s) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER || CHECK((k * s) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER ||
(k * (EXHAUSTIVE_TEST_ORDER - s)) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER); (k * (EXHAUSTIVE_TEST_ORDER - s)) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER);
/* Overflow means we've tried every possible nonce */ /* Overflow means we've tried every possible nonce */
if (k < starting_k) { if (k < starting_k) {
break; break;
} }
▲ Show 20 Lines • Show All 74 Lines • Show Last 20 Lines