Bitcoin ABC 0.26.3
P2P Digital Currency
Loading...
Searching...
No Matches
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
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;
26 secp256k1_scalar sk, msg, r, s, expected_r;
27 unsigned char sk32[32], msg32[32];
29 int recid;
30 int overflow;
35
37
38 /* Check directly */
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 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;
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) {
57 } else {
59 }
61
62 /* Convert to a standard sig then check */
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. */
69 CHECK(r == expected_r);
70 CHECK((k * 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++) {
96 int recid = 0;
97 int k, should_verify;
98 unsigned char msg32[32];
99
100 if (skip_section(&iter)) continue;
101
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++) {
115 if (r_s == check_x_s) {
121 }
122 }
123 /* nb we have a "high s" rule */
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 */
138 }
139 }
140 }
141 }
142}
143
148
149#endif /* SECP256K1_MODULE_RECOVERY_EXHAUSTIVE_TESTS_H */
secp256k1_context * ctx
static int secp256k1_fe_is_odd(const secp256k1_fe *a)
Check the "oddness" of a field element.
static void secp256k1_fe_normalize(secp256k1_fe *r)
Field element module.
SchnorrSig sig
T GetRand(T nMax=std::numeric_limits< T >::max()) noexcept
Generate a uniform random integer of type T in the range [0..nMax) nMax defaults to std::numeric_limi...
Definition random.h:85
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)
void test_exhaustive_recovery_verify(const secp256k1_context *ctx, const secp256k1_ge *group)
void test_exhaustive_recovery_sign(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.
#define CHECK(cond)
Definition util.h:53
static void secp256k1_pubkey_save(secp256k1_pubkey *pubkey, secp256k1_ge *ge)
Definition secp256k1.c:264
static void secp256k1_ecdsa_signature_load(const secp256k1_context *ctx, secp256k1_scalar *r, secp256k1_scalar *s, const secp256k1_ecdsa_signature *sig)
Definition secp256k1.c:319
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:424
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:80
A group element of the secp256k1 curve, in affine coordinates.
Definition group.h:13
Opaque data structure that holds a parsed and valid public key.
Definition secp256k1.h:67
A scalar modulo the group order of the secp256k1 curve.
Definition scalar_4x64.h:13
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)
static SECP256K1_INLINE int skip_section(uint64_t *iter)
void r_from_k(secp256k1_scalar *r, const secp256k1_ge *group, int k, int *overflow)
#define EXHAUSTIVE_TEST_ORDER