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) 2020 Pieter Wuille *
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_SCHNORRSIG_TESTS_EXHAUSTIVE_H
8#define SECP256K1_MODULE_SCHNORRSIG_TESTS_EXHAUSTIVE_H
9
12
13static const unsigned char invalid_pubkey_bytes[][32] = {
14 /* 0 */
15 {
16 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
17 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
18 },
19 /* 2 */
20 {
21 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
22 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2
23 },
24 /* order */
25 {
26 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
27 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
28 ((EXHAUSTIVE_TEST_ORDER + 0UL) >> 24) & 0xFF,
29 ((EXHAUSTIVE_TEST_ORDER + 0UL) >> 16) & 0xFF,
30 ((EXHAUSTIVE_TEST_ORDER + 0UL) >> 8) & 0xFF,
31 (EXHAUSTIVE_TEST_ORDER + 0UL) & 0xFF
32 },
33 /* order + 1 */
34 {
35 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
36 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
37 ((EXHAUSTIVE_TEST_ORDER + 1UL) >> 24) & 0xFF,
38 ((EXHAUSTIVE_TEST_ORDER + 1UL) >> 16) & 0xFF,
39 ((EXHAUSTIVE_TEST_ORDER + 1UL) >> 8) & 0xFF,
40 (EXHAUSTIVE_TEST_ORDER + 1UL) & 0xFF
41 },
42 /* field size */
43 {
44 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
45 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFC, 0x2F
46 },
47 /* field size + 1 (note that 1 is legal) */
48 {
49 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
50 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFC, 0x30
51 },
52 /* 2^256 - 1 */
53 {
54 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
55 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF
56 }
57};
58
59#define NUM_INVALID_KEYS (sizeof(invalid_pubkey_bytes) / sizeof(invalid_pubkey_bytes[0]))
60
61static int secp256k1_hardened_nonce_function_smallint(unsigned char *nonce32, const unsigned char *msg32,
62 const unsigned char *key32, const unsigned char *xonly_pk32,
63 const unsigned char *algo16, void* data) {
65 int *idata = data;
66 (void)msg32;
67 (void)key32;
69 (void)algo16;
72 return 1;
73}
74
75static void test_exhaustive_schnorrsig_verify(const secp256k1_context *ctx, const secp256k1_xonly_pubkey* pubkeys, unsigned char (*xonly_pubkey_bytes)[32], const int* parities) {
76 int d;
77 uint64_t iter = 0;
78 /* Iterate over the possible public keys to verify against (through their corresponding DL d). */
79 for (d = 1; d <= EXHAUSTIVE_TEST_ORDER / 2; ++d) {
80 int actual_d;
81 unsigned k;
82 unsigned char pk32[32];
83 memcpy(pk32, xonly_pubkey_bytes[d - 1], 32);
84 actual_d = parities[d - 1] ? EXHAUSTIVE_TEST_ORDER - d : d;
85 /* Iterate over the possible valid first 32 bytes in the signature, through their corresponding DL k.
86 Values above EXHAUSTIVE_TEST_ORDER/2 refer to the entries in invalid_pubkey_bytes. */
87 for (k = 1; k <= EXHAUSTIVE_TEST_ORDER / 2 + NUM_INVALID_KEYS; ++k) {
88 unsigned char sig64[64];
89 int actual_k = -1;
91 int e_count_done = 0;
92 if (skip_section(&iter)) continue;
93 if (k <= EXHAUSTIVE_TEST_ORDER / 2) {
94 memcpy(sig64, xonly_pubkey_bytes[k - 1], 32);
95 actual_k = parities[k - 1] ? EXHAUSTIVE_TEST_ORDER - k : k;
96 } else {
98 }
99 /* Randomly generate messages until all challenges have been hit. */
102 unsigned char msg32[32];
105 /* Only do work if we hit a challenge we haven't tried before. */
106 if (!e_done[e]) {
107 /* Iterate over the possible valid last 32 bytes in the signature.
108 0..order=that s value; order+1=random bytes */
109 int count_valid = 0, s;
110 for (s = 0; s <= EXHAUSTIVE_TEST_ORDER + 1; ++s) {
111 int expect_valid, valid;
112 if (s <= EXHAUSTIVE_TEST_ORDER) {
118 } else {
120 expect_valid = 0;
121 }
122 valid = secp256k1_schnorrsig_verify(ctx, sig64, msg32, &pubkeys[d - 1]);
123 CHECK(valid == expect_valid);
124 count_valid += valid;
125 }
126 /* Exactly one s value must verify, unless R is illegal. */
127 CHECK(count_valid == (actual_k != -1));
128 /* Don't retry other messages that result in the same challenge. */
129 e_done[e] = 1;
130 ++e_count_done;
131 }
132 }
133 }
134 }
135}
136
137static void test_exhaustive_schnorrsig_sign(const secp256k1_context *ctx, unsigned char (*xonly_pubkey_bytes)[32], const secp256k1_keypair* keypairs, const int* parities) {
138 int d, k;
139 uint64_t iter = 0;
140 /* Loop over keys. */
141 for (d = 1; d < EXHAUSTIVE_TEST_ORDER; ++d) {
142 int actual_d = d;
143 if (parities[d - 1]) actual_d = EXHAUSTIVE_TEST_ORDER - d;
144 /* Loop over nonces. */
145 for (k = 1; k < EXHAUSTIVE_TEST_ORDER; ++k) {
146 int e_done[EXHAUSTIVE_TEST_ORDER] = {0};
147 int e_count_done = 0;
148 unsigned char msg32[32];
149 unsigned char sig64[64];
150 int actual_k = k;
151 if (skip_section(&iter)) continue;
152 if (parities[k - 1]) actual_k = EXHAUSTIVE_TEST_ORDER - k;
153 /* Generate random messages until all challenges have been tried. */
158 /* Only do work if we hit a challenge we haven't tried before. */
159 if (!e_done[e]) {
161 unsigned char expected_s_bytes[32];
163 /* Invoke the real function to construct a signature. */
165 /* The first 32 bytes must match the xonly pubkey for the specified k. */
167 /* The last 32 bytes must match the expected s value. */
169 /* Don't retry other messages that result in the same challenge. */
170 e_done[e] = 1;
171 ++e_count_done;
172 }
173 }
174 }
175 }
176}
177
182 unsigned char xonly_pubkey_bytes[EXHAUSTIVE_TEST_ORDER - 1][32];
183 unsigned i;
184
185 /* Verify that all invalid_pubkey_bytes are actually invalid. */
186 for (i = 0; i < NUM_INVALID_KEYS; ++i) {
189 }
190
191 /* Construct keypairs and xonly-pubkeys for the entire group. */
192 for (i = 1; i < EXHAUSTIVE_TEST_ORDER; ++i) {
194 unsigned char buf[32];
198 CHECK(secp256k1_keypair_xonly_pub(ctx, &xonly_pubkey[i - 1], &parity[i - 1], &keypair[i - 1]));
200 }
201
204}
205
206#endif
secp256k1_context * ctx
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_scalar_set_int(secp256k1_scalar *r, unsigned int v)
Set a scalar to an unsigned integer.
static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar *a)
Convert a scalar to a byte array.
static void secp256k1_schnorrsig_challenge(secp256k1_scalar *e, const unsigned char *r32, const unsigned char *msg32, const unsigned char *pubkey32)
Definition main_impl.h:111
static void test_exhaustive_schnorrsig(const secp256k1_context *ctx)
static int secp256k1_hardened_nonce_function_smallint(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, const unsigned char *xonly_pk32, const unsigned char *algo16, void *data)
static const unsigned char invalid_pubkey_bytes[][32]
#define NUM_INVALID_KEYS
static void test_exhaustive_schnorrsig_verify(const secp256k1_context *ctx, const secp256k1_xonly_pubkey *pubkeys, unsigned char(*xonly_pubkey_bytes)[32], const int *parities)
static void test_exhaustive_schnorrsig_sign(const secp256k1_context *ctx, unsigned char(*xonly_pubkey_bytes)[32], const secp256k1_keypair *keypairs, const int *parities)
static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n)
Semantics like memcmp.
Definition util.h:224
#define CHECK(cond)
Definition util.h:53
SECP256K1_API int secp256k1_xonly_pubkey_serialize(const secp256k1_context *ctx, unsigned char *output32, const secp256k1_xonly_pubkey *pubkey) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3)
Serialize an xonly_pubkey object into a 32-byte sequence.
Definition main_impl.h:43
SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_keypair_create(const secp256k1_context *ctx, secp256k1_keypair *keypair, const unsigned char *seckey) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3)
Compute the keypair for a secret key.
Definition main_impl.h:171
SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_keypair_xonly_pub(const secp256k1_context *ctx, secp256k1_xonly_pubkey *pubkey, int *pk_parity, const secp256k1_keypair *keypair) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(4)
Get the x-only public key from a keypair.
Definition main_impl.h:209
SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_xonly_pubkey_parse(const secp256k1_context *ctx, secp256k1_xonly_pubkey *pubkey, const unsigned char *input32) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3)
Parse a 32-byte sequence into a xonly_pubkey object.
Definition main_impl.h:21
SECP256K1_API int secp256k1_schnorrsig_sign(const secp256k1_context *ctx, unsigned char *sig64, const unsigned char *msg32, const secp256k1_keypair *keypair, secp256k1_nonce_function_hardened noncefp, void *ndata) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4)
Create a Schnorr signature.
Definition main_impl.h:127
SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_schnorrsig_verify(const secp256k1_context *ctx, const unsigned char *sig64, const unsigned char *msg32, const secp256k1_xonly_pubkey *pubkey) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4)
Verify a Schnorr signature.
Definition main_impl.h:190
Opaque data structure that holds a keypair consisting of a secret and a public key.
A scalar modulo the group order of the secp256k1 curve.
Definition scalar_4x64.h:13
Opaque data structure that holds a parsed and valid "x-only" public key.
static void secp256k1_testrand256(unsigned char *b32)
Generate a pseudorandom 32-byte array.
static SECP256K1_INLINE int skip_section(uint64_t *iter)
#define EXHAUSTIVE_TEST_ORDER