tests_exhaustive_impl.h (8349B)
1 /*********************************************************************** 2 * Copyright (c) 2016 Andrew Poelstra * 3 * Distributed under the MIT software license, see the accompanying * 4 * file COPYING or https://www.opensource.org/licenses/mit-license.php.* 5 ***********************************************************************/ 6 7 #ifndef SECP256K1_MODULE_RECOVERY_EXHAUSTIVE_TESTS_H 8 #define SECP256K1_MODULE_RECOVERY_EXHAUSTIVE_TESTS_H 9 10 #include "main_impl.h" 11 #include "../../../include/secp256k1_recovery.h" 12 13 static void test_exhaustive_recovery_sign(const haskellsecp256k1_v0_1_0_context *ctx, const haskellsecp256k1_v0_1_0_ge *group) { 14 int i, j, k; 15 uint64_t iter = 0; 16 17 /* Loop */ 18 for (i = 1; i < EXHAUSTIVE_TEST_ORDER; i++) { /* message */ 19 for (j = 1; j < EXHAUSTIVE_TEST_ORDER; j++) { /* key */ 20 if (skip_section(&iter)) continue; 21 for (k = 1; k < EXHAUSTIVE_TEST_ORDER; k++) { /* nonce */ 22 const int starting_k = k; 23 haskellsecp256k1_v0_1_0_fe r_dot_y_normalized; 24 haskellsecp256k1_v0_1_0_ecdsa_recoverable_signature rsig; 25 haskellsecp256k1_v0_1_0_ecdsa_signature sig; 26 haskellsecp256k1_v0_1_0_scalar sk, msg, r, s, expected_r; 27 unsigned char sk32[32], msg32[32]; 28 int expected_recid; 29 int recid; 30 int overflow; 31 haskellsecp256k1_v0_1_0_scalar_set_int(&msg, i); 32 haskellsecp256k1_v0_1_0_scalar_set_int(&sk, j); 33 haskellsecp256k1_v0_1_0_scalar_get_b32(sk32, &sk); 34 haskellsecp256k1_v0_1_0_scalar_get_b32(msg32, &msg); 35 36 haskellsecp256k1_v0_1_0_ecdsa_sign_recoverable(ctx, &rsig, msg32, sk32, haskellsecp256k1_v0_1_0_nonce_function_smallint, &k); 37 38 /* Check directly */ 39 haskellsecp256k1_v0_1_0_ecdsa_recoverable_signature_load(ctx, &r, &s, &recid, &rsig); 40 r_from_k(&expected_r, group, k, &overflow); 41 CHECK(r == expected_r); 42 CHECK((k * s) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER || 43 (k * (EXHAUSTIVE_TEST_ORDER - s)) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER); 44 /* The recid's second bit is for conveying overflow (R.x value >= group order). 45 * In the actual secp256k1 this is an astronomically unlikely event, but in the 46 * small group used here, it will almost certainly be the case for all points. 47 * Note that this isn't actually useful; full recovery would need to convey 48 * floor(R.x / group_order), but only one bit is used as that is sufficient 49 * in the real group. */ 50 expected_recid = overflow ? 2 : 0; 51 r_dot_y_normalized = group[k].y; 52 haskellsecp256k1_v0_1_0_fe_normalize(&r_dot_y_normalized); 53 /* Also the recovery id is flipped depending if we hit the low-s branch */ 54 if ((k * s) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER) { 55 expected_recid |= haskellsecp256k1_v0_1_0_fe_is_odd(&r_dot_y_normalized); 56 } else { 57 expected_recid |= !haskellsecp256k1_v0_1_0_fe_is_odd(&r_dot_y_normalized); 58 } 59 CHECK(recid == expected_recid); 60 61 /* Convert to a standard sig then check */ 62 haskellsecp256k1_v0_1_0_ecdsa_recoverable_signature_convert(ctx, &sig, &rsig); 63 haskellsecp256k1_v0_1_0_ecdsa_signature_load(ctx, &r, &s, &sig); 64 /* Note that we compute expected_r *after* signing -- this is important 65 * because our nonce-computing function function might change k during 66 * signing. */ 67 r_from_k(&expected_r, group, k, NULL); 68 CHECK(r == expected_r); 69 CHECK((k * s) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER || 70 (k * (EXHAUSTIVE_TEST_ORDER - s)) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER); 71 72 /* Overflow means we've tried every possible nonce */ 73 if (k < starting_k) { 74 break; 75 } 76 } 77 } 78 } 79 } 80 81 static void test_exhaustive_recovery_verify(const haskellsecp256k1_v0_1_0_context *ctx, const haskellsecp256k1_v0_1_0_ge *group) { 82 /* This is essentially a copy of test_exhaustive_verify, with recovery added */ 83 int s, r, msg, key; 84 uint64_t iter = 0; 85 for (s = 1; s < EXHAUSTIVE_TEST_ORDER; s++) { 86 for (r = 1; r < EXHAUSTIVE_TEST_ORDER; r++) { 87 for (msg = 1; msg < EXHAUSTIVE_TEST_ORDER; msg++) { 88 for (key = 1; key < EXHAUSTIVE_TEST_ORDER; key++) { 89 haskellsecp256k1_v0_1_0_ge nonconst_ge; 90 haskellsecp256k1_v0_1_0_ecdsa_recoverable_signature rsig; 91 haskellsecp256k1_v0_1_0_ecdsa_signature sig; 92 haskellsecp256k1_v0_1_0_pubkey pk; 93 haskellsecp256k1_v0_1_0_scalar sk_s, msg_s, r_s, s_s; 94 haskellsecp256k1_v0_1_0_scalar s_times_k_s, msg_plus_r_times_sk_s; 95 int recid = 0; 96 int k, should_verify; 97 unsigned char msg32[32]; 98 99 if (skip_section(&iter)) continue; 100 101 haskellsecp256k1_v0_1_0_scalar_set_int(&s_s, s); 102 haskellsecp256k1_v0_1_0_scalar_set_int(&r_s, r); 103 haskellsecp256k1_v0_1_0_scalar_set_int(&msg_s, msg); 104 haskellsecp256k1_v0_1_0_scalar_set_int(&sk_s, key); 105 haskellsecp256k1_v0_1_0_scalar_get_b32(msg32, &msg_s); 106 107 /* Verify by hand */ 108 /* Run through every k value that gives us this r and check that *one* works. 109 * Note there could be none, there could be multiple, ECDSA is weird. */ 110 should_verify = 0; 111 for (k = 0; k < EXHAUSTIVE_TEST_ORDER; k++) { 112 haskellsecp256k1_v0_1_0_scalar check_x_s; 113 r_from_k(&check_x_s, group, k, NULL); 114 if (r_s == check_x_s) { 115 haskellsecp256k1_v0_1_0_scalar_set_int(&s_times_k_s, k); 116 haskellsecp256k1_v0_1_0_scalar_mul(&s_times_k_s, &s_times_k_s, &s_s); 117 haskellsecp256k1_v0_1_0_scalar_mul(&msg_plus_r_times_sk_s, &r_s, &sk_s); 118 haskellsecp256k1_v0_1_0_scalar_add(&msg_plus_r_times_sk_s, &msg_plus_r_times_sk_s, &msg_s); 119 should_verify |= haskellsecp256k1_v0_1_0_scalar_eq(&s_times_k_s, &msg_plus_r_times_sk_s); 120 } 121 } 122 /* nb we have a "high s" rule */ 123 should_verify &= !haskellsecp256k1_v0_1_0_scalar_is_high(&s_s); 124 125 /* We would like to try recovering the pubkey and checking that it matches, 126 * but pubkey recovery is impossible in the exhaustive tests (the reason 127 * being that there are 12 nonzero r values, 12 nonzero points, and no 128 * overlap between the sets, so there are no valid signatures). */ 129 130 /* Verify by converting to a standard signature and calling verify */ 131 haskellsecp256k1_v0_1_0_ecdsa_recoverable_signature_save(&rsig, &r_s, &s_s, recid); 132 haskellsecp256k1_v0_1_0_ecdsa_recoverable_signature_convert(ctx, &sig, &rsig); 133 memcpy(&nonconst_ge, &group[sk_s], sizeof(nonconst_ge)); 134 haskellsecp256k1_v0_1_0_pubkey_save(&pk, &nonconst_ge); 135 CHECK(should_verify == 136 haskellsecp256k1_v0_1_0_ecdsa_verify(ctx, &sig, msg32, &pk)); 137 } 138 } 139 } 140 } 141 } 142 143 static void test_exhaustive_recovery(const haskellsecp256k1_v0_1_0_context *ctx, const haskellsecp256k1_v0_1_0_ge *group) { 144 test_exhaustive_recovery_sign(ctx, group); 145 test_exhaustive_recovery_verify(ctx, group); 146 } 147 148 #endif /* SECP256K1_MODULE_RECOVERY_EXHAUSTIVE_TESTS_H */