src/tests.c

   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  **********************************************************************/
   6
   7 #if defined HAVE_CONFIG_H
   8 #include "libsecp256k1-config.h"
   9 #endif
  10
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13
  14 #include <time.h>
  15
  16 #include "secp256k1.c"
  17 #include "include/secp256k1.h"
  18 #include "testrand_impl.h"
  19
  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"
  25 #endif
  26
  27 #include "contrib/lax_der_parsing.c"
  28 #include "contrib/lax_der_privatekey_parsing.c"
  29
  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))
  35 # else
  36 #  define VG_UNDEF(x,y)
  37 #  define VG_CHECK(x,y)
  38 # endif
  39 #endif
  40
  41 static int count = 64;
  42 static secp256k1_context *ctx = NULL;
  43
  44 static void counting_illegal_callback_fn(const char* str, void* data) {
  45     /* Dummy callback function that just counts. */
  46     int32_t *p;
  47     (void)str;
  48     p = data;
  49     (*p)++;
  50 }
  51
  52 static void uncounting_illegal_callback_fn(const char* str, void* data) {
  53     /* Dummy callback function that just counts (backwards). */
  54     int32_t *p;
  55     (void)str;
  56     p = data;
  57     (*p)--;
  58 }
  59
  60 void random_field_element_test(secp256k1_fe *fe) {
  61     do {
  62         unsigned char b32[32];
  63         secp256k1_rand256_test(b32);
  64         if (secp256k1_fe_set_b32(fe, b32)) {
  65             break;
  66         }
  67     } while(1);
  68 }
  69
  70 void random_field_element_magnitude(secp256k1_fe *fe) {
  71     secp256k1_fe zero;
  72     int n = secp256k1_rand_int(9);
  73     secp256k1_fe_normalize(fe);
  74     if (n == 0) {
  75         return;
  76     }
  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);
  82 }
  83
  84 void random_group_element_test(secp256k1_ge *ge) {
  85     secp256k1_fe fe;
  86     do {
  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);
  90             break;
  91         }
  92     } while(1);
  93 }
  94
  95 void random_group_element_jacobian_test(secp256k1_gej *gej, const secp256k1_ge *ge) {
  96     secp256k1_fe z2, z3;
  97     do {
  98         random_field_element_test(&gej->z);
  99         if (!secp256k1_fe_is_zero(&gej->z)) {
 100             break;
 101         }
 102     } while(1);
 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;
 108 }
 109
 110 void random_scalar_order_test(secp256k1_scalar *num) {
 111     do {
 112         unsigned char b32[32];
 113         int overflow = 0;
 114         secp256k1_rand256_test(b32);
 115         secp256k1_scalar_set_b32(num, b32, &overflow);
 116         if (overflow || secp256k1_scalar_is_zero(num)) {
 117             continue;
 118         }
 119         break;
 120     } while(1);
 121 }
 122
 123 void random_scalar_order(secp256k1_scalar *num) {
 124     do {
 125         unsigned char b32[32];
 126         int overflow = 0;
 127         secp256k1_rand256(b32);
 128         secp256k1_scalar_set_b32(num, b32, &overflow);
 129         if (overflow || secp256k1_scalar_is_zero(num)) {
 130             continue;
 131         }
 132         break;
 133     } while(1);
 134 }
 135
 136 void run_context_tests(void) {
 137     secp256k1_pubkey pubkey;
 138     secp256k1_ecdsa_signature sig;
 139     unsigned char ctmp[32];
 140     int32_t ecount;
 141     int32_t ecount2;
 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);
 146
 147     secp256k1_gej pubj;
 148     secp256k1_ge pub;
 149     secp256k1_scalar msg, key, nonce;
 150     secp256k1_scalar sigr, sigs;
 151
 152     ecount = 0;
 153     ecount2 = 10;
 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);
 158
 159     /*** clone and destroy all of them to make sure cloning was complete ***/
 160     {
 161         secp256k1_context *ctx_tmp;
 162
 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);
 167     }
 168
 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);
 174
 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);
 180
 181     /* Verify context-type checking illegal-argument errors. */
 182     memset(ctmp, 1, 32);
 183     CHECK(secp256k1_ec_pubkey_create(vrfy, &pubkey, ctmp) == 0);
 184     CHECK(ecount == 1);
 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);
 189     CHECK(ecount == 2);
 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);
 197     CHECK(ecount == 2);
 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);
 201     CHECK(ecount == 2);
 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);
 205     CHECK(ecount == 2);
 206     CHECK(secp256k1_context_randomize(vrfy, ctmp) == 0);
 207     CHECK(ecount == 3);
 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);
 212
 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);
 216
 217     /* obtain a working nonce */
 218     do {
 219         random_scalar_order_test(&nonce);
 220     } while(!secp256k1_ecdsa_sig_sign(&both->ecmult_gen_ctx, &sigr, &sigs, &key, &msg, &nonce, NULL));
 221
 222     /* try signing */
 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));
 225
 226     /* try verifying */
 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));
 229
 230     /* cleanup */
 231     secp256k1_context_destroy(none);
 232     secp256k1_context_destroy(sign);
 233     secp256k1_context_destroy(vrfy);
 234     secp256k1_context_destroy(both);
 235 }
 236
 237 /***** HASH TESTS *****/
 238
 239 void run_sha256_tests(void) {
 240     static const char *inputs[8] = {
 241         "", "abc", "message digest", "secure hash algorithm", "SHA256 is considered to be safe",
 242         "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
 243         "For this sample, this 63-byte string will be used as input data",
 244         "This is exactly 64 bytes long, not counting the terminating byte"
 245     };
 246     static const unsigned char outputs[8][32] = {
 247         {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},
 248         {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},
 249         {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},
 250         {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},
 251         {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},
 252         {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},
 253         {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},
 254         {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}
 255     };
 256     int i;
 257     for (i = 0; i < 8; i++) {
 258         unsigned char out[32];
 259         secp256k1_sha256_t hasher;
 260         secp256k1_sha256_initialize(&hasher);
 261         secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i]), strlen(inputs[i]));
 262         secp256k1_sha256_finalize(&hasher, out);
 263         CHECK(memcmp(out, outputs[i], 32) == 0);
 264         if (strlen(inputs[i]) > 0) {
 265             int split = secp256k1_rand_int(strlen(inputs[i]));
 266             secp256k1_sha256_initialize(&hasher);
 267             secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i]), split);
 268             secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i] + split), strlen(inputs[i]) - split);
 269             secp256k1_sha256_finalize(&hasher, out);
 270             CHECK(memcmp(out, outputs[i], 32) == 0);
 271         }
 272     }
 273 }
 274
 275 void run_hmac_sha256_tests(void) {
 276     static const char *keys[6] = {
 277         "\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b",
 278         "\x4a\x65\x66\x65",
 279         "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa",
 280         "\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",
 281         "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa",
 282         "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa"
 283     };
 284     static const char *inputs[6] = {
 285         "\x48\x69\x20\x54\x68\x65\x72\x65",
 286         "\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",
 287         "\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",
 288         "\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",
 289         "\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",
 290         "\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"
 291     };
 292     static const unsigned char outputs[6][32] = {
 293         {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},
 294         {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},
 295         {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},
 296         {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},
 297         {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},
 298         {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}
 299     };
 300     int i;
 301     for (i = 0; i < 6; i++) {
 302         secp256k1_hmac_sha256_t hasher;
 303         unsigned char out[32];
 304         secp256k1_hmac_sha256_initialize(&hasher, (const unsigned char*)(keys[i]), strlen(keys[i]));
 305         secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i]), strlen(inputs[i]));
 306         secp256k1_hmac_sha256_finalize(&hasher, out);
 307         CHECK(memcmp(out, outputs[i], 32) == 0);
 308         if (strlen(inputs[i]) > 0) {
 309             int split = secp256k1_rand_int(strlen(inputs[i]));
 310             secp256k1_hmac_sha256_initialize(&hasher, (const unsigned char*)(keys[i]), strlen(keys[i]));
 311             secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i]), split);
 312             secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i] + split), strlen(inputs[i]) - split);
 313             secp256k1_hmac_sha256_finalize(&hasher, out);
 314             CHECK(memcmp(out, outputs[i], 32) == 0);
 315         }
 316     }
 317 }
 318
 319 void run_rfc6979_hmac_sha256_tests(void) {
 320     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};
 321     static const unsigned char out1[3][32] = {
 322         {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},
 323         {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},
 324         {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}
 325     };
 326
 327     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};
 328     static const unsigned char out2[3][32] = {
 329         {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},
 330         {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},
 331         {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}
 332     };
 333
 334     secp256k1_rfc6979_hmac_sha256_t rng;
 335     unsigned char out[32];
 336     int i;
 337
 338     secp256k1_rfc6979_hmac_sha256_initialize(&rng, key1, 64);
 339     for (i = 0; i < 3; i++) {
 340         secp256k1_rfc6979_hmac_sha256_generate(&rng, out, 32);
 341         CHECK(memcmp(out, out1[i], 32) == 0);
 342     }
 343     secp256k1_rfc6979_hmac_sha256_finalize(&rng);
 344
 345     secp256k1_rfc6979_hmac_sha256_initialize(&rng, key1, 65);
 346     for (i = 0; i < 3; i++) {
 347         secp256k1_rfc6979_hmac_sha256_generate(&rng, out, 32);
 348         CHECK(memcmp(out, out1[i], 32) != 0);
 349     }
 350     secp256k1_rfc6979_hmac_sha256_finalize(&rng);
 351
 352     secp256k1_rfc6979_hmac_sha256_initialize(&rng, key2, 64);
 353     for (i = 0; i < 3; i++) {
 354         secp256k1_rfc6979_hmac_sha256_generate(&rng, out, 32);
 355         CHECK(memcmp(out, out2[i], 32) == 0);
 356     }
 357     secp256k1_rfc6979_hmac_sha256_finalize(&rng);
 358 }
 359
 360 /***** RANDOM TESTS *****/
 361
 362 void test_rand_bits(int rand32, int bits) {
 363     /* (1-1/2^B)^rounds[B] < 1/10^9, so rounds is the number of iterations to
 364      * get a false negative chance below once in a billion */
 365     static const unsigned int rounds[7] = {1, 30, 73, 156, 322, 653, 1316};
 366     /* We try multiplying the results with various odd numbers, which shouldn't
 367      * influence the uniform distribution modulo a power of 2. */
 368     static const uint32_t mults[6] = {1, 3, 21, 289, 0x9999, 0x80402011};
 369     /* We only select up to 6 bits from the output to analyse */
 370     unsigned int usebits = bits > 6 ? 6 : bits;
 371     unsigned int maxshift = bits - usebits;
 372     /* For each of the maxshift+1 usebits-bit sequences inside a bits-bit
 373        number, track all observed outcomes, one per bit in a uint64_t. */
 374     uint64_t x[6][27] = {{0}};
 375     unsigned int i, shift, m;
 376     /* Multiply the output of all rand calls with the odd number m, which
 377        should not change the uniformity of its distribution. */
 378     for (i = 0; i < rounds[usebits]; i++) {
 379         uint32_t r = (rand32 ? secp256k1_rand32() : secp256k1_rand_bits(bits));
 380         CHECK((((uint64_t)r) >> bits) == 0);
 381         for (m = 0; m < sizeof(mults) / sizeof(mults[0]); m++) {
 382             uint32_t rm = r * mults[m];
 383             for (shift = 0; shift <= maxshift; shift++) {
 384                 x[m][shift] |= (((uint64_t)1) << ((rm >> shift) & ((1 << usebits) - 1)));
 385             }
 386         }
 387     }
 388     for (m = 0; m < sizeof(mults) / sizeof(mults[0]); m++) {
 389         for (shift = 0; shift <= maxshift; shift++) {
 390             /* Test that the lower usebits bits of x[shift] are 1 */
 391             CHECK(((~x[m][shift]) << (64 - (1 << usebits))) == 0);
 392         }
 393     }
 394 }
 395
 396 /* Subrange must be a whole divisor of range, and at most 64 */
 397 void test_rand_int(uint32_t range, uint32_t subrange) {
 398     /* (1-1/subrange)^rounds < 1/10^9 */
 399     int rounds = (subrange * 2073) / 100;
 400     int i;
 401     uint64_t x = 0;
 402     CHECK((range % subrange) == 0);
 403     for (i = 0; i < rounds; i++) {
 404         uint32_t r = secp256k1_rand_int(range);
 405         CHECK(r < range);
 406         r = r % subrange;
 407         x |= (((uint64_t)1) << r);
 408     }
 409     /* Test that the lower subrange bits of x are 1. */
 410     CHECK(((~x) << (64 - subrange)) == 0);
 411 }
 412
 413 void run_rand_bits(void) {
 414     size_t b;
 415     test_rand_bits(1, 32);
 416     for (b = 1; b <= 32; b++) {
 417         test_rand_bits(0, b);
 418     }
 419 }
 420
 421 void run_rand_int(void) {
 422     static const uint32_t ms[] = {1, 3, 17, 1000, 13771, 999999, 33554432};
 423     static const uint32_t ss[] = {1, 3, 6, 9, 13, 31, 64};
 424     unsigned int m, s;
 425     for (m = 0; m < sizeof(ms) / sizeof(ms[0]); m++) {
 426         for (s = 0; s < sizeof(ss) / sizeof(ss[0]); s++) {
 427             test_rand_int(ms[m] * ss[s], ss[s]);
 428         }
 429     }
 430 }
 431
 432 /***** NUM TESTS *****/
 433
 434 #ifndef USE_NUM_NONE
 435 void random_num_negate(secp256k1_num *num) {
 436     if (secp256k1_rand_bits(1)) {
 437         secp256k1_num_negate(num);
 438     }
 439 }
 440
 441 void random_num_order_test(secp256k1_num *num) {
 442     secp256k1_scalar sc;
 443     random_scalar_order_test(&sc);
 444     secp256k1_scalar_get_num(num, &sc);
 445 }
 446
 447 void random_num_order(secp256k1_num *num) {
 448     secp256k1_scalar sc;
 449     random_scalar_order(&sc);
 450     secp256k1_scalar_get_num(num, &sc);
 451 }
 452
 453 void test_num_negate(void) {
 454     secp256k1_num n1;
 455     secp256k1_num n2;
 456     random_num_order_test(&n1); /* n1 = R */
 457     random_num_negate(&n1);
 458     secp256k1_num_copy(&n2, &n1); /* n2 = R */
 459     secp256k1_num_sub(&n1, &n2, &n1); /* n1 = n2-n1 = 0 */
 460     CHECK(secp256k1_num_is_zero(&n1));
 461     secp256k1_num_copy(&n1, &n2); /* n1 = R */
 462     secp256k1_num_negate(&n1); /* n1 = -R */
 463     CHECK(!secp256k1_num_is_zero(&n1));
 464     secp256k1_num_add(&n1, &n2, &n1); /* n1 = n2+n1 = 0 */
 465     CHECK(secp256k1_num_is_zero(&n1));
 466     secp256k1_num_copy(&n1, &n2); /* n1 = R */
 467     secp256k1_num_negate(&n1); /* n1 = -R */
 468     CHECK(secp256k1_num_is_neg(&n1) != secp256k1_num_is_neg(&n2));
 469     secp256k1_num_negate(&n1); /* n1 = R */
 470     CHECK(secp256k1_num_eq(&n1, &n2));
 471 }
 472
 473 void test_num_add_sub(void) {
 474     secp256k1_num n1;
 475     secp256k1_num n2;
 476     secp256k1_num n1p2, n2p1, n1m2, n2m1;
 477     random_num_order_test(&n1); /* n1 = R1 */
 478     if (secp256k1_rand_bits(1)) {
 479         random_num_negate(&n1);
 480     }
 481     random_num_order_test(&n2); /* n2 = R2 */
 482     if (secp256k1_rand_bits(1)) {
 483         random_num_negate(&n2);
 484     }
 485     secp256k1_num_add(&n1p2, &n1, &n2); /* n1p2 = R1 + R2 */
 486     secp256k1_num_add(&n2p1, &n2, &n1); /* n2p1 = R2 + R1 */
 487     secp256k1_num_sub(&n1m2, &n1, &n2); /* n1m2 = R1 - R2 */
 488     secp256k1_num_sub(&n2m1, &n2, &n1); /* n2m1 = R2 - R1 */
 489     CHECK(secp256k1_num_eq(&n1p2, &n2p1));
 490     CHECK(!secp256k1_num_eq(&n1p2, &n1m2));
 491     secp256k1_num_negate(&n2m1); /* n2m1 = -R2 + R1 */
 492     CHECK(secp256k1_num_eq(&n2m1, &n1m2));
 493     CHECK(!secp256k1_num_eq(&n2m1, &n1));
 494     secp256k1_num_add(&n2m1, &n2m1, &n2); /* n2m1 = -R2 + R1 + R2 = R1 */
 495     CHECK(secp256k1_num_eq(&n2m1, &n1));
 496     CHECK(!secp256k1_num_eq(&n2p1, &n1));
 497     secp256k1_num_sub(&n2p1, &n2p1, &n2); /* n2p1 = R2 + R1 - R2 = R1 */
 498     CHECK(secp256k1_num_eq(&n2p1, &n1));
 499 }
 500
 501 void run_num_smalltests(void) {
 502     int i;
 503     for (i = 0; i < 100*count; i++) {
 504         test_num_negate();
 505         test_num_add_sub();
 506     }
 507 }
 508 #endif
 509
 510 /***** SCALAR TESTS *****/
 511
 512 void scalar_test(void) {
 513     secp256k1_scalar s;
 514     secp256k1_scalar s1;
 515     secp256k1_scalar s2;
 516 #ifndef USE_NUM_NONE
 517     secp256k1_num snum, s1num, s2num;
 518     secp256k1_num order, half_order;
 519 #endif
 520     unsigned char c[32];
 521
 522     /* Set 's' to a random scalar, with value 'snum'. */
 523     random_scalar_order_test(&s);
 524
 525     /* Set 's1' to a random scalar, with value 's1num'. */
 526     random_scalar_order_test(&s1);
 527
 528     /* Set 's2' to a random scalar, with value 'snum2', and byte array representation 'c'. */
 529     random_scalar_order_test(&s2);
 530     secp256k1_scalar_get_b32(c, &s2);
 531
 532 #ifndef USE_NUM_NONE
 533     secp256k1_scalar_get_num(&snum, &s);
 534     secp256k1_scalar_get_num(&s1num, &s1);
 535     secp256k1_scalar_get_num(&s2num, &s2);
 536
 537     secp256k1_scalar_order_get_num(&order);
 538     half_order = order;
 539     secp256k1_num_shift(&half_order, 1);
 540 #endif
 541
 542     {
 543         int i;
 544         /* Test that fetching groups of 4 bits from a scalar and recursing n(i)=16*n(i-1)+p(i) reconstructs it. */
 545         secp256k1_scalar n;
 546         secp256k1_scalar_set_int(&n, 0);
 547         for (i = 0; i < 256; i += 4) {
 548             secp256k1_scalar t;
 549             int j;
 550             secp256k1_scalar_set_int(&t, secp256k1_scalar_get_bits(&s, 256 - 4 - i, 4));
 551             for (j = 0; j < 4; j++) {
 552                 secp256k1_scalar_add(&n, &n, &n);
 553             }
 554             secp256k1_scalar_add(&n, &n, &t);
 555         }
 556         CHECK(secp256k1_scalar_eq(&n, &s));
 557     }
 558
 559     {
 560         /* Test that fetching groups of randomly-sized bits from a scalar and recursing n(i)=b*n(i-1)+p(i) reconstructs it. */
 561         secp256k1_scalar n;
 562         int i = 0;
 563         secp256k1_scalar_set_int(&n, 0);
 564         while (i < 256) {
 565             secp256k1_scalar t;
 566             int j;
 567             int now = secp256k1_rand_int(15) + 1;
 568             if (now + i > 256) {
 569                 now = 256 - i;
 570             }
 571             secp256k1_scalar_set_int(&t, secp256k1_scalar_get_bits_var(&s, 256 - now - i, now));
 572             for (j = 0; j < now; j++) {
 573                 secp256k1_scalar_add(&n, &n, &n);
 574             }
 575             secp256k1_scalar_add(&n, &n, &t);
 576             i += now;
 577         }
 578         CHECK(secp256k1_scalar_eq(&n, &s));
 579     }
 580
 581 #ifndef USE_NUM_NONE
 582     {
 583         /* Test that adding the scalars together is equal to adding their numbers together modulo the order. */
 584         secp256k1_num rnum;
 585         secp256k1_num r2num;
 586         secp256k1_scalar r;
 587         secp256k1_num_add(&rnum, &snum, &s2num);
 588         secp256k1_num_mod(&rnum, &order);
 589         secp256k1_scalar_add(&r, &s, &s2);
 590         secp256k1_scalar_get_num(&r2num, &r);
 591         CHECK(secp256k1_num_eq(&rnum, &r2num));
 592     }
 593
 594     {
 595         /* Test that multipying the scalars is equal to multiplying their numbers modulo the order. */
 596         secp256k1_scalar r;
 597         secp256k1_num r2num;
 598         secp256k1_num rnum;
 599         secp256k1_num_mul(&rnum, &snum, &s2num);
 600         secp256k1_num_mod(&rnum, &order);
 601         secp256k1_scalar_mul(&r, &s, &s2);
 602         secp256k1_scalar_get_num(&r2num, &r);
 603         CHECK(secp256k1_num_eq(&rnum, &r2num));
 604         /* The result can only be zero if at least one of the factors was zero. */
 605         CHECK(secp256k1_scalar_is_zero(&r) == (secp256k1_scalar_is_zero(&s) || secp256k1_scalar_is_zero(&s2)));
 606         /* The results can only be equal to one of the factors if that factor was zero, or the other factor was one. */
 607         CHECK(secp256k1_num_eq(&rnum, &snum) == (secp256k1_scalar_is_zero(&s) || secp256k1_scalar_is_one(&s2)));
 608         CHECK(secp256k1_num_eq(&rnum, &s2num) == (secp256k1_scalar_is_zero(&s2) || secp256k1_scalar_is_one(&s)));
 609     }
 610
 611     {
 612         secp256k1_scalar neg;
 613         secp256k1_num negnum;
 614         secp256k1_num negnum2;
 615         /* Check that comparison with zero matches comparison with zero on the number. */
 616         CHECK(secp256k1_num_is_zero(&snum) == secp256k1_scalar_is_zero(&s));
 617         /* Check that comparison with the half order is equal to testing for high scalar. */
 618         CHECK(secp256k1_scalar_is_high(&s) == (secp256k1_num_cmp(&snum, &half_order) > 0));
 619         secp256k1_scalar_negate(&neg, &s);
 620         secp256k1_num_sub(&negnum, &order, &snum);
 621         secp256k1_num_mod(&negnum, &order);
 622         /* Check that comparison with the half order is equal to testing for high scalar after negation. */
 623         CHECK(secp256k1_scalar_is_high(&neg) == (secp256k1_num_cmp(&negnum, &half_order) > 0));
 624         /* Negating should change the high property, unless the value was already zero. */
 625         CHECK((secp256k1_scalar_is_high(&s) == secp256k1_scalar_is_high(&neg)) == secp256k1_scalar_is_zero(&s));
 626         secp256k1_scalar_get_num(&negnum2, &neg);
 627         /* Negating a scalar should be equal to (order - n) mod order on the number. */
 628         CHECK(secp256k1_num_eq(&negnum, &negnum2));
 629         secp256k1_scalar_add(&neg, &neg, &s);
 630         /* Adding a number to its negation should result in zero. */
 631         CHECK(secp256k1_scalar_is_zero(&neg));
 632         secp256k1_scalar_negate(&neg, &neg);
 633         /* Negating zero should still result in zero. */
 634         CHECK(secp256k1_scalar_is_zero(&neg));
 635     }
 636
 637     {
 638         /* Test secp256k1_scalar_mul_shift_var. */
 639         secp256k1_scalar r;
 640         secp256k1_num one;
 641         secp256k1_num rnum;
 642         secp256k1_num rnum2;
 643         unsigned char cone[1] = {0x01};
 644         unsigned int shift = 256 + secp256k1_rand_int(257);
 645         secp256k1_scalar_mul_shift_var(&r, &s1, &s2, shift);
 646         secp256k1_num_mul(&rnum, &s1num, &s2num);
 647         secp256k1_num_shift(&rnum, shift - 1);
 648         secp256k1_num_set_bin(&one, cone, 1);
 649         secp256k1_num_add(&rnum, &rnum, &one);
 650         secp256k1_num_shift(&rnum, 1);
 651         secp256k1_scalar_get_num(&rnum2, &r);
 652         CHECK(secp256k1_num_eq(&rnum, &rnum2));
 653     }
 654
 655     {
 656         /* test secp256k1_scalar_shr_int */
 657         secp256k1_scalar r;
 658         int i;
 659         random_scalar_order_test(&r);
 660         for (i = 0; i < 100; ++i) {
 661             int low;
 662             int shift = 1 + secp256k1_rand_int(15);
 663             int expected = r.d[0] % (1 << shift);
 664             low = secp256k1_scalar_shr_int(&r, shift);
 665             CHECK(expected == low);
 666         }
 667     }
 668 #endif
 669
 670     {
 671         /* Test that scalar inverses are equal to the inverse of their number modulo the order. */
 672         if (!secp256k1_scalar_is_zero(&s)) {
 673             secp256k1_scalar inv;
 674 #ifndef USE_NUM_NONE
 675             secp256k1_num invnum;
 676             secp256k1_num invnum2;
 677 #endif
 678             secp256k1_scalar_inverse(&inv, &s);
 679 #ifndef USE_NUM_NONE
 680             secp256k1_num_mod_inverse(&invnum, &snum, &order);
 681             secp256k1_scalar_get_num(&invnum2, &inv);
 682             CHECK(secp256k1_num_eq(&invnum, &invnum2));
 683 #endif
 684             secp256k1_scalar_mul(&inv, &inv, &s);
 685             /* Multiplying a scalar with its inverse must result in one. */
 686             CHECK(secp256k1_scalar_is_one(&inv));
 687             secp256k1_scalar_inverse(&inv, &inv);
 688             /* Inverting one must result in one. */
 689             CHECK(secp256k1_scalar_is_one(&inv));
 690         }
 691     }
 692
 693     {
 694         /* Test commutativity of add. */
 695         secp256k1_scalar r1, r2;
 696         secp256k1_scalar_add(&r1, &s1, &s2);
 697         secp256k1_scalar_add(&r2, &s2, &s1);
 698         CHECK(secp256k1_scalar_eq(&r1, &r2));
 699     }
 700
 701     {
 702         secp256k1_scalar r1, r2;
 703         secp256k1_scalar b;
 704         int i;
 705         /* Test add_bit. */
 706         int bit = secp256k1_rand_bits(8);
 707         secp256k1_scalar_set_int(&b, 1);
 708         CHECK(secp256k1_scalar_is_one(&b));
 709         for (i = 0; i < bit; i++) {
 710             secp256k1_scalar_add(&b, &b, &b);
 711         }
 712         r1 = s1;
 713         r2 = s1;
 714         if (!secp256k1_scalar_add(&r1, &r1, &b)) {
 715             /* No overflow happened. */
 716             secp256k1_scalar_cadd_bit(&r2, bit, 1);
 717             CHECK(secp256k1_scalar_eq(&r1, &r2));
 718             /* cadd is a noop when flag is zero */
 719             secp256k1_scalar_cadd_bit(&r2, bit, 0);
 720             CHECK(secp256k1_scalar_eq(&r1, &r2));
 721         }
 722     }
 723
 724     {
 725         /* Test commutativity of mul. */
 726         secp256k1_scalar r1, r2;
 727         secp256k1_scalar_mul(&r1, &s1, &s2);
 728         secp256k1_scalar_mul(&r2, &s2, &s1);
 729         CHECK(secp256k1_scalar_eq(&r1, &r2));
 730     }
 731
 732     {
 733         /* Test associativity of add. */
 734         secp256k1_scalar r1, r2;
 735         secp256k1_scalar_add(&r1, &s1, &s2);
 736         secp256k1_scalar_add(&r1, &r1, &s);
 737         secp256k1_scalar_add(&r2, &s2, &s);
 738         secp256k1_scalar_add(&r2, &s1, &r2);
 739         CHECK(secp256k1_scalar_eq(&r1, &r2));
 740     }
 741
 742     {
 743         /* Test associativity of mul. */
 744         secp256k1_scalar r1, r2;
 745         secp256k1_scalar_mul(&r1, &s1, &s2);
 746         secp256k1_scalar_mul(&r1, &r1, &s);
 747         secp256k1_scalar_mul(&r2, &s2, &s);
 748         secp256k1_scalar_mul(&r2, &s1, &r2);
 749         CHECK(secp256k1_scalar_eq(&r1, &r2));
 750     }
 751
 752     {
 753         /* Test distributitivity of mul over add. */
 754         secp256k1_scalar r1, r2, t;
 755         secp256k1_scalar_add(&r1, &s1, &s2);
 756         secp256k1_scalar_mul(&r1, &r1, &s);
 757         secp256k1_scalar_mul(&r2, &s1, &s);
 758         secp256k1_scalar_mul(&t, &s2, &s);
 759         secp256k1_scalar_add(&r2, &r2, &t);
 760         CHECK(secp256k1_scalar_eq(&r1, &r2));
 761     }
 762
 763     {
 764         /* Test square. */
 765         secp256k1_scalar r1, r2;
 766         secp256k1_scalar_sqr(&r1, &s1);
 767         secp256k1_scalar_mul(&r2, &s1, &s1);
 768         CHECK(secp256k1_scalar_eq(&r1, &r2));
 769     }
 770
 771     {
 772         /* Test multiplicative identity. */
 773         secp256k1_scalar r1, v1;
 774         secp256k1_scalar_set_int(&v1,1);
 775         secp256k1_scalar_mul(&r1, &s1, &v1);
 776         CHECK(secp256k1_scalar_eq(&r1, &s1));
 777     }
 778
 779     {
 780         /* Test additive identity. */
 781         secp256k1_scalar r1, v0;
 782         secp256k1_scalar_set_int(&v0,0);
 783         secp256k1_scalar_add(&r1, &s1, &v0);
 784         CHECK(secp256k1_scalar_eq(&r1, &s1));
 785     }
 786
 787     {
 788         /* Test zero product property. */
 789         secp256k1_scalar r1, v0;
 790         secp256k1_scalar_set_int(&v0,0);
 791         secp256k1_scalar_mul(&r1, &s1, &v0);
 792         CHECK(secp256k1_scalar_eq(&r1, &v0));
 793     }
 794
 795 }
 796
 797 void run_scalar_tests(void) {
 798     int i;
 799     for (i = 0; i < 128 * count; i++) {
 800         scalar_test();
 801     }
 802
 803     {
 804         /* (-1)+1 should be zero. */
 805         secp256k1_scalar s, o;
 806         secp256k1_scalar_set_int(&s, 1);
 807         CHECK(secp256k1_scalar_is_one(&s));
 808         secp256k1_scalar_negate(&o, &s);
 809         secp256k1_scalar_add(&o, &o, &s);
 810         CHECK(secp256k1_scalar_is_zero(&o));
 811         secp256k1_scalar_negate(&o, &o);
 812         CHECK(secp256k1_scalar_is_zero(&o));
 813     }
 814
 815 #ifndef USE_NUM_NONE
 816     {
 817         /* A scalar with value of the curve order should be 0. */
 818         secp256k1_num order;
 819         secp256k1_scalar zero;
 820         unsigned char bin[32];
 821         int overflow = 0;
 822         secp256k1_scalar_order_get_num(&order);
 823         secp256k1_num_get_bin(bin, 32, &order);
 824         secp256k1_scalar_set_b32(&zero, bin, &overflow);
 825         CHECK(overflow == 1);
 826         CHECK(secp256k1_scalar_is_zero(&zero));
 827     }
 828 #endif
 829
 830     {
 831         /* Does check_overflow check catch all ones? */
 832         static const secp256k1_scalar overflowed = SECP256K1_SCALAR_CONST(
 833             0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL,
 834             0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL
 835         );
 836         CHECK(secp256k1_scalar_check_overflow(&overflowed));
 837     }
 838
 839     {
 840         /* Static test vectors.
 841          * These were reduced from ~10^12 random vectors based on comparision-decision
 842          *  and edge-case coverage on 32-bit and 64-bit implementations.
 843          * The responses were generated with Sage 5.9.
 844          */
 845         secp256k1_scalar x;
 846         secp256k1_scalar y;
 847         secp256k1_scalar z;
 848         secp256k1_scalar zz;
 849         secp256k1_scalar one;
 850         secp256k1_scalar r1;
 851         secp256k1_scalar r2;
 852 #if defined(USE_SCALAR_INV_NUM)
 853         secp256k1_scalar zzv;
 854 #endif
 855         int overflow;
 856         unsigned char chal[32][2][32] = {
 857             {{0xff, 0xff, 0x03, 0x07, 0x00, 0x00, 0x00, 0x00,
 858               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x03,
 859               0x00, 0x00, 0x00, 0x00, 0x00, 0xf8, 0xff, 0xff,
 860               0xff, 0xff, 0x03, 0x00, 0xc0, 0xff, 0xff, 0xff},
 861              {0xff, 0xff, 0xff, 0xff, 0xff, 0x0f, 0x00, 0x00,
 862               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xf8,
 863               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 864               0xff, 0x03, 0x00, 0x00, 0x00, 0x00, 0xe0, 0xff}},
 865             {{0xef, 0xff, 0x1f, 0x00, 0x00, 0x00, 0x00, 0x00,
 866               0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3f, 0x00,
 867               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 868               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00},
 869              {0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
 870               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xe0,
 871               0xff, 0xff, 0xff, 0xff, 0xfc, 0xff, 0xff, 0xff,
 872               0xff, 0xff, 0xff, 0xff, 0x7f, 0x00, 0x80, 0xff}},
 873             {{0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
 874               0x00, 0x00, 0x00, 0x00, 0x00, 0x06, 0x00, 0x00,
 875               0x80, 0x00, 0x00, 0x80, 0xff, 0x3f, 0x00, 0x00,
 876               0x00, 0x00, 0x00, 0xf8, 0xff, 0xff, 0xff, 0x00},
 877              {0x00, 0x00, 0xfc, 0xff, 0xff, 0xff, 0xff, 0x80,
 878               0xff, 0xff, 0xff, 0xff, 0xff, 0x0f, 0x00, 0xe0,
 879               0xff, 0xff, 0xff, 0xff, 0xff, 0x7f, 0x00, 0x00,
 880               0x00, 0x00, 0x00, 0x00, 0x7f, 0xff, 0xff, 0xff}},
 881             {{0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
 882               0x00, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x80,
 883               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
 884               0x00, 0x1e, 0xf8, 0xff, 0xff, 0xff, 0xfd, 0xff},
 885              {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x1f,
 886               0x00, 0x00, 0x00, 0xf8, 0xff, 0x03, 0x00, 0xe0,
 887               0xff, 0x0f, 0x00, 0x00, 0x00, 0x00, 0xf0, 0xff,
 888               0xf3, 0xff, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00}},
 889             {{0x80, 0x00, 0x00, 0x80, 0xff, 0xff, 0xff, 0x00,
 890               0x00, 0x1c, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff,
 891               0xff, 0xff, 0xff, 0xe0, 0xff, 0xff, 0xff, 0x00,
 892               0x00, 0x00, 0x00, 0x00, 0xe0, 0xff, 0xff, 0xff},
 893              {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x03, 0x00,
 894               0xf8, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 895               0xff, 0x1f, 0x00, 0x00, 0x80, 0xff, 0xff, 0x3f,
 896               0x00, 0xfe, 0xff, 0xff, 0xff, 0xdf, 0xff, 0xff}},
 897             {{0xff, 0xff, 0xff, 0xff, 0x00, 0x0f, 0xfc, 0x9f,
 898               0xff, 0xff, 0xff, 0x00, 0x80, 0x00, 0x00, 0x80,
 899               0xff, 0x0f, 0xfc, 0xff, 0x7f, 0x00, 0x00, 0x00,
 900               0x00, 0xf8, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00},
 901              {0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80,
 902               0x00, 0x00, 0xf8, 0xff, 0x0f, 0xc0, 0xff, 0xff,
 903               0xff, 0x1f, 0x00, 0x00, 0x00, 0xc0, 0xff, 0xff,
 904               0xff, 0xff, 0xff, 0x07, 0x80, 0xff, 0xff, 0xff}},
 905             {{0xff, 0xff, 0xff, 0xff, 0xff, 0x3f, 0x00, 0x00,
 906               0x80, 0x00, 0x00, 0x80, 0xff, 0xff, 0xff, 0xff,
 907               0xf7, 0xff, 0xff, 0xef, 0xff, 0xff, 0xff, 0x00,
 908               0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0xf0},
 909              {0x00, 0x00, 0x00, 0x00, 0xf8, 0xff, 0xff, 0xff,
 910               0xff, 0xff, 0xff, 0xff, 0x01, 0x00, 0x00, 0x00,
 911               0x00, 0x00, 0x80, 0xff, 0xff, 0xff, 0xff, 0xff,
 912               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}},
 913             {{0x00, 0xf8, 0xff, 0x03, 0xff, 0xff, 0xff, 0x00,
 914               0x00, 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
 915               0x80, 0x00, 0x00, 0x80, 0xff, 0xff, 0xff, 0xff,
 916               0xff, 0xff, 0x03, 0xc0, 0xff, 0x0f, 0xfc, 0xff},
 917              {0xff, 0xff, 0xff, 0xff, 0xff, 0xe0, 0xff, 0xff,
 918               0xff, 0x01, 0x00, 0x00, 0x00, 0x3f, 0x00, 0xc0,
 919               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 920               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}},
 921             {{0x8f, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 922               0x00, 0x00, 0xf8, 0xff, 0xff, 0xff, 0xff, 0xff,
 923               0xff, 0x7f, 0x00, 0x00, 0x80, 0x00, 0x00, 0x80,
 924               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00},
 925              {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 926               0xff, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 927               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 928               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}},
 929             {{0x00, 0x00, 0x00, 0xc0, 0xff, 0xff, 0xff, 0xff,
 930               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 931               0xff, 0xff, 0x03, 0x00, 0x80, 0x00, 0x00, 0x80,
 932               0xff, 0xff, 0xff, 0x00, 0x00, 0x80, 0xff, 0x7f},
 933              {0xff, 0xcf, 0xff, 0xff, 0x01, 0x00, 0x00, 0x00,
 934               0x00, 0xc0, 0xff, 0xcf, 0xff, 0xff, 0xff, 0xff,
 935               0xbf, 0xff, 0x0e, 0x00, 0x00, 0x00, 0x00, 0x00,
 936               0x80, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00}},
 937             {{0x00, 0x00, 0x00, 0x00, 0x00, 0x80, 0xff, 0xff,
 938               0xff, 0xff, 0x00, 0xfc, 0xff, 0xff, 0xff, 0xff,
 939               0xff, 0xff, 0xff, 0x00, 0x80, 0x00, 0x00, 0x80,
 940               0xff, 0x01, 0xfc, 0xff, 0x01, 0x00, 0xfe, 0xff},
 941              {0xff, 0xff, 0xff, 0x03, 0x00, 0x00, 0x00, 0x00,
 942               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 943               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xc0,
 944               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x03, 0x00}},
 945             {{0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
 946               0xe0, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 947               0x00, 0xf8, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 948               0x7f, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x80},
 949              {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 950               0x00, 0xf8, 0xff, 0x01, 0x00, 0xf0, 0xff, 0xff,
 951               0xe0, 0xff, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x00,
 952               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}},
 953             {{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 954               0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 955               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 956               0x00, 0x00, 0x00, 0x00, 0x00, 0xf8, 0xff, 0x00},
 957              {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00,
 958               0xfc, 0xff, 0xff, 0x3f, 0xf0, 0xff, 0xff, 0x3f,
 959               0x00, 0x00, 0xf8, 0x07, 0x00, 0x00, 0x00, 0xff,
 960               0xff, 0xff, 0xff, 0xff, 0x0f, 0x7e, 0x00, 0x00}},
 961             {{0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
 962               0x00, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x80,
 963               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 964               0xff, 0xff, 0x1f, 0x00, 0x00, 0xfe, 0x07, 0x00},
 965              {0x00, 0x00, 0x00, 0xf0, 0xff, 0xff, 0xff, 0xff,
 966               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 967               0xff, 0xfb, 0xff, 0x07, 0x00, 0x00, 0x00, 0x00,
 968               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x60}},
 969             {{0xff, 0x01, 0x00, 0xff, 0xff, 0xff, 0x0f, 0x00,
 970               0x80, 0x7f, 0xfe, 0xff, 0xff, 0xff, 0xff, 0x03,
 971               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 972               0x00, 0x80, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff},
 973              {0xff, 0xff, 0x1f, 0x00, 0xf0, 0xff, 0xff, 0xff,
 974               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 975               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 976               0xff, 0xff, 0xff, 0x3f, 0x00, 0x00, 0x00, 0x00}},
 977             {{0x80, 0x00, 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
 978               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 979               0xff, 0xff, 0xff, 0xff, 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, 0xf1, 0xff,
 983               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x03,
 984               0x00, 0x00, 0x00, 0xe0, 0xff, 0xff, 0xff, 0xff}},
 985             {{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
 986               0x7e, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 987               0xc0, 0xff, 0xff, 0xcf, 0xff, 0x1f, 0x00, 0x00,
 988               0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80},
 989              {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 990               0x00, 0x00, 0x00, 0x00, 0x00, 0xe0, 0xff, 0xff,
 991               0xff, 0xff, 0xff, 0xff, 0xff, 0x3f, 0x00, 0x7e,
 992               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}},
 993             {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 994               0x00, 0x00, 0x00, 0xfc, 0xff, 0xff, 0xff, 0xff,
 995               0xff, 0xff, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00,
 996               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x7c, 0x00},
 997              {0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80,
 998               0xff, 0xff, 0x7f, 0x00, 0x80, 0x00, 0x00, 0x00,
 999               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
1000               0x00, 0x00, 0xe0, 0xff, 0xff, 0xff, 0xff, 0xff}},
1001             {{0xff, 0xff, 0xff, 0xff, 0xff, 0x1f, 0x00, 0x80,
1002               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
1003               0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80,
1004               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00},
1005              {0xf0, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1006               0xff, 0xff, 0xff, 0xff, 0x3f, 0x00, 0x00, 0x80,
1007               0xff, 0x01, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff,
1008               0xff, 0x7f, 0xf8, 0xff, 0xff, 0x1f, 0x00, 0xfe}},
1009             {{0xff, 0xff, 0xff, 0x3f, 0xf8, 0xff, 0xff, 0xff,
1010               0xff, 0x03, 0xfe, 0x01, 0x00, 0x00, 0x00, 0x00,
1011               0xf0, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1012               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x07},
1013              {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
1014               0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80,
1015               0xff, 0xff, 0xff, 0xff, 0x01, 0x80, 0xff, 0xff,
1016               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00}},
1017             {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1018               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1019               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1020               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00},
1021              {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1022               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
1023               0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
1024               0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x40}},
1025             {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1026               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1027               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1028               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01},
1029              {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1030               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1031               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1032               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}},
1033             {{0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1034               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1035               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1036               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff},
1037              {0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1038               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1039               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1040               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}},
1041             {{0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0xc0,
1042               0xff, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1043               0x00, 0x00, 0xf0, 0xff, 0xff, 0xff, 0xff, 0xff,
1044               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f},
1045              {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01, 0x00,
1046               0xf0, 0xff, 0xff, 0xff, 0xff, 0x07, 0x00, 0x00,
1047               0x00, 0x00, 0x00, 0xfe, 0xff, 0xff, 0xff, 0xff,
1048               0xff, 0xff, 0xff, 0xff, 0x01, 0xff, 0xff, 0xff}},
1049             {{0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1050               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1051               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1052               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff},
1053              {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1054               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1055               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1056               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02}},
1057             {{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1058               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
1059               0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
1060               0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x40},
1061              {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1062               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1063               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1064               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01}},
1065             {{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1066               0x7e, 0x00, 0x00, 0xc0, 0xff, 0xff, 0x07, 0x00,
1067               0x80, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x00,
1068               0xfc, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff},
1069              {0xff, 0x01, 0x00, 0x00, 0x00, 0xe0, 0xff, 0xff,
1070               0xff, 0xff, 0xff, 0xff, 0xff, 0x1f, 0x00, 0x80,
1071               0xff, 0xff, 0xff, 0xff, 0xff, 0x03, 0x00, 0x00,
1072               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}},
1073             {{0xff, 0xff, 0xf0, 0xff, 0xff, 0xff, 0xff, 0x00,
1074               0xf0, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
1075               0x00, 0xe0, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01,
1076               0x80, 0x00, 0x00, 0x80, 0xff, 0xff, 0xff, 0xff},
1077              {0x00, 0x00, 0x00, 0x00, 0x00, 0xe0, 0xff, 0xff,
1078               0xff, 0xff, 0x3f, 0x00, 0xf8, 0xff, 0xff, 0xff,
1079               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1080               0xff, 0x3f, 0x00, 0x00, 0xc0, 0xf1, 0x7f, 0x00}},
1081             {{0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
1082               0x00, 0x00, 0x00, 0xc0, 0xff, 0xff, 0xff, 0xff,
1083               0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00,
1084               0x80, 0x00, 0x00, 0x80, 0xff, 0xff, 0xff, 0x00},
1085              {0x00, 0xf8, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01,
1086               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xf8, 0xff,
1087               0xff, 0x7f, 0x00, 0x00, 0x00, 0x00, 0x80, 0x1f,
1088               0x00, 0x00, 0xfc, 0xff, 0xff, 0x01, 0xff, 0xff}},
1089             {{0x00, 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
1090               0x80, 0x00, 0x00, 0x80, 0xff, 0x03, 0xe0, 0x01,
1091               0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0xfc, 0xff,
1092               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00},
1093              {0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
1094               0xfe, 0xff, 0xff, 0xf0, 0x07, 0x00, 0x3c, 0x80,
1095               0xff, 0xff, 0xff, 0xff, 0xfc, 0xff, 0xff, 0xff,
1096               0xff, 0xff, 0x07, 0xe0, 0xff, 0x00, 0x00, 0x00}},
1097             {{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00,
1098               0xfc, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1099               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x07, 0xf8,
1100               0x00, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x80},
1101              {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1102               0xff, 0xff, 0xff, 0xff, 0xff, 0x0c, 0x80, 0x00,
1103               0x00, 0x00, 0x00, 0xc0, 0x7f, 0xfe, 0xff, 0x1f,
1104               0x00, 0xfe, 0xff, 0x03, 0x00, 0x00, 0xfe, 0xff}},
1105             {{0xff, 0xff, 0x81, 0xff, 0xff, 0xff, 0xff, 0x00,
1106               0x80, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x83,
1107               0xff, 0xff, 0x00, 0x00, 0x80, 0x00, 0x00, 0x80,
1108               0xff, 0xff, 0x7f, 0x00, 0x00, 0x00, 0x00, 0xf0},
1109              {0xff, 0x01, 0x00, 0x00, 0x00, 0x00, 0xf8, 0xff,
1110               0xff, 0xff, 0xff, 0xff, 0xff, 0x1f, 0x00, 0x00,
1111               0xf8, 0x07, 0x00, 0x80, 0xff, 0xff, 0xff, 0xff,
1112               0xff, 0xc7, 0xff, 0xff, 0xe0, 0xff, 0xff, 0xff}}
1113         };
1114         unsigned char res[32][2][32] = {
1115             {{0x0c, 0x3b, 0x0a, 0xca, 0x8d, 0x1a, 0x2f, 0xb9,
1116               0x8a, 0x7b, 0x53, 0x5a, 0x1f, 0xc5, 0x22, 0xa1,
1117               0x07, 0x2a, 0x48, 0xea, 0x02, 0xeb, 0xb3, 0xd6,
1118               0x20, 0x1e, 0x86, 0xd0, 0x95, 0xf6, 0x92, 0x35},
1119              {0xdc, 0x90, 0x7a, 0x07, 0x2e, 0x1e, 0x44, 0x6d,
1120               0xf8, 0x15, 0x24, 0x5b, 0x5a, 0x96, 0x37, 0x9c,
1121               0x37, 0x7b, 0x0d, 0xac, 0x1b, 0x65, 0x58, 0x49,
1122               0x43, 0xb7, 0x31, 0xbb, 0xa7, 0xf4, 0x97, 0x15}},
1123             {{0xf1, 0xf7, 0x3a, 0x50, 0xe6, 0x10, 0xba, 0x22,
1124               0x43, 0x4d, 0x1f, 0x1f, 0x7c, 0x27, 0xca, 0x9c,
1125               0xb8, 0xb6, 0xa0, 0xfc, 0xd8, 0xc0, 0x05, 0x2f,
1126               0xf7, 0x08, 0xe1, 0x76, 0xdd, 0xd0, 0x80, 0xc8},
1127              {0xe3, 0x80, 0x80, 0xb8, 0xdb, 0xe3, 0xa9, 0x77,
1128               0x00, 0xb0, 0xf5, 0x2e, 0x27, 0xe2, 0x68, 0xc4,
1129               0x88, 0xe8, 0x04, 0xc1, 0x12, 0xbf, 0x78, 0x59,
1130               0xe6, 0xa9, 0x7c, 0xe1, 0x81, 0xdd, 0xb9, 0xd5}},
1131             {{0x96, 0xe2, 0xee, 0x01, 0xa6, 0x80, 0x31, 0xef,
1132               0x5c, 0xd0, 0x19, 0xb4, 0x7d, 0x5f, 0x79, 0xab,
1133               0xa1, 0x97, 0xd3, 0x7e, 0x33, 0xbb, 0x86, 0x55,
1134               0x60, 0x20, 0x10, 0x0d, 0x94, 0x2d, 0x11, 0x7c},
1135              {0xcc, 0xab, 0xe0, 0xe8, 0x98, 0x65, 0x12, 0x96,
1136               0x38, 0x5a, 0x1a, 0xf2, 0x85, 0x23, 0x59, 0x5f,
1137               0xf9, 0xf3, 0xc2, 0x81, 0x70, 0x92, 0x65, 0x12,
1138               0x9c, 0x65, 0x1e, 0x96, 0x00, 0xef, 0xe7, 0x63}},
1139             {{0xac, 0x1e, 0x62, 0xc2, 0x59, 0xfc, 0x4e, 0x5c,
1140               0x83, 0xb0, 0xd0, 0x6f, 0xce, 0x19, 0xf6, 0xbf,
1141               0xa4, 0xb0, 0xe0, 0x53, 0x66, 0x1f, 0xbf, 0xc9,
1142               0x33, 0x47, 0x37, 0xa9, 0x3d, 0x5d, 0xb0, 0x48},
1143              {0x86, 0xb9, 0x2a, 0x7f, 0x8e, 0xa8, 0x60, 0x42,
1144               0x26, 0x6d, 0x6e, 0x1c, 0xa2, 0xec, 0xe0, 0xe5,
1145               0x3e, 0x0a, 0x33, 0xbb, 0x61, 0x4c, 0x9f, 0x3c,
1146               0xd1, 0xdf, 0x49, 0x33, 0xcd, 0x72, 0x78, 0x18}},
1147             {{0xf7, 0xd3, 0xcd, 0x49, 0x5c, 0x13, 0x22, 0xfb,
1148               0x2e, 0xb2, 0x2f, 0x27, 0xf5, 0x8a, 0x5d, 0x74,
1149               0xc1, 0x58, 0xc5, 0xc2, 0x2d, 0x9f, 0x52, 0xc6,
1150               0x63, 0x9f, 0xba, 0x05, 0x76, 0x45, 0x7a, 0x63},
1151              {0x8a, 0xfa, 0x55, 0x4d, 0xdd, 0xa3, 0xb2, 0xc3,
1152               0x44, 0xfd, 0xec, 0x72, 0xde, 0xef, 0xc0, 0x99,
1153               0xf5, 0x9f, 0xe2, 0x52, 0xb4, 0x05, 0x32, 0x58,
1154               0x57, 0xc1, 0x8f, 0xea, 0xc3, 0x24, 0x5b, 0x94}},
1155             {{0x05, 0x83, 0xee, 0xdd, 0x64, 0xf0, 0x14, 0x3b,
1156               0xa0, 0x14, 0x4a, 0x3a, 0x41, 0x82, 0x7c, 0xa7,
1157               0x2c, 0xaa, 0xb1, 0x76, 0xbb, 0x59, 0x64, 0x5f,
1158               0x52, 0xad, 0x25, 0x29, 0x9d, 0x8f, 0x0b, 0xb0},
1159              {0x7e, 0xe3, 0x7c, 0xca, 0xcd, 0x4f, 0xb0, 0x6d,
1160               0x7a, 0xb2, 0x3e, 0xa0, 0x08, 0xb9, 0xa8, 0x2d,
1161               0xc2, 0xf4, 0x99, 0x66, 0xcc, 0xac, 0xd8, 0xb9,
1162               0x72, 0x2a, 0x4a, 0x3e, 0x0f, 0x7b, 0xbf, 0xf4}},
1163             {{0x8c, 0x9c, 0x78, 0x2b, 0x39, 0x61, 0x7e, 0xf7,
1164               0x65, 0x37, 0x66, 0x09, 0x38, 0xb9, 0x6f, 0x70,
1165               0x78, 0x87, 0xff, 0xcf, 0x93, 0xca, 0x85, 0x06,
1166               0x44, 0x84, 0xa7, 0xfe, 0xd3, 0xa4, 0xe3, 0x7e},
1167              {0xa2, 0x56, 0x49, 0x23, 0x54, 0xa5, 0x50, 0xe9,
1168               0x5f, 0xf0, 0x4d, 0xe7, 0xdc, 0x38, 0x32, 0x79,
1169               0x4f, 0x1c, 0xb7, 0xe4, 0xbb, 0xf8, 0xbb, 0x2e,
1170               0x40, 0x41, 0x4b, 0xcc, 0xe3, 0x1e, 0x16, 0x36}},
1171             {{0x0c, 0x1e, 0xd7, 0x09, 0x25, 0x40, 0x97, 0xcb,
1172               0x5c, 0x46, 0xa8, 0xda, 0xef, 0x25, 0xd5, 0xe5,
1173               0x92, 0x4d, 0xcf, 0xa3, 0xc4, 0x5d, 0x35, 0x4a,
1174               0xe4, 0x61, 0x92, 0xf3, 0xbf, 0x0e, 0xcd, 0xbe},
1175              {0xe4, 0xaf, 0x0a, 0xb3, 0x30, 0x8b, 0x9b, 0x48,
1176               0x49, 0x43, 0xc7, 0x64, 0x60, 0x4a, 0x2b, 0x9e,
1177               0x95, 0x5f, 0x56, 0xe8, 0x35, 0xdc, 0xeb, 0xdc,
1178               0xc7, 0xc4, 0xfe, 0x30, 0x40, 0xc7, 0xbf, 0xa4}},
1179             {{0xd4, 0xa0, 0xf5, 0x81, 0x49, 0x6b, 0xb6, 0x8b,
1180               0x0a, 0x69, 0xf9, 0xfe, 0xa8, 0x32, 0xe5, 0xe0,
1181               0xa5, 0xcd, 0x02, 0x53, 0xf9, 0x2c, 0xe3, 0x53,
1182               0x83, 0x36, 0xc6, 0x02, 0xb5, 0xeb, 0x64, 0xb8},
1183              {0x1d, 0x42, 0xb9, 0xf9, 0xe9, 0xe3, 0x93, 0x2c,
1184               0x4c, 0xee, 0x6c, 0x5a, 0x47, 0x9e, 0x62, 0x01,
1185               0x6b, 0x04, 0xfe, 0xa4, 0x30, 0x2b, 0x0d, 0x4f,
1186               0x71, 0x10, 0xd3, 0x55, 0xca, 0xf3, 0x5e, 0x80}},
1187             {{0x77, 0x05, 0xf6, 0x0c, 0x15, 0x9b, 0x45, 0xe7,
1188               0xb9, 0x11, 0xb8, 0xf5, 0xd6, 0xda, 0x73, 0x0c,
1189               0xda, 0x92, 0xea, 0xd0, 0x9d, 0xd0, 0x18, 0x92,
1190               0xce, 0x9a, 0xaa, 0xee, 0x0f, 0xef, 0xde, 0x30},
1191              {0xf1, 0xf1, 0xd6, 0x9b, 0x51, 0xd7, 0x77, 0x62,
1192               0x52, 0x10, 0xb8, 0x7a, 0x84, 0x9d, 0x15, 0x4e,
1193               0x07, 0xdc, 0x1e, 0x75, 0x0d, 0x0c, 0x3b, 0xdb,
1194               0x74, 0x58, 0x62, 0x02, 0x90, 0x54, 0x8b, 0x43}},
1195             {{0xa6, 0xfe, 0x0b, 0x87, 0x80, 0x43, 0x67, 0x25,
1196               0x57, 0x5d, 0xec, 0x40, 0x50, 0x08, 0xd5, 0x5d,
1197               0x43, 0xd7, 0xe0, 0xaa, 0xe0, 0x13, 0xb6, 0xb0,
1198               0xc0, 0xd4, 0xe5, 0x0d, 0x45, 0x83, 0xd6, 0x13},
1199              {0x40, 0x45, 0x0a, 0x92, 0x31, 0xea, 0x8c, 0x60,
1200               0x8c, 0x1f, 0xd8, 0x76, 0x45, 0xb9, 0x29, 0x00,
1201               0x26, 0x32, 0xd8, 0xa6, 0x96, 0x88, 0xe2, 0xc4,
1202               0x8b, 0xdb, 0x7f, 0x17, 0x87, 0xcc, 0xc8, 0xf2}},
1203             {{0xc2, 0x56, 0xe2, 0xb6, 0x1a, 0x81, 0xe7, 0x31,
1204               0x63, 0x2e, 0xbb, 0x0d, 0x2f, 0x81, 0x67, 0xd4,
1205               0x22, 0xe2, 0x38, 0x02, 0x25, 0x97, 0xc7, 0x88,
1206               0x6e, 0xdf, 0xbe, 0x2a, 0xa5, 0x73, 0x63, 0xaa},
1207              {0x50, 0x45, 0xe2, 0xc3, 0xbd, 0x89, 0xfc, 0x57,
1208               0xbd, 0x3c, 0xa3, 0x98, 0x7e, 0x7f, 0x36, 0x38,
1209               0x92, 0x39, 0x1f, 0x0f, 0x81, 0x1a, 0x06, 0x51,
1210               0x1f, 0x8d, 0x6a, 0xff, 0x47, 0x16, 0x06, 0x9c}},
1211             {{0x33, 0x95, 0xa2, 0x6f, 0x27, 0x5f, 0x9c, 0x9c,
1212               0x64, 0x45, 0xcb, 0xd1, 0x3c, 0xee, 0x5e, 0x5f,
1213               0x48, 0xa6, 0xaf, 0xe3, 0x79, 0xcf, 0xb1, 0xe2,
1214               0xbf, 0x55, 0x0e, 0xa2, 0x3b, 0x62, 0xf0, 0xe4},
1215              {0x14, 0xe8, 0x06, 0xe3, 0xbe, 0x7e, 0x67, 0x01,
1216               0xc5, 0x21, 0x67, 0xd8, 0x54, 0xb5, 0x7f, 0xa4,
1217               0xf9, 0x75, 0x70, 0x1c, 0xfd, 0x79, 0xdb, 0x86,
1218               0xad, 0x37, 0x85, 0x83, 0x56, 0x4e, 0xf0, 0xbf}},
1219             {{0xbc, 0xa6, 0xe0, 0x56, 0x4e, 0xef, 0xfa, 0xf5,
1220               0x1d, 0x5d, 0x3f, 0x2a, 0x5b, 0x19, 0xab, 0x51,
1221               0xc5, 0x8b, 0xdd, 0x98, 0x28, 0x35, 0x2f, 0xc3,
1222               0x81, 0x4f, 0x5c, 0xe5, 0x70, 0xb9, 0xeb, 0x62},
1223              {0xc4, 0x6d, 0x26, 0xb0, 0x17, 0x6b, 0xfe, 0x6c,
1224               0x12, 0xf8, 0xe7, 0xc1, 0xf5, 0x2f, 0xfa, 0x91,
1225               0x13, 0x27, 0xbd, 0x73, 0xcc, 0x33, 0x31, 0x1c,
1226               0x39, 0xe3, 0x27, 0x6a, 0x95, 0xcf, 0xc5, 0xfb}},
1227             {{0x30, 0xb2, 0x99, 0x84, 0xf0, 0x18, 0x2a, 0x6e,
1228               0x1e, 0x27, 0xed, 0xa2, 0x29, 0x99, 0x41, 0x56,
1229               0xe8, 0xd4, 0x0d, 0xef, 0x99, 0x9c, 0xf3, 0x58,
1230               0x29, 0x55, 0x1a, 0xc0, 0x68, 0xd6, 0x74, 0xa4},
1231              {0x07, 0x9c, 0xe7, 0xec, 0xf5, 0x36, 0x73, 0x41,
1232               0xa3, 0x1c, 0xe5, 0x93, 0x97, 0x6a, 0xfd, 0xf7,
1233               0x53, 0x18, 0xab, 0xaf, 0xeb, 0x85, 0xbd, 0x92,
1234               0x90, 0xab, 0x3c, 0xbf, 0x30, 0x82, 0xad, 0xf6}},
1235             {{0xc6, 0x87, 0x8a, 0x2a, 0xea, 0xc0, 0xa9, 0xec,
1236               0x6d, 0xd3, 0xdc, 0x32, 0x23, 0xce, 0x62, 0x19,
1237               0xa4, 0x7e, 0xa8, 0xdd, 0x1c, 0x33, 0xae, 0xd3,
1238               0x4f, 0x62, 0x9f, 0x52, 0xe7, 0x65, 0x46, 0xf4},
1239              {0x97, 0x51, 0x27, 0x67, 0x2d, 0xa2, 0x82, 0x87,
1240               0x98, 0xd3, 0xb6, 0x14, 0x7f, 0x51, 0xd3, 0x9a,
1241               0x0b, 0xd0, 0x76, 0x81, 0xb2, 0x4f, 0x58, 0x92,
1242               0xa4, 0x86, 0xa1, 0xa7, 0x09, 0x1d, 0xef, 0x9b}},
1243             {{0xb3, 0x0f, 0x2b, 0x69, 0x0d, 0x06, 0x90, 0x64,
1244               0xbd, 0x43, 0x4c, 0x10, 0xe8, 0x98, 0x1c, 0xa3,
1245               0xe1, 0x68, 0xe9, 0x79, 0x6c, 0x29, 0x51, 0x3f,
1246               0x41, 0xdc, 0xdf, 0x1f, 0xf3, 0x60, 0xbe, 0x33},
1247              {0xa1, 0x5f, 0xf7, 0x1d, 0xb4, 0x3e, 0x9b, 0x3c,
1248               0xe7, 0xbd, 0xb6, 0x06, 0xd5, 0x60, 0x06, 0x6d,
1249               0x50, 0xd2, 0xf4, 0x1a, 0x31, 0x08, 0xf2, 0xea,
1250               0x8e, 0xef, 0x5f, 0x7d, 0xb6, 0xd0, 0xc0, 0x27}},
1251             {{0x62, 0x9a, 0xd9, 0xbb, 0x38, 0x36, 0xce, 0xf7,
1252               0x5d, 0x2f, 0x13, 0xec, 0xc8, 0x2d, 0x02, 0x8a,
1253               0x2e, 0x72, 0xf0, 0xe5, 0x15, 0x9d, 0x72, 0xae,
1254               0xfc, 0xb3, 0x4f, 0x02, 0xea, 0xe1, 0x09, 0xfe},
1255              {0x00, 0x00, 0x00, 0x00, 0xfa, 0x0a, 0x3d, 0xbc,
1256               0xad, 0x16, 0x0c, 0xb6, 0xe7, 0x7c, 0x8b, 0x39,
1257               0x9a, 0x43, 0xbb, 0xe3, 0xc2, 0x55, 0x15, 0x14,
1258               0x75, 0xac, 0x90, 0x9b, 0x7f, 0x9a, 0x92, 0x00}},
1259             {{0x8b, 0xac, 0x70, 0x86, 0x29, 0x8f, 0x00, 0x23,
1260               0x7b, 0x45, 0x30, 0xaa, 0xb8, 0x4c, 0xc7, 0x8d,
1261               0x4e, 0x47, 0x85, 0xc6, 0x19, 0xe3, 0x96, 0xc2,
1262               0x9a, 0xa0, 0x12, 0xed, 0x6f, 0xd7, 0x76, 0x16},
1263              {0x45, 0xaf, 0x7e, 0x33, 0xc7, 0x7f, 0x10, 0x6c,
1264               0x7c, 0x9f, 0x29, 0xc1, 0xa8, 0x7e, 0x15, 0x84,
1265               0xe7, 0x7d, 0xc0, 0x6d, 0xab, 0x71, 0x5d, 0xd0,
1266               0x6b, 0x9f, 0x97, 0xab, 0xcb, 0x51, 0x0c, 0x9f}},
1267             {{0x9e, 0xc3, 0x92, 0xb4, 0x04, 0x9f, 0xc8, 0xbb,
1268               0xdd, 0x9e, 0xc6, 0x05, 0xfd, 0x65, 0xec, 0x94,
1269               0x7f, 0x2c, 0x16, 0xc4, 0x40, 0xac, 0x63, 0x7b,
1270               0x7d, 0xb8, 0x0c, 0xe4, 0x5b, 0xe3, 0xa7, 0x0e},
1271              {0x43, 0xf4, 0x44, 0xe8, 0xcc, 0xc8, 0xd4, 0x54,
1272               0x33, 0x37, 0x50, 0xf2, 0x87, 0x42, 0x2e, 0x00,
1273               0x49, 0x60, 0x62, 0x02, 0xfd, 0x1a, 0x7c, 0xdb,
1274               0x29, 0x6c, 0x6d, 0x54, 0x53, 0x08, 0xd1, 0xc8}},
1275             {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1276               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1277               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1278               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00},
1279              {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1280               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1281               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1282               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}},
1283             {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1284               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1285               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1286               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00},
1287              {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1288               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1289               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1290               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01}},
1291             {{0x27, 0x59, 0xc7, 0x35, 0x60, 0x71, 0xa6, 0xf1,
1292               0x79, 0xa5, 0xfd, 0x79, 0x16, 0xf3, 0x41, 0xf0,
1293               0x57, 0xb4, 0x02, 0x97, 0x32, 0xe7, 0xde, 0x59,
1294               0xe2, 0x2d, 0x9b, 0x11, 0xea, 0x2c, 0x35, 0x92},
1295              {0x27, 0x59, 0xc7, 0x35, 0x60, 0x71, 0xa6, 0xf1,
1296               0x79, 0xa5, 0xfd, 0x79, 0x16, 0xf3, 0x41, 0xf0,
1297               0x57, 0xb4, 0x02, 0x97, 0x32, 0xe7, 0xde, 0x59,
1298               0xe2, 0x2d, 0x9b, 0x11, 0xea, 0x2c, 0x35, 0x92}},
1299             {{0x28, 0x56, 0xac, 0x0e, 0x4f, 0x98, 0x09, 0xf0,
1300               0x49, 0xfa, 0x7f, 0x84, 0xac, 0x7e, 0x50, 0x5b,
1301               0x17, 0x43, 0x14, 0x89, 0x9c, 0x53, 0xa8, 0x94,
1302               0x30, 0xf2, 0x11, 0x4d, 0x92, 0x14, 0x27, 0xe8},
1303              {0x39, 0x7a, 0x84, 0x56, 0x79, 0x9d, 0xec, 0x26,
1304               0x2c, 0x53, 0xc1, 0x94, 0xc9, 0x8d, 0x9e, 0x9d,
1305               0x32, 0x1f, 0xdd, 0x84, 0x04, 0xe8, 0xe2, 0x0a,
1306               0x6b, 0xbe, 0xbb, 0x42, 0x40, 0x67, 0x30, 0x6c}},
1307             {{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1308               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
1309               0x45, 0x51, 0x23, 0x19, 0x50, 0xb7, 0x5f, 0xc4,
1310               0x40, 0x2d, 0xa1, 0x73, 0x2f, 0xc9, 0xbe, 0xbd},
1311              {0x27, 0x59, 0xc7, 0x35, 0x60, 0x71, 0xa6, 0xf1,
1312               0x79, 0xa5, 0xfd, 0x79, 0x16, 0xf3, 0x41, 0xf0,
1313               0x57, 0xb4, 0x02, 0x97, 0x32, 0xe7, 0xde, 0x59,
1314               0xe2, 0x2d, 0x9b, 0x11, 0xea, 0x2c, 0x35, 0x92}},
1315             {{0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1316               0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
1317               0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
1318               0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x40},
1319              {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1320               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1321               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1322               0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01}},
1323             {{0x1c, 0xc4, 0xf7, 0xda, 0x0f, 0x65, 0xca, 0x39,
1324               0x70, 0x52, 0x92, 0x8e, 0xc3, 0xc8, 0x15, 0xea,
1325               0x7f, 0x10, 0x9e, 0x77, 0x4b, 0x6e, 0x2d, 0xdf,
1326               0xe8, 0x30, 0x9d, 0xda, 0xe8, 0x9a, 0x65, 0xae},
1327              {0x02, 0xb0, 0x16, 0xb1, 0x1d, 0xc8, 0x57, 0x7b,
1328               0xa2, 0x3a, 0xa2, 0xa3, 0x38, 0x5c, 0x8f, 0xeb,
1329               0x66, 0x37, 0x91, 0xa8, 0x5f, 0xef, 0x04, 0xf6,
1330               0x59, 0x75, 0xe1, 0xee, 0x92, 0xf6, 0x0e, 0x30}},
1331             {{0x8d, 0x76, 0x14, 0xa4, 0x14, 0x06, 0x9f, 0x9a,
1332               0xdf, 0x4a, 0x85, 0xa7, 0x6b, 0xbf, 0x29, 0x6f,
1333               0xbc, 0x34, 0x87, 0x5d, 0xeb, 0xbb, 0x2e, 0xa9,
1334               0xc9, 0x1f, 0x58, 0xd6, 0x9a, 0x82, 0xa0, 0x56},
1335              {0xd4, 0xb9, 0xdb, 0x88, 0x1d, 0x04, 0xe9, 0x93,
1336               0x8d, 0x3f, 0x20, 0xd5, 0x86, 0xa8, 0x83, 0x07,
1337               0xdb, 0x09, 0xd8, 0x22, 0x1f, 0x7f, 0xf1, 0x71,
1338               0xc8, 0xe7, 0x5d, 0x47, 0xaf, 0x8b, 0x72, 0xe9}},
1339             {{0x83, 0xb9, 0x39, 0xb2, 0xa4, 0xdf, 0x46, 0x87,
1340               0xc2, 0xb8, 0xf1, 0xe6, 0x4c, 0xd1, 0xe2, 0xa9,
1341               0xe4, 0x70, 0x30, 0x34, 0xbc, 0x52, 0x7c, 0x55,
1342               0xa6, 0xec, 0x80, 0xa4, 0xe5, 0xd2, 0xdc, 0x73},
1343              {0x08, 0xf1, 0x03, 0xcf, 0x16, 0x73, 0xe8, 0x7d,
1344               0xb6, 0x7e, 0x9b, 0xc0, 0xb4, 0xc2, 0xa5, 0x86,
1345               0x02, 0x77, 0xd5, 0x27, 0x86, 0xa5, 0x15, 0xfb,
1346               0xae, 0x9b, 0x8c, 0xa9, 0xf9, 0xf8, 0xa8, 0x4a}},
1347             {{0x8b, 0x00, 0x49, 0xdb, 0xfa, 0xf0, 0x1b, 0xa2,
1348               0xed, 0x8a, 0x9a, 0x7a, 0x36, 0x78, 0x4a, 0xc7,
1349               0xf7, 0xad, 0x39, 0xd0, 0x6c, 0x65, 0x7a, 0x41,
1350               0xce, 0xd6, 0xd6, 0x4c, 0x20, 0x21, 0x6b, 0xc7},
1351              {0xc6, 0xca, 0x78, 0x1d, 0x32, 0x6c, 0x6c, 0x06,
1352               0x91, 0xf2, 0x1a, 0xe8, 0x43, 0x16, 0xea, 0x04,
1353               0x3c, 0x1f, 0x07, 0x85, 0xf7, 0x09, 0x22, 0x08,
1354               0xba, 0x13, 0xfd, 0x78, 0x1e, 0x3f, 0x6f, 0x62}},
1355             {{0x25, 0x9b, 0x7c, 0xb0, 0xac, 0x72, 0x6f, 0xb2,
1356               0xe3, 0x53, 0x84, 0x7a, 0x1a, 0x9a, 0x98, 0x9b,
1357               0x44, 0xd3, 0x59, 0xd0, 0x8e, 0x57, 0x41, 0x40,
1358               0x78, 0xa7, 0x30, 0x2f, 0x4c, 0x9c, 0xb9, 0x68},
1359              {0xb7, 0x75, 0x03, 0x63, 0x61, 0xc2, 0x48, 0x6e,
1360               0x12, 0x3d, 0xbf, 0x4b, 0x27, 0xdf, 0xb1, 0x7a,
1361               0xff, 0x4e, 0x31, 0x07, 0x83, 0xf4, 0x62, 0x5b,
1362               0x19, 0xa5, 0xac, 0xa0, 0x32, 0x58, 0x0d, 0xa7}},
1363             {{0x43, 0x4f, 0x10, 0xa4, 0xca, 0xdb, 0x38, 0x67,
1364               0xfa, 0xae, 0x96, 0xb5, 0x6d, 0x97, 0xff, 0x1f,
1365               0xb6, 0x83, 0x43, 0xd3, 0xa0, 0x2d, 0x70, 0x7a,
1366               0x64, 0x05, 0x4c, 0xa7, 0xc1, 0xa5, 0x21, 0x51},
1367              {0xe4, 0xf1, 0x23, 0x84, 0xe1, 0xb5, 0x9d, 0xf2,
1368               0xb8, 0x73, 0x8b, 0x45, 0x2b, 0x35, 0x46, 0x38,
1369               0x10, 0x2b, 0x50, 0xf8, 0x8b, 0x35, 0xcd, 0x34,
1370               0xc8, 0x0e, 0xf6, 0xdb, 0x09, 0x35, 0xf0, 0xda}}
1371         };
1372         secp256k1_scalar_set_int(&one, 1);
1373         for (i = 0; i < 32; i++) {
1374             secp256k1_scalar_set_b32(&x, chal[i][0], &overflow);
1375             CHECK(!overflow);
1376             secp256k1_scalar_set_b32(&y, chal[i][1], &overflow);
1377             CHECK(!overflow);
1378             secp256k1_scalar_set_b32(&r1, res[i][0], &overflow);
1379             CHECK(!overflow);
1380             secp256k1_scalar_set_b32(&r2, res[i][1], &overflow);
1381             CHECK(!overflow);
1382             secp256k1_scalar_mul(&z, &x, &y);
1383             CHECK(!secp256k1_scalar_check_overflow(&z));
1384             CHECK(secp256k1_scalar_eq(&r1, &z));
1385             if (!secp256k1_scalar_is_zero(&y)) {
1386                 secp256k1_scalar_inverse(&zz, &y);
1387                 CHECK(!secp256k1_scalar_check_overflow(&zz));
1388 #if defined(USE_SCALAR_INV_NUM)
1389                 secp256k1_scalar_inverse_var(&zzv, &y);
1390                 CHECK(secp256k1_scalar_eq(&zzv, &zz));
1391 #endif
1392                 secp256k1_scalar_mul(&z, &z, &zz);
1393                 CHECK(!secp256k1_scalar_check_overflow(&z));
1394                 CHECK(secp256k1_scalar_eq(&x, &z));
1395                 secp256k1_scalar_mul(&zz, &zz, &y);
1396                 CHECK(!secp256k1_scalar_check_overflow(&zz));
1397                 CHECK(secp256k1_scalar_eq(&one, &zz));
1398             }
1399             secp256k1_scalar_mul(&z, &x, &x);
1400             CHECK(!secp256k1_scalar_check_overflow(&z));
1401             secp256k1_scalar_sqr(&zz, &x);
1402             CHECK(!secp256k1_scalar_check_overflow(&zz));
1403             CHECK(secp256k1_scalar_eq(&zz, &z));
1404             CHECK(secp256k1_scalar_eq(&r2, &zz));
1405         }
1406     }
1407 }
1408
1409 /***** FIELD TESTS *****/
1410
1411 void random_fe(secp256k1_fe *x) {
1412     unsigned char bin[32];
1413     do {
1414         secp256k1_rand256(bin);
1415         if (secp256k1_fe_set_b32(x, bin)) {
1416             return;
1417         }
1418     } while(1);
1419 }
1420
1421 void random_fe_non_zero(secp256k1_fe *nz) {
1422     int tries = 10;
1423     while (--tries >= 0) {
1424         random_fe(nz);
1425         secp256k1_fe_normalize(nz);
1426         if (!secp256k1_fe_is_zero(nz)) {
1427             break;
1428         }
1429     }
1430     /* Infinitesimal probability of spurious failure here */
1431     CHECK(tries >= 0);
1432 }
1433
1434 void random_fe_non_square(secp256k1_fe *ns) {
1435     secp256k1_fe r;
1436     random_fe_non_zero(ns);
1437     if (secp256k1_fe_sqrt_var(&r, ns)) {
1438         secp256k1_fe_negate(ns, ns, 1);
1439     }
1440 }
1441
1442 int check_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b) {
1443     secp256k1_fe an = *a;
1444     secp256k1_fe bn = *b;
1445     secp256k1_fe_normalize_weak(&an);
1446     secp256k1_fe_normalize_var(&bn);
1447     return secp256k1_fe_equal_var(&an, &bn);
1448 }
1449
1450 int check_fe_inverse(const secp256k1_fe *a, const secp256k1_fe *ai) {
1451     secp256k1_fe x;
1452     secp256k1_fe one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1);
1453     secp256k1_fe_mul(&x, a, ai);
1454     return check_fe_equal(&x, &one);
1455 }
1456
1457 void run_field_convert(void) {
1458     static const unsigned char b32[32] = {
1459         0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
1460         0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18,
1461         0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29,
1462         0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x40
1463     };
1464     static const secp256k1_fe_storage fes = SECP256K1_FE_STORAGE_CONST(
1465         0x00010203UL, 0x04050607UL, 0x11121314UL, 0x15161718UL,
1466         0x22232425UL, 0x26272829UL, 0x33343536UL, 0x37383940UL
1467     );
1468     static const secp256k1_fe fe = SECP256K1_FE_CONST(
1469         0x00010203UL, 0x04050607UL, 0x11121314UL, 0x15161718UL,
1470         0x22232425UL, 0x26272829UL, 0x33343536UL, 0x37383940UL
1471     );
1472     secp256k1_fe fe2;
1473     unsigned char b322[32];
1474     secp256k1_fe_storage fes2;
1475     /* Check conversions to fe. */
1476     CHECK(secp256k1_fe_set_b32(&fe2, b32));
1477     CHECK(secp256k1_fe_equal_var(&fe, &fe2));
1478     secp256k1_fe_from_storage(&fe2, &fes);
1479     CHECK(secp256k1_fe_equal_var(&fe, &fe2));
1480     /* Check conversion from fe. */
1481     secp256k1_fe_get_b32(b322, &fe);
1482     CHECK(memcmp(b322, b32, 32) == 0);
1483     secp256k1_fe_to_storage(&fes2, &fe);
1484     CHECK(memcmp(&fes2, &fes, sizeof(fes)) == 0);
1485 }
1486
1487 int fe_memcmp(const secp256k1_fe *a, const secp256k1_fe *b) {
1488     secp256k1_fe t = *b;
1489 #ifdef VERIFY
1490     t.magnitude = a->magnitude;
1491     t.normalized = a->normalized;
1492 #endif
1493     return memcmp(a, &t, sizeof(secp256k1_fe));
1494 }
1495
1496 void run_field_misc(void) {
1497     secp256k1_fe x;
1498     secp256k1_fe y;
1499     secp256k1_fe z;
1500     secp256k1_fe q;
1501     secp256k1_fe fe5 = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 5);
1502     int i, j;
1503     for (i = 0; i < 5*count; i++) {
1504         secp256k1_fe_storage xs, ys, zs;
1505         random_fe(&x);
1506         random_fe_non_zero(&y);
1507         /* Test the fe equality and comparison operations. */
1508         CHECK(secp256k1_fe_cmp_var(&x, &x) == 0);
1509         CHECK(secp256k1_fe_equal_var(&x, &x));
1510         z = x;
1511         secp256k1_fe_add(&z,&y);
1512         /* Test fe conditional move; z is not normalized here. */
1513         q = x;
1514         secp256k1_fe_cmov(&x, &z, 0);
1515         VERIFY_CHECK(!x.normalized && x.magnitude == z.magnitude);
1516         secp256k1_fe_cmov(&x, &x, 1);
1517         CHECK(fe_memcmp(&x, &z) != 0);
1518         CHECK(fe_memcmp(&x, &q) == 0);
1519         secp256k1_fe_cmov(&q, &z, 1);
1520         VERIFY_CHECK(!q.normalized && q.magnitude == z.magnitude);
1521         CHECK(fe_memcmp(&q, &z) == 0);
1522         secp256k1_fe_normalize_var(&x);
1523         secp256k1_fe_normalize_var(&z);
1524         CHECK(!secp256k1_fe_equal_var(&x, &z));
1525         secp256k1_fe_normalize_var(&q);
1526         secp256k1_fe_cmov(&q, &z, (i&1));
1527         VERIFY_CHECK(q.normalized && q.magnitude == 1);
1528         for (j = 0; j < 6; j++) {
1529             secp256k1_fe_negate(&z, &z, j+1);
1530             secp256k1_fe_normalize_var(&q);
1531             secp256k1_fe_cmov(&q, &z, (j&1));
1532             VERIFY_CHECK(!q.normalized && q.magnitude == (j+2));
1533         }
1534         secp256k1_fe_normalize_var(&z);
1535         /* Test storage conversion and conditional moves. */
1536         secp256k1_fe_to_storage(&xs, &x);
1537         secp256k1_fe_to_storage(&ys, &y);
1538         secp256k1_fe_to_storage(&zs, &z);
1539         secp256k1_fe_storage_cmov(&zs, &xs, 0);
1540         secp256k1_fe_storage_cmov(&zs, &zs, 1);
1541         CHECK(memcmp(&xs, &zs, sizeof(xs)) != 0);
1542         secp256k1_fe_storage_cmov(&ys, &xs, 1);
1543         CHECK(memcmp(&xs, &ys, sizeof(xs)) == 0);
1544         secp256k1_fe_from_storage(&x, &xs);
1545         secp256k1_fe_from_storage(&y, &ys);
1546         secp256k1_fe_from_storage(&z, &zs);
1547         /* Test that mul_int, mul, and add agree. */
1548         secp256k1_fe_add(&y, &x);
1549         secp256k1_fe_add(&y, &x);
1550         z = x;
1551         secp256k1_fe_mul_int(&z, 3);
1552         CHECK(check_fe_equal(&y, &z));
1553         secp256k1_fe_add(&y, &x);
1554         secp256k1_fe_add(&z, &x);
1555         CHECK(check_fe_equal(&z, &y));
1556         z = x;
1557         secp256k1_fe_mul_int(&z, 5);
1558         secp256k1_fe_mul(&q, &x, &fe5);
1559         CHECK(check_fe_equal(&z, &q));
1560         secp256k1_fe_negate(&x, &x, 1);
1561         secp256k1_fe_add(&z, &x);
1562         secp256k1_fe_add(&q, &x);
1563         CHECK(check_fe_equal(&y, &z));
1564         CHECK(check_fe_equal(&q, &y));
1565     }
1566 }
1567
1568 void run_field_inv(void) {
1569     secp256k1_fe x, xi, xii;
1570     int i;
1571     for (i = 0; i < 10*count; i++) {
1572         random_fe_non_zero(&x);
1573         secp256k1_fe_inv(&xi, &x);
1574         CHECK(check_fe_inverse(&x, &xi));
1575         secp256k1_fe_inv(&xii, &xi);
1576         CHECK(check_fe_equal(&x, &xii));
1577     }
1578 }
1579
1580 void run_field_inv_var(void) {
1581     secp256k1_fe x, xi, xii;
1582     int i;
1583     for (i = 0; i < 10*count; i++) {
1584         random_fe_non_zero(&x);
1585         secp256k1_fe_inv_var(&xi, &x);
1586         CHECK(check_fe_inverse(&x, &xi));
1587         secp256k1_fe_inv_var(&xii, &xi);
1588         CHECK(check_fe_equal(&x, &xii));
1589     }
1590 }
1591
1592 void run_field_inv_all_var(void) {
1593     secp256k1_fe x[16], xi[16], xii[16];
1594     int i;
1595     /* Check it's safe to call for 0 elements */
1596     secp256k1_fe_inv_all_var(0, xi, x);
1597     for (i = 0; i < count; i++) {
1598         size_t j;
1599         size_t len = secp256k1_rand_int(15) + 1;
1600         for (j = 0; j < len; j++) {
1601             random_fe_non_zero(&x[j]);
1602         }
1603         secp256k1_fe_inv_all_var(len, xi, x);
1604         for (j = 0; j < len; j++) {
1605             CHECK(check_fe_inverse(&x[j], &xi[j]));
1606         }
1607         secp256k1_fe_inv_all_var(len, xii, xi);
1608         for (j = 0; j < len; j++) {
1609             CHECK(check_fe_equal(&x[j], &xii[j]));
1610         }
1611     }
1612 }
1613
1614 void run_sqr(void) {
1615     secp256k1_fe x, s;
1616
1617     {
1618         int i;
1619         secp256k1_fe_set_int(&x, 1);
1620         secp256k1_fe_negate(&x, &x, 1);
1621
1622         for (i = 1; i <= 512; ++i) {
1623             secp256k1_fe_mul_int(&x, 2);
1624             secp256k1_fe_normalize(&x);
1625             secp256k1_fe_sqr(&s, &x);
1626         }
1627     }
1628 }
1629
1630 void test_sqrt(const secp256k1_fe *a, const secp256k1_fe *k) {
1631     secp256k1_fe r1, r2;
1632     int v = secp256k1_fe_sqrt_var(&r1, a);
1633     CHECK((v == 0) == (k == NULL));
1634
1635     if (k != NULL) {
1636         /* Check that the returned root is +/- the given known answer */
1637         secp256k1_fe_negate(&r2, &r1, 1);
1638         secp256k1_fe_add(&r1, k); secp256k1_fe_add(&r2, k);
1639         secp256k1_fe_normalize(&r1); secp256k1_fe_normalize(&r2);
1640         CHECK(secp256k1_fe_is_zero(&r1) || secp256k1_fe_is_zero(&r2));
1641     }
1642 }
1643
1644 void run_sqrt(void) {
1645     secp256k1_fe ns, x, s, t;
1646     int i;
1647
1648     /* Check sqrt(0) is 0 */
1649     secp256k1_fe_set_int(&x, 0);
1650     secp256k1_fe_sqr(&s, &x);
1651     test_sqrt(&s, &x);
1652
1653     /* Check sqrt of small squares (and their negatives) */
1654     for (i = 1; i <= 100; i++) {
1655         secp256k1_fe_set_int(&x, i);
1656         secp256k1_fe_sqr(&s, &x);
1657         test_sqrt(&s, &x);
1658         secp256k1_fe_negate(&t, &s, 1);
1659         test_sqrt(&t, NULL);
1660     }
1661
1662     /* Consistency checks for large random values */
1663     for (i = 0; i < 10; i++) {
1664         int j;
1665         random_fe_non_square(&ns);
1666         for (j = 0; j < count; j++) {
1667             random_fe(&x);
1668             secp256k1_fe_sqr(&s, &x);
1669             test_sqrt(&s, &x);
1670             secp256k1_fe_negate(&t, &s, 1);
1671             test_sqrt(&t, NULL);
1672             secp256k1_fe_mul(&t, &s, &ns);
1673             test_sqrt(&t, NULL);
1674         }
1675     }
1676 }
1677
1678 /***** GROUP TESTS *****/
1679
1680 void ge_equals_ge(const secp256k1_ge *a, const secp256k1_ge *b) {
1681     CHECK(a->infinity == b->infinity);
1682     if (a->infinity) {
1683         return;
1684     }
1685     CHECK(secp256k1_fe_equal_var(&a->x, &b->x));
1686     CHECK(secp256k1_fe_equal_var(&a->y, &b->y));
1687 }
1688
1689 /* This compares jacobian points including their Z, not just their geometric meaning. */
1690 int gej_xyz_equals_gej(const secp256k1_gej *a, const secp256k1_gej *b) {
1691     secp256k1_gej a2;
1692     secp256k1_gej b2;
1693     int ret = 1;
1694     ret &= a->infinity == b->infinity;
1695     if (ret && !a->infinity) {
1696         a2 = *a;
1697         b2 = *b;
1698         secp256k1_fe_normalize(&a2.x);
1699         secp256k1_fe_normalize(&a2.y);
1700         secp256k1_fe_normalize(&a2.z);
1701         secp256k1_fe_normalize(&b2.x);
1702         secp256k1_fe_normalize(&b2.y);
1703         secp256k1_fe_normalize(&b2.z);
1704         ret &= secp256k1_fe_cmp_var(&a2.x, &b2.x) == 0;
1705         ret &= secp256k1_fe_cmp_var(&a2.y, &b2.y) == 0;
1706         ret &= secp256k1_fe_cmp_var(&a2.z, &b2.z) == 0;
1707     }
1708     return ret;
1709 }
1710
1711 void ge_equals_gej(const secp256k1_ge *a, const secp256k1_gej *b) {
1712     secp256k1_fe z2s;
1713     secp256k1_fe u1, u2, s1, s2;
1714     CHECK(a->infinity == b->infinity);
1715     if (a->infinity) {
1716         return;
1717     }
1718     /* Check a.x * b.z^2 == b.x && a.y * b.z^3 == b.y, to avoid inverses. */
1719     secp256k1_fe_sqr(&z2s, &b->z);
1720     secp256k1_fe_mul(&u1, &a->x, &z2s);
1721     u2 = b->x; secp256k1_fe_normalize_weak(&u2);
1722     secp256k1_fe_mul(&s1, &a->y, &z2s); secp256k1_fe_mul(&s1, &s1, &b->z);
1723     s2 = b->y; secp256k1_fe_normalize_weak(&s2);
1724     CHECK(secp256k1_fe_equal_var(&u1, &u2));
1725     CHECK(secp256k1_fe_equal_var(&s1, &s2));
1726 }
1727
1728 void test_ge(void) {
1729     int i, i1;
1730 #ifdef USE_ENDOMORPHISM
1731     int runs = 6;
1732 #else
1733     int runs = 4;
1734 #endif
1735     /* Points: (infinity, p1, p1, -p1, -p1, p2, p2, -p2, -p2, p3, p3, -p3, -p3, p4, p4, -p4, -p4).
1736      * The second in each pair of identical points uses a random Z coordinate in the Jacobian form.
1737      * All magnitudes are randomized.
1738      * All 17*17 combinations of points are added to eachother, using all applicable methods.
1739      *
1740      * When the endomorphism code is compiled in, p5 = lambda*p1 and p6 = lambda^2*p1 are added as well.
1741      */
1742     secp256k1_ge *ge = (secp256k1_ge *)malloc(sizeof(secp256k1_ge) * (1 + 4 * runs));
1743     secp256k1_gej *gej = (secp256k1_gej *)malloc(sizeof(secp256k1_gej) * (1 + 4 * runs));
1744     secp256k1_fe *zinv = (secp256k1_fe *)malloc(sizeof(secp256k1_fe) * (1 + 4 * runs));
1745     secp256k1_fe zf;
1746     secp256k1_fe zfi2, zfi3;
1747
1748     secp256k1_gej_set_infinity(&gej[0]);
1749     secp256k1_ge_clear(&ge[0]);
1750     secp256k1_ge_set_gej_var(&ge[0], &gej[0]);
1751     for (i = 0; i < runs; i++) {
1752         int j;
1753         secp256k1_ge g;
1754         random_group_element_test(&g);
1755 #ifdef USE_ENDOMORPHISM
1756         if (i >= runs - 2) {
1757             secp256k1_ge_mul_lambda(&g, &ge[1]);
1758         }
1759         if (i >= runs - 1) {
1760             secp256k1_ge_mul_lambda(&g, &g);
1761         }
1762 #endif
1763         ge[1 + 4 * i] = g;
1764         ge[2 + 4 * i] = g;
1765         secp256k1_ge_neg(&ge[3 + 4 * i], &g);
1766         secp256k1_ge_neg(&ge[4 + 4 * i], &g);
1767         secp256k1_gej_set_ge(&gej[1 + 4 * i], &ge[1 + 4 * i]);
1768         random_group_element_jacobian_test(&gej[2 + 4 * i], &ge[2 + 4 * i]);
1769         secp256k1_gej_set_ge(&gej[3 + 4 * i], &ge[3 + 4 * i]);
1770         random_group_element_jacobian_test(&gej[4 + 4 * i], &ge[4 + 4 * i]);
1771         for (j = 0; j < 4; j++) {
1772             random_field_element_magnitude(&ge[1 + j + 4 * i].x);
1773             random_field_element_magnitude(&ge[1 + j + 4 * i].y);
1774             random_field_element_magnitude(&gej[1 + j + 4 * i].x);
1775             random_field_element_magnitude(&gej[1 + j + 4 * i].y);
1776             random_field_element_magnitude(&gej[1 + j + 4 * i].z);
1777         }
1778     }
1779
1780     /* Compute z inverses. */
1781     {
1782         secp256k1_fe *zs = malloc(sizeof(secp256k1_fe) * (1 + 4 * runs));
1783         for (i = 0; i < 4 * runs + 1; i++) {
1784             if (i == 0) {
1785                 /* The point at infinity does not have a meaningful z inverse. Any should do. */
1786                 do {
1787                     random_field_element_test(&zs[i]);
1788                 } while(secp256k1_fe_is_zero(&zs[i]));
1789             } else {
1790                 zs[i] = gej[i].z;
1791             }
1792         }
1793         secp256k1_fe_inv_all_var(4 * runs + 1, zinv, zs);
1794         free(zs);
1795     }
1796
1797     /* Generate random zf, and zfi2 = 1/zf^2, zfi3 = 1/zf^3 */
1798     do {
1799         random_field_element_test(&zf);
1800     } while(secp256k1_fe_is_zero(&zf));
1801     random_field_element_magnitude(&zf);
1802     secp256k1_fe_inv_var(&zfi3, &zf);
1803     secp256k1_fe_sqr(&zfi2, &zfi3);
1804     secp256k1_fe_mul(&zfi3, &zfi3, &zfi2);
1805
1806     for (i1 = 0; i1 < 1 + 4 * runs; i1++) {
1807         int i2;
1808         for (i2 = 0; i2 < 1 + 4 * runs; i2++) {
1809             /* Compute reference result using gej + gej (var). */
1810             secp256k1_gej refj, resj;
1811             secp256k1_ge ref;
1812             secp256k1_fe zr;
1813             secp256k1_gej_add_var(&refj, &gej[i1], &gej[i2], secp256k1_gej_is_infinity(&gej[i1]) ? NULL : &zr);
1814             /* Check Z ratio. */
1815             if (!secp256k1_gej_is_infinity(&gej[i1]) && !secp256k1_gej_is_infinity(&refj)) {
1816                 secp256k1_fe zrz; secp256k1_fe_mul(&zrz, &zr, &gej[i1].z);
1817                 CHECK(secp256k1_fe_equal_var(&zrz, &refj.z));
1818             }
1819             secp256k1_ge_set_gej_var(&ref, &refj);
1820
1821             /* Test gej + ge with Z ratio result (var). */
1822             secp256k1_gej_add_ge_var(&resj, &gej[i1], &ge[i2], secp256k1_gej_is_infinity(&gej[i1]) ? NULL : &zr);
1823             ge_equals_gej(&ref, &resj);
1824             if (!secp256k1_gej_is_infinity(&gej[i1]) && !secp256k1_gej_is_infinity(&resj)) {
1825                 secp256k1_fe zrz; secp256k1_fe_mul(&zrz, &zr, &gej[i1].z);
1826                 CHECK(secp256k1_fe_equal_var(&zrz, &resj.z));
1827             }
1828
1829             /* Test gej + ge (var, with additional Z factor). */
1830             {
1831                 secp256k1_ge ge2_zfi = ge[i2]; /* the second term with x and y rescaled for z = 1/zf */
1832                 secp256k1_fe_mul(&ge2_zfi.x, &ge2_zfi.x, &zfi2);
1833                 secp256k1_fe_mul(&ge2_zfi.y, &ge2_zfi.y, &zfi3);
1834                 random_field_element_magnitude(&ge2_zfi.x);
1835                 random_field_element_magnitude(&ge2_zfi.y);
1836                 secp256k1_gej_add_zinv_var(&resj, &gej[i1], &ge2_zfi, &zf);
1837                 ge_equals_gej(&ref, &resj);
1838             }
1839
1840             /* Test gej + ge (const). */
1841             if (i2 != 0) {
1842                 /* secp256k1_gej_add_ge does not support its second argument being infinity. */
1843                 secp256k1_gej_add_ge(&resj, &gej[i1], &ge[i2]);
1844                 ge_equals_gej(&ref, &resj);
1845             }
1846
1847             /* Test doubling (var). */
1848             if ((i1 == 0 && i2 == 0) || ((i1 + 3)/4 == (i2 + 3)/4 && ((i1 + 3)%4)/2 == ((i2 + 3)%4)/2)) {
1849                 secp256k1_fe zr2;
1850                 /* Normal doubling with Z ratio result. */
1851                 secp256k1_gej_double_var(&resj, &gej[i1], &zr2);
1852                 ge_equals_gej(&ref, &resj);
1853                 /* Check Z ratio. */
1854                 secp256k1_fe_mul(&zr2, &zr2, &gej[i1].z);
1855                 CHECK(secp256k1_fe_equal_var(&zr2, &resj.z));
1856                 /* Normal doubling. */
1857                 secp256k1_gej_double_var(&resj, &gej[i2], NULL);
1858                 ge_equals_gej(&ref, &resj);
1859             }
1860
1861             /* Test adding opposites. */
1862             if ((i1 == 0 && i2 == 0) || ((i1 + 3)/4 == (i2 + 3)/4 && ((i1 + 3)%4)/2 != ((i2 + 3)%4)/2)) {
1863                 CHECK(secp256k1_ge_is_infinity(&ref));
1864             }
1865
1866             /* Test adding infinity. */
1867             if (i1 == 0) {
1868                 CHECK(secp256k1_ge_is_infinity(&ge[i1]));
1869                 CHECK(secp256k1_gej_is_infinity(&gej[i1]));
1870                 ge_equals_gej(&ref, &gej[i2]);
1871             }
1872             if (i2 == 0) {
1873                 CHECK(secp256k1_ge_is_infinity(&ge[i2]));
1874                 CHECK(secp256k1_gej_is_infinity(&gej[i2]));
1875                 ge_equals_gej(&ref, &gej[i1]);
1876             }
1877         }
1878     }
1879
1880     /* Test adding all points together in random order equals infinity. */
1881     {
1882         secp256k1_gej sum = SECP256K1_GEJ_CONST_INFINITY;
1883         secp256k1_gej *gej_shuffled = (secp256k1_gej *)malloc((4 * runs + 1) * sizeof(secp256k1_gej));
1884         for (i = 0; i < 4 * runs + 1; i++) {
1885             gej_shuffled[i] = gej[i];
1886         }
1887         for (i = 0; i < 4 * runs + 1; i++) {
1888             int swap = i + secp256k1_rand_int(4 * runs + 1 - i);
1889             if (swap != i) {
1890                 secp256k1_gej t = gej_shuffled[i];
1891                 gej_shuffled[i] = gej_shuffled[swap];
1892                 gej_shuffled[swap] = t;
1893             }
1894         }
1895         for (i = 0; i < 4 * runs + 1; i++) {
1896             secp256k1_gej_add_var(&sum, &sum, &gej_shuffled[i], NULL);
1897         }
1898         CHECK(secp256k1_gej_is_infinity(&sum));
1899         free(gej_shuffled);
1900     }
1901
1902     /* Test batch gej -> ge conversion with and without known z ratios. */
1903     {
1904         secp256k1_fe *zr = (secp256k1_fe *)malloc((4 * runs + 1) * sizeof(secp256k1_fe));
1905         secp256k1_ge *ge_set_table = (secp256k1_ge *)malloc((4 * runs + 1) * sizeof(secp256k1_ge));
1906         secp256k1_ge *ge_set_all = (secp256k1_ge *)malloc((4 * runs + 1) * sizeof(secp256k1_ge));
1907         for (i = 0; i < 4 * runs + 1; i++) {
1908             /* Compute gej[i + 1].z / gez[i].z (with gej[n].z taken to be 1). */
1909             if (i < 4 * runs) {
1910                 secp256k1_fe_mul(&zr[i + 1], &zinv[i], &gej[i + 1].z);
1911             }
1912         }
1913         secp256k1_ge_set_table_gej_var(4 * runs + 1, ge_set_table, gej, zr);
1914         secp256k1_ge_set_all_gej_var(4 * runs + 1, ge_set_all, gej, &ctx->error_callback);
1915         for (i = 0; i < 4 * runs + 1; i++) {
1916             secp256k1_fe s;
1917             random_fe_non_zero(&s);
1918             secp256k1_gej_rescale(&gej[i], &s);
1919             ge_equals_gej(&ge_set_table[i], &gej[i]);
1920             ge_equals_gej(&ge_set_all[i], &gej[i]);
1921         }
1922         free(ge_set_table);
1923         free(ge_set_all);
1924         free(zr);
1925     }
1926
1927     free(ge);
1928     free(gej);
1929     free(zinv);
1930 }
1931
1932 void test_add_neg_y_diff_x(void) {
1933     /* The point of this test is to check that we can add two points
1934      * whose y-coordinates are negatives of each other but whose x
1935      * coordinates differ. If the x-coordinates were the same, these
1936      * points would be negatives of each other and their sum is
1937      * infinity. This is cool because it "covers up" any degeneracy
1938      * in the addition algorithm that would cause the xy coordinates
1939      * of the sum to be wrong (since infinity has no xy coordinates).
1940      * HOWEVER, if the x-coordinates are different, infinity is the
1941      * wrong answer, and such degeneracies are exposed. This is the
1942      * root of https://github.com/bitcoin/secp256k1/issues/257 which
1943      * this test is a regression test for.
1944      *
1945      * These points were generated in sage as
1946      * # secp256k1 params
1947      * F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
1948      * C = EllipticCurve ([F (0), F (7)])
1949      * G = C.lift_x(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
1950      * N = FiniteField(G.order())
1951      *
1952      * # endomorphism values (lambda is 1^{1/3} in N, beta is 1^{1/3} in F)
1953      * x = polygen(N)
1954      * lam  = (1 - x^3).roots()[1][0]
1955      *
1956      * # random "bad pair"
1957      * P = C.random_element()
1958      * Q = -int(lam) * P
1959      * print "    P: %x %x" % P.xy()
1960      * print "    Q: %x %x" % Q.xy()
1961      * print "P + Q: %x %x" % (P + Q).xy()
1962      */
1963     secp256k1_gej aj = SECP256K1_GEJ_CONST(
1964         0x8d24cd95, 0x0a355af1, 0x3c543505, 0x44238d30,
1965         0x0643d79f, 0x05a59614, 0x2f8ec030, 0xd58977cb,
1966         0x001e337a, 0x38093dcd, 0x6c0f386d, 0x0b1293a8,
1967         0x4d72c879, 0xd7681924, 0x44e6d2f3, 0x9190117d
1968     );
1969     secp256k1_gej bj = SECP256K1_GEJ_CONST(
1970         0xc7b74206, 0x1f788cd9, 0xabd0937d, 0x164a0d86,
1971         0x95f6ff75, 0xf19a4ce9, 0xd013bd7b, 0xbf92d2a7,
1972         0xffe1cc85, 0xc7f6c232, 0x93f0c792, 0xf4ed6c57,
1973         0xb28d3786, 0x2897e6db, 0xbb192d0b, 0x6e6feab2
1974     );
1975     secp256k1_gej sumj = SECP256K1_GEJ_CONST(
1976         0x671a63c0, 0x3efdad4c, 0x389a7798, 0x24356027,
1977         0xb3d69010, 0x278625c3, 0x5c86d390, 0x184a8f7a,
1978         0x5f6409c2, 0x2ce01f2b, 0x511fd375, 0x25071d08,
1979         0xda651801, 0x70e95caf, 0x8f0d893c, 0xbed8fbbe
1980     );
1981     secp256k1_ge b;
1982     secp256k1_gej resj;
1983     secp256k1_ge res;
1984     secp256k1_ge_set_gej(&b, &bj);
1985
1986     secp256k1_gej_add_var(&resj, &aj, &bj, NULL);
1987     secp256k1_ge_set_gej(&res, &resj);
1988     ge_equals_gej(&res, &sumj);
1989
1990     secp256k1_gej_add_ge(&resj, &aj, &b);
1991     secp256k1_ge_set_gej(&res, &resj);
1992     ge_equals_gej(&res, &sumj);
1993
1994     secp256k1_gej_add_ge_var(&resj, &aj, &b, NULL);
1995     secp256k1_ge_set_gej(&res, &resj);
1996     ge_equals_gej(&res, &sumj);
1997 }
1998
1999 void run_ge(void) {
2000     int i;
2001     for (i = 0; i < count * 32; i++) {
2002         test_ge();
2003     }
2004     test_add_neg_y_diff_x();
2005 }
2006
2007 void test_ec_combine(void) {
2008     secp256k1_scalar sum = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
2009     secp256k1_pubkey data[6];
2010     const secp256k1_pubkey* d[6];
2011     secp256k1_pubkey sd;
2012     secp256k1_pubkey sd2;
2013     secp256k1_gej Qj;
2014     secp256k1_ge Q;
2015     int i;
2016     for (i = 1; i <= 6; i++) {
2017         secp256k1_scalar s;
2018         random_scalar_order_test(&s);
2019         secp256k1_scalar_add(&sum, &sum, &s);
2020         secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &Qj, &s);
2021         secp256k1_ge_set_gej(&Q, &Qj);
2022         secp256k1_pubkey_save(&data[i - 1], &Q);
2023         d[i - 1] = &data[i - 1];
2024         secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &Qj, &sum);
2025         secp256k1_ge_set_gej(&Q, &Qj);
2026         secp256k1_pubkey_save(&sd, &Q);
2027         CHECK(secp256k1_ec_pubkey_combine(ctx, &sd2, d, i) == 1);
2028         CHECK(memcmp(&sd, &sd2, sizeof(sd)) == 0);
2029     }
2030 }
2031
2032 void run_ec_combine(void) {
2033     int i;
2034     for (i = 0; i < count * 8; i++) {
2035          test_ec_combine();
2036     }
2037 }
2038
2039 /***** ECMULT TESTS *****/
2040
2041 void run_ecmult_chain(void) {
2042     /* random starting point A (on the curve) */
2043     secp256k1_gej a = SECP256K1_GEJ_CONST(
2044         0x8b30bbe9, 0xae2a9906, 0x96b22f67, 0x0709dff3,
2045         0x727fd8bc, 0x04d3362c, 0x6c7bf458, 0xe2846004,
2046         0xa357ae91, 0x5c4a6528, 0x1309edf2, 0x0504740f,
2047         0x0eb33439, 0x90216b4f, 0x81063cb6, 0x5f2f7e0f
2048     );
2049     /* two random initial factors xn and gn */
2050     secp256k1_scalar xn = SECP256K1_SCALAR_CONST(
2051         0x84cc5452, 0xf7fde1ed, 0xb4d38a8c, 0xe9b1b84c,
2052         0xcef31f14, 0x6e569be9, 0x705d357a, 0x42985407
2053     );
2054     secp256k1_scalar gn = SECP256K1_SCALAR_CONST(
2055         0xa1e58d22, 0x553dcd42, 0xb2398062, 0x5d4c57a9,
2056         0x6e9323d4, 0x2b3152e5, 0xca2c3990, 0xedc7c9de
2057     );
2058     /* two small multipliers to be applied to xn and gn in every iteration: */
2059     static const secp256k1_scalar xf = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0x1337);
2060     static const secp256k1_scalar gf = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0x7113);
2061     /* accumulators with the resulting coefficients to A and G */
2062     secp256k1_scalar ae = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1);
2063     secp256k1_scalar ge = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
2064     /* actual points */
2065     secp256k1_gej x;
2066     secp256k1_gej x2;
2067     int i;
2068
2069     /* the point being computed */
2070     x = a;
2071     for (i = 0; i < 200*count; i++) {
2072         /* in each iteration, compute X = xn*X + gn*G; */
2073         secp256k1_ecmult(&ctx->ecmult_ctx, &x, &x, &xn, &gn);
2074         /* also compute ae and ge: the actual accumulated factors for A and G */
2075         /* if X was (ae*A+ge*G), xn*X + gn*G results in (xn*ae*A + (xn*ge+gn)*G) */
2076         secp256k1_scalar_mul(&ae, &ae, &xn);
2077         secp256k1_scalar_mul(&ge, &ge, &xn);
2078         secp256k1_scalar_add(&ge, &ge, &gn);
2079         /* modify xn and gn */
2080         secp256k1_scalar_mul(&xn, &xn, &xf);
2081         secp256k1_scalar_mul(&gn, &gn, &gf);
2082
2083         /* verify */
2084         if (i == 19999) {
2085             /* expected result after 19999 iterations */
2086             secp256k1_gej rp = SECP256K1_GEJ_CONST(
2087                 0xD6E96687, 0xF9B10D09, 0x2A6F3543, 0x9D86CEBE,
2088                 0xA4535D0D, 0x409F5358, 0x6440BD74, 0xB933E830,
2089                 0xB95CBCA2, 0xC77DA786, 0x539BE8FD, 0x53354D2D,
2090                 0x3B4F566A, 0xE6580454, 0x07ED6015, 0xEE1B2A88
2091             );
2092
2093             secp256k1_gej_neg(&rp, &rp);
2094             secp256k1_gej_add_var(&rp, &rp, &x, NULL);
2095             CHECK(secp256k1_gej_is_infinity(&rp));
2096         }
2097     }
2098     /* redo the computation, but directly with the resulting ae and ge coefficients: */
2099     secp256k1_ecmult(&ctx->ecmult_ctx, &x2, &a, &ae, &ge);
2100     secp256k1_gej_neg(&x2, &x2);
2101     secp256k1_gej_add_var(&x2, &x2, &x, NULL);
2102     CHECK(secp256k1_gej_is_infinity(&x2));
2103 }
2104
2105 void test_point_times_order(const secp256k1_gej *point) {
2106     /* X * (point + G) + (order-X) * (pointer + G) = 0 */
2107     secp256k1_scalar x;
2108     secp256k1_scalar nx;
2109     secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
2110     secp256k1_scalar one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1);
2111     secp256k1_gej res1, res2;
2112     secp256k1_ge res3;
2113     unsigned char pub[65];
2114     size_t psize = 65;
2115     random_scalar_order_test(&x);
2116     secp256k1_scalar_negate(&nx, &x);
2117     secp256k1_ecmult(&ctx->ecmult_ctx, &res1, point, &x, &x); /* calc res1 = x * point + x * G; */
2118     secp256k1_ecmult(&ctx->ecmult_ctx, &res2, point, &nx, &nx); /* calc res2 = (order - x) * point + (order - x) * G; */
2119     secp256k1_gej_add_var(&res1, &res1, &res2, NULL);
2120     CHECK(secp256k1_gej_is_infinity(&res1));
2121     CHECK(secp256k1_gej_is_valid_var(&res1) == 0);
2122     secp256k1_ge_set_gej(&res3, &res1);
2123     CHECK(secp256k1_ge_is_infinity(&res3));
2124     CHECK(secp256k1_ge_is_valid_var(&res3) == 0);
2125     CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 0) == 0);
2126     psize = 65;
2127     CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 1) == 0);
2128     /* check zero/one edge cases */
2129     secp256k1_ecmult(&ctx->ecmult_ctx, &res1, point, &zero, &zero);
2130     secp256k1_ge_set_gej(&res3, &res1);
2131     CHECK(secp256k1_ge_is_infinity(&res3));
2132     secp256k1_ecmult(&ctx->ecmult_ctx, &res1, point, &one, &zero);
2133     secp256k1_ge_set_gej(&res3, &res1);
2134     ge_equals_gej(&res3, point);
2135     secp256k1_ecmult(&ctx->ecmult_ctx, &res1, point, &zero, &one);
2136     secp256k1_ge_set_gej(&res3, &res1);
2137     ge_equals_ge(&res3, &secp256k1_ge_const_g);
2138 }
2139
2140 void run_point_times_order(void) {
2141     int i;
2142     secp256k1_fe x = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 2);
2143     static const secp256k1_fe xr = SECP256K1_FE_CONST(
2144         0x7603CB59, 0xB0EF6C63, 0xFE608479, 0x2A0C378C,
2145         0xDB3233A8, 0x0F8A9A09, 0xA877DEAD, 0x31B38C45
2146     );
2147     for (i = 0; i < 500; i++) {
2148         secp256k1_ge p;
2149         if (secp256k1_ge_set_xo_var(&p, &x, 1)) {
2150             secp256k1_gej j;
2151             CHECK(secp256k1_ge_is_valid_var(&p));
2152             secp256k1_gej_set_ge(&j, &p);
2153             CHECK(secp256k1_gej_is_valid_var(&j));
2154             test_point_times_order(&j);
2155         }
2156         secp256k1_fe_sqr(&x, &x);
2157     }
2158     secp256k1_fe_normalize_var(&x);
2159     CHECK(secp256k1_fe_equal_var(&x, &xr));
2160 }
2161
2162 void ecmult_const_random_mult(void) {
2163     /* random starting point A (on the curve) */
2164     secp256k1_ge a = SECP256K1_GE_CONST(
2165         0x6d986544, 0x57ff52b8, 0xcf1b8126, 0x5b802a5b,
2166         0xa97f9263, 0xb1e88044, 0x93351325, 0x91bc450a,
2167         0x535c59f7, 0x325e5d2b, 0xc391fbe8, 0x3c12787c,
2168         0x337e4a98, 0xe82a9011, 0x0123ba37, 0xdd769c7d
2169     );
2170     /* random initial factor xn */
2171     secp256k1_scalar xn = SECP256K1_SCALAR_CONST(
2172         0x649d4f77, 0xc4242df7, 0x7f2079c9, 0x14530327,
2173         0xa31b876a, 0xd2d8ce2a, 0x2236d5c6, 0xd7b2029b
2174     );
2175     /* expected xn * A (from sage) */
2176     secp256k1_ge expected_b = SECP256K1_GE_CONST(
2177         0x23773684, 0x4d209dc7, 0x098a786f, 0x20d06fcd,
2178         0x070a38bf, 0xc11ac651, 0x03004319, 0x1e2a8786,
2179         0xed8c3b8e, 0xc06dd57b, 0xd06ea66e, 0x45492b0f,
2180         0xb84e4e1b, 0xfb77e21f, 0x96baae2a, 0x63dec956
2181     );
2182     secp256k1_gej b;
2183     secp256k1_ecmult_const(&b, &a, &xn);
2184
2185     CHECK(secp256k1_ge_is_valid_var(&a));
2186     ge_equals_gej(&expected_b, &b);
2187 }
2188
2189 void ecmult_const_commutativity(void) {
2190     secp256k1_scalar a;
2191     secp256k1_scalar b;
2192     secp256k1_gej res1;
2193     secp256k1_gej res2;
2194     secp256k1_ge mid1;
2195     secp256k1_ge mid2;
2196     random_scalar_order_test(&a);
2197     random_scalar_order_test(&b);
2198
2199     secp256k1_ecmult_const(&res1, &secp256k1_ge_const_g, &a);
2200     secp256k1_ecmult_const(&res2, &secp256k1_ge_const_g, &b);
2201     secp256k1_ge_set_gej(&mid1, &res1);
2202     secp256k1_ge_set_gej(&mid2, &res2);
2203     secp256k1_ecmult_const(&res1, &mid1, &b);
2204     secp256k1_ecmult_const(&res2, &mid2, &a);
2205     secp256k1_ge_set_gej(&mid1, &res1);
2206     secp256k1_ge_set_gej(&mid2, &res2);
2207     ge_equals_ge(&mid1, &mid2);
2208 }
2209
2210 void ecmult_const_mult_zero_one(void) {
2211     secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
2212     secp256k1_scalar one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1);
2213     secp256k1_scalar negone;
2214     secp256k1_gej res1;
2215     secp256k1_ge res2;
2216     secp256k1_ge point;
2217     secp256k1_scalar_negate(&negone, &one);
2218
2219     random_group_element_test(&point);
2220     secp256k1_ecmult_const(&res1, &point, &zero);
2221     secp256k1_ge_set_gej(&res2, &res1);
2222     CHECK(secp256k1_ge_is_infinity(&res2));
2223     secp256k1_ecmult_const(&res1, &point, &one);
2224     secp256k1_ge_set_gej(&res2, &res1);
2225     ge_equals_ge(&res2, &point);
2226     secp256k1_ecmult_const(&res1, &point, &negone);
2227     secp256k1_gej_neg(&res1, &res1);
2228     secp256k1_ge_set_gej(&res2, &res1);
2229     ge_equals_ge(&res2, &point);
2230 }
2231
2232 void ecmult_const_chain_multiply(void) {
2233     /* Check known result (randomly generated test problem from sage) */
2234     const secp256k1_scalar scalar = SECP256K1_SCALAR_CONST(
2235         0x4968d524, 0x2abf9b7a, 0x466abbcf, 0x34b11b6d,
2236         0xcd83d307, 0x827bed62, 0x05fad0ce, 0x18fae63b
2237     );
2238     const secp256k1_gej expected_point = SECP256K1_GEJ_CONST(
2239         0x5494c15d, 0x32099706, 0xc2395f94, 0x348745fd,
2240         0x757ce30e, 0x4e8c90fb, 0xa2bad184, 0xf883c69f,
2241         0x5d195d20, 0xe191bf7f, 0x1be3e55f, 0x56a80196,
2242         0x6071ad01, 0xf1462f66, 0xc997fa94, 0xdb858435
2243     );
2244     secp256k1_gej point;
2245     secp256k1_ge res;
2246     int i;
2247
2248     secp256k1_gej_set_ge(&point, &secp256k1_ge_const_g);
2249     for (i = 0; i < 100; ++i) {
2250         secp256k1_ge tmp;
2251         secp256k1_ge_set_gej(&tmp, &point);
2252         secp256k1_ecmult_const(&point, &tmp, &scalar);
2253     }
2254     secp256k1_ge_set_gej(&res, &point);
2255     ge_equals_gej(&res, &expected_point);
2256 }
2257
2258 void run_ecmult_const_tests(void) {
2259     ecmult_const_mult_zero_one();
2260     ecmult_const_random_mult();
2261     ecmult_const_commutativity();
2262     ecmult_const_chain_multiply();
2263 }
2264
2265 void test_wnaf(const secp256k1_scalar *number, int w) {
2266     secp256k1_scalar x, two, t;
2267     int wnaf[256];
2268     int zeroes = -1;
2269     int i;
2270     int bits;
2271     secp256k1_scalar_set_int(&x, 0);
2272     secp256k1_scalar_set_int(&two, 2);
2273     bits = secp256k1_ecmult_wnaf(wnaf, 256, number, w);
2274     CHECK(bits <= 256);
2275     for (i = bits-1; i >= 0; i--) {
2276         int v = wnaf[i];
2277         secp256k1_scalar_mul(&x, &x, &two);
2278         if (v) {
2279             CHECK(zeroes == -1 || zeroes >= w-1); /* check that distance between non-zero elements is at least w-1 */
2280             zeroes=0;
2281             CHECK((v & 1) == 1); /* check non-zero elements are odd */
2282             CHECK(v <= (1 << (w-1)) - 1); /* check range below */
2283             CHECK(v >= -(1 << (w-1)) - 1); /* check range above */
2284         } else {
2285             CHECK(zeroes != -1); /* check that no unnecessary zero padding exists */
2286             zeroes++;
2287         }
2288         if (v >= 0) {
2289             secp256k1_scalar_set_int(&t, v);
2290         } else {
2291             secp256k1_scalar_set_int(&t, -v);
2292             secp256k1_scalar_negate(&t, &t);
2293         }
2294         secp256k1_scalar_add(&x, &x, &t);
2295     }
2296     CHECK(secp256k1_scalar_eq(&x, number)); /* check that wnaf represents number */
2297 }
2298
2299 void test_constant_wnaf_negate(const secp256k1_scalar *number) {
2300     secp256k1_scalar neg1 = *number;
2301     secp256k1_scalar neg2 = *number;
2302     int sign1 = 1;
2303     int sign2 = 1;
2304
2305     if (!secp256k1_scalar_get_bits(&neg1, 0, 1)) {
2306         secp256k1_scalar_negate(&neg1, &neg1);
2307         sign1 = -1;
2308     }
2309     sign2 = secp256k1_scalar_cond_negate(&neg2, secp256k1_scalar_is_even(&neg2));
2310     CHECK(sign1 == sign2);
2311     CHECK(secp256k1_scalar_eq(&neg1, &neg2));
2312 }
2313
2314 void test_constant_wnaf(const secp256k1_scalar *number, int w) {
2315     secp256k1_scalar x, shift;
2316     int wnaf[256] = {0};
2317     int i;
2318 #ifdef USE_ENDOMORPHISM
2319     int skew;
2320 #endif
2321     secp256k1_scalar num = *number;
2322
2323     secp256k1_scalar_set_int(&x, 0);
2324     secp256k1_scalar_set_int(&shift, 1 << w);
2325     /* With USE_ENDOMORPHISM on we only consider 128-bit numbers */
2326 #ifdef USE_ENDOMORPHISM
2327     for (i = 0; i < 16; ++i) {
2328         secp256k1_scalar_shr_int(&num, 8);
2329     }
2330     skew = secp256k1_wnaf_const(wnaf, num, w);
2331 #else
2332     secp256k1_wnaf_const(wnaf, num, w);
2333 #endif
2334
2335     for (i = WNAF_SIZE(w); i >= 0; --i) {
2336         secp256k1_scalar t;
2337         int v = wnaf[i];
2338         CHECK(v != 0); /* check nonzero */
2339         CHECK(v & 1);  /* check parity */
2340         CHECK(v > -(1 << w)); /* check range above */
2341         CHECK(v < (1 << w));  /* check range below */
2342
2343         secp256k1_scalar_mul(&x, &x, &shift);
2344         if (v >= 0) {
2345             secp256k1_scalar_set_int(&t, v);
2346         } else {
2347             secp256k1_scalar_set_int(&t, -v);
2348             secp256k1_scalar_negate(&t, &t);
2349         }
2350         secp256k1_scalar_add(&x, &x, &t);
2351     }
2352 #ifdef USE_ENDOMORPHISM
2353     /* Skew num because when encoding 128-bit numbers as odd we use an offset */
2354     secp256k1_scalar_cadd_bit(&num, skew == 2, 1);
2355 #endif
2356     CHECK(secp256k1_scalar_eq(&x, &num));
2357 }
2358
2359 void run_wnaf(void) {
2360     int i;
2361     secp256k1_scalar n = {{0}};
2362
2363     /* Sanity check: 1 and 2 are the smallest odd and even numbers and should
2364      *               have easier-to-diagnose failure modes  */
2365     n.d[0] = 1;
2366     test_constant_wnaf(&n, 4);
2367     n.d[0] = 2;
2368     test_constant_wnaf(&n, 4);
2369     /* Random tests */
2370     for (i = 0; i < count; i++) {
2371         random_scalar_order(&n);
2372         test_wnaf(&n, 4+(i%10));
2373         test_constant_wnaf_negate(&n);
2374         test_constant_wnaf(&n, 4 + (i % 10));
2375     }
2376     secp256k1_scalar_set_int(&n, 0);
2377     CHECK(secp256k1_scalar_cond_negate(&n, 1) == -1);
2378     CHECK(secp256k1_scalar_is_zero(&n));
2379     CHECK(secp256k1_scalar_cond_negate(&n, 0) == 1);
2380     CHECK(secp256k1_scalar_is_zero(&n));
2381 }
2382
2383 void test_ecmult_constants(void) {
2384     /* Test ecmult_gen() for [0..36) and [order-36..0). */
2385     secp256k1_scalar x;
2386     secp256k1_gej r;
2387     secp256k1_ge ng;
2388     int i;
2389     int j;
2390     secp256k1_ge_neg(&ng, &secp256k1_ge_const_g);
2391     for (i = 0; i < 36; i++ ) {
2392         secp256k1_scalar_set_int(&x, i);
2393         secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &r, &x);
2394         for (j = 0; j < i; j++) {
2395             if (j == i - 1) {
2396                 ge_equals_gej(&secp256k1_ge_const_g, &r);
2397             }
2398             secp256k1_gej_add_ge(&r, &r, &ng);
2399         }
2400         CHECK(secp256k1_gej_is_infinity(&r));
2401     }
2402     for (i = 1; i <= 36; i++ ) {
2403         secp256k1_scalar_set_int(&x, i);
2404         secp256k1_scalar_negate(&x, &x);
2405         secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &r, &x);
2406         for (j = 0; j < i; j++) {
2407             if (j == i - 1) {
2408                 ge_equals_gej(&ng, &r);
2409             }
2410             secp256k1_gej_add_ge(&r, &r, &secp256k1_ge_const_g);
2411         }
2412         CHECK(secp256k1_gej_is_infinity(&r));
2413     }
2414 }
2415
2416 void run_ecmult_constants(void) {
2417     test_ecmult_constants();
2418 }
2419
2420 void test_ecmult_gen_blind(void) {
2421     /* Test ecmult_gen() blinding and confirm that the blinding changes, the affline points match, and the z's don't match. */
2422     secp256k1_scalar key;
2423     secp256k1_scalar b;
2424     unsigned char seed32[32];
2425     secp256k1_gej pgej;
2426     secp256k1_gej pgej2;
2427     secp256k1_gej i;
2428     secp256k1_ge pge;
2429     random_scalar_order_test(&key);
2430     secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pgej, &key);
2431     secp256k1_rand256(seed32);
2432     b = ctx->ecmult_gen_ctx.blind;
2433     i = ctx->ecmult_gen_ctx.initial;
2434     secp256k1_ecmult_gen_blind(&ctx->ecmult_gen_ctx, seed32);
2435     CHECK(!secp256k1_scalar_eq(&b, &ctx->ecmult_gen_ctx.blind));
2436     secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pgej2, &key);
2437     CHECK(!gej_xyz_equals_gej(&pgej, &pgej2));
2438     CHECK(!gej_xyz_equals_gej(&i, &ctx->ecmult_gen_ctx.initial));
2439     secp256k1_ge_set_gej(&pge, &pgej);
2440     ge_equals_gej(&pge, &pgej2);
2441 }
2442
2443 void test_ecmult_gen_blind_reset(void) {
2444     /* Test ecmult_gen() blinding reset and confirm that the blinding is consistent. */
2445     secp256k1_scalar b;
2446     secp256k1_gej initial;
2447     secp256k1_ecmult_gen_blind(&ctx->ecmult_gen_ctx, 0);
2448     b = ctx->ecmult_gen_ctx.blind;
2449     initial = ctx->ecmult_gen_ctx.initial;
2450     secp256k1_ecmult_gen_blind(&ctx->ecmult_gen_ctx, 0);
2451     CHECK(secp256k1_scalar_eq(&b, &ctx->ecmult_gen_ctx.blind));
2452     CHECK(gej_xyz_equals_gej(&initial, &ctx->ecmult_gen_ctx.initial));
2453 }
2454
2455 void run_ecmult_gen_blind(void) {
2456     int i;
2457     test_ecmult_gen_blind_reset();
2458     for (i = 0; i < 10; i++) {
2459         test_ecmult_gen_blind();
2460     }
2461 }
2462
2463 #ifdef USE_ENDOMORPHISM
2464 /***** ENDOMORPHISH TESTS *****/
2465 void test_scalar_split(void) {
2466     secp256k1_scalar full;
2467     secp256k1_scalar s1, slam;
2468     const unsigned char zero[32] = {0};
2469     unsigned char tmp[32];
2470
2471     random_scalar_order_test(&full);
2472     secp256k1_scalar_split_lambda(&s1, &slam, &full);
2473
2474     /* check that both are <= 128 bits in size */
2475     if (secp256k1_scalar_is_high(&s1)) {
2476         secp256k1_scalar_negate(&s1, &s1);
2477     }
2478     if (secp256k1_scalar_is_high(&slam)) {
2479         secp256k1_scalar_negate(&slam, &slam);
2480     }
2481
2482     secp256k1_scalar_get_b32(tmp, &s1);
2483     CHECK(memcmp(zero, tmp, 16) == 0);
2484     secp256k1_scalar_get_b32(tmp, &slam);
2485     CHECK(memcmp(zero, tmp, 16) == 0);
2486 }
2487
2488 void run_endomorphism_tests(void) {
2489     test_scalar_split();
2490 }
2491 #endif
2492
2493 void ec_pubkey_parse_pointtest(const unsigned char *input, int xvalid, int yvalid) {
2494     unsigned char pubkeyc[65];
2495     secp256k1_pubkey pubkey;
2496     secp256k1_ge ge;
2497     size_t pubkeyclen;
2498     int32_t ecount;
2499     ecount = 0;
2500     secp256k1_context_set_illegal_callback(ctx, counting_illegal_callback_fn, &ecount);
2501     for (pubkeyclen = 3; pubkeyclen <= 65; pubkeyclen++) {
2502         /* Smaller sizes are tested exhaustively elsewhere. */
2503         int32_t i;
2504         memcpy(&pubkeyc[1], input, 64);
2505         VG_UNDEF(&pubkeyc[pubkeyclen], 65 - pubkeyclen);
2506         for (i = 0; i < 256; i++) {
2507             /* Try all type bytes. */
2508             int xpass;
2509             int ypass;
2510             int ysign;
2511             pubkeyc[0] = i;
2512             /* What sign does this point have? */
2513             ysign = (input[63] & 1) + 2;
2514             /* For the current type (i) do we expect parsing to work? Handled all of compressed/uncompressed/hybrid. */
2515             xpass = xvalid && (pubkeyclen == 33) && ((i & 254) == 2);
2516             /* Do we expect a parse and re-serialize as uncompressed to give a matching y? */
2517             ypass = xvalid && yvalid && ((i & 4) == ((pubkeyclen == 65) << 2)) &&
2518                 ((i == 4) || ((i & 251) == ysign)) && ((pubkeyclen == 33) || (pubkeyclen == 65));
2519             if (xpass || ypass) {
2520                 /* These cases must parse. */
2521                 unsigned char pubkeyo[65];
2522                 size_t outl;
2523                 memset(&pubkey, 0, sizeof(pubkey));
2524                 VG_UNDEF(&pubkey, sizeof(pubkey));
2525                 ecount = 0;
2526                 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, pubkeyclen) == 1);
2527                 VG_CHECK(&pubkey, sizeof(pubkey));
2528                 outl = 65;
2529                 VG_UNDEF(pubkeyo, 65);
2530                 CHECK(secp256k1_ec_pubkey_serialize(ctx, pubkeyo, &outl, &pubkey, SECP256K1_EC_COMPRESSED) == 1);
2531                 VG_CHECK(pubkeyo, outl);
2532                 CHECK(outl == 33);
2533                 CHECK(memcmp(&pubkeyo[1], &pubkeyc[1], 32) == 0);
2534                 CHECK((pubkeyclen != 33) || (pubkeyo[0] == pubkeyc[0]));
2535                 if (ypass) {
2536                     /* This test isn't always done because we decode with alternative signs, so the y won't match. */
2537                     CHECK(pubkeyo[0] == ysign);
2538                     CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 1);
2539                     memset(&pubkey, 0, sizeof(pubkey));
2540                     VG_UNDEF(&pubkey, sizeof(pubkey));
2541                     secp256k1_pubkey_save(&pubkey, &ge);
2542                     VG_CHECK(&pubkey, sizeof(pubkey));
2543                     outl = 65;
2544                     VG_UNDEF(pubkeyo, 65);
2545                     CHECK(secp256k1_ec_pubkey_serialize(ctx, pubkeyo, &outl, &pubkey, SECP256K1_EC_UNCOMPRESSED) == 1);
2546                     VG_CHECK(pubkeyo, outl);
2547                     CHECK(outl == 65);
2548                     CHECK(pubkeyo[0] == 4);
2549                     CHECK(memcmp(&pubkeyo[1], input, 64) == 0);
2550                 }
2551                 CHECK(ecount == 0);
2552             } else {
2553                 /* These cases must fail to parse. */
2554                 memset(&pubkey, 0xfe, sizeof(pubkey));
2555                 ecount = 0;
2556                 VG_UNDEF(&pubkey, sizeof(pubkey));
2557                 CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, pubkeyclen) == 0);
2558                 VG_CHECK(&pubkey, sizeof(pubkey));
2559                 CHECK(ecount == 0);
2560                 CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2561                 CHECK(ecount == 1);
2562             }
2563         }
2564     }
2565     secp256k1_context_set_illegal_callback(ctx, NULL, NULL);
2566 }
2567
2568 void run_ec_pubkey_parse_test(void) {
2569 #define SECP256K1_EC_PARSE_TEST_NVALID (12)
2570     const unsigned char valid[SECP256K1_EC_PARSE_TEST_NVALID][64] = {
2571         {
2572             /* Point with leading and trailing zeros in x and y serialization. */
2573             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x42, 0x52,
2574             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2575             0x00, 0x00, 0x64, 0xef, 0xa1, 0x7b, 0x77, 0x61, 0xe1, 0xe4, 0x27, 0x06, 0x98, 0x9f, 0xb4, 0x83,
2576             0xb8, 0xd2, 0xd4, 0x9b, 0xf7, 0x8f, 0xae, 0x98, 0x03, 0xf0, 0x99, 0xb8, 0x34, 0xed, 0xeb, 0x00
2577         },
2578         {
2579             /* Point with x equal to a 3rd root of unity.*/
2580             0x7a, 0xe9, 0x6a, 0x2b, 0x65, 0x7c, 0x07, 0x10, 0x6e, 0x64, 0x47, 0x9e, 0xac, 0x34, 0x34, 0xe9,
2581             0x9c, 0xf0, 0x49, 0x75, 0x12, 0xf5, 0x89, 0x95, 0xc1, 0x39, 0x6c, 0x28, 0x71, 0x95, 0x01, 0xee,
2582             0x42, 0x18, 0xf2, 0x0a, 0xe6, 0xc6, 0x46, 0xb3, 0x63, 0xdb, 0x68, 0x60, 0x58, 0x22, 0xfb, 0x14,
2583             0x26, 0x4c, 0xa8, 0xd2, 0x58, 0x7f, 0xdd, 0x6f, 0xbc, 0x75, 0x0d, 0x58, 0x7e, 0x76, 0xa7, 0xee,
2584         },
2585         {
2586             /* Point with largest x. (1/2) */
2587             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2588             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2c,
2589             0x0e, 0x99, 0x4b, 0x14, 0xea, 0x72, 0xf8, 0xc3, 0xeb, 0x95, 0xc7, 0x1e, 0xf6, 0x92, 0x57, 0x5e,
2590             0x77, 0x50, 0x58, 0x33, 0x2d, 0x7e, 0x52, 0xd0, 0x99, 0x5c, 0xf8, 0x03, 0x88, 0x71, 0xb6, 0x7d,
2591         },
2592         {
2593             /* Point with largest x. (2/2) */
2594             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2595             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2c,
2596             0xf1, 0x66, 0xb4, 0xeb, 0x15, 0x8d, 0x07, 0x3c, 0x14, 0x6a, 0x38, 0xe1, 0x09, 0x6d, 0xa8, 0xa1,
2597             0x88, 0xaf, 0xa7, 0xcc, 0xd2, 0x81, 0xad, 0x2f, 0x66, 0xa3, 0x07, 0xfb, 0x77, 0x8e, 0x45, 0xb2,
2598         },
2599         {
2600             /* Point with smallest x. (1/2) */
2601             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2602             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2603             0x42, 0x18, 0xf2, 0x0a, 0xe6, 0xc6, 0x46, 0xb3, 0x63, 0xdb, 0x68, 0x60, 0x58, 0x22, 0xfb, 0x14,
2604             0x26, 0x4c, 0xa8, 0xd2, 0x58, 0x7f, 0xdd, 0x6f, 0xbc, 0x75, 0x0d, 0x58, 0x7e, 0x76, 0xa7, 0xee,
2605         },
2606         {
2607             /* Point with smallest x. (2/2) */
2608             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2609             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2610             0xbd, 0xe7, 0x0d, 0xf5, 0x19, 0x39, 0xb9, 0x4c, 0x9c, 0x24, 0x97, 0x9f, 0xa7, 0xdd, 0x04, 0xeb,
2611             0xd9, 0xb3, 0x57, 0x2d, 0xa7, 0x80, 0x22, 0x90, 0x43, 0x8a, 0xf2, 0xa6, 0x81, 0x89, 0x54, 0x41,
2612         },
2613         {
2614             /* Point with largest y. (1/3) */
2615             0x1f, 0xe1, 0xe5, 0xef, 0x3f, 0xce, 0xb5, 0xc1, 0x35, 0xab, 0x77, 0x41, 0x33, 0x3c, 0xe5, 0xa6,
2616             0xe8, 0x0d, 0x68, 0x16, 0x76, 0x53, 0xf6, 0xb2, 0xb2, 0x4b, 0xcb, 0xcf, 0xaa, 0xaf, 0xf5, 0x07,
2617             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2618             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2619         },
2620         {
2621             /* Point with largest y. (2/3) */
2622             0xcb, 0xb0, 0xde, 0xab, 0x12, 0x57, 0x54, 0xf1, 0xfd, 0xb2, 0x03, 0x8b, 0x04, 0x34, 0xed, 0x9c,
2623             0xb3, 0xfb, 0x53, 0xab, 0x73, 0x53, 0x91, 0x12, 0x99, 0x94, 0xa5, 0x35, 0xd9, 0x25, 0xf6, 0x73,
2624             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2625             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2626         },
2627         {
2628             /* Point with largest y. (3/3) */
2629             0x14, 0x6d, 0x3b, 0x65, 0xad, 0xd9, 0xf5, 0x4c, 0xcc, 0xa2, 0x85, 0x33, 0xc8, 0x8e, 0x2c, 0xbc,
2630             0x63, 0xf7, 0x44, 0x3e, 0x16, 0x58, 0x78, 0x3a, 0xb4, 0x1f, 0x8e, 0xf9, 0x7c, 0x2a, 0x10, 0xb5,
2631             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2632             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2633         },
2634         {
2635             /* Point with smallest y. (1/3) */
2636             0x1f, 0xe1, 0xe5, 0xef, 0x3f, 0xce, 0xb5, 0xc1, 0x35, 0xab, 0x77, 0x41, 0x33, 0x3c, 0xe5, 0xa6,
2637             0xe8, 0x0d, 0x68, 0x16, 0x76, 0x53, 0xf6, 0xb2, 0xb2, 0x4b, 0xcb, 0xcf, 0xaa, 0xaf, 0xf5, 0x07,
2638             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2639             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2640         },
2641         {
2642             /* Point with smallest y. (2/3) */
2643             0xcb, 0xb0, 0xde, 0xab, 0x12, 0x57, 0x54, 0xf1, 0xfd, 0xb2, 0x03, 0x8b, 0x04, 0x34, 0xed, 0x9c,
2644             0xb3, 0xfb, 0x53, 0xab, 0x73, 0x53, 0x91, 0x12, 0x99, 0x94, 0xa5, 0x35, 0xd9, 0x25, 0xf6, 0x73,
2645             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2646             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2647         },
2648         {
2649             /* Point with smallest y. (3/3) */
2650             0x14, 0x6d, 0x3b, 0x65, 0xad, 0xd9, 0xf5, 0x4c, 0xcc, 0xa2, 0x85, 0x33, 0xc8, 0x8e, 0x2c, 0xbc,
2651             0x63, 0xf7, 0x44, 0x3e, 0x16, 0x58, 0x78, 0x3a, 0xb4, 0x1f, 0x8e, 0xf9, 0x7c, 0x2a, 0x10, 0xb5,
2652             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2653             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01
2654         }
2655     };
2656 #define SECP256K1_EC_PARSE_TEST_NXVALID (4)
2657     const unsigned char onlyxvalid[SECP256K1_EC_PARSE_TEST_NXVALID][64] = {
2658         {
2659             /* Valid if y overflow ignored (y = 1 mod p). (1/3) */
2660             0x1f, 0xe1, 0xe5, 0xef, 0x3f, 0xce, 0xb5, 0xc1, 0x35, 0xab, 0x77, 0x41, 0x33, 0x3c, 0xe5, 0xa6,
2661             0xe8, 0x0d, 0x68, 0x16, 0x76, 0x53, 0xf6, 0xb2, 0xb2, 0x4b, 0xcb, 0xcf, 0xaa, 0xaf, 0xf5, 0x07,
2662             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2663             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2664         },
2665         {
2666             /* Valid if y overflow ignored (y = 1 mod p). (2/3) */
2667             0xcb, 0xb0, 0xde, 0xab, 0x12, 0x57, 0x54, 0xf1, 0xfd, 0xb2, 0x03, 0x8b, 0x04, 0x34, 0xed, 0x9c,
2668             0xb3, 0xfb, 0x53, 0xab, 0x73, 0x53, 0x91, 0x12, 0x99, 0x94, 0xa5, 0x35, 0xd9, 0x25, 0xf6, 0x73,
2669             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2670             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2671         },
2672         {
2673             /* Valid if y overflow ignored (y = 1 mod p). (3/3)*/
2674             0x14, 0x6d, 0x3b, 0x65, 0xad, 0xd9, 0xf5, 0x4c, 0xcc, 0xa2, 0x85, 0x33, 0xc8, 0x8e, 0x2c, 0xbc,
2675             0x63, 0xf7, 0x44, 0x3e, 0x16, 0x58, 0x78, 0x3a, 0xb4, 0x1f, 0x8e, 0xf9, 0x7c, 0x2a, 0x10, 0xb5,
2676             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2677             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2678         },
2679         {
2680             /* x on curve, y is from y^2 = x^3 + 8. */
2681             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2682             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2683             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2684             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03
2685         }
2686     };
2687 #define SECP256K1_EC_PARSE_TEST_NINVALID (7)
2688     const unsigned char invalid[SECP256K1_EC_PARSE_TEST_NINVALID][64] = {
2689         {
2690             /* x is third root of -8, y is -1 * (x^3+7); also on the curve for y^2 = x^3 + 9. */
2691             0x0a, 0x2d, 0x2b, 0xa9, 0x35, 0x07, 0xf1, 0xdf, 0x23, 0x37, 0x70, 0xc2, 0xa7, 0x97, 0x96, 0x2c,
2692             0xc6, 0x1f, 0x6d, 0x15, 0xda, 0x14, 0xec, 0xd4, 0x7d, 0x8d, 0x27, 0xae, 0x1c, 0xd5, 0xf8, 0x53,
2693             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2694             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
2695         },
2696         {
2697             /* Valid if x overflow ignored (x = 1 mod p). */
2698             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2699             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2700             0x42, 0x18, 0xf2, 0x0a, 0xe6, 0xc6, 0x46, 0xb3, 0x63, 0xdb, 0x68, 0x60, 0x58, 0x22, 0xfb, 0x14,
2701             0x26, 0x4c, 0xa8, 0xd2, 0x58, 0x7f, 0xdd, 0x6f, 0xbc, 0x75, 0x0d, 0x58, 0x7e, 0x76, 0xa7, 0xee,
2702         },
2703         {
2704             /* Valid if x overflow ignored (x = 1 mod p). */
2705             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2706             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x30,
2707             0xbd, 0xe7, 0x0d, 0xf5, 0x19, 0x39, 0xb9, 0x4c, 0x9c, 0x24, 0x97, 0x9f, 0xa7, 0xdd, 0x04, 0xeb,
2708             0xd9, 0xb3, 0x57, 0x2d, 0xa7, 0x80, 0x22, 0x90, 0x43, 0x8a, 0xf2, 0xa6, 0x81, 0x89, 0x54, 0x41,
2709         },
2710         {
2711             /* x is -1, y is the result of the sqrt ladder; also on the curve for y^2 = x^3 - 5. */
2712             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2713             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2714             0xf4, 0x84, 0x14, 0x5c, 0xb0, 0x14, 0x9b, 0x82, 0x5d, 0xff, 0x41, 0x2f, 0xa0, 0x52, 0xa8, 0x3f,
2715             0xcb, 0x72, 0xdb, 0x61, 0xd5, 0x6f, 0x37, 0x70, 0xce, 0x06, 0x6b, 0x73, 0x49, 0xa2, 0xaa, 0x28,
2716         },
2717         {
2718             /* x is -1, y is the result of the sqrt ladder; also on the curve for y^2 = x^3 - 5. */
2719             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2720             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2e,
2721             0x0b, 0x7b, 0xeb, 0xa3, 0x4f, 0xeb, 0x64, 0x7d, 0xa2, 0x00, 0xbe, 0xd0, 0x5f, 0xad, 0x57, 0xc0,
2722             0x34, 0x8d, 0x24, 0x9e, 0x2a, 0x90, 0xc8, 0x8f, 0x31, 0xf9, 0x94, 0x8b, 0xb6, 0x5d, 0x52, 0x07,
2723         },
2724         {
2725             /* x is zero, y is the result of the sqrt ladder; also on the curve for y^2 = x^3 - 7. */
2726             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2727             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2728             0x8f, 0x53, 0x7e, 0xef, 0xdf, 0xc1, 0x60, 0x6a, 0x07, 0x27, 0xcd, 0x69, 0xb4, 0xa7, 0x33, 0x3d,
2729             0x38, 0xed, 0x44, 0xe3, 0x93, 0x2a, 0x71, 0x79, 0xee, 0xcb, 0x4b, 0x6f, 0xba, 0x93, 0x60, 0xdc,
2730         },
2731         {
2732             /* x is zero, y is the result of the sqrt ladder; also on the curve for y^2 = x^3 - 7. */
2733             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2734             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2735             0x70, 0xac, 0x81, 0x10, 0x20, 0x3e, 0x9f, 0x95, 0xf8, 0xd8, 0x32, 0x96, 0x4b, 0x58, 0xcc, 0xc2,
2736             0xc7, 0x12, 0xbb, 0x1c, 0x6c, 0xd5, 0x8e, 0x86, 0x11, 0x34, 0xb4, 0x8f, 0x45, 0x6c, 0x9b, 0x53
2737         }
2738     };
2739     const unsigned char pubkeyc[66] = {
2740         /* Serialization of G. */
2741         0x04, 0x79, 0xBE, 0x66, 0x7E, 0xF9, 0xDC, 0xBB, 0xAC, 0x55, 0xA0, 0x62, 0x95, 0xCE, 0x87, 0x0B,
2742         0x07, 0x02, 0x9B, 0xFC, 0xDB, 0x2D, 0xCE, 0x28, 0xD9, 0x59, 0xF2, 0x81, 0x5B, 0x16, 0xF8, 0x17,
2743         0x98, 0x48, 0x3A, 0xDA, 0x77, 0x26, 0xA3, 0xC4, 0x65, 0x5D, 0xA4, 0xFB, 0xFC, 0x0E, 0x11, 0x08,
2744         0xA8, 0xFD, 0x17, 0xB4, 0x48, 0xA6, 0x85, 0x54, 0x19, 0x9C, 0x47, 0xD0, 0x8F, 0xFB, 0x10, 0xD4,
2745         0xB8, 0x00
2746     };
2747     unsigned char shortkey[2];
2748     secp256k1_ge ge;
2749     secp256k1_pubkey pubkey;
2750     int32_t i;
2751     int32_t ecount;
2752     int32_t ecount2;
2753     ecount = 0;
2754     /* Nothing should be reading this far into pubkeyc. */
2755     VG_UNDEF(&pubkeyc[65], 1);
2756     secp256k1_context_set_illegal_callback(ctx, counting_illegal_callback_fn, &ecount);
2757     /* Zero length claimed, fail, zeroize, no illegal arg error. */
2758     memset(&pubkey, 0xfe, sizeof(pubkey));
2759     ecount = 0;
2760     VG_UNDEF(shortkey, 2);
2761     VG_UNDEF(&pubkey, sizeof(pubkey));
2762     CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, shortkey, 0) == 0);
2763     VG_CHECK(&pubkey, sizeof(pubkey));
2764     CHECK(ecount == 0);
2765     CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2766     CHECK(ecount == 1);
2767     /* Length one claimed, fail, zeroize, no illegal arg error. */
2768     for (i = 0; i < 256 ; i++) {
2769         memset(&pubkey, 0xfe, sizeof(pubkey));
2770         ecount = 0;
2771         shortkey[0] = i;
2772         VG_UNDEF(&shortkey[1], 1);
2773         VG_UNDEF(&pubkey, sizeof(pubkey));
2774         CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, shortkey, 1) == 0);
2775         VG_CHECK(&pubkey, sizeof(pubkey));
2776         CHECK(ecount == 0);
2777         CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2778         CHECK(ecount == 1);
2779     }
2780     /* Length two claimed, fail, zeroize, no illegal arg error. */
2781     for (i = 0; i < 65536 ; i++) {
2782         memset(&pubkey, 0xfe, sizeof(pubkey));
2783         ecount = 0;
2784         shortkey[0] = i & 255;
2785         shortkey[1] = i >> 8;
2786         VG_UNDEF(&pubkey, sizeof(pubkey));
2787         CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, shortkey, 2) == 0);
2788         VG_CHECK(&pubkey, sizeof(pubkey));
2789         CHECK(ecount == 0);
2790         CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2791         CHECK(ecount == 1);
2792     }
2793     memset(&pubkey, 0xfe, sizeof(pubkey));
2794     ecount = 0;
2795     VG_UNDEF(&pubkey, sizeof(pubkey));
2796     /* 33 bytes claimed on otherwise valid input starting with 0x04, fail, zeroize output, no illegal arg error. */
2797     CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, 33) == 0);
2798     VG_CHECK(&pubkey, sizeof(pubkey));
2799     CHECK(ecount == 0);
2800     CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2801     CHECK(ecount == 1);
2802     /* NULL pubkey, illegal arg error. Pubkey isn't rewritten before this step, since it's NULL into the parser. */
2803     CHECK(secp256k1_ec_pubkey_parse(ctx, NULL, pubkeyc, 65) == 0);
2804     CHECK(ecount == 2);
2805     /* NULL input string. Illegal arg and zeroize output. */
2806     memset(&pubkey, 0xfe, sizeof(pubkey));
2807     ecount = 0;
2808     VG_UNDEF(&pubkey, sizeof(pubkey));
2809     CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, NULL, 65) == 0);
2810     VG_CHECK(&pubkey, sizeof(pubkey));
2811     CHECK(ecount == 1);
2812     CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2813     CHECK(ecount == 2);
2814     /* 64 bytes claimed on input starting with 0x04, fail, zeroize output, no illegal arg error. */
2815     memset(&pubkey, 0xfe, sizeof(pubkey));
2816     ecount = 0;
2817     VG_UNDEF(&pubkey, sizeof(pubkey));
2818     CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, 64) == 0);
2819     VG_CHECK(&pubkey, sizeof(pubkey));
2820     CHECK(ecount == 0);
2821     CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2822     CHECK(ecount == 1);
2823     /* 66 bytes claimed, fail, zeroize output, no illegal arg error. */
2824     memset(&pubkey, 0xfe, sizeof(pubkey));
2825     ecount = 0;
2826     VG_UNDEF(&pubkey, sizeof(pubkey));
2827     CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, 66) == 0);
2828     VG_CHECK(&pubkey, sizeof(pubkey));
2829     CHECK(ecount == 0);
2830     CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 0);
2831     CHECK(ecount == 1);
2832     /* Valid parse. */
2833     memset(&pubkey, 0, sizeof(pubkey));
2834     ecount = 0;
2835     VG_UNDEF(&pubkey, sizeof(pubkey));
2836     CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, 65) == 1);
2837     VG_CHECK(&pubkey, sizeof(pubkey));
2838     CHECK(ecount == 0);
2839     VG_UNDEF(&ge, sizeof(ge));
2840     CHECK(secp256k1_pubkey_load(ctx, &ge, &pubkey) == 1);
2841     VG_CHECK(&ge.x, sizeof(ge.x));
2842     VG_CHECK(&ge.y, sizeof(ge.y));
2843     VG_CHECK(&ge.infinity, sizeof(ge.infinity));
2844     ge_equals_ge(&secp256k1_ge_const_g, &ge);
2845     CHECK(ecount == 0);
2846     /* Multiple illegal args. Should still set arg error only once. */
2847     ecount = 0;
2848     ecount2 = 11;
2849     CHECK(secp256k1_ec_pubkey_parse(ctx, NULL, NULL, 65) == 0);
2850     CHECK(ecount == 1);
2851     /* Does the illegal arg callback actually change the behavior? */
2852     secp256k1_context_set_illegal_callback(ctx, uncounting_illegal_callback_fn, &ecount2);
2853     CHECK(secp256k1_ec_pubkey_parse(ctx, NULL, NULL, 65) == 0);
2854     CHECK(ecount == 1);
2855     CHECK(ecount2 == 10);
2856     secp256k1_context_set_illegal_callback(ctx, NULL, NULL);
2857     /* Try a bunch of prefabbed points with all possible encodings. */
2858     for (i = 0; i < SECP256K1_EC_PARSE_TEST_NVALID; i++) {
2859         ec_pubkey_parse_pointtest(valid[i], 1, 1);
2860     }
2861     for (i = 0; i < SECP256K1_EC_PARSE_TEST_NXVALID; i++) {
2862         ec_pubkey_parse_pointtest(onlyxvalid[i], 1, 0);
2863     }
2864     for (i = 0; i < SECP256K1_EC_PARSE_TEST_NINVALID; i++) {
2865         ec_pubkey_parse_pointtest(invalid[i], 0, 0);
2866     }
2867 }
2868
2869 void run_eckey_edge_case_test(void) {
2870     const unsigned char orderc[32] = {
2871         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
2872         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
2873         0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
2874         0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41
2875     };
2876     const unsigned char zeros[sizeof(secp256k1_pubkey)] = {0x00};
2877     unsigned char ctmp[32];
2878     unsigned char ctmp2[32];
2879     secp256k1_pubkey pubkey;
2880     secp256k1_pubkey pubkey2;
2881     int32_t ecount;
2882     /* Group order is too large, reject. */
2883     CHECK(secp256k1_ec_seckey_verify(ctx, orderc) == 0);
2884     VG_UNDEF(&pubkey, sizeof(pubkey));
2885     CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, orderc) == 0);
2886     VG_CHECK(&pubkey, sizeof(pubkey));
2887     CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
2888     /* Maximum value is too large, reject. */
2889     memset(ctmp, 255, 32);
2890     CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 0);
2891     memset(&pubkey, 1, sizeof(pubkey));
2892     VG_UNDEF(&pubkey, sizeof(pubkey));
2893     CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 0);
2894     VG_CHECK(&pubkey, sizeof(pubkey));
2895     CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
2896     /* Zero is too small, reject. */
2897     memset(ctmp, 0, 32);
2898     CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 0);
2899     memset(&pubkey, 1, sizeof(pubkey));
2900     VG_UNDEF(&pubkey, sizeof(pubkey));
2901     CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 0);
2902     VG_CHECK(&pubkey, sizeof(pubkey));
2903     CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
2904     /* One must be accepted. */
2905     ctmp[31] = 0x01;
2906     CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 1);
2907     memset(&pubkey, 0, sizeof(pubkey));
2908     VG_UNDEF(&pubkey, sizeof(pubkey));
2909     CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 1);
2910     VG_CHECK(&pubkey, sizeof(pubkey));
2911     CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) > 0);
2912     /* Group order + 1 is too large, reject. */
2913     memcpy(ctmp, orderc, 32);
2914     ctmp[31] = 0x42;
2915     CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 0);
2916     memset(&pubkey, 1, sizeof(pubkey));
2917     VG_UNDEF(&pubkey, sizeof(pubkey));
2918     CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 0);
2919     VG_CHECK(&pubkey, sizeof(pubkey));
2920     CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) == 0);
2921     /* -1 must be accepted. */
2922     ctmp[31] = 0x40;
2923     CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 1);
2924     memset(&pubkey, 0, sizeof(pubkey));
2925     VG_UNDEF(&pubkey, sizeof(pubkey));
2926     CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, ctmp) == 1);
2927     VG_CHECK(&pubkey, sizeof(pubkey));
2928     CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) > 0);
2929     /* Tweak of zero leaves the value changed. */
2930     memset(ctmp2, 0, 32);
2931     CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp, ctmp2) == 1);
2932     CHECK(memcmp(orderc, ctmp, 31) == 0 && ctmp[31] == 0x40);
2933     memcpy(&pubkey2, &pubkey, sizeof(pubkey));
2934     CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 1);
2935     CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
2936     /* Multiply tweak of zero zeroizes the output. */
2937     CHECK(secp256k1_ec_privkey_tweak_mul(ctx, ctmp, ctmp2) == 0);
2938     CHECK(memcmp(zeros, ctmp, 32) == 0);
2939     CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, ctmp2) == 0);
2940     CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
2941     memcpy(&pubkey, &pubkey2, sizeof(pubkey));
2942     /* Overflowing key tweak zeroizes. */
2943     memcpy(ctmp, orderc, 32);
2944     ctmp[31] = 0x40;
2945     CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp, orderc) == 0);
2946     CHECK(memcmp(zeros, ctmp, 32) == 0);
2947     memcpy(ctmp, orderc, 32);
2948     ctmp[31] = 0x40;
2949     CHECK(secp256k1_ec_privkey_tweak_mul(ctx, ctmp, orderc) == 0);
2950     CHECK(memcmp(zeros, ctmp, 32) == 0);
2951     memcpy(ctmp, orderc, 32);
2952     ctmp[31] = 0x40;
2953     CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, orderc) == 0);
2954     CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
2955     memcpy(&pubkey, &pubkey2, sizeof(pubkey));
2956     CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, orderc) == 0);
2957     CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
2958     memcpy(&pubkey, &pubkey2, sizeof(pubkey));
2959     /* Private key tweaks results in a key of zero. */
2960     ctmp2[31] = 1;
2961     CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp2, ctmp) == 0);
2962     CHECK(memcmp(zeros, ctmp2, 32) == 0);
2963     ctmp2[31] = 1;
2964     CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 0);
2965     CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
2966     memcpy(&pubkey, &pubkey2, sizeof(pubkey));
2967     /* Tweak computation wraps and results in a key of 1. */
2968     ctmp2[31] = 2;
2969     CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp2, ctmp) == 1);
2970     CHECK(memcmp(ctmp2, zeros, 31) == 0 && ctmp2[31] == 1);
2971     ctmp2[31] = 2;
2972     CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 1);
2973     ctmp2[31] = 1;
2974     CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey2, ctmp2) == 1);
2975     CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
2976     /* Tweak mul * 2 = 1+1. */
2977     CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 1);
2978     ctmp2[31] = 2;
2979     CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey2, ctmp2) == 1);
2980     CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
2981     /* Test argument errors. */
2982     ecount = 0;
2983     secp256k1_context_set_illegal_callback(ctx, counting_illegal_callback_fn, &ecount);
2984     CHECK(ecount == 0);
2985     /* Zeroize pubkey on parse error. */
2986     memset(&pubkey, 0, 32);
2987     CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 0);
2988     CHECK(ecount == 1);
2989     CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0);
2990     memcpy(&pubkey, &pubkey2, sizeof(pubkey));
2991     memset(&pubkey2, 0, 32);
2992     CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey2, ctmp2) == 0);
2993     CHECK(ecount == 2);
2994     CHECK(memcmp(&pubkey2, zeros, sizeof(pubkey2)) == 0);
2995     /* Plain argument errors. */
2996     ecount = 0;
2997     CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 1);
2998     CHECK(ecount == 0);
2999     CHECK(secp256k1_ec_seckey_verify(ctx, NULL) == 0);
3000     CHECK(ecount == 1);
3001     ecount = 0;
3002     memset(ctmp2, 0, 32);
3003     ctmp2[31] = 4;
3004     CHECK(secp256k1_ec_pubkey_tweak_add(ctx, NULL, ctmp2) == 0);
3005     CHECK(ecount == 1);
3006     CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, NULL) == 0);
3007     CHECK(ecount == 2);
3008     ecount = 0;
3009     memset(ctmp2, 0, 32);
3010     ctmp2[31] = 4;
3011     CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, NULL, ctmp2) == 0);
3012     CHECK(ecount == 1);
3013     CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, NULL) == 0);
3014     CHECK(ecount == 2);
3015     ecount = 0;
3016     memset(ctmp2, 0, 32);
3017     CHECK(secp256k1_ec_privkey_tweak_add(ctx, NULL, ctmp2) == 0);
3018     CHECK(ecount == 1);
3019     CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp, NULL) == 0);
3020     CHECK(ecount == 2);
3021     ecount = 0;
3022     memset(ctmp2, 0, 32);
3023     ctmp2[31] = 1;
3024     CHECK(secp256k1_ec_privkey_tweak_mul(ctx, NULL, ctmp2) == 0);
3025     CHECK(ecount == 1);
3026     CHECK(secp256k1_ec_privkey_tweak_mul(ctx, ctmp, NULL) == 0);
3027     CHECK(ecount == 2);
3028     ecount = 0;
3029     CHECK(secp256k1_ec_pubkey_create(ctx, NULL, ctmp) == 0);
3030     CHECK(ecount == 1);
3031     memset(&pubkey, 1, sizeof(pubkey));
3032     CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, NULL) == 0);
3033     CHECK(ecount == 2);
3034     CHECK(memcmp(&pubkey, zeros, sizeof(secp256k1_pubkey)) > 0);
3035     secp256k1_context_set_illegal_callback(ctx, NULL, NULL);
3036 }
3037
3038 void random_sign(secp256k1_scalar *sigr, secp256k1_scalar *sigs, const secp256k1_scalar *key, const secp256k1_scalar *msg, int *recid) {
3039     secp256k1_scalar nonce;
3040     do {
3041         random_scalar_order_test(&nonce);
3042     } while(!secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, sigr, sigs, key, msg, &nonce, recid));
3043 }
3044
3045 void test_ecdsa_sign_verify(void) {
3046     secp256k1_gej pubj;
3047     secp256k1_ge pub;
3048     secp256k1_scalar one;
3049     secp256k1_scalar msg, key;
3050     secp256k1_scalar sigr, sigs;
3051     int recid;
3052     int getrec;
3053     random_scalar_order_test(&msg);
3054     random_scalar_order_test(&key);
3055     secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pubj, &key);
3056     secp256k1_ge_set_gej(&pub, &pubj);
3057     getrec = secp256k1_rand_bits(1);
3058     random_sign(&sigr, &sigs, &key, &msg, getrec?&recid:NULL);
3059     if (getrec) {
3060         CHECK(recid >= 0 && recid < 4);
3061     }
3062     CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sigr, &sigs, &pub, &msg));
3063     secp256k1_scalar_set_int(&one, 1);
3064     secp256k1_scalar_add(&msg, &msg, &one);
3065     CHECK(!secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sigr, &sigs, &pub, &msg));
3066 }
3067
3068 void run_ecdsa_sign_verify(void) {
3069     int i;
3070     for (i = 0; i < 10*count; i++) {
3071         test_ecdsa_sign_verify();
3072     }
3073 }
3074
3075 /** Dummy nonce generation function that just uses a precomputed nonce, and fails if it is not accepted. Use only for testing. */
3076 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) {
3077     (void)msg32;
3078     (void)key32;
3079     (void)algo16;
3080     memcpy(nonce32, data, 32);
3081     return (counter == 0);
3082 }
3083
3084 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) {
3085    /* Dummy nonce generator that has a fatal error on the first counter value. */
3086    if (counter == 0) {
3087        return 0;
3088    }
3089    return nonce_function_rfc6979(nonce32, msg32, key32, algo16, data, counter - 1);
3090 }
3091
3092 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) {
3093    /* Dummy nonce generator that produces unacceptable nonces for the first several counter values. */
3094    if (counter < 3) {
3095        memset(nonce32, counter==0 ? 0 : 255, 32);
3096        if (counter == 2) {
3097            nonce32[31]--;
3098        }
3099        return 1;
3100    }
3101    if (counter < 5) {
3102        static const unsigned char order[] = {
3103            0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
3104            0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
3105            0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
3106            0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x41
3107        };
3108        memcpy(nonce32, order, 32);
3109        if (counter == 4) {
3110            nonce32[31]++;
3111        }
3112        return 1;
3113    }
3114    /* Retry rate of 6979 is negligible esp. as we only call this in determinstic tests. */
3115    /* If someone does fine a case where it retries for secp256k1, we'd like to know. */
3116    if (counter > 5) {
3117        return 0;
3118    }
3119    return nonce_function_rfc6979(nonce32, msg32, key32, algo16, data, counter - 5);
3120 }
3121
3122 int is_empty_signature(const secp256k1_ecdsa_signature *sig) {
3123     static const unsigned char res[sizeof(secp256k1_ecdsa_signature)] = {0};
3124     return memcmp(sig, res, sizeof(secp256k1_ecdsa_signature)) == 0;
3125 }
3126
3127 void test_ecdsa_end_to_end(void) {
3128     unsigned char extra[32] = {0x00};
3129     unsigned char privkey[32];
3130     unsigned char message[32];
3131     unsigned char privkey2[32];
3132     secp256k1_ecdsa_signature signature[6];
3133     secp256k1_scalar r, s;
3134     unsigned char sig[74];
3135     size_t siglen = 74;
3136     unsigned char pubkeyc[65];
3137     size_t pubkeyclen = 65;
3138     secp256k1_pubkey pubkey;
3139     unsigned char seckey[300];
3140     size_t seckeylen = 300;
3141
3142     /* Generate a random key and message. */
3143     {
3144         secp256k1_scalar msg, key;
3145         random_scalar_order_test(&msg);
3146         random_scalar_order_test(&key);
3147         secp256k1_scalar_get_b32(privkey, &key);
3148         secp256k1_scalar_get_b32(message, &msg);
3149     }
3150
3151     /* Construct and verify corresponding public key. */
3152     CHECK(secp256k1_ec_seckey_verify(ctx, privkey) == 1);
3153     CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, privkey) == 1);
3154
3155     /* Verify exporting and importing public key. */
3156     CHECK(secp256k1_ec_pubkey_serialize(ctx, pubkeyc, &pubkeyclen, &pubkey, secp256k1_rand_bits(1) == 1 ? SECP256K1_EC_COMPRESSED : SECP256K1_EC_UNCOMPRESSED));
3157     memset(&pubkey, 0, sizeof(pubkey));
3158     CHECK(secp256k1_ec_pubkey_parse(ctx, &pubkey, pubkeyc, pubkeyclen) == 1);
3159
3160     /* Verify private key import and export. */
3161     CHECK(ec_privkey_export_der(ctx, seckey, &seckeylen, privkey, secp256k1_rand_bits(1) == 1));
3162     CHECK(ec_privkey_import_der(ctx, privkey2, seckey, seckeylen) == 1);
3163     CHECK(memcmp(privkey, privkey2, 32) == 0);
3164
3165     /* Optionally tweak the keys using addition. */
3166     if (secp256k1_rand_int(3) == 0) {
3167         int ret1;
3168         int ret2;
3169         unsigned char rnd[32];
3170         secp256k1_pubkey pubkey2;
3171         secp256k1_rand256_test(rnd);
3172         ret1 = secp256k1_ec_privkey_tweak_add(ctx, privkey, rnd);
3173         ret2 = secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, rnd);
3174         CHECK(ret1 == ret2);
3175         if (ret1 == 0) {
3176             return;
3177         }
3178         CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey2, privkey) == 1);
3179         CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
3180     }
3181
3182     /* Optionally tweak the keys using multiplication. */
3183     if (secp256k1_rand_int(3) == 0) {
3184         int ret1;
3185         int ret2;
3186         unsigned char rnd[32];
3187         secp256k1_pubkey pubkey2;
3188         secp256k1_rand256_test(rnd);
3189         ret1 = secp256k1_ec_privkey_tweak_mul(ctx, privkey, rnd);
3190         ret2 = secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, rnd);
3191         CHECK(ret1 == ret2);
3192         if (ret1 == 0) {
3193             return;
3194         }
3195         CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey2, privkey) == 1);
3196         CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0);
3197     }
3198
3199     /* Sign. */
3200     CHECK(secp256k1_ecdsa_sign(ctx, &signature[0], message, privkey, NULL, NULL) == 1);
3201     CHECK(secp256k1_ecdsa_sign(ctx, &signature[4], message, privkey, NULL, NULL) == 1);
3202     CHECK(secp256k1_ecdsa_sign(ctx, &signature[1], message, privkey, NULL, extra) == 1);
3203     extra[31] = 1;
3204     CHECK(secp256k1_ecdsa_sign(ctx, &signature[2], message, privkey, NULL, extra) == 1);
3205     extra[31] = 0;
3206     extra[0] = 1;
3207     CHECK(secp256k1_ecdsa_sign(ctx, &signature[3], message, privkey, NULL, extra) == 1);
3208     CHECK(memcmp(&signature[0], &signature[4], sizeof(signature[0])) == 0);
3209     CHECK(memcmp(&signature[0], &signature[1], sizeof(signature[0])) != 0);
3210     CHECK(memcmp(&signature[0], &signature[2], sizeof(signature[0])) != 0);
3211     CHECK(memcmp(&signature[0], &signature[3], sizeof(signature[0])) != 0);
3212     CHECK(memcmp(&signature[1], &signature[2], sizeof(signature[0])) != 0);
3213     CHECK(memcmp(&signature[1], &signature[3], sizeof(signature[0])) != 0);
3214     CHECK(memcmp(&signature[2], &signature[3], sizeof(signature[0])) != 0);
3215     /* Verify. */
3216     CHECK(secp256k1_ecdsa_verify(ctx, &signature[0], message, &pubkey) == 1);
3217     CHECK(secp256k1_ecdsa_verify(ctx, &signature[1], message, &pubkey) == 1);
3218     CHECK(secp256k1_ecdsa_verify(ctx, &signature[2], message, &pubkey) == 1);
3219     CHECK(secp256k1_ecdsa_verify(ctx, &signature[3], message, &pubkey) == 1);
3220     /* Test lower-S form, malleate, verify and fail, test again, malleate again */
3221     CHECK(!secp256k1_ecdsa_signature_normalize(ctx, NULL, &signature[0]));
3222     secp256k1_ecdsa_signature_load(ctx, &r, &s, &signature[0]);
3223     secp256k1_scalar_negate(&s, &s);
3224     secp256k1_ecdsa_signature_save(&signature[5], &r, &s);
3225     CHECK(secp256k1_ecdsa_verify(ctx, &signature[5], message, &pubkey) == 0);
3226     CHECK(secp256k1_ecdsa_signature_normalize(ctx, NULL, &signature[5]));
3227     CHECK(secp256k1_ecdsa_signature_normalize(ctx, &signature[5], &signature[5]));
3228     CHECK(!secp256k1_ecdsa_signature_normalize(ctx, NULL, &signature[5]));
3229     CHECK(secp256k1_ecdsa_verify(ctx, &signature[5], message, &pubkey) == 1);
3230     secp256k1_scalar_negate(&s, &s);
3231     secp256k1_ecdsa_signature_save(&signature[5], &r, &s);
3232     CHECK(!secp256k1_ecdsa_signature_normalize(ctx, NULL, &signature[5]));
3233     CHECK(secp256k1_ecdsa_verify(ctx, &signature[5], message, &pubkey) == 1);
3234     CHECK(memcmp(&signature[5], &signature[0], 64) == 0);
3235
3236     /* Serialize/parse DER and verify again */
3237     CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, sig, &siglen, &signature[0]) == 1);
3238     memset(&signature[0], 0, sizeof(signature[0]));
3239     CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &signature[0], sig, siglen) == 1);
3240     CHECK(secp256k1_ecdsa_verify(ctx, &signature[0], message, &pubkey) == 1);
3241     /* Serialize/destroy/parse DER and verify again. */
3242     siglen = 74;
3243     CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, sig, &siglen, &signature[0]) == 1);
3244     sig[secp256k1_rand_int(siglen)] += 1 + secp256k1_rand_int(255);
3245     CHECK(secp256k1_ecdsa_signature_parse_der(ctx, &signature[0], sig, siglen) == 0 ||
3246           secp256k1_ecdsa_verify(ctx, &signature[0], message, &pubkey) == 0);
3247 }
3248
3249 void test_random_pubkeys(void) {
3250     secp256k1_ge elem;
3251     secp256k1_ge elem2;
3252     unsigned char in[65];
3253     /* Generate some randomly sized pubkeys. */
3254     size_t len = secp256k1_rand_bits(2) == 0 ? 65 : 33;
3255     if (secp256k1_rand_bits(2) == 0) {
3256         len = secp256k1_rand_bits(6);
3257     }
3258     if (len == 65) {
3259       in[0] = secp256k1_rand_bits(1) ? 4 : (secp256k1_rand_bits(1) ? 6 : 7);
3260     } else {
3261       in[0] = secp256k1_rand_bits(1) ? 2 : 3;
3262     }
3263     if (secp256k1_rand_bits(3) == 0) {
3264         in[0] = secp256k1_rand_bits(8);
3265     }
3266     if (len > 1) {
3267         secp256k1_rand256(&in[1]);
3268     }
3269     if (len > 33) {
3270         secp256k1_rand256(&in[33]);
3271     }
3272     if (secp256k1_eckey_pubkey_parse(&elem, in, len)) {
3273         unsigned char out[65];
3274         unsigned char firstb;
3275         int res;
3276         size_t size = len;
3277         firstb = in[0];
3278         /* If the pubkey can be parsed, it should round-trip... */
3279         CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, len == 33));
3280         CHECK(size == len);
3281         CHECK(memcmp(&in[1], &out[1], len-1) == 0);
3282         /* ... except for the type of hybrid inputs. */
3283         if ((in[0] != 6) && (in[0] != 7)) {
3284             CHECK(in[0] == out[0]);
3285         }
3286         size = 65;
3287         CHECK(secp256k1_eckey_pubkey_serialize(&elem, in, &size, 0));
3288         CHECK(size == 65);
3289         CHECK(secp256k1_eckey_pubkey_parse(&elem2, in, size));
3290         ge_equals_ge(&elem,&elem2);
3291         /* Check that the X9.62 hybrid type is checked. */
3292         in[0] = secp256k1_rand_bits(1) ? 6 : 7;
3293         res = secp256k1_eckey_pubkey_parse(&elem2, in, size);
3294         if (firstb == 2 || firstb == 3) {
3295             if (in[0] == firstb + 4) {
3296               CHECK(res);
3297             } else {
3298               CHECK(!res);
3299             }
3300         }
3301         if (res) {
3302             ge_equals_ge(&elem,&elem2);
3303             CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, 0));
3304             CHECK(memcmp(&in[1], &out[1], 64) == 0);
3305         }
3306     }
3307 }
3308
3309 void run_random_pubkeys(void) {
3310     int i;
3311     for (i = 0; i < 10*count; i++) {
3312         test_random_pubkeys();
3313     }
3314 }
3315
3316 void run_ecdsa_end_to_end(void) {
3317     int i;
3318     for (i = 0; i < 64*count; i++) {
3319         test_ecdsa_end_to_end();
3320     }
3321 }
3322
3323 int test_ecdsa_der_parse(const unsigned char *sig, size_t siglen, int certainly_der, int certainly_not_der) {
3324     static const unsigned char zeroes[32] = {0};
3325     static const unsigned char max_scalar[32] = {
3326         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3327         0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
3328         0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
3329         0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x40
3330     };
3331
3332     int ret = 0;
3333
3334     secp256k1_ecdsa_signature sig_der;
3335     unsigned char roundtrip_der[2048];
3336     unsigned char compact_der[64];
3337     size_t len_der = 2048;
3338     int parsed_der = 0, valid_der = 0, roundtrips_der = 0;
3339
3340     secp256k1_ecdsa_signature sig_der_lax;
3341     unsigned char roundtrip_der_lax[2048];
3342     unsigned char compact_der_lax[64];
3343     size_t len_der_lax = 2048;
3344     int parsed_der_lax = 0, valid_der_lax = 0, roundtrips_der_lax = 0;
3345
3346 #ifdef ENABLE_OPENSSL_TESTS
3347     ECDSA_SIG *sig_openssl;
3348     const unsigned char *sigptr;
3349     unsigned char roundtrip_openssl[2048];
3350     int len_openssl = 2048;
3351     int parsed_openssl, valid_openssl = 0, roundtrips_openssl = 0;
3352 #endif
3353
3354     parsed_der = secp256k1_ecdsa_signature_parse_der(ctx, &sig_der, sig, siglen);
3355     if (parsed_der) {
3356         ret |= (!secp256k1_ecdsa_signature_serialize_compact(ctx, compact_der, &sig_der)) << 0;
3357         valid_der = (memcmp(compact_der, zeroes, 32) != 0) && (memcmp(compact_der + 32, zeroes, 32) != 0);
3358     }
3359     if (valid_der) {
3360         ret |= (!secp256k1_ecdsa_signature_serialize_der(ctx, roundtrip_der, &len_der, &sig_der)) << 1;
3361         roundtrips_der = (len_der == siglen) && memcmp(roundtrip_der, sig, siglen) == 0;
3362     }
3363
3364     parsed_der_lax = ecdsa_signature_parse_der_lax(ctx, &sig_der_lax, sig, siglen);
3365     if (parsed_der_lax) {
3366         ret |= (!secp256k1_ecdsa_signature_serialize_compact(ctx, compact_der_lax, &sig_der_lax)) << 10;
3367         valid_der_lax = (memcmp(compact_der_lax, zeroes, 32) != 0) && (memcmp(compact_der_lax + 32, zeroes, 32) != 0);
3368     }
3369     if (valid_der_lax) {
3370         ret |= (!secp256k1_ecdsa_signature_serialize_der(ctx, roundtrip_der_lax, &len_der_lax, &sig_der_lax)) << 11;
3371         roundtrips_der_lax = (len_der_lax == siglen) && memcmp(roundtrip_der_lax, sig, siglen) == 0;
3372     }
3373
3374     if (certainly_der) {
3375         ret |= (!parsed_der) << 2;
3376     }
3377     if (certainly_not_der) {
3378         ret |= (parsed_der) << 17;
3379     }
3380     if (valid_der) {
3381         ret |= (!roundtrips_der) << 3;
3382     }
3383
3384     if (valid_der) {
3385         ret |= (!roundtrips_der_lax) << 12;
3386         ret |= (len_der != len_der_lax) << 13;
3387         ret |= (memcmp(roundtrip_der_lax, roundtrip_der, len_der) != 0) << 14;
3388     }
3389     ret |= (roundtrips_der != roundtrips_der_lax) << 15;
3390     if (parsed_der) {
3391         ret |= (!parsed_der_lax) << 16;
3392     }
3393
3394 #ifdef ENABLE_OPENSSL_TESTS
3395     sig_openssl = ECDSA_SIG_new();
3396     sigptr = sig;
3397     parsed_openssl = (d2i_ECDSA_SIG(&sig_openssl, &sigptr, siglen) != NULL);
3398     if (parsed_openssl) {
3399         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;
3400         if (valid_openssl) {
3401             unsigned char tmp[32] = {0};
3402             BN_bn2bin(sig_openssl->r, tmp + 32 - BN_num_bytes(sig_openssl->r));
3403             valid_openssl = memcmp(tmp, max_scalar, 32) < 0;
3404         }
3405         if (valid_openssl) {
3406             unsigned char tmp[32] = {0};
3407             BN_bn2bin(sig_openssl->s, tmp + 32 - BN_num_bytes(sig_openssl->s));
3408             valid_openssl = memcmp(tmp, max_scalar, 32) < 0;
3409         }
3410     }
3411     len_openssl = i2d_ECDSA_SIG(sig_openssl, NULL);
3412     if (len_openssl <= 2048) {
3413         unsigned char *ptr = roundtrip_openssl;
3414         CHECK(i2d_ECDSA_SIG(sig_openssl, &ptr) == len_openssl);
3415         roundtrips_openssl = valid_openssl && ((size_t)len_openssl == siglen) && (memcmp(roundtrip_openssl, sig, siglen) == 0);
3416     } else {
3417         len_openssl = 0;
3418     }
3419     ECDSA_SIG_free(sig_openssl);
3420
3421     ret |= (parsed_der && !parsed_openssl) << 4;
3422     ret |= (valid_der && !valid_openssl) << 5;
3423     ret |= (roundtrips_openssl && !parsed_der) << 6;
3424     ret |= (roundtrips_der != roundtrips_openssl) << 7;
3425     if (roundtrips_openssl) {
3426         ret |= (len_der != (size_t)len_openssl) << 8;
3427         ret |= (memcmp(roundtrip_der, roundtrip_openssl, len_der) != 0) << 9;
3428     }
3429 #endif
3430     return ret;
3431 }
3432
3433 static void assign_big_endian(unsigned char *ptr, size_t ptrlen, uint32_t val) {
3434     size_t i;
3435     for (i = 0; i < ptrlen; i++) {
3436         int shift = ptrlen - 1 - i;
3437         if (shift >= 4) {
3438             ptr[i] = 0;
3439         } else {
3440             ptr[i] = (val >> shift) & 0xFF;
3441         }
3442     }
3443 }
3444
3445 static void damage_array(unsigned char *sig, size_t *len) {
3446     int pos;
3447     int action = secp256k1_rand_bits(3);
3448     if (action < 1) {
3449         /* Delete a byte. */
3450         pos = secp256k1_rand_int(*len);
3451         memmove(sig + pos, sig + pos + 1, *len - pos - 1);
3452         (*len)--;
3453         return;
3454     } else if (action < 2) {
3455         /* Insert a byte. */
3456         pos = secp256k1_rand_int(1 + *len);
3457         memmove(sig + pos + 1, sig + pos, *len - pos);
3458         sig[pos] = secp256k1_rand_bits(8);
3459         (*len)++;
3460         return;
3461     } else if (action < 4) {
3462         /* Modify a byte. */
3463         sig[secp256k1_rand_int(*len)] += 1 + secp256k1_rand_int(255);
3464         return;
3465     } else { /* action < 8 */
3466         /* Modify a bit. */
3467         sig[secp256k1_rand_int(*len)] ^= 1 << secp256k1_rand_bits(3);
3468         return;
3469     }
3470 }
3471
3472 static void random_ber_signature(unsigned char *sig, size_t *len, int* certainly_der, int* certainly_not_der) {
3473     int der;
3474     int nlow[2], nlen[2], nlenlen[2], nhbit[2], nhbyte[2], nzlen[2];
3475     size_t tlen, elen, glen;
3476     int indet;
3477     int n;
3478
3479     *len = 0;
3480     der = secp256k1_rand_bits(2) == 0;
3481     *certainly_der = der;
3482     *certainly_not_der = 0;
3483     indet = der ? 0 : secp256k1_rand_int(10) == 0;
3484
3485     for (n = 0; n < 2; n++) {
3486         /* 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) */
3487         nlow[n] = der ? 1 : (secp256k1_rand_bits(3) != 0);
3488         /* The length of the number in bytes (the first byte of which will always be nonzero) */
3489         nlen[n] = nlow[n] ? secp256k1_rand_int(33) : 32 + secp256k1_rand_int(200) * secp256k1_rand_int(8) / 8;
3490         CHECK(nlen[n] <= 232);
3491         /* The top bit of the number. */
3492         nhbit[n] = (nlow[n] == 0 && nlen[n] == 32) ? 1 : (nlen[n] == 0 ? 0 : secp256k1_rand_bits(1));
3493         /* The top byte of the number (after the potential hardcoded 16 0xFF characters for "high" 32 bytes numbers) */
3494         nhbyte[n] = nlen[n] == 0 ? 0 : (nhbit[n] ? 128 + secp256k1_rand_bits(7) : 1 + secp256k1_rand_int(127));
3495         /* 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) */
3496         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);
3497         if (nzlen[n] > ((nlen[n] == 0 || nhbit[n]) ? 1 : 0)) {
3498             *certainly_not_der = 1;
3499         }
3500         CHECK(nlen[n] + nzlen[n] <= 300);
3501         /* The length of the length descriptor for the number. 0 means short encoding, anything else is long encoding. */
3502         nlenlen[n] = nlen[n] + nzlen[n] < 128 ? 0 : (nlen[n] + nzlen[n] < 256 ? 1 : 2);
3503         if (!der) {
3504             /* nlenlen[n] max 127 bytes */
3505             int add = secp256k1_rand_int(127 - nlenlen[n]) * secp256k1_rand_int(16) * secp256k1_rand_int(16) / 256;
3506             nlenlen[n] += add;
3507             if (add != 0) {
3508                 *certainly_not_der = 1;
3509             }
3510         }
3511         CHECK(nlen[n] + nzlen[n] + nlenlen[n] <= 427);
3512     }
3513
3514     /* The total length of the data to go, so far */
3515     tlen = 2 + nlenlen[0] + nlen[0] + nzlen[0] + 2 + nlenlen[1] + nlen[1] + nzlen[1];
3516     CHECK(tlen <= 856);
3517
3518     /* The length of the garbage inside the tuple. */
3519     elen = (der || indet) ? 0 : secp256k1_rand_int(980 - tlen) * secp256k1_rand_int(8) / 8;
3520     if (elen != 0) {
3521         *certainly_not_der = 1;
3522     }
3523     tlen += elen;
3524     CHECK(tlen <= 980);
3525
3526     /* The length of the garbage after the end of the tuple. */
3527     glen = der ? 0 : secp256k1_rand_int(990 - tlen) * secp256k1_rand_int(8) / 8;
3528     if (glen != 0) {
3529         *certainly_not_der = 1;
3530     }
3531     CHECK(tlen + glen <= 990);
3532
3533     /* Write the tuple header. */
3534     sig[(*len)++] = 0x30;
3535     if (indet) {
3536         /* Indeterminate length */
3537         sig[(*len)++] = 0x80;
3538         *certainly_not_der = 1;
3539     } else {
3540         int tlenlen = tlen < 128 ? 0 : (tlen < 256 ? 1 : 2);
3541         if (!der) {
3542             int add = secp256k1_rand_int(127 - tlenlen) * secp256k1_rand_int(16) * secp256k1_rand_int(16) / 256;
3543             tlenlen += add;
3544             if (add != 0) {
3545                 *certainly_not_der = 1;
3546             }
3547         }
3548         if (tlenlen == 0) {
3549             /* Short length notation */
3550             sig[(*len)++] = tlen;
3551         } else {
3552             /* Long length notation */
3553             sig[(*len)++] = 128 + tlenlen;
3554             assign_big_endian(sig + *len, tlenlen, tlen);
3555             *len += tlenlen;
3556         }
3557         tlen += tlenlen;
3558     }
3559     tlen += 2;
3560     CHECK(tlen + glen <= 1119);
3561
3562     for (n = 0; n < 2; n++) {
3563         /* Write the integer header. */
3564         sig[(*len)++] = 0x02;
3565         if (nlenlen[n] == 0) {
3566             /* Short length notation */
3567             sig[(*len)++] = nlen[n] + nzlen[n];
3568         } else {
3569             /* Long length notation. */
3570             sig[(*len)++] = 128 + nlenlen[n];
3571             assign_big_endian(sig + *len, nlenlen[n], nlen[n] + nzlen[n]);
3572             *len += nlenlen[n];
3573         }
3574         /* Write zero padding */
3575         while (nzlen[n] > 0) {
3576             sig[(*len)++] = 0x00;
3577             nzlen[n]--;
3578         }
3579         if (nlen[n] == 32 && !nlow[n]) {
3580             /* Special extra 16 0xFF bytes in "high" 32-byte numbers */
3581             int i;
3582             for (i = 0; i < 16; i++) {
3583                 sig[(*len)++] = 0xFF;
3584             }
3585             nlen[n] -= 16;
3586         }
3587         /* Write first byte of number */
3588         if (nlen[n] > 0) {
3589             sig[(*len)++] = nhbyte[n];
3590             nlen[n]--;
3591         }
3592         /* Generate remaining random bytes of number */
3593         secp256k1_rand_bytes_test(sig + *len, nlen[n]);
3594         *len += nlen[n];
3595         nlen[n] = 0;
3596     }
3597
3598     /* Generate random garbage inside tuple. */
3599     secp256k1_rand_bytes_test(sig + *len, elen);
3600     *len += elen;
3601
3602     /* Generate end-of-contents bytes. */
3603     if (indet) {
3604         sig[(*len)++] = 0;
3605         sig[(*len)++] = 0;
3606         tlen += 2;
3607     }
3608     CHECK(tlen + glen <= 1121);
3609
3610     /* Generate random garbage outside tuple. */
3611     secp256k1_rand_bytes_test(sig + *len, glen);
3612     *len += glen;
3613     tlen += glen;
3614     CHECK(tlen <= 1121);
3615     CHECK(tlen == *len);
3616 }
3617
3618 void run_ecdsa_der_parse(void) {
3619     int i,j;
3620     for (i = 0; i < 200 * count; i++) {
3621         unsigned char buffer[2048];
3622         size_t buflen = 0;
3623         int certainly_der = 0;
3624         int certainly_not_der = 0;
3625         random_ber_signature(buffer, &buflen, &certainly_der, &certainly_not_der);
3626         for (j = 0; j < 16; j++) {
3627             int ret = 0;
3628             if (j > 0) {
3629                 damage_array(buffer, &buflen);
3630                 /* We don't know anything anymore about the DERness of the result */
3631                 certainly_der = 0;
3632                 certainly_not_der = 0;
3633             }
3634             ret = test_ecdsa_der_parse(buffer, buflen, certainly_der, certainly_not_der);
3635             if (ret != 0) {
3636                 size_t k;
3637                 fprintf(stderr, "Failure %x on ", ret);
3638                 for (k = 0; k < buflen; k++) {
3639                     fprintf(stderr, "%02x ", buffer[k]);
3640                 }
3641                 fprintf(stderr, "\n");
3642             }
3643             CHECK(ret == 0);
3644         }
3645     }
3646 }
3647
3648 /* Tests several edge cases. */
3649 void test_ecdsa_edge_cases(void) {
3650     int t;
3651     secp256k1_ecdsa_signature sig;
3652
3653     /* Test the case where ECDSA recomputes a point that is infinity. */
3654     {
3655         secp256k1_gej keyj;
3656         secp256k1_ge key;
3657         secp256k1_scalar msg;
3658         secp256k1_scalar sr, ss;
3659         secp256k1_scalar_set_int(&ss, 1);
3660         secp256k1_scalar_negate(&ss, &ss);
3661         secp256k1_scalar_inverse(&ss, &ss);
3662         secp256k1_scalar_set_int(&sr, 1);
3663         secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &keyj, &sr);
3664         secp256k1_ge_set_gej(&key, &keyj);
3665         msg = ss;
3666         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3667     }
3668
3669     /* Verify signature with r of zero fails. */
3670     {
3671         const unsigned char pubkey_mods_zero[33] = {
3672             0x02, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3673             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3674             0xfe, 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0,
3675             0x3b, 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41,
3676             0x41
3677         };
3678         secp256k1_ge key;
3679         secp256k1_scalar msg;
3680         secp256k1_scalar sr, ss;
3681         secp256k1_scalar_set_int(&ss, 1);
3682         secp256k1_scalar_set_int(&msg, 0);
3683         secp256k1_scalar_set_int(&sr, 0);
3684         CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey_mods_zero, 33));
3685         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3686     }
3687
3688     /* Verify signature with s of zero fails. */
3689     {
3690         const unsigned char pubkey[33] = {
3691             0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3692             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3693             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3694             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3695             0x01
3696         };
3697         secp256k1_ge key;
3698         secp256k1_scalar msg;
3699         secp256k1_scalar sr, ss;
3700         secp256k1_scalar_set_int(&ss, 0);
3701         secp256k1_scalar_set_int(&msg, 0);
3702         secp256k1_scalar_set_int(&sr, 1);
3703         CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey, 33));
3704         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3705     }
3706
3707     /* Verify signature with message 0 passes. */
3708     {
3709         const unsigned char pubkey[33] = {
3710             0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3711             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3712             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3713             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3714             0x02
3715         };
3716         const unsigned char pubkey2[33] = {
3717             0x02, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3718             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3719             0xfe, 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0,
3720             0x3b, 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41,
3721             0x43
3722         };
3723         secp256k1_ge key;
3724         secp256k1_ge key2;
3725         secp256k1_scalar msg;
3726         secp256k1_scalar sr, ss;
3727         secp256k1_scalar_set_int(&ss, 2);
3728         secp256k1_scalar_set_int(&msg, 0);
3729         secp256k1_scalar_set_int(&sr, 2);
3730         CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey, 33));
3731         CHECK(secp256k1_eckey_pubkey_parse(&key2, pubkey2, 33));
3732         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3733         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 1);
3734         secp256k1_scalar_negate(&ss, &ss);
3735         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3736         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 1);
3737         secp256k1_scalar_set_int(&ss, 1);
3738         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3739         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 0);
3740     }
3741
3742     /* Verify signature with message 1 passes. */
3743     {
3744         const unsigned char pubkey[33] = {
3745             0x02, 0x14, 0x4e, 0x5a, 0x58, 0xef, 0x5b, 0x22,
3746             0x6f, 0xd2, 0xe2, 0x07, 0x6a, 0x77, 0xcf, 0x05,
3747             0xb4, 0x1d, 0xe7, 0x4a, 0x30, 0x98, 0x27, 0x8c,
3748             0x93, 0xe6, 0xe6, 0x3c, 0x0b, 0xc4, 0x73, 0x76,
3749             0x25
3750         };
3751         const unsigned char pubkey2[33] = {
3752             0x02, 0x8a, 0xd5, 0x37, 0xed, 0x73, 0xd9, 0x40,
3753             0x1d, 0xa0, 0x33, 0xd2, 0xdc, 0xf0, 0xaf, 0xae,
3754             0x34, 0xcf, 0x5f, 0x96, 0x4c, 0x73, 0x28, 0x0f,
3755             0x92, 0xc0, 0xf6, 0x9d, 0xd9, 0xb2, 0x09, 0x10,
3756             0x62
3757         };
3758         const unsigned char csr[32] = {
3759             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3760             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
3761             0x45, 0x51, 0x23, 0x19, 0x50, 0xb7, 0x5f, 0xc4,
3762             0x40, 0x2d, 0xa1, 0x72, 0x2f, 0xc9, 0xba, 0xeb
3763         };
3764         secp256k1_ge key;
3765         secp256k1_ge key2;
3766         secp256k1_scalar msg;
3767         secp256k1_scalar sr, ss;
3768         secp256k1_scalar_set_int(&ss, 1);
3769         secp256k1_scalar_set_int(&msg, 1);
3770         secp256k1_scalar_set_b32(&sr, csr, NULL);
3771         CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey, 33));
3772         CHECK(secp256k1_eckey_pubkey_parse(&key2, pubkey2, 33));
3773         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3774         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 1);
3775         secp256k1_scalar_negate(&ss, &ss);
3776         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3777         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 1);
3778         secp256k1_scalar_set_int(&ss, 2);
3779         secp256k1_scalar_inverse_var(&ss, &ss);
3780         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3781         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key2, &msg) == 0);
3782     }
3783
3784     /* Verify signature with message -1 passes. */
3785     {
3786         const unsigned char pubkey[33] = {
3787             0x03, 0xaf, 0x97, 0xff, 0x7d, 0x3a, 0xf6, 0xa0,
3788             0x02, 0x94, 0xbd, 0x9f, 0x4b, 0x2e, 0xd7, 0x52,
3789             0x28, 0xdb, 0x49, 0x2a, 0x65, 0xcb, 0x1e, 0x27,
3790             0x57, 0x9c, 0xba, 0x74, 0x20, 0xd5, 0x1d, 0x20,
3791             0xf1
3792         };
3793         const unsigned char csr[32] = {
3794             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3795             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
3796             0x45, 0x51, 0x23, 0x19, 0x50, 0xb7, 0x5f, 0xc4,
3797             0x40, 0x2d, 0xa1, 0x72, 0x2f, 0xc9, 0xba, 0xee
3798         };
3799         secp256k1_ge key;
3800         secp256k1_scalar msg;
3801         secp256k1_scalar sr, ss;
3802         secp256k1_scalar_set_int(&ss, 1);
3803         secp256k1_scalar_set_int(&msg, 1);
3804         secp256k1_scalar_negate(&msg, &msg);
3805         secp256k1_scalar_set_b32(&sr, csr, NULL);
3806         CHECK(secp256k1_eckey_pubkey_parse(&key, pubkey, 33));
3807         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3808         secp256k1_scalar_negate(&ss, &ss);
3809         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 1);
3810         secp256k1_scalar_set_int(&ss, 3);
3811         secp256k1_scalar_inverse_var(&ss, &ss);
3812         CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sr, &ss, &key, &msg) == 0);
3813     }
3814
3815     /* Signature where s would be zero. */
3816     {
3817         secp256k1_pubkey pubkey;
3818         size_t siglen;
3819         int32_t ecount;
3820         unsigned char signature[72];
3821         static const unsigned char nonce[32] = {
3822             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3823             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3824             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3825             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
3826         };
3827         static const unsigned char nonce2[32] = {
3828             0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
3829             0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
3830             0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
3831             0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x40
3832         };
3833         const unsigned char key[32] = {
3834             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3835             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3836             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
3837             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
3838         };
3839         unsigned char msg[32] = {
3840             0x86, 0x41, 0x99, 0x81, 0x06, 0x23, 0x44, 0x53,
3841             0xaa, 0x5f, 0x9d, 0x6a, 0x31, 0x78, 0xf4, 0xf7,
3842             0xb8, 0x12, 0xe0, 0x0b, 0x81, 0x7a, 0x77, 0x62,
3843             0x65, 0xdf, 0xdd, 0x31, 0xb9, 0x3e, 0x29, 0xa9,
3844         };
3845         ecount = 0;
3846         secp256k1_context_set_illegal_callback(ctx, counting_illegal_callback_fn, &ecount);
3847         CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, precomputed_nonce_function, nonce) == 0);
3848         CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, precomputed_nonce_function, nonce2) == 0);
3849         msg[31] = 0xaa;
3850         CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, precomputed_nonce_function, nonce) == 1);
3851         CHECK(ecount == 0);
3852         CHECK(secp256k1_ecdsa_sign(ctx, NULL, msg, key, precomputed_nonce_function, nonce2) == 0);
3853         CHECK(ecount == 1);
3854         CHECK(secp256k1_ecdsa_sign(ctx, &sig, NULL, key, precomputed_nonce_function, nonce2) == 0);
3855         CHECK(ecount == 2);
3856         CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, NULL, precomputed_nonce_function, nonce2) == 0);
3857         CHECK(ecount == 3);
3858         CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, precomputed_nonce_function, nonce2) == 1);
3859         CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey, key) == 1);
3860         CHECK(secp256k1_ecdsa_verify(ctx, NULL, msg, &pubkey) == 0);
3861         CHECK(ecount == 4);
3862         CHECK(secp256k1_ecdsa_verify(ctx, &sig, NULL, &pubkey) == 0);
3863         CHECK(ecount == 5);
3864         CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg, NULL) == 0);
3865         CHECK(ecount == 6);
3866         CHECK(secp256k1_ecdsa_verify(ctx, &sig, msg, &pubkey) == 1);
3867         siglen = 72;
3868         CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, NULL, &siglen, &sig) == 0);
3869         CHECK(ecount == 7);
3870         CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, signature, NULL, &sig) == 0);
3871         CHECK(ecount == 8);
3872         CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, signature, &siglen, NULL) == 0);
3873         CHECK(ecount == 9);
3874         CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, signature, &siglen, &sig) == 1);
3875         siglen = 10;
3876         CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, signature, &siglen, &sig) == 0);
3877         CHECK(ecount == 9);
3878         secp256k1_context_set_illegal_callback(ctx, NULL, NULL);
3879     }
3880
3881     /* Nonce function corner cases. */
3882     for (t = 0; t < 2; t++) {
3883         static const unsigned char zero[32] = {0x00};
3884         int i;
3885         unsigned char key[32];
3886         unsigned char msg[32];
3887         secp256k1_ecdsa_signature sig2;
3888         secp256k1_scalar sr[512], ss;
3889         const unsigned char *extra;
3890         extra = t == 0 ? NULL : zero;
3891         memset(msg, 0, 32);
3892         msg[31] = 1;
3893         /* High key results in signature failure. */
3894         memset(key, 0xFF, 32);
3895         CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, NULL, extra) == 0);
3896         CHECK(is_empty_signature(&sig));
3897         /* Zero key results in signature failure. */
3898         memset(key, 0, 32);
3899         CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, NULL, extra) == 0);
3900         CHECK(is_empty_signature(&sig));
3901         /* Nonce function failure results in signature failure. */
3902         key[31] = 1;
3903         CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, nonce_function_test_fail, extra) == 0);
3904         CHECK(is_empty_signature(&sig));
3905         /* The retry loop successfully makes its way to the first good value. */
3906         CHECK(secp256k1_ecdsa_sign(ctx, &sig, msg, key, nonce_function_test_retry, extra) == 1);
3907         CHECK(!is_empty_signature(&sig));
3908         CHECK(secp256k1_ecdsa_sign(ctx, &sig2, msg, key, nonce_function_rfc6979, extra) == 1);
3909         CHECK(!is_empty_signature(&sig2));
3910         CHECK(memcmp(&sig, &sig2, sizeof(sig)) == 0);
3911         /* The default nonce function is determinstic. */
3912         CHECK(secp256k1_ecdsa_sign(ctx, &sig2, msg, key, NULL, extra) == 1);
3913         CHECK(!is_empty_signature(&sig2));
3914         CHECK(memcmp(&sig, &sig2, sizeof(sig)) == 0);
3915         /* The default nonce function changes output with different messages. */
3916         for(i = 0; i < 256; i++) {
3917             int j;
3918             msg[0] = i;
3919             CHECK(secp256k1_ecdsa_sign(ctx, &sig2, msg, key, NULL, extra) == 1);
3920             CHECK(!is_empty_signature(&sig2));
3921             secp256k1_ecdsa_signature_load(ctx, &sr[i], &ss, &sig2);
3922             for (j = 0; j < i; j++) {
3923                 CHECK(!secp256k1_scalar_eq(&sr[i], &sr[j]));
3924             }
3925         }
3926         msg[0] = 0;
3927         msg[31] = 2;
3928         /* The default nonce function changes output with different keys. */
3929         for(i = 256; i < 512; i++) {
3930             int j;
3931             key[0] = i - 256;
3932             CHECK(secp256k1_ecdsa_sign(ctx, &sig2, msg, key, NULL, extra) == 1);
3933             CHECK(!is_empty_signature(&sig2));
3934             secp256k1_ecdsa_signature_load(ctx, &sr[i], &ss, &sig2);
3935             for (j = 0; j < i; j++) {
3936                 CHECK(!secp256k1_scalar_eq(&sr[i], &sr[j]));
3937             }
3938         }
3939         key[0] = 0;
3940     }
3941
3942     {
3943         /* Check that optional nonce arguments do not have equivilent effect. */
3944         const unsigned char zeros[32] = {0};
3945         unsigned char nonce[32];
3946         unsigned char nonce2[32];
3947         unsigned char nonce3[32];
3948         unsigned char nonce4[32];
3949         VG_UNDEF(nonce,32);
3950         VG_UNDEF(nonce2,32);
3951         VG_UNDEF(nonce3,32);
3952         VG_UNDEF(nonce4,32);
3953         CHECK(nonce_function_rfc6979(nonce, zeros, zeros, NULL, NULL, 0) == 1);
3954         VG_CHECK(nonce,32);
3955         CHECK(nonce_function_rfc6979(nonce2, zeros, zeros, zeros, NULL, 0) == 1);
3956         VG_CHECK(nonce2,32);
3957         CHECK(nonce_function_rfc6979(nonce3, zeros, zeros, NULL, (void *)zeros, 0) == 1);
3958         VG_CHECK(nonce3,32);
3959         CHECK(nonce_function_rfc6979(nonce4, zeros, zeros, zeros, (void *)zeros, 0) == 1);
3960         VG_CHECK(nonce4,32);
3961         CHECK(memcmp(nonce, nonce2, 32) != 0);
3962         CHECK(memcmp(nonce, nonce3, 32) != 0);
3963         CHECK(memcmp(nonce, nonce4, 32) != 0);
3964         CHECK(memcmp(nonce2, nonce3, 32) != 0);
3965         CHECK(memcmp(nonce2, nonce4, 32) != 0);
3966         CHECK(memcmp(nonce3, nonce4, 32) != 0);
3967     }
3968
3969
3970     /* Privkey export where pubkey is the point at infinity. */
3971     {
3972         unsigned char privkey[300];
3973         unsigned char seckey[32] = {
3974             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
3975             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
3976             0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
3977             0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41,
3978         };
3979         size_t outlen = 300;
3980         CHECK(!ec_privkey_export_der(ctx, privkey, &outlen, seckey, 0));
3981         outlen = 300;
3982         CHECK(!ec_privkey_export_der(ctx, privkey, &outlen, seckey, 1));
3983     }
3984 }
3985
3986 void run_ecdsa_edge_cases(void) {
3987     test_ecdsa_edge_cases();
3988 }
3989
3990 #ifdef ENABLE_OPENSSL_TESTS
3991 EC_KEY *get_openssl_key(const unsigned char *key32) {
3992     unsigned char privkey[300];
3993     size_t privkeylen;
3994     const unsigned char* pbegin = privkey;
3995     int compr = secp256k1_rand_bits(1);
3996     EC_KEY *ec_key = EC_KEY_new_by_curve_name(NID_secp256k1);
3997     CHECK(ec_privkey_export_der(ctx, privkey, &privkeylen, key32, compr));
3998     CHECK(d2i_ECPrivateKey(&ec_key, &pbegin, privkeylen));
3999     CHECK(EC_KEY_check_key(ec_key));
4000     return ec_key;
4001 }
4002
4003 void test_ecdsa_openssl(void) {
4004     secp256k1_gej qj;
4005     secp256k1_ge q;
4006     secp256k1_scalar sigr, sigs;
4007     secp256k1_scalar one;
4008     secp256k1_scalar msg2;
4009     secp256k1_scalar key, msg;
4010     EC_KEY *ec_key;
4011     unsigned int sigsize = 80;
4012     size_t secp_sigsize = 80;
4013     unsigned char message[32];
4014     unsigned char signature[80];
4015     unsigned char key32[32];
4016     secp256k1_rand256_test(message);
4017     secp256k1_scalar_set_b32(&msg, message, NULL);
4018     random_scalar_order_test(&key);
4019     secp256k1_scalar_get_b32(key32, &key);
4020     secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &qj, &key);
4021     secp256k1_ge_set_gej(&q, &qj);
4022     ec_key = get_openssl_key(key32);
4023     CHECK(ec_key != NULL);
4024     CHECK(ECDSA_sign(0, message, sizeof(message), signature, &sigsize, ec_key));
4025     CHECK(secp256k1_ecdsa_sig_parse(&sigr, &sigs, signature, sigsize));
4026     CHECK(secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sigr, &sigs, &q, &msg));
4027     secp256k1_scalar_set_int(&one, 1);
4028     secp256k1_scalar_add(&msg2, &msg, &one);
4029     CHECK(!secp256k1_ecdsa_sig_verify(&ctx->ecmult_ctx, &sigr, &sigs, &q, &msg2));
4030
4031     random_sign(&sigr, &sigs, &key, &msg, NULL);
4032     CHECK(secp256k1_ecdsa_sig_serialize(signature, &secp_sigsize, &sigr, &sigs));
4033     CHECK(ECDSA_verify(0, message, sizeof(message), signature, secp_sigsize, ec_key) == 1);
4034
4035     EC_KEY_free(ec_key);
4036 }
4037
4038 void run_ecdsa_openssl(void) {
4039     int i;
4040     for (i = 0; i < 10*count; i++) {
4041         test_ecdsa_openssl();
4042     }
4043 }
4044 #endif
4045
4046 #ifdef ENABLE_MODULE_ECDH
4047 # include "modules/ecdh/tests_impl.h"
4048 #endif
4049
4050 #ifdef ENABLE_MODULE_SCHNORR
4051 # include "modules/schnorr/tests_impl.h"
4052 #endif
4053
4054 #ifdef ENABLE_MODULE_RECOVERY
4055 # include "modules/recovery/tests_impl.h"
4056 #endif
4057
4058 int main(int argc, char **argv) {
4059     unsigned char seed16[16] = {0};
4060     unsigned char run32[32] = {0};
4061     /* find iteration count */
4062     if (argc > 1) {
4063         count = strtol(argv[1], NULL, 0);
4064     }
4065
4066     /* find random seed */
4067     if (argc > 2) {
4068         int pos = 0;
4069         const char* ch = argv[2];
4070         while (pos < 16 && ch[0] != 0 && ch[1] != 0) {
4071             unsigned short sh;
4072             if (sscanf(ch, "%2hx", &sh)) {
4073                 seed16[pos] = sh;
4074             } else {
4075                 break;
4076             }
4077             ch += 2;
4078             pos++;
4079         }
4080     } else {
4081         FILE *frand = fopen("/dev/urandom", "r");
4082         if ((frand == NULL) || !fread(&seed16, sizeof(seed16), 1, frand)) {
4083             uint64_t t = time(NULL) * (uint64_t)1337;
4084             seed16[0] ^= t;
4085             seed16[1] ^= t >> 8;
4086             seed16[2] ^= t >> 16;
4087             seed16[3] ^= t >> 24;
4088             seed16[4] ^= t >> 32;
4089             seed16[5] ^= t >> 40;
4090             seed16[6] ^= t >> 48;
4091             seed16[7] ^= t >> 56;
4092         }
4093         fclose(frand);
4094     }
4095     secp256k1_rand_seed(seed16);
4096
4097     printf("test count = %i\n", count);
4098     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]);
4099
4100     /* initialize */
4101     run_context_tests();
4102     ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY);
4103     if (secp256k1_rand_bits(1)) {
4104         secp256k1_rand256(run32);
4105         CHECK(secp256k1_context_randomize(ctx, secp256k1_rand_bits(1) ? run32 : NULL));
4106     }
4107
4108     run_rand_bits();
4109     run_rand_int();
4110
4111     run_sha256_tests();
4112     run_hmac_sha256_tests();
4113     run_rfc6979_hmac_sha256_tests();
4114
4115 #ifndef USE_NUM_NONE
4116     /* num tests */
4117     run_num_smalltests();
4118 #endif
4119
4120     /* scalar tests */
4121     run_scalar_tests();
4122
4123     /* field tests */
4124     run_field_inv();
4125     run_field_inv_var();
4126     run_field_inv_all_var();
4127     run_field_misc();
4128     run_field_convert();
4129     run_sqr();
4130     run_sqrt();
4131
4132     /* group tests */
4133     run_ge();
4134
4135     /* ecmult tests */
4136     run_wnaf();
4137     run_point_times_order();
4138     run_ecmult_chain();
4139     run_ecmult_constants();
4140     run_ecmult_gen_blind();
4141     run_ecmult_const_tests();
4142     run_ec_combine();
4143
4144     /* endomorphism tests */
4145 #ifdef USE_ENDOMORPHISM
4146     run_endomorphism_tests();
4147 #endif
4148
4149     /* EC point parser test */
4150     run_ec_pubkey_parse_test();
4151
4152     /* EC key edge cases */
4153     run_eckey_edge_case_test();
4154
4155 #ifdef ENABLE_MODULE_ECDH
4156     /* ecdh tests */
4157     run_ecdh_tests();
4158 #endif
4159
4160     /* ecdsa tests */
4161     run_random_pubkeys();
4162     run_ecdsa_der_parse();
4163     run_ecdsa_sign_verify();
4164     run_ecdsa_end_to_end();
4165     run_ecdsa_edge_cases();
4166 #ifdef ENABLE_OPENSSL_TESTS
4167     run_ecdsa_openssl();
4168 #endif
4169
4170 #ifdef ENABLE_MODULE_SCHNORR
4171     /* Schnorr tests */
4172     run_schnorr_tests();
4173 #endif
4174
4175 #ifdef ENABLE_MODULE_RECOVERY
4176     /* ECDSA pubkey recovery tests */
4177     run_recovery_tests();
4178 #endif
4179
4180     secp256k1_rand256(run32);
4181     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]);
4182
4183     /* shutdown */
4184     secp256k1_context_destroy(ctx);
4185
4186     printf("no problems found\n");
4187     return 0;
4188 }