Bitcoin Core  27.99.0
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 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 
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;
33  secp256k1_scalar_get_b32(sk32, &sk);
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 ||
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  secp256k1_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 |= secp256k1_fe_is_odd(&r_dot_y_normalized);
56  } else {
57  expected_recid |= !secp256k1_fe_is_odd(&r_dot_y_normalized);
58  }
59  CHECK(recid == expected_recid);
60 
61  /* Convert to a standard sig then check */
63  secp256k1_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 ||
71 
72  /* Overflow means we've tried every possible nonce */
73  if (k < starting_k) {
74  break;
75  }
76  }
77  }
78  }
79 }
80 
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  secp256k1_ge nonconst_ge;
93  secp256k1_scalar sk_s, msg_s, r_s, s_s;
94  secp256k1_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  secp256k1_scalar_set_int(&s_s, s);
102  secp256k1_scalar_set_int(&r_s, r);
103  secp256k1_scalar_set_int(&msg_s, msg);
104  secp256k1_scalar_set_int(&sk_s, key);
105  secp256k1_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  secp256k1_scalar check_x_s;
113  r_from_k(&check_x_s, group, k, NULL);
114  if (r_s == check_x_s) {
115  secp256k1_scalar_set_int(&s_times_k_s, k);
116  secp256k1_scalar_mul(&s_times_k_s, &s_times_k_s, &s_s);
117  secp256k1_scalar_mul(&msg_plus_r_times_sk_s, &r_s, &sk_s);
118  secp256k1_scalar_add(&msg_plus_r_times_sk_s, &msg_plus_r_times_sk_s, &msg_s);
119  should_verify |= secp256k1_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 &= !secp256k1_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  secp256k1_ecdsa_recoverable_signature_save(&rsig, &r_s, &s_s, recid);
133  memcpy(&nonconst_ge, &group[sk_s], sizeof(nonconst_ge));
134  secp256k1_pubkey_save(&pk, &nonconst_ge);
135  CHECK(should_verify ==
136  secp256k1_ecdsa_verify(ctx, &sig, msg32, &pk));
137  }
138  }
139  }
140  }
141 }
142 
146 }
147 
148 #endif /* SECP256K1_MODULE_RECOVERY_EXHAUSTIVE_TESTS_H */
#define secp256k1_fe_is_odd
Definition: field.h:86
#define secp256k1_fe_normalize
Definition: field.h:78
#define CHECK(cond)
Unconditional failure on condition failure.
Definition: util.h:35
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
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
static void test_exhaustive_recovery(const secp256k1_context *ctx, const secp256k1_ge *group)
static void test_exhaustive_recovery_sign(const secp256k1_context *ctx, const secp256k1_ge *group)
static void test_exhaustive_recovery_verify(const secp256k1_context *ctx, const secp256k1_ge *group)
static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v)
Set a scalar to an unsigned integer.
static int secp256k1_scalar_eq(const secp256k1_scalar *a, const secp256k1_scalar *b)
Compare two scalars.
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).
static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Multiply two scalars (modulo the group order).
static int secp256k1_scalar_is_high(const secp256k1_scalar *a)
Check whether a scalar is higher than the group order divided by 2.
static void secp256k1_pubkey_save(secp256k1_pubkey *pubkey, secp256k1_ge *ge)
Definition: secp256k1.c:253
static void secp256k1_ecdsa_signature_load(const secp256k1_context *ctx, secp256k1_scalar *r, secp256k1_scalar *s, const secp256k1_ecdsa_signature *sig)
Definition: secp256k1.c:357
SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_ecdsa_verify(const secp256k1_context *ctx, const secp256k1_ecdsa_signature *sig, const unsigned char *msghash32, 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:462
SECP256K1_API int secp256k1_ecdsa_sign_recoverable(const secp256k1_context *ctx, secp256k1_ecdsa_recoverable_signature *sig, const unsigned char *msghash32, 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
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
Opaque data structured that holds a parsed ECDSA signature, supporting pubkey recovery.
Opaque data structured that holds a parsed ECDSA signature.
Definition: secp256k1.h:87
This field implementation represents the value as 10 uint32_t limbs in base 2^26.
Definition: field_10x26.h:14
A group element in affine coordinates on the secp256k1 curve, or occasionally on an isomorphic curve ...
Definition: group.h:16
Opaque data structure that holds a parsed and valid public key.
Definition: secp256k1.h:74
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
static SECP256K1_INLINE int skip_section(uint64_t *iter)
static void r_from_k(secp256k1_scalar *r, const secp256k1_ge *group, int k, int *overflow)
#define EXHAUSTIVE_TEST_ORDER
static 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)