1 /**********************************************************************
2 * Copyright (c) 2016 Andrew Poelstra *
3 * Distributed under the MIT software license, see the accompanying *
4 * file COPYING or http://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 "src/modules/recovery/main_impl.h"
11 #include "include/secp256k1_recovery.h"
12
test_exhaustive_recovery_sign(const secp256k1_context * ctx,const secp256k1_ge * group)13 void test_exhaustive_recovery_sign(const secp256k1_context *ctx, const secp256k1_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 secp256k1_fe r_dot_y_normalized;
24 secp256k1_ecdsa_recoverable_signature rsig;
25 secp256k1_ecdsa_signature sig;
26 secp256k1_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 secp256k1_scalar_set_int(&msg, i);
32 secp256k1_scalar_set_int(&sk, j);
33 secp256k1_scalar_get_b32(sk32, &sk);
34 secp256k1_scalar_get_b32(msg32, &msg);
35
36 secp256k1_ecdsa_sign_recoverable(ctx, &rsig, msg32, sk32, secp256k1_nonce_function_smallint, &k);
37
38 /* Check directly */
39 secp256k1_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 be the case for all points except the ones where
47 * R.x=1 (which the group is specifically selected to have).
48 * Note that this isn't actually useful; full recovery would need to convey
49 * floor(R.x / group_order), but only one bit is used as that is sufficient
50 * in the real group. */
51 expected_recid = overflow ? 2 : 0;
52 r_dot_y_normalized = group[k].y;
53 secp256k1_fe_normalize(&r_dot_y_normalized);
54 /* Also the recovery id is flipped depending if we hit the low-s branch */
55 if ((k * s) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER) {
56 expected_recid |= secp256k1_fe_is_odd(&r_dot_y_normalized);
57 } else {
58 expected_recid |= !secp256k1_fe_is_odd(&r_dot_y_normalized);
59 }
60 CHECK(recid == expected_recid);
61
62 /* Convert to a standard sig then check */
63 secp256k1_ecdsa_recoverable_signature_convert(ctx, &sig, &rsig);
64 secp256k1_ecdsa_signature_load(ctx, &r, &s, &sig);
65 /* Note that we compute expected_r *after* signing -- this is important
66 * because our nonce-computing function function might change k during
67 * signing. */
68 r_from_k(&expected_r, group, k, NULL);
69 CHECK(r == expected_r);
70 CHECK((k * s) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER ||
71 (k * (EXHAUSTIVE_TEST_ORDER - s)) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER);
72
73 /* Overflow means we've tried every possible nonce */
74 if (k < starting_k) {
75 break;
76 }
77 }
78 }
79 }
80 }
81
test_exhaustive_recovery_verify(const secp256k1_context * ctx,const secp256k1_ge * group)82 void test_exhaustive_recovery_verify(const secp256k1_context *ctx, const secp256k1_ge *group) {
83 /* This is essentially a copy of test_exhaustive_verify, with recovery added */
84 int s, r, msg, key;
85 uint64_t iter = 0;
86 for (s = 1; s < EXHAUSTIVE_TEST_ORDER; s++) {
87 for (r = 1; r < EXHAUSTIVE_TEST_ORDER; r++) {
88 for (msg = 1; msg < EXHAUSTIVE_TEST_ORDER; msg++) {
89 for (key = 1; key < EXHAUSTIVE_TEST_ORDER; key++) {
90 secp256k1_ge nonconst_ge;
91 secp256k1_ecdsa_recoverable_signature rsig;
92 secp256k1_ecdsa_signature sig;
93 secp256k1_pubkey pk;
94 secp256k1_scalar sk_s, msg_s, r_s, s_s;
95 secp256k1_scalar s_times_k_s, msg_plus_r_times_sk_s;
96 int recid = 0;
97 int k, should_verify;
98 unsigned char msg32[32];
99
100 if (skip_section(&iter)) continue;
101
102 secp256k1_scalar_set_int(&s_s, s);
103 secp256k1_scalar_set_int(&r_s, r);
104 secp256k1_scalar_set_int(&msg_s, msg);
105 secp256k1_scalar_set_int(&sk_s, key);
106 secp256k1_scalar_get_b32(msg32, &msg_s);
107
108 /* Verify by hand */
109 /* Run through every k value that gives us this r and check that *one* works.
110 * Note there could be none, there could be multiple, ECDSA is weird. */
111 should_verify = 0;
112 for (k = 0; k < EXHAUSTIVE_TEST_ORDER; k++) {
113 secp256k1_scalar check_x_s;
114 r_from_k(&check_x_s, group, k, NULL);
115 if (r_s == check_x_s) {
116 secp256k1_scalar_set_int(&s_times_k_s, k);
117 secp256k1_scalar_mul(&s_times_k_s, &s_times_k_s, &s_s);
118 secp256k1_scalar_mul(&msg_plus_r_times_sk_s, &r_s, &sk_s);
119 secp256k1_scalar_add(&msg_plus_r_times_sk_s, &msg_plus_r_times_sk_s, &msg_s);
120 should_verify |= secp256k1_scalar_eq(&s_times_k_s, &msg_plus_r_times_sk_s);
121 }
122 }
123 /* nb we have a "high s" rule */
124 should_verify &= !secp256k1_scalar_is_high(&s_s);
125
126 /* We would like to try recovering the pubkey and checking that it matches,
127 * but pubkey recovery is impossible in the exhaustive tests (the reason
128 * being that there are 12 nonzero r values, 12 nonzero points, and no
129 * overlap between the sets, so there are no valid signatures). */
130
131 /* Verify by converting to a standard signature and calling verify */
132 secp256k1_ecdsa_recoverable_signature_save(&rsig, &r_s, &s_s, recid);
133 secp256k1_ecdsa_recoverable_signature_convert(ctx, &sig, &rsig);
134 memcpy(&nonconst_ge, &group[sk_s], sizeof(nonconst_ge));
135 secp256k1_pubkey_save(&pk, &nonconst_ge);
136 CHECK(should_verify ==
137 secp256k1_ecdsa_verify(ctx, &sig, msg32, &pk));
138 }
139 }
140 }
141 }
142 }
143
test_exhaustive_recovery(const secp256k1_context * ctx,const secp256k1_ge * group)144 static void test_exhaustive_recovery(const secp256k1_context *ctx, const secp256k1_ge *group) {
145 test_exhaustive_recovery_sign(ctx, group);
146 test_exhaustive_recovery_verify(ctx, group);
147 }
148
149 #endif /* SECP256K1_MODULE_RECOVERY_EXHAUSTIVE_TESTS_H */
150