Changeset View
Changeset View
Standalone View
Standalone View
src/secp256k1/src/modules/recovery/tests_exhaustive_impl.h
- This file was added.
/********************************************************************** | |||||
* Copyright (c) 2016 Andrew Poelstra * | |||||
* Distributed under the MIT software license, see the accompanying * | |||||
* file COPYING or http://www.opensource.org/licenses/mit-license.php.* | |||||
**********************************************************************/ | |||||
#ifndef SECP256K1_MODULE_RECOVERY_EXHAUSTIVE_TESTS_H | |||||
#define SECP256K1_MODULE_RECOVERY_EXHAUSTIVE_TESTS_H | |||||
#include "src/modules/recovery/main_impl.h" | |||||
#include "include/secp256k1_recovery.h" | |||||
void test_exhaustive_recovery_sign(const secp256k1_context *ctx, const secp256k1_ge *group) { | |||||
int i, j, k; | |||||
/* Loop */ | |||||
for (i = 1; i < EXHAUSTIVE_TEST_ORDER; i++) { /* message */ | |||||
for (j = 1; j < EXHAUSTIVE_TEST_ORDER; j++) { /* key */ | |||||
for (k = 1; k < EXHAUSTIVE_TEST_ORDER; k++) { /* nonce */ | |||||
const int starting_k = k; | |||||
secp256k1_fe r_dot_y_normalized; | |||||
secp256k1_ecdsa_recoverable_signature rsig; | |||||
secp256k1_ecdsa_signature sig; | |||||
secp256k1_scalar sk, msg, r, s, expected_r; | |||||
unsigned char sk32[32], msg32[32]; | |||||
int expected_recid; | |||||
int recid; | |||||
secp256k1_scalar_set_int(&msg, i); | |||||
secp256k1_scalar_set_int(&sk, j); | |||||
secp256k1_scalar_get_b32(sk32, &sk); | |||||
secp256k1_scalar_get_b32(msg32, &msg); | |||||
secp256k1_ecdsa_sign_recoverable(ctx, &rsig, msg32, sk32, secp256k1_nonce_function_smallint, &k); | |||||
/* Check directly */ | |||||
secp256k1_ecdsa_recoverable_signature_load(ctx, &r, &s, &recid, &rsig); | |||||
r_from_k(&expected_r, group, k); | |||||
CHECK(r == expected_r); | |||||
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); | |||||
/* In computing the recid, there is an overflow condition that is disabled in | |||||
* scalar_low_impl.h `secp256k1_scalar_set_b32` because almost every r.y value | |||||
* will exceed the group order, and our signing code always holds out for r | |||||
* values that don't overflow, so with a proper overflow check the tests would | |||||
* loop indefinitely. */ | |||||
r_dot_y_normalized = group[k].y; | |||||
secp256k1_fe_normalize(&r_dot_y_normalized); | |||||
/* Also the recovery id is flipped depending if we hit the low-s branch */ | |||||
if ((k * s) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER) { | |||||
expected_recid = secp256k1_fe_is_odd(&r_dot_y_normalized) ? 1 : 0; | |||||
} else { | |||||
expected_recid = secp256k1_fe_is_odd(&r_dot_y_normalized) ? 0 : 1; | |||||
} | |||||
CHECK(recid == expected_recid); | |||||
/* Convert to a standard sig then check */ | |||||
secp256k1_ecdsa_recoverable_signature_convert(ctx, &sig, &rsig); | |||||
secp256k1_ecdsa_signature_load(ctx, &r, &s, &sig); | |||||
/* Note that we compute expected_r *after* signing -- this is important | |||||
* because our nonce-computing function function might change k during | |||||
* signing. */ | |||||
r_from_k(&expected_r, group, k); | |||||
CHECK(r == expected_r); | |||||
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); | |||||
/* Overflow means we've tried every possible nonce */ | |||||
if (k < starting_k) { | |||||
break; | |||||
} | |||||
} | |||||
} | |||||
} | |||||
} | |||||
void test_exhaustive_recovery_verify(const secp256k1_context *ctx, const secp256k1_ge *group) { | |||||
/* This is essentially a copy of test_exhaustive_verify, with recovery added */ | |||||
int s, r, msg, key; | |||||
for (s = 1; s < EXHAUSTIVE_TEST_ORDER; s++) { | |||||
for (r = 1; r < EXHAUSTIVE_TEST_ORDER; r++) { | |||||
for (msg = 1; msg < EXHAUSTIVE_TEST_ORDER; msg++) { | |||||
for (key = 1; key < EXHAUSTIVE_TEST_ORDER; key++) { | |||||
secp256k1_ge nonconst_ge; | |||||
secp256k1_ecdsa_recoverable_signature rsig; | |||||
secp256k1_ecdsa_signature sig; | |||||
secp256k1_pubkey pk; | |||||
secp256k1_scalar sk_s, msg_s, r_s, s_s; | |||||
secp256k1_scalar s_times_k_s, msg_plus_r_times_sk_s; | |||||
int recid = 0; | |||||
int k, should_verify; | |||||
unsigned char msg32[32]; | |||||
secp256k1_scalar_set_int(&s_s, s); | |||||
secp256k1_scalar_set_int(&r_s, r); | |||||
secp256k1_scalar_set_int(&msg_s, msg); | |||||
secp256k1_scalar_set_int(&sk_s, key); | |||||
secp256k1_scalar_get_b32(msg32, &msg_s); | |||||
/* Verify by hand */ | |||||
/* 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. */ | |||||
should_verify = 0; | |||||
for (k = 0; k < EXHAUSTIVE_TEST_ORDER; k++) { | |||||
secp256k1_scalar check_x_s; | |||||
r_from_k(&check_x_s, group, k); | |||||
if (r_s == check_x_s) { | |||||
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(&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); | |||||
should_verify |= secp256k1_scalar_eq(&s_times_k_s, &msg_plus_r_times_sk_s); | |||||
} | |||||
} | |||||
/* nb we have a "high s" rule */ | |||||
should_verify &= !secp256k1_scalar_is_high(&s_s); | |||||
/* We would like to try recovering the pubkey and checking that it matches, | |||||
* but pubkey recovery is impossible in the exhaustive tests (the reason | |||||
* being that there are 12 nonzero r values, 12 nonzero points, and no | |||||
* overlap between the sets, so there are no valid signatures). */ | |||||
/* Verify by converting to a standard signature and calling verify */ | |||||
secp256k1_ecdsa_recoverable_signature_save(&rsig, &r_s, &s_s, recid); | |||||
secp256k1_ecdsa_recoverable_signature_convert(ctx, &sig, &rsig); | |||||
memcpy(&nonconst_ge, &group[sk_s], sizeof(nonconst_ge)); | |||||
secp256k1_pubkey_save(&pk, &nonconst_ge); | |||||
CHECK(should_verify == | |||||
secp256k1_ecdsa_verify(ctx, &sig, msg32, &pk)); | |||||
} | |||||
} | |||||
} | |||||
} | |||||
} | |||||
static void test_exhaustive_recovery(const secp256k1_context *ctx, const secp256k1_ge *group) { | |||||
test_exhaustive_recovery_sign(ctx, group); | |||||
test_exhaustive_recovery_verify(ctx, group); | |||||
} | |||||
#endif /* SECP256K1_MODULE_RECOVERY_EXHAUSTIVE_TESTS_H */ |