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[33][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}},
1115 {{0x82, 0xc9, 0xfa, 0xb0, 0x68, 0x04, 0xa0, 0x00,
1116 0x82, 0xc9, 0xfa, 0xb0, 0x68, 0x04, 0xa0, 0x00,
1117 0xff, 0xff, 0xff, 0xff, 0xff, 0x6f, 0x03, 0xfb,
1118 0xfa, 0x8a, 0x7d, 0xdf, 0x13, 0x86, 0xe2, 0x03},
1119 {0x82, 0xc9, 0xfa, 0xb0, 0x68, 0x04, 0xa0, 0x00,
1120 0x82, 0xc9, 0xfa, 0xb0, 0x68, 0x04, 0xa0, 0x00,
1121 0xff, 0xff, 0xff, 0xff, 0xff, 0x6f, 0x03, 0xfb,
1122 0xfa, 0x8a, 0x7d, 0xdf, 0x13, 0x86, 0xe2, 0x03}}
1124 unsigned char res[33][2][32] = {
1125 {{0x0c, 0x3b, 0x0a, 0xca, 0x8d, 0x1a, 0x2f, 0xb9,
1126 0x8a, 0x7b, 0x53, 0x5a, 0x1f, 0xc5, 0x22, 0xa1,
1127 0x07, 0x2a, 0x48, 0xea, 0x02, 0xeb, 0xb3, 0xd6,
1128 0x20, 0x1e, 0x86, 0xd0, 0x95, 0xf6, 0x92, 0x35},
1129 {0xdc, 0x90, 0x7a, 0x07, 0x2e, 0x1e, 0x44, 0x6d,
1130 0xf8, 0x15, 0x24, 0x5b, 0x5a, 0x96, 0x37, 0x9c,
1131 0x37, 0x7b, 0x0d, 0xac, 0x1b, 0x65, 0x58, 0x49,
1132 0x43, 0xb7, 0x31, 0xbb, 0xa7, 0xf4, 0x97, 0x15}},
1133 {{0xf1, 0xf7, 0x3a, 0x50, 0xe6, 0x10, 0xba, 0x22,
1134 0x43, 0x4d, 0x1f, 0x1f, 0x7c, 0x27, 0xca, 0x9c,
1135 0xb8, 0xb6, 0xa0, 0xfc, 0xd8, 0xc0, 0x05, 0x2f,
1136 0xf7, 0x08, 0xe1, 0x76, 0xdd, 0xd0, 0x80, 0xc8},
1137 {0xe3, 0x80, 0x80, 0xb8, 0xdb, 0xe3, 0xa9, 0x77,
1138 0x00, 0xb0, 0xf5, 0x2e, 0x27, 0xe2, 0x68, 0xc4,
1139 0x88, 0xe8, 0x04, 0xc1, 0x12, 0xbf, 0x78, 0x59,
1140 0xe6, 0xa9, 0x7c, 0xe1, 0x81, 0xdd, 0xb9, 0xd5}},
1141 {{0x96, 0xe2, 0xee, 0x01, 0xa6, 0x80, 0x31, 0xef,
1142 0x5c, 0xd0, 0x19, 0xb4, 0x7d, 0x5f, 0x79, 0xab,
1143 0xa1, 0x97, 0xd3, 0x7e, 0x33, 0xbb, 0x86, 0x55,
1144 0x60, 0x20, 0x10, 0x0d, 0x94, 0x2d, 0x11, 0x7c},
1145 {0xcc, 0xab, 0xe0, 0xe8, 0x98, 0x65, 0x12, 0x96,
1146 0x38, 0x5a, 0x1a, 0xf2, 0x85, 0x23, 0x59, 0x5f,
1147 0xf9, 0xf3, 0xc2, 0x81, 0x70, 0x92, 0x65, 0x12,
1148 0x9c, 0x65, 0x1e, 0x96, 0x00, 0xef, 0xe7, 0x63}},
1149 {{0xac, 0x1e, 0x62, 0xc2, 0x59, 0xfc, 0x4e, 0x5c,
1150 0x83, 0xb0, 0xd0, 0x6f, 0xce, 0x19, 0xf6, 0xbf,
1151 0xa4, 0xb0, 0xe0, 0x53, 0x66, 0x1f, 0xbf, 0xc9,
1152 0x33, 0x47, 0x37, 0xa9, 0x3d, 0x5d, 0xb0, 0x48},
1153 {0x86, 0xb9, 0x2a, 0x7f, 0x8e, 0xa8, 0x60, 0x42,
1154 0x26, 0x6d, 0x6e, 0x1c, 0xa2, 0xec, 0xe0, 0xe5,
1155 0x3e, 0x0a, 0x33, 0xbb, 0x61, 0x4c, 0x9f, 0x3c,
1156 0xd1, 0xdf, 0x49, 0x33, 0xcd, 0x72, 0x78, 0x18}},
1157 {{0xf7, 0xd3, 0xcd, 0x49, 0x5c, 0x13, 0x22, 0xfb,
1158 0x2e, 0xb2, 0x2f, 0x27, 0xf5, 0x8a, 0x5d, 0x74,
1159 0xc1, 0x58, 0xc5, 0xc2, 0x2d, 0x9f, 0x52, 0xc6,
1160 0x63, 0x9f, 0xba, 0x05, 0x76, 0x45, 0x7a, 0x63},
1161 {0x8a, 0xfa, 0x55, 0x4d, 0xdd, 0xa3, 0xb2, 0xc3,
1162 0x44, 0xfd, 0xec, 0x72, 0xde, 0xef, 0xc0, 0x99,
1163 0xf5, 0x9f, 0xe2, 0x52, 0xb4, 0x05, 0x32, 0x58,
1164 0x57, 0xc1, 0x8f, 0xea, 0xc3, 0x24, 0x5b, 0x94}},
1165 {{0x05, 0x83, 0xee, 0xdd, 0x64, 0xf0, 0x14, 0x3b,
1166 0xa0, 0x14, 0x4a, 0x3a, 0x41, 0x82, 0x7c, 0xa7,
1167 0x2c, 0xaa, 0xb1, 0x76, 0xbb, 0x59, 0x64, 0x5f,
1168 0x52, 0xad, 0x25, 0x29, 0x9d, 0x8f, 0x0b, 0xb0},
1169 {0x7e, 0xe3, 0x7c, 0xca, 0xcd, 0x4f, 0xb0, 0x6d,
1170 0x7a, 0xb2, 0x3e, 0xa0, 0x08, 0xb9, 0xa8, 0x2d,
1171 0xc2, 0xf4, 0x99, 0x66, 0xcc, 0xac, 0xd8, 0xb9,
1172 0x72, 0x2a, 0x4a, 0x3e, 0x0f, 0x7b, 0xbf, 0xf4}},
1173 {{0x8c, 0x9c, 0x78, 0x2b, 0x39, 0x61, 0x7e, 0xf7,
1174 0x65, 0x37, 0x66, 0x09, 0x38, 0xb9, 0x6f, 0x70,
1175 0x78, 0x87, 0xff, 0xcf, 0x93, 0xca, 0x85, 0x06,
1176 0x44, 0x84, 0xa7, 0xfe, 0xd3, 0xa4, 0xe3, 0x7e},
1177 {0xa2, 0x56, 0x49, 0x23, 0x54, 0xa5, 0x50, 0xe9,
1178 0x5f, 0xf0, 0x4d, 0xe7, 0xdc, 0x38, 0x32, 0x79,
1179 0x4f, 0x1c, 0xb7, 0xe4, 0xbb, 0xf8, 0xbb, 0x2e,
1180 0x40, 0x41, 0x4b, 0xcc, 0xe3, 0x1e, 0x16, 0x36}},
1181 {{0x0c, 0x1e, 0xd7, 0x09, 0x25, 0x40, 0x97, 0xcb,
1182 0x5c, 0x46, 0xa8, 0xda, 0xef, 0x25, 0xd5, 0xe5,
1183 0x92, 0x4d, 0xcf, 0xa3, 0xc4, 0x5d, 0x35, 0x4a,
1184 0xe4, 0x61, 0x92, 0xf3, 0xbf, 0x0e, 0xcd, 0xbe},
1185 {0xe4, 0xaf, 0x0a, 0xb3, 0x30, 0x8b, 0x9b, 0x48,
1186 0x49, 0x43, 0xc7, 0x64, 0x60, 0x4a, 0x2b, 0x9e,
1187 0x95, 0x5f, 0x56, 0xe8, 0x35, 0xdc, 0xeb, 0xdc,
1188 0xc7, 0xc4, 0xfe, 0x30, 0x40, 0xc7, 0xbf, 0xa4}},
1189 {{0xd4, 0xa0, 0xf5, 0x81, 0x49, 0x6b, 0xb6, 0x8b,
1190 0x0a, 0x69, 0xf9, 0xfe, 0xa8, 0x32, 0xe5, 0xe0,
1191 0xa5, 0xcd, 0x02, 0x53, 0xf9, 0x2c, 0xe3, 0x53,
1192 0x83, 0x36, 0xc6, 0x02, 0xb5, 0xeb, 0x64, 0xb8},
1193 {0x1d, 0x42, 0xb9, 0xf9, 0xe9, 0xe3, 0x93, 0x2c,
1194 0x4c, 0xee, 0x6c, 0x5a, 0x47, 0x9e, 0x62, 0x01,
1195 0x6b, 0x04, 0xfe, 0xa4, 0x30, 0x2b, 0x0d, 0x4f,
1196 0x71, 0x10, 0xd3, 0x55, 0xca, 0xf3, 0x5e, 0x80}},
1197 {{0x77, 0x05, 0xf6, 0x0c, 0x15, 0x9b, 0x45, 0xe7,
1198 0xb9, 0x11, 0xb8, 0xf5, 0xd6, 0xda, 0x73, 0x0c,
1199 0xda, 0x92, 0xea, 0xd0, 0x9d, 0xd0, 0x18, 0x92,
1200 0xce, 0x9a, 0xaa, 0xee, 0x0f, 0xef, 0xde, 0x30},
1201 {0xf1, 0xf1, 0xd6, 0x9b, 0x51, 0xd7, 0x77, 0x62,
1202 0x52, 0x10, 0xb8, 0x7a, 0x84, 0x9d, 0x15, 0x4e,
1203 0x07, 0xdc, 0x1e, 0x75, 0x0d, 0x0c, 0x3b, 0xdb,
1204 0x74, 0x58, 0x62, 0x02, 0x90, 0x54, 0x8b, 0x43}},
1205 {{0xa6, 0xfe, 0x0b, 0x87, 0x80, 0x43, 0x67, 0x25,
1206 0x57, 0x5d, 0xec, 0x40, 0x50, 0x08, 0xd5, 0x5d,
1207 0x43, 0xd7, 0xe0, 0xaa, 0xe0, 0x13, 0xb6, 0xb0,
1208 0xc0, 0xd4, 0xe5, 0x0d, 0x45, 0x83, 0xd6, 0x13},
1209 {0x40, 0x45, 0x0a, 0x92, 0x31, 0xea, 0x8c, 0x60,
1210 0x8c, 0x1f, 0xd8, 0x76, 0x45, 0xb9, 0x29, 0x00,
1211 0x26, 0x32, 0xd8, 0xa6, 0x96, 0x88, 0xe2, 0xc4,
1212 0x8b, 0xdb, 0x7f, 0x17, 0x87, 0xcc, 0xc8, 0xf2}},
1213 {{0xc2, 0x56, 0xe2, 0xb6, 0x1a, 0x81, 0xe7, 0x31,
1214 0x63, 0x2e, 0xbb, 0x0d, 0x2f, 0x81, 0x67, 0xd4,
1215 0x22, 0xe2, 0x38, 0x02, 0x25, 0x97, 0xc7, 0x88,
1216 0x6e, 0xdf, 0xbe, 0x2a, 0xa5, 0x73, 0x63, 0xaa},
1217 {0x50, 0x45, 0xe2, 0xc3, 0xbd, 0x89, 0xfc, 0x57,
1218 0xbd, 0x3c, 0xa3, 0x98, 0x7e, 0x7f, 0x36, 0x38,
1219 0x92, 0x39, 0x1f, 0x0f, 0x81, 0x1a, 0x06, 0x51,
1220 0x1f, 0x8d, 0x6a, 0xff, 0x47, 0x16, 0x06, 0x9c}},
1221 {{0x33, 0x95, 0xa2, 0x6f, 0x27, 0x5f, 0x9c, 0x9c,
1222 0x64, 0x45, 0xcb, 0xd1, 0x3c, 0xee, 0x5e, 0x5f,
1223 0x48, 0xa6, 0xaf, 0xe3, 0x79, 0xcf, 0xb1, 0xe2,
1224 0xbf, 0x55, 0x0e, 0xa2, 0x3b, 0x62, 0xf0, 0xe4},
1225 {0x14, 0xe8, 0x06, 0xe3, 0xbe, 0x7e, 0x67, 0x01,
1226 0xc5, 0x21, 0x67, 0xd8, 0x54, 0xb5, 0x7f, 0xa4,
1227 0xf9, 0x75, 0x70, 0x1c, 0xfd, 0x79, 0xdb, 0x86,
1228 0xad, 0x37, 0x85, 0x83, 0x56, 0x4e, 0xf0, 0xbf}},
1229 {{0xbc, 0xa6, 0xe0, 0x56, 0x4e, 0xef, 0xfa, 0xf5,
1230 0x1d, 0x5d, 0x3f, 0x2a, 0x5b, 0x19, 0xab, 0x51,
1231 0xc5, 0x8b, 0xdd, 0x98, 0x28, 0x35, 0x2f, 0xc3,
1232 0x81, 0x4f, 0x5c, 0xe5, 0x70, 0xb9, 0xeb, 0x62},
1233 {0xc4, 0x6d, 0x26, 0xb0, 0x17, 0x6b, 0xfe, 0x6c,
1234 0x12, 0xf8, 0xe7, 0xc1, 0xf5, 0x2f, 0xfa, 0x91,
1235 0x13, 0x27, 0xbd, 0x73, 0xcc, 0x33, 0x31, 0x1c,
1236 0x39, 0xe3, 0x27, 0x6a, 0x95, 0xcf, 0xc5, 0xfb}},
1237 {{0x30, 0xb2, 0x99, 0x84, 0xf0, 0x18, 0x2a, 0x6e,
1238 0x1e, 0x27, 0xed, 0xa2, 0x29, 0x99, 0x41, 0x56,
1239 0xe8, 0xd4, 0x0d, 0xef, 0x99, 0x9c, 0xf3, 0x58,
1240 0x29, 0x55, 0x1a, 0xc0, 0x68, 0xd6, 0x74, 0xa4},
1241 {0x07, 0x9c, 0xe7, 0xec, 0xf5, 0x36, 0x73, 0x41,
1242 0xa3, 0x1c, 0xe5, 0x93, 0x97, 0x6a, 0xfd, 0xf7,
1243 0x53, 0x18, 0xab, 0xaf, 0xeb, 0x85, 0xbd, 0x92,
1244 0x90, 0xab, 0x3c, 0xbf, 0x30, 0x82, 0xad, 0xf6}},
1245 {{0xc6, 0x87, 0x8a, 0x2a, 0xea, 0xc0, 0xa9, 0xec,
1246 0x6d, 0xd3, 0xdc, 0x32, 0x23, 0xce, 0x62, 0x19,
1247 0xa4, 0x7e, 0xa8, 0xdd, 0x1c, 0x33, 0xae, 0xd3,
1248 0x4f, 0x62, 0x9f, 0x52, 0xe7, 0x65, 0x46, 0xf4},
1249 {0x97, 0x51, 0x27, 0x67, 0x2d, 0xa2, 0x82, 0x87,
1250 0x98, 0xd3, 0xb6, 0x14, 0x7f, 0x51, 0xd3, 0x9a,
1251 0x0b, 0xd0, 0x76, 0x81, 0xb2, 0x4f, 0x58, 0x92,
1252 0xa4, 0x86, 0xa1, 0xa7, 0x09, 0x1d, 0xef, 0x9b}},
1253 {{0xb3, 0x0f, 0x2b, 0x69, 0x0d, 0x06, 0x90, 0x64,
1254 0xbd, 0x43, 0x4c, 0x10, 0xe8, 0x98, 0x1c, 0xa3,
1255 0xe1, 0x68, 0xe9, 0x79, 0x6c, 0x29, 0x51, 0x3f,
1256 0x41, 0xdc, 0xdf, 0x1f, 0xf3, 0x60, 0xbe, 0x33},
1257 {0xa1, 0x5f, 0xf7, 0x1d, 0xb4, 0x3e, 0x9b, 0x3c,
1258 0xe7, 0xbd, 0xb6, 0x06, 0xd5, 0x60, 0x06, 0x6d,
1259 0x50, 0xd2, 0xf4, 0x1a, 0x31, 0x08, 0xf2, 0xea,
1260 0x8e, 0xef, 0x5f, 0x7d, 0xb6, 0xd0, 0xc0, 0x27}},
1261 {{0x62, 0x9a, 0xd9, 0xbb, 0x38, 0x36, 0xce, 0xf7,
1262 0x5d, 0x2f, 0x13, 0xec, 0xc8, 0x2d, 0x02, 0x8a,
1263 0x2e, 0x72, 0xf0, 0xe5, 0x15, 0x9d, 0x72, 0xae,
1264 0xfc, 0xb3, 0x4f, 0x02, 0xea, 0xe1, 0x09, 0xfe},
1265 {0x00, 0x00, 0x00, 0x00, 0xfa, 0x0a, 0x3d, 0xbc,
1266 0xad, 0x16, 0x0c, 0xb6, 0xe7, 0x7c, 0x8b, 0x39,
1267 0x9a, 0x43, 0xbb, 0xe3, 0xc2, 0x55, 0x15, 0x14,
1268 0x75, 0xac, 0x90, 0x9b, 0x7f, 0x9a, 0x92, 0x00}},
1269 {{0x8b, 0xac, 0x70, 0x86, 0x29, 0x8f, 0x00, 0x23,
1270 0x7b, 0x45, 0x30, 0xaa, 0xb8, 0x4c, 0xc7, 0x8d,
1271 0x4e, 0x47, 0x85, 0xc6, 0x19, 0xe3, 0x96, 0xc2,
1272 0x9a, 0xa0, 0x12, 0xed, 0x6f, 0xd7, 0x76, 0x16},
1273 {0x45, 0xaf, 0x7e, 0x33, 0xc7, 0x7f, 0x10, 0x6c,
1274 0x7c, 0x9f, 0x29, 0xc1, 0xa8, 0x7e, 0x15, 0x84,
1275 0xe7, 0x7d, 0xc0, 0x6d, 0xab, 0x71, 0x5d, 0xd0,
1276 0x6b, 0x9f, 0x97, 0xab, 0xcb, 0x51, 0x0c, 0x9f}},
1277 {{0x9e, 0xc3, 0x92, 0xb4, 0x04, 0x9f, 0xc8, 0xbb,
1278 0xdd, 0x9e, 0xc6, 0x05, 0xfd, 0x65, 0xec, 0x94,
1279 0x7f, 0x2c, 0x16, 0xc4, 0x40, 0xac, 0x63, 0x7b,
1280 0x7d, 0xb8, 0x0c, 0xe4, 0x5b, 0xe3, 0xa7, 0x0e},
1281 {0x43, 0xf4, 0x44, 0xe8, 0xcc, 0xc8, 0xd4, 0x54,
1282 0x33, 0x37, 0x50, 0xf2, 0x87, 0x42, 0x2e, 0x00,
1283 0x49, 0x60, 0x62, 0x02, 0xfd, 0x1a, 0x7c, 0xdb,
1284 0x29, 0x6c, 0x6d, 0x54, 0x53, 0x08, 0xd1, 0xc8}},
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, 0x00}},
1293 {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1294 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1295 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1296 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00},
1297 {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1298 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1299 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1300 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01}},
1301 {{0x27, 0x59, 0xc7, 0x35, 0x60, 0x71, 0xa6, 0xf1,
1302 0x79, 0xa5, 0xfd, 0x79, 0x16, 0xf3, 0x41, 0xf0,
1303 0x57, 0xb4, 0x02, 0x97, 0x32, 0xe7, 0xde, 0x59,
1304 0xe2, 0x2d, 0x9b, 0x11, 0xea, 0x2c, 0x35, 0x92},
1305 {0x27, 0x59, 0xc7, 0x35, 0x60, 0x71, 0xa6, 0xf1,
1306 0x79, 0xa5, 0xfd, 0x79, 0x16, 0xf3, 0x41, 0xf0,
1307 0x57, 0xb4, 0x02, 0x97, 0x32, 0xe7, 0xde, 0x59,
1308 0xe2, 0x2d, 0x9b, 0x11, 0xea, 0x2c, 0x35, 0x92}},
1309 {{0x28, 0x56, 0xac, 0x0e, 0x4f, 0x98, 0x09, 0xf0,
1310 0x49, 0xfa, 0x7f, 0x84, 0xac, 0x7e, 0x50, 0x5b,
1311 0x17, 0x43, 0x14, 0x89, 0x9c, 0x53, 0xa8, 0x94,
1312 0x30, 0xf2, 0x11, 0x4d, 0x92, 0x14, 0x27, 0xe8},
1313 {0x39, 0x7a, 0x84, 0x56, 0x79, 0x9d, 0xec, 0x26,
1314 0x2c, 0x53, 0xc1, 0x94, 0xc9, 0x8d, 0x9e, 0x9d,
1315 0x32, 0x1f, 0xdd, 0x84, 0x04, 0xe8, 0xe2, 0x0a,
1316 0x6b, 0xbe, 0xbb, 0x42, 0x40, 0x67, 0x30, 0x6c}},
1317 {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1318 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
1319 0x45, 0x51, 0x23, 0x19, 0x50, 0xb7, 0x5f, 0xc4,
1320 0x40, 0x2d, 0xa1, 0x73, 0x2f, 0xc9, 0xbe, 0xbd},
1321 {0x27, 0x59, 0xc7, 0x35, 0x60, 0x71, 0xa6, 0xf1,
1322 0x79, 0xa5, 0xfd, 0x79, 0x16, 0xf3, 0x41, 0xf0,
1323 0x57, 0xb4, 0x02, 0x97, 0x32, 0xe7, 0xde, 0x59,
1324 0xe2, 0x2d, 0x9b, 0x11, 0xea, 0x2c, 0x35, 0x92}},
1325 {{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1326 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
1327 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
1328 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x40},
1329 {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1330 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1331 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1332 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01}},
1333 {{0x1c, 0xc4, 0xf7, 0xda, 0x0f, 0x65, 0xca, 0x39,
1334 0x70, 0x52, 0x92, 0x8e, 0xc3, 0xc8, 0x15, 0xea,
1335 0x7f, 0x10, 0x9e, 0x77, 0x4b, 0x6e, 0x2d, 0xdf,
1336 0xe8, 0x30, 0x9d, 0xda, 0xe8, 0x9a, 0x65, 0xae},
1337 {0x02, 0xb0, 0x16, 0xb1, 0x1d, 0xc8, 0x57, 0x7b,
1338 0xa2, 0x3a, 0xa2, 0xa3, 0x38, 0x5c, 0x8f, 0xeb,
1339 0x66, 0x37, 0x91, 0xa8, 0x5f, 0xef, 0x04, 0xf6,
1340 0x59, 0x75, 0xe1, 0xee, 0x92, 0xf6, 0x0e, 0x30}},
1341 {{0x8d, 0x76, 0x14, 0xa4, 0x14, 0x06, 0x9f, 0x9a,
1342 0xdf, 0x4a, 0x85, 0xa7, 0x6b, 0xbf, 0x29, 0x6f,
1343 0xbc, 0x34, 0x87, 0x5d, 0xeb, 0xbb, 0x2e, 0xa9,
1344 0xc9, 0x1f, 0x58, 0xd6, 0x9a, 0x82, 0xa0, 0x56},
1345 {0xd4, 0xb9, 0xdb, 0x88, 0x1d, 0x04, 0xe9, 0x93,
1346 0x8d, 0x3f, 0x20, 0xd5, 0x86, 0xa8, 0x83, 0x07,
1347 0xdb, 0x09, 0xd8, 0x22, 0x1f, 0x7f, 0xf1, 0x71,
1348 0xc8, 0xe7, 0x5d, 0x47, 0xaf, 0x8b, 0x72, 0xe9}},
1349 {{0x83, 0xb9, 0x39, 0xb2, 0xa4, 0xdf, 0x46, 0x87,
1350 0xc2, 0xb8, 0xf1, 0xe6, 0x4c, 0xd1, 0xe2, 0xa9,
1351 0xe4, 0x70, 0x30, 0x34, 0xbc, 0x52, 0x7c, 0x55,
1352 0xa6, 0xec, 0x80, 0xa4, 0xe5, 0xd2, 0xdc, 0x73},
1353 {0x08, 0xf1, 0x03, 0xcf, 0x16, 0x73, 0xe8, 0x7d,
1354 0xb6, 0x7e, 0x9b, 0xc0, 0xb4, 0xc2, 0xa5, 0x86,
1355 0x02, 0x77, 0xd5, 0x27, 0x86, 0xa5, 0x15, 0xfb,
1356 0xae, 0x9b, 0x8c, 0xa9, 0xf9, 0xf8, 0xa8, 0x4a}},
1357 {{0x8b, 0x00, 0x49, 0xdb, 0xfa, 0xf0, 0x1b, 0xa2,
1358 0xed, 0x8a, 0x9a, 0x7a, 0x36, 0x78, 0x4a, 0xc7,
1359 0xf7, 0xad, 0x39, 0xd0, 0x6c, 0x65, 0x7a, 0x41,
1360 0xce, 0xd6, 0xd6, 0x4c, 0x20, 0x21, 0x6b, 0xc7},
1361 {0xc6, 0xca, 0x78, 0x1d, 0x32, 0x6c, 0x6c, 0x06,
1362 0x91, 0xf2, 0x1a, 0xe8, 0x43, 0x16, 0xea, 0x04,
1363 0x3c, 0x1f, 0x07, 0x85, 0xf7, 0x09, 0x22, 0x08,
1364 0xba, 0x13, 0xfd, 0x78, 0x1e, 0x3f, 0x6f, 0x62}},
1365 {{0x25, 0x9b, 0x7c, 0xb0, 0xac, 0x72, 0x6f, 0xb2,
1366 0xe3, 0x53, 0x84, 0x7a, 0x1a, 0x9a, 0x98, 0x9b,
1367 0x44, 0xd3, 0x59, 0xd0, 0x8e, 0x57, 0x41, 0x40,
1368 0x78, 0xa7, 0x30, 0x2f, 0x4c, 0x9c, 0xb9, 0x68},
1369 {0xb7, 0x75, 0x03, 0x63, 0x61, 0xc2, 0x48, 0x6e,
1370 0x12, 0x3d, 0xbf, 0x4b, 0x27, 0xdf, 0xb1, 0x7a,
1371 0xff, 0x4e, 0x31, 0x07, 0x83, 0xf4, 0x62, 0x5b,
1372 0x19, 0xa5, 0xac, 0xa0, 0x32, 0x58, 0x0d, 0xa7}},
1373 {{0x43, 0x4f, 0x10, 0xa4, 0xca, 0xdb, 0x38, 0x67,
1374 0xfa, 0xae, 0x96, 0xb5, 0x6d, 0x97, 0xff, 0x1f,
1375 0xb6, 0x83, 0x43, 0xd3, 0xa0, 0x2d, 0x70, 0x7a,
1376 0x64, 0x05, 0x4c, 0xa7, 0xc1, 0xa5, 0x21, 0x51},
1377 {0xe4, 0xf1, 0x23, 0x84, 0xe1, 0xb5, 0x9d, 0xf2,
1378 0xb8, 0x73, 0x8b, 0x45, 0x2b, 0x35, 0x46, 0x38,
1379 0x10, 0x2b, 0x50, 0xf8, 0x8b, 0x35, 0xcd, 0x34,
1380 0xc8, 0x0e, 0xf6, 0xdb, 0x09, 0x35, 0xf0, 0xda}},
1381 {{0xdb, 0x21, 0x5c, 0x8d, 0x83, 0x1d, 0xb3, 0x34,
1382 0xc7, 0x0e, 0x43, 0xa1, 0x58, 0x79, 0x67, 0x13,
1383 0x1e, 0x86, 0x5d, 0x89, 0x63, 0xe6, 0x0a, 0x46,
1384 0x5c, 0x02, 0x97, 0x1b, 0x62, 0x43, 0x86, 0xf5},
1385 {0xdb, 0x21, 0x5c, 0x8d, 0x83, 0x1d, 0xb3, 0x34,
1386 0xc7, 0x0e, 0x43, 0xa1, 0x58, 0x79, 0x67, 0x13,
1387 0x1e, 0x86, 0x5d, 0x89, 0x63, 0xe6, 0x0a, 0x46,
1388 0x5c, 0x02, 0x97, 0x1b, 0x62, 0x43, 0x86, 0xf5}}
1390 secp256k1_scalar_set_int(&one, 1);
1391 for (i = 0; i < 33; i++) {
1392 secp256k1_scalar_set_b32(&x, chal[i][0], &overflow);
1394 secp256k1_scalar_set_b32(&y, chal[i][1], &overflow);
1396 secp256k1_scalar_set_b32(&r1, res[i][0], &overflow);
1398 secp256k1_scalar_set_b32(&r2, res[i][1], &overflow);
1400 secp256k1_scalar_mul(&z, &x, &y);
1401 CHECK(!secp256k1_scalar_check_overflow(&z));
1402 CHECK(secp256k1_scalar_eq(&r1, &z));
1403 if (!secp256k1_scalar_is_zero(&y)) {
1404 secp256k1_scalar_inverse(&zz, &y);
1405 CHECK(!secp256k1_scalar_check_overflow(&zz));
1406 #if defined(USE_SCALAR_INV_NUM)
1407 secp256k1_scalar_inverse_var(&zzv, &y);
1408 CHECK(secp256k1_scalar_eq(&zzv, &zz));
1410 secp256k1_scalar_mul(&z, &z, &zz);
1411 CHECK(!secp256k1_scalar_check_overflow(&z));
1412 CHECK(secp256k1_scalar_eq(&x, &z));
1413 secp256k1_scalar_mul(&zz, &zz, &y);
1414 CHECK(!secp256k1_scalar_check_overflow(&zz));
1415 CHECK(secp256k1_scalar_eq(&one, &zz));
1417 secp256k1_scalar_mul(&z, &x, &x);
1418 CHECK(!secp256k1_scalar_check_overflow(&z));
1419 secp256k1_scalar_sqr(&zz, &x);
1420 CHECK(!secp256k1_scalar_check_overflow(&zz));
1421 CHECK(secp256k1_scalar_eq(&zz, &z));
1422 CHECK(secp256k1_scalar_eq(&r2, &zz));
1427 /***** FIELD TESTS *****/
1429 void random_fe(secp256k1_fe *x) {
1430 unsigned char bin[32];
1432 secp256k1_rand256(bin);
1433 if (secp256k1_fe_set_b32(x, bin)) {
1439 void random_fe_test(secp256k1_fe *x) {
1440 unsigned char bin[32];
1442 secp256k1_rand256_test(bin);
1443 if (secp256k1_fe_set_b32(x, bin)) {
1449 void random_fe_non_zero(secp256k1_fe *nz) {
1451 while (--tries >= 0) {
1453 secp256k1_fe_normalize(nz);
1454 if (!secp256k1_fe_is_zero(nz)) {
1458 /* Infinitesimal probability of spurious failure here */
1462 void random_fe_non_square(secp256k1_fe *ns) {
1464 random_fe_non_zero(ns);
1465 if (secp256k1_fe_sqrt_var(&r, ns)) {
1466 secp256k1_fe_negate(ns, ns, 1);
1470 int check_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b) {
1471 secp256k1_fe an = *a;
1472 secp256k1_fe bn = *b;
1473 secp256k1_fe_normalize_weak(&an);
1474 secp256k1_fe_normalize_var(&bn);
1475 return secp256k1_fe_equal_var(&an, &bn);
1478 int check_fe_inverse(const secp256k1_fe *a, const secp256k1_fe *ai) {
1480 secp256k1_fe one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1);
1481 secp256k1_fe_mul(&x, a, ai);
1482 return check_fe_equal(&x, &one);
1485 void run_field_convert(void) {
1486 static const unsigned char b32[32] = {
1487 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
1488 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18,
1489 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29,
1490 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x40
1492 static const secp256k1_fe_storage fes = SECP256K1_FE_STORAGE_CONST(
1493 0x00010203UL, 0x04050607UL, 0x11121314UL, 0x15161718UL,
1494 0x22232425UL, 0x26272829UL, 0x33343536UL, 0x37383940UL
1496 static const secp256k1_fe fe = SECP256K1_FE_CONST(
1497 0x00010203UL, 0x04050607UL, 0x11121314UL, 0x15161718UL,
1498 0x22232425UL, 0x26272829UL, 0x33343536UL, 0x37383940UL
1501 unsigned char b322[32];
1502 secp256k1_fe_storage fes2;
1503 /* Check conversions to fe. */
1504 CHECK(secp256k1_fe_set_b32(&fe2, b32));
1505 CHECK(secp256k1_fe_equal_var(&fe, &fe2));
1506 secp256k1_fe_from_storage(&fe2, &fes);
1507 CHECK(secp256k1_fe_equal_var(&fe, &fe2));
1508 /* Check conversion from fe. */
1509 secp256k1_fe_get_b32(b322, &fe);
1510 CHECK(memcmp(b322, b32, 32) == 0);
1511 secp256k1_fe_to_storage(&fes2, &fe);
1512 CHECK(memcmp(&fes2, &fes, sizeof(fes)) == 0);
1515 int fe_memcmp(const secp256k1_fe *a, const secp256k1_fe *b) {
1516 secp256k1_fe t = *b;
1518 t.magnitude = a->magnitude;
1519 t.normalized = a->normalized;
1521 return memcmp(a, &t, sizeof(secp256k1_fe));
1524 void run_field_misc(void) {
1529 secp256k1_fe fe5 = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 5);
1531 for (i = 0; i < 5*count; i++) {
1532 secp256k1_fe_storage xs, ys, zs;
1534 random_fe_non_zero(&y);
1535 /* Test the fe equality and comparison operations. */
1536 CHECK(secp256k1_fe_cmp_var(&x, &x) == 0);
1537 CHECK(secp256k1_fe_equal_var(&x, &x));
1539 secp256k1_fe_add(&z,&y);
1540 /* Test fe conditional move; z is not normalized here. */
1542 secp256k1_fe_cmov(&x, &z, 0);
1543 VERIFY_CHECK(!x.normalized && x.magnitude == z.magnitude);
1544 secp256k1_fe_cmov(&x, &x, 1);
1545 CHECK(fe_memcmp(&x, &z) != 0);
1546 CHECK(fe_memcmp(&x, &q) == 0);
1547 secp256k1_fe_cmov(&q, &z, 1);
1548 VERIFY_CHECK(!q.normalized && q.magnitude == z.magnitude);
1549 CHECK(fe_memcmp(&q, &z) == 0);
1550 secp256k1_fe_normalize_var(&x);
1551 secp256k1_fe_normalize_var(&z);
1552 CHECK(!secp256k1_fe_equal_var(&x, &z));
1553 secp256k1_fe_normalize_var(&q);
1554 secp256k1_fe_cmov(&q, &z, (i&1));
1555 VERIFY_CHECK(q.normalized && q.magnitude == 1);
1556 for (j = 0; j < 6; j++) {
1557 secp256k1_fe_negate(&z, &z, j+1);
1558 secp256k1_fe_normalize_var(&q);
1559 secp256k1_fe_cmov(&q, &z, (j&1));
1560 VERIFY_CHECK(!q.normalized && q.magnitude == (j+2));
1562 secp256k1_fe_normalize_var(&z);
1563 /* Test storage conversion and conditional moves. */
1564 secp256k1_fe_to_storage(&xs, &x);
1565 secp256k1_fe_to_storage(&ys, &y);
1566 secp256k1_fe_to_storage(&zs, &z);
1567 secp256k1_fe_storage_cmov(&zs, &xs, 0);
1568 secp256k1_fe_storage_cmov(&zs, &zs, 1);
1569 CHECK(memcmp(&xs, &zs, sizeof(xs)) != 0);
1570 secp256k1_fe_storage_cmov(&ys, &xs, 1);
1571 CHECK(memcmp(&xs, &ys, sizeof(xs)) == 0);
1572 secp256k1_fe_from_storage(&x, &xs);
1573 secp256k1_fe_from_storage(&y, &ys);
1574 secp256k1_fe_from_storage(&z, &zs);
1575 /* Test that mul_int, mul, and add agree. */
1576 secp256k1_fe_add(&y, &x);
1577 secp256k1_fe_add(&y, &x);
1579 secp256k1_fe_mul_int(&z, 3);
1580 CHECK(check_fe_equal(&y, &z));
1581 secp256k1_fe_add(&y, &x);
1582 secp256k1_fe_add(&z, &x);
1583 CHECK(check_fe_equal(&z, &y));
1585 secp256k1_fe_mul_int(&z, 5);
1586 secp256k1_fe_mul(&q, &x, &fe5);
1587 CHECK(check_fe_equal(&z, &q));
1588 secp256k1_fe_negate(&x, &x, 1);
1589 secp256k1_fe_add(&z, &x);
1590 secp256k1_fe_add(&q, &x);
1591 CHECK(check_fe_equal(&y, &z));
1592 CHECK(check_fe_equal(&q, &y));
1596 void run_field_inv(void) {
1597 secp256k1_fe x, xi, xii;
1599 for (i = 0; i < 10*count; i++) {
1600 random_fe_non_zero(&x);
1601 secp256k1_fe_inv(&xi, &x);
1602 CHECK(check_fe_inverse(&x, &xi));
1603 secp256k1_fe_inv(&xii, &xi);
1604 CHECK(check_fe_equal(&x, &xii));
1608 void run_field_inv_var(void) {
1609 secp256k1_fe x, xi, xii;
1611 for (i = 0; i < 10*count; i++) {
1612 random_fe_non_zero(&x);
1613 secp256k1_fe_inv_var(&xi, &x);
1614 CHECK(check_fe_inverse(&x, &xi));
1615 secp256k1_fe_inv_var(&xii, &xi);
1616 CHECK(check_fe_equal(&x, &xii));
1620 void run_field_inv_all_var(void) {
1621 secp256k1_fe x[16], xi[16], xii[16];
1623 /* Check it's safe to call for 0 elements */
1624 secp256k1_fe_inv_all_var(0, xi, x);
1625 for (i = 0; i < count; i++) {
1627 size_t len = secp256k1_rand_int(15) + 1;
1628 for (j = 0; j < len; j++) {
1629 random_fe_non_zero(&x[j]);
1631 secp256k1_fe_inv_all_var(len, xi, x);
1632 for (j = 0; j < len; j++) {
1633 CHECK(check_fe_inverse(&x[j], &xi[j]));
1635 secp256k1_fe_inv_all_var(len, xii, xi);
1636 for (j = 0; j < len; j++) {
1637 CHECK(check_fe_equal(&x[j], &xii[j]));
1642 void run_sqr(void) {
1647 secp256k1_fe_set_int(&x, 1);
1648 secp256k1_fe_negate(&x, &x, 1);
1650 for (i = 1; i <= 512; ++i) {
1651 secp256k1_fe_mul_int(&x, 2);
1652 secp256k1_fe_normalize(&x);
1653 secp256k1_fe_sqr(&s, &x);
1658 void test_sqrt(const secp256k1_fe *a, const secp256k1_fe *k) {
1659 secp256k1_fe r1, r2;
1660 int v = secp256k1_fe_sqrt_var(&r1, a);
1661 CHECK((v == 0) == (k == NULL));
1664 /* Check that the returned root is +/- the given known answer */
1665 secp256k1_fe_negate(&r2, &r1, 1);
1666 secp256k1_fe_add(&r1, k); secp256k1_fe_add(&r2, k);
1667 secp256k1_fe_normalize(&r1); secp256k1_fe_normalize(&r2);
1668 CHECK(secp256k1_fe_is_zero(&r1) || secp256k1_fe_is_zero(&r2));
1672 void run_sqrt(void) {
1673 secp256k1_fe ns, x, s, t;
1676 /* Check sqrt(0) is 0 */
1677 secp256k1_fe_set_int(&x, 0);
1678 secp256k1_fe_sqr(&s, &x);
1681 /* Check sqrt of small squares (and their negatives) */
1682 for (i = 1; i <= 100; i++) {
1683 secp256k1_fe_set_int(&x, i);
1684 secp256k1_fe_sqr(&s, &x);
1686 secp256k1_fe_negate(&t, &s, 1);
1687 test_sqrt(&t, NULL);
1690 /* Consistency checks for large random values */
1691 for (i = 0; i < 10; i++) {
1693 random_fe_non_square(&ns);
1694 for (j = 0; j < count; j++) {
1696 secp256k1_fe_sqr(&s, &x);
1698 secp256k1_fe_negate(&t, &s, 1);
1699 test_sqrt(&t, NULL);
1700 secp256k1_fe_mul(&t, &s, &ns);
1701 test_sqrt(&t, NULL);
1706 /***** GROUP TESTS *****/
1708 void ge_equals_ge(const secp256k1_ge *a, const secp256k1_ge *b) {
1709 CHECK(a->infinity == b->infinity);
1713 CHECK(secp256k1_fe_equal_var(&a->x, &b->x));
1714 CHECK(secp256k1_fe_equal_var(&a->y, &b->y));
1717 /* This compares jacobian points including their Z, not just their geometric meaning. */
1718 int gej_xyz_equals_gej(const secp256k1_gej *a, const secp256k1_gej *b) {
1722 ret &= a->infinity == b->infinity;
1723 if (ret && !a->infinity) {
1726 secp256k1_fe_normalize(&a2.x);
1727 secp256k1_fe_normalize(&a2.y);
1728 secp256k1_fe_normalize(&a2.z);
1729 secp256k1_fe_normalize(&b2.x);
1730 secp256k1_fe_normalize(&b2.y);
1731 secp256k1_fe_normalize(&b2.z);
1732 ret &= secp256k1_fe_cmp_var(&a2.x, &b2.x) == 0;
1733 ret &= secp256k1_fe_cmp_var(&a2.y, &b2.y) == 0;
1734 ret &= secp256k1_fe_cmp_var(&a2.z, &b2.z) == 0;
1739 void ge_equals_gej(const secp256k1_ge *a, const secp256k1_gej *b) {
1741 secp256k1_fe u1, u2, s1, s2;
1742 CHECK(a->infinity == b->infinity);
1746 /* Check a.x * b.z^2 == b.x && a.y * b.z^3 == b.y, to avoid inverses. */
1747 secp256k1_fe_sqr(&z2s, &b->z);
1748 secp256k1_fe_mul(&u1, &a->x, &z2s);
1749 u2 = b->x; secp256k1_fe_normalize_weak(&u2);
1750 secp256k1_fe_mul(&s1, &a->y, &z2s); secp256k1_fe_mul(&s1, &s1, &b->z);
1751 s2 = b->y; secp256k1_fe_normalize_weak(&s2);
1752 CHECK(secp256k1_fe_equal_var(&u1, &u2));
1753 CHECK(secp256k1_fe_equal_var(&s1, &s2));
1756 void test_ge(void) {
1758 #ifdef USE_ENDOMORPHISM
1763 /* Points: (infinity, p1, p1, -p1, -p1, p2, p2, -p2, -p2, p3, p3, -p3, -p3, p4, p4, -p4, -p4).
1764 * The second in each pair of identical points uses a random Z coordinate in the Jacobian form.
1765 * All magnitudes are randomized.
1766 * All 17*17 combinations of points are added to each other, using all applicable methods.
1768 * When the endomorphism code is compiled in, p5 = lambda*p1 and p6 = lambda^2*p1 are added as well.
1770 secp256k1_ge *ge = (secp256k1_ge *)malloc(sizeof(secp256k1_ge) * (1 + 4 * runs));
1771 secp256k1_gej *gej = (secp256k1_gej *)malloc(sizeof(secp256k1_gej) * (1 + 4 * runs));
1772 secp256k1_fe *zinv = (secp256k1_fe *)malloc(sizeof(secp256k1_fe) * (1 + 4 * runs));
1774 secp256k1_fe zfi2, zfi3;
1776 secp256k1_gej_set_infinity(&gej[0]);
1777 secp256k1_ge_clear(&ge[0]);
1778 secp256k1_ge_set_gej_var(&ge[0], &gej[0]);
1779 for (i = 0; i < runs; i++) {
1782 random_group_element_test(&g);
1783 #ifdef USE_ENDOMORPHISM
1784 if (i >= runs - 2) {
1785 secp256k1_ge_mul_lambda(&g, &ge[1]);
1787 if (i >= runs - 1) {
1788 secp256k1_ge_mul_lambda(&g, &g);
1793 secp256k1_ge_neg(&ge[3 + 4 * i], &g);
1794 secp256k1_ge_neg(&ge[4 + 4 * i], &g);
1795 secp256k1_gej_set_ge(&gej[1 + 4 * i], &ge[1 + 4 * i]);
1796 random_group_element_jacobian_test(&gej[2 + 4 * i], &ge[2 + 4 * i]);
1797 secp256k1_gej_set_ge(&gej[3 + 4 * i], &ge[3 + 4 * i]);
1798 random_group_element_jacobian_test(&gej[4 + 4 * i], &ge[4 + 4 * i]);
1799 for (j = 0; j < 4; j++) {
1800 random_field_element_magnitude(&ge[1 + j + 4 * i].x);
1801 random_field_element_magnitude(&ge[1 + j + 4 * i].y);
1802 random_field_element_magnitude(&gej[1 + j + 4 * i].x);
1803 random_field_element_magnitude(&gej[1 + j + 4 * i].y);
1804 random_field_element_magnitude(&gej[1 + j + 4 * i].z);
1808 /* Compute z inverses. */
1810 secp256k1_fe *zs = malloc(sizeof(secp256k1_fe) * (1 + 4 * runs));
1811 for (i = 0; i < 4 * runs + 1; i++) {
1813 /* The point at infinity does not have a meaningful z inverse. Any should do. */
1815 random_field_element_test(&zs[i]);
1816 } while(secp256k1_fe_is_zero(&zs[i]));
1821 secp256k1_fe_inv_all_var(4 * runs + 1, zinv, zs);
1825 /* Generate random zf, and zfi2 = 1/zf^2, zfi3 = 1/zf^3 */
1827 random_field_element_test(&zf);
1828 } while(secp256k1_fe_is_zero(&zf));
1829 random_field_element_magnitude(&zf);
1830 secp256k1_fe_inv_var(&zfi3, &zf);
1831 secp256k1_fe_sqr(&zfi2, &zfi3);
1832 secp256k1_fe_mul(&zfi3, &zfi3, &zfi2);
1834 for (i1 = 0; i1 < 1 + 4 * runs; i1++) {
1836 for (i2 = 0; i2 < 1 + 4 * runs; i2++) {
1837 /* Compute reference result using gej + gej (var). */
1838 secp256k1_gej refj, resj;
1841 secp256k1_gej_add_var(&refj, &gej[i1], &gej[i2], secp256k1_gej_is_infinity(&gej[i1]) ? NULL : &zr);
1842 /* Check Z ratio. */
1843 if (!secp256k1_gej_is_infinity(&gej[i1]) && !secp256k1_gej_is_infinity(&refj)) {
1844 secp256k1_fe zrz; secp256k1_fe_mul(&zrz, &zr, &gej[i1].z);
1845 CHECK(secp256k1_fe_equal_var(&zrz, &refj.z));
1847 secp256k1_ge_set_gej_var(&ref, &refj);
1849 /* Test gej + ge with Z ratio result (var). */
1850 secp256k1_gej_add_ge_var(&resj, &gej[i1], &ge[i2], secp256k1_gej_is_infinity(&gej[i1]) ? NULL : &zr);
1851 ge_equals_gej(&ref, &resj);
1852 if (!secp256k1_gej_is_infinity(&gej[i1]) && !secp256k1_gej_is_infinity(&resj)) {
1853 secp256k1_fe zrz; secp256k1_fe_mul(&zrz, &zr, &gej[i1].z);
1854 CHECK(secp256k1_fe_equal_var(&zrz, &resj.z));
1857 /* Test gej + ge (var, with additional Z factor). */
1859 secp256k1_ge ge2_zfi = ge[i2]; /* the second term with x and y rescaled for z = 1/zf */
1860 secp256k1_fe_mul(&ge2_zfi.x, &ge2_zfi.x, &zfi2);
1861 secp256k1_fe_mul(&ge2_zfi.y, &ge2_zfi.y, &zfi3);
1862 random_field_element_magnitude(&ge2_zfi.x);
1863 random_field_element_magnitude(&ge2_zfi.y);
1864 secp256k1_gej_add_zinv_var(&resj, &gej[i1], &ge2_zfi, &zf);
1865 ge_equals_gej(&ref, &resj);
1868 /* Test gej + ge (const). */
1870 /* secp256k1_gej_add_ge does not support its second argument being infinity. */
1871 secp256k1_gej_add_ge(&resj, &gej[i1], &ge[i2]);
1872 ge_equals_gej(&ref, &resj);
1875 /* Test doubling (var). */
1876 if ((i1 == 0 && i2 == 0) || ((i1 + 3)/4 == (i2 + 3)/4 && ((i1 + 3)%4)/2 == ((i2 + 3)%4)/2)) {
1878 /* Normal doubling with Z ratio result. */
1879 secp256k1_gej_double_var(&resj, &gej[i1], &zr2);
1880 ge_equals_gej(&ref, &resj);
1881 /* Check Z ratio. */
1882 secp256k1_fe_mul(&zr2, &zr2, &gej[i1].z);
1883 CHECK(secp256k1_fe_equal_var(&zr2, &resj.z));
1884 /* Normal doubling. */
1885 secp256k1_gej_double_var(&resj, &gej[i2], NULL);
1886 ge_equals_gej(&ref, &resj);
1889 /* Test adding opposites. */
1890 if ((i1 == 0 && i2 == 0) || ((i1 + 3)/4 == (i2 + 3)/4 && ((i1 + 3)%4)/2 != ((i2 + 3)%4)/2)) {
1891 CHECK(secp256k1_ge_is_infinity(&ref));
1894 /* Test adding infinity. */
1896 CHECK(secp256k1_ge_is_infinity(&ge[i1]));
1897 CHECK(secp256k1_gej_is_infinity(&gej[i1]));
1898 ge_equals_gej(&ref, &gej[i2]);
1901 CHECK(secp256k1_ge_is_infinity(&ge[i2]));
1902 CHECK(secp256k1_gej_is_infinity(&gej[i2]));
1903 ge_equals_gej(&ref, &gej[i1]);
1908 /* Test adding all points together in random order equals infinity. */
1910 secp256k1_gej sum = SECP256K1_GEJ_CONST_INFINITY;
1911 secp256k1_gej *gej_shuffled = (secp256k1_gej *)malloc((4 * runs + 1) * sizeof(secp256k1_gej));
1912 for (i = 0; i < 4 * runs + 1; i++) {
1913 gej_shuffled[i] = gej[i];
1915 for (i = 0; i < 4 * runs + 1; i++) {
1916 int swap = i + secp256k1_rand_int(4 * runs + 1 - i);
1918 secp256k1_gej t = gej_shuffled[i];
1919 gej_shuffled[i] = gej_shuffled[swap];
1920 gej_shuffled[swap] = t;
1923 for (i = 0; i < 4 * runs + 1; i++) {
1924 secp256k1_gej_add_var(&sum, &sum, &gej_shuffled[i], NULL);
1926 CHECK(secp256k1_gej_is_infinity(&sum));
1930 /* Test batch gej -> ge conversion with and without known z ratios. */
1932 secp256k1_fe *zr = (secp256k1_fe *)malloc((4 * runs + 1) * sizeof(secp256k1_fe));
1933 secp256k1_ge *ge_set_table = (secp256k1_ge *)malloc((4 * runs + 1) * sizeof(secp256k1_ge));
1934 secp256k1_ge *ge_set_all = (secp256k1_ge *)malloc((4 * runs + 1) * sizeof(secp256k1_ge));
1935 for (i = 0; i < 4 * runs + 1; i++) {
1936 /* Compute gej[i + 1].z / gez[i].z (with gej[n].z taken to be 1). */
1938 secp256k1_fe_mul(&zr[i + 1], &zinv[i], &gej[i + 1].z);
1941 secp256k1_ge_set_table_gej_var(4 * runs + 1, ge_set_table, gej, zr);
1942 secp256k1_ge_set_all_gej_var(4 * runs + 1, ge_set_all, gej, &ctx->error_callback);
1943 for (i = 0; i < 4 * runs + 1; i++) {
1945 random_fe_non_zero(&s);
1946 secp256k1_gej_rescale(&gej[i], &s);
1947 ge_equals_gej(&ge_set_table[i], &gej[i]);
1948 ge_equals_gej(&ge_set_all[i], &gej[i]);
1960 void test_add_neg_y_diff_x(void) {
1961 /* The point of this test is to check that we can add two points
1962 * whose y-coordinates are negatives of each other but whose x
1963 * coordinates differ. If the x-coordinates were the same, these
1964 * points would be negatives of each other and their sum is
1965 * infinity. This is cool because it "covers up" any degeneracy
1966 * in the addition algorithm that would cause the xy coordinates
1967 * of the sum to be wrong (since infinity has no xy coordinates).
1968 * HOWEVER, if the x-coordinates are different, infinity is the
1969 * wrong answer, and such degeneracies are exposed. This is the
1970 * root of https://github.com/bitcoin-core/secp256k1/issues/257
1971 * which this test is a regression test for.
1973 * These points were generated in sage as
1974 * # secp256k1 params
1975 * F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
1976 * C = EllipticCurve ([F (0), F (7)])
1977 * G = C.lift_x(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
1978 * N = FiniteField(G.order())
1980 * # endomorphism values (lambda is 1^{1/3} in N, beta is 1^{1/3} in F)
1982 * lam = (1 - x^3).roots()[1][0]
1984 * # random "bad pair"
1985 * P = C.random_element()
1987 * print " P: %x %x" % P.xy()
1988 * print " Q: %x %x" % Q.xy()
1989 * print "P + Q: %x %x" % (P + Q).xy()
1991 secp256k1_gej aj = SECP256K1_GEJ_CONST(
1992 0x8d24cd95, 0x0a355af1, 0x3c543505, 0x44238d30,
1993 0x0643d79f, 0x05a59614, 0x2f8ec030, 0xd58977cb,
1994 0x001e337a, 0x38093dcd, 0x6c0f386d, 0x0b1293a8,
1995 0x4d72c879, 0xd7681924, 0x44e6d2f3, 0x9190117d
1997 secp256k1_gej bj = SECP256K1_GEJ_CONST(
1998 0xc7b74206, 0x1f788cd9, 0xabd0937d, 0x164a0d86,
1999 0x95f6ff75, 0xf19a4ce9, 0xd013bd7b, 0xbf92d2a7,
2000 0xffe1cc85, 0xc7f6c232, 0x93f0c792, 0xf4ed6c57,
2001 0xb28d3786, 0x2897e6db, 0xbb192d0b, 0x6e6feab2
2003 secp256k1_gej sumj = SECP256K1_GEJ_CONST(
2004 0x671a63c0, 0x3efdad4c, 0x389a7798, 0x24356027,
2005 0xb3d69010, 0x278625c3, 0x5c86d390, 0x184a8f7a,
2006 0x5f6409c2, 0x2ce01f2b, 0x511fd375, 0x25071d08,
2007 0xda651801, 0x70e95caf, 0x8f0d893c, 0xbed8fbbe
2012 secp256k1_ge_set_gej(&b, &bj);
2014 secp256k1_gej_add_var(&resj, &aj, &bj, NULL);
2015 secp256k1_ge_set_gej(&res, &resj);
2016 ge_equals_gej(&res, &sumj);
2018 secp256k1_gej_add_ge(&resj, &aj, &b);
2019 secp256k1_ge_set_gej(&res, &resj);
2020 ge_equals_gej(&res, &sumj);
2022 secp256k1_gej_add_ge_var(&resj, &aj, &b, NULL);
2023 secp256k1_ge_set_gej(&res, &resj);
2024 ge_equals_gej(&res, &sumj);
2029 for (i = 0; i < count * 32; i++) {
2032 test_add_neg_y_diff_x();
2035 void test_ec_combine(void) {
2036 secp256k1_scalar sum = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
2037 secp256k1_pubkey data[6];
2038 const secp256k1_pubkey* d[6];
2039 secp256k1_pubkey sd;
2040 secp256k1_pubkey sd2;
2044 for (i = 1; i <= 6; i++) {
2046 random_scalar_order_test(&s);
2047 secp256k1_scalar_add(&sum, &sum, &s);
2048 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &Qj, &s);
2049 secp256k1_ge_set_gej(&Q, &Qj);
2050 secp256k1_pubkey_save(&data[i - 1], &Q);
2051 d[i - 1] = &data[i - 1];
2052 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &Qj, &sum);
2053 secp256k1_ge_set_gej(&Q, &Qj);
2054 secp256k1_pubkey_save(&sd, &Q);
2055 CHECK(secp256k1_ec_pubkey_combine(ctx, &sd2, d, i) == 1);
2056 CHECK(memcmp(&sd, &sd2, sizeof(sd)) == 0);
2060 void run_ec_combine(void) {
2062 for (i = 0; i < count * 8; i++) {
2067 void test_group_decompress(const secp256k1_fe* x) {
2068 /* The input itself, normalized. */
2069 secp256k1_fe fex = *x;
2071 /* Results of set_xquad_var, set_xo_var(..., 0), set_xo_var(..., 1). */
2072 secp256k1_ge ge_quad, ge_even, ge_odd;
2073 /* Return values of the above calls. */
2074 int res_quad, res_even, res_odd;
2076 secp256k1_fe_normalize_var(&fex);
2078 res_quad = secp256k1_ge_set_xquad_var(&ge_quad, &fex);
2079 res_even = secp256k1_ge_set_xo_var(&ge_even, &fex, 0);
2080 res_odd = secp256k1_ge_set_xo_var(&ge_odd, &fex, 1);
2082 CHECK(res_quad == res_even);
2083 CHECK(res_quad == res_odd);
2086 secp256k1_fe_normalize_var(&ge_quad.x);
2087 secp256k1_fe_normalize_var(&ge_odd.x);
2088 secp256k1_fe_normalize_var(&ge_even.x);
2089 secp256k1_fe_normalize_var(&ge_quad.y);
2090 secp256k1_fe_normalize_var(&ge_odd.y);
2091 secp256k1_fe_normalize_var(&ge_even.y);
2093 /* No infinity allowed. */
2094 CHECK(!ge_quad.infinity);
2095 CHECK(!ge_even.infinity);
2096 CHECK(!ge_odd.infinity);
2098 /* Check that the x coordinates check out. */
2099 CHECK(secp256k1_fe_equal_var(&ge_quad.x, x));
2100 CHECK(secp256k1_fe_equal_var(&ge_even.x, x));
2101 CHECK(secp256k1_fe_equal_var(&ge_odd.x, x));
2103 /* Check that the Y coordinate result in ge_quad is a square. */
2104 CHECK(secp256k1_fe_sqrt_var(&tmp, &ge_quad.y));
2105 secp256k1_fe_sqr(&tmp, &tmp);
2106 CHECK(secp256k1_fe_equal_var(&tmp, &ge_quad.y));
2108 /* Check odd/even Y in ge_odd, ge_even. */
2109 CHECK(secp256k1_fe_is_odd(&ge_odd.y));
2110 CHECK(!secp256k1_fe_is_odd(&ge_even.y));
2114 void run_group_decompress(void) {
2116 for (i = 0; i < count * 4; i++) {
2118 random_fe_test(&fe);
2119 test_group_decompress(&fe);
2123 /***** ECMULT TESTS *****/
2125 void run_ecmult_chain(void) {
2126 /* random starting point A (on the curve) */
2127 secp256k1_gej a = SECP256K1_GEJ_CONST(
2128 0x8b30bbe9, 0xae2a9906, 0x96b22f67, 0x0709dff3,
2129 0x727fd8bc, 0x04d3362c, 0x6c7bf458, 0xe2846004,
2130 0xa357ae91, 0x5c4a6528, 0x1309edf2, 0x0504740f,
2131 0x0eb33439, 0x90216b4f, 0x81063cb6, 0x5f2f7e0f
2133 /* two random initial factors xn and gn */
2134 secp256k1_scalar xn = SECP256K1_SCALAR_CONST(
2135 0x84cc5452, 0xf7fde1ed, 0xb4d38a8c, 0xe9b1b84c,
2136 0xcef31f14, 0x6e569be9, 0x705d357a, 0x42985407
2138 secp256k1_scalar gn = SECP256K1_SCALAR_CONST(
2139 0xa1e58d22, 0x553dcd42, 0xb2398062, 0x5d4c57a9,
2140 0x6e9323d4, 0x2b3152e5, 0xca2c3990, 0xedc7c9de
2142 /* two small multipliers to be applied to xn and gn in every iteration: */
2143 static const secp256k1_scalar xf = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0x1337);
2144 static const secp256k1_scalar gf = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0x7113);
2145 /* accumulators with the resulting coefficients to A and G */
2146 secp256k1_scalar ae = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1);
2147 secp256k1_scalar ge = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
2153 /* the point being computed */
2155 for (i = 0; i < 200*count; i++) {
2156 /* in each iteration, compute X = xn*X + gn*G; */
2157 secp256k1_ecmult(&ctx->ecmult_ctx, &x, &x, &xn, &gn);
2158 /* also compute ae and ge: the actual accumulated factors for A and G */
2159 /* if X was (ae*A+ge*G), xn*X + gn*G results in (xn*ae*A + (xn*ge+gn)*G) */
2160 secp256k1_scalar_mul(&ae, &ae, &xn);
2161 secp256k1_scalar_mul(&ge, &ge, &xn);
2162 secp256k1_scalar_add(&ge, &ge, &gn);
2163 /* modify xn and gn */
2164 secp256k1_scalar_mul(&xn, &xn, &xf);
2165 secp256k1_scalar_mul(&gn, &gn, &gf);
2169 /* expected result after 19999 iterations */
2170 secp256k1_gej rp = SECP256K1_GEJ_CONST(
2171 0xD6E96687, 0xF9B10D09, 0x2A6F3543, 0x9D86CEBE,
2172 0xA4535D0D, 0x409F5358, 0x6440BD74, 0xB933E830,
2173 0xB95CBCA2, 0xC77DA786, 0x539BE8FD, 0x53354D2D,
2174 0x3B4F566A, 0xE6580454, 0x07ED6015, 0xEE1B2A88
2177 secp256k1_gej_neg(&rp, &rp);
2178 secp256k1_gej_add_var(&rp, &rp, &x, NULL);
2179 CHECK(secp256k1_gej_is_infinity(&rp));
2182 /* redo the computation, but directly with the resulting ae and ge coefficients: */
2183 secp256k1_ecmult(&ctx->ecmult_ctx, &x2, &a, &ae, &ge);
2184 secp256k1_gej_neg(&x2, &x2);
2185 secp256k1_gej_add_var(&x2, &x2, &x, NULL);
2186 CHECK(secp256k1_gej_is_infinity(&x2));
2189 void test_point_times_order(const secp256k1_gej *point) {
2190 /* X * (point + G) + (order-X) * (pointer + G) = 0 */
2192 secp256k1_scalar nx;
2193 secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
2194 secp256k1_scalar one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1);
2195 secp256k1_gej res1, res2;
2197 unsigned char pub[65];
2199 random_scalar_order_test(&x);
2200 secp256k1_scalar_negate(&nx, &x);
2201 secp256k1_ecmult(&ctx->ecmult_ctx, &res1, point, &x, &x); /* calc res1 = x * point + x * G; */
2202 secp256k1_ecmult(&ctx->ecmult_ctx, &res2, point, &nx, &nx); /* calc res2 = (order - x) * point + (order - x) * G; */
2203 secp256k1_gej_add_var(&res1, &res1, &res2, NULL);
2204 CHECK(secp256k1_gej_is_infinity(&res1));
2205 CHECK(secp256k1_gej_is_valid_var(&res1) == 0);
2206 secp256k1_ge_set_gej(&res3, &res1);
2207 CHECK(secp256k1_ge_is_infinity(&res3));
2208 CHECK(secp256k1_ge_is_valid_var(&res3) == 0);
2209 CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 0) == 0);
2211 CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 1) == 0);
2212 /* check zero/one edge cases */
2213 secp256k1_ecmult(&ctx->ecmult_ctx, &res1, point, &zero, &zero);
2214 secp256k1_ge_set_gej(&res3, &res1);
2215 CHECK(secp256k1_ge_is_infinity(&res3));
2216 secp256k1_ecmult(&ctx->ecmult_ctx, &res1, point, &one, &zero);
2217 secp256k1_ge_set_gej(&res3, &res1);
2218 ge_equals_gej(&res3, point);
2219 secp256k1_ecmult(&ctx->ecmult_ctx, &res1, point, &zero, &one);
2220 secp256k1_ge_set_gej(&res3, &res1);
2221 ge_equals_ge(&res3, &secp256k1_ge_const_g);
2224 void run_point_times_order(void) {
2226 secp256k1_fe x = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 2);
2227 static const secp256k1_fe xr = SECP256K1_FE_CONST(
2228 0x7603CB59, 0xB0EF6C63, 0xFE608479, 0x2A0C378C,
2229 0xDB3233A8, 0x0F8A9A09, 0xA877DEAD, 0x31B38C45
2231 for (i = 0; i < 500; i++) {
2233 if (secp256k1_ge_set_xo_var(&p, &x, 1)) {
2235 CHECK(secp256k1_ge_is_valid_var(&p));
2236 secp256k1_gej_set_ge(&j, &p);
2237 CHECK(secp256k1_gej_is_valid_var(&j));
2238 test_point_times_order(&j);
2240 secp256k1_fe_sqr(&x, &x);
2242 secp256k1_fe_normalize_var(&x);
2243 CHECK(secp256k1_fe_equal_var(&x, &xr));
2246 void ecmult_const_random_mult(void) {
2247 /* random starting point A (on the curve) */
2248 secp256k1_ge a = SECP256K1_GE_CONST(
2249 0x6d986544, 0x57ff52b8, 0xcf1b8126, 0x5b802a5b,
2250 0xa97f9263, 0xb1e88044, 0x93351325, 0x91bc450a,
2251 0x535c59f7, 0x325e5d2b, 0xc391fbe8, 0x3c12787c,
2252 0x337e4a98, 0xe82a9011, 0x0123ba37, 0xdd769c7d
2254 /* random initial factor xn */
2255 secp256k1_scalar xn = SECP256K1_SCALAR_CONST(
2256 0x649d4f77, 0xc4242df7, 0x7f2079c9, 0x14530327,
2257 0xa31b876a, 0xd2d8ce2a, 0x2236d5c6, 0xd7b2029b
2259 /* expected xn * A (from sage) */
2260 secp256k1_ge expected_b = SECP256K1_GE_CONST(
2261 0x23773684, 0x4d209dc7, 0x098a786f, 0x20d06fcd,
2262 0x070a38bf, 0xc11ac651, 0x03004319, 0x1e2a8786,
2263 0xed8c3b8e, 0xc06dd57b, 0xd06ea66e, 0x45492b0f,
2264 0xb84e4e1b, 0xfb77e21f, 0x96baae2a, 0x63dec956
2267 secp256k1_ecmult_const(&b, &a, &xn);
2269 CHECK(secp256k1_ge_is_valid_var(&a));
2270 ge_equals_gej(&expected_b, &b);
2273 void ecmult_const_commutativity(void) {
2280 random_scalar_order_test(&a);
2281 random_scalar_order_test(&b);
2283 secp256k1_ecmult_const(&res1, &secp256k1_ge_const_g, &a);
2284 secp256k1_ecmult_const(&res2, &secp256k1_ge_const_g, &b);
2285 secp256k1_ge_set_gej(&mid1, &res1);
2286 secp256k1_ge_set_gej(&mid2, &res2);
2287 secp256k1_ecmult_const(&res1, &mid1, &b);
2288 secp256k1_ecmult_const(&res2, &mid2, &a);
2289 secp256k1_ge_set_gej(&mid1, &res1);
2290 secp256k1_ge_set_gej(&mid2, &res2);
2291 ge_equals_ge(&mid1, &mid2);
2294 void ecmult_const_mult_zero_one(void) {
2295 secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
2296 secp256k1_scalar one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1);
2297 secp256k1_scalar negone;
2301 secp256k1_scalar_negate(&negone, &one);
2303 random_group_element_test(&point);
2304 secp256k1_ecmult_const(&res1, &point, &zero);
2305 secp256k1_ge_set_gej(&res2, &res1);
2306 CHECK(secp256k1_ge_is_infinity(&res2));
2307 secp256k1_ecmult_const(&res1, &point, &one);
2308 secp256k1_ge_set_gej(&res2, &res1);
2309 ge_equals_ge(&res2, &point);
2310 secp256k1_ecmult_const(&res1, &point, &negone);
2311 secp256k1_gej_neg(&res1, &res1);
2312 secp256k1_ge_set_gej(&res2, &res1);
2313 ge_equals_ge(&res2, &point);
2316 void ecmult_const_chain_multiply(void) {
2317 /* Check known result (randomly generated test problem from sage) */
2318 const secp256k1_scalar scalar = SECP256K1_SCALAR_CONST(
2319 0x4968d524, 0x2abf9b7a, 0x466abbcf, 0x34b11b6d,
2320 0xcd83d307, 0x827bed62, 0x05fad0ce, 0x18fae63b
2322 const secp256k1_gej expected_point = SECP256K1_GEJ_CONST(
2323 0x5494c15d, 0x32099706, 0xc2395f94, 0x348745fd,
2324 0x757ce30e, 0x4e8c90fb, 0xa2bad184, 0xf883c69f,
2325 0x5d195d20, 0xe191bf7f, 0x1be3e55f, 0x56a80196,
2326 0x6071ad01, 0xf1462f66, 0xc997fa94, 0xdb858435
2328 secp256k1_gej point;
2332 secp256k1_gej_set_ge(&point, &secp256k1_ge_const_g);
2333 for (i = 0; i < 100; ++i) {
2335 secp256k1_ge_set_gej(&tmp, &point);
2336 secp256k1_ecmult_const(&point, &tmp, &scalar);
2338 secp256k1_ge_set_gej(&res, &point);
2339 ge_equals_gej(&res, &expected_point);
2342 void run_ecmult_const_tests(void) {
2343 ecmult_const_mult_zero_one();
2344 ecmult_const_random_mult();
2345 ecmult_const_commutativity();
2346 ecmult_const_chain_multiply();
2349 void test_wnaf(const secp256k1_scalar *number, int w) {
2350 secp256k1_scalar x, two, t;
2355 secp256k1_scalar_set_int(&x, 0);
2356 secp256k1_scalar_set_int(&two, 2);
2357 bits = secp256k1_ecmult_wnaf(wnaf, 256, number, w);
2359 for (i = bits-1; i >= 0; i--) {
2361 secp256k1_scalar_mul(&x, &x, &two);
2363 CHECK(zeroes == -1 || zeroes >= w-1); /* check that distance between non-zero elements is at least w-1 */
2365 CHECK((v & 1) == 1); /* check non-zero elements are odd */
2366 CHECK(v <= (1 << (w-1)) - 1); /* check range below */
2367 CHECK(v >= -(1 << (w-1)) - 1); /* check range above */
2369 CHECK(zeroes != -1); /* check that no unnecessary zero padding exists */
2373 secp256k1_scalar_set_int(&t, v);
2375 secp256k1_scalar_set_int(&t, -v);
2376 secp256k1_scalar_negate(&t, &t);
2378 secp256k1_scalar_add(&x, &x, &t);
2380 CHECK(secp256k1_scalar_eq(&x, number)); /* check that wnaf represents number */
2383 void test_constant_wnaf_negate(const secp256k1_scalar *number) {
2384 secp256k1_scalar neg1 = *number;
2385 secp256k1_scalar neg2 = *number;
2389 if (!secp256k1_scalar_get_bits(&neg1, 0, 1)) {
2390 secp256k1_scalar_negate(&neg1, &neg1);
2393 sign2 = secp256k1_scalar_cond_negate(&neg2, secp256k1_scalar_is_even(&neg2));
2394 CHECK(sign1 == sign2);
2395 CHECK(secp256k1_scalar_eq(&neg1, &neg2));
2398 void test_constant_wnaf(const secp256k1_scalar *number, int w) {
2399 secp256k1_scalar x, shift;
2400 int wnaf[256] = {0};
2402 #ifdef USE_ENDOMORPHISM
2405 secp256k1_scalar num = *number;
2407 secp256k1_scalar_set_int(&x, 0);
2408 secp256k1_scalar_set_int(&shift, 1 << w);
2409 /* With USE_ENDOMORPHISM on we only consider 128-bit numbers */
2410 #ifdef USE_ENDOMORPHISM
2411 for (i = 0; i < 16; ++i) {
2412 secp256k1_scalar_shr_int(&num, 8);
2414 skew = secp256k1_wnaf_const(wnaf, num, w);
2416 secp256k1_wnaf_const(wnaf, num, w);
2419 for (i = WNAF_SIZE(w); i >= 0; --i) {
2422 CHECK(v != 0); /* check nonzero */
2423 CHECK(v & 1); /* check parity */
2424 CHECK(v > -(1 << w)); /* check range above */
2425 CHECK(v < (1 << w)); /* check range below */
2427 secp256k1_scalar_mul(&x, &x, &shift);
2429 secp256k1_scalar_set_int(&t, v);
2431 secp256k1_scalar_set_int(&t, -v);
2432 secp256k1_scalar_negate(&t, &t);
2434 secp256k1_scalar_add(&x, &x, &t);
2436 #ifdef USE_ENDOMORPHISM
2437 /* Skew num because when encoding 128-bit numbers as odd we use an offset */
2438 secp256k1_scalar_cadd_bit(&num, skew == 2, 1);
2440 CHECK(secp256k1_scalar_eq(&x, &num));
2443 void run_wnaf(void) {
2445 secp256k1_scalar n = {{0}};
2447 /* Sanity check: 1 and 2 are the smallest odd and even numbers and should
2448 * have easier-to-diagnose failure modes */
2450 test_constant_wnaf(&n, 4);
2452 test_constant_wnaf(&n, 4);
2454 for (i = 0; i < count; i++) {
2455 random_scalar_order(&n);
2456 test_wnaf(&n, 4+(i%10));
2457 test_constant_wnaf_negate(&n);
2458 test_constant_wnaf(&n, 4 + (i % 10));
2460 secp256k1_scalar_set_int(&n, 0);
2461 CHECK(secp256k1_scalar_cond_negate(&n, 1) == -1);
2462 CHECK(secp256k1_scalar_is_zero(&n));
2463 CHECK(secp256k1_scalar_cond_negate(&n, 0) == 1);
2464 CHECK(secp256k1_scalar_is_zero(&n));
2467 void test_ecmult_constants(void) {
2468 /* Test ecmult_gen() for [0..36) and [order-36..0). */
2474 secp256k1_ge_neg(&ng, &secp256k1_ge_const_g);
2475 for (i = 0; i < 36; i++ ) {
2476 secp256k1_scalar_set_int(&x, i);
2477 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &r, &x);
2478 for (j = 0; j < i; j++) {
2480 ge_equals_gej(&secp256k1_ge_const_g, &r);
2482 secp256k1_gej_add_ge(&r, &r, &ng);
2484 CHECK(secp256k1_gej_is_infinity(&r));
2486 for (i = 1; i <= 36; i++ ) {
2487 secp256k1_scalar_set_int(&x, i);
2488 secp256k1_scalar_negate(&x, &x);
2489 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &r, &x);
2490 for (j = 0; j < i; j++) {
2492 ge_equals_gej(&ng, &r);
2494 secp256k1_gej_add_ge(&r, &r, &secp256k1_ge_const_g);
2496 CHECK(secp256k1_gej_is_infinity(&r));
2500 void run_ecmult_constants(void) {
2501 test_ecmult_constants();
2504 void test_ecmult_gen_blind(void) {
2505 /* Test ecmult_gen() blinding and confirm that the blinding changes, the affine points match, and the z's don't match. */
2506 secp256k1_scalar key;
2508 unsigned char seed32[32];
2510 secp256k1_gej pgej2;
2513 random_scalar_order_test(&key);
2514 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pgej, &key);
2515 secp256k1_rand256(seed32);
2516 b = ctx->ecmult_gen_ctx.blind;
2517 i = ctx->ecmult_gen_ctx.initial;
2518 secp256k1_ecmult_gen_blind(&ctx->ecmult_gen_ctx, seed32);
2519 CHECK(!secp256k1_scalar_eq(&b, &ctx->ecmult_gen_ctx.blind));
2520 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pgej2, &key);
2521 CHECK(!gej_xyz_equals_gej(&pgej, &pgej2));
2522 CHECK(!gej_xyz_equals_gej(&i, &ctx->ecmult_gen_ctx.initial));
2523 secp256k1_ge_set_gej(&pge, &pgej);
2524 ge_equals_gej(&pge, &pgej2);
2527 void test_ecmult_gen_blind_reset(void) {
2528 /* Test ecmult_gen() blinding reset and confirm that the blinding is consistent. */
2530 secp256k1_gej initial;
2531 secp256k1_ecmult_gen_blind(&ctx->ecmult_gen_ctx, 0);
2532 b = ctx->ecmult_gen_ctx.blind;
2533 initial = ctx->ecmult_gen_ctx.initial;
2534 secp256k1_ecmult_gen_blind(&ctx->ecmult_gen_ctx, 0);
2535 CHECK(secp256k1_scalar_eq(&b, &ctx->ecmult_gen_ctx.blind));
2536 CHECK(gej_xyz_equals_gej(&initial, &ctx->ecmult_gen_ctx.initial));
2539 void run_ecmult_gen_blind(void) {
2541 test_ecmult_gen_blind_reset();
2542 for (i = 0; i < 10; i++) {
2543 test_ecmult_gen_blind();
2547 #ifdef USE_ENDOMORPHISM
2548 /***** ENDOMORPHISH TESTS *****/
2549 void test_scalar_split(void) {
2550 secp256k1_scalar full;
2551 secp256k1_scalar s1, slam;
2552 const unsigned char zero[32] = {0};
2553 unsigned char tmp[32];
2555 random_scalar_order_test(&full);
2556 secp256k1_scalar_split_lambda(&s1, &slam, &full);
2558 /* check that both are <= 128 bits in size */
2559 if (secp256k1_scalar_is_high(&s1)) {
2560 secp256k1_scalar_negate(&s1, &s1);
2562 if (secp256k1_scalar_is_high(&slam)) {
2563 secp256k1_scalar_negate(&slam, &slam);
2566 secp256k1_scalar_get_b32(tmp, &s1);
2567 CHECK(memcmp(zero, tmp, 16) == 0);
2568 secp256k1_scalar_get_b32(tmp, &slam);
2569 CHECK(memcmp(zero, tmp, 16) == 0);
2572 void run_endomorphism_tests(void) {
2573 test_scalar_split();
2577 void ec_pubkey_parse_pointtest(const unsigned char *input, int xvalid, int yvalid) {
2578 unsigned char pubkeyc[65];
2579 secp256k1_pubkey pubkey;
2584 secp256k1_context_set_illegal_callback(ctx, counting_illegal_callback_fn, &ecount);
2585 for (pubkeyclen = 3; pubkeyclen <= 65; pubkeyclen++) {
2586 /* Smaller sizes are tested exhaustively elsewhere. */
2588 memcpy(&pubkeyc[1], input, 64);
2589 VG_UNDEF(&pubkeyc[pubkeyclen], 65 - pubkeyclen);
2590 for (i = 0; i < 256; i++) {
2591 /* Try all type bytes. */
2596 /* What sign does this point have? */
2597 ysign = (input[63] & 1) + 2;
2598 /* For the current type (i) do we expect parsing to work? Handled all of compressed/uncompressed/hybrid. */
2599 xpass = xvalid && (pubkeyclen == 33) && ((i & 254) == 2);
2600 /* Do we expect a parse and re-serialize as uncompressed to give a matching y? */
2601 ypass = xvalid && yvalid && ((i & 4) == ((pubkeyclen == 65) << 2)) &&
2602 ((i == 4) || ((i & 251) == ysign)) && ((pubkeyclen == 33) || (pubkeyclen == 65));
2603 if (xpass || ypass) {
2604 /* These cases must parse. */
2605 unsigned char pubkeyo[65];
2607 memset(&pubkey, 0, sizeof(pubkey));
2608 VG_UNDEF(&pubkey, sizeof(pubkey));
2610 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, pubkeyclen) == 1);
2611 VG_CHECK(&pubkey, sizeof(pubkey));
2613 VG_UNDEF(pubkeyo, 65);
2614 CHECK(secp256k1_ec_pubkey_serialize(ctx, pubkeyo, &outl, &pubkey, SECP256K1_EC_COMPRESSED) == 1);
2615 VG_CHECK(pubkeyo, outl);
2617 CHECK(memcmp(&pubkeyo[1], &pubkeyc[1], 32) == 0);
2618 CHECK((pubkeyclen != 33) || (pubkeyo[0] == pubkeyc[0]));
2620 /* This test isn't always done because we decode with alternative signs, so the y won't match. */
2621 CHECK(pubkeyo[0] == ysign);
2622 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 1);
2623 memset(&pubkey, 0, sizeof(pubkey));
2624 VG_UNDEF(&pubkey, sizeof(pubkey));
2625 secp256k1_pubkey_save(&pubkey, &ge);
2626 VG_CHECK(&pubkey, sizeof(pubkey));
2628 VG_UNDEF(pubkeyo, 65);
2629 CHECK(secp256k1_ec_pubkey_serialize(ctx, pubkeyo, &outl, &pubkey, SECP256K1_EC_UNCOMPRESSED) == 1);
2630 VG_CHECK(pubkeyo, outl);
2632 CHECK(pubkeyo[0] == 4);
2633 CHECK(memcmp(&pubkeyo[1], input, 64) == 0);
2637 /* These cases must fail to parse. */
2638 memset(&pubkey, 0xfe, sizeof(pubkey));
2640 VG_UNDEF(&pubkey, sizeof(pubkey));
2641 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, pubkeyclen) == 0);
2642 VG_CHECK(&pubkey, sizeof(pubkey));
2644 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2649 secp256k1_context_set_illegal_callback(ctx, NULL, NULL);
2652 void run_ec_pubkey_parse_test(void) {
2653 #define SECP256K1_EC_PARSE_TEST_NVALID (12)
2654 const unsigned char valid[SECP256K1_EC_PARSE_TEST_NVALID][64] = {
2656 /* Point with leading and trailing zeros in x and y serialization. */
2657 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x42, 0x52,
2658 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2659 0x00, 0x00, 0x64, 0xef, 0xa1, 0x7b, 0x77, 0x61, 0xe1, 0xe4, 0x27, 0x06, 0x98, 0x9f, 0xb4, 0x83,
2660 0xb8, 0xd2, 0xd4, 0x9b, 0xf7, 0x8f, 0xae, 0x98, 0x03, 0xf0, 0x99, 0xb8, 0x34, 0xed, 0xeb, 0x00
2663 /* Point with x equal to a 3rd root of unity.*/
2664 0x7a, 0xe9, 0x6a, 0x2b, 0x65, 0x7c, 0x07, 0x10, 0x6e, 0x64, 0x47, 0x9e, 0xac, 0x34, 0x34, 0xe9,
2665 0x9c, 0xf0, 0x49, 0x75, 0x12, 0xf5, 0x89, 0x95, 0xc1, 0x39, 0x6c, 0x28, 0x71, 0x95, 0x01, 0xee,
2666 0x42, 0x18, 0xf2, 0x0a, 0xe6, 0xc6, 0x46, 0xb3, 0x63, 0xdb, 0x68, 0x60, 0x58, 0x22, 0xfb, 0x14,
2667 0x26, 0x4c, 0xa8, 0xd2, 0x58, 0x7f, 0xdd, 0x6f, 0xbc, 0x75, 0x0d, 0x58, 0x7e, 0x76, 0xa7, 0xee,
2670 /* Point with largest x. (1/2) */
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, 0x2c,
2673 0x0e, 0x99, 0x4b, 0x14, 0xea, 0x72, 0xf8, 0xc3, 0xeb, 0x95, 0xc7, 0x1e, 0xf6, 0x92, 0x57, 0x5e,
2674 0x77, 0x50, 0x58, 0x33, 0x2d, 0x7e, 0x52, 0xd0, 0x99, 0x5c, 0xf8, 0x03, 0x88, 0x71, 0xb6, 0x7d,
2677 /* Point with largest x. (2/2) */
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, 0x2c,
2680 0xf1, 0x66, 0xb4, 0xeb, 0x15, 0x8d, 0x07, 0x3c, 0x14, 0x6a, 0x38, 0xe1, 0x09, 0x6d, 0xa8, 0xa1,
2681 0x88, 0xaf, 0xa7, 0xcc, 0xd2, 0x81, 0xad, 0x2f, 0x66, 0xa3, 0x07, 0xfb, 0x77, 0x8e, 0x45, 0xb2,
2684 /* Point with smallest x. (1/2) */
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, 0x01,
2687 0x42, 0x18, 0xf2, 0x0a, 0xe6, 0xc6, 0x46, 0xb3, 0x63, 0xdb, 0x68, 0x60, 0x58, 0x22, 0xfb, 0x14,
2688 0x26, 0x4c, 0xa8, 0xd2, 0x58, 0x7f, 0xdd, 0x6f, 0xbc, 0x75, 0x0d, 0x58, 0x7e, 0x76, 0xa7, 0xee,
2691 /* Point with smallest x. (2/2) */
2692 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2693 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2694 0xbd, 0xe7, 0x0d, 0xf5, 0x19, 0x39, 0xb9, 0x4c, 0x9c, 0x24, 0x97, 0x9f, 0xa7, 0xdd, 0x04, 0xeb,
2695 0xd9, 0xb3, 0x57, 0x2d, 0xa7, 0x80, 0x22, 0x90, 0x43, 0x8a, 0xf2, 0xa6, 0x81, 0x89, 0x54, 0x41,
2698 /* Point with largest y. (1/3) */
2699 0x1f, 0xe1, 0xe5, 0xef, 0x3f, 0xce, 0xb5, 0xc1, 0x35, 0xab, 0x77, 0x41, 0x33, 0x3c, 0xe5, 0xa6,
2700 0xe8, 0x0d, 0x68, 0x16, 0x76, 0x53, 0xf6, 0xb2, 0xb2, 0x4b, 0xcb, 0xcf, 0xaa, 0xaf, 0xf5, 0x07,
2701 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2702 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2705 /* Point with largest y. (2/3) */
2706 0xcb, 0xb0, 0xde, 0xab, 0x12, 0x57, 0x54, 0xf1, 0xfd, 0xb2, 0x03, 0x8b, 0x04, 0x34, 0xed, 0x9c,
2707 0xb3, 0xfb, 0x53, 0xab, 0x73, 0x53, 0x91, 0x12, 0x99, 0x94, 0xa5, 0x35, 0xd9, 0x25, 0xf6, 0x73,
2708 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2709 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2712 /* Point with largest y. (3/3) */
2713 0x14, 0x6d, 0x3b, 0x65, 0xad, 0xd9, 0xf5, 0x4c, 0xcc, 0xa2, 0x85, 0x33, 0xc8, 0x8e, 0x2c, 0xbc,
2714 0x63, 0xf7, 0x44, 0x3e, 0x16, 0x58, 0x78, 0x3a, 0xb4, 0x1f, 0x8e, 0xf9, 0x7c, 0x2a, 0x10, 0xb5,
2715 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2716 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2719 /* Point with smallest y. (1/3) */
2720 0x1f, 0xe1, 0xe5, 0xef, 0x3f, 0xce, 0xb5, 0xc1, 0x35, 0xab, 0x77, 0x41, 0x33, 0x3c, 0xe5, 0xa6,
2721 0xe8, 0x0d, 0x68, 0x16, 0x76, 0x53, 0xf6, 0xb2, 0xb2, 0x4b, 0xcb, 0xcf, 0xaa, 0xaf, 0xf5, 0x07,
2722 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2723 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2726 /* Point with smallest y. (2/3) */
2727 0xcb, 0xb0, 0xde, 0xab, 0x12, 0x57, 0x54, 0xf1, 0xfd, 0xb2, 0x03, 0x8b, 0x04, 0x34, 0xed, 0x9c,
2728 0xb3, 0xfb, 0x53, 0xab, 0x73, 0x53, 0x91, 0x12, 0x99, 0x94, 0xa5, 0x35, 0xd9, 0x25, 0xf6, 0x73,
2729 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2730 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2733 /* Point with smallest y. (3/3) */
2734 0x14, 0x6d, 0x3b, 0x65, 0xad, 0xd9, 0xf5, 0x4c, 0xcc, 0xa2, 0x85, 0x33, 0xc8, 0x8e, 0x2c, 0xbc,
2735 0x63, 0xf7, 0x44, 0x3e, 0x16, 0x58, 0x78, 0x3a, 0xb4, 0x1f, 0x8e, 0xf9, 0x7c, 0x2a, 0x10, 0xb5,
2736 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2737 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01
2740 #define SECP256K1_EC_PARSE_TEST_NXVALID (4)
2741 const unsigned char onlyxvalid[SECP256K1_EC_PARSE_TEST_NXVALID][64] = {
2743 /* Valid if y overflow ignored (y = 1 mod p). (1/3) */
2744 0x1f, 0xe1, 0xe5, 0xef, 0x3f, 0xce, 0xb5, 0xc1, 0x35, 0xab, 0x77, 0x41, 0x33, 0x3c, 0xe5, 0xa6,
2745 0xe8, 0x0d, 0x68, 0x16, 0x76, 0x53, 0xf6, 0xb2, 0xb2, 0x4b, 0xcb, 0xcf, 0xaa, 0xaf, 0xf5, 0x07,
2746 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2747 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2750 /* Valid if y overflow ignored (y = 1 mod p). (2/3) */
2751 0xcb, 0xb0, 0xde, 0xab, 0x12, 0x57, 0x54, 0xf1, 0xfd, 0xb2, 0x03, 0x8b, 0x04, 0x34, 0xed, 0x9c,
2752 0xb3, 0xfb, 0x53, 0xab, 0x73, 0x53, 0x91, 0x12, 0x99, 0x94, 0xa5, 0x35, 0xd9, 0x25, 0xf6, 0x73,
2753 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2754 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2757 /* Valid if y overflow ignored (y = 1 mod p). (3/3)*/
2758 0x14, 0x6d, 0x3b, 0x65, 0xad, 0xd9, 0xf5, 0x4c, 0xcc, 0xa2, 0x85, 0x33, 0xc8, 0x8e, 0x2c, 0xbc,
2759 0x63, 0xf7, 0x44, 0x3e, 0x16, 0x58, 0x78, 0x3a, 0xb4, 0x1f, 0x8e, 0xf9, 0x7c, 0x2a, 0x10, 0xb5,
2760 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2761 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2764 /* x on curve, y is from y^2 = x^3 + 8. */
2765 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2766 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2767 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2768 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03
2771 #define SECP256K1_EC_PARSE_TEST_NINVALID (7)
2772 const unsigned char invalid[SECP256K1_EC_PARSE_TEST_NINVALID][64] = {
2774 /* x is third root of -8, y is -1 * (x^3+7); also on the curve for y^2 = x^3 + 9. */
2775 0x0a, 0x2d, 0x2b, 0xa9, 0x35, 0x07, 0xf1, 0xdf, 0x23, 0x37, 0x70, 0xc2, 0xa7, 0x97, 0x96, 0x2c,
2776 0xc6, 0x1f, 0x6d, 0x15, 0xda, 0x14, 0xec, 0xd4, 0x7d, 0x8d, 0x27, 0xae, 0x1c, 0xd5, 0xf8, 0x53,
2777 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2778 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2781 /* Valid if x overflow ignored (x = 1 mod p). */
2782 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2783 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2784 0x42, 0x18, 0xf2, 0x0a, 0xe6, 0xc6, 0x46, 0xb3, 0x63, 0xdb, 0x68, 0x60, 0x58, 0x22, 0xfb, 0x14,
2785 0x26, 0x4c, 0xa8, 0xd2, 0x58, 0x7f, 0xdd, 0x6f, 0xbc, 0x75, 0x0d, 0x58, 0x7e, 0x76, 0xa7, 0xee,
2788 /* Valid if x overflow ignored (x = 1 mod p). */
2789 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2790 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2791 0xbd, 0xe7, 0x0d, 0xf5, 0x19, 0x39, 0xb9, 0x4c, 0x9c, 0x24, 0x97, 0x9f, 0xa7, 0xdd, 0x04, 0xeb,
2792 0xd9, 0xb3, 0x57, 0x2d, 0xa7, 0x80, 0x22, 0x90, 0x43, 0x8a, 0xf2, 0xa6, 0x81, 0x89, 0x54, 0x41,
2795 /* x is -1, y is the result of the sqrt ladder; also on the curve for y^2 = x^3 - 5. */
2796 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2797 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2798 0xf4, 0x84, 0x14, 0x5c, 0xb0, 0x14, 0x9b, 0x82, 0x5d, 0xff, 0x41, 0x2f, 0xa0, 0x52, 0xa8, 0x3f,
2799 0xcb, 0x72, 0xdb, 0x61, 0xd5, 0x6f, 0x37, 0x70, 0xce, 0x06, 0x6b, 0x73, 0x49, 0xa2, 0xaa, 0x28,
2802 /* x is -1, y is the result of the sqrt ladder; also on the curve for y^2 = x^3 - 5. */
2803 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2804 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2805 0x0b, 0x7b, 0xeb, 0xa3, 0x4f, 0xeb, 0x64, 0x7d, 0xa2, 0x00, 0xbe, 0xd0, 0x5f, 0xad, 0x57, 0xc0,
2806 0x34, 0x8d, 0x24, 0x9e, 0x2a, 0x90, 0xc8, 0x8f, 0x31, 0xf9, 0x94, 0x8b, 0xb6, 0x5d, 0x52, 0x07,
2809 /* x is zero, y is the result of the sqrt ladder; also on the curve for y^2 = x^3 - 7. */
2810 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2811 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2812 0x8f, 0x53, 0x7e, 0xef, 0xdf, 0xc1, 0x60, 0x6a, 0x07, 0x27, 0xcd, 0x69, 0xb4, 0xa7, 0x33, 0x3d,
2813 0x38, 0xed, 0x44, 0xe3, 0x93, 0x2a, 0x71, 0x79, 0xee, 0xcb, 0x4b, 0x6f, 0xba, 0x93, 0x60, 0xdc,
2816 /* x is zero, y is the result of the sqrt ladder; also on the curve for y^2 = x^3 - 7. */
2817 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2818 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2819 0x70, 0xac, 0x81, 0x10, 0x20, 0x3e, 0x9f, 0x95, 0xf8, 0xd8, 0x32, 0x96, 0x4b, 0x58, 0xcc, 0xc2,
2820 0xc7, 0x12, 0xbb, 0x1c, 0x6c, 0xd5, 0x8e, 0x86, 0x11, 0x34, 0xb4, 0x8f, 0x45, 0x6c, 0x9b, 0x53
2823 const unsigned char pubkeyc[66] = {
2824 /* Serialization of G. */
2825 0x04, 0x79, 0xBE, 0x66, 0x7E, 0xF9, 0xDC, 0xBB, 0xAC, 0x55, 0xA0, 0x62, 0x95, 0xCE, 0x87, 0x0B,
2826 0x07, 0x02, 0x9B, 0xFC, 0xDB, 0x2D, 0xCE, 0x28, 0xD9, 0x59, 0xF2, 0x81, 0x5B, 0x16, 0xF8, 0x17,
2827 0x98, 0x48, 0x3A, 0xDA, 0x77, 0x26, 0xA3, 0xC4, 0x65, 0x5D, 0xA4, 0xFB, 0xFC, 0x0E, 0x11, 0x08,
2828 0xA8, 0xFD, 0x17, 0xB4, 0x48, 0xA6, 0x85, 0x54, 0x19, 0x9C, 0x47, 0xD0, 0x8F, 0xFB, 0x10, 0xD4,
2831 unsigned char sout[65];
2832 unsigned char shortkey[2];
2834 secp256k1_pubkey pubkey;
2840 /* Nothing should be reading this far into pubkeyc. */
2841 VG_UNDEF(&pubkeyc[65], 1);
2842 secp256k1_context_set_illegal_callback(ctx, counting_illegal_callback_fn, &ecount);
2843 /* Zero length claimed, fail, zeroize, no illegal arg error. */
2844 memset(&pubkey, 0xfe, sizeof(pubkey));
2846 VG_UNDEF(shortkey, 2);
2847 VG_UNDEF(&pubkey, sizeof(pubkey));
2848 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, shortkey, 0) == 0);
2849 VG_CHECK(&pubkey, sizeof(pubkey));
2851 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2853 /* Length one claimed, fail, zeroize, no illegal arg error. */
2854 for (i = 0; i < 256 ; i++) {
2855 memset(&pubkey, 0xfe, sizeof(pubkey));
2858 VG_UNDEF(&shortkey[1], 1);
2859 VG_UNDEF(&pubkey, sizeof(pubkey));
2860 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, shortkey, 1) == 0);
2861 VG_CHECK(&pubkey, sizeof(pubkey));
2863 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2866 /* Length two claimed, fail, zeroize, no illegal arg error. */
2867 for (i = 0; i < 65536 ; i++) {
2868 memset(&pubkey, 0xfe, sizeof(pubkey));
2870 shortkey[0] = i & 255;
2871 shortkey[1] = i >> 8;
2872 VG_UNDEF(&pubkey, sizeof(pubkey));
2873 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, shortkey, 2) == 0);
2874 VG_CHECK(&pubkey, sizeof(pubkey));
2876 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2879 memset(&pubkey, 0xfe, sizeof(pubkey));
2881 VG_UNDEF(&pubkey, sizeof(pubkey));
2882 /* 33 bytes claimed on otherwise valid input starting with 0x04, fail, zeroize output, no illegal arg error. */
2883 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, 33) == 0);
2884 VG_CHECK(&pubkey, sizeof(pubkey));
2886 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2888 /* NULL pubkey, illegal arg error. Pubkey isn't rewritten before this step, since it's NULL into the parser. */
2889 CHECK(secp256k1_ec_pubkey_parse(ctx, NULL, pubkeyc, 65) == 0);
2891 /* NULL input string. Illegal arg and zeroize output. */
2892 memset(&pubkey, 0xfe, sizeof(pubkey));
2894 VG_UNDEF(&pubkey, sizeof(pubkey));
2895 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, NULL, 65) == 0);
2896 VG_CHECK(&pubkey, sizeof(pubkey));
2898 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2900 /* 64 bytes claimed on input starting with 0x04, fail, zeroize output, no illegal arg error. */
2901 memset(&pubkey, 0xfe, sizeof(pubkey));
2903 VG_UNDEF(&pubkey, sizeof(pubkey));
2904 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, 64) == 0);
2905 VG_CHECK(&pubkey, sizeof(pubkey));
2907 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2909 /* 66 bytes claimed, fail, zeroize output, no illegal arg error. */
2910 memset(&pubkey, 0xfe, sizeof(pubkey));
2912 VG_UNDEF(&pubkey, sizeof(pubkey));
2913 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, 66) == 0);
2914 VG_CHECK(&pubkey, sizeof(pubkey));
2916 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2919 memset(&pubkey, 0, sizeof(pubkey));
2921 VG_UNDEF(&pubkey, sizeof(pubkey));
2922 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, 65) == 1);
2923 VG_CHECK(&pubkey, sizeof(pubkey));
2925 VG_UNDEF(&ge, sizeof(ge));
2926 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 1);
2927 VG_CHECK(&ge.x, sizeof(ge.x));
2928 VG_CHECK(&ge.y, sizeof(ge.y));
2929 VG_CHECK(&ge.infinity, sizeof(ge.infinity));
2930 ge_equals_ge(&secp256k1_ge_const_g, &ge);
2932 /* secp256k1_ec_pubkey_serialize illegal args. */
2935 CHECK(secp256k1_ec_pubkey_serialize(ctx, NULL, &len, &pubkey, SECP256K1_EC_UNCOMPRESSED) == 0);
2938 CHECK(secp256k1_ec_pubkey_serialize(ctx, sout, NULL, &pubkey, SECP256K1_EC_UNCOMPRESSED) == 0);
2942 CHECK(secp256k1_ec_pubkey_serialize(ctx, sout, &len, NULL, SECP256K1_EC_UNCOMPRESSED) == 0);
2947 CHECK(secp256k1_ec_pubkey_serialize(ctx, sout, &len, &pubkey, ~0) == 0);
2952 CHECK(secp256k1_ec_pubkey_serialize(ctx, sout, &len, &pubkey, SECP256K1_EC_UNCOMPRESSED) == 1);
2956 /* Multiple illegal args. Should still set arg error only once. */
2959 CHECK(secp256k1_ec_pubkey_parse(ctx, NULL, NULL, 65) == 0);
2961 /* Does the illegal arg callback actually change the behavior? */
2962 secp256k1_context_set_illegal_callback(ctx, uncounting_illegal_callback_fn, &ecount2);
2963 CHECK(secp256k1_ec_pubkey_parse(ctx, NULL, NULL, 65) == 0);
2965 CHECK(ecount2 == 10);
2966 secp256k1_context_set_illegal_callback(ctx, NULL, NULL);
2967 /* Try a bunch of prefabbed points with all possible encodings. */
2968 for (i = 0; i < SECP256K1_EC_PARSE_TEST_NVALID; i++) {
2969 ec_pubkey_parse_pointtest(valid[i], 1, 1);
2971 for (i = 0; i < SECP256K1_EC_PARSE_TEST_NXVALID; i++) {
2972 ec_pubkey_parse_pointtest(onlyxvalid[i], 1, 0);
2974 for (i = 0; i < SECP256K1_EC_PARSE_TEST_NINVALID; i++) {
2975 ec_pubkey_parse_pointtest(invalid[i], 0, 0);
2979 void run_eckey_edge_case_test(void) {
2980 const unsigned char orderc[32] = {
2981 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2982 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
2983 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
2984 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41
2986 const unsigned char zeros[sizeof(secp256k1_pubkey)] = {0x00};
2987 unsigned char ctmp[33];
2988 unsigned char ctmp2[33];
2989 secp256k1_pubkey pubkey;
2990 secp256k1_pubkey pubkey2;
2991 secp256k1_pubkey pubkey_one;
2992 secp256k1_pubkey pubkey_negone;
2993 const secp256k1_pubkey *pubkeys[3];
2996 /* Group order is too large, reject. */
2997 CHECK(secp256k1_ec_seckey_verify(ctx, orderc) == 0);
2998 VG_UNDEF(&pubkey, sizeof(pubkey));
2999 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, orderc) == 0);
3000 VG_CHECK(&pubkey, sizeof(pubkey));
3001 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
3002 /* Maximum value is too large, reject. */
3003 memset(ctmp, 255, 32);
3004 CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 0);
3005 memset(&pubkey, 1, sizeof(pubkey));
3006 VG_UNDEF(&pubkey, sizeof(pubkey));
3007 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 0);
3008 VG_CHECK(&pubkey, sizeof(pubkey));
3009 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
3010 /* Zero is too small, reject. */
3011 memset(ctmp, 0, 32);
3012 CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 0);
3013 memset(&pubkey, 1, sizeof(pubkey));
3014 VG_UNDEF(&pubkey, sizeof(pubkey));
3015 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 0);
3016 VG_CHECK(&pubkey, sizeof(pubkey));
3017 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
3018 /* One must be accepted. */
3020 CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 1);
3021 memset(&pubkey, 0, sizeof(pubkey));
3022 VG_UNDEF(&pubkey, sizeof(pubkey));
3023 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 1);
3024 VG_CHECK(&pubkey, sizeof(pubkey));
3025 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) > 0);
3026 pubkey_one = pubkey;
3027 /* Group order + 1 is too large, reject. */
3028 memcpy(ctmp, orderc, 32);
3030 CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 0);
3031 memset(&pubkey, 1, sizeof(pubkey));
3032 VG_UNDEF(&pubkey, sizeof(pubkey));
3033 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 0);
3034 VG_CHECK(&pubkey, sizeof(pubkey));
3035 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
3036 /* -1 must be accepted. */
3038 CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 1);
3039 memset(&pubkey, 0, sizeof(pubkey));
3040 VG_UNDEF(&pubkey, sizeof(pubkey));
3041 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 1);
3042 VG_CHECK(&pubkey, sizeof(pubkey));
3043 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) > 0);
3044 pubkey_negone = pubkey;
3045 /* Tweak of zero leaves the value changed. */
3046 memset(ctmp2, 0, 32);
3047 CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp, ctmp2) == 1);
3048 CHECK(memcmp(orderc, ctmp, 31) == 0 && ctmp[31] == 0x40);
3049 memcpy(&pubkey2, &pubkey, sizeof(pubkey));
3050 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 1);
3051 CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
3052 /* Multiply tweak of zero zeroizes the output. */
3053 CHECK(secp256k1_ec_privkey_tweak_mul(ctx, ctmp, ctmp2) == 0);
3054 CHECK(memcmp(zeros, ctmp, 32) == 0);
3055 CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, ctmp2) == 0);
3056 CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
3057 memcpy(&pubkey, &pubkey2, sizeof(pubkey));
3058 /* Overflowing key tweak zeroizes. */
3059 memcpy(ctmp, orderc, 32);
3061 CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp, orderc) == 0);
3062 CHECK(memcmp(zeros, ctmp, 32) == 0);
3063 memcpy(ctmp, orderc, 32);
3065 CHECK(secp256k1_ec_privkey_tweak_mul(ctx, ctmp, orderc) == 0);
3066 CHECK(memcmp(zeros, ctmp, 32) == 0);
3067 memcpy(ctmp, orderc, 32);
3069 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, orderc) == 0);
3070 CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
3071 memcpy(&pubkey, &pubkey2, sizeof(pubkey));
3072 CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, orderc) == 0);
3073 CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
3074 memcpy(&pubkey, &pubkey2, sizeof(pubkey));
3075 /* Private key tweaks results in a key of zero. */
3077 CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp2, ctmp) == 0);
3078 CHECK(memcmp(zeros, ctmp2, 32) == 0);
3080 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 0);
3081 CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
3082 memcpy(&pubkey, &pubkey2, sizeof(pubkey));
3083 /* Tweak computation wraps and results in a key of 1. */
3085 CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp2, ctmp) == 1);
3086 CHECK(memcmp(ctmp2, zeros, 31) == 0 && ctmp2[31] == 1);
3088 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 1);
3090 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey2, ctmp2) == 1);
3091 CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
3092 /* Tweak mul * 2 = 1+1. */
3093 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 1);
3095 CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey2, ctmp2) == 1);
3096 CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
3097 /* Test argument errors. */
3099 secp256k1_context_set_illegal_callback(ctx, counting_illegal_callback_fn, &ecount);
3101 /* Zeroize pubkey on parse error. */
3102 memset(&pubkey, 0, 32);
3103 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 0);
3105 CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
3106 memcpy(&pubkey, &pubkey2, sizeof(pubkey));
3107 memset(&pubkey2, 0, 32);
3108 CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey2, ctmp2) == 0);
3110 CHECK(memcmp(&pubkey2, zeros, sizeof(pubkey2)) == 0);
3111 /* Plain argument errors. */
3113 CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 1);
3115 CHECK(secp256k1_ec_seckey_verify(ctx, NULL) == 0);
3118 memset(ctmp2, 0, 32);
3120 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, NULL, ctmp2) == 0);
3122 CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, NULL) == 0);
3125 memset(ctmp2, 0, 32);
3127 CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, NULL, ctmp2) == 0);
3129 CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, NULL) == 0);
3132 memset(ctmp2, 0, 32);
3133 CHECK(secp256k1_ec_privkey_tweak_add(ctx, NULL, ctmp2) == 0);
3135 CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp, NULL) == 0);
3138 memset(ctmp2, 0, 32);
3140 CHECK(secp256k1_ec_privkey_tweak_mul(ctx, NULL, ctmp2) == 0);
3142 CHECK(secp256k1_ec_privkey_tweak_mul(ctx, ctmp, NULL) == 0);
3145 CHECK(secp256k1_ec_pubkey_create(ctx, NULL, ctmp) == 0);
3147 memset(&pubkey, 1, sizeof(pubkey));
3148 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, NULL) == 0);
3150 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
3151 /* secp256k1_ec_pubkey_combine tests. */
3153 pubkeys[0] = &pubkey_one;
3154 VG_UNDEF(&pubkeys[0], sizeof(secp256k1_pubkey *));
3155 VG_UNDEF(&pubkeys[1], sizeof(secp256k1_pubkey *));
3156 VG_UNDEF(&pubkeys[2], sizeof(secp256k1_pubkey *));
3157 memset(&pubkey, 255, sizeof(secp256k1_pubkey));
3158 VG_UNDEF(&pubkey, sizeof(secp256k1_pubkey));
3159 CHECK(secp256k1_ec_pubkey_combine(ctx, &pubkey, pubkeys, 0) == 0);
3160 VG_CHECK(&pubkey, sizeof(secp256k1_pubkey));
3161 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
3163 CHECK(secp256k1_ec_pubkey_combine(ctx, NULL, pubkeys, 1) == 0);
3164 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
3166 memset(&pubkey, 255, sizeof(secp256k1_pubkey));
3167 VG_UNDEF(&pubkey, sizeof(secp256k1_pubkey));
3168 CHECK(secp256k1_ec_pubkey_combine(ctx, &pubkey, NULL, 1) == 0);
3169 VG_CHECK(&pubkey, sizeof(secp256k1_pubkey));
3170 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
3172 pubkeys[0] = &pubkey_negone;
3173 memset(&pubkey, 255, sizeof(secp256k1_pubkey));
3174 VG_UNDEF(&pubkey, sizeof(secp256k1_pubkey));
3175 CHECK(secp256k1_ec_pubkey_combine(ctx, &pubkey, pubkeys, 1) == 1);
3176 VG_CHECK(&pubkey, sizeof(secp256k1_pubkey));
3177 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) > 0);
3180 CHECK(secp256k1_ec_pubkey_serialize(ctx, ctmp, &len, &pubkey, SECP256K1_EC_COMPRESSED) == 1);
3181 CHECK(secp256k1_ec_pubkey_serialize(ctx, ctmp2, &len, &pubkey_negone, SECP256K1_EC_COMPRESSED) == 1);
3182 CHECK(memcmp(ctmp, ctmp2, 33) == 0);
3183 /* Result is infinity. */
3184 pubkeys[0] = &pubkey_one;
3185 pubkeys[1] = &pubkey_negone;
3186 memset(&pubkey, 255, sizeof(secp256k1_pubkey));
3187 VG_UNDEF(&pubkey, sizeof(secp256k1_pubkey));
3188 CHECK(secp256k1_ec_pubkey_combine(ctx, &pubkey, pubkeys, 2) == 0);
3189 VG_CHECK(&pubkey, sizeof(secp256k1_pubkey));
3190 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
3192 /* Passes through infinity but comes out one. */
3193 pubkeys[2] = &pubkey_one;
3194 memset(&pubkey, 255, sizeof(secp256k1_pubkey));
3195 VG_UNDEF(&pubkey, sizeof(secp256k1_pubkey));
3196 CHECK(secp256k1_ec_pubkey_combine(ctx, &pubkey, pubkeys, 3) == 1);
3197 VG_CHECK(&pubkey, sizeof(secp256k1_pubkey));
3198 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) > 0);
3201 CHECK(secp256k1_ec_pubkey_serialize(ctx, ctmp, &len, &pubkey, SECP256K1_EC_COMPRESSED) == 1);
3202 CHECK(secp256k1_ec_pubkey_serialize(ctx, ctmp2, &len, &pubkey_one, SECP256K1_EC_COMPRESSED) == 1);
3203 CHECK(memcmp(ctmp, ctmp2, 33) == 0);
3205 pubkeys[1] = &pubkey_one;
3206 memset(&pubkey, 255, sizeof(secp256k1_pubkey));
3207 VG_UNDEF(&pubkey, sizeof(secp256k1_pubkey));
3208 CHECK(secp256k1_ec_pubkey_combine(ctx, &pubkey, pubkeys, 2) == 1);
3209 VG_CHECK(&pubkey, sizeof(secp256k1_pubkey));
3210 CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) > 0);
3212 secp256k1_context_set_illegal_callback(ctx, NULL, NULL);
3215 void random_sign(secp256k1_scalar *sigr, secp256k1_scalar *sigs, const secp256k1_scalar *key, const secp256k1_scalar *msg, int *recid) {
3216 secp256k1_scalar nonce;
3218 random_scalar_order_test(&nonce);
3219 } while(!secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, sigr, sigs, key, msg, &nonce, recid));
3222 void test_ecdsa_sign_verify(void) {
3225 secp256k1_scalar one;
3226 secp256k1_scalar msg, key;
3227 secp256k1_scalar sigr, sigs;
3230 random_scalar_order_test(&msg);
3231 random_scalar_order_test(&key);
3232 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pubj, &key);
3233 secp256k1_ge_set_gej(&pub, &pubj);
3234 getrec = secp256k1_rand_bits(1);
3235 random_sign(&sigr, &sigs, &key, &msg, getrec?&recid:NULL);
3237 CHECK(recid >= 0 && recid < 4);
3239 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sigr, &sigs, &pub, &msg));
3240 secp256k1_scalar_set_int(&one, 1);
3241 secp256k1_scalar_add(&msg, &msg, &one);
3242 CHECK(!secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sigr, &sigs, &pub, &msg));
3245 void run_ecdsa_sign_verify(void) {
3247 for (i = 0; i < 10*count; i++) {
3248 test_ecdsa_sign_verify();
3252 /** Dummy nonce generation function that just uses a precomputed nonce, and fails if it is not accepted. Use only for testing. */
3253 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) {
3257 memcpy(nonce32, data, 32);
3258 return (counter == 0);
3261 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) {
3262 /* Dummy nonce generator that has a fatal error on the first counter value. */
3266 return nonce_function_rfc6979(nonce32, msg32, key32, algo16, data, counter - 1);
3269 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) {
3270 /* Dummy nonce generator that produces unacceptable nonces for the first several counter values. */
3272 memset(nonce32, counter==0 ? 0 : 255, 32);
3279 static const unsigned char order[] = {
3280 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
3281 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
3282 0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
3283 0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x41
3285 memcpy(nonce32, order, 32);
3291 /* Retry rate of 6979 is negligible esp. as we only call this in deterministic tests. */
3292 /* If someone does fine a case where it retries for secp256k1, we'd like to know. */
3296 return nonce_function_rfc6979(nonce32, msg32, key32, algo16, data, counter - 5);
3299 int is_empty_signature(const secp256k1_ecdsa_signature *sig) {
3300 static const unsigned char res[sizeof(secp256k1_ecdsa_signature)] = {0};
3301 return memcmp(sig, res, sizeof(secp256k1_ecdsa_signature)) == 0;
3304 void test_ecdsa_end_to_end(void) {
3305 unsigned char extra[32] = {0x00};
3306 unsigned char privkey[32];
3307 unsigned char message[32];
3308 unsigned char privkey2[32];
3309 secp256k1_ecdsa_signature signature[6];
3310 secp256k1_scalar r, s;
3311 unsigned char sig[74];
3313 unsigned char pubkeyc[65];
3314 size_t pubkeyclen = 65;
3315 secp256k1_pubkey pubkey;
3316 unsigned char seckey[300];
3317 size_t seckeylen = 300;
3319 /* Generate a random key and message. */
3321 secp256k1_scalar msg, key;
3322 random_scalar_order_test(&msg);
3323 random_scalar_order_test(&key);
3324 secp256k1_scalar_get_b32(privkey, &key);
3325 secp256k1_scalar_get_b32(message, &msg);
3328 /* Construct and verify corresponding public key. */
3329 CHECK(secp256k1_ec_seckey_verify(ctx, privkey) == 1);
3330 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, privkey) == 1);
3332 /* Verify exporting and importing public key. */
3333 CHECK(secp256k1_ec_pubkey_serialize(ctx, pubkeyc, &pubkeyclen, &pubkey, secp256k1_rand_bits(1) == 1 ? SECP256K1_EC_COMPRESSED : SECP256K1_EC_UNCOMPRESSED));
3334 memset(&pubkey, 0, sizeof(pubkey));
3335 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, pubkeyclen) == 1);
3337 /* Verify private key import and export. */
3338 CHECK(ec_privkey_export_der(ctx, seckey, &seckeylen, privkey, secp256k1_rand_bits(1) == 1));
3339 CHECK(ec_privkey_import_der(ctx, privkey2, seckey, seckeylen) == 1);
3340 CHECK(memcmp(privkey, privkey2, 32) == 0);
3342 /* Optionally tweak the keys using addition. */
3343 if (secp256k1_rand_int(3) == 0) {
3346 unsigned char rnd[32];
3347 secp256k1_pubkey pubkey2;
3348 secp256k1_rand256_test(rnd);
3349 ret1 = secp256k1_ec_privkey_tweak_add(ctx, privkey, rnd);
3350 ret2 = secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, rnd);
3351 CHECK(ret1 == ret2);
3355 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey2, privkey) == 1);
3356 CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
3359 /* Optionally tweak the keys using multiplication. */
3360 if (secp256k1_rand_int(3) == 0) {
3363 unsigned char rnd[32];
3364 secp256k1_pubkey pubkey2;
3365 secp256k1_rand256_test(rnd);
3366 ret1 = secp256k1_ec_privkey_tweak_mul(ctx, privkey, rnd);
3367 ret2 = secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, rnd);
3368 CHECK(ret1 == ret2);
3372 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey2, privkey) == 1);
3373 CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
3377 CHECK(secp256k1_ecdsa_sign(ctx, &signature[0], message, privkey, NULL, NULL) == 1);
3378 CHECK(secp256k1_ecdsa_sign(ctx, &signature[4], message, privkey, NULL, NULL) == 1);
3379 CHECK(secp256k1_ecdsa_sign(ctx, &signature[1], message, privkey, NULL, extra) == 1);
3381 CHECK(secp256k1_ecdsa_sign(ctx, &signature[2], message, privkey, NULL, extra) == 1);
3384 CHECK(secp256k1_ecdsa_sign(ctx, &signature[3], message, privkey, NULL, extra) == 1);
3385 CHECK(memcmp(&signature[0], &signature[4], sizeof(signature[0])) == 0);
3386 CHECK(memcmp(&signature[0], &signature[1], sizeof(signature[0])) != 0);
3387 CHECK(memcmp(&signature[0], &signature[2], sizeof(signature[0])) != 0);
3388 CHECK(memcmp(&signature[0], &signature[3], sizeof(signature[0])) != 0);
3389 CHECK(memcmp(&signature[1], &signature[2], sizeof(signature[0])) != 0);
3390 CHECK(memcmp(&signature[1], &signature[3], sizeof(signature[0])) != 0);
3391 CHECK(memcmp(&signature[2], &signature[3], sizeof(signature[0])) != 0);
3393 CHECK(secp256k1_ecdsa_verify(ctx, &signature[0], message, &pubkey) == 1);
3394 CHECK(secp256k1_ecdsa_verify(ctx, &signature[1], message, &pubkey) == 1);
3395 CHECK(secp256k1_ecdsa_verify(ctx, &signature[2], message, &pubkey) == 1);
3396 CHECK(secp256k1_ecdsa_verify(ctx, &signature[3], message, &pubkey) == 1);
3397 /* Test lower-S form, malleate, verify and fail, test again, malleate again */
3398 CHECK(!secp256k1_ecdsa_signature_normalize(ctx, NULL, &signature[0]));
3399 secp256k1_ecdsa_signature_load(ctx, &r, &s, &signature[0]);
3400 secp256k1_scalar_negate(&s, &s);
3401 secp256k1_ecdsa_signature_save(&signature[5], &r, &s);
3402 CHECK(secp256k1_ecdsa_verify(ctx, &signature[5], message, &pubkey) == 0);
3403 CHECK(secp256k1_ecdsa_signature_normalize(ctx, NULL, &signature[5]));
3404 CHECK(secp256k1_ecdsa_signature_normalize(ctx, &signature[5], &signature[5]));
3405 CHECK(!secp256k1_ecdsa_signature_normalize(ctx, NULL, &signature[5]));
3406 CHECK(!secp256k1_ecdsa_signature_normalize(ctx, &signature[5], &signature[5]));
3407 CHECK(secp256k1_ecdsa_verify(ctx, &signature[5], message, &pubkey) == 1);
3408 secp256k1_scalar_negate(&s, &s);
3409 secp256k1_ecdsa_signature_save(&signature[5], &r, &s);
3410 CHECK(!secp256k1_ecdsa_signature_normalize(ctx, NULL, &signature[5]));
3411 CHECK(secp256k1_ecdsa_verify(ctx, &signature[5], message, &pubkey) == 1);
3412 CHECK(memcmp(&signature[5], &signature[0], 64) == 0);
3414 /* Serialize/parse DER and verify again */
3415 CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, sig, &siglen, &signature[0]) == 1);
3416 memset(&signature[0], 0, sizeof(signature[0]));
3417 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &signature[0], sig, siglen) == 1);
3418 CHECK(secp256k1_ecdsa_verify(ctx, &signature[0], message, &pubkey) == 1);
3419 /* Serialize/destroy/parse DER and verify again. */
3421 CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, sig, &siglen, &signature[0]) == 1);
3422 sig[secp256k1_rand_int(siglen)] += 1 + secp256k1_rand_int(255);
3423 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &signature[0], sig, siglen) == 0 ||
3424 secp256k1_ecdsa_verify(ctx, &signature[0], message, &pubkey) == 0);
3427 void test_random_pubkeys(void) {
3430 unsigned char in[65];
3431 /* Generate some randomly sized pubkeys. */
3432 size_t len = secp256k1_rand_bits(2) == 0 ? 65 : 33;
3433 if (secp256k1_rand_bits(2) == 0) {
3434 len = secp256k1_rand_bits(6);
3437 in[0] = secp256k1_rand_bits(1) ? 4 : (secp256k1_rand_bits(1) ? 6 : 7);
3439 in[0] = secp256k1_rand_bits(1) ? 2 : 3;
3441 if (secp256k1_rand_bits(3) == 0) {
3442 in[0] = secp256k1_rand_bits(8);
3445 secp256k1_rand256(&in[1]);
3448 secp256k1_rand256(&in[33]);
3450 if (secp256k1_eckey_pubkey_parse(&elem, in, len)) {
3451 unsigned char out[65];
3452 unsigned char firstb;
3456 /* If the pubkey can be parsed, it should round-trip... */
3457 CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, len == 33));
3459 CHECK(memcmp(&in[1], &out[1], len-1) == 0);
3460 /* ... except for the type of hybrid inputs. */
3461 if ((in[0] != 6) && (in[0] != 7)) {
3462 CHECK(in[0] == out[0]);
3465 CHECK(secp256k1_eckey_pubkey_serialize(&elem, in, &size, 0));
3467 CHECK(secp256k1_eckey_pubkey_parse(&elem2, in, size));
3468 ge_equals_ge(&elem,&elem2);
3469 /* Check that the X9.62 hybrid type is checked. */
3470 in[0] = secp256k1_rand_bits(1) ? 6 : 7;
3471 res = secp256k1_eckey_pubkey_parse(&elem2, in, size);
3472 if (firstb == 2 || firstb == 3) {
3473 if (in[0] == firstb + 4) {
3480 ge_equals_ge(&elem,&elem2);
3481 CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, 0));
3482 CHECK(memcmp(&in[1], &out[1], 64) == 0);
3487 void run_random_pubkeys(void) {
3489 for (i = 0; i < 10*count; i++) {
3490 test_random_pubkeys();
3494 void run_ecdsa_end_to_end(void) {
3496 for (i = 0; i < 64*count; i++) {
3497 test_ecdsa_end_to_end();
3501 int test_ecdsa_der_parse(const unsigned char *sig, size_t siglen, int certainly_der, int certainly_not_der) {
3502 static const unsigned char zeroes[32] = {0};
3503 static const unsigned char max_scalar[32] = {
3504 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3505 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
3506 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
3507 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x40
3512 secp256k1_ecdsa_signature sig_der;
3513 unsigned char roundtrip_der[2048];
3514 unsigned char compact_der[64];
3515 size_t len_der = 2048;
3516 int parsed_der = 0, valid_der = 0, roundtrips_der = 0;
3518 secp256k1_ecdsa_signature sig_der_lax;
3519 unsigned char roundtrip_der_lax[2048];
3520 unsigned char compact_der_lax[64];
3521 size_t len_der_lax = 2048;
3522 int parsed_der_lax = 0, valid_der_lax = 0, roundtrips_der_lax = 0;
3524 #ifdef ENABLE_OPENSSL_TESTS
3525 ECDSA_SIG *sig_openssl;
3526 const unsigned char *sigptr;
3527 unsigned char roundtrip_openssl[2048];
3528 int len_openssl = 2048;
3529 int parsed_openssl, valid_openssl = 0, roundtrips_openssl = 0;
3532 parsed_der = secp256k1_ecdsa_signature_parse_der(ctx, &sig_der, sig, siglen);
3534 ret |= (!secp256k1_ecdsa_signature_serialize_compact(ctx, compact_der, &sig_der)) << 0;
3535 valid_der = (memcmp(compact_der, zeroes, 32) != 0) && (memcmp(compact_der + 32, zeroes, 32) != 0);
3538 ret |= (!secp256k1_ecdsa_signature_serialize_der(ctx, roundtrip_der, &len_der, &sig_der)) << 1;
3539 roundtrips_der = (len_der == siglen) && memcmp(roundtrip_der, sig, siglen) == 0;
3542 parsed_der_lax = ecdsa_signature_parse_der_lax(ctx, &sig_der_lax, sig, siglen);
3543 if (parsed_der_lax) {
3544 ret |= (!secp256k1_ecdsa_signature_serialize_compact(ctx, compact_der_lax, &sig_der_lax)) << 10;
3545 valid_der_lax = (memcmp(compact_der_lax, zeroes, 32) != 0) && (memcmp(compact_der_lax + 32, zeroes, 32) != 0);
3547 if (valid_der_lax) {
3548 ret |= (!secp256k1_ecdsa_signature_serialize_der(ctx, roundtrip_der_lax, &len_der_lax, &sig_der_lax)) << 11;
3549 roundtrips_der_lax = (len_der_lax == siglen) && memcmp(roundtrip_der_lax, sig, siglen) == 0;
3552 if (certainly_der) {
3553 ret |= (!parsed_der) << 2;
3555 if (certainly_not_der) {
3556 ret |= (parsed_der) << 17;
3559 ret |= (!roundtrips_der) << 3;
3563 ret |= (!roundtrips_der_lax) << 12;
3564 ret |= (len_der != len_der_lax) << 13;
3565 ret |= (memcmp(roundtrip_der_lax, roundtrip_der, len_der) != 0) << 14;
3567 ret |= (roundtrips_der != roundtrips_der_lax) << 15;
3569 ret |= (!parsed_der_lax) << 16;
3572 #ifdef ENABLE_OPENSSL_TESTS
3573 sig_openssl = ECDSA_SIG_new();
3575 parsed_openssl = (d2i_ECDSA_SIG(&sig_openssl, &sigptr, siglen) != NULL);
3576 if (parsed_openssl) {
3577 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;
3578 if (valid_openssl) {
3579 unsigned char tmp[32] = {0};
3580 BN_bn2bin(sig_openssl->r, tmp + 32 - BN_num_bytes(sig_openssl->r));
3581 valid_openssl = memcmp(tmp, max_scalar, 32) < 0;
3583 if (valid_openssl) {
3584 unsigned char tmp[32] = {0};
3585 BN_bn2bin(sig_openssl->s, tmp + 32 - BN_num_bytes(sig_openssl->s));
3586 valid_openssl = memcmp(tmp, max_scalar, 32) < 0;
3589 len_openssl = i2d_ECDSA_SIG(sig_openssl, NULL);
3590 if (len_openssl <= 2048) {
3591 unsigned char *ptr = roundtrip_openssl;
3592 CHECK(i2d_ECDSA_SIG(sig_openssl, &ptr) == len_openssl);
3593 roundtrips_openssl = valid_openssl && ((size_t)len_openssl == siglen) && (memcmp(roundtrip_openssl, sig, siglen) == 0);
3597 ECDSA_SIG_free(sig_openssl);
3599 ret |= (parsed_der && !parsed_openssl) << 4;
3600 ret |= (valid_der && !valid_openssl) << 5;
3601 ret |= (roundtrips_openssl && !parsed_der) << 6;
3602 ret |= (roundtrips_der != roundtrips_openssl) << 7;
3603 if (roundtrips_openssl) {
3604 ret |= (len_der != (size_t)len_openssl) << 8;
3605 ret |= (memcmp(roundtrip_der, roundtrip_openssl, len_der) != 0) << 9;
3611 static void assign_big_endian(unsigned char *ptr, size_t ptrlen, uint32_t val) {
3613 for (i = 0; i < ptrlen; i++) {
3614 int shift = ptrlen - 1 - i;
3618 ptr[i] = (val >> shift) & 0xFF;
3623 static void damage_array(unsigned char *sig, size_t *len) {
3625 int action = secp256k1_rand_bits(3);
3626 if (action < 1 && *len > 3) {
3627 /* Delete a byte. */
3628 pos = secp256k1_rand_int(*len);
3629 memmove(sig + pos, sig + pos + 1, *len - pos - 1);
3632 } else if (action < 2 && *len < 2048) {
3633 /* Insert a byte. */
3634 pos = secp256k1_rand_int(1 + *len);
3635 memmove(sig + pos + 1, sig + pos, *len - pos);
3636 sig[pos] = secp256k1_rand_bits(8);
3639 } else if (action < 4) {
3640 /* Modify a byte. */
3641 sig[secp256k1_rand_int(*len)] += 1 + secp256k1_rand_int(255);
3643 } else { /* action < 8 */
3645 sig[secp256k1_rand_int(*len)] ^= 1 << secp256k1_rand_bits(3);
3650 static void random_ber_signature(unsigned char *sig, size_t *len, int* certainly_der, int* certainly_not_der) {
3652 int nlow[2], nlen[2], nlenlen[2], nhbit[2], nhbyte[2], nzlen[2];
3653 size_t tlen, elen, glen;
3658 der = secp256k1_rand_bits(2) == 0;
3659 *certainly_der = der;
3660 *certainly_not_der = 0;
3661 indet = der ? 0 : secp256k1_rand_int(10) == 0;
3663 for (n = 0; n < 2; n++) {
3664 /* 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) */
3665 nlow[n] = der ? 1 : (secp256k1_rand_bits(3) != 0);
3666 /* The length of the number in bytes (the first byte of which will always be nonzero) */
3667 nlen[n] = nlow[n] ? secp256k1_rand_int(33) : 32 + secp256k1_rand_int(200) * secp256k1_rand_int(8) / 8;
3668 CHECK(nlen[n] <= 232);
3669 /* The top bit of the number. */
3670 nhbit[n] = (nlow[n] == 0 && nlen[n] == 32) ? 1 : (nlen[n] == 0 ? 0 : secp256k1_rand_bits(1));
3671 /* The top byte of the number (after the potential hardcoded 16 0xFF characters for "high" 32 bytes numbers) */
3672 nhbyte[n] = nlen[n] == 0 ? 0 : (nhbit[n] ? 128 + secp256k1_rand_bits(7) : 1 + secp256k1_rand_int(127));
3673 /* 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) */
3674 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);
3675 if (nzlen[n] > ((nlen[n] == 0 || nhbit[n]) ? 1 : 0)) {
3676 *certainly_not_der = 1;
3678 CHECK(nlen[n] + nzlen[n] <= 300);
3679 /* The length of the length descriptor for the number. 0 means short encoding, anything else is long encoding. */
3680 nlenlen[n] = nlen[n] + nzlen[n] < 128 ? 0 : (nlen[n] + nzlen[n] < 256 ? 1 : 2);
3682 /* nlenlen[n] max 127 bytes */
3683 int add = secp256k1_rand_int(127 - nlenlen[n]) * secp256k1_rand_int(16) * secp256k1_rand_int(16) / 256;
3686 *certainly_not_der = 1;
3689 CHECK(nlen[n] + nzlen[n] + nlenlen[n] <= 427);
3692 /* The total length of the data to go, so far */
3693 tlen = 2 + nlenlen[0] + nlen[0] + nzlen[0] + 2 + nlenlen[1] + nlen[1] + nzlen[1];
3696 /* The length of the garbage inside the tuple. */
3697 elen = (der || indet) ? 0 : secp256k1_rand_int(980 - tlen) * secp256k1_rand_int(8) / 8;
3699 *certainly_not_der = 1;
3704 /* The length of the garbage after the end of the tuple. */
3705 glen = der ? 0 : secp256k1_rand_int(990 - tlen) * secp256k1_rand_int(8) / 8;
3707 *certainly_not_der = 1;
3709 CHECK(tlen + glen <= 990);
3711 /* Write the tuple header. */
3712 sig[(*len)++] = 0x30;
3714 /* Indeterminate length */
3715 sig[(*len)++] = 0x80;
3716 *certainly_not_der = 1;
3718 int tlenlen = tlen < 128 ? 0 : (tlen < 256 ? 1 : 2);
3720 int add = secp256k1_rand_int(127 - tlenlen) * secp256k1_rand_int(16) * secp256k1_rand_int(16) / 256;
3723 *certainly_not_der = 1;
3727 /* Short length notation */
3728 sig[(*len)++] = tlen;
3730 /* Long length notation */
3731 sig[(*len)++] = 128 + tlenlen;
3732 assign_big_endian(sig + *len, tlenlen, tlen);
3738 CHECK(tlen + glen <= 1119);
3740 for (n = 0; n < 2; n++) {
3741 /* Write the integer header. */
3742 sig[(*len)++] = 0x02;
3743 if (nlenlen[n] == 0) {
3744 /* Short length notation */
3745 sig[(*len)++] = nlen[n] + nzlen[n];
3747 /* Long length notation. */
3748 sig[(*len)++] = 128 + nlenlen[n];
3749 assign_big_endian(sig + *len, nlenlen[n], nlen[n] + nzlen[n]);
3752 /* Write zero padding */
3753 while (nzlen[n] > 0) {
3754 sig[(*len)++] = 0x00;
3757 if (nlen[n] == 32 && !nlow[n]) {
3758 /* Special extra 16 0xFF bytes in "high" 32-byte numbers */
3760 for (i = 0; i < 16; i++) {
3761 sig[(*len)++] = 0xFF;
3765 /* Write first byte of number */
3767 sig[(*len)++] = nhbyte[n];
3770 /* Generate remaining random bytes of number */
3771 secp256k1_rand_bytes_test(sig + *len, nlen[n]);
3776 /* Generate random garbage inside tuple. */
3777 secp256k1_rand_bytes_test(sig + *len, elen);
3780 /* Generate end-of-contents bytes. */
3786 CHECK(tlen + glen <= 1121);
3788 /* Generate random garbage outside tuple. */
3789 secp256k1_rand_bytes_test(sig + *len, glen);
3792 CHECK(tlen <= 1121);
3793 CHECK(tlen == *len);
3796 void run_ecdsa_der_parse(void) {
3798 for (i = 0; i < 200 * count; i++) {
3799 unsigned char buffer[2048];
3801 int certainly_der = 0;
3802 int certainly_not_der = 0;
3803 random_ber_signature(buffer, &buflen, &certainly_der, &certainly_not_der);
3804 CHECK(buflen <= 2048);
3805 for (j = 0; j < 16; j++) {
3808 damage_array(buffer, &buflen);
3809 /* We don't know anything anymore about the DERness of the result */
3811 certainly_not_der = 0;
3813 ret = test_ecdsa_der_parse(buffer, buflen, certainly_der, certainly_not_der);
3816 fprintf(stderr, "Failure %x on ", ret);
3817 for (k = 0; k < buflen; k++) {
3818 fprintf(stderr, "%02x ", buffer[k]);
3820 fprintf(stderr, "\n");
3827 /* Tests several edge cases. */
3828 void test_ecdsa_edge_cases(void) {
3830 secp256k1_ecdsa_signature sig;
3832 /* Test the case where ECDSA recomputes a point that is infinity. */
3836 secp256k1_scalar msg;
3837 secp256k1_scalar sr, ss;
3838 secp256k1_scalar_set_int(&ss, 1);
3839 secp256k1_scalar_negate(&ss, &ss);
3840 secp256k1_scalar_inverse(&ss, &ss);
3841 secp256k1_scalar_set_int(&sr, 1);
3842 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &keyj, &sr);
3843 secp256k1_ge_set_gej(&key, &keyj);
3845 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3848 /* Verify signature with r of zero fails. */
3850 const unsigned char pubkey_mods_zero[33] = {
3851 0x02, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3852 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3853 0xfe, 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0,
3854 0x3b, 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41,
3858 secp256k1_scalar msg;
3859 secp256k1_scalar sr, ss;
3860 secp256k1_scalar_set_int(&ss, 1);
3861 secp256k1_scalar_set_int(&msg, 0);
3862 secp256k1_scalar_set_int(&sr, 0);
3863 CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey_mods_zero, 33));
3864 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3867 /* Verify signature with s of zero fails. */
3869 const unsigned char pubkey[33] = {
3870 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3871 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3872 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3873 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3877 secp256k1_scalar msg;
3878 secp256k1_scalar sr, ss;
3879 secp256k1_scalar_set_int(&ss, 0);
3880 secp256k1_scalar_set_int(&msg, 0);
3881 secp256k1_scalar_set_int(&sr, 1);
3882 CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey, 33));
3883 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3886 /* Verify signature with message 0 passes. */
3888 const unsigned char pubkey[33] = {
3889 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3890 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3891 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3892 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3895 const unsigned char pubkey2[33] = {
3896 0x02, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3897 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3898 0xfe, 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0,
3899 0x3b, 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41,
3904 secp256k1_scalar msg;
3905 secp256k1_scalar sr, ss;
3906 secp256k1_scalar_set_int(&ss, 2);
3907 secp256k1_scalar_set_int(&msg, 0);
3908 secp256k1_scalar_set_int(&sr, 2);
3909 CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey, 33));
3910 CHECK(secp256k1_eckey_pubkey_parse(&key2, pubkey2, 33));
3911 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3912 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 1);
3913 secp256k1_scalar_negate(&ss, &ss);
3914 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3915 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 1);
3916 secp256k1_scalar_set_int(&ss, 1);
3917 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3918 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 0);
3921 /* Verify signature with message 1 passes. */
3923 const unsigned char pubkey[33] = {
3924 0x02, 0x14, 0x4e, 0x5a, 0x58, 0xef, 0x5b, 0x22,
3925 0x6f, 0xd2, 0xe2, 0x07, 0x6a, 0x77, 0xcf, 0x05,
3926 0xb4, 0x1d, 0xe7, 0x4a, 0x30, 0x98, 0x27, 0x8c,
3927 0x93, 0xe6, 0xe6, 0x3c, 0x0b, 0xc4, 0x73, 0x76,
3930 const unsigned char pubkey2[33] = {
3931 0x02, 0x8a, 0xd5, 0x37, 0xed, 0x73, 0xd9, 0x40,
3932 0x1d, 0xa0, 0x33, 0xd2, 0xdc, 0xf0, 0xaf, 0xae,
3933 0x34, 0xcf, 0x5f, 0x96, 0x4c, 0x73, 0x28, 0x0f,
3934 0x92, 0xc0, 0xf6, 0x9d, 0xd9, 0xb2, 0x09, 0x10,
3937 const unsigned char csr[32] = {
3938 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3939 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
3940 0x45, 0x51, 0x23, 0x19, 0x50, 0xb7, 0x5f, 0xc4,
3941 0x40, 0x2d, 0xa1, 0x72, 0x2f, 0xc9, 0xba, 0xeb
3945 secp256k1_scalar msg;
3946 secp256k1_scalar sr, ss;
3947 secp256k1_scalar_set_int(&ss, 1);
3948 secp256k1_scalar_set_int(&msg, 1);
3949 secp256k1_scalar_set_b32(&sr, csr, NULL);
3950 CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey, 33));
3951 CHECK(secp256k1_eckey_pubkey_parse(&key2, pubkey2, 33));
3952 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3953 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 1);
3954 secp256k1_scalar_negate(&ss, &ss);
3955 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3956 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 1);
3957 secp256k1_scalar_set_int(&ss, 2);
3958 secp256k1_scalar_inverse_var(&ss, &ss);
3959 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3960 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 0);
3963 /* Verify signature with message -1 passes. */
3965 const unsigned char pubkey[33] = {
3966 0x03, 0xaf, 0x97, 0xff, 0x7d, 0x3a, 0xf6, 0xa0,
3967 0x02, 0x94, 0xbd, 0x9f, 0x4b, 0x2e, 0xd7, 0x52,
3968 0x28, 0xdb, 0x49, 0x2a, 0x65, 0xcb, 0x1e, 0x27,
3969 0x57, 0x9c, 0xba, 0x74, 0x20, 0xd5, 0x1d, 0x20,
3972 const unsigned char csr[32] = {
3973 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3974 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
3975 0x45, 0x51, 0x23, 0x19, 0x50, 0xb7, 0x5f, 0xc4,
3976 0x40, 0x2d, 0xa1, 0x72, 0x2f, 0xc9, 0xba, 0xee
3979 secp256k1_scalar msg;
3980 secp256k1_scalar sr, ss;
3981 secp256k1_scalar_set_int(&ss, 1);
3982 secp256k1_scalar_set_int(&msg, 1);
3983 secp256k1_scalar_negate(&msg, &msg);
3984 secp256k1_scalar_set_b32(&sr, csr, NULL);
3985 CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey, 33));
3986 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3987 secp256k1_scalar_negate(&ss, &ss);
3988 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3989 secp256k1_scalar_set_int(&ss, 3);
3990 secp256k1_scalar_inverse_var(&ss, &ss);
3991 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3994 /* Signature where s would be zero. */
3996 secp256k1_pubkey pubkey;
3999 unsigned char signature[72];
4000 static const unsigned char nonce[32] = {
4001 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
4002 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
4003 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
4004 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
4006 static const unsigned char nonce2[32] = {
4007 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
4008 0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
4009 0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
4010 0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x40
4012 const unsigned char key[32] = {
4013 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
4014 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
4015 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
4016 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
4018 unsigned char msg[32] = {
4019 0x86, 0x41, 0x99, 0x81, 0x06, 0x23, 0x44, 0x53,
4020 0xaa, 0x5f, 0x9d, 0x6a, 0x31, 0x78, 0xf4, 0xf7,
4021 0xb8, 0x12, 0xe0, 0x0b, 0x81, 0x7a, 0x77, 0x62,
4022 0x65, 0xdf, 0xdd, 0x31, 0xb9, 0x3e, 0x29, 0xa9,
4025 secp256k1_context_set_illegal_callback(ctx, counting_illegal_callback_fn, &ecount);
4026 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, precomputed_nonce_function, nonce) == 0);
4027 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, precomputed_nonce_function, nonce2) == 0);
4029 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, precomputed_nonce_function, nonce) == 1);
4031 CHECK(secp256k1_ecdsa_sign(ctx, NULL, msg, key, precomputed_nonce_function, nonce2) == 0);
4033 CHECK(secp256k1_ecdsa_sign(ctx, &sig, NULL, key, precomputed_nonce_function, nonce2) == 0);
4035 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, NULL, precomputed_nonce_function, nonce2) == 0);
4037 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, precomputed_nonce_function, nonce2) == 1);
4038 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, key) == 1);
4039 CHECK(secp256k1_ecdsa_verify(ctx, NULL, msg, &pubkey) == 0);
4041 CHECK(secp256k1_ecdsa_verify(ctx, &sig, NULL, &pubkey) == 0);
4043 CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg, NULL) == 0);
4045 CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg, &pubkey) == 1);
4047 CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, NULL) == 0);
4049 /* That pubkeyload fails via an ARGCHECK is a little odd but makes sense because pubkeys are an opaque data type. */
4050 CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg, &pubkey) == 0);
4053 CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, NULL, &siglen, &sig) == 0);
4055 CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, signature, NULL, &sig) == 0);
4056 CHECK(ecount == 10);
4057 CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, signature, &siglen, NULL) == 0);
4058 CHECK(ecount == 11);
4059 CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, signature, &siglen, &sig) == 1);
4060 CHECK(ecount == 11);
4061 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, NULL, signature, siglen) == 0);
4062 CHECK(ecount == 12);
4063 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, NULL, siglen) == 0);
4064 CHECK(ecount == 13);
4065 CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &sig, signature, siglen) == 1);
4066 CHECK(ecount == 13);
4068 /* Too little room for a signature does not fail via ARGCHECK. */
4069 CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, signature, &siglen, &sig) == 0);
4070 CHECK(ecount == 13);
4072 CHECK(secp256k1_ecdsa_signature_normalize(ctx, NULL, NULL) == 0);
4074 CHECK(secp256k1_ecdsa_signature_serialize_compact(ctx, NULL, &sig) == 0);
4076 CHECK(secp256k1_ecdsa_signature_serialize_compact(ctx, signature, NULL) == 0);
4078 CHECK(secp256k1_ecdsa_signature_serialize_compact(ctx, signature, &sig) == 1);
4080 CHECK(secp256k1_ecdsa_signature_parse_compact(ctx, NULL, signature) == 0);
4082 CHECK(secp256k1_ecdsa_signature_parse_compact(ctx, &sig, NULL) == 0);
4084 CHECK(secp256k1_ecdsa_signature_parse_compact(ctx, &sig, signature) == 1);
4086 memset(signature, 255, 64);
4087 CHECK(secp256k1_ecdsa_signature_parse_compact(ctx, &sig, signature) == 0);
4089 secp256k1_context_set_illegal_callback(ctx, NULL, NULL);
4092 /* Nonce function corner cases. */
4093 for (t = 0; t < 2; t++) {
4094 static const unsigned char zero[32] = {0x00};
4096 unsigned char key[32];
4097 unsigned char msg[32];
4098 secp256k1_ecdsa_signature sig2;
4099 secp256k1_scalar sr[512], ss;
4100 const unsigned char *extra;
4101 extra = t == 0 ? NULL : zero;
4104 /* High key results in signature failure. */
4105 memset(key, 0xFF, 32);
4106 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, NULL, extra) == 0);
4107 CHECK(is_empty_signature(&sig));
4108 /* Zero key results in signature failure. */
4110 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, NULL, extra) == 0);
4111 CHECK(is_empty_signature(&sig));
4112 /* Nonce function failure results in signature failure. */
4114 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, nonce_function_test_fail, extra) == 0);
4115 CHECK(is_empty_signature(&sig));
4116 /* The retry loop successfully makes its way to the first good value. */
4117 CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, nonce_function_test_retry, extra) == 1);
4118 CHECK(!is_empty_signature(&sig));
4119 CHECK(secp256k1_ecdsa_sign(ctx, &sig2, msg, key, nonce_function_rfc6979, extra) == 1);
4120 CHECK(!is_empty_signature(&sig2));
4121 CHECK(memcmp(&sig, &sig2, sizeof(sig)) == 0);
4122 /* The default nonce function is deterministic. */
4123 CHECK(secp256k1_ecdsa_sign(ctx, &sig2, msg, key, NULL, extra) == 1);
4124 CHECK(!is_empty_signature(&sig2));
4125 CHECK(memcmp(&sig, &sig2, sizeof(sig)) == 0);
4126 /* The default nonce function changes output with different messages. */
4127 for(i = 0; i < 256; i++) {
4130 CHECK(secp256k1_ecdsa_sign(ctx, &sig2, msg, key, NULL, extra) == 1);
4131 CHECK(!is_empty_signature(&sig2));
4132 secp256k1_ecdsa_signature_load(ctx, &sr[i], &ss, &sig2);
4133 for (j = 0; j < i; j++) {
4134 CHECK(!secp256k1_scalar_eq(&sr[i], &sr[j]));
4139 /* The default nonce function changes output with different keys. */
4140 for(i = 256; i < 512; i++) {
4143 CHECK(secp256k1_ecdsa_sign(ctx, &sig2, msg, key, NULL, extra) == 1);
4144 CHECK(!is_empty_signature(&sig2));
4145 secp256k1_ecdsa_signature_load(ctx, &sr[i], &ss, &sig2);
4146 for (j = 0; j < i; j++) {
4147 CHECK(!secp256k1_scalar_eq(&sr[i], &sr[j]));
4154 /* Check that optional nonce arguments do not have equivalent effect. */
4155 const unsigned char zeros[32] = {0};
4156 unsigned char nonce[32];
4157 unsigned char nonce2[32];
4158 unsigned char nonce3[32];
4159 unsigned char nonce4[32];
4161 VG_UNDEF(nonce2,32);
4162 VG_UNDEF(nonce3,32);
4163 VG_UNDEF(nonce4,32);
4164 CHECK(nonce_function_rfc6979(nonce, zeros, zeros, NULL, NULL, 0) == 1);
4166 CHECK(nonce_function_rfc6979(nonce2, zeros, zeros, zeros, NULL, 0) == 1);
4167 VG_CHECK(nonce2,32);
4168 CHECK(nonce_function_rfc6979(nonce3, zeros, zeros, NULL, (void *)zeros, 0) == 1);
4169 VG_CHECK(nonce3,32);
4170 CHECK(nonce_function_rfc6979(nonce4, zeros, zeros, zeros, (void *)zeros, 0) == 1);
4171 VG_CHECK(nonce4,32);
4172 CHECK(memcmp(nonce, nonce2, 32) != 0);
4173 CHECK(memcmp(nonce, nonce3, 32) != 0);
4174 CHECK(memcmp(nonce, nonce4, 32) != 0);
4175 CHECK(memcmp(nonce2, nonce3, 32) != 0);
4176 CHECK(memcmp(nonce2, nonce4, 32) != 0);
4177 CHECK(memcmp(nonce3, nonce4, 32) != 0);
4181 /* Privkey export where pubkey is the point at infinity. */
4183 unsigned char privkey[300];
4184 unsigned char seckey[32] = {
4185 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
4186 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
4187 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
4188 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41,
4190 size_t outlen = 300;
4191 CHECK(!ec_privkey_export_der(ctx, privkey, &outlen, seckey, 0));
4193 CHECK(!ec_privkey_export_der(ctx, privkey, &outlen, seckey, 1));
4197 void run_ecdsa_edge_cases(void) {
4198 test_ecdsa_edge_cases();
4201 #ifdef ENABLE_OPENSSL_TESTS
4202 EC_KEY *get_openssl_key(const unsigned char *key32) {
4203 unsigned char privkey[300];
4205 const unsigned char* pbegin = privkey;
4206 int compr = secp256k1_rand_bits(1);
4207 EC_KEY *ec_key = EC_KEY_new_by_curve_name(NID_secp256k1);
4208 CHECK(ec_privkey_export_der(ctx, privkey, &privkeylen, key32, compr));
4209 CHECK(d2i_ECPrivateKey(&ec_key, &pbegin, privkeylen));
4210 CHECK(EC_KEY_check_key(ec_key));
4214 void test_ecdsa_openssl(void) {
4217 secp256k1_scalar sigr, sigs;
4218 secp256k1_scalar one;
4219 secp256k1_scalar msg2;
4220 secp256k1_scalar key, msg;
4222 unsigned int sigsize = 80;
4223 size_t secp_sigsize = 80;
4224 unsigned char message[32];
4225 unsigned char signature[80];
4226 unsigned char key32[32];
4227 secp256k1_rand256_test(message);
4228 secp256k1_scalar_set_b32(&msg, message, NULL);
4229 random_scalar_order_test(&key);
4230 secp256k1_scalar_get_b32(key32, &key);
4231 secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &qj, &key);
4232 secp256k1_ge_set_gej(&q, &qj);
4233 ec_key = get_openssl_key(key32);
4234 CHECK(ec_key != NULL);
4235 CHECK(ECDSA_sign(0, message, sizeof(message), signature, &sigsize, ec_key));
4236 CHECK(secp256k1_ecdsa_sig_parse(&sigr, &sigs, signature, sigsize));
4237 CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sigr, &sigs, &q, &msg));
4238 secp256k1_scalar_set_int(&one, 1);
4239 secp256k1_scalar_add(&msg2, &msg, &one);
4240 CHECK(!secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sigr, &sigs, &q, &msg2));
4242 random_sign(&sigr, &sigs, &key, &msg, NULL);
4243 CHECK(secp256k1_ecdsa_sig_serialize(signature, &secp_sigsize, &sigr, &sigs));
4244 CHECK(ECDSA_verify(0, message, sizeof(message), signature, secp_sigsize, ec_key) == 1);
4246 EC_KEY_free(ec_key);
4249 void run_ecdsa_openssl(void) {
4251 for (i = 0; i < 10*count; i++) {
4252 test_ecdsa_openssl();
4257 #ifdef ENABLE_MODULE_ECDH
4258 # include "modules/ecdh/tests_impl.h"
4261 #ifdef ENABLE_MODULE_SCHNORR
4262 # include "modules/schnorr/tests_impl.h"
4265 #ifdef ENABLE_MODULE_RECOVERY
4266 # include "modules/recovery/tests_impl.h"
4269 int main(int argc, char **argv) {
4270 unsigned char seed16[16] = {0};
4271 unsigned char run32[32] = {0};
4272 /* find iteration count */
4274 count = strtol(argv[1], NULL, 0);
4277 /* find random seed */
4280 const char* ch = argv[2];
4281 while (pos < 16 && ch[0] != 0 && ch[1] != 0) {
4283 if (sscanf(ch, "%2hx", &sh)) {
4292 FILE *frand = fopen("/dev/urandom", "r");
4293 if ((frand == NULL) || !fread(&seed16, sizeof(seed16), 1, frand)) {
4294 uint64_t t = time(NULL) * (uint64_t)1337;
4296 seed16[1] ^= t >> 8;
4297 seed16[2] ^= t >> 16;
4298 seed16[3] ^= t >> 24;
4299 seed16[4] ^= t >> 32;
4300 seed16[5] ^= t >> 40;
4301 seed16[6] ^= t >> 48;
4302 seed16[7] ^= t >> 56;
4306 secp256k1_rand_seed(seed16);
4308 printf("test count = %i\n", count);
4309 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]);
4312 run_context_tests();
4313 ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY);
4314 if (secp256k1_rand_bits(1)) {
4315 secp256k1_rand256(run32);
4316 CHECK(secp256k1_context_randomize(ctx, secp256k1_rand_bits(1) ? run32 : NULL));
4323 run_hmac_sha256_tests();
4324 run_rfc6979_hmac_sha256_tests();
4326 #ifndef USE_NUM_NONE
4328 run_num_smalltests();
4336 run_field_inv_var();
4337 run_field_inv_all_var();
4339 run_field_convert();
4345 run_group_decompress();
4349 run_point_times_order();
4351 run_ecmult_constants();
4352 run_ecmult_gen_blind();
4353 run_ecmult_const_tests();
4356 /* endomorphism tests */
4357 #ifdef USE_ENDOMORPHISM
4358 run_endomorphism_tests();
4361 /* EC point parser test */
4362 run_ec_pubkey_parse_test();
4364 /* EC key edge cases */
4365 run_eckey_edge_case_test();
4367 #ifdef ENABLE_MODULE_ECDH
4373 run_random_pubkeys();
4374 run_ecdsa_der_parse();
4375 run_ecdsa_sign_verify();
4376 run_ecdsa_end_to_end();
4377 run_ecdsa_edge_cases();
4378 #ifdef ENABLE_OPENSSL_TESTS
4379 run_ecdsa_openssl();
4382 #ifdef ENABLE_MODULE_SCHNORR
4384 run_schnorr_tests();
4387 #ifdef ENABLE_MODULE_RECOVERY
4388 /* ECDSA pubkey recovery tests */
4389 run_recovery_tests();
4392 secp256k1_rand256(run32);
4393 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]);
4396 secp256k1_context_destroy(ctx);
4398 printf("no problems found\n");