Bitcoin Core  0.20.99
P2P Digital Currency
tests_exhaustive_impl.h
Go to the documentation of this file.
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 
12 
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;
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);
33  secp256k1_scalar_get_b32(sk32, &sk);
34  secp256k1_scalar_get_b32(msg32, &msg);
35 
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 */
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 
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;
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);
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 
144 static void test_exhaustive_recovery(const secp256k1_context *ctx, const secp256k1_ge *group) {
145  test_exhaustive_recovery_sign(ctx, group);
147 }
148 
149 #endif /* SECP256K1_MODULE_RECOVERY_EXHAUSTIVE_TESTS_H */
static int secp256k1_scalar_eq(const secp256k1_scalar *a, const secp256k1_scalar *b)
Compare two scalars.
static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Multiply two scalars (modulo the group order).
static void secp256k1_ecdsa_recoverable_signature_load(const secp256k1_context *ctx, secp256k1_scalar *r, secp256k1_scalar *s, int *recid, const secp256k1_ecdsa_recoverable_signature *sig)
Definition: main_impl.h:12
Opaque data structured that holds a parsed ECDSA signature, supporting pubkey recovery.
static SECP256K1_INLINE int skip_section(uint64_t *iter)
SECP256K1_API int secp256k1_ecdsa_recoverable_signature_convert(const secp256k1_context *ctx, secp256k1_ecdsa_signature *sig, const secp256k1_ecdsa_recoverable_signature *sigin) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3)
Convert a recoverable signature into a normal signature.
Definition: main_impl.h:74
static void test_exhaustive_recovery(const secp256k1_context *ctx, const secp256k1_ge *group)
static void secp256k1_pubkey_save(secp256k1_pubkey *pubkey, secp256k1_ge *ge)
Definition: secp256k1.c:263
void r_from_k(secp256k1_scalar *r, const secp256k1_ge *group, int k, int *overflow)
void test_exhaustive_recovery_sign(const secp256k1_context *ctx, const secp256k1_ge *group)
static int secp256k1_fe_is_odd(const secp256k1_fe *a)
Check the "oddness" of a field element.
static secp256k1_context * ctx
Definition: tests.c:36
SECP256K1_API int secp256k1_ecdsa_sign_recoverable(const secp256k1_context *ctx, secp256k1_ecdsa_recoverable_signature *sig, const unsigned char *msg32, const unsigned char *seckey, secp256k1_nonce_function noncefp, const void *ndata) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4)
Create a recoverable ECDSA signature.
Definition: main_impl.h:123
static int secp256k1_scalar_is_high(const secp256k1_scalar *a)
Check whether a scalar is higher than the group order divided by 2.
void test_exhaustive_recovery_verify(const secp256k1_context *ctx, const secp256k1_ge *group)
A group element of the secp256k1 curve, in affine coordinates.
Definition: group.h:14
Opaque data structured that holds a parsed ECDSA signature.
Definition: secp256k1.h:80
#define CHECK(cond)
Definition: util.h:53
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
static void secp256k1_ecdsa_signature_load(const secp256k1_context *ctx, secp256k1_scalar *r, secp256k1_scalar *s, const secp256k1_ecdsa_signature *sig)
Definition: secp256k1.c:318
static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar *a)
Convert a scalar to a byte array.
static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Add two scalars together (modulo the group order).
#define EXHAUSTIVE_TEST_ORDER
static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v)
Set a scalar to an unsigned integer.
void * memcpy(void *a, const void *b, size_t c)
static void secp256k1_fe_normalize(secp256k1_fe *r)
Field element module.
int secp256k1_nonce_function_smallint(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, const unsigned char *algo16, void *data, unsigned int attempt)
secp256k1_fe y
Definition: group.h:16
static void secp256k1_ecdsa_recoverable_signature_save(secp256k1_ecdsa_recoverable_signature *sig, const secp256k1_scalar *r, const secp256k1_scalar *s, int recid)
Definition: main_impl.h:27
Opaque data structure that holds a parsed and valid public key.
Definition: secp256k1.h:67
SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_ecdsa_verify(const secp256k1_context *ctx, const secp256k1_ecdsa_signature *sig, const unsigned char *msg32, const secp256k1_pubkey *pubkey) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4)
Verify an ECDSA signature.
Definition: secp256k1.c:423