1 /**********************************************************************
2 * Copyright (c) 2013, 2014, 2015 Pieter Wuille, Gregory Maxwell *
3 * Distributed under the MIT software license, see the accompanying *
4 * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
5 **********************************************************************/
7 #if defined HAVE_CONFIG_H
8 #include "libsecp256k1-config.h"
16 #include "secp256k1.c"
17 #include "include/secp256k1.h"
18 #include "testrand_impl.h"
20 #ifdef ENABLE_OPENSSL_TESTS
21 #include "openssl/bn.h"
22 #include "openssl/ec.h"
23 #include "openssl/ecdsa.h"
24 #include "openssl/obj_mac.h"
27 #include "contrib/lax_der_parsing.c"
28 #include "contrib/lax_der_privatekey_parsing.c"
30 #if !defined(VG_CHECK)
31 # if defined(VALGRIND)
32 # include <valgrind/memcheck.h>
33 # define VG_UNDEF(x,y) VALGRIND_MAKE_MEM_UNDEFINED((x),(y))
34 # define VG_CHECK(x,y) VALGRIND_CHECK_MEM_IS_DEFINED((x),(y))
36 # define VG_UNDEF(x,y)
37 # define VG_CHECK(x,y)
41 static int count = 64;
42 static secp256k1_context *ctx = NULL;
44 static void counting_illegal_callback_fn(const char* str, void* data) {
45 /* Dummy callback function that just counts. */
52 static void uncounting_illegal_callback_fn(const char* str, void* data) {
53 /* Dummy callback function that just counts (backwards). */
60 void random_field_element_test(secp256k1_fe *fe) {
62 unsigned char b32[32];
63 secp256k1_rand256_test(b32);
64 if (secp256k1_fe_set_b32(fe, b32)) {
70 void random_field_element_magnitude(secp256k1_fe *fe) {
72 int n = secp256k1_rand_int(9);
73 secp256k1_fe_normalize(fe);
77 secp256k1_fe_clear(&zero);
78 secp256k1_fe_negate(&zero, &zero, 0);
79 secp256k1_fe_mul_int(&zero, n - 1);
80 secp256k1_fe_add(fe, &zero);
81 VERIFY_CHECK(fe->magnitude == n);
84 void random_group_element_test(secp256k1_ge *ge) {
87 random_field_element_test(&fe);
88 if (secp256k1_ge_set_xo_var(ge, &fe, secp256k1_rand_bits(1))) {
89 secp256k1_fe_normalize(&ge->y);
95 void random_group_element_jacobian_test(secp256k1_gej *gej, const secp256k1_ge *ge) {
98 random_field_element_test(&gej->z);
99 if (!secp256k1_fe_is_zero(&gej->z)) {
103 secp256k1_fe_sqr(&z2, &gej->z);
104 secp256k1_fe_mul(&z3, &z2, &gej->z);
105 secp256k1_fe_mul(&gej->x, &ge->x, &z2);
106 secp256k1_fe_mul(&gej->y, &ge->y, &z3);
107 gej->infinity = ge->infinity;
110 void random_scalar_order_test(secp256k1_scalar *num) {
112 unsigned char b32[32];
114 secp256k1_rand256_test(b32);
115 secp256k1_scalar_set_b32(num, b32, &overflow);
116 if (overflow || secp256k1_scalar_is_zero(num)) {
123 void random_scalar_order(secp256k1_scalar *num) {
125 unsigned char b32[32];
127 secp256k1_rand256(b32);
128 secp256k1_scalar_set_b32(num, b32, &overflow);
129 if (overflow || secp256k1_scalar_is_zero(num)) {
136 void run_context_tests(void) {
137 secp256k1_pubkey pubkey;
138 secp256k1_ecdsa_signature sig;
139 unsigned char ctmp[32];
142 secp256k1_context *none = secp256k1_context_create(SECP256K1_CONTEXT_NONE);
143 secp256k1_context *sign = secp256k1_context_create(SECP256K1_CONTEXT_SIGN);
144 secp256k1_context *vrfy = secp256k1_context_create(SECP256K1_CONTEXT_VERIFY);
145 secp256k1_context *both = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY);
149 secp256k1_scalar msg, key, nonce;
150 secp256k1_scalar sigr, sigs;
154 secp256k1_context_set_illegal_callback(vrfy, counting_illegal_callback_fn, &ecount);
155 secp256k1_context_set_illegal_callback(sign, counting_illegal_callback_fn, &ecount2);
156 secp256k1_context_set_error_callback(sign, counting_illegal_callback_fn, NULL);
157 CHECK(vrfy->error_callback.fn != sign->error_callback.fn);
159 /*** clone and destroy all of them to make sure cloning was complete ***/
161 secp256k1_context *ctx_tmp;
163 ctx_tmp = none; none = secp256k1_context_clone(none); secp256k1_context_destroy(ctx_tmp);
164 ctx_tmp = sign; sign = secp256k1_context_clone(sign); secp256k1_context_destroy(ctx_tmp);
165 ctx_tmp = vrfy; vrfy = secp256k1_context_clone(vrfy); secp256k1_context_destroy(ctx_tmp);
166 ctx_tmp = both; both = secp256k1_context_clone(both); secp256k1_context_destroy(ctx_tmp);
169 /* Verify that the error callback makes it across the clone. */
170 CHECK(vrfy->error_callback.fn != sign->error_callback.fn);
171 /* And that it resets back to default. */
172 secp256k1_context_set_error_callback(sign, NULL, NULL);
173 CHECK(vrfy->error_callback.fn == sign->error_callback.fn);
175 /*** attempt to use them ***/
176 random_scalar_order_test(&msg);
177 random_scalar_order_test(&key);
178 secp256k1_ecmult_gen(&both->ecmult_gen_ctx, &pubj, &key);
179 secp256k1_ge_set_gej(&pub, &pubj);
181 /* Verify context-type checking illegal-argument errors. */
183 CHECK(secp256k1_ec_pubkey_create(vrfy, &pubkey, ctmp) == 0);
185 VG_UNDEF(&pubkey, sizeof(pubkey));
186 CHECK(secp256k1_ec_pubkey_create(sign, &pubkey, ctmp) == 1);
187 VG_CHECK(&pubkey, sizeof(pubkey));
188 CHECK(secp256k1_ecdsa_sign(vrfy, &sig, ctmp, ctmp, NULL, NULL) == 0);
190 VG_UNDEF(&sig, sizeof(sig));
191 CHECK(secp256k1_ecdsa_sign(sign, &sig, ctmp, ctmp, NULL, NULL) == 1);
192 VG_CHECK(&sig, sizeof(sig));
193 CHECK(ecount2 == 10);
194 CHECK(secp256k1_ecdsa_verify(sign, &sig, ctmp, &pubkey) == 0);
195 CHECK(ecount2 == 11);
196 CHECK(secp256k1_ecdsa_verify(vrfy, &sig, ctmp, &pubkey) == 1);
198 CHECK(secp256k1_ec_pubkey_tweak_add(sign, &pubkey, ctmp) == 0);
199 CHECK(ecount2 == 12);
200 CHECK(secp256k1_ec_pubkey_tweak_add(vrfy, &pubkey, ctmp) == 1);
202 CHECK(secp256k1_ec_pubkey_tweak_mul(sign, &pubkey, ctmp) == 0);
203 CHECK(ecount2 == 13);
204 CHECK(secp256k1_ec_pubkey_tweak_mul(vrfy, &pubkey, ctmp) == 1);
206 CHECK(secp256k1_context_randomize(vrfy, ctmp) == 0);
208 CHECK(secp256k1_context_randomize(sign, NULL) == 1);
209 CHECK(ecount2 == 13);
210 secp256k1_context_set_illegal_callback(vrfy, NULL, NULL);
211 secp256k1_context_set_illegal_callback(sign, NULL, NULL);
213 /* This shouldn't leak memory, due to already-set tests. */
214 secp256k1_ecmult_gen_context_build(&sign->ecmult_gen_ctx, NULL);
215 secp256k1_ecmult_context_build(&vrfy->ecmult_ctx, NULL);
217 /* obtain a working nonce */
219 random_scalar_order_test(&nonce);
220 } while(!secp256k1_ecdsa_sig_sign(&both->ecmult_gen_ctx, &sigr, &sigs, &key, &msg, &nonce, NULL));
223 CHECK(secp256k1_ecdsa_sig_sign(&sign->ecmult_gen_ctx, &sigr, &sigs, &key, &msg, &nonce, NULL));
224 CHECK(secp256k1_ecdsa_sig_sign(&both->ecmult_gen_ctx, &sigr, &sigs, &key, &msg, &nonce, NULL));
227 CHECK(secp256k1_ecdsa_sig_verify(&vrfy->ecmult_ctx, &sigr, &sigs, &pub, &msg));
228 CHECK(secp256k1_ecdsa_sig_verify(&both->ecmult_ctx, &sigr, &sigs, &pub, &msg));
231 secp256k1_context_destroy(none);
232 secp256k1_context_destroy(sign);
233 secp256k1_context_destroy(vrfy);
234 secp256k1_context_destroy(both);
235 /* Defined as no-op. */
236 secp256k1_context_destroy(NULL);
239 /***** HASH TESTS *****/
241 void run_sha256_tests(void) {
242 static const char *inputs[8] = {
243 "", "abc", "message digest", "secure hash algorithm", "SHA256 is considered to be safe",
244 "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
245 "For this sample, this 63-byte string will be used as input data",
246 "This is exactly 64 bytes long, not counting the terminating byte"
248 static const unsigned char outputs[8][32] = {
249 {0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24, 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55},
250 {0xba, 0x78, 0x16, 0xbf, 0x8f, 0x01, 0xcf, 0xea, 0x41, 0x41, 0x40, 0xde, 0x5d, 0xae, 0x22, 0x23, 0xb0, 0x03, 0x61, 0xa3, 0x96, 0x17, 0x7a, 0x9c, 0xb4, 0x10, 0xff, 0x61, 0xf2, 0x00, 0x15, 0xad},
251 {0xf7, 0x84, 0x6f, 0x55, 0xcf, 0x23, 0xe1, 0x4e, 0xeb, 0xea, 0xb5, 0xb4, 0xe1, 0x55, 0x0c, 0xad, 0x5b, 0x50, 0x9e, 0x33, 0x48, 0xfb, 0xc4, 0xef, 0xa3, 0xa1, 0x41, 0x3d, 0x39, 0x3c, 0xb6, 0x50},
252 {0xf3, 0x0c, 0xeb, 0x2b, 0xb2, 0x82, 0x9e, 0x79, 0xe4, 0xca, 0x97, 0x53, 0xd3, 0x5a, 0x8e, 0xcc, 0x00, 0x26, 0x2d, 0x16, 0x4c, 0xc0, 0x77, 0x08, 0x02, 0x95, 0x38, 0x1c, 0xbd, 0x64, 0x3f, 0x0d},
253 {0x68, 0x19, 0xd9, 0x15, 0xc7, 0x3f, 0x4d, 0x1e, 0x77, 0xe4, 0xe1, 0xb5, 0x2d, 0x1f, 0xa0, 0xf9, 0xcf, 0x9b, 0xea, 0xea, 0xd3, 0x93, 0x9f, 0x15, 0x87, 0x4b, 0xd9, 0x88, 0xe2, 0xa2, 0x36, 0x30},
254 {0x24, 0x8d, 0x6a, 0x61, 0xd2, 0x06, 0x38, 0xb8, 0xe5, 0xc0, 0x26, 0x93, 0x0c, 0x3e, 0x60, 0x39, 0xa3, 0x3c, 0xe4, 0x59, 0x64, 0xff, 0x21, 0x67, 0xf6, 0xec, 0xed, 0xd4, 0x19, 0xdb, 0x06, 0xc1},
255 {0xf0, 0x8a, 0x78, 0xcb, 0xba, 0xee, 0x08, 0x2b, 0x05, 0x2a, 0xe0, 0x70, 0x8f, 0x32, 0xfa, 0x1e, 0x50, 0xc5, 0xc4, 0x21, 0xaa, 0x77, 0x2b, 0xa5, 0xdb, 0xb4, 0x06, 0xa2, 0xea, 0x6b, 0xe3, 0x42},
256 {0xab, 0x64, 0xef, 0xf7, 0xe8, 0x8e, 0x2e, 0x46, 0x16, 0x5e, 0x29, 0xf2, 0xbc, 0xe4, 0x18, 0x26, 0xbd, 0x4c, 0x7b, 0x35, 0x52, 0xf6, 0xb3, 0x82, 0xa9, 0xe7, 0xd3, 0xaf, 0x47, 0xc2, 0x45, 0xf8}
259 for (i = 0; i < 8; i++) {
260 unsigned char out[32];
261 secp256k1_sha256_t hasher;
262 secp256k1_sha256_initialize(&hasher);
263 secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i]), strlen(inputs[i]));
264 secp256k1_sha256_finalize(&hasher, out);
265 CHECK(memcmp(out, outputs[i], 32) == 0);
266 if (strlen(inputs[i]) > 0) {
267 int split = secp256k1_rand_int(strlen(inputs[i]));
268 secp256k1_sha256_initialize(&hasher);
269 secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i]), split);
270 secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i] + split), strlen(inputs[i]) - split);
271 secp256k1_sha256_finalize(&hasher, out);
272 CHECK(memcmp(out, outputs[i], 32) == 0);
277 void run_hmac_sha256_tests(void) {
278 static const char *keys[6] = {
279 "\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b",
281 "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa",
282 "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19",
283 "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa",
284 "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa"
286 static const char *inputs[6] = {
287 "\x48\x69\x20\x54\x68\x65\x72\x65",
288 "\x77\x68\x61\x74\x20\x64\x6f\x20\x79\x61\x20\x77\x61\x6e\x74\x20\x66\x6f\x72\x20\x6e\x6f\x74\x68\x69\x6e\x67\x3f",
289 "\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd",
290 "\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd",
291 "\x54\x65\x73\x74\x20\x55\x73\x69\x6e\x67\x20\x4c\x61\x72\x67\x65\x72\x20\x54\x68\x61\x6e\x20\x42\x6c\x6f\x63\x6b\x2d\x53\x69\x7a\x65\x20\x4b\x65\x79\x20\x2d\x20\x48\x61\x73\x68\x20\x4b\x65\x79\x20\x46\x69\x72\x73\x74",
292 "\x54\x68\x69\x73\x20\x69\x73\x20\x61\x20\x74\x65\x73\x74\x20\x75\x73\x69\x6e\x67\x20\x61\x20\x6c\x61\x72\x67\x65\x72\x20\x74\x68\x61\x6e\x20\x62\x6c\x6f\x63\x6b\x2d\x73\x69\x7a\x65\x20\x6b\x65\x79\x20\x61\x6e\x64\x20\x61\x20\x6c\x61\x72\x67\x65\x72\x20\x74\x68\x61\x6e\x20\x62\x6c\x6f\x63\x6b\x2d\x73\x69\x7a\x65\x20\x64\x61\x74\x61\x2e\x20\x54\x68\x65\x20\x6b\x65\x79\x20\x6e\x65\x65\x64\x73\x20\x74\x6f\x20\x62\x65\x20\x68\x61\x73\x68\x65\x64\x20\x62\x65\x66\x6f\x72\x65\x20\x62\x65\x69\x6e\x67\x20\x75\x73\x65\x64\x20\x62\x79\x20\x74\x68\x65\x20\x48\x4d\x41\x43\x20\x61\x6c\x67\x6f\x72\x69\x74\x68\x6d\x2e"
294 static const unsigned char outputs[6][32] = {
295 {0xb0, 0x34, 0x4c, 0x61, 0xd8, 0xdb, 0x38, 0x53, 0x5c, 0xa8, 0xaf, 0xce, 0xaf, 0x0b, 0xf1, 0x2b, 0x88, 0x1d, 0xc2, 0x00, 0xc9, 0x83, 0x3d, 0xa7, 0x26, 0xe9, 0x37, 0x6c, 0x2e, 0x32, 0xcf, 0xf7},
296 {0x5b, 0xdc, 0xc1, 0x46, 0xbf, 0x60, 0x75, 0x4e, 0x6a, 0x04, 0x24, 0x26, 0x08, 0x95, 0x75, 0xc7, 0x5a, 0x00, 0x3f, 0x08, 0x9d, 0x27, 0x39, 0x83, 0x9d, 0xec, 0x58, 0xb9, 0x64, 0xec, 0x38, 0x43},
297 {0x77, 0x3e, 0xa9, 0x1e, 0x36, 0x80, 0x0e, 0x46, 0x85, 0x4d, 0xb8, 0xeb, 0xd0, 0x91, 0x81, 0xa7, 0x29, 0x59, 0x09, 0x8b, 0x3e, 0xf8, 0xc1, 0x22, 0xd9, 0x63, 0x55, 0x14, 0xce, 0xd5, 0x65, 0xfe},
298 {0x82, 0x55, 0x8a, 0x38, 0x9a, 0x44, 0x3c, 0x0e, 0xa4, 0xcc, 0x81, 0x98, 0x99, 0xf2, 0x08, 0x3a, 0x85, 0xf0, 0xfa, 0xa3, 0xe5, 0x78, 0xf8, 0x07, 0x7a, 0x2e, 0x3f, 0xf4, 0x67, 0x29, 0x66, 0x5b},
299 {0x60, 0xe4, 0x31, 0x59, 0x1e, 0xe0, 0xb6, 0x7f, 0x0d, 0x8a, 0x26, 0xaa, 0xcb, 0xf5, 0xb7, 0x7f, 0x8e, 0x0b, 0xc6, 0x21, 0x37, 0x28, 0xc5, 0x14, 0x05, 0x46, 0x04, 0x0f, 0x0e, 0xe3, 0x7f, 0x54},
300 {0x9b, 0x09, 0xff, 0xa7, 0x1b, 0x94, 0x2f, 0xcb, 0x27, 0x63, 0x5f, 0xbc, 0xd5, 0xb0, 0xe9, 0x44, 0xbf, 0xdc, 0x63, 0x64, 0x4f, 0x07, 0x13, 0x93, 0x8a, 0x7f, 0x51, 0x53, 0x5c, 0x3a, 0x35, 0xe2}
303 for (i = 0; i < 6; i++) {
304 secp256k1_hmac_sha256_t hasher;
305 unsigned char out[32];
306 secp256k1_hmac_sha256_initialize(&hasher, (const unsigned char*)(keys[i]), strlen(keys[i]));
307 secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i]), strlen(inputs[i]));
308 secp256k1_hmac_sha256_finalize(&hasher, out);
309 CHECK(memcmp(out, outputs[i], 32) == 0);
310 if (strlen(inputs[i]) > 0) {
311 int split = secp256k1_rand_int(strlen(inputs[i]));
312 secp256k1_hmac_sha256_initialize(&hasher, (const unsigned char*)(keys[i]), strlen(keys[i]));
313 secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i]), split);
314 secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i] + split), strlen(inputs[i]) - split);
315 secp256k1_hmac_sha256_finalize(&hasher, out);
316 CHECK(memcmp(out, outputs[i], 32) == 0);
321 void run_rfc6979_hmac_sha256_tests(void) {
322 static const unsigned char key1[65] = {0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x00, 0x4b, 0xf5, 0x12, 0x2f, 0x34, 0x45, 0x54, 0xc5, 0x3b, 0xde, 0x2e, 0xbb, 0x8c, 0xd2, 0xb7, 0xe3, 0xd1, 0x60, 0x0a, 0xd6, 0x31, 0xc3, 0x85, 0xa5, 0xd7, 0xcc, 0xe2, 0x3c, 0x77, 0x85, 0x45, 0x9a, 0};
323 static const unsigned char out1[3][32] = {
324 {0x4f, 0xe2, 0x95, 0x25, 0xb2, 0x08, 0x68, 0x09, 0x15, 0x9a, 0xcd, 0xf0, 0x50, 0x6e, 0xfb, 0x86, 0xb0, 0xec, 0x93, 0x2c, 0x7b, 0xa4, 0x42, 0x56, 0xab, 0x32, 0x1e, 0x42, 0x1e, 0x67, 0xe9, 0xfb},
325 {0x2b, 0xf0, 0xff, 0xf1, 0xd3, 0xc3, 0x78, 0xa2, 0x2d, 0xc5, 0xde, 0x1d, 0x85, 0x65, 0x22, 0x32, 0x5c, 0x65, 0xb5, 0x04, 0x49, 0x1a, 0x0c, 0xbd, 0x01, 0xcb, 0x8f, 0x3a, 0xa6, 0x7f, 0xfd, 0x4a},
326 {0xf5, 0x28, 0xb4, 0x10, 0xcb, 0x54, 0x1f, 0x77, 0x00, 0x0d, 0x7a, 0xfb, 0x6c, 0x5b, 0x53, 0xc5, 0xc4, 0x71, 0xea, 0xb4, 0x3e, 0x46, 0x6d, 0x9a, 0xc5, 0x19, 0x0c, 0x39, 0xc8, 0x2f, 0xd8, 0x2e}
329 static const unsigned char key2[64] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24, 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55};
330 static const unsigned char out2[3][32] = {
331 {0x9c, 0x23, 0x6c, 0x16, 0x5b, 0x82, 0xae, 0x0c, 0xd5, 0x90, 0x65, 0x9e, 0x10, 0x0b, 0x6b, 0xab, 0x30, 0x36, 0xe7, 0xba, 0x8b, 0x06, 0x74, 0x9b, 0xaf, 0x69, 0x81, 0xe1, 0x6f, 0x1a, 0x2b, 0x95},
332 {0xdf, 0x47, 0x10, 0x61, 0x62, 0x5b, 0xc0, 0xea, 0x14, 0xb6, 0x82, 0xfe, 0xee, 0x2c, 0x9c, 0x02, 0xf2, 0x35, 0xda, 0x04, 0x20, 0x4c, 0x1d, 0x62, 0xa1, 0x53, 0x6c, 0x6e, 0x17, 0xae, 0xd7, 0xa9},
333 {0x75, 0x97, 0x88, 0x7c, 0xbd, 0x76, 0x32, 0x1f, 0x32, 0xe3, 0x04, 0x40, 0x67, 0x9a, 0x22, 0xcf, 0x7f, 0x8d, 0x9d, 0x2e, 0xac, 0x39, 0x0e, 0x58, 0x1f, 0xea, 0x09, 0x1c, 0xe2, 0x02, 0xba, 0x94}
336 secp256k1_rfc6979_hmac_sha256_t rng;
337 unsigned char out[32];
340 secp256k1_rfc6979_hmac_sha256_initialize(&rng, key1, 64);
341 for (i = 0; i < 3; i++) {
342 secp256k1_rfc6979_hmac_sha256_generate(&rng, out, 32);
343 CHECK(memcmp(out, out1[i], 32) == 0);
345 secp256k1_rfc6979_hmac_sha256_finalize(&rng);
347 secp256k1_rfc6979_hmac_sha256_initialize(&rng, key1, 65);
348 for (i = 0; i < 3; i++) {
349 secp256k1_rfc6979_hmac_sha256_generate(&rng, out, 32);
350 CHECK(memcmp(out, out1[i], 32) != 0);
352 secp256k1_rfc6979_hmac_sha256_finalize(&rng);
354 secp256k1_rfc6979_hmac_sha256_initialize(&rng, key2, 64);
355 for (i = 0; i < 3; i++) {
356 secp256k1_rfc6979_hmac_sha256_generate(&rng, out, 32);
357 CHECK(memcmp(out, out2[i], 32) == 0);
359 secp256k1_rfc6979_hmac_sha256_finalize(&rng);
362 /***** RANDOM TESTS *****/
364 void test_rand_bits(int rand32, int bits) {
365 /* (1-1/2^B)^rounds[B] < 1/10^9, so rounds is the number of iterations to
366 * get a false negative chance below once in a billion */
367 static const unsigned int rounds[7] = {1, 30, 73, 156, 322, 653, 1316};
368 /* We try multiplying the results with various odd numbers, which shouldn't
369 * influence the uniform distribution modulo a power of 2. */
370 static const uint32_t mults[6] = {1, 3, 21, 289, 0x9999, 0x80402011};
371 /* We only select up to 6 bits from the output to analyse */
372 unsigned int usebits = bits > 6 ? 6 : bits;
373 unsigned int maxshift = bits - usebits;
374 /* For each of the maxshift+1 usebits-bit sequences inside a bits-bit
375 number, track all observed outcomes, one per bit in a uint64_t. */
376 uint64_t x[6][27] = {{0}};
377 unsigned int i, shift, m;
378 /* Multiply the output of all rand calls with the odd number m, which
379 should not change the uniformity of its distribution. */
380 for (i = 0; i < rounds[usebits]; i++) {
381 uint32_t r = (rand32 ? secp256k1_rand32() : secp256k1_rand_bits(bits));
382 CHECK((((uint64_t)r) >> bits) == 0);
383 for (m = 0; m < sizeof(mults) / sizeof(mults[0]); m++) {
384 uint32_t rm = r * mults[m];
385 for (shift = 0; shift <= maxshift; shift++) {
386 x[m][shift] |= (((uint64_t)1) << ((rm >> shift) & ((1 << usebits) - 1)));
390 for (m = 0; m < sizeof(mults) / sizeof(mults[0]); m++) {
391 for (shift = 0; shift <= maxshift; shift++) {
392 /* Test that the lower usebits bits of x[shift] are 1 */
393 CHECK(((~x[m][shift]) << (64 - (1 << usebits))) == 0);
398 /* Subrange must be a whole divisor of range, and at most 64 */
399 void test_rand_int(uint32_t range, uint32_t subrange) {
400 /* (1-1/subrange)^rounds < 1/10^9 */
401 int rounds = (subrange * 2073) / 100;
404 CHECK((range % subrange) == 0);
405 for (i = 0; i < rounds; i++) {
406 uint32_t r = secp256k1_rand_int(range);
409 x |= (((uint64_t)1) << r);
411 /* Test that the lower subrange bits of x are 1. */
412 CHECK(((~x) << (64 - subrange)) == 0);
415 void run_rand_bits(void) {
417 test_rand_bits(1, 32);
418 for (b = 1; b <= 32; b++) {
419 test_rand_bits(0, b);
423 void run_rand_int(void) {
424 static const uint32_t ms[] = {1, 3, 17, 1000, 13771, 999999, 33554432};
425 static const uint32_t ss[] = {1, 3, 6, 9, 13, 31, 64};
427 for (m = 0; m < sizeof(ms) / sizeof(ms[0]); m++) {
428 for (s = 0; s < sizeof(ss) / sizeof(ss[0]); s++) {
429 test_rand_int(ms[m] * ss[s], ss[s]);
434 /***** NUM TESTS *****/
437 void random_num_negate(secp256k1_num *num) {
438 if (secp256k1_rand_bits(1)) {
439 secp256k1_num_negate(num);
443 void random_num_order_test(secp256k1_num *num) {
445 random_scalar_order_test(&sc);
446 secp256k1_scalar_get_num(num, &sc);
449 void random_num_order(secp256k1_num *num) {
451 random_scalar_order(&sc);
452 secp256k1_scalar_get_num(num, &sc);
455 void test_num_negate(void) {
458 random_num_order_test(&n1); /* n1 = R */
459 random_num_negate(&n1);
460 secp256k1_num_copy(&n2, &n1); /* n2 = R */
461 secp256k1_num_sub(&n1, &n2, &n1); /* n1 = n2-n1 = 0 */
462 CHECK(secp256k1_num_is_zero(&n1));
463 secp256k1_num_copy(&n1, &n2); /* n1 = R */
464 secp256k1_num_negate(&n1); /* n1 = -R */
465 CHECK(!secp256k1_num_is_zero(&n1));
466 secp256k1_num_add(&n1, &n2, &n1); /* n1 = n2+n1 = 0 */
467 CHECK(secp256k1_num_is_zero(&n1));
468 secp256k1_num_copy(&n1, &n2); /* n1 = R */
469 secp256k1_num_negate(&n1); /* n1 = -R */
470 CHECK(secp256k1_num_is_neg(&n1) != secp256k1_num_is_neg(&n2));
471 secp256k1_num_negate(&n1); /* n1 = R */
472 CHECK(secp256k1_num_eq(&n1, &n2));
475 void test_num_add_sub(void) {
478 secp256k1_num n1p2, n2p1, n1m2, n2m1;
479 random_num_order_test(&n1); /* n1 = R1 */
480 if (secp256k1_rand_bits(1)) {
481 random_num_negate(&n1);
483 random_num_order_test(&n2); /* n2 = R2 */
484 if (secp256k1_rand_bits(1)) {
485 random_num_negate(&n2);
487 secp256k1_num_add(&n1p2, &n1, &n2); /* n1p2 = R1 + R2 */
488 secp256k1_num_add(&n2p1, &n2, &n1); /* n2p1 = R2 + R1 */
489 secp256k1_num_sub(&n1m2, &n1, &n2); /* n1m2 = R1 - R2 */
490 secp256k1_num_sub(&n2m1, &n2, &n1); /* n2m1 = R2 - R1 */
491 CHECK(secp256k1_num_eq(&n1p2, &n2p1));
492 CHECK(!secp256k1_num_eq(&n1p2, &n1m2));
493 secp256k1_num_negate(&n2m1); /* n2m1 = -R2 + R1 */
494 CHECK(secp256k1_num_eq(&n2m1, &n1m2));
495 CHECK(!secp256k1_num_eq(&n2m1, &n1));
496 secp256k1_num_add(&n2m1, &n2m1, &n2); /* n2m1 = -R2 + R1 + R2 = R1 */
497 CHECK(secp256k1_num_eq(&n2m1, &n1));
498 CHECK(!secp256k1_num_eq(&n2p1, &n1));
499 secp256k1_num_sub(&n2p1, &n2p1, &n2); /* n2p1 = R2 + R1 - R2 = R1 */
500 CHECK(secp256k1_num_eq(&n2p1, &n1));
503 void run_num_smalltests(void) {
505 for (i = 0; i < 100*count; i++) {
512 /***** SCALAR TESTS *****/
514 void scalar_test(void) {
519 secp256k1_num snum, s1num, s2num;
520 secp256k1_num order, half_order;
524 /* Set 's' to a random scalar, with value 'snum'. */
525 random_scalar_order_test(&s);
527 /* Set 's1' to a random scalar, with value 's1num'. */
528 random_scalar_order_test(&s1);
530 /* Set 's2' to a random scalar, with value 'snum2', and byte array representation 'c'. */
531 random_scalar_order_test(&s2);
532 secp256k1_scalar_get_b32(c, &s2);
535 secp256k1_scalar_get_num(&snum, &s);
536 secp256k1_scalar_get_num(&s1num, &s1);
537 secp256k1_scalar_get_num(&s2num, &s2);
539 secp256k1_scalar_order_get_num(&order);
541 secp256k1_num_shift(&half_order, 1);
546 /* Test that fetching groups of 4 bits from a scalar and recursing n(i)=16*n(i-1)+p(i) reconstructs it. */
548 secp256k1_scalar_set_int(&n, 0);
549 for (i = 0; i < 256; i += 4) {
552 secp256k1_scalar_set_int(&t, secp256k1_scalar_get_bits(&s, 256 - 4 - i, 4));
553 for (j = 0; j < 4; j++) {
554 secp256k1_scalar_add(&n, &n, &n);
556 secp256k1_scalar_add(&n, &n, &t);
558 CHECK(secp256k1_scalar_eq(&n, &s));
562 /* Test that fetching groups of randomly-sized bits from a scalar and recursing n(i)=b*n(i-1)+p(i) reconstructs it. */
565 secp256k1_scalar_set_int(&n, 0);
569 int now = secp256k1_rand_int(15) + 1;
573 secp256k1_scalar_set_int(&t, secp256k1_scalar_get_bits_var(&s, 256 - now - i, now));
574 for (j = 0; j < now; j++) {
575 secp256k1_scalar_add(&n, &n, &n);
577 secp256k1_scalar_add(&n, &n, &t);
580 CHECK(secp256k1_scalar_eq(&n, &s));
585 /* Test that adding the scalars together is equal to adding their numbers together modulo the order. */
589 secp256k1_num_add(&rnum, &snum, &s2num);
590 secp256k1_num_mod(&rnum, &order);
591 secp256k1_scalar_add(&r, &s, &s2);
592 secp256k1_scalar_get_num(&r2num, &r);
593 CHECK(secp256k1_num_eq(&rnum, &r2num));
597 /* Test that multiplying the scalars is equal to multiplying their numbers modulo the order. */
601 secp256k1_num_mul(&rnum, &snum, &s2num);
602 secp256k1_num_mod(&rnum, &order);
603 secp256k1_scalar_mul(&r, &s, &s2);
604 secp256k1_scalar_get_num(&r2num, &r);
605 CHECK(secp256k1_num_eq(&rnum, &r2num));
606 /* The result can only be zero if at least one of the factors was zero. */
607 CHECK(secp256k1_scalar_is_zero(&r) == (secp256k1_scalar_is_zero(&s) || secp256k1_scalar_is_zero(&s2)));
608 /* The results can only be equal to one of the factors if that factor was zero, or the other factor was one. */
609 CHECK(secp256k1_num_eq(&rnum, &snum) == (secp256k1_scalar_is_zero(&s) || secp256k1_scalar_is_one(&s2)));
610 CHECK(secp256k1_num_eq(&rnum, &s2num) == (secp256k1_scalar_is_zero(&s2) || secp256k1_scalar_is_one(&s)));
614 secp256k1_scalar neg;
615 secp256k1_num negnum;
616 secp256k1_num negnum2;
617 /* Check that comparison with zero matches comparison with zero on the number. */
618 CHECK(secp256k1_num_is_zero(&snum) == secp256k1_scalar_is_zero(&s));
619 /* Check that comparison with the half order is equal to testing for high scalar. */
620 CHECK(secp256k1_scalar_is_high(&s) == (secp256k1_num_cmp(&snum, &half_order) > 0));
621 secp256k1_scalar_negate(&neg, &s);
622 secp256k1_num_sub(&negnum, &order, &snum);
623 secp256k1_num_mod(&negnum, &order);
624 /* Check that comparison with the half order is equal to testing for high scalar after negation. */
625 CHECK(secp256k1_scalar_is_high(&neg) == (secp256k1_num_cmp(&negnum, &half_order) > 0));
626 /* Negating should change the high property, unless the value was already zero. */
627 CHECK((secp256k1_scalar_is_high(&s) == secp256k1_scalar_is_high(&neg)) == secp256k1_scalar_is_zero(&s));
628 secp256k1_scalar_get_num(&negnum2, &neg);
629 /* Negating a scalar should be equal to (order - n) mod order on the number. */
630 CHECK(secp256k1_num_eq(&negnum, &negnum2));
631 secp256k1_scalar_add(&neg, &neg, &s);
632 /* Adding a number to its negation should result in zero. */
633 CHECK(secp256k1_scalar_is_zero(&neg));
634 secp256k1_scalar_negate(&neg, &neg);
635 /* Negating zero should still result in zero. */
636 CHECK(secp256k1_scalar_is_zero(&neg));
640 /* Test secp256k1_scalar_mul_shift_var. */
645 unsigned char cone[1] = {0x01};
646 unsigned int shift = 256 + secp256k1_rand_int(257);
647 secp256k1_scalar_mul_shift_var(&r, &s1, &s2, shift);
648 secp256k1_num_mul(&rnum, &s1num, &s2num);
649 secp256k1_num_shift(&rnum, shift - 1);
650 secp256k1_num_set_bin(&one, cone, 1);
651 secp256k1_num_add(&rnum, &rnum, &one);
652 secp256k1_num_shift(&rnum, 1);
653 secp256k1_scalar_get_num(&rnum2, &r);
654 CHECK(secp256k1_num_eq(&rnum, &rnum2));
658 /* test secp256k1_scalar_shr_int */
661 random_scalar_order_test(&r);
662 for (i = 0; i < 100; ++i) {
664 int shift = 1 + secp256k1_rand_int(15);
665 int expected = r.d[0] % (1 << shift);
666 low = secp256k1_scalar_shr_int(&r, shift);
667 CHECK(expected == low);
673 /* Test that scalar inverses are equal to the inverse of their number modulo the order. */
674 if (!secp256k1_scalar_is_zero(&s)) {
675 secp256k1_scalar inv;
677 secp256k1_num invnum;
678 secp256k1_num invnum2;
680 secp256k1_scalar_inverse(&inv, &s);
682 secp256k1_num_mod_inverse(&invnum, &snum, &order);
683 secp256k1_scalar_get_num(&invnum2, &inv);
684 CHECK(secp256k1_num_eq(&invnum, &invnum2));
686 secp256k1_scalar_mul(&inv, &inv, &s);
687 /* Multiplying a scalar with its inverse must result in one. */
688 CHECK(secp256k1_scalar_is_one(&inv));
689 secp256k1_scalar_inverse(&inv, &inv);
690 /* Inverting one must result in one. */
691 CHECK(secp256k1_scalar_is_one(&inv));
696 /* Test commutativity of add. */
697 secp256k1_scalar r1, r2;
698 secp256k1_scalar_add(&r1, &s1, &s2);
699 secp256k1_scalar_add(&r2, &s2, &s1);
700 CHECK(secp256k1_scalar_eq(&r1, &r2));
704 secp256k1_scalar r1, r2;
708 int bit = secp256k1_rand_bits(8);
709 secp256k1_scalar_set_int(&b, 1);
710 CHECK(secp256k1_scalar_is_one(&b));
711 for (i = 0; i < bit; i++) {
712 secp256k1_scalar_add(&b, &b, &b);
716 if (!secp256k1_scalar_add(&r1, &r1, &b)) {
717 /* No overflow happened. */
718 secp256k1_scalar_cadd_bit(&r2, bit, 1);
719 CHECK(secp256k1_scalar_eq(&r1, &r2));
720 /* cadd is a noop when flag is zero */
721 secp256k1_scalar_cadd_bit(&r2, bit, 0);
722 CHECK(secp256k1_scalar_eq(&r1, &r2));
727 /* Test commutativity of mul. */
728 secp256k1_scalar r1, r2;
729 secp256k1_scalar_mul(&r1, &s1, &s2);
730 secp256k1_scalar_mul(&r2, &s2, &s1);
731 CHECK(secp256k1_scalar_eq(&r1, &r2));
735 /* Test associativity of add. */
736 secp256k1_scalar r1, r2;
737 secp256k1_scalar_add(&r1, &s1, &s2);
738 secp256k1_scalar_add(&r1, &r1, &s);
739 secp256k1_scalar_add(&r2, &s2, &s);
740 secp256k1_scalar_add(&r2, &s1, &r2);
741 CHECK(secp256k1_scalar_eq(&r1, &r2));
745 /* Test associativity of mul. */
746 secp256k1_scalar r1, r2;
747 secp256k1_scalar_mul(&r1, &s1, &s2);
748 secp256k1_scalar_mul(&r1, &r1, &s);
749 secp256k1_scalar_mul(&r2, &s2, &s);
750 secp256k1_scalar_mul(&r2, &s1, &r2);
751 CHECK(secp256k1_scalar_eq(&r1, &r2));
755 /* Test distributitivity of mul over add. */
756 secp256k1_scalar r1, r2, t;
757 secp256k1_scalar_add(&r1, &s1, &s2);
758 secp256k1_scalar_mul(&r1, &r1, &s);
759 secp256k1_scalar_mul(&r2, &s1, &s);
760 secp256k1_scalar_mul(&t, &s2, &s);
761 secp256k1_scalar_add(&r2, &r2, &t);
762 CHECK(secp256k1_scalar_eq(&r1, &r2));
767 secp256k1_scalar r1, r2;
768 secp256k1_scalar_sqr(&r1, &s1);
769 secp256k1_scalar_mul(&r2, &s1, &s1);
770 CHECK(secp256k1_scalar_eq(&r1, &r2));
774 /* Test multiplicative identity. */
775 secp256k1_scalar r1, v1;
776 secp256k1_scalar_set_int(&v1,1);
777 secp256k1_scalar_mul(&r1, &s1, &v1);
778 CHECK(secp256k1_scalar_eq(&r1, &s1));
782 /* Test additive identity. */
783 secp256k1_scalar r1, v0;
784 secp256k1_scalar_set_int(&v0,0);
785 secp256k1_scalar_add(&r1, &s1, &v0);
786 CHECK(secp256k1_scalar_eq(&r1, &s1));
790 /* Test zero product property. */
791 secp256k1_scalar r1, v0;
792 secp256k1_scalar_set_int(&v0,0);
793 secp256k1_scalar_mul(&r1, &s1, &v0);
794 CHECK(secp256k1_scalar_eq(&r1, &v0));
799 void run_scalar_tests(void) {
801 for (i = 0; i < 128 * count; i++) {
806 /* (-1)+1 should be zero. */
807 secp256k1_scalar s, o;
808 secp256k1_scalar_set_int(&s, 1);
809 CHECK(secp256k1_scalar_is_one(&s));
810 secp256k1_scalar_negate(&o, &s);
811 secp256k1_scalar_add(&o, &o, &s);
812 CHECK(secp256k1_scalar_is_zero(&o));
813 secp256k1_scalar_negate(&o, &o);
814 CHECK(secp256k1_scalar_is_zero(&o));
819 /* A scalar with value of the curve order should be 0. */
821 secp256k1_scalar zero;
822 unsigned char bin[32];
824 secp256k1_scalar_order_get_num(&order);
825 secp256k1_num_get_bin(bin, 32, &order);
826 secp256k1_scalar_set_b32(&zero, bin, &overflow);
827 CHECK(overflow == 1);
828 CHECK(secp256k1_scalar_is_zero(&zero));
833 /* Does check_overflow check catch all ones? */
834 static const secp256k1_scalar overflowed = SECP256K1_SCALAR_CONST(
835 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL,
836 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL
838 CHECK(secp256k1_scalar_check_overflow(&overflowed));
842 /* Static test vectors.
843 * These were reduced from ~10^12 random vectors based on comparison-decision
844 * and edge-case coverage on 32-bit and 64-bit implementations.
845 * The responses were generated with Sage 5.9.
851 secp256k1_scalar one;
854 #if defined(USE_SCALAR_INV_NUM)
855 secp256k1_scalar zzv;
858 unsigned char chal[32][2][32] = {
859 {{0xff, 0xff, 0x03, 0x07, 0x00, 0x00, 0x00, 0x00,
860 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x03,
861 0x00, 0x00, 0x00, 0x00, 0x00, 0xf8, 0xff, 0xff,
862 0xff, 0xff, 0x03, 0x00, 0xc0, 0xff, 0xff, 0xff},
863 {0xff, 0xff, 0xff, 0xff, 0xff, 0x0f, 0x00, 0x00,
864 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xf8,
865 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
866 0xff, 0x03, 0x00, 0x00, 0x00, 0x00, 0xe0, 0xff}},
867 {{0xef, 0xff, 0x1f, 0x00, 0x00, 0x00, 0x00, 0x00,
868 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f, 0x00,
869 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
870 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00},
871 {0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
872 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xe0,
873 0xff, 0xff, 0xff, 0xff, 0xfc, 0xff, 0xff, 0xff,
874 0xff, 0xff, 0xff, 0xff, 0x7f, 0x00, 0x80, 0xff}},
875 {{0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
876 0x00, 0x00, 0x00, 0x00, 0x00, 0x06, 0x00, 0x00,
877 0x80, 0x00, 0x00, 0x80, 0xff, 0x3f, 0x00, 0x00,
878 0x00, 0x00, 0x00, 0xf8, 0xff, 0xff, 0xff, 0x00},
879 {0x00, 0x00, 0xfc, 0xff, 0xff, 0xff, 0xff, 0x80,
880 0xff, 0xff, 0xff, 0xff, 0xff, 0x0f, 0x00, 0xe0,
881 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f, 0x00, 0x00,
882 0x00, 0x00, 0x00, 0x00, 0x7f, 0xff, 0xff, 0xff}},
883 {{0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
884 0x00, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x80,
885 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
886 0x00, 0x1e, 0xf8, 0xff, 0xff, 0xff, 0xfd, 0xff},
887 {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x1f,
888 0x00, 0x00, 0x00, 0xf8, 0xff, 0x03, 0x00, 0xe0,
889 0xff, 0x0f, 0x00, 0x00, 0x00, 0x00, 0xf0, 0xff,
890 0xf3, 0xff, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00}},
891 {{0x80, 0x00, 0x00, 0x80, 0xff, 0xff, 0xff, 0x00,
892 0x00, 0x1c, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff,
893 0xff, 0xff, 0xff, 0xe0, 0xff, 0xff, 0xff, 0x00,
894 0x00, 0x00, 0x00, 0x00, 0xe0, 0xff, 0xff, 0xff},
895 {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x03, 0x00,
896 0xf8, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
897 0xff, 0x1f, 0x00, 0x00, 0x80, 0xff, 0xff, 0x3f,
898 0x00, 0xfe, 0xff, 0xff, 0xff, 0xdf, 0xff, 0xff}},
899 {{0xff, 0xff, 0xff, 0xff, 0x00, 0x0f, 0xfc, 0x9f,
900 0xff, 0xff, 0xff, 0x00, 0x80, 0x00, 0x00, 0x80,
901 0xff, 0x0f, 0xfc, 0xff, 0x7f, 0x00, 0x00, 0x00,
902 0x00, 0xf8, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00},
903 {0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80,
904 0x00, 0x00, 0xf8, 0xff, 0x0f, 0xc0, 0xff, 0xff,
905 0xff, 0x1f, 0x00, 0x00, 0x00, 0xc0, 0xff, 0xff,
906 0xff, 0xff, 0xff, 0x07, 0x80, 0xff, 0xff, 0xff}},
907 {{0xff, 0xff, 0xff, 0xff, 0xff, 0x3f, 0x00, 0x00,
908 0x80, 0x00, 0x00, 0x80, 0xff, 0xff, 0xff, 0xff,
909 0xf7, 0xff, 0xff, 0xef, 0xff, 0xff, 0xff, 0x00,
910 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0xf0},
911 {0x00, 0x00, 0x00, 0x00, 0xf8, 0xff, 0xff, 0xff,
912 0xff, 0xff, 0xff, 0xff, 0x01, 0x00, 0x00, 0x00,
913 0x00, 0x00, 0x80, 0xff, 0xff, 0xff, 0xff, 0xff,
914 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}},
915 {{0x00, 0xf8, 0xff, 0x03, 0xff, 0xff, 0xff, 0x00,
916 0x00, 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
917 0x80, 0x00, 0x00, 0x80, 0xff, 0xff, 0xff, 0xff,
918 0xff, 0xff, 0x03, 0xc0, 0xff, 0x0f, 0xfc, 0xff},
919 {0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0xff, 0xff,
920 0xff, 0x01, 0x00, 0x00, 0x00, 0x3f, 0x00, 0xc0,
921 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
922 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}},
923 {{0x8f, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
924 0x00, 0x00, 0xf8, 0xff, 0xff, 0xff, 0xff, 0xff,
925 0xff, 0x7f, 0x00, 0x00, 0x80, 0x00, 0x00, 0x80,
926 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00},
927 {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
928 0xff, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
929 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
930 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}},
931 {{0x00, 0x00, 0x00, 0xc0, 0xff, 0xff, 0xff, 0xff,
932 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
933 0xff, 0xff, 0x03, 0x00, 0x80, 0x00, 0x00, 0x80,
934 0xff, 0xff, 0xff, 0x00, 0x00, 0x80, 0xff, 0x7f},
935 {0xff, 0xcf, 0xff, 0xff, 0x01, 0x00, 0x00, 0x00,
936 0x00, 0xc0, 0xff, 0xcf, 0xff, 0xff, 0xff, 0xff,
937 0xbf, 0xff, 0x0e, 0x00, 0x00, 0x00, 0x00, 0x00,
938 0x80, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00}},
939 {{0x00, 0x00, 0x00, 0x00, 0x00, 0x80, 0xff, 0xff,
940 0xff, 0xff, 0x00, 0xfc, 0xff, 0xff, 0xff, 0xff,
941 0xff, 0xff, 0xff, 0x00, 0x80, 0x00, 0x00, 0x80,
942 0xff, 0x01, 0xfc, 0xff, 0x01, 0x00, 0xfe, 0xff},
943 {0xff, 0xff, 0xff, 0x03, 0x00, 0x00, 0x00, 0x00,
944 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
945 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xc0,
946 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x03, 0x00}},
947 {{0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
948 0xe0, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
949 0x00, 0xf8, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
950 0x7f, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x80},
951 {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
952 0x00, 0xf8, 0xff, 0x01, 0x00, 0xf0, 0xff, 0xff,
953 0xe0, 0xff, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x00,
954 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}},
955 {{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
956 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
957 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
958 0x00, 0x00, 0x00, 0x00, 0x00, 0xf8, 0xff, 0x00},
959 {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00,
960 0xfc, 0xff, 0xff, 0x3f, 0xf0, 0xff, 0xff, 0x3f,
961 0x00, 0x00, 0xf8, 0x07, 0x00, 0x00, 0x00, 0xff,
962 0xff, 0xff, 0xff, 0xff, 0x0f, 0x7e, 0x00, 0x00}},
963 {{0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
964 0x00, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x80,
965 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
966 0xff, 0xff, 0x1f, 0x00, 0x00, 0xfe, 0x07, 0x00},
967 {0x00, 0x00, 0x00, 0xf0, 0xff, 0xff, 0xff, 0xff,
968 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
969 0xff, 0xfb, 0xff, 0x07, 0x00, 0x00, 0x00, 0x00,
970 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x60}},
971 {{0xff, 0x01, 0x00, 0xff, 0xff, 0xff, 0x0f, 0x00,
972 0x80, 0x7f, 0xfe, 0xff, 0xff, 0xff, 0xff, 0x03,
973 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
974 0x00, 0x80, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff},
975 {0xff, 0xff, 0x1f, 0x00, 0xf0, 0xff, 0xff, 0xff,
976 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
977 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
978 0xff, 0xff, 0xff, 0x3f, 0x00, 0x00, 0x00, 0x00}},
979 {{0x80, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
980 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
981 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
982 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff},
983 {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
984 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xf1, 0xff,
985 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x03,
986 0x00, 0x00, 0x00, 0xe0, 0xff, 0xff, 0xff, 0xff}},
987 {{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
988 0x7e, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
989 0xc0, 0xff, 0xff, 0xcf, 0xff, 0x1f, 0x00, 0x00,
990 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80},
991 {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
992 0x00, 0x00, 0x00, 0x00, 0x00, 0xe0, 0xff, 0xff,
993 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f, 0x00, 0x7e,
994 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}},
995 {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
996 0x00, 0x00, 0x00, 0xfc, 0xff, 0xff, 0xff, 0xff,
997 0xff, 0xff, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00,
998 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x7c, 0x00},
999 {0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80,
1000 0xff, 0xff, 0x7f, 0x00, 0x80, 0x00, 0x00, 0x00,
1001 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
1002 0x00, 0x00, 0xe0, 0xff, 0xff, 0xff, 0xff, 0xff}},
1003 {{0xff, 0xff, 0xff, 0xff, 0xff, 0x1f, 0x00, 0x80,
1004 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
1005 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80,
1006 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00},
1007 {0xf0, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1008 0xff, 0xff, 0xff, 0xff, 0x3f, 0x00, 0x00, 0x80,
1009 0xff, 0x01, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff,
1010 0xff, 0x7f, 0xf8, 0xff, 0xff, 0x1f, 0x00, 0xfe}},
1011 {{0xff, 0xff, 0xff, 0x3f, 0xf8, 0xff, 0xff, 0xff,
1012 0xff, 0x03, 0xfe, 0x01, 0x00, 0x00, 0x00, 0x00,
1013 0xf0, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1014 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x07},
1015 {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
1016 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80,
1017 0xff, 0xff, 0xff, 0xff, 0x01, 0x80, 0xff, 0xff,
1018 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00}},
1019 {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1020 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1021 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1022 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00},
1023 {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1024 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
1025 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
1026 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x40}},
1027 {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1028 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1029 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1030 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01},
1031 {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1032 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1033 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1034 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}},
1035 {{0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1036 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1037 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1038 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff},
1039 {0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1040 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1041 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1042 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}},
1043 {{0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0xc0,
1044 0xff, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1045 0x00, 0x00, 0xf0, 0xff, 0xff, 0xff, 0xff, 0xff,
1046 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f},
1047 {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01, 0x00,
1048 0xf0, 0xff, 0xff, 0xff, 0xff, 0x07, 0x00, 0x00,
1049 0x00, 0x00, 0x00, 0xfe, 0xff, 0xff, 0xff, 0xff,
1050 0xff, 0xff, 0xff, 0xff, 0x01, 0xff, 0xff, 0xff}},
1051 {{0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1052 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1053 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1054 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff},
1055 {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1056 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1057 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1058 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02}},
1059 {{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1060 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
1061 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
1062 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x40},
1063 {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1064 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1065 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1066 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01}},
1067 {{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1068 0x7e, 0x00, 0x00, 0xc0, 0xff, 0xff, 0x07, 0x00,
1069 0x80, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x00,
1070 0xfc, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff},
1071 {0xff, 0x01, 0x00, 0x00, 0x00, 0xe0, 0xff, 0xff,
1072 0xff, 0xff, 0xff, 0xff, 0xff, 0x1f, 0x00, 0x80,
1073 0xff, 0xff, 0xff, 0xff, 0xff, 0x03, 0x00, 0x00,
1074 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}},
1075 {{0xff, 0xff, 0xf0, 0xff, 0xff, 0xff, 0xff, 0x00,
1076 0xf0, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
1077 0x00, 0xe0, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01,
1078 0x80, 0x00, 0x00, 0x80, 0xff, 0xff, 0xff, 0xff},
1079 {0x00, 0x00, 0x00, 0x00, 0x00, 0xe0, 0xff, 0xff,
1080 0xff, 0xff, 0x3f, 0x00, 0xf8, 0xff, 0xff, 0xff,
1081 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1082 0xff, 0x3f, 0x00, 0x00, 0xc0, 0xf1, 0x7f, 0x00}},
1083 {{0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
1084 0x00, 0x00, 0x00, 0xc0, 0xff, 0xff, 0xff, 0xff,
1085 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
1086 0x80, 0x00, 0x00, 0x80, 0xff, 0xff, 0xff, 0x00},
1087 {0x00, 0xf8, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01,
1088 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xf8, 0xff,
1089 0xff, 0x7f, 0x00, 0x00, 0x00, 0x00, 0x80, 0x1f,
1090 0x00, 0x00, 0xfc, 0xff, 0xff, 0x01, 0xff, 0xff}},
1091 {{0x00, 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
1092 0x80, 0x00, 0x00, 0x80, 0xff, 0x03, 0xe0, 0x01,
1093 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0xfc, 0xff,
1094 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00},
1095 {0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
1096 0xfe, 0xff, 0xff, 0xf0, 0x07, 0x00, 0x3c, 0x80,
1097 0xff, 0xff, 0xff, 0xff, 0xfc, 0xff, 0xff, 0xff,
1098 0xff, 0xff, 0x07, 0xe0, 0xff, 0x00, 0x00, 0x00}},
1099 {{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
1100 0xfc, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1101 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x07, 0xf8,
1102 0x00, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x80},
1103 {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1104 0xff, 0xff, 0xff, 0xff, 0xff, 0x0c, 0x80, 0x00,
1105 0x00, 0x00, 0x00, 0xc0, 0x7f, 0xfe, 0xff, 0x1f,
1106 0x00, 0xfe, 0xff, 0x03, 0x00, 0x00, 0xfe, 0xff}},
1107 {{0xff, 0xff, 0x81, 0xff, 0xff, 0xff, 0xff, 0x00,
1108 0x80, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x83,
1109 0xff, 0xff, 0x00, 0x00, 0x80, 0x00, 0x00, 0x80,
1110 0xff, 0xff, 0x7f, 0x00, 0x00, 0x00, 0x00, 0xf0},
1111 {0xff, 0x01, 0x00, 0x00, 0x00, 0x00, 0xf8, 0xff,
1112 0xff, 0xff, 0xff, 0xff, 0xff, 0x1f, 0x00, 0x00,
1113 0xf8, 0x07, 0x00, 0x80, 0xff, 0xff, 0xff, 0xff,
1114 0xff, 0xc7, 0xff, 0xff, 0xe0, 0xff, 0xff, 0xff}}
1116 unsigned char res[32][2][32] = {
1117 {{0x0c, 0x3b, 0x0a, 0xca, 0x8d, 0x1a, 0x2f, 0xb9,
1118 0x8a, 0x7b, 0x53, 0x5a, 0x1f, 0xc5, 0x22, 0xa1,
1119 0x07, 0x2a, 0x48, 0xea, 0x02, 0xeb, 0xb3, 0xd6,
1120 0x20, 0x1e, 0x86, 0xd0, 0x95, 0xf6, 0x92, 0x35},
1121 {0xdc, 0x90, 0x7a, 0x07, 0x2e, 0x1e, 0x44, 0x6d,
1122 0xf8, 0x15, 0x24, 0x5b, 0x5a, 0x96, 0x37, 0x9c,
1123 0x37, 0x7b, 0x0d, 0xac, 0x1b, 0x65, 0x58, 0x49,
1124 0x43, 0xb7, 0x31, 0xbb, 0xa7, 0xf4, 0x97, 0x15}},
1125 {{0xf1, 0xf7, 0x3a, 0x50, 0xe6, 0x10, 0xba, 0x22,
1126 0x43, 0x4d, 0x1f, 0x1f, 0x7c, 0x27, 0xca, 0x9c,
1127 0xb8, 0xb6, 0xa0, 0xfc, 0xd8, 0xc0, 0x05, 0x2f,
1128 0xf7, 0x08, 0xe1, 0x76, 0xdd, 0xd0, 0x80, 0xc8},
1129 {0xe3, 0x80, 0x80, 0xb8, 0xdb, 0xe3, 0xa9, 0x77,
1130 0x00, 0xb0, 0xf5, 0x2e, 0x27, 0xe2, 0x68, 0xc4,
1131 0x88, 0xe8, 0x04, 0xc1, 0x12, 0xbf, 0x78, 0x59,
1132 0xe6, 0xa9, 0x7c, 0xe1, 0x81, 0xdd, 0xb9, 0xd5}},
1133 {{0x96, 0xe2, 0xee, 0x01, 0xa6, 0x80, 0x31, 0xef,
1134 0x5c, 0xd0, 0x19, 0xb4, 0x7d, 0x5f, 0x79, 0xab,
1135 0xa1, 0x97, 0xd3, 0x7e, 0x33, 0xbb, 0x86, 0x55,
1136 0x60, 0x20, 0x10, 0x0d, 0x94, 0x2d, 0x11, 0x7c},
1137 {0xcc, 0xab, 0xe0, 0xe8, 0x98, 0x65, 0x12, 0x96,
1138 0x38, 0x5a, 0x1a, 0xf2, 0x85, 0x23, 0x59, 0x5f,
1139 0xf9, 0xf3, 0xc2, 0x81, 0x70, 0x92, 0x65, 0x12,
1140 0x9c, 0x65, 0x1e, 0x96, 0x00, 0xef, 0xe7, 0x63}},
1141 {{0xac, 0x1e, 0x62, 0xc2, 0x59, 0xfc, 0x4e, 0x5c,
1142 0x83, 0xb0, 0xd0, 0x6f, 0xce, 0x19, 0xf6, 0xbf,
1143 0xa4, 0xb0, 0xe0, 0x53, 0x66, 0x1f, 0xbf, 0xc9,
1144 0x33, 0x47, 0x37, 0xa9, 0x3d, 0x5d, 0xb0, 0x48},
1145 {0x86, 0xb9, 0x2a, 0x7f, 0x8e, 0xa8, 0x60, 0x42,
1146 0x26, 0x6d, 0x6e, 0x1c, 0xa2, 0xec, 0xe0, 0xe5,
1147 0x3e, 0x0a, 0x33, 0xbb, 0x61, 0x4c, 0x9f, 0x3c,
1148 0xd1, 0xdf, 0x49, 0x33, 0xcd, 0x72, 0x78, 0x18}},
1149 {{0xf7, 0xd3, 0xcd, 0x49, 0x5c, 0x13, 0x22, 0xfb,
1150 0x2e, 0xb2, 0x2f, 0x27, 0xf5, 0x8a, 0x5d, 0x74,
1151 0xc1, 0x58, 0xc5, 0xc2, 0x2d, 0x9f, 0x52, 0xc6,
1152 0x63, 0x9f, 0xba, 0x05, 0x76, 0x45, 0x7a, 0x63},
1153 {0x8a, 0xfa, 0x55, 0x4d, 0xdd, 0xa3, 0xb2, 0xc3,
1154 0x44, 0xfd, 0xec, 0x72, 0xde, 0xef, 0xc0, 0x99,
1155 0xf5, 0x9f, 0xe2, 0x52, 0xb4, 0x05, 0x32, 0x58,
1156 0x57, 0xc1, 0x8f, 0xea, 0xc3, 0x24, 0x5b, 0x94}},
1157 {{0x05, 0x83, 0xee, 0xdd, 0x64, 0xf0, 0x14, 0x3b,
1158 0xa0, 0x14, 0x4a, 0x3a, 0x41, 0x82, 0x7c, 0xa7,
1159 0x2c, 0xaa, 0xb1, 0x76, 0xbb, 0x59, 0x64, 0x5f,
1160 0x52, 0xad, 0x25, 0x29, 0x9d, 0x8f, 0x0b, 0xb0},
1161 {0x7e, 0xe3, 0x7c, 0xca, 0xcd, 0x4f, 0xb0, 0x6d,
1162 0x7a, 0xb2, 0x3e, 0xa0, 0x08, 0xb9, 0xa8, 0x2d,
1163 0xc2, 0xf4, 0x99, 0x66, 0xcc, 0xac, 0xd8, 0xb9,
1164 0x72, 0x2a, 0x4a, 0x3e, 0x0f, 0x7b, 0xbf, 0xf4}},
1165 {{0x8c, 0x9c, 0x78, 0x2b, 0x39, 0x61, 0x7e, 0xf7,
1166 0x65, 0x37, 0x66, 0x09, 0x38, 0xb9, 0x6f, 0x70,
1167 0x78, 0x87, 0xff, 0xcf, 0x93, 0xca, 0x85, 0x06,
1168 0x44, 0x84, 0xa7, 0xfe, 0xd3, 0xa4, 0xe3, 0x7e},
1169 {0xa2, 0x56, 0x49, 0x23, 0x54, 0xa5, 0x50, 0xe9,
1170 0x5f, 0xf0, 0x4d, 0xe7, 0xdc, 0x38, 0x32, 0x79,
1171 0x4f, 0x1c, 0xb7, 0xe4, 0xbb, 0xf8, 0xbb, 0x2e,
1172 0x40, 0x41, 0x4b, 0xcc, 0xe3, 0x1e, 0x16, 0x36}},
1173 {{0x0c, 0x1e, 0xd7, 0x09, 0x25, 0x40, 0x97, 0xcb,
1174 0x5c, 0x46, 0xa8, 0xda, 0xef, 0x25, 0xd5, 0xe5,
1175 0x92, 0x4d, 0xcf, 0xa3, 0xc4, 0x5d, 0x35, 0x4a,
1176 0xe4, 0x61, 0x92, 0xf3, 0xbf, 0x0e, 0xcd, 0xbe},
1177 {0xe4, 0xaf, 0x0a, 0xb3, 0x30, 0x8b, 0x9b, 0x48,
1178 0x49, 0x43, 0xc7, 0x64, 0x60, 0x4a, 0x2b, 0x9e,
1179 0x95, 0x5f, 0x56, 0xe8, 0x35, 0xdc, 0xeb, 0xdc,
1180 0xc7, 0xc4, 0xfe, 0x30, 0x40, 0xc7, 0xbf, 0xa4}},
1181 {{0xd4, 0xa0, 0xf5, 0x81, 0x49, 0x6b, 0xb6, 0x8b,
1182 0x0a, 0x69, 0xf9, 0xfe, 0xa8, 0x32, 0xe5, 0xe0,
1183 0xa5, 0xcd, 0x02, 0x53, 0xf9, 0x2c, 0xe3, 0x53,
1184 0x83, 0x36, 0xc6, 0x02, 0xb5, 0xeb, 0x64, 0xb8},
1185 {0x1d, 0x42, 0xb9, 0xf9, 0xe9, 0xe3, 0x93, 0x2c,
1186 0x4c, 0xee, 0x6c, 0x5a, 0x47, 0x9e, 0x62, 0x01,
1187 0x6b, 0x04, 0xfe, 0xa4, 0x30, 0x2b, 0x0d, 0x4f,
1188 0x71, 0x10, 0xd3, 0x55, 0xca, 0xf3, 0x5e, 0x80}},
1189 {{0x77, 0x05, 0xf6, 0x0c, 0x15, 0x9b, 0x45, 0xe7,
1190 0xb9, 0x11, 0xb8, 0xf5, 0xd6, 0xda, 0x73, 0x0c,
1191 0xda, 0x92, 0xea, 0xd0, 0x9d, 0xd0, 0x18, 0x92,
1192 0xce, 0x9a, 0xaa, 0xee, 0x0f, 0xef, 0xde, 0x30},
1193 {0xf1, 0xf1, 0xd6, 0x9b, 0x51, 0xd7, 0x77, 0x62,
1194 0x52, 0x10, 0xb8, 0x7a, 0x84, 0x9d, 0x15, 0x4e,
1195 0x07, 0xdc, 0x1e, 0x75, 0x0d, 0x0c, 0x3b, 0xdb,
1196 0x74, 0x58, 0x62, 0x02, 0x90, 0x54, 0x8b, 0x43}},
1197 {{0xa6, 0xfe, 0x0b, 0x87, 0x80, 0x43, 0x67, 0x25,
1198 0x57, 0x5d, 0xec, 0x40, 0x50, 0x08, 0xd5, 0x5d,
1199 0x43, 0xd7, 0xe0, 0xaa, 0xe0, 0x13, 0xb6, 0xb0,
1200 0xc0, 0xd4, 0xe5, 0x0d, 0x45, 0x83, 0xd6, 0x13},
1201 {0x40, 0x45, 0x0a, 0x92, 0x31, 0xea, 0x8c, 0x60,
1202 0x8c, 0x1f, 0xd8, 0x76, 0x45, 0xb9, 0x29, 0x00,
1203 0x26, 0x32, 0xd8, 0xa6, 0x96, 0x88, 0xe2, 0xc4,
1204 0x8b, 0xdb, 0x7f, 0x17, 0x87, 0xcc, 0xc8, 0xf2}},
1205 {{0xc2, 0x56, 0xe2, 0xb6, 0x1a, 0x81, 0xe7, 0x31,
1206 0x63, 0x2e, 0xbb, 0x0d, 0x2f, 0x81, 0x67, 0xd4,
1207 0x22, 0xe2, 0x38, 0x02, 0x25, 0x97, 0xc7, 0x88,
1208 0x6e, 0xdf, 0xbe, 0x2a, 0xa5, 0x73, 0x63, 0xaa},
1209 {0x50, 0x45, 0xe2, 0xc3, 0xbd, 0x89, 0xfc, 0x57,
1210 0xbd, 0x3c, 0xa3, 0x98, 0x7e, 0x7f, 0x36, 0x38,
1211 0x92, 0x39, 0x1f, 0x0f, 0x81, 0x1a, 0x06, 0x51,
1212 0x1f, 0x8d, 0x6a, 0xff, 0x47, 0x16, 0x06, 0x9c}},
1213 {{0x33, 0x95, 0xa2, 0x6f, 0x27, 0x5f, 0x9c, 0x9c,
1214 0x64, 0x45, 0xcb, 0xd1, 0x3c, 0xee, 0x5e, 0x5f,
1215 0x48, 0xa6, 0xaf, 0xe3, 0x79, 0xcf, 0xb1, 0xe2,
1216 0xbf, 0x55, 0x0e, 0xa2, 0x3b, 0x62, 0xf0, 0xe4},
1217 {0x14, 0xe8, 0x06, 0xe3, 0xbe, 0x7e, 0x67, 0x01,
1218 0xc5, 0x21, 0x67, 0xd8, 0x54, 0xb5, 0x7f, 0xa4,
1219 0xf9, 0x75, 0x70, 0x1c, 0xfd, 0x79, 0xdb, 0x86,
1220 0xad, 0x37, 0x85, 0x83, 0x56, 0x4e, 0xf0, 0xbf}},
1221 {{0xbc, 0xa6, 0xe0, 0x56, 0x4e, 0xef, 0xfa, 0xf5,
1222 0x1d, 0x5d, 0x3f, 0x2a, 0x5b, 0x19, 0xab, 0x51,
1223 0xc5, 0x8b, 0xdd, 0x98, 0x28, 0x35, 0x2f, 0xc3,
1224 0x81, 0x4f, 0x5c, 0xe5, 0x70, 0xb9, 0xeb, 0x62},
1225 {0xc4, 0x6d, 0x26, 0xb0, 0x17, 0x6b, 0xfe, 0x6c,
1226 0x12, 0xf8, 0xe7, 0xc1, 0xf5, 0x2f, 0xfa, 0x91,
1227 0x13, 0x27, 0xbd, 0x73, 0xcc, 0x33, 0x31, 0x1c,
1228 0x39, 0xe3, 0x27, 0x6a, 0x95, 0xcf, 0xc5, 0xfb}},
1229 {{0x30, 0xb2, 0x99, 0x84, 0xf0, 0x18, 0x2a, 0x6e,
1230 0x1e, 0x27, 0xed, 0xa2, 0x29, 0x99, 0x41, 0x56,
1231 0xe8, 0xd4, 0x0d, 0xef, 0x99, 0x9c, 0xf3, 0x58,
1232 0x29, 0x55, 0x1a, 0xc0, 0x68, 0xd6, 0x74, 0xa4},
1233 {0x07, 0x9c, 0xe7, 0xec, 0xf5, 0x36, 0x73, 0x41,
1234 0xa3, 0x1c, 0xe5, 0x93, 0x97, 0x6a, 0xfd, 0xf7,
1235 0x53, 0x18, 0xab, 0xaf, 0xeb, 0x85, 0xbd, 0x92,
1236 0x90, 0xab, 0x3c, 0xbf, 0x30, 0x82, 0xad, 0xf6}},
1237 {{0xc6, 0x87, 0x8a, 0x2a, 0xea, 0xc0, 0xa9, 0xec,
1238 0x6d, 0xd3, 0xdc, 0x32, 0x23, 0xce, 0x62, 0x19,
1239 0xa4, 0x7e, 0xa8, 0xdd, 0x1c, 0x33, 0xae, 0xd3,
1240 0x4f, 0x62, 0x9f, 0x52, 0xe7, 0x65, 0x46, 0xf4},
1241 {0x97, 0x51, 0x27, 0x67, 0x2d, 0xa2, 0x82, 0x87,
1242 0x98, 0xd3, 0xb6, 0x14, 0x7f, 0x51, 0xd3, 0x9a,
1243 0x0b, 0xd0, 0x76, 0x81, 0xb2, 0x4f, 0x58, 0x92,
1244 0xa4, 0x86, 0xa1, 0xa7, 0x09, 0x1d, 0xef, 0x9b}},
1245 {{0xb3, 0x0f, 0x2b, 0x69, 0x0d, 0x06, 0x90, 0x64,
1246 0xbd, 0x43, 0x4c, 0x10, 0xe8, 0x98, 0x1c, 0xa3,
1247 0xe1, 0x68, 0xe9, 0x79, 0x6c, 0x29, 0x51, 0x3f,
1248 0x41, 0xdc, 0xdf, 0x1f, 0xf3, 0x60, 0xbe, 0x33},
1249 {0xa1, 0x5f, 0xf7, 0x1d, 0xb4, 0x3e, 0x9b, 0x3c,
1250 0xe7, 0xbd, 0xb6, 0x06, 0xd5, 0x60, 0x06, 0x6d,
1251 0x50, 0xd2, 0xf4, 0x1a, 0x31, 0x08, 0xf2, 0xea,
1252 0x8e, 0xef, 0x5f, 0x7d, 0xb6, 0xd0, 0xc0, 0x27}},
1253 {{0x62, 0x9a, 0xd9, 0xbb, 0x38, 0x36, 0xce, 0xf7,
1254 0x5d, 0x2f, 0x13, 0xec, 0xc8, 0x2d, 0x02, 0x8a,
1255 0x2e, 0x72, 0xf0, 0xe5, 0x15, 0x9d, 0x72, 0xae,
1256 0xfc, 0xb3, 0x4f, 0x02, 0xea, 0xe1, 0x09, 0xfe},
1257 {0x00, 0x00, 0x00, 0x00, 0xfa, 0x0a, 0x3d, 0xbc,
1258 0xad, 0x16, 0x0c, 0xb6, 0xe7, 0x7c, 0x8b, 0x39,
1259 0x9a, 0x43, 0xbb, 0xe3, 0xc2, 0x55, 0x15, 0x14,
1260 0x75, 0xac, 0x90, 0x9b, 0x7f, 0x9a, 0x92, 0x00}},
1261 {{0x8b, 0xac, 0x70, 0x86, 0x29, 0x8f, 0x00, 0x23,
1262 0x7b, 0x45, 0x30, 0xaa, 0xb8, 0x4c, 0xc7, 0x8d,
1263 0x4e, 0x47, 0x85, 0xc6, 0x19, 0xe3, 0x96, 0xc2,
1264 0x9a, 0xa0, 0x12, 0xed, 0x6f, 0xd7, 0x76, 0x16},
1265 {0x45, 0xaf, 0x7e, 0x33, 0xc7, 0x7f, 0x10, 0x6c,
1266 0x7c, 0x9f, 0x29, 0xc1, 0xa8, 0x7e, 0x15, 0x84,
1267 0xe7, 0x7d, 0xc0, 0x6d, 0xab, 0x71, 0x5d, 0xd0,
1268 0x6b, 0x9f, 0x97, 0xab, 0xcb, 0x51, 0x0c, 0x9f}},
1269 {{0x9e, 0xc3, 0x92, 0xb4, 0x04, 0x9f, 0xc8, 0xbb,
1270 0xdd, 0x9e, 0xc6, 0x05, 0xfd, 0x65, 0xec, 0x94,
1271 0x7f, 0x2c, 0x16, 0xc4, 0x40, 0xac, 0x63, 0x7b,
1272 0x7d, 0xb8, 0x0c, 0xe4, 0x5b, 0xe3, 0xa7, 0x0e},
1273 {0x43, 0xf4, 0x44, 0xe8, 0xcc, 0xc8, 0xd4, 0x54,
1274 0x33, 0x37, 0x50, 0xf2, 0x87, 0x42, 0x2e, 0x00,
1275 0x49, 0x60, 0x62, 0x02, 0xfd, 0x1a, 0x7c, 0xdb,
1276 0x29, 0x6c, 0x6d, 0x54, 0x53, 0x08, 0xd1, 0xc8}},
1277 {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1278 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1279 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1280 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00},
1281 {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1282 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1283 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1284 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}},
1285 {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1286 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1287 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1288 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00},
1289 {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1290 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1291 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1292 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01}},
1293 {{0x27, 0x59, 0xc7, 0x35, 0x60, 0x71, 0xa6, 0xf1,
1294 0x79, 0xa5, 0xfd, 0x79, 0x16, 0xf3, 0x41, 0xf0,
1295 0x57, 0xb4, 0x02, 0x97, 0x32, 0xe7, 0xde, 0x59,
1296 0xe2, 0x2d, 0x9b, 0x11, 0xea, 0x2c, 0x35, 0x92},
1297 {0x27, 0x59, 0xc7, 0x35, 0x60, 0x71, 0xa6, 0xf1,
1298 0x79, 0xa5, 0xfd, 0x79, 0x16, 0xf3, 0x41, 0xf0,
1299 0x57, 0xb4, 0x02, 0x97, 0x32, 0xe7, 0xde, 0x59,
1300 0xe2, 0x2d, 0x9b, 0x11, 0xea, 0x2c, 0x35, 0x92}},
1301 {{0x28, 0x56, 0xac, 0x0e, 0x4f, 0x98, 0x09, 0xf0,
1302 0x49, 0xfa, 0x7f, 0x84, 0xac, 0x7e, 0x50, 0x5b,
1303 0x17, 0x43, 0x14, 0x89, 0x9c, 0x53, 0xa8, 0x94,
1304 0x30, 0xf2, 0x11, 0x4d, 0x92, 0x14, 0x27, 0xe8},
1305 {0x39, 0x7a, 0x84, 0x56, 0x79, 0x9d, 0xec, 0x26,
1306 0x2c, 0x53, 0xc1, 0x94, 0xc9, 0x8d, 0x9e, 0x9d,
1307 0x32, 0x1f, 0xdd, 0x84, 0x04, 0xe8, 0xe2, 0x0a,
1308 0x6b, 0xbe, 0xbb, 0x42, 0x40, 0x67, 0x30, 0x6c}},
1309 {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1310 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
1311 0x45, 0x51, 0x23, 0x19, 0x50, 0xb7, 0x5f, 0xc4,
1312 0x40, 0x2d, 0xa1, 0x73, 0x2f, 0xc9, 0xbe, 0xbd},
1313 {0x27, 0x59, 0xc7, 0x35, 0x60, 0x71, 0xa6, 0xf1,
1314 0x79, 0xa5, 0xfd, 0x79, 0x16, 0xf3, 0x41, 0xf0,
1315 0x57, 0xb4, 0x02, 0x97, 0x32, 0xe7, 0xde, 0x59,
1316 0xe2, 0x2d, 0x9b, 0x11, 0xea, 0x2c, 0x35, 0x92}},
1317 {{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1318 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
1319 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
1320 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x40},
1321 {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1322 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1323 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1324 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01}},
1325 {{0x1c, 0xc4, 0xf7, 0xda, 0x0f, 0x65, 0xca, 0x39,
1326 0x70, 0x52, 0x92, 0x8e, 0xc3, 0xc8, 0x15, 0xea,
1327 0x7f, 0x10, 0x9e, 0x77, 0x4b, 0x6e, 0x2d, 0xdf,
1328 0xe8, 0x30, 0x9d, 0xda, 0xe8, 0x9a, 0x65, 0xae},
1329 {0x02, 0xb0, 0x16, 0xb1, 0x1d, 0xc8, 0x57, 0x7b,
1330 0xa2, 0x3a, 0xa2, 0xa3, 0x38, 0x5c, 0x8f, 0xeb,
1331 0x66, 0x37, 0x91, 0xa8, 0x5f, 0xef, 0x04, 0xf6,
1332 0x59, 0x75, 0xe1, 0xee, 0x92, 0xf6, 0x0e, 0x30}},
1333 {{0x8d, 0x76, 0x14, 0xa4, 0x14, 0x06, 0x9f, 0x9a,
1334 0xdf, 0x4a, 0x85, 0xa7, 0x6b, 0xbf, 0x29, 0x6f,
1335 0xbc, 0x34, 0x87, 0x5d, 0xeb, 0xbb, 0x2e, 0xa9,
1336 0xc9, 0x1f, 0x58, 0xd6, 0x9a, 0x82, 0xa0, 0x56},
1337 {0xd4, 0xb9, 0xdb, 0x88, 0x1d, 0x04, 0xe9, 0x93,
1338 0x8d, 0x3f, 0x20, 0xd5, 0x86, 0xa8, 0x83, 0x07,
1339 0xdb, 0x09, 0xd8, 0x22, 0x1f, 0x7f, 0xf1, 0x71,
1340 0xc8, 0xe7, 0x5d, 0x47, 0xaf, 0x8b, 0x72, 0xe9}},
1341 {{0x83, 0xb9, 0x39, 0xb2, 0xa4, 0xdf, 0x46, 0x87,
1342 0xc2, 0xb8, 0xf1, 0xe6, 0x4c, 0xd1, 0xe2, 0xa9,
1343 0xe4, 0x70, 0x30, 0x34, 0xbc, 0x52, 0x7c, 0x55,
1344 0xa6, 0xec, 0x80, 0xa4, 0xe5, 0xd2, 0xdc, 0x73},
1345 {0x08, 0xf1, 0x03, 0xcf, 0x16, 0x73, 0xe8, 0x7d,
1346 0xb6, 0x7e, 0x9b, 0xc0, 0xb4, 0xc2, 0xa5, 0x86,
1347 0x02, 0x77, 0xd5, 0x27, 0x86, 0xa5, 0x15, 0xfb,
1348 0xae, 0x9b, 0x8c, 0xa9, 0xf9, 0xf8, 0xa8, 0x4a}},
1349 {{0x8b, 0x00, 0x49, 0xdb, 0xfa, 0xf0, 0x1b, 0xa2,
1350 0xed, 0x8a, 0x9a, 0x7a, 0x36, 0x78, 0x4a, 0xc7,
1351 0xf7, 0xad, 0x39, 0xd0, 0x6c, 0x65, 0x7a, 0x41,
1352 0xce, 0xd6, 0xd6, 0x4c, 0x20, 0x21, 0x6b, 0xc7},
1353 {0xc6, 0xca, 0x78, 0x1d, 0x32, 0x6c, 0x6c, 0x06,
1354 0x91, 0xf2, 0x1a, 0xe8, 0x43, 0x16, 0xea, 0x04,
1355 0x3c, 0x1f, 0x07, 0x85, 0xf7, 0x09, 0x22, 0x08,
1356 0xba, 0x13, 0xfd, 0x78, 0x1e, 0x3f, 0x6f, 0x62}},
1357 {{0x25, 0x9b, 0x7c, 0xb0, 0xac, 0x72, 0x6f, 0xb2,
1358 0xe3, 0x53, 0x84, 0x7a, 0x1a, 0x9a, 0x98, 0x9b,
1359 0x44, 0xd3, 0x59, 0xd0, 0x8e, 0x57, 0x41, 0x40,
1360 0x78, 0xa7, 0x30, 0x2f, 0x4c, 0x9c, 0xb9, 0x68},
1361 {0xb7, 0x75, 0x03, 0x63, 0x61, 0xc2, 0x48, 0x6e,
1362 0x12, 0x3d, 0xbf, 0x4b, 0x27, 0xdf, 0xb1, 0x7a,
1363 0xff, 0x4e, 0x31, 0x07, 0x83, 0xf4, 0x62, 0x5b,
1364 0x19, 0xa5, 0xac, 0xa0, 0x32, 0x58, 0x0d, 0xa7}},
1365 {{0x43, 0x4f, 0x10, 0xa4, 0xca, 0xdb, 0x38, 0x67,
1366 0xfa, 0xae, 0x96, 0xb5, 0x6d, 0x97, 0xff, 0x1f,
1367 0xb6, 0x83, 0x43, 0xd3, 0xa0, 0x2d, 0x70, 0x7a,
1368 0x64, 0x05, 0x4c, 0xa7, 0xc1, 0xa5, 0x21, 0x51},
1369 {0xe4, 0xf1, 0x23, 0x84, 0xe1, 0xb5, 0x9d, 0xf2,
1370 0xb8, 0x73, 0x8b, 0x45, 0x2b, 0x35, 0x46, 0x38,
1371 0x10, 0x2b, 0x50, 0xf8, 0x8b, 0x35, 0xcd, 0x34,
1372 0xc8, 0x0e, 0xf6, 0xdb, 0x09, 0x35, 0xf0, 0xda}}
1374 secp256k1_scalar_set_int(&one, 1);
1375 for (i = 0; i < 32; i++) {
1376 secp256k1_scalar_set_b32(&x, chal[i][0], &overflow);
1378 secp256k1_scalar_set_b32(&y, chal[i][1], &overflow);
1380 secp256k1_scalar_set_b32(&r1, res[i][0], &overflow);
1382 secp256k1_scalar_set_b32(&r2, res[i][1], &overflow);
1384 secp256k1_scalar_mul(&z, &x, &y);
1385 CHECK(!secp256k1_scalar_check_overflow(&z));
1386 CHECK(secp256k1_scalar_eq(&r1, &z));
1387 if (!secp256k1_scalar_is_zero(&y)) {
1388 secp256k1_scalar_inverse(&zz, &y);
1389 CHECK(!secp256k1_scalar_check_overflow(&zz));
1390 #if defined(USE_SCALAR_INV_NUM)
1391 secp256k1_scalar_inverse_var(&zzv, &y);
1392 CHECK(secp256k1_scalar_eq(&zzv, &zz));
1394 secp256k1_scalar_mul(&z, &z, &zz);
1395 CHECK(!secp256k1_scalar_check_overflow(&z));
1396 CHECK(secp256k1_scalar_eq(&x, &z));
1397 secp256k1_scalar_mul(&zz, &zz, &y);
1398 CHECK(!secp256k1_scalar_check_overflow(&zz));
1399 CHECK(secp256k1_scalar_eq(&one, &zz));
1401 secp256k1_scalar_mul(&z, &x, &x);
1402 CHECK(!secp256k1_scalar_check_overflow(&z));
1403 secp256k1_scalar_sqr(&zz, &x);
1404 CHECK(!secp256k1_scalar_check_overflow(&zz));
1405 CHECK(secp256k1_scalar_eq(&zz, &z));
1406 CHECK(secp256k1_scalar_eq(&r2, &zz));
1411 /***** FIELD TESTS *****/
1413 void random_fe(secp256k1_fe *x) {
1414 unsigned char bin[32];
1416 secp256k1_rand256(bin);
1417 if (secp256k1_fe_set_b32(x, bin)) {
1423 void random_fe_non_zero(secp256k1_fe *nz) {
1425 while (--tries >= 0) {
1427 secp256k1_fe_normalize(nz);
1428 if (!secp256k1_fe_is_zero(nz)) {
1432 /* Infinitesimal probability of spurious failure here */
1436 void random_fe_non_square(secp256k1_fe *ns) {
1438 random_fe_non_zero(ns);
1439 if (secp256k1_fe_sqrt_var(&r, ns)) {
1440 secp256k1_fe_negate(ns, ns, 1);
1444 int check_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b) {
1445 secp256k1_fe an = *a;
1446 secp256k1_fe bn = *b;
1447 secp256k1_fe_normalize_weak(&an);
1448 secp256k1_fe_normalize_var(&bn);
1449 return secp256k1_fe_equal_var(&an, &bn);
1452 int check_fe_inverse(const secp256k1_fe *a, const secp256k1_fe *ai) {
1454 secp256k1_fe one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1);
1455 secp256k1_fe_mul(&x, a, ai);
1456 return check_fe_equal(&x, &one);
1459 void run_field_convert(void) {
1460 static const unsigned char b32[32] = {
1461 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
1462 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18,
1463 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29,
1464 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x40
1466 static const secp256k1_fe_storage fes = SECP256K1_FE_STORAGE_CONST(
1467 0x00010203UL, 0x04050607UL, 0x11121314UL, 0x15161718UL,
1468 0x22232425UL, 0x26272829UL, 0x33343536UL, 0x37383940UL
1470 static const secp256k1_fe fe = SECP256K1_FE_CONST(
1471 0x00010203UL, 0x04050607UL, 0x11121314UL, 0x15161718UL,
1472 0x22232425UL, 0x26272829UL, 0x33343536UL, 0x37383940UL
1475 unsigned char b322[32];
1476 secp256k1_fe_storage fes2;
1477 /* Check conversions to fe. */
1478 CHECK(secp256k1_fe_set_b32(&fe2, b32));
1479 CHECK(secp256k1_fe_equal_var(&fe, &fe2));
1480 secp256k1_fe_from_storage(&fe2, &fes);
1481 CHECK(secp256k1_fe_equal_var(&fe, &fe2));
1482 /* Check conversion from fe. */
1483 secp256k1_fe_get_b32(b322, &fe);
1484 CHECK(memcmp(b322, b32, 32) == 0);
1485 secp256k1_fe_to_storage(&fes2, &fe);
1486 CHECK(memcmp(&fes2, &fes, sizeof(fes)) == 0);
1489 int fe_memcmp(const secp256k1_fe *a, const secp256k1_fe *b) {
1490 secp256k1_fe t = *b;
1492 t.magnitude = a->magnitude;
1493 t.normalized = a->normalized;
1495 return memcmp(a, &t, sizeof(secp256k1_fe));
1498 void run_field_misc(void) {
1503 secp256k1_fe fe5 = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 5);
1505 for (i = 0; i < 5*count; i++) {
1506 secp256k1_fe_storage xs, ys, zs;
1508 random_fe_non_zero(&y);
1509 /* Test the fe equality and comparison operations. */
1510 CHECK(secp256k1_fe_cmp_var(&x, &x) == 0);
1511 CHECK(secp256k1_fe_equal_var(&x, &x));
1513 secp256k1_fe_add(&z,&y);
1514 /* Test fe conditional move; z is not normalized here. */
1516 secp256k1_fe_cmov(&x, &z, 0);
1517 VERIFY_CHECK(!x.normalized && x.magnitude == z.magnitude);
1518 secp256k1_fe_cmov(&x, &x, 1);
1519 CHECK(fe_memcmp(&x, &z) != 0);
1520 CHECK(fe_memcmp(&x, &q) == 0);
1521 secp256k1_fe_cmov(&q, &z, 1);
1522 VERIFY_CHECK(!q.normalized && q.magnitude == z.magnitude);
1523 CHECK(fe_memcmp(&q, &z) == 0);
1524 secp256k1_fe_normalize_var(&x);
1525 secp256k1_fe_normalize_var(&z);
1526 CHECK(!secp256k1_fe_equal_var(&x, &z));
1527 secp256k1_fe_normalize_var(&q);
1528 secp256k1_fe_cmov(&q, &z, (i&1));
1529 VERIFY_CHECK(q.normalized && q.magnitude == 1);
1530 for (j = 0; j < 6; j++) {
1531 secp256k1_fe_negate(&z, &z, j+1);
1532 secp256k1_fe_normalize_var(&q);
1533 secp256k1_fe_cmov(&q, &z, (j&1));
1534 VERIFY_CHECK(!q.normalized && q.magnitude == (j+2));
1536 secp256k1_fe_normalize_var(&z);
1537 /* Test storage conversion and conditional moves. */
1538 secp256k1_fe_to_storage(&xs, &x);
1539 secp256k1_fe_to_storage(&ys, &y);
1540 secp256k1_fe_to_storage(&zs, &z);
1541 secp256k1_fe_storage_cmov(&zs, &xs, 0);
1542 secp256k1_fe_storage_cmov(&zs, &zs, 1);
1543 CHECK(memcmp(&xs, &zs, sizeof(xs)) != 0);
1544 secp256k1_fe_storage_cmov(&ys, &xs, 1);
1545 CHECK(memcmp(&xs, &ys, sizeof(xs)) == 0);
1546 secp256k1_fe_from_storage(&x, &xs);
1547 secp256k1_fe_from_storage(&y, &ys);
1548 secp256k1_fe_from_storage(&z, &zs);
1549 /* Test that mul_int, mul, and add agree. */
1550 secp256k1_fe_add(&y, &x);
1551 secp256k1_fe_add(&y, &x);
1553 secp256k1_fe_mul_int(&z, 3);
1554 CHECK(check_fe_equal(&y, &z));
1555 secp256k1_fe_add(&y, &x);
1556 secp256k1_fe_add(&z, &x);
1557 CHECK(check_fe_equal(&z, &y));
1559 secp256k1_fe_mul_int(&z, 5);
1560 secp256k1_fe_mul(&q, &x, &fe5);
1561 CHECK(check_fe_equal(&z, &q));
1562 secp256k1_fe_negate(&x, &x, 1);
1563 secp256k1_fe_add(&z, &x);
1564 secp256k1_fe_add(&q, &x);
1565 CHECK(check_fe_equal(&y, &z));
1566 CHECK(check_fe_equal(&q, &y));
1570 void run_field_inv(void) {
1571 secp256k1_fe x, xi, xii;
1573 for (i = 0; i < 10*count; i++) {
1574 random_fe_non_zero(&x);
1575 secp256k1_fe_inv(&xi, &x);
1576 CHECK(check_fe_inverse(&x, &xi));
1577 secp256k1_fe_inv(&xii, &xi);
1578 CHECK(check_fe_equal(&x, &xii));
1582 void run_field_inv_var(void) {
1583 secp256k1_fe x, xi, xii;
1585 for (i = 0; i < 10*count; i++) {
1586 random_fe_non_zero(&x);
1587 secp256k1_fe_inv_var(&xi, &x);
1588 CHECK(check_fe_inverse(&x, &xi));
1589 secp256k1_fe_inv_var(&xii, &xi);
1590 CHECK(check_fe_equal(&x, &xii));
1594 void run_field_inv_all_var(void) {
1595 secp256k1_fe x[16], xi[16], xii[16];
1597 /* Check it's safe to call for 0 elements */
1598 secp256k1_fe_inv_all_var(0, xi, x);
1599 for (i = 0; i < count; i++) {
1601 size_t len = secp256k1_rand_int(15) + 1;
1602 for (j = 0; j < len; j++) {
1603 random_fe_non_zero(&x[j]);
1605 secp256k1_fe_inv_all_var(len, xi, x);
1606 for (j = 0; j < len; j++) {
1607 CHECK(check_fe_inverse(&x[j], &xi[j]));
1609 secp256k1_fe_inv_all_var(len, xii, xi);
1610 for (j = 0; j < len; j++) {
1611 CHECK(check_fe_equal(&x[j], &xii[j]));
1616 void run_sqr(void) {
1621 secp256k1_fe_set_int(&x, 1);
1622 secp256k1_fe_negate(&x, &x, 1);
1624 for (i = 1; i <= 512; ++i) {
1625 secp256k1_fe_mul_int(&x, 2);
1626 secp256k1_fe_normalize(&x);
1627 secp256k1_fe_sqr(&s, &x);
1632 void test_sqrt(const secp256k1_fe *a, const secp256k1_fe *k) {
1633 secp256k1_fe r1, r2;
1634 int v = secp256k1_fe_sqrt_var(&r1, a);
1635 CHECK((v == 0) == (k == NULL));
1638 /* Check that the returned root is +/- the given known answer */
1639 secp256k1_fe_negate(&r2, &r1, 1);
1640 secp256k1_fe_add(&r1, k); secp256k1_fe_add(&r2, k);
1641 secp256k1_fe_normalize(&r1); secp256k1_fe_normalize(&r2);
1642 CHECK(secp256k1_fe_is_zero(&r1) || secp256k1_fe_is_zero(&r2));
1646 void run_sqrt(void) {
1647 secp256k1_fe ns, x, s, t;
1650 /* Check sqrt(0) is 0 */
1651 secp256k1_fe_set_int(&x, 0);
1652 secp256k1_fe_sqr(&s, &x);
1655 /* Check sqrt of small squares (and their negatives) */
1656 for (i = 1; i <= 100; i++) {
1657 secp256k1_fe_set_int(&x, i);
1658 secp256k1_fe_sqr(&s, &x);
1660 secp256k1_fe_negate(&t, &s, 1);
1661 test_sqrt(&t, NULL);
1664 /* Consistency checks for large random values */
1665 for (i = 0; i < 10; i++) {
1667 random_fe_non_square(&ns);
1668 for (j = 0; j < count; j++) {
1670 secp256k1_fe_sqr(&s, &x);
1672 secp256k1_fe_negate(&t, &s, 1);
1673 test_sqrt(&t, NULL);
1674 secp256k1_fe_mul(&t, &s, &ns);
1675 test_sqrt(&t, NULL);
1680 /***** GROUP TESTS *****/
1682 void ge_equals_ge(const secp256k1_ge *a, const secp256k1_ge *b) {
1683 CHECK(a->infinity == b->infinity);
1687 CHECK(secp256k1_fe_equal_var(&a->x, &b->x));
1688 CHECK(secp256k1_fe_equal_var(&a->y, &b->y));
1691 /* This compares jacobian points including their Z, not just their geometric meaning. */
1692 int gej_xyz_equals_gej(const secp256k1_gej *a, const secp256k1_gej *b) {
1696 ret &= a->infinity == b->infinity;
1697 if (ret && !a->infinity) {
1700 secp256k1_fe_normalize(&a2.x);
1701 secp256k1_fe_normalize(&a2.y);
1702 secp256k1_fe_normalize(&a2.z);
1703 secp256k1_fe_normalize(&b2.x);
1704 secp256k1_fe_normalize(&b2.y);
1705 secp256k1_fe_normalize(&b2.z);
1706 ret &= secp256k1_fe_cmp_var(&a2.x, &b2.x) == 0;
1707 ret &= secp256k1_fe_cmp_var(&a2.y, &b2.y) == 0;
1708 ret &= secp256k1_fe_cmp_var(&a2.z, &b2.z) == 0;
1713 void ge_equals_gej(const secp256k1_ge *a, const secp256k1_gej *b) {
1715 secp256k1_fe u1, u2, s1, s2;
1716 CHECK(a->infinity == b->infinity);
1720 /* Check a.x * b.z^2 == b.x && a.y * b.z^3 == b.y, to avoid inverses. */
1721 secp256k1_fe_sqr(&z2s, &b->z);
1722 secp256k1_fe_mul(&u1, &a->x, &z2s);
1723 u2 = b->x; secp256k1_fe_normalize_weak(&u2);
1724 secp256k1_fe_mul(&s1, &a->y, &z2s); secp256k1_fe_mul(&s1, &s1, &b->z);
1725 s2 = b->y; secp256k1_fe_normalize_weak(&s2);
1726 CHECK(secp256k1_fe_equal_var(&u1, &u2));
1727 CHECK(secp256k1_fe_equal_var(&s1, &s2));
1730 void test_ge(void) {
1732 #ifdef USE_ENDOMORPHISM
1737 /* Points: (infinity, p1, p1, -p1, -p1, p2, p2, -p2, -p2, p3, p3, -p3, -p3, p4, p4, -p4, -p4).
1738 * The second in each pair of identical points uses a random Z coordinate in the Jacobian form.
1739 * All magnitudes are randomized.
1740 * All 17*17 combinations of points are added to each other, using all applicable methods.
1742 * When the endomorphism code is compiled in, p5 = lambda*p1 and p6 = lambda^2*p1 are added as well.
1744 secp256k1_ge *ge = (secp256k1_ge *)malloc(sizeof(secp256k1_ge) * (1 + 4 * runs));
1745 secp256k1_gej *gej = (secp256k1_gej *)malloc(sizeof(secp256k1_gej) * (1 + 4 * runs));
1746 secp256k1_fe *zinv = (secp256k1_fe *)malloc(sizeof(secp256k1_fe) * (1 + 4 * runs));
1748 secp256k1_fe zfi2, zfi3;
1750 secp256k1_gej_set_infinity(&gej[0]);
1751 secp256k1_ge_clear(&ge[0]);
1752 secp256k1_ge_set_gej_var(&ge[0], &gej[0]);
1753 for (i = 0; i < runs; i++) {
1756 random_group_element_test(&g);
1757 #ifdef USE_ENDOMORPHISM
1758 if (i >= runs - 2) {
1759 secp256k1_ge_mul_lambda(&g, &ge[1]);
1761 if (i >= runs - 1) {
1762 secp256k1_ge_mul_lambda(&g, &g);
1767 secp256k1_ge_neg(&ge[3 + 4 * i], &g);
1768 secp256k1_ge_neg(&ge[4 + 4 * i], &g);
1769 secp256k1_gej_set_ge(&gej[1 + 4 * i], &ge[1 + 4 * i]);
1770 random_group_element_jacobian_test(&gej[2 + 4 * i], &ge[2 + 4 * i]);
1771 secp256k1_gej_set_ge(&gej[3 + 4 * i], &ge[3 + 4 * i]);
1772 random_group_element_jacobian_test(&gej[4 + 4 * i], &ge[4 + 4 * i]);
1773 for (j = 0; j < 4; j++) {
1774 random_field_element_magnitude(&ge[1 + j + 4 * i].x);
1775 random_field_element_magnitude(&ge[1 + j + 4 * i].y);
1776 random_field_element_magnitude(&gej[1 + j + 4 * i].x);
1777 random_field_element_magnitude(&gej[1 + j + 4 * i].y);
1778 random_field_element_magnitude(&gej[1 + j + 4 * i].z);
1782 /* Compute z inverses. */
1784 secp256k1_fe *zs = malloc(sizeof(secp256k1_fe) * (1 + 4 * runs));
1785 for (i = 0; i < 4 * runs + 1; i++) {
1787 /* The point at infinity does not have a meaningful z inverse. Any should do. */
1789 random_field_element_test(&zs[i]);
1790 } while(secp256k1_fe_is_zero(&zs[i]));
1795 secp256k1_fe_inv_all_var(4 * runs + 1, zinv, zs);
1799 /* Generate random zf, and zfi2 = 1/zf^2, zfi3 = 1/zf^3 */
1801 random_field_element_test(&zf);
1802 } while(secp256k1_fe_is_zero(&zf));
1803 random_field_element_magnitude(&zf);
1804 secp256k1_fe_inv_var(&zfi3, &zf);
1805 secp256k1_fe_sqr(&zfi2, &zfi3);
1806 secp256k1_fe_mul(&zfi3, &zfi3, &zfi2);
1808 for (i1 = 0; i1 < 1 + 4 * runs; i1++) {
1810 for (i2 = 0; i2 < 1 + 4 * runs; i2++) {
1811 /* Compute reference result using gej + gej (var). */
1812 secp256k1_gej refj, resj;
1815 secp256k1_gej_add_var(&refj, &gej[i1], &gej[i2], secp256k1_gej_is_infinity(&gej[i1]) ? NULL : &zr);
1816 /* Check Z ratio. */
1817 if (!secp256k1_gej_is_infinity(&gej[i1]) && !secp256k1_gej_is_infinity(&refj)) {
1818 secp256k1_fe zrz; secp256k1_fe_mul(&zrz, &zr, &gej[i1].z);
1819 CHECK(secp256k1_fe_equal_var(&zrz, &refj.z));
1821 secp256k1_ge_set_gej_var(&ref, &refj);
1823 /* Test gej + ge with Z ratio result (var). */
1824 secp256k1_gej_add_ge_var(&resj, &gej[i1], &ge[i2], secp256k1_gej_is_infinity(&gej[i1]) ? NULL : &zr);
1825 ge_equals_gej(&ref, &resj);
1826 if (!secp256k1_gej_is_infinity(&gej[i1]) && !secp256k1_gej_is_infinity(&resj)) {
1827 secp256k1_fe zrz; secp256k1_fe_mul(&zrz, &zr, &gej[i1].z);
1828 CHECK(secp256k1_fe_equal_var(&zrz, &resj.z));
1831 /* Test gej + ge (var, with additional Z factor). */
1833 secp256k1_ge ge2_zfi = ge[i2]; /* the second term with x and y rescaled for z = 1/zf */
1834 secp256k1_fe_mul(&ge2_zfi.x, &ge2_zfi.x, &zfi2);
1835 secp256k1_fe_mul(&ge2_zfi.y, &ge2_zfi.y, &zfi3);
1836 random_field_element_magnitude(&ge2_zfi.x);
1837 random_field_element_magnitude(&ge2_zfi.y);
1838 secp256k1_gej_add_zinv_var(&resj, &gej[i1], &ge2_zfi, &zf);
1839 ge_equals_gej(&ref, &resj);
1842 /* Test gej + ge (const). */
1844 /* secp256k1_gej_add_ge does not support its second argument being infinity. */
1845 secp256k1_gej_add_ge(&resj, &gej[i1], &ge[i2]);
1846 ge_equals_gej(&ref, &resj);
1849 /* Test doubling (var). */
1850 if ((i1 == 0 && i2 == 0) || ((i1 + 3)/4 == (i2 + 3)/4 && ((i1 + 3)%4)/2 == ((i2 + 3)%4)/2)) {
1852 /* Normal doubling with Z ratio result. */
1853 secp256k1_gej_double_var(&resj, &gej[i1], &zr2);
1854 ge_equals_gej(&ref, &resj);
1855 /* Check Z ratio. */
1856 secp256k1_fe_mul(&zr2, &zr2, &gej[i1].z);
1857 CHECK(secp256k1_fe_equal_var(&zr2, &resj.z));
1858 /* Normal doubling. */
1859 secp256k1_gej_double_var(&resj, &gej[i2], NULL);
1860 ge_equals_gej(&ref, &resj);
1863 /* Test adding opposites. */
1864 if ((i1 == 0 && i2 == 0) || ((i1 + 3)/4 == (i2 + 3)/4 && ((i1 + 3)%4)/2 != ((i2 + 3)%4)/2)) {
1865 CHECK(secp256k1_ge_is_infinity(&ref));
1868 /* Test adding infinity. */
1870 CHECK(secp256k1_ge_is_infinity(&ge[i1]));
1871 CHECK(secp256k1_gej_is_infinity(&gej[i1]));
1872 ge_equals_gej(&ref, &gej[i2]);
1875 CHECK(secp256k1_ge_is_infinity(&ge[i2]));
1876 CHECK(secp256k1_gej_is_infinity(&gej[i2]));
1877 ge_equals_gej(&ref, &gej[i1]);
1882 /* Test adding all points together in random order equals infinity. */
1884 secp256k1_gej sum = SECP256K1_GEJ_CONST_INFINITY;
1885 secp256k1_gej *gej_shuffled = (secp256k1_gej *)malloc((4 * runs + 1) * sizeof(secp256k1_gej));
1886 for (i = 0; i < 4 * runs + 1; i++) {
1887 gej_shuffled[i] = gej[i];
1889 for (i = 0; i < 4 * runs + 1; i++) {
1890 int swap = i + secp256k1_rand_int(4 * runs + 1 - i);
1892 secp256k1_gej t = gej_shuffled[i];
1893 gej_shuffled[i] = gej_shuffled[swap];
1894 gej_shuffled[swap] = t;
1897 for (i = 0; i < 4 * runs + 1; i++) {
1898 secp256k1_gej_add_var(&sum, &sum, &gej_shuffled[i], NULL);
1900 CHECK(secp256k1_gej_is_infinity(&sum));
1904 /* Test batch gej -> ge conversion with and without known z ratios. */
1906 secp256k1_fe *zr = (secp256k1_fe *)malloc((4 * runs + 1) * sizeof(secp256k1_fe));
1907 secp256k1_ge *ge_set_table = (secp256k1_ge *)malloc((4 * runs + 1) * sizeof(secp256k1_ge));
1908 secp256k1_ge *ge_set_all = (secp256k1_ge *)malloc((4 * runs + 1) * sizeof(secp256k1_ge));
1909 for (i = 0; i < 4 * runs + 1; i++) {
1910 /* Compute gej[i + 1].z / gez[i].z (with gej[n].z taken to be 1). */
1912 secp256k1_fe_mul(&zr[i + 1], &zinv[i], &gej[i + 1].z);
1915 secp256k1_ge_set_table_gej_var(4 * runs + 1, ge_set_table, gej, zr);
1916 secp256k1_ge_set_all_gej_var(4 * runs + 1, ge_set_all, gej, &ctx->error_callback);
1917 for (i = 0; i < 4 * runs + 1; i++) {
1919 random_fe_non_zero(&s);
1920 secp256k1_gej_rescale(&gej[i], &s);
1921 ge_equals_gej(&ge_set_table[i], &gej[i]);
1922 ge_equals_gej(&ge_set_all[i], &gej[i]);
1934 void test_add_neg_y_diff_x(void) {
1935 /* The point of this test is to check that we can add two points
1936 * whose y-coordinates are negatives of each other but whose x
1937 * coordinates differ. If the x-coordinates were the same, these
1938 * points would be negatives of each other and their sum is
1939 * infinity. This is cool because it "covers up" any degeneracy
1940 * in the addition algorithm that would cause the xy coordinates
1941 * of the sum to be wrong (since infinity has no xy coordinates).
1942 * HOWEVER, if the x-coordinates are different, infinity is the
1943 * wrong answer, and such degeneracies are exposed. This is the
1944 * root of https://github.com/bitcoin/secp256k1/issues/257 which
1945 * this test is a regression test for.
1947 * These points were generated in sage as
1948 * # secp256k1 params
1949 * F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
1950 * C = EllipticCurve ([F (0), F (7)])
1951 * G = C.lift_x(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
1952 * N = FiniteField(G.order())
1954 * # endomorphism values (lambda is 1^{1/3} in N, beta is 1^{1/3} in F)
1956 * lam = (1 - x^3).roots()[1][0]
1958 * # random "bad pair"
1959 * P = C.random_element()
1961 * print " P: %x %x" % P.xy()
1962 * print " Q: %x %x" % Q.xy()
1963 * print "P + Q: %x %x" % (P + Q).xy()
1965 secp256k1_gej aj = SECP256K1_GEJ_CONST(
1966 0x8d24cd95, 0x0a355af1, 0x3c543505, 0x44238d30,
1967 0x0643d79f, 0x05a59614, 0x2f8ec030, 0xd58977cb,
1968 0x001e337a, 0x38093dcd, 0x6c0f386d, 0x0b1293a8,
1969 0x4d72c879, 0xd7681924, 0x44e6d2f3, 0x9190117d
1971 secp256k1_gej bj = SECP256K1_GEJ_CONST(
1972 0xc7b74206, 0x1f788cd9, 0xabd0937d, 0x164a0d86,
1973 0x95f6ff75, 0xf19a4ce9, 0xd013bd7b, 0xbf92d2a7,
1974 0xffe1cc85, 0xc7f6c232, 0x93f0c792, 0xf4ed6c57,
1975 0xb28d3786, 0x2897e6db, 0xbb192d0b, 0x6e6feab2
1977 secp256k1_gej sumj = SECP256K1_GEJ_CONST(
1978 0x671a63c0, 0x3efdad4c, 0x389a7798, 0x24356027,
1979 0xb3d69010, 0x278625c3, 0x5c86d390, 0x184a8f7a,
1980 0x5f6409c2, 0x2ce01f2b, 0x511fd375, 0x25071d08,
1981 0xda651801, 0x70e95caf, 0x8f0d893c, 0xbed8fbbe
1986 secp256k1_ge_set_gej(&b, &bj);
1988 secp256k1_gej_add_var(&resj, &aj, &bj, NULL);
1989 secp256k1_ge_set_gej(&res, &resj);
1990 ge_equals_gej(&res, &sumj);
1992 secp256k1_gej_add_ge(&resj, &aj, &b);
1993 secp256k1_ge_set_gej(&res, &resj);
1994 ge_equals_gej(&res, &sumj);
1996 secp256k1_gej_add_ge_var(&resj, &aj, &b, NULL);
1997 secp256k1_ge_set_gej(&res, &resj);
1998 ge_equals_gej(&res, &sumj);
2003 for (i = 0; i < count * 32; i++) {
2006 test_add_neg_y_diff_x();
2009 void test_ec_combine(void) {
2010 secp256k1_scalar sum = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
2011 secp256k1_pubkey data[6];
2012 const secp256k1_pubkey* d[6];
2013 secp256k1_pubkey sd;
2014 secp256k1_pubkey sd2;
2018 for (i = 1; i <= 6; i++) {
2020 random_scalar_order_test(&s);
2021 secp256k1_scalar_add(&sum, &sum, &s);
2022 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &Qj, &s);
2023 secp256k1_ge_set_gej(&Q, &Qj);
2024 secp256k1_pubkey_save(&data[i - 1], &Q);
2025 d[i - 1] = &data[i - 1];
2026 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &Qj, &sum);
2027 secp256k1_ge_set_gej(&Q, &Qj);
2028 secp256k1_pubkey_save(&sd, &Q);
2029 CHECK(secp256k1_ec_pubkey_combine(ctx, &sd2, d, i) == 1);
2030 CHECK(memcmp(&sd, &sd2, sizeof(sd)) == 0);
2034 void run_ec_combine(void) {
2036 for (i = 0; i < count * 8; i++) {
2041 /***** ECMULT TESTS *****/
2043 void run_ecmult_chain(void) {
2044 /* random starting point A (on the curve) */
2045 secp256k1_gej a = SECP256K1_GEJ_CONST(
2046 0x8b30bbe9, 0xae2a9906, 0x96b22f67, 0x0709dff3,
2047 0x727fd8bc, 0x04d3362c, 0x6c7bf458, 0xe2846004,
2048 0xa357ae91, 0x5c4a6528, 0x1309edf2, 0x0504740f,
2049 0x0eb33439, 0x90216b4f, 0x81063cb6, 0x5f2f7e0f
2051 /* two random initial factors xn and gn */
2052 secp256k1_scalar xn = SECP256K1_SCALAR_CONST(
2053 0x84cc5452, 0xf7fde1ed, 0xb4d38a8c, 0xe9b1b84c,
2054 0xcef31f14, 0x6e569be9, 0x705d357a, 0x42985407
2056 secp256k1_scalar gn = SECP256K1_SCALAR_CONST(
2057 0xa1e58d22, 0x553dcd42, 0xb2398062, 0x5d4c57a9,
2058 0x6e9323d4, 0x2b3152e5, 0xca2c3990, 0xedc7c9de
2060 /* two small multipliers to be applied to xn and gn in every iteration: */
2061 static const secp256k1_scalar xf = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0x1337);
2062 static const secp256k1_scalar gf = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0x7113);
2063 /* accumulators with the resulting coefficients to A and G */
2064 secp256k1_scalar ae = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1);
2065 secp256k1_scalar ge = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
2071 /* the point being computed */
2073 for (i = 0; i < 200*count; i++) {
2074 /* in each iteration, compute X = xn*X + gn*G; */
2075 secp256k1_ecmult(&ctx->ecmult_ctx, &x, &x, &xn, &gn);
2076 /* also compute ae and ge: the actual accumulated factors for A and G */
2077 /* if X was (ae*A+ge*G), xn*X + gn*G results in (xn*ae*A + (xn*ge+gn)*G) */
2078 secp256k1_scalar_mul(&ae, &ae, &xn);
2079 secp256k1_scalar_mul(&ge, &ge, &xn);
2080 secp256k1_scalar_add(&ge, &ge, &gn);
2081 /* modify xn and gn */
2082 secp256k1_scalar_mul(&xn, &xn, &xf);
2083 secp256k1_scalar_mul(&gn, &gn, &gf);
2087 /* expected result after 19999 iterations */
2088 secp256k1_gej rp = SECP256K1_GEJ_CONST(
2089 0xD6E96687, 0xF9B10D09, 0x2A6F3543, 0x9D86CEBE,
2090 0xA4535D0D, 0x409F5358, 0x6440BD74, 0xB933E830,
2091 0xB95CBCA2, 0xC77DA786, 0x539BE8FD, 0x53354D2D,
2092 0x3B4F566A, 0xE6580454, 0x07ED6015, 0xEE1B2A88
2095 secp256k1_gej_neg(&rp, &rp);
2096 secp256k1_gej_add_var(&rp, &rp, &x, NULL);
2097 CHECK(secp256k1_gej_is_infinity(&rp));
2100 /* redo the computation, but directly with the resulting ae and ge coefficients: */
2101 secp256k1_ecmult(&ctx->ecmult_ctx, &x2, &a, &ae, &ge);
2102 secp256k1_gej_neg(&x2, &x2);
2103 secp256k1_gej_add_var(&x2, &x2, &x, NULL);
2104 CHECK(secp256k1_gej_is_infinity(&x2));
2107 void test_point_times_order(const secp256k1_gej *point) {
2108 /* X * (point + G) + (order-X) * (pointer + G) = 0 */
2110 secp256k1_scalar nx;
2111 secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
2112 secp256k1_scalar one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1);
2113 secp256k1_gej res1, res2;
2115 unsigned char pub[65];
2117 random_scalar_order_test(&x);
2118 secp256k1_scalar_negate(&nx, &x);
2119 secp256k1_ecmult(&ctx->ecmult_ctx, &res1, point, &x, &x); /* calc res1 = x * point + x * G; */
2120 secp256k1_ecmult(&ctx->ecmult_ctx, &res2, point, &nx, &nx); /* calc res2 = (order - x) * point + (order - x) * G; */
2121 secp256k1_gej_add_var(&res1, &res1, &res2, NULL);
2122 CHECK(secp256k1_gej_is_infinity(&res1));
2123 CHECK(secp256k1_gej_is_valid_var(&res1) == 0);
2124 secp256k1_ge_set_gej(&res3, &res1);
2125 CHECK(secp256k1_ge_is_infinity(&res3));
2126 CHECK(secp256k1_ge_is_valid_var(&res3) == 0);
2127 CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 0) == 0);
2129 CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 1) == 0);
2130 /* check zero/one edge cases */
2131 secp256k1_ecmult(&ctx->ecmult_ctx, &res1, point, &zero, &zero);
2132 secp256k1_ge_set_gej(&res3, &res1);
2133 CHECK(secp256k1_ge_is_infinity(&res3));
2134 secp256k1_ecmult(&ctx->ecmult_ctx, &res1, point, &one, &zero);
2135 secp256k1_ge_set_gej(&res3, &res1);
2136 ge_equals_gej(&res3, point);
2137 secp256k1_ecmult(&ctx->ecmult_ctx, &res1, point, &zero, &one);
2138 secp256k1_ge_set_gej(&res3, &res1);
2139 ge_equals_ge(&res3, &secp256k1_ge_const_g);
2142 void run_point_times_order(void) {
2144 secp256k1_fe x = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 2);
2145 static const secp256k1_fe xr = SECP256K1_FE_CONST(
2146 0x7603CB59, 0xB0EF6C63, 0xFE608479, 0x2A0C378C,
2147 0xDB3233A8, 0x0F8A9A09, 0xA877DEAD, 0x31B38C45
2149 for (i = 0; i < 500; i++) {
2151 if (secp256k1_ge_set_xo_var(&p, &x, 1)) {
2153 CHECK(secp256k1_ge_is_valid_var(&p));
2154 secp256k1_gej_set_ge(&j, &p);
2155 CHECK(secp256k1_gej_is_valid_var(&j));
2156 test_point_times_order(&j);
2158 secp256k1_fe_sqr(&x, &x);
2160 secp256k1_fe_normalize_var(&x);
2161 CHECK(secp256k1_fe_equal_var(&x, &xr));
2164 void ecmult_const_random_mult(void) {
2165 /* random starting point A (on the curve) */
2166 secp256k1_ge a = SECP256K1_GE_CONST(
2167 0x6d986544, 0x57ff52b8, 0xcf1b8126, 0x5b802a5b,
2168 0xa97f9263, 0xb1e88044, 0x93351325, 0x91bc450a,
2169 0x535c59f7, 0x325e5d2b, 0xc391fbe8, 0x3c12787c,
2170 0x337e4a98, 0xe82a9011, 0x0123ba37, 0xdd769c7d
2172 /* random initial factor xn */
2173 secp256k1_scalar xn = SECP256K1_SCALAR_CONST(
2174 0x649d4f77, 0xc4242df7, 0x7f2079c9, 0x14530327,
2175 0xa31b876a, 0xd2d8ce2a, 0x2236d5c6, 0xd7b2029b
2177 /* expected xn * A (from sage) */
2178 secp256k1_ge expected_b = SECP256K1_GE_CONST(
2179 0x23773684, 0x4d209dc7, 0x098a786f, 0x20d06fcd,
2180 0x070a38bf, 0xc11ac651, 0x03004319, 0x1e2a8786,
2181 0xed8c3b8e, 0xc06dd57b, 0xd06ea66e, 0x45492b0f,
2182 0xb84e4e1b, 0xfb77e21f, 0x96baae2a, 0x63dec956
2185 secp256k1_ecmult_const(&b, &a, &xn);
2187 CHECK(secp256k1_ge_is_valid_var(&a));
2188 ge_equals_gej(&expected_b, &b);
2191 void ecmult_const_commutativity(void) {
2198 random_scalar_order_test(&a);
2199 random_scalar_order_test(&b);
2201 secp256k1_ecmult_const(&res1, &secp256k1_ge_const_g, &a);
2202 secp256k1_ecmult_const(&res2, &secp256k1_ge_const_g, &b);
2203 secp256k1_ge_set_gej(&mid1, &res1);
2204 secp256k1_ge_set_gej(&mid2, &res2);
2205 secp256k1_ecmult_const(&res1, &mid1, &b);
2206 secp256k1_ecmult_const(&res2, &mid2, &a);
2207 secp256k1_ge_set_gej(&mid1, &res1);
2208 secp256k1_ge_set_gej(&mid2, &res2);
2209 ge_equals_ge(&mid1, &mid2);
2212 void ecmult_const_mult_zero_one(void) {
2213 secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
2214 secp256k1_scalar one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1);
2215 secp256k1_scalar negone;
2219 secp256k1_scalar_negate(&negone, &one);
2221 random_group_element_test(&point);
2222 secp256k1_ecmult_const(&res1, &point, &zero);
2223 secp256k1_ge_set_gej(&res2, &res1);
2224 CHECK(secp256k1_ge_is_infinity(&res2));
2225 secp256k1_ecmult_const(&res1, &point, &one);
2226 secp256k1_ge_set_gej(&res2, &res1);
2227 ge_equals_ge(&res2, &point);
2228 secp256k1_ecmult_const(&res1, &point, &negone);
2229 secp256k1_gej_neg(&res1, &res1);
2230 secp256k1_ge_set_gej(&res2, &res1);
2231 ge_equals_ge(&res2, &point);
2234 void ecmult_const_chain_multiply(void) {
2235 /* Check known result (randomly generated test problem from sage) */
2236 const secp256k1_scalar scalar = SECP256K1_SCALAR_CONST(
2237 0x4968d524, 0x2abf9b7a, 0x466abbcf, 0x34b11b6d,
2238 0xcd83d307, 0x827bed62, 0x05fad0ce, 0x18fae63b
2240 const secp256k1_gej expected_point = SECP256K1_GEJ_CONST(
2241 0x5494c15d, 0x32099706, 0xc2395f94, 0x348745fd,
2242 0x757ce30e, 0x4e8c90fb, 0xa2bad184, 0xf883c69f,
2243 0x5d195d20, 0xe191bf7f, 0x1be3e55f, 0x56a80196,
2244 0x6071ad01, 0xf1462f66, 0xc997fa94, 0xdb858435
2246 secp256k1_gej point;
2250 secp256k1_gej_set_ge(&point, &secp256k1_ge_const_g);
2251 for (i = 0; i < 100; ++i) {
2253 secp256k1_ge_set_gej(&tmp, &point);
2254 secp256k1_ecmult_const(&point, &tmp, &scalar);
2256 secp256k1_ge_set_gej(&res, &point);
2257 ge_equals_gej(&res, &expected_point);
2260 void run_ecmult_const_tests(void) {
2261 ecmult_const_mult_zero_one();
2262 ecmult_const_random_mult();
2263 ecmult_const_commutativity();
2264 ecmult_const_chain_multiply();
2267 void test_wnaf(const secp256k1_scalar *number, int w) {
2268 secp256k1_scalar x, two, t;
2273 secp256k1_scalar_set_int(&x, 0);
2274 secp256k1_scalar_set_int(&two, 2);
2275 bits = secp256k1_ecmult_wnaf(wnaf, 256, number, w);
2277 for (i = bits-1; i >= 0; i--) {
2279 secp256k1_scalar_mul(&x, &x, &two);
2281 CHECK(zeroes == -1 || zeroes >= w-1); /* check that distance between non-zero elements is at least w-1 */
2283 CHECK((v & 1) == 1); /* check non-zero elements are odd */
2284 CHECK(v <= (1 << (w-1)) - 1); /* check range below */
2285 CHECK(v >= -(1 << (w-1)) - 1); /* check range above */
2287 CHECK(zeroes != -1); /* check that no unnecessary zero padding exists */
2291 secp256k1_scalar_set_int(&t, v);
2293 secp256k1_scalar_set_int(&t, -v);
2294 secp256k1_scalar_negate(&t, &t);
2296 secp256k1_scalar_add(&x, &x, &t);
2298 CHECK(secp256k1_scalar_eq(&x, number)); /* check that wnaf represents number */
2301 void test_constant_wnaf_negate(const secp256k1_scalar *number) {
2302 secp256k1_scalar neg1 = *number;
2303 secp256k1_scalar neg2 = *number;
2307 if (!secp256k1_scalar_get_bits(&neg1, 0, 1)) {
2308 secp256k1_scalar_negate(&neg1, &neg1);
2311 sign2 = secp256k1_scalar_cond_negate(&neg2, secp256k1_scalar_is_even(&neg2));
2312 CHECK(sign1 == sign2);
2313 CHECK(secp256k1_scalar_eq(&neg1, &neg2));
2316 void test_constant_wnaf(const secp256k1_scalar *number, int w) {
2317 secp256k1_scalar x, shift;
2318 int wnaf[256] = {0};
2320 #ifdef USE_ENDOMORPHISM
2323 secp256k1_scalar num = *number;
2325 secp256k1_scalar_set_int(&x, 0);
2326 secp256k1_scalar_set_int(&shift, 1 << w);
2327 /* With USE_ENDOMORPHISM on we only consider 128-bit numbers */
2328 #ifdef USE_ENDOMORPHISM
2329 for (i = 0; i < 16; ++i) {
2330 secp256k1_scalar_shr_int(&num, 8);
2332 skew = secp256k1_wnaf_const(wnaf, num, w);
2334 secp256k1_wnaf_const(wnaf, num, w);
2337 for (i = WNAF_SIZE(w); i >= 0; --i) {
2340 CHECK(v != 0); /* check nonzero */
2341 CHECK(v & 1); /* check parity */
2342 CHECK(v > -(1 << w)); /* check range above */
2343 CHECK(v < (1 << w)); /* check range below */
2345 secp256k1_scalar_mul(&x, &x, &shift);
2347 secp256k1_scalar_set_int(&t, v);
2349 secp256k1_scalar_set_int(&t, -v);
2350 secp256k1_scalar_negate(&t, &t);
2352 secp256k1_scalar_add(&x, &x, &t);
2354 #ifdef USE_ENDOMORPHISM
2355 /* Skew num because when encoding 128-bit numbers as odd we use an offset */
2356 secp256k1_scalar_cadd_bit(&num, skew == 2, 1);
2358 CHECK(secp256k1_scalar_eq(&x, &num));
2361 void run_wnaf(void) {
2363 secp256k1_scalar n = {{0}};
2365 /* Sanity check: 1 and 2 are the smallest odd and even numbers and should
2366 * have easier-to-diagnose failure modes */
2368 test_constant_wnaf(&n, 4);
2370 test_constant_wnaf(&n, 4);
2372 for (i = 0; i < count; i++) {
2373 random_scalar_order(&n);
2374 test_wnaf(&n, 4+(i%10));
2375 test_constant_wnaf_negate(&n);
2376 test_constant_wnaf(&n, 4 + (i % 10));
2378 secp256k1_scalar_set_int(&n, 0);
2379 CHECK(secp256k1_scalar_cond_negate(&n, 1) == -1);
2380 CHECK(secp256k1_scalar_is_zero(&n));
2381 CHECK(secp256k1_scalar_cond_negate(&n, 0) == 1);
2382 CHECK(secp256k1_scalar_is_zero(&n));
2385 void test_ecmult_constants(void) {
2386 /* Test ecmult_gen() for [0..36) and [order-36..0). */
2392 secp256k1_ge_neg(&ng, &secp256k1_ge_const_g);
2393 for (i = 0; i < 36; i++ ) {
2394 secp256k1_scalar_set_int(&x, i);
2395 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &r, &x);
2396 for (j = 0; j < i; j++) {
2398 ge_equals_gej(&secp256k1_ge_const_g, &r);
2400 secp256k1_gej_add_ge(&r, &r, &ng);
2402 CHECK(secp256k1_gej_is_infinity(&r));
2404 for (i = 1; i <= 36; i++ ) {
2405 secp256k1_scalar_set_int(&x, i);
2406 secp256k1_scalar_negate(&x, &x);
2407 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &r, &x);
2408 for (j = 0; j < i; j++) {
2410 ge_equals_gej(&ng, &r);
2412 secp256k1_gej_add_ge(&r, &r, &secp256k1_ge_const_g);
2414 CHECK(secp256k1_gej_is_infinity(&r));
2418 void run_ecmult_constants(void) {
2419 test_ecmult_constants();
2422 void test_ecmult_gen_blind(void) {
2423 /* Test ecmult_gen() blinding and confirm that the blinding changes, the affine points match, and the z's don't match. */
2424 secp256k1_scalar key;
2426 unsigned char seed32[32];
2428 secp256k1_gej pgej2;
2431 random_scalar_order_test(&key);
2432 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pgej, &key);
2433 secp256k1_rand256(seed32);
2434 b = ctx->ecmult_gen_ctx.blind;
2435 i = ctx->ecmult_gen_ctx.initial;
2436 secp256k1_ecmult_gen_blind(&ctx->ecmult_gen_ctx, seed32);
2437 CHECK(!secp256k1_scalar_eq(&b, &ctx->ecmult_gen_ctx.blind));
2438 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pgej2, &key);
2439 CHECK(!gej_xyz_equals_gej(&pgej, &pgej2));
2440 CHECK(!gej_xyz_equals_gej(&i, &ctx->ecmult_gen_ctx.initial));
2441 secp256k1_ge_set_gej(&pge, &pgej);
2442 ge_equals_gej(&pge, &pgej2);
2445 void test_ecmult_gen_blind_reset(void) {
2446 /* Test ecmult_gen() blinding reset and confirm that the blinding is consistent. */
2448 secp256k1_gej initial;
2449 secp256k1_ecmult_gen_blind(&ctx->ecmult_gen_ctx, 0);
2450 b = ctx->ecmult_gen_ctx.blind;
2451 initial = ctx->ecmult_gen_ctx.initial;
2452 secp256k1_ecmult_gen_blind(&ctx->ecmult_gen_ctx, 0);
2453 CHECK(secp256k1_scalar_eq(&b, &ctx->ecmult_gen_ctx.blind));
2454 CHECK(gej_xyz_equals_gej(&initial, &ctx->ecmult_gen_ctx.initial));
2457 void run_ecmult_gen_blind(void) {
2459 test_ecmult_gen_blind_reset();
2460 for (i = 0; i < 10; i++) {
2461 test_ecmult_gen_blind();
2465 #ifdef USE_ENDOMORPHISM
2466 /***** ENDOMORPHISH TESTS *****/
2467 void test_scalar_split(void) {
2468 secp256k1_scalar full;
2469 secp256k1_scalar s1, slam;
2470 const unsigned char zero[32] = {0};
2471 unsigned char tmp[32];
2473 random_scalar_order_test(&full);
2474 secp256k1_scalar_split_lambda(&s1, &slam, &full);
2476 /* check that both are <= 128 bits in size */
2477 if (secp256k1_scalar_is_high(&s1)) {
2478 secp256k1_scalar_negate(&s1, &s1);
2480 if (secp256k1_scalar_is_high(&slam)) {
2481 secp256k1_scalar_negate(&slam, &slam);
2484 secp256k1_scalar_get_b32(tmp, &s1);
2485 CHECK(memcmp(zero, tmp, 16) == 0);
2486 secp256k1_scalar_get_b32(tmp, &slam);
2487 CHECK(memcmp(zero, tmp, 16) == 0);
2490 void run_endomorphism_tests(void) {
2491 test_scalar_split();
2495 void ec_pubkey_parse_pointtest(const unsigned char *input, int xvalid, int yvalid) {
2496 unsigned char pubkeyc[65];
2497 secp256k1_pubkey pubkey;
2502 secp256k1_context_set_illegal_callback(ctx, counting_illegal_callback_fn, &ecount);
2503 for (pubkeyclen = 3; pubkeyclen <= 65; pubkeyclen++) {
2504 /* Smaller sizes are tested exhaustively elsewhere. */
2506 memcpy(&pubkeyc[1], input, 64);
2507 VG_UNDEF(&pubkeyc[pubkeyclen], 65 - pubkeyclen);
2508 for (i = 0; i < 256; i++) {
2509 /* Try all type bytes. */
2514 /* What sign does this point have? */
2515 ysign = (input[63] & 1) + 2;
2516 /* For the current type (i) do we expect parsing to work? Handled all of compressed/uncompressed/hybrid. */
2517 xpass = xvalid && (pubkeyclen == 33) && ((i & 254) == 2);
2518 /* Do we expect a parse and re-serialize as uncompressed to give a matching y? */
2519 ypass = xvalid && yvalid && ((i & 4) == ((pubkeyclen == 65) << 2)) &&
2520 ((i == 4) || ((i & 251) == ysign)) && ((pubkeyclen == 33) || (pubkeyclen == 65));
2521 if (xpass || ypass) {
2522 /* These cases must parse. */
2523 unsigned char pubkeyo[65];
2525 memset(&pubkey, 0, sizeof(pubkey));
2526 VG_UNDEF(&pubkey, sizeof(pubkey));
2528 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, pubkeyclen) == 1);
2529 VG_CHECK(&pubkey, sizeof(pubkey));
2531 VG_UNDEF(pubkeyo, 65);
2532 CHECK(secp256k1_ec_pubkey_serialize(ctx, pubkeyo, &outl, &pubkey, SECP256K1_EC_COMPRESSED) == 1);
2533 VG_CHECK(pubkeyo, outl);
2535 CHECK(memcmp(&pubkeyo[1], &pubkeyc[1], 32) == 0);
2536 CHECK((pubkeyclen != 33) || (pubkeyo[0] == pubkeyc[0]));
2538 /* This test isn't always done because we decode with alternative signs, so the y won't match. */
2539 CHECK(pubkeyo[0] == ysign);
2540 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 1);
2541 memset(&pubkey, 0, sizeof(pubkey));
2542 VG_UNDEF(&pubkey, sizeof(pubkey));
2543 secp256k1_pubkey_save(&pubkey, &ge);
2544 VG_CHECK(&pubkey, sizeof(pubkey));
2546 VG_UNDEF(pubkeyo, 65);
2547 CHECK(secp256k1_ec_pubkey_serialize(ctx, pubkeyo, &outl, &pubkey, SECP256K1_EC_UNCOMPRESSED) == 1);
2548 VG_CHECK(pubkeyo, outl);
2550 CHECK(pubkeyo[0] == 4);
2551 CHECK(memcmp(&pubkeyo[1], input, 64) == 0);
2555 /* These cases must fail to parse. */
2556 memset(&pubkey, 0xfe, sizeof(pubkey));
2558 VG_UNDEF(&pubkey, sizeof(pubkey));
2559 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, pubkeyclen) == 0);
2560 VG_CHECK(&pubkey, sizeof(pubkey));
2562 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2567 secp256k1_context_set_illegal_callback(ctx, NULL, NULL);
2570 void run_ec_pubkey_parse_test(void) {
2571 #define SECP256K1_EC_PARSE_TEST_NVALID (12)
2572 const unsigned char valid[SECP256K1_EC_PARSE_TEST_NVALID][64] = {
2574 /* Point with leading and trailing zeros in x and y serialization. */
2575 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x42, 0x52,
2576 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2577 0x00, 0x00, 0x64, 0xef, 0xa1, 0x7b, 0x77, 0x61, 0xe1, 0xe4, 0x27, 0x06, 0x98, 0x9f, 0xb4, 0x83,
2578 0xb8, 0xd2, 0xd4, 0x9b, 0xf7, 0x8f, 0xae, 0x98, 0x03, 0xf0, 0x99, 0xb8, 0x34, 0xed, 0xeb, 0x00
2581 /* Point with x equal to a 3rd root of unity.*/
2582 0x7a, 0xe9, 0x6a, 0x2b, 0x65, 0x7c, 0x07, 0x10, 0x6e, 0x64, 0x47, 0x9e, 0xac, 0x34, 0x34, 0xe9,
2583 0x9c, 0xf0, 0x49, 0x75, 0x12, 0xf5, 0x89, 0x95, 0xc1, 0x39, 0x6c, 0x28, 0x71, 0x95, 0x01, 0xee,
2584 0x42, 0x18, 0xf2, 0x0a, 0xe6, 0xc6, 0x46, 0xb3, 0x63, 0xdb, 0x68, 0x60, 0x58, 0x22, 0xfb, 0x14,
2585 0x26, 0x4c, 0xa8, 0xd2, 0x58, 0x7f, 0xdd, 0x6f, 0xbc, 0x75, 0x0d, 0x58, 0x7e, 0x76, 0xa7, 0xee,
2588 /* Point with largest x. (1/2) */
2589 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2590 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2c,
2591 0x0e, 0x99, 0x4b, 0x14, 0xea, 0x72, 0xf8, 0xc3, 0xeb, 0x95, 0xc7, 0x1e, 0xf6, 0x92, 0x57, 0x5e,
2592 0x77, 0x50, 0x58, 0x33, 0x2d, 0x7e, 0x52, 0xd0, 0x99, 0x5c, 0xf8, 0x03, 0x88, 0x71, 0xb6, 0x7d,
2595 /* Point with largest x. (2/2) */
2596 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2597 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2c,
2598 0xf1, 0x66, 0xb4, 0xeb, 0x15, 0x8d, 0x07, 0x3c, 0x14, 0x6a, 0x38, 0xe1, 0x09, 0x6d, 0xa8, 0xa1,
2599 0x88, 0xaf, 0xa7, 0xcc, 0xd2, 0x81, 0xad, 0x2f, 0x66, 0xa3, 0x07, 0xfb, 0x77, 0x8e, 0x45, 0xb2,
2602 /* Point with smallest x. (1/2) */
2603 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2604 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2605 0x42, 0x18, 0xf2, 0x0a, 0xe6, 0xc6, 0x46, 0xb3, 0x63, 0xdb, 0x68, 0x60, 0x58, 0x22, 0xfb, 0x14,
2606 0x26, 0x4c, 0xa8, 0xd2, 0x58, 0x7f, 0xdd, 0x6f, 0xbc, 0x75, 0x0d, 0x58, 0x7e, 0x76, 0xa7, 0xee,
2609 /* Point with smallest x. (2/2) */
2610 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2611 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2612 0xbd, 0xe7, 0x0d, 0xf5, 0x19, 0x39, 0xb9, 0x4c, 0x9c, 0x24, 0x97, 0x9f, 0xa7, 0xdd, 0x04, 0xeb,
2613 0xd9, 0xb3, 0x57, 0x2d, 0xa7, 0x80, 0x22, 0x90, 0x43, 0x8a, 0xf2, 0xa6, 0x81, 0x89, 0x54, 0x41,
2616 /* Point with largest y. (1/3) */
2617 0x1f, 0xe1, 0xe5, 0xef, 0x3f, 0xce, 0xb5, 0xc1, 0x35, 0xab, 0x77, 0x41, 0x33, 0x3c, 0xe5, 0xa6,
2618 0xe8, 0x0d, 0x68, 0x16, 0x76, 0x53, 0xf6, 0xb2, 0xb2, 0x4b, 0xcb, 0xcf, 0xaa, 0xaf, 0xf5, 0x07,
2619 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2620 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2623 /* Point with largest y. (2/3) */
2624 0xcb, 0xb0, 0xde, 0xab, 0x12, 0x57, 0x54, 0xf1, 0xfd, 0xb2, 0x03, 0x8b, 0x04, 0x34, 0xed, 0x9c,
2625 0xb3, 0xfb, 0x53, 0xab, 0x73, 0x53, 0x91, 0x12, 0x99, 0x94, 0xa5, 0x35, 0xd9, 0x25, 0xf6, 0x73,
2626 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2627 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2630 /* Point with largest y. (3/3) */
2631 0x14, 0x6d, 0x3b, 0x65, 0xad, 0xd9, 0xf5, 0x4c, 0xcc, 0xa2, 0x85, 0x33, 0xc8, 0x8e, 0x2c, 0xbc,
2632 0x63, 0xf7, 0x44, 0x3e, 0x16, 0x58, 0x78, 0x3a, 0xb4, 0x1f, 0x8e, 0xf9, 0x7c, 0x2a, 0x10, 0xb5,
2633 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2634 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2637 /* Point with smallest y. (1/3) */
2638 0x1f, 0xe1, 0xe5, 0xef, 0x3f, 0xce, 0xb5, 0xc1, 0x35, 0xab, 0x77, 0x41, 0x33, 0x3c, 0xe5, 0xa6,
2639 0xe8, 0x0d, 0x68, 0x16, 0x76, 0x53, 0xf6, 0xb2, 0xb2, 0x4b, 0xcb, 0xcf, 0xaa, 0xaf, 0xf5, 0x07,
2640 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2641 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2644 /* Point with smallest y. (2/3) */
2645 0xcb, 0xb0, 0xde, 0xab, 0x12, 0x57, 0x54, 0xf1, 0xfd, 0xb2, 0x03, 0x8b, 0x04, 0x34, 0xed, 0x9c,
2646 0xb3, 0xfb, 0x53, 0xab, 0x73, 0x53, 0x91, 0x12, 0x99, 0x94, 0xa5, 0x35, 0xd9, 0x25, 0xf6, 0x73,
2647 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2648 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2651 /* Point with smallest y. (3/3) */
2652 0x14, 0x6d, 0x3b, 0x65, 0xad, 0xd9, 0xf5, 0x4c, 0xcc, 0xa2, 0x85, 0x33, 0xc8, 0x8e, 0x2c, 0xbc,
2653 0x63, 0xf7, 0x44, 0x3e, 0x16, 0x58, 0x78, 0x3a, 0xb4, 0x1f, 0x8e, 0xf9, 0x7c, 0x2a, 0x10, 0xb5,
2654 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2655 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01
2658 #define SECP256K1_EC_PARSE_TEST_NXVALID (4)
2659 const unsigned char onlyxvalid[SECP256K1_EC_PARSE_TEST_NXVALID][64] = {
2661 /* Valid if y overflow ignored (y = 1 mod p). (1/3) */
2662 0x1f, 0xe1, 0xe5, 0xef, 0x3f, 0xce, 0xb5, 0xc1, 0x35, 0xab, 0x77, 0x41, 0x33, 0x3c, 0xe5, 0xa6,
2663 0xe8, 0x0d, 0x68, 0x16, 0x76, 0x53, 0xf6, 0xb2, 0xb2, 0x4b, 0xcb, 0xcf, 0xaa, 0xaf, 0xf5, 0x07,
2664 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2665 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2668 /* Valid if y overflow ignored (y = 1 mod p). (2/3) */
2669 0xcb, 0xb0, 0xde, 0xab, 0x12, 0x57, 0x54, 0xf1, 0xfd, 0xb2, 0x03, 0x8b, 0x04, 0x34, 0xed, 0x9c,
2670 0xb3, 0xfb, 0x53, 0xab, 0x73, 0x53, 0x91, 0x12, 0x99, 0x94, 0xa5, 0x35, 0xd9, 0x25, 0xf6, 0x73,
2671 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2672 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2675 /* Valid if y overflow ignored (y = 1 mod p). (3/3)*/
2676 0x14, 0x6d, 0x3b, 0x65, 0xad, 0xd9, 0xf5, 0x4c, 0xcc, 0xa2, 0x85, 0x33, 0xc8, 0x8e, 0x2c, 0xbc,
2677 0x63, 0xf7, 0x44, 0x3e, 0x16, 0x58, 0x78, 0x3a, 0xb4, 0x1f, 0x8e, 0xf9, 0x7c, 0x2a, 0x10, 0xb5,
2678 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2679 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2682 /* x on curve, y is from y^2 = x^3 + 8. */
2683 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2684 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2685 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2686 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03
2689 #define SECP256K1_EC_PARSE_TEST_NINVALID (7)
2690 const unsigned char invalid[SECP256K1_EC_PARSE_TEST_NINVALID][64] = {
2692 /* x is third root of -8, y is -1 * (x^3+7); also on the curve for y^2 = x^3 + 9. */
2693 0x0a, 0x2d, 0x2b, 0xa9, 0x35, 0x07, 0xf1, 0xdf, 0x23, 0x37, 0x70, 0xc2, 0xa7, 0x97, 0x96, 0x2c,
2694 0xc6, 0x1f, 0x6d, 0x15, 0xda, 0x14, 0xec, 0xd4, 0x7d, 0x8d, 0x27, 0xae, 0x1c, 0xd5, 0xf8, 0x53,
2695 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2696 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2699 /* Valid if x overflow ignored (x = 1 mod p). */
2700 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2701 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2702 0x42, 0x18, 0xf2, 0x0a, 0xe6, 0xc6, 0x46, 0xb3, 0x63, 0xdb, 0x68, 0x60, 0x58, 0x22, 0xfb, 0x14,
2703 0x26, 0x4c, 0xa8, 0xd2, 0x58, 0x7f, 0xdd, 0x6f, 0xbc, 0x75, 0x0d, 0x58, 0x7e, 0x76, 0xa7, 0xee,
2706 /* Valid if x overflow ignored (x = 1 mod p). */
2707 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2708 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2709 0xbd, 0xe7, 0x0d, 0xf5, 0x19, 0x39, 0xb9, 0x4c, 0x9c, 0x24, 0x97, 0x9f, 0xa7, 0xdd, 0x04, 0xeb,
2710 0xd9, 0xb3, 0x57, 0x2d, 0xa7, 0x80, 0x22, 0x90, 0x43, 0x8a, 0xf2, 0xa6, 0x81, 0x89, 0x54, 0x41,
2713 /* x is -1, y is the result of the sqrt ladder; also on the curve for y^2 = x^3 - 5. */
2714 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2715 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2716 0xf4, 0x84, 0x14, 0x5c, 0xb0, 0x14, 0x9b, 0x82, 0x5d, 0xff, 0x41, 0x2f, 0xa0, 0x52, 0xa8, 0x3f,
2717 0xcb, 0x72, 0xdb, 0x61, 0xd5, 0x6f, 0x37, 0x70, 0xce, 0x06, 0x6b, 0x73, 0x49, 0xa2, 0xaa, 0x28,
2720 /* x is -1, y is the result of the sqrt ladder; also on the curve for y^2 = x^3 - 5. */
2721 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2722 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2723 0x0b, 0x7b, 0xeb, 0xa3, 0x4f, 0xeb, 0x64, 0x7d, 0xa2, 0x00, 0xbe, 0xd0, 0x5f, 0xad, 0x57, 0xc0,
2724 0x34, 0x8d, 0x24, 0x9e, 0x2a, 0x90, 0xc8, 0x8f, 0x31, 0xf9, 0x94, 0x8b, 0xb6, 0x5d, 0x52, 0x07,
2727 /* x is zero, y is the result of the sqrt ladder; also on the curve for y^2 = x^3 - 7. */
2728 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2729 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2730 0x8f, 0x53, 0x7e, 0xef, 0xdf, 0xc1, 0x60, 0x6a, 0x07, 0x27, 0xcd, 0x69, 0xb4, 0xa7, 0x33, 0x3d,
2731 0x38, 0xed, 0x44, 0xe3, 0x93, 0x2a, 0x71, 0x79, 0xee, 0xcb, 0x4b, 0x6f, 0xba, 0x93, 0x60, 0xdc,
2734 /* x is zero, y is the result of the sqrt ladder; also on the curve for y^2 = x^3 - 7. */
2735 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2736 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2737 0x70, 0xac, 0x81, 0x10, 0x20, 0x3e, 0x9f, 0x95, 0xf8, 0xd8, 0x32, 0x96, 0x4b, 0x58, 0xcc, 0xc2,
2738 0xc7, 0x12, 0xbb, 0x1c, 0x6c, 0xd5, 0x8e, 0x86, 0x11, 0x34, 0xb4, 0x8f, 0x45, 0x6c, 0x9b, 0x53
2741 const unsigned char pubkeyc[66] = {
2742 /* Serialization of G. */
2743 0x04, 0x79, 0xBE, 0x66, 0x7E, 0xF9, 0xDC, 0xBB, 0xAC, 0x55, 0xA0, 0x62, 0x95, 0xCE, 0x87, 0x0B,
2744 0x07, 0x02, 0x9B, 0xFC, 0xDB, 0x2D, 0xCE, 0x28, 0xD9, 0x59, 0xF2, 0x81, 0x5B, 0x16, 0xF8, 0x17,
2745 0x98, 0x48, 0x3A, 0xDA, 0x77, 0x26, 0xA3, 0xC4, 0x65, 0x5D, 0xA4, 0xFB, 0xFC, 0x0E, 0x11, 0x08,
2746 0xA8, 0xFD, 0x17, 0xB4, 0x48, 0xA6, 0x85, 0x54, 0x19, 0x9C, 0x47, 0xD0, 0x8F, 0xFB, 0x10, 0xD4,
2749 unsigned char sout[65];
2750 unsigned char shortkey[2];
2752 secp256k1_pubkey pubkey;
2758 /* Nothing should be reading this far into pubkeyc. */
2759 VG_UNDEF(&pubkeyc[65], 1);
2760 secp256k1_context_set_illegal_callback(ctx, counting_illegal_callback_fn, &ecount);
2761 /* Zero length claimed, fail, zeroize, no illegal arg error. */
2762 memset(&pubkey, 0xfe, sizeof(pubkey));
2764 VG_UNDEF(shortkey, 2);
2765 VG_UNDEF(&pubkey, sizeof(pubkey));
2766 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, shortkey, 0) == 0);
2767 VG_CHECK(&pubkey, sizeof(pubkey));
2769 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2771 /* Length one claimed, fail, zeroize, no illegal arg error. */
2772 for (i = 0; i < 256 ; i++) {
2773 memset(&pubkey, 0xfe, sizeof(pubkey));
2776 VG_UNDEF(&shortkey[1], 1);
2777 VG_UNDEF(&pubkey, sizeof(pubkey));
2778 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, shortkey, 1) == 0);
2779 VG_CHECK(&pubkey, sizeof(pubkey));
2781 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2784 /* Length two claimed, fail, zeroize, no illegal arg error. */
2785 for (i = 0; i < 65536 ; i++) {
2786 memset(&pubkey, 0xfe, sizeof(pubkey));
2788 shortkey[0] = i & 255;
2789 shortkey[1] = i >> 8;
2790 VG_UNDEF(&pubkey, sizeof(pubkey));
2791 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, shortkey, 2) == 0);
2792 VG_CHECK(&pubkey, sizeof(pubkey));
2794 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2797 memset(&pubkey, 0xfe, sizeof(pubkey));
2799 VG_UNDEF(&pubkey, sizeof(pubkey));
2800 /* 33 bytes claimed on otherwise valid input starting with 0x04, fail, zeroize output, no illegal arg error. */
2801 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, 33) == 0);
2802 VG_CHECK(&pubkey, sizeof(pubkey));
2804 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2806 /* NULL pubkey, illegal arg error. Pubkey isn't rewritten before this step, since it's NULL into the parser. */
2807 CHECK(secp256k1_ec_pubkey_parse(ctx, NULL, pubkeyc, 65) == 0);
2809 /* NULL input string. Illegal arg and zeroize output. */
2810 memset(&pubkey, 0xfe, sizeof(pubkey));
2812 VG_UNDEF(&pubkey, sizeof(pubkey));
2813 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, NULL, 65) == 0);
2814 VG_CHECK(&pubkey, sizeof(pubkey));
2816 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2818 /* 64 bytes claimed on input starting with 0x04, fail, zeroize output, no illegal arg error. */
2819 memset(&pubkey, 0xfe, sizeof(pubkey));
2821 VG_UNDEF(&pubkey, sizeof(pubkey));
2822 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, 64) == 0);
2823 VG_CHECK(&pubkey, sizeof(pubkey));
2825 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2827 /* 66 bytes claimed, fail, zeroize output, no illegal arg error. */
2828 memset(&pubkey, 0xfe, sizeof(pubkey));
2830 VG_UNDEF(&pubkey, sizeof(pubkey));
2831 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, 66) == 0);
2832 VG_CHECK(&pubkey, sizeof(pubkey));
2834 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2837 memset(&pubkey, 0, sizeof(pubkey));
2839 VG_UNDEF(&pubkey, sizeof(pubkey));
2840 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, 65) == 1);
2841 VG_CHECK(&pubkey, sizeof(pubkey));
2843 VG_UNDEF(&ge, sizeof(ge));
2844 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 1);
2845 VG_CHECK(&ge.x, sizeof(ge.x));
2846 VG_CHECK(&ge.y, sizeof(ge.y));
2847 VG_CHECK(&ge.infinity, sizeof(ge.infinity));
2848 ge_equals_ge(&secp256k1_ge_const_g, &ge);
2850 /* secp256k1_ec_pubkey_serialize illegal args. */
2853 CHECK(secp256k1_ec_pubkey_serialize(ctx, NULL, &len, &pubkey, SECP256K1_EC_UNCOMPRESSED) == 0);
2856 CHECK(secp256k1_ec_pubkey_serialize(ctx, sout, NULL, &pubkey, SECP256K1_EC_UNCOMPRESSED) == 0);
2860 CHECK(secp256k1_ec_pubkey_serialize(ctx, sout, &len, NULL, SECP256K1_EC_UNCOMPRESSED) == 0);
2865 CHECK(secp256k1_ec_pubkey_serialize(ctx, sout, &len, &pubkey, ~0) == 0);
2870 CHECK(secp256k1_ec_pubkey_serialize(ctx, sout, &len, &pubkey, SECP256K1_EC_UNCOMPRESSED) == 1);
2874 /* Multiple illegal args. Should still set arg error only once. */
2877 CHECK(secp256k1_ec_pubkey_parse(ctx, NULL, NULL, 65) == 0);
2879 /* Does the illegal arg callback actually change the behavior? */
2880 secp256k1_context_set_illegal_callback(ctx, uncounting_illegal_callback_fn, &ecount2);
2881 CHECK(secp256k1_ec_pubkey_parse(ctx, NULL, NULL, 65) == 0);
2883 CHECK(ecount2 == 10);
2884 secp256k1_context_set_illegal_callback(ctx, NULL, NULL);
2885 /* Try a bunch of prefabbed points with all possible encodings. */
2886 for (i = 0; i < SECP256K1_EC_PARSE_TEST_NVALID; i++) {
2887 ec_pubkey_parse_pointtest(valid[i], 1, 1);
2889 for (i = 0; i < SECP256K1_EC_PARSE_TEST_NXVALID; i++) {
2890 ec_pubkey_parse_pointtest(onlyxvalid[i], 1, 0);
2892 for (i = 0; i < SECP256K1_EC_PARSE_TEST_NINVALID; i++) {
2893 ec_pubkey_parse_pointtest(invalid[i], 0, 0);
2897 void run_eckey_edge_case_test(void) {
2898 const unsigned char orderc[32] = {
2899 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2900 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
2901 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
2902 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41
2904 const unsigned char zeros[sizeof(secp256k1_pubkey)] = {0x00};
2905 unsigned char ctmp[32];
2906 unsigned char ctmp2[32];
2907 secp256k1_pubkey pubkey;
2908 secp256k1_pubkey pubkey2;
2910 /* Group order is too large, reject. */
2911 CHECK(secp256k1_ec_seckey_verify(ctx, orderc) == 0);
2912 VG_UNDEF(&pubkey, sizeof(pubkey));
2913 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, orderc) == 0);
2914 VG_CHECK(&pubkey, sizeof(pubkey));
2915 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
2916 /* Maximum value is too large, reject. */
2917 memset(ctmp, 255, 32);
2918 CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 0);
2919 memset(&pubkey, 1, sizeof(pubkey));
2920 VG_UNDEF(&pubkey, sizeof(pubkey));
2921 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 0);
2922 VG_CHECK(&pubkey, sizeof(pubkey));
2923 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
2924 /* Zero is too small, reject. */
2925 memset(ctmp, 0, 32);
2926 CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 0);
2927 memset(&pubkey, 1, sizeof(pubkey));
2928 VG_UNDEF(&pubkey, sizeof(pubkey));
2929 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 0);
2930 VG_CHECK(&pubkey, sizeof(pubkey));
2931 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
2932 /* One must be accepted. */
2934 CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 1);
2935 memset(&pubkey, 0, sizeof(pubkey));
2936 VG_UNDEF(&pubkey, sizeof(pubkey));
2937 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 1);
2938 VG_CHECK(&pubkey, sizeof(pubkey));
2939 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) > 0);
2940 /* Group order + 1 is too large, reject. */
2941 memcpy(ctmp, orderc, 32);
2943 CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 0);
2944 memset(&pubkey, 1, sizeof(pubkey));
2945 VG_UNDEF(&pubkey, sizeof(pubkey));
2946 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 0);
2947 VG_CHECK(&pubkey, sizeof(pubkey));
2948 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
2949 /* -1 must be accepted. */
2951 CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 1);
2952 memset(&pubkey, 0, sizeof(pubkey));
2953 VG_UNDEF(&pubkey, sizeof(pubkey));
2954 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 1);
2955 VG_CHECK(&pubkey, sizeof(pubkey));
2956 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) > 0);
2957 /* Tweak of zero leaves the value changed. */
2958 memset(ctmp2, 0, 32);
2959 CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp, ctmp2) == 1);
2960 CHECK(memcmp(orderc, ctmp, 31) == 0 && ctmp[31] == 0x40);
2961 memcpy(&pubkey2, &pubkey, sizeof(pubkey));
2962 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 1);
2963 CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
2964 /* Multiply tweak of zero zeroizes the output. */
2965 CHECK(secp256k1_ec_privkey_tweak_mul(ctx, ctmp, ctmp2) == 0);
2966 CHECK(memcmp(zeros, ctmp, 32) == 0);
2967 CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, ctmp2) == 0);
2968 CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
2969 memcpy(&pubkey, &pubkey2, sizeof(pubkey));
2970 /* Overflowing key tweak zeroizes. */
2971 memcpy(ctmp, orderc, 32);
2973 CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp, orderc) == 0);
2974 CHECK(memcmp(zeros, ctmp, 32) == 0);
2975 memcpy(ctmp, orderc, 32);
2977 CHECK(secp256k1_ec_privkey_tweak_mul(ctx, ctmp, orderc) == 0);
2978 CHECK(memcmp(zeros, ctmp, 32) == 0);
2979 memcpy(ctmp, orderc, 32);
2981 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, orderc) == 0);
2982 CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
2983 memcpy(&pubkey, &pubkey2, sizeof(pubkey));
2984 CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, orderc) == 0);
2985 CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
2986 memcpy(&pubkey, &pubkey2, sizeof(pubkey));
2987 /* Private key tweaks results in a key of zero. */
2989 CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp2, ctmp) == 0);
2990 CHECK(memcmp(zeros, ctmp2, 32) == 0);
2992 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 0);
2993 CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
2994 memcpy(&pubkey, &pubkey2, sizeof(pubkey));
2995 /* Tweak computation wraps and results in a key of 1. */
2997 CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp2, ctmp) == 1);
2998 CHECK(memcmp(ctmp2, zeros, 31) == 0 && ctmp2[31] == 1);
3000 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 1);
3002 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey2, ctmp2) == 1);
3003 CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
3004 /* Tweak mul * 2 = 1+1. */
3005 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 1);
3007 CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey2, ctmp2) == 1);
3008 CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
3009 /* Test argument errors. */
3011 secp256k1_context_set_illegal_callback(ctx, counting_illegal_callback_fn, &ecount);
3013 /* Zeroize pubkey on parse error. */
3014 memset(&pubkey, 0, 32);
3015 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 0);
3017 CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
3018 memcpy(&pubkey, &pubkey2, sizeof(pubkey));
3019 memset(&pubkey2, 0, 32);
3020 CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey2, ctmp2) == 0);
3022 CHECK(memcmp(&pubkey2, zeros, sizeof(pubkey2)) == 0);
3023 /* Plain argument errors. */
3025 CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 1);
3027 CHECK(secp256k1_ec_seckey_verify(ctx, NULL) == 0);
3030 memset(ctmp2, 0, 32);
3032 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, NULL, ctmp2) == 0);
3034 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, NULL) == 0);
3037 memset(ctmp2, 0, 32);
3039 CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, NULL, ctmp2) == 0);
3041 CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, NULL) == 0);
3044 memset(ctmp2, 0, 32);
3045 CHECK(secp256k1_ec_privkey_tweak_add(ctx, NULL, ctmp2) == 0);
3047 CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp, NULL) == 0);
3050 memset(ctmp2, 0, 32);
3052 CHECK(secp256k1_ec_privkey_tweak_mul(ctx, NULL, ctmp2) == 0);
3054 CHECK(secp256k1_ec_privkey_tweak_mul(ctx, ctmp, NULL) == 0);
3057 CHECK(secp256k1_ec_pubkey_create(ctx, NULL, ctmp) == 0);
3059 memset(&pubkey, 1, sizeof(pubkey));
3060 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, NULL) == 0);
3062 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
3063 secp256k1_context_set_illegal_callback(ctx, NULL, NULL);
3066 void random_sign(secp256k1_scalar *sigr, secp256k1_scalar *sigs, const secp256k1_scalar *key, const secp256k1_scalar *msg, int *recid) {
3067 secp256k1_scalar nonce;
3069 random_scalar_order_test(&nonce);
3070 } while(!secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, sigr, sigs, key, msg, &nonce, recid));
3073 void test_ecdsa_sign_verify(void) {
3076 secp256k1_scalar one;
3077 secp256k1_scalar msg, key;
3078 secp256k1_scalar sigr, sigs;
3081 random_scalar_order_test(&msg);
3082 random_scalar_order_test(&key);
3083 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pubj, &key);
3084 secp256k1_ge_set_gej(&pub, &pubj);
3085 getrec = secp256k1_rand_bits(1);
3086 random_sign(&sigr, &sigs, &key, &msg, getrec?&recid:NULL);
3088 CHECK(recid >= 0 && recid < 4);
3090 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sigr, &sigs, &pub, &msg));
3091 secp256k1_scalar_set_int(&one, 1);
3092 secp256k1_scalar_add(&msg, &msg, &one);
3093 CHECK(!secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sigr, &sigs, &pub, &msg));
3096 void run_ecdsa_sign_verify(void) {
3098 for (i = 0; i < 10*count; i++) {
3099 test_ecdsa_sign_verify();
3103 /** Dummy nonce generation function that just uses a precomputed nonce, and fails if it is not accepted. Use only for testing. */
3104 static int precomputed_nonce_function(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, const unsigned char *algo16, void *data, unsigned int counter) {
3108 memcpy(nonce32, data, 32);
3109 return (counter == 0);
3112 static int nonce_function_test_fail(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, const unsigned char *algo16, void *data, unsigned int counter) {
3113 /* Dummy nonce generator that has a fatal error on the first counter value. */
3117 return nonce_function_rfc6979(nonce32, msg32, key32, algo16, data, counter - 1);
3120 static int nonce_function_test_retry(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, const unsigned char *algo16, void *data, unsigned int counter) {
3121 /* Dummy nonce generator that produces unacceptable nonces for the first several counter values. */
3123 memset(nonce32, counter==0 ? 0 : 255, 32);
3130 static const unsigned char order[] = {
3131 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
3132 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
3133 0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
3134 0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x41
3136 memcpy(nonce32, order, 32);
3142 /* Retry rate of 6979 is negligible esp. as we only call this in deterministic tests. */
3143 /* If someone does fine a case where it retries for secp256k1, we'd like to know. */
3147 return nonce_function_rfc6979(nonce32, msg32, key32, algo16, data, counter - 5);
3150 int is_empty_signature(const secp256k1_ecdsa_signature *sig) {
3151 static const unsigned char res[sizeof(secp256k1_ecdsa_signature)] = {0};
3152 return memcmp(sig, res, sizeof(secp256k1_ecdsa_signature)) == 0;
3155 void test_ecdsa_end_to_end(void) {
3156 unsigned char extra[32] = {0x00};
3157 unsigned char privkey[32];
3158 unsigned char message[32];
3159 unsigned char privkey2[32];
3160 secp256k1_ecdsa_signature signature[6];
3161 secp256k1_scalar r, s;
3162 unsigned char sig[74];
3164 unsigned char pubkeyc[65];
3165 size_t pubkeyclen = 65;
3166 secp256k1_pubkey pubkey;
3167 unsigned char seckey[300];
3168 size_t seckeylen = 300;
3170 /* Generate a random key and message. */
3172 secp256k1_scalar msg, key;
3173 random_scalar_order_test(&msg);
3174 random_scalar_order_test(&key);
3175 secp256k1_scalar_get_b32(privkey, &key);
3176 secp256k1_scalar_get_b32(message, &msg);
3179 /* Construct and verify corresponding public key. */
3180 CHECK(secp256k1_ec_seckey_verify(ctx, privkey) == 1);
3181 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, privkey) == 1);
3183 /* Verify exporting and importing public key. */
3184 CHECK(secp256k1_ec_pubkey_serialize(ctx, pubkeyc, &pubkeyclen, &pubkey, secp256k1_rand_bits(1) == 1 ? SECP256K1_EC_COMPRESSED : SECP256K1_EC_UNCOMPRESSED));
3185 memset(&pubkey, 0, sizeof(pubkey));
3186 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, pubkeyclen) == 1);
3188 /* Verify private key import and export. */
3189 CHECK(ec_privkey_export_der(ctx, seckey, &seckeylen, privkey, secp256k1_rand_bits(1) == 1));
3190 CHECK(ec_privkey_import_der(ctx, privkey2, seckey, seckeylen) == 1);
3191 CHECK(memcmp(privkey, privkey2, 32) == 0);
3193 /* Optionally tweak the keys using addition. */
3194 if (secp256k1_rand_int(3) == 0) {
3197 unsigned char rnd[32];
3198 secp256k1_pubkey pubkey2;
3199 secp256k1_rand256_test(rnd);
3200 ret1 = secp256k1_ec_privkey_tweak_add(ctx, privkey, rnd);
3201 ret2 = secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, rnd);
3202 CHECK(ret1 == ret2);
3206 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey2, privkey) == 1);
3207 CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
3210 /* Optionally tweak the keys using multiplication. */
3211 if (secp256k1_rand_int(3) == 0) {
3214 unsigned char rnd[32];
3215 secp256k1_pubkey pubkey2;
3216 secp256k1_rand256_test(rnd);
3217 ret1 = secp256k1_ec_privkey_tweak_mul(ctx, privkey, rnd);
3218 ret2 = secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, rnd);
3219 CHECK(ret1 == ret2);
3223 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey2, privkey) == 1);
3224 CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
3228 CHECK(secp256k1_ecdsa_sign(ctx, &signature[0], message, privkey, NULL, NULL) == 1);
3229 CHECK(secp256k1_ecdsa_sign(ctx, &signature[4], message, privkey, NULL, NULL) == 1);
3230 CHECK(secp256k1_ecdsa_sign(ctx, &signature[1], message, privkey, NULL, extra) == 1);
3232 CHECK(secp256k1_ecdsa_sign(ctx, &signature[2], message, privkey, NULL, extra) == 1);
3235 CHECK(secp256k1_ecdsa_sign(ctx, &signature[3], message, privkey, NULL, extra) == 1);
3236 CHECK(memcmp(&signature[0], &signature[4], sizeof(signature[0])) == 0);
3237 CHECK(memcmp(&signature[0], &signature[1], sizeof(signature[0])) != 0);
3238 CHECK(memcmp(&signature[0], &signature[2], sizeof(signature[0])) != 0);
3239 CHECK(memcmp(&signature[0], &signature[3], sizeof(signature[0])) != 0);
3240 CHECK(memcmp(&signature[1], &signature[2], sizeof(signature[0])) != 0);
3241 CHECK(memcmp(&signature[1], &signature[3], sizeof(signature[0])) != 0);
3242 CHECK(memcmp(&signature[2], &signature[3], sizeof(signature[0])) != 0);
3244 CHECK(secp256k1_ecdsa_verify(ctx, &signature[0], message, &pubkey) == 1);
3245 CHECK(secp256k1_ecdsa_verify(ctx, &signature[1], message, &pubkey) == 1);
3246 CHECK(secp256k1_ecdsa_verify(ctx, &signature[2], message, &pubkey) == 1);
3247 CHECK(secp256k1_ecdsa_verify(ctx, &signature[3], message, &pubkey) == 1);
3248 /* Test lower-S form, malleate, verify and fail, test again, malleate again */
3249 CHECK(!secp256k1_ecdsa_signature_normalize(ctx, NULL, &signature[0]));
3250 secp256k1_ecdsa_signature_load(ctx, &r, &s, &signature[0]);
3251 secp256k1_scalar_negate(&s, &s);
3252 secp256k1_ecdsa_signature_save(&signature[5], &r, &s);
3253 CHECK(secp256k1_ecdsa_verify(ctx, &signature[5], message, &pubkey) == 0);
3254 CHECK(secp256k1_ecdsa_signature_normalize(ctx, NULL, &signature[5]));
3255 CHECK(secp256k1_ecdsa_signature_normalize(ctx, &signature[5], &signature[5]));
3256 CHECK(!secp256k1_ecdsa_signature_normalize(ctx, NULL, &signature[5]));
3257 CHECK(!secp256k1_ecdsa_signature_normalize(ctx, &signature[5], &signature[5]));
3258 CHECK(secp256k1_ecdsa_verify(ctx, &signature[5], message, &pubkey) == 1);
3259 secp256k1_scalar_negate(&s, &s);
3260 secp256k1_ecdsa_signature_save(&signature[5], &r, &s);
3261 CHECK(!secp256k1_ecdsa_signature_normalize(ctx, NULL, &signature[5]));
3262 CHECK(secp256k1_ecdsa_verify(ctx, &signature[5], message, &pubkey) == 1);
3263 CHECK(memcmp(&signature[5], &signature[0], 64) == 0);
3265 /* Serialize/parse DER and verify again */
3266 CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, sig, &siglen, &signature[0]) == 1);
3267 memset(&signature[0], 0, sizeof(signature[0]));
3268 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &signature[0], sig, siglen) == 1);
3269 CHECK(secp256k1_ecdsa_verify(ctx, &signature[0], message, &pubkey) == 1);
3270 /* Serialize/destroy/parse DER and verify again. */
3272 CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, sig, &siglen, &signature[0]) == 1);
3273 sig[secp256k1_rand_int(siglen)] += 1 + secp256k1_rand_int(255);
3274 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &signature[0], sig, siglen) == 0 ||
3275 secp256k1_ecdsa_verify(ctx, &signature[0], message, &pubkey) == 0);
3278 void test_random_pubkeys(void) {
3281 unsigned char in[65];
3282 /* Generate some randomly sized pubkeys. */
3283 size_t len = secp256k1_rand_bits(2) == 0 ? 65 : 33;
3284 if (secp256k1_rand_bits(2) == 0) {
3285 len = secp256k1_rand_bits(6);
3288 in[0] = secp256k1_rand_bits(1) ? 4 : (secp256k1_rand_bits(1) ? 6 : 7);
3290 in[0] = secp256k1_rand_bits(1) ? 2 : 3;
3292 if (secp256k1_rand_bits(3) == 0) {
3293 in[0] = secp256k1_rand_bits(8);
3296 secp256k1_rand256(&in[1]);
3299 secp256k1_rand256(&in[33]);
3301 if (secp256k1_eckey_pubkey_parse(&elem, in, len)) {
3302 unsigned char out[65];
3303 unsigned char firstb;
3307 /* If the pubkey can be parsed, it should round-trip... */
3308 CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, len == 33));
3310 CHECK(memcmp(&in[1], &out[1], len-1) == 0);
3311 /* ... except for the type of hybrid inputs. */
3312 if ((in[0] != 6) && (in[0] != 7)) {
3313 CHECK(in[0] == out[0]);
3316 CHECK(secp256k1_eckey_pubkey_serialize(&elem, in, &size, 0));
3318 CHECK(secp256k1_eckey_pubkey_parse(&elem2, in, size));
3319 ge_equals_ge(&elem,&elem2);
3320 /* Check that the X9.62 hybrid type is checked. */
3321 in[0] = secp256k1_rand_bits(1) ? 6 : 7;
3322 res = secp256k1_eckey_pubkey_parse(&elem2, in, size);
3323 if (firstb == 2 || firstb == 3) {
3324 if (in[0] == firstb + 4) {
3331 ge_equals_ge(&elem,&elem2);
3332 CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, 0));
3333 CHECK(memcmp(&in[1], &out[1], 64) == 0);
3338 void run_random_pubkeys(void) {
3340 for (i = 0; i < 10*count; i++) {
3341 test_random_pubkeys();
3345 void run_ecdsa_end_to_end(void) {
3347 for (i = 0; i < 64*count; i++) {
3348 test_ecdsa_end_to_end();
3352 int test_ecdsa_der_parse(const unsigned char *sig, size_t siglen, int certainly_der, int certainly_not_der) {
3353 static const unsigned char zeroes[32] = {0};
3354 static const unsigned char max_scalar[32] = {
3355 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3356 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
3357 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
3358 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x40
3363 secp256k1_ecdsa_signature sig_der;
3364 unsigned char roundtrip_der[2048];
3365 unsigned char compact_der[64];
3366 size_t len_der = 2048;
3367 int parsed_der = 0, valid_der = 0, roundtrips_der = 0;
3369 secp256k1_ecdsa_signature sig_der_lax;
3370 unsigned char roundtrip_der_lax[2048];
3371 unsigned char compact_der_lax[64];
3372 size_t len_der_lax = 2048;
3373 int parsed_der_lax = 0, valid_der_lax = 0, roundtrips_der_lax = 0;
3375 #ifdef ENABLE_OPENSSL_TESTS
3376 ECDSA_SIG *sig_openssl;
3377 const unsigned char *sigptr;
3378 unsigned char roundtrip_openssl[2048];
3379 int len_openssl = 2048;
3380 int parsed_openssl, valid_openssl = 0, roundtrips_openssl = 0;
3383 parsed_der = secp256k1_ecdsa_signature_parse_der(ctx, &sig_der, sig, siglen);
3385 ret |= (!secp256k1_ecdsa_signature_serialize_compact(ctx, compact_der, &sig_der)) << 0;
3386 valid_der = (memcmp(compact_der, zeroes, 32) != 0) && (memcmp(compact_der + 32, zeroes, 32) != 0);
3389 ret |= (!secp256k1_ecdsa_signature_serialize_der(ctx, roundtrip_der, &len_der, &sig_der)) << 1;
3390 roundtrips_der = (len_der == siglen) && memcmp(roundtrip_der, sig, siglen) == 0;
3393 parsed_der_lax = ecdsa_signature_parse_der_lax(ctx, &sig_der_lax, sig, siglen);
3394 if (parsed_der_lax) {
3395 ret |= (!secp256k1_ecdsa_signature_serialize_compact(ctx, compact_der_lax, &sig_der_lax)) << 10;
3396 valid_der_lax = (memcmp(compact_der_lax, zeroes, 32) != 0) && (memcmp(compact_der_lax + 32, zeroes, 32) != 0);
3398 if (valid_der_lax) {
3399 ret |= (!secp256k1_ecdsa_signature_serialize_der(ctx, roundtrip_der_lax, &len_der_lax, &sig_der_lax)) << 11;
3400 roundtrips_der_lax = (len_der_lax == siglen) && memcmp(roundtrip_der_lax, sig, siglen) == 0;
3403 if (certainly_der) {
3404 ret |= (!parsed_der) << 2;
3406 if (certainly_not_der) {
3407 ret |= (parsed_der) << 17;
3410 ret |= (!roundtrips_der) << 3;
3414 ret |= (!roundtrips_der_lax) << 12;
3415 ret |= (len_der != len_der_lax) << 13;
3416 ret |= (memcmp(roundtrip_der_lax, roundtrip_der, len_der) != 0) << 14;
3418 ret |= (roundtrips_der != roundtrips_der_lax) << 15;
3420 ret |= (!parsed_der_lax) << 16;
3423 #ifdef ENABLE_OPENSSL_TESTS
3424 sig_openssl = ECDSA_SIG_new();
3426 parsed_openssl = (d2i_ECDSA_SIG(&sig_openssl, &sigptr, siglen) != NULL);
3427 if (parsed_openssl) {
3428 valid_openssl = !BN_is_negative(sig_openssl->r) && !BN_is_negative(sig_openssl->s) && BN_num_bits(sig_openssl->r) > 0 && BN_num_bits(sig_openssl->r) <= 256 && BN_num_bits(sig_openssl->s) > 0 && BN_num_bits(sig_openssl->s) <= 256;
3429 if (valid_openssl) {
3430 unsigned char tmp[32] = {0};
3431 BN_bn2bin(sig_openssl->r, tmp + 32 - BN_num_bytes(sig_openssl->r));
3432 valid_openssl = memcmp(tmp, max_scalar, 32) < 0;
3434 if (valid_openssl) {
3435 unsigned char tmp[32] = {0};
3436 BN_bn2bin(sig_openssl->s, tmp + 32 - BN_num_bytes(sig_openssl->s));
3437 valid_openssl = memcmp(tmp, max_scalar, 32) < 0;
3440 len_openssl = i2d_ECDSA_SIG(sig_openssl, NULL);
3441 if (len_openssl <= 2048) {
3442 unsigned char *ptr = roundtrip_openssl;
3443 CHECK(i2d_ECDSA_SIG(sig_openssl, &ptr) == len_openssl);
3444 roundtrips_openssl = valid_openssl && ((size_t)len_openssl == siglen) && (memcmp(roundtrip_openssl, sig, siglen) == 0);
3448 ECDSA_SIG_free(sig_openssl);
3450 ret |= (parsed_der && !parsed_openssl) << 4;
3451 ret |= (valid_der && !valid_openssl) << 5;
3452 ret |= (roundtrips_openssl && !parsed_der) << 6;
3453 ret |= (roundtrips_der != roundtrips_openssl) << 7;
3454 if (roundtrips_openssl) {
3455 ret |= (len_der != (size_t)len_openssl) << 8;
3456 ret |= (memcmp(roundtrip_der, roundtrip_openssl, len_der) != 0) << 9;
3462 static void assign_big_endian(unsigned char *ptr, size_t ptrlen, uint32_t val) {
3464 for (i = 0; i < ptrlen; i++) {
3465 int shift = ptrlen - 1 - i;
3469 ptr[i] = (val >> shift) & 0xFF;
3474 static void damage_array(unsigned char *sig, size_t *len) {
3476 int action = secp256k1_rand_bits(3);
3478 /* Delete a byte. */
3479 pos = secp256k1_rand_int(*len);
3480 memmove(sig + pos, sig + pos + 1, *len - pos - 1);
3483 } else if (action < 2) {
3484 /* Insert a byte. */
3485 pos = secp256k1_rand_int(1 + *len);
3486 memmove(sig + pos + 1, sig + pos, *len - pos);
3487 sig[pos] = secp256k1_rand_bits(8);
3490 } else if (action < 4) {
3491 /* Modify a byte. */
3492 sig[secp256k1_rand_int(*len)] += 1 + secp256k1_rand_int(255);
3494 } else { /* action < 8 */
3496 sig[secp256k1_rand_int(*len)] ^= 1 << secp256k1_rand_bits(3);
3501 static void random_ber_signature(unsigned char *sig, size_t *len, int* certainly_der, int* certainly_not_der) {
3503 int nlow[2], nlen[2], nlenlen[2], nhbit[2], nhbyte[2], nzlen[2];
3504 size_t tlen, elen, glen;
3509 der = secp256k1_rand_bits(2) == 0;
3510 *certainly_der = der;
3511 *certainly_not_der = 0;
3512 indet = der ? 0 : secp256k1_rand_int(10) == 0;
3514 for (n = 0; n < 2; n++) {
3515 /* We generate two classes of numbers: nlow==1 "low" ones (up to 32 bytes), nlow==0 "high" ones (32 bytes with 129 top bits set, or larger than 32 bytes) */
3516 nlow[n] = der ? 1 : (secp256k1_rand_bits(3) != 0);
3517 /* The length of the number in bytes (the first byte of which will always be nonzero) */
3518 nlen[n] = nlow[n] ? secp256k1_rand_int(33) : 32 + secp256k1_rand_int(200) * secp256k1_rand_int(8) / 8;
3519 CHECK(nlen[n] <= 232);
3520 /* The top bit of the number. */
3521 nhbit[n] = (nlow[n] == 0 && nlen[n] == 32) ? 1 : (nlen[n] == 0 ? 0 : secp256k1_rand_bits(1));
3522 /* The top byte of the number (after the potential hardcoded 16 0xFF characters for "high" 32 bytes numbers) */
3523 nhbyte[n] = nlen[n] == 0 ? 0 : (nhbit[n] ? 128 + secp256k1_rand_bits(7) : 1 + secp256k1_rand_int(127));
3524 /* The number of zero bytes in front of the number (which is 0 or 1 in case of DER, otherwise we extend up to 300 bytes) */
3525 nzlen[n] = der ? ((nlen[n] == 0 || nhbit[n]) ? 1 : 0) : (nlow[n] ? secp256k1_rand_int(3) : secp256k1_rand_int(300 - nlen[n]) * secp256k1_rand_int(8) / 8);
3526 if (nzlen[n] > ((nlen[n] == 0 || nhbit[n]) ? 1 : 0)) {
3527 *certainly_not_der = 1;
3529 CHECK(nlen[n] + nzlen[n] <= 300);
3530 /* The length of the length descriptor for the number. 0 means short encoding, anything else is long encoding. */
3531 nlenlen[n] = nlen[n] + nzlen[n] < 128 ? 0 : (nlen[n] + nzlen[n] < 256 ? 1 : 2);
3533 /* nlenlen[n] max 127 bytes */
3534 int add = secp256k1_rand_int(127 - nlenlen[n]) * secp256k1_rand_int(16) * secp256k1_rand_int(16) / 256;
3537 *certainly_not_der = 1;
3540 CHECK(nlen[n] + nzlen[n] + nlenlen[n] <= 427);
3543 /* The total length of the data to go, so far */
3544 tlen = 2 + nlenlen[0] + nlen[0] + nzlen[0] + 2 + nlenlen[1] + nlen[1] + nzlen[1];
3547 /* The length of the garbage inside the tuple. */
3548 elen = (der || indet) ? 0 : secp256k1_rand_int(980 - tlen) * secp256k1_rand_int(8) / 8;
3550 *certainly_not_der = 1;
3555 /* The length of the garbage after the end of the tuple. */
3556 glen = der ? 0 : secp256k1_rand_int(990 - tlen) * secp256k1_rand_int(8) / 8;
3558 *certainly_not_der = 1;
3560 CHECK(tlen + glen <= 990);
3562 /* Write the tuple header. */
3563 sig[(*len)++] = 0x30;
3565 /* Indeterminate length */
3566 sig[(*len)++] = 0x80;
3567 *certainly_not_der = 1;
3569 int tlenlen = tlen < 128 ? 0 : (tlen < 256 ? 1 : 2);
3571 int add = secp256k1_rand_int(127 - tlenlen) * secp256k1_rand_int(16) * secp256k1_rand_int(16) / 256;
3574 *certainly_not_der = 1;
3578 /* Short length notation */
3579 sig[(*len)++] = tlen;
3581 /* Long length notation */
3582 sig[(*len)++] = 128 + tlenlen;
3583 assign_big_endian(sig + *len, tlenlen, tlen);
3589 CHECK(tlen + glen <= 1119);
3591 for (n = 0; n < 2; n++) {
3592 /* Write the integer header. */
3593 sig[(*len)++] = 0x02;
3594 if (nlenlen[n] == 0) {
3595 /* Short length notation */
3596 sig[(*len)++] = nlen[n] + nzlen[n];
3598 /* Long length notation. */
3599 sig[(*len)++] = 128 + nlenlen[n];
3600 assign_big_endian(sig + *len, nlenlen[n], nlen[n] + nzlen[n]);
3603 /* Write zero padding */
3604 while (nzlen[n] > 0) {
3605 sig[(*len)++] = 0x00;
3608 if (nlen[n] == 32 && !nlow[n]) {
3609 /* Special extra 16 0xFF bytes in "high" 32-byte numbers */
3611 for (i = 0; i < 16; i++) {
3612 sig[(*len)++] = 0xFF;
3616 /* Write first byte of number */
3618 sig[(*len)++] = nhbyte[n];
3621 /* Generate remaining random bytes of number */
3622 secp256k1_rand_bytes_test(sig + *len, nlen[n]);
3627 /* Generate random garbage inside tuple. */
3628 secp256k1_rand_bytes_test(sig + *len, elen);
3631 /* Generate end-of-contents bytes. */
3637 CHECK(tlen + glen <= 1121);
3639 /* Generate random garbage outside tuple. */
3640 secp256k1_rand_bytes_test(sig + *len, glen);
3643 CHECK(tlen <= 1121);
3644 CHECK(tlen == *len);
3647 void run_ecdsa_der_parse(void) {
3649 for (i = 0; i < 200 * count; i++) {
3650 unsigned char buffer[2048];
3652 int certainly_der = 0;
3653 int certainly_not_der = 0;
3654 random_ber_signature(buffer, &buflen, &certainly_der, &certainly_not_der);
3655 for (j = 0; j < 16; j++) {
3658 damage_array(buffer, &buflen);
3659 /* We don't know anything anymore about the DERness of the result */
3661 certainly_not_der = 0;
3663 ret = test_ecdsa_der_parse(buffer, buflen, certainly_der, certainly_not_der);
3666 fprintf(stderr, "Failure %x on ", ret);
3667 for (k = 0; k < buflen; k++) {
3668 fprintf(stderr, "%02x ", buffer[k]);
3670 fprintf(stderr, "\n");
3677 /* Tests several edge cases. */
3678 void test_ecdsa_edge_cases(void) {
3680 secp256k1_ecdsa_signature sig;
3682 /* Test the case where ECDSA recomputes a point that is infinity. */
3686 secp256k1_scalar msg;
3687 secp256k1_scalar sr, ss;
3688 secp256k1_scalar_set_int(&ss, 1);
3689 secp256k1_scalar_negate(&ss, &ss);
3690 secp256k1_scalar_inverse(&ss, &ss);
3691 secp256k1_scalar_set_int(&sr, 1);
3692 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &keyj, &sr);
3693 secp256k1_ge_set_gej(&key, &keyj);
3695 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3698 /* Verify signature with r of zero fails. */
3700 const unsigned char pubkey_mods_zero[33] = {
3701 0x02, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3702 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3703 0xfe, 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0,
3704 0x3b, 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41,
3708 secp256k1_scalar msg;
3709 secp256k1_scalar sr, ss;
3710 secp256k1_scalar_set_int(&ss, 1);
3711 secp256k1_scalar_set_int(&msg, 0);
3712 secp256k1_scalar_set_int(&sr, 0);
3713 CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey_mods_zero, 33));
3714 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3717 /* Verify signature with s of zero fails. */
3719 const unsigned char pubkey[33] = {
3720 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3721 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3722 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3723 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3727 secp256k1_scalar msg;
3728 secp256k1_scalar sr, ss;
3729 secp256k1_scalar_set_int(&ss, 0);
3730 secp256k1_scalar_set_int(&msg, 0);
3731 secp256k1_scalar_set_int(&sr, 1);
3732 CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey, 33));
3733 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3736 /* Verify signature with message 0 passes. */
3738 const unsigned char pubkey[33] = {
3739 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3740 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3741 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3742 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3745 const unsigned char pubkey2[33] = {
3746 0x02, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3747 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3748 0xfe, 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0,
3749 0x3b, 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41,
3754 secp256k1_scalar msg;
3755 secp256k1_scalar sr, ss;
3756 secp256k1_scalar_set_int(&ss, 2);
3757 secp256k1_scalar_set_int(&msg, 0);
3758 secp256k1_scalar_set_int(&sr, 2);
3759 CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey, 33));
3760 CHECK(secp256k1_eckey_pubkey_parse(&key2, pubkey2, 33));
3761 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3762 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 1);
3763 secp256k1_scalar_negate(&ss, &ss);
3764 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3765 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 1);
3766 secp256k1_scalar_set_int(&ss, 1);
3767 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3768 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 0);
3771 /* Verify signature with message 1 passes. */
3773 const unsigned char pubkey[33] = {
3774 0x02, 0x14, 0x4e, 0x5a, 0x58, 0xef, 0x5b, 0x22,
3775 0x6f, 0xd2, 0xe2, 0x07, 0x6a, 0x77, 0xcf, 0x05,
3776 0xb4, 0x1d, 0xe7, 0x4a, 0x30, 0x98, 0x27, 0x8c,
3777 0x93, 0xe6, 0xe6, 0x3c, 0x0b, 0xc4, 0x73, 0x76,
3780 const unsigned char pubkey2[33] = {
3781 0x02, 0x8a, 0xd5, 0x37, 0xed, 0x73, 0xd9, 0x40,
3782 0x1d, 0xa0, 0x33, 0xd2, 0xdc, 0xf0, 0xaf, 0xae,
3783 0x34, 0xcf, 0x5f, 0x96, 0x4c, 0x73, 0x28, 0x0f,
3784 0x92, 0xc0, 0xf6, 0x9d, 0xd9, 0xb2, 0x09, 0x10,
3787 const unsigned char csr[32] = {
3788 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3789 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
3790 0x45, 0x51, 0x23, 0x19, 0x50, 0xb7, 0x5f, 0xc4,
3791 0x40, 0x2d, 0xa1, 0x72, 0x2f, 0xc9, 0xba, 0xeb
3795 secp256k1_scalar msg;
3796 secp256k1_scalar sr, ss;
3797 secp256k1_scalar_set_int(&ss, 1);
3798 secp256k1_scalar_set_int(&msg, 1);
3799 secp256k1_scalar_set_b32(&sr, csr, NULL);
3800 CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey, 33));
3801 CHECK(secp256k1_eckey_pubkey_parse(&key2, pubkey2, 33));
3802 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3803 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 1);
3804 secp256k1_scalar_negate(&ss, &ss);
3805 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3806 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 1);
3807 secp256k1_scalar_set_int(&ss, 2);
3808 secp256k1_scalar_inverse_var(&ss, &ss);
3809 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3810 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 0);
3813 /* Verify signature with message -1 passes. */
3815 const unsigned char pubkey[33] = {
3816 0x03, 0xaf, 0x97, 0xff, 0x7d, 0x3a, 0xf6, 0xa0,
3817 0x02, 0x94, 0xbd, 0x9f, 0x4b, 0x2e, 0xd7, 0x52,
3818 0x28, 0xdb, 0x49, 0x2a, 0x65, 0xcb, 0x1e, 0x27,
3819 0x57, 0x9c, 0xba, 0x74, 0x20, 0xd5, 0x1d, 0x20,
3822 const unsigned char csr[32] = {
3823 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3824 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
3825 0x45, 0x51, 0x23, 0x19, 0x50, 0xb7, 0x5f, 0xc4,
3826 0x40, 0x2d, 0xa1, 0x72, 0x2f, 0xc9, 0xba, 0xee
3829 secp256k1_scalar msg;
3830 secp256k1_scalar sr, ss;
3831 secp256k1_scalar_set_int(&ss, 1);
3832 secp256k1_scalar_set_int(&msg, 1);
3833 secp256k1_scalar_negate(&msg, &msg);
3834 secp256k1_scalar_set_b32(&sr, csr, NULL);
3835 CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey, 33));
3836 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3837 secp256k1_scalar_negate(&ss, &ss);
3838 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3839 secp256k1_scalar_set_int(&ss, 3);
3840 secp256k1_scalar_inverse_var(&ss, &ss);
3841 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3844 /* Signature where s would be zero. */
3846 secp256k1_pubkey pubkey;
3849 unsigned char signature[72];
3850 static const unsigned char nonce[32] = {
3851 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3852 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3853 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3854 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
3856 static const unsigned char nonce2[32] = {
3857 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
3858 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
3859 0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
3860 0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x40
3862 const unsigned char key[32] = {
3863 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3864 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3865 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3866 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
3868 unsigned char msg[32] = {
3869 0x86, 0x41, 0x99, 0x81, 0x06, 0x23, 0x44, 0x53,
3870 0xaa, 0x5f, 0x9d, 0x6a, 0x31, 0x78, 0xf4, 0xf7,
3871 0xb8, 0x12, 0xe0, 0x0b, 0x81, 0x7a, 0x77, 0x62,
3872 0x65, 0xdf, 0xdd, 0x31, 0xb9, 0x3e, 0x29, 0xa9,
3875 secp256k1_context_set_illegal_callback(ctx, counting_illegal_callback_fn, &ecount);
3876 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, precomputed_nonce_function, nonce) == 0);
3877 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, precomputed_nonce_function, nonce2) == 0);
3879 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, precomputed_nonce_function, nonce) == 1);
3881 CHECK(secp256k1_ecdsa_sign(ctx, NULL, msg, key, precomputed_nonce_function, nonce2) == 0);
3883 CHECK(secp256k1_ecdsa_sign(ctx, &sig, NULL, key, precomputed_nonce_function, nonce2) == 0);
3885 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, NULL, precomputed_nonce_function, nonce2) == 0);
3887 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, precomputed_nonce_function, nonce2) == 1);
3888 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, key) == 1);
3889 CHECK(secp256k1_ecdsa_verify(ctx, NULL, msg, &pubkey) == 0);
3891 CHECK(secp256k1_ecdsa_verify(ctx, &sig, NULL, &pubkey) == 0);
3893 CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg, NULL) == 0);
3895 CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg, &pubkey) == 1);
3897 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, NULL) == 0);
3899 /* That pubkeyload fails via an ARGCHECK is a little odd but makes sense because pubkeys are an opaque data type. */
3900 CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg, &pubkey) == 0);
3903 CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, NULL, &siglen, &sig) == 0);
3905 CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, signature, NULL, &sig) == 0);
3906 CHECK(ecount == 10);
3907 CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, signature, &siglen, NULL) == 0);
3908 CHECK(ecount == 11);
3909 CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, signature, &siglen, &sig) == 1);
3910 CHECK(ecount == 11);
3911 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, NULL, signature, siglen) == 0);
3912 CHECK(ecount == 12);
3913 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, NULL, siglen) == 0);
3914 CHECK(ecount == 13);
3915 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, signature, siglen) == 1);
3916 CHECK(ecount == 13);
3918 /* Too little room for a signature does not fail via ARGCHECK. */
3919 CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, signature, &siglen, &sig) == 0);
3920 CHECK(ecount == 13);
3922 CHECK(secp256k1_ecdsa_signature_normalize(ctx, NULL, NULL) == 0);
3924 CHECK(secp256k1_ecdsa_signature_serialize_compact(ctx, NULL, &sig) == 0);
3926 CHECK(secp256k1_ecdsa_signature_serialize_compact(ctx, signature, NULL) == 0);
3928 CHECK(secp256k1_ecdsa_signature_serialize_compact(ctx, signature, &sig) == 1);
3930 CHECK(secp256k1_ecdsa_signature_parse_compact(ctx, NULL, signature) == 0);
3932 CHECK(secp256k1_ecdsa_signature_parse_compact(ctx, &sig, NULL) == 0);
3934 CHECK(secp256k1_ecdsa_signature_parse_compact(ctx, &sig, signature) == 1);
3936 secp256k1_context_set_illegal_callback(ctx, NULL, NULL);
3939 /* Nonce function corner cases. */
3940 for (t = 0; t < 2; t++) {
3941 static const unsigned char zero[32] = {0x00};
3943 unsigned char key[32];
3944 unsigned char msg[32];
3945 secp256k1_ecdsa_signature sig2;
3946 secp256k1_scalar sr[512], ss;
3947 const unsigned char *extra;
3948 extra = t == 0 ? NULL : zero;
3951 /* High key results in signature failure. */
3952 memset(key, 0xFF, 32);
3953 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, NULL, extra) == 0);
3954 CHECK(is_empty_signature(&sig));
3955 /* Zero key results in signature failure. */
3957 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, NULL, extra) == 0);
3958 CHECK(is_empty_signature(&sig));
3959 /* Nonce function failure results in signature failure. */
3961 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, nonce_function_test_fail, extra) == 0);
3962 CHECK(is_empty_signature(&sig));
3963 /* The retry loop successfully makes its way to the first good value. */
3964 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, nonce_function_test_retry, extra) == 1);
3965 CHECK(!is_empty_signature(&sig));
3966 CHECK(secp256k1_ecdsa_sign(ctx, &sig2, msg, key, nonce_function_rfc6979, extra) == 1);
3967 CHECK(!is_empty_signature(&sig2));
3968 CHECK(memcmp(&sig, &sig2, sizeof(sig)) == 0);
3969 /* The default nonce function is deterministic. */
3970 CHECK(secp256k1_ecdsa_sign(ctx, &sig2, msg, key, NULL, extra) == 1);
3971 CHECK(!is_empty_signature(&sig2));
3972 CHECK(memcmp(&sig, &sig2, sizeof(sig)) == 0);
3973 /* The default nonce function changes output with different messages. */
3974 for(i = 0; i < 256; i++) {
3977 CHECK(secp256k1_ecdsa_sign(ctx, &sig2, msg, key, NULL, extra) == 1);
3978 CHECK(!is_empty_signature(&sig2));
3979 secp256k1_ecdsa_signature_load(ctx, &sr[i], &ss, &sig2);
3980 for (j = 0; j < i; j++) {
3981 CHECK(!secp256k1_scalar_eq(&sr[i], &sr[j]));
3986 /* The default nonce function changes output with different keys. */
3987 for(i = 256; i < 512; i++) {
3990 CHECK(secp256k1_ecdsa_sign(ctx, &sig2, msg, key, NULL, extra) == 1);
3991 CHECK(!is_empty_signature(&sig2));
3992 secp256k1_ecdsa_signature_load(ctx, &sr[i], &ss, &sig2);
3993 for (j = 0; j < i; j++) {
3994 CHECK(!secp256k1_scalar_eq(&sr[i], &sr[j]));
4001 /* Check that optional nonce arguments do not have equivalent effect. */
4002 const unsigned char zeros[32] = {0};
4003 unsigned char nonce[32];
4004 unsigned char nonce2[32];
4005 unsigned char nonce3[32];
4006 unsigned char nonce4[32];
4008 VG_UNDEF(nonce2,32);
4009 VG_UNDEF(nonce3,32);
4010 VG_UNDEF(nonce4,32);
4011 CHECK(nonce_function_rfc6979(nonce, zeros, zeros, NULL, NULL, 0) == 1);
4013 CHECK(nonce_function_rfc6979(nonce2, zeros, zeros, zeros, NULL, 0) == 1);
4014 VG_CHECK(nonce2,32);
4015 CHECK(nonce_function_rfc6979(nonce3, zeros, zeros, NULL, (void *)zeros, 0) == 1);
4016 VG_CHECK(nonce3,32);
4017 CHECK(nonce_function_rfc6979(nonce4, zeros, zeros, zeros, (void *)zeros, 0) == 1);
4018 VG_CHECK(nonce4,32);
4019 CHECK(memcmp(nonce, nonce2, 32) != 0);
4020 CHECK(memcmp(nonce, nonce3, 32) != 0);
4021 CHECK(memcmp(nonce, nonce4, 32) != 0);
4022 CHECK(memcmp(nonce2, nonce3, 32) != 0);
4023 CHECK(memcmp(nonce2, nonce4, 32) != 0);
4024 CHECK(memcmp(nonce3, nonce4, 32) != 0);
4028 /* Privkey export where pubkey is the point at infinity. */
4030 unsigned char privkey[300];
4031 unsigned char seckey[32] = {
4032 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
4033 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
4034 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
4035 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41,
4037 size_t outlen = 300;
4038 CHECK(!ec_privkey_export_der(ctx, privkey, &outlen, seckey, 0));
4040 CHECK(!ec_privkey_export_der(ctx, privkey, &outlen, seckey, 1));
4044 void run_ecdsa_edge_cases(void) {
4045 test_ecdsa_edge_cases();
4048 #ifdef ENABLE_OPENSSL_TESTS
4049 EC_KEY *get_openssl_key(const unsigned char *key32) {
4050 unsigned char privkey[300];
4052 const unsigned char* pbegin = privkey;
4053 int compr = secp256k1_rand_bits(1);
4054 EC_KEY *ec_key = EC_KEY_new_by_curve_name(NID_secp256k1);
4055 CHECK(ec_privkey_export_der(ctx, privkey, &privkeylen, key32, compr));
4056 CHECK(d2i_ECPrivateKey(&ec_key, &pbegin, privkeylen));
4057 CHECK(EC_KEY_check_key(ec_key));
4061 void test_ecdsa_openssl(void) {
4064 secp256k1_scalar sigr, sigs;
4065 secp256k1_scalar one;
4066 secp256k1_scalar msg2;
4067 secp256k1_scalar key, msg;
4069 unsigned int sigsize = 80;
4070 size_t secp_sigsize = 80;
4071 unsigned char message[32];
4072 unsigned char signature[80];
4073 unsigned char key32[32];
4074 secp256k1_rand256_test(message);
4075 secp256k1_scalar_set_b32(&msg, message, NULL);
4076 random_scalar_order_test(&key);
4077 secp256k1_scalar_get_b32(key32, &key);
4078 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &qj, &key);
4079 secp256k1_ge_set_gej(&q, &qj);
4080 ec_key = get_openssl_key(key32);
4081 CHECK(ec_key != NULL);
4082 CHECK(ECDSA_sign(0, message, sizeof(message), signature, &sigsize, ec_key));
4083 CHECK(secp256k1_ecdsa_sig_parse(&sigr, &sigs, signature, sigsize));
4084 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sigr, &sigs, &q, &msg));
4085 secp256k1_scalar_set_int(&one, 1);
4086 secp256k1_scalar_add(&msg2, &msg, &one);
4087 CHECK(!secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sigr, &sigs, &q, &msg2));
4089 random_sign(&sigr, &sigs, &key, &msg, NULL);
4090 CHECK(secp256k1_ecdsa_sig_serialize(signature, &secp_sigsize, &sigr, &sigs));
4091 CHECK(ECDSA_verify(0, message, sizeof(message), signature, secp_sigsize, ec_key) == 1);
4093 EC_KEY_free(ec_key);
4096 void run_ecdsa_openssl(void) {
4098 for (i = 0; i < 10*count; i++) {
4099 test_ecdsa_openssl();
4104 #ifdef ENABLE_MODULE_ECDH
4105 # include "modules/ecdh/tests_impl.h"
4108 #ifdef ENABLE_MODULE_SCHNORR
4109 # include "modules/schnorr/tests_impl.h"
4112 #ifdef ENABLE_MODULE_RECOVERY
4113 # include "modules/recovery/tests_impl.h"
4116 int main(int argc, char **argv) {
4117 unsigned char seed16[16] = {0};
4118 unsigned char run32[32] = {0};
4119 /* find iteration count */
4121 count = strtol(argv[1], NULL, 0);
4124 /* find random seed */
4127 const char* ch = argv[2];
4128 while (pos < 16 && ch[0] != 0 && ch[1] != 0) {
4130 if (sscanf(ch, "%2hx", &sh)) {
4139 FILE *frand = fopen("/dev/urandom", "r");
4140 if ((frand == NULL) || !fread(&seed16, sizeof(seed16), 1, frand)) {
4141 uint64_t t = time(NULL) * (uint64_t)1337;
4143 seed16[1] ^= t >> 8;
4144 seed16[2] ^= t >> 16;
4145 seed16[3] ^= t >> 24;
4146 seed16[4] ^= t >> 32;
4147 seed16[5] ^= t >> 40;
4148 seed16[6] ^= t >> 48;
4149 seed16[7] ^= t >> 56;
4153 secp256k1_rand_seed(seed16);
4155 printf("test count = %i\n", count);
4156 printf("random seed = %02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x\n", seed16[0], seed16[1], seed16[2], seed16[3], seed16[4], seed16[5], seed16[6], seed16[7], seed16[8], seed16[9], seed16[10], seed16[11], seed16[12], seed16[13], seed16[14], seed16[15]);
4159 run_context_tests();
4160 ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY);
4161 if (secp256k1_rand_bits(1)) {
4162 secp256k1_rand256(run32);
4163 CHECK(secp256k1_context_randomize(ctx, secp256k1_rand_bits(1) ? run32 : NULL));
4170 run_hmac_sha256_tests();
4171 run_rfc6979_hmac_sha256_tests();
4173 #ifndef USE_NUM_NONE
4175 run_num_smalltests();
4183 run_field_inv_var();
4184 run_field_inv_all_var();
4186 run_field_convert();
4195 run_point_times_order();
4197 run_ecmult_constants();
4198 run_ecmult_gen_blind();
4199 run_ecmult_const_tests();
4202 /* endomorphism tests */
4203 #ifdef USE_ENDOMORPHISM
4204 run_endomorphism_tests();
4207 /* EC point parser test */
4208 run_ec_pubkey_parse_test();
4210 /* EC key edge cases */
4211 run_eckey_edge_case_test();
4213 #ifdef ENABLE_MODULE_ECDH
4219 run_random_pubkeys();
4220 run_ecdsa_der_parse();
4221 run_ecdsa_sign_verify();
4222 run_ecdsa_end_to_end();
4223 run_ecdsa_edge_cases();
4224 #ifdef ENABLE_OPENSSL_TESTS
4225 run_ecdsa_openssl();
4228 #ifdef ENABLE_MODULE_SCHNORR
4230 run_schnorr_tests();
4233 #ifdef ENABLE_MODULE_RECOVERY
4234 /* ECDSA pubkey recovery tests */
4235 run_recovery_tests();
4238 secp256k1_rand256(run32);
4239 printf("random run = %02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x\n", run32[0], run32[1], run32[2], run32[3], run32[4], run32[5], run32[6], run32[7], run32[8], run32[9], run32[10], run32[11], run32[12], run32[13], run32[14], run32[15]);
4242 secp256k1_context_destroy(ctx);
4244 printf("no problems found\n");