src/tests.c

   1 /**********************************************************************
   2  * Copyright (c) 2013, 2014 Pieter Wuille                             *
   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 "testrand_impl.h"
  18
  19 #ifdef ENABLE_OPENSSL_TESTS
  20 #include "openssl/bn.h"
  21 #include "openssl/ec.h"
  22 #include "openssl/ecdsa.h"
  23 #include "openssl/obj_mac.h"
  24 #endif
  25
  26 static int count = 64;
  27
  28 void random_field_element_test(secp256k1_fe_t *fe) {
  29     do {
  30         unsigned char b32[32];
  31         secp256k1_rand256_test(b32);
  32         if (secp256k1_fe_set_b32(fe, b32)) {
  33             break;
  34         }
  35     } while(1);
  36 }
  37
  38 void random_field_element_magnitude(secp256k1_fe_t *fe) {
  39     secp256k1_fe_t zero;
  40     int n = secp256k1_rand32() % 9;
  41     secp256k1_fe_normalize(fe);
  42     if (n == 0) {
  43         return;
  44     }
  45     secp256k1_fe_clear(&zero);
  46     secp256k1_fe_negate(&zero, &zero, 0);
  47     secp256k1_fe_mul_int(&zero, n - 1);
  48     secp256k1_fe_add(fe, &zero);
  49 #ifdef VERIFY
  50     CHECK(fe->magnitude == n);
  51 #endif
  52 }
  53
  54 void random_group_element_test(secp256k1_ge_t *ge) {
  55     secp256k1_fe_t fe;
  56     do {
  57         random_field_element_test(&fe);
  58         if (secp256k1_ge_set_xo_var(ge, &fe, secp256k1_rand32() & 1)) {
  59             break;
  60         }
  61     } while(1);
  62 }
  63
  64 void random_group_element_jacobian_test(secp256k1_gej_t *gej, const secp256k1_ge_t *ge) {
  65     secp256k1_fe_t z2, z3;
  66     do {
  67         random_field_element_test(&gej->z);
  68         if (!secp256k1_fe_is_zero(&gej->z)) {
  69             break;
  70         }
  71     } while(1);
  72     secp256k1_fe_sqr(&z2, &gej->z);
  73     secp256k1_fe_mul(&z3, &z2, &gej->z);
  74     secp256k1_fe_mul(&gej->x, &ge->x, &z2);
  75     secp256k1_fe_mul(&gej->y, &ge->y, &z3);
  76     gej->infinity = ge->infinity;
  77 }
  78
  79 void random_scalar_order_test(secp256k1_scalar_t *num) {
  80     do {
  81         unsigned char b32[32];
  82         int overflow = 0;
  83         secp256k1_rand256_test(b32);
  84         secp256k1_scalar_set_b32(num, b32, &overflow);
  85         if (overflow || secp256k1_scalar_is_zero(num)) {
  86             continue;
  87         }
  88         break;
  89     } while(1);
  90 }
  91
  92 void random_scalar_order(secp256k1_scalar_t *num) {
  93     do {
  94         unsigned char b32[32];
  95         int overflow = 0;
  96         secp256k1_rand256(b32);
  97         secp256k1_scalar_set_b32(num, b32, &overflow);
  98         if (overflow || secp256k1_scalar_is_zero(num)) {
  99             continue;
 100         }
 101         break;
 102     } while(1);
 103 }
 104
 105 /***** HASH TESTS *****/
 106
 107 void run_sha256_tests(void) {
 108     static const char *inputs[8] = {
 109         "", "abc", "message digest", "secure hash algorithm", "SHA256 is considered to be safe",
 110         "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
 111         "For this sample, this 63-byte string will be used as input data",
 112         "This is exactly 64 bytes long, not counting the terminating byte"
 113     };
 114     static const unsigned char outputs[8][32] = {
 115         {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},
 116         {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},
 117         {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},
 118         {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},
 119         {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},
 120         {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},
 121         {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},
 122         {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}
 123     };
 124     int i;
 125     for (i = 0; i < 8; i++) {
 126         unsigned char out[32];
 127         secp256k1_sha256_t hasher;
 128         secp256k1_sha256_initialize(&hasher);
 129         secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i]), strlen(inputs[i]));
 130         secp256k1_sha256_finalize(&hasher, out);
 131         CHECK(memcmp(out, outputs[i], 32) == 0);
 132         if (strlen(inputs[i]) > 0) {
 133             int split = secp256k1_rand32() % strlen(inputs[i]);
 134             secp256k1_sha256_initialize(&hasher);
 135             secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i]), split);
 136             secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i] + split), strlen(inputs[i]) - split);
 137             secp256k1_sha256_finalize(&hasher, out);
 138             CHECK(memcmp(out, outputs[i], 32) == 0);
 139         }
 140     }
 141 }
 142
 143 void run_hmac_sha256_tests(void) {
 144     static const char *keys[6] = {
 145         "\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b",
 146         "\x4a\x65\x66\x65",
 147         "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa",
 148         "\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",
 149         "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa",
 150         "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa"
 151     };
 152     static const char *inputs[6] = {
 153         "\x48\x69\x20\x54\x68\x65\x72\x65",
 154         "\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",
 155         "\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",
 156         "\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",
 157         "\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",
 158         "\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"
 159     };
 160     static const unsigned char outputs[6][32] = {
 161         {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},
 162         {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},
 163         {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},
 164         {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},
 165         {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},
 166         {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}
 167     };
 168     int i;
 169     for (i = 0; i < 6; i++) {
 170         secp256k1_hmac_sha256_t hasher;
 171         unsigned char out[32];
 172         secp256k1_hmac_sha256_initialize(&hasher, (const unsigned char*)(keys[i]), strlen(keys[i]));
 173         secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i]), strlen(inputs[i]));
 174         secp256k1_hmac_sha256_finalize(&hasher, out);
 175         CHECK(memcmp(out, outputs[i], 32) == 0);
 176         if (strlen(inputs[i]) > 0) {
 177             int split = secp256k1_rand32() % strlen(inputs[i]);
 178             secp256k1_hmac_sha256_initialize(&hasher, (const unsigned char*)(keys[i]), strlen(keys[i]));
 179             secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i]), split);
 180             secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i] + split), strlen(inputs[i]) - split);
 181             secp256k1_hmac_sha256_finalize(&hasher, out);
 182             CHECK(memcmp(out, outputs[i], 32) == 0);
 183         }
 184     }
 185 }
 186
 187 void run_rfc6979_hmac_sha256_tests(void) {
 188     static const unsigned char key1[32] = {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};
 189     static const unsigned char msg1[32] = {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};
 190     static const unsigned char out1[3][32] = {
 191         {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},
 192         {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},
 193         {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}
 194     };
 195
 196     static const unsigned char key2[32] = {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};
 197     static const unsigned char msg2[32] = {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};
 198     static const unsigned char out2[3][32] = {
 199         {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},
 200         {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},
 201         {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}
 202     };
 203
 204     secp256k1_rfc6979_hmac_sha256_t rng;
 205     unsigned char out[32];
 206     unsigned char zero[1] = {0};
 207     int i;
 208
 209     secp256k1_rfc6979_hmac_sha256_initialize(&rng, key1, 32, msg1, 32, NULL, 1);
 210     for (i = 0; i < 3; i++) {
 211         secp256k1_rfc6979_hmac_sha256_generate(&rng, out, 32);
 212         CHECK(memcmp(out, out1[i], 32) == 0);
 213     }
 214     secp256k1_rfc6979_hmac_sha256_finalize(&rng);
 215
 216     secp256k1_rfc6979_hmac_sha256_initialize(&rng, key1, 32, msg1, 32, zero, 1);
 217     for (i = 0; i < 3; i++) {
 218         secp256k1_rfc6979_hmac_sha256_generate(&rng, out, 32);
 219         CHECK(memcmp(out, out1[i], 32) != 0);
 220     }
 221     secp256k1_rfc6979_hmac_sha256_finalize(&rng);
 222
 223     secp256k1_rfc6979_hmac_sha256_initialize(&rng, key2, 32, msg2, 32, zero, 0);
 224     for (i = 0; i < 3; i++) {
 225         secp256k1_rfc6979_hmac_sha256_generate(&rng, out, 32);
 226         CHECK(memcmp(out, out2[i], 32) == 0);
 227     }
 228     secp256k1_rfc6979_hmac_sha256_finalize(&rng);
 229 }
 230
 231 /***** NUM TESTS *****/
 232
 233 #ifndef USE_NUM_NONE
 234 void random_num_negate(secp256k1_num_t *num) {
 235     if (secp256k1_rand32() & 1) {
 236         secp256k1_num_negate(num);
 237     }
 238 }
 239
 240 void random_num_order_test(secp256k1_num_t *num) {
 241     secp256k1_scalar_t sc;
 242     random_scalar_order_test(&sc);
 243     secp256k1_scalar_get_num(num, &sc);
 244 }
 245
 246 void random_num_order(secp256k1_num_t *num) {
 247     secp256k1_scalar_t sc;
 248     random_scalar_order(&sc);
 249     secp256k1_scalar_get_num(num, &sc);
 250 }
 251
 252 void test_num_negate(void) {
 253     secp256k1_num_t n1;
 254     secp256k1_num_t n2;
 255     random_num_order_test(&n1); /* n1 = R */
 256     random_num_negate(&n1);
 257     secp256k1_num_copy(&n2, &n1); /* n2 = R */
 258     secp256k1_num_sub(&n1, &n2, &n1); /* n1 = n2-n1 = 0 */
 259     CHECK(secp256k1_num_is_zero(&n1));
 260     secp256k1_num_copy(&n1, &n2); /* n1 = R */
 261     secp256k1_num_negate(&n1); /* n1 = -R */
 262     CHECK(!secp256k1_num_is_zero(&n1));
 263     secp256k1_num_add(&n1, &n2, &n1); /* n1 = n2+n1 = 0 */
 264     CHECK(secp256k1_num_is_zero(&n1));
 265     secp256k1_num_copy(&n1, &n2); /* n1 = R */
 266     secp256k1_num_negate(&n1); /* n1 = -R */
 267     CHECK(secp256k1_num_is_neg(&n1) != secp256k1_num_is_neg(&n2));
 268     secp256k1_num_negate(&n1); /* n1 = R */
 269     CHECK(secp256k1_num_eq(&n1, &n2));
 270 }
 271
 272 void test_num_add_sub(void) {
 273     secp256k1_num_t n1;
 274     secp256k1_num_t n2;
 275     secp256k1_num_t n1p2, n2p1, n1m2, n2m1;
 276     int r = secp256k1_rand32();
 277     random_num_order_test(&n1); /* n1 = R1 */
 278     if (r & 1) {
 279         random_num_negate(&n1);
 280     }
 281     random_num_order_test(&n2); /* n2 = R2 */
 282     if (r & 2) {
 283         random_num_negate(&n2);
 284     }
 285     secp256k1_num_add(&n1p2, &n1, &n2); /* n1p2 = R1 + R2 */
 286     secp256k1_num_add(&n2p1, &n2, &n1); /* n2p1 = R2 + R1 */
 287     secp256k1_num_sub(&n1m2, &n1, &n2); /* n1m2 = R1 - R2 */
 288     secp256k1_num_sub(&n2m1, &n2, &n1); /* n2m1 = R2 - R1 */
 289     CHECK(secp256k1_num_eq(&n1p2, &n2p1));
 290     CHECK(!secp256k1_num_eq(&n1p2, &n1m2));
 291     secp256k1_num_negate(&n2m1); /* n2m1 = -R2 + R1 */
 292     CHECK(secp256k1_num_eq(&n2m1, &n1m2));
 293     CHECK(!secp256k1_num_eq(&n2m1, &n1));
 294     secp256k1_num_add(&n2m1, &n2m1, &n2); /* n2m1 = -R2 + R1 + R2 = R1 */
 295     CHECK(secp256k1_num_eq(&n2m1, &n1));
 296     CHECK(!secp256k1_num_eq(&n2p1, &n1));
 297     secp256k1_num_sub(&n2p1, &n2p1, &n2); /* n2p1 = R2 + R1 - R2 = R1 */
 298     CHECK(secp256k1_num_eq(&n2p1, &n1));
 299 }
 300
 301 void run_num_smalltests(void) {
 302     int i;
 303     for (i = 0; i < 100*count; i++) {
 304         test_num_negate();
 305         test_num_add_sub();
 306     }
 307 }
 308 #endif
 309
 310 /***** SCALAR TESTS *****/
 311
 312 void scalar_test(void) {
 313     secp256k1_scalar_t s;
 314     secp256k1_scalar_t s1;
 315     secp256k1_scalar_t s2;
 316 #ifndef USE_NUM_NONE
 317     secp256k1_num_t snum, s1num, s2num;
 318     secp256k1_num_t order, half_order;
 319 #endif
 320     unsigned char c[32];
 321
 322     /* Set 's' to a random scalar, with value 'snum'. */
 323     random_scalar_order_test(&s);
 324
 325     /* Set 's1' to a random scalar, with value 's1num'. */
 326     random_scalar_order_test(&s1);
 327
 328     /* Set 's2' to a random scalar, with value 'snum2', and byte array representation 'c'. */
 329     random_scalar_order_test(&s2);
 330     secp256k1_scalar_get_b32(c, &s2);
 331
 332 #ifndef USE_NUM_NONE
 333     secp256k1_scalar_get_num(&snum, &s);
 334     secp256k1_scalar_get_num(&s1num, &s1);
 335     secp256k1_scalar_get_num(&s2num, &s2);
 336
 337     secp256k1_scalar_order_get_num(&order);
 338     half_order = order;
 339     secp256k1_num_shift(&half_order, 1);
 340 #endif
 341
 342     {
 343         int i;
 344         /* Test that fetching groups of 4 bits from a scalar and recursing n(i)=16*n(i-1)+p(i) reconstructs it. */
 345         secp256k1_scalar_t n;
 346         secp256k1_scalar_set_int(&n, 0);
 347         for (i = 0; i < 256; i += 4) {
 348             secp256k1_scalar_t t;
 349             int j;
 350             secp256k1_scalar_set_int(&t, secp256k1_scalar_get_bits(&s, 256 - 4 - i, 4));
 351             for (j = 0; j < 4; j++) {
 352                 secp256k1_scalar_add(&n, &n, &n);
 353             }
 354             secp256k1_scalar_add(&n, &n, &t);
 355         }
 356         CHECK(secp256k1_scalar_eq(&n, &s));
 357     }
 358
 359     {
 360         /* Test that fetching groups of randomly-sized bits from a scalar and recursing n(i)=b*n(i-1)+p(i) reconstructs it. */
 361         secp256k1_scalar_t n;
 362         int i = 0;
 363         secp256k1_scalar_set_int(&n, 0);
 364         while (i < 256) {
 365             secp256k1_scalar_t t;
 366             int j;
 367             int now = (secp256k1_rand32() % 15) + 1;
 368             if (now + i > 256) {
 369                 now = 256 - i;
 370             }
 371             secp256k1_scalar_set_int(&t, secp256k1_scalar_get_bits_var(&s, 256 - now - i, now));
 372             for (j = 0; j < now; j++) {
 373                 secp256k1_scalar_add(&n, &n, &n);
 374             }
 375             secp256k1_scalar_add(&n, &n, &t);
 376             i += now;
 377         }
 378         CHECK(secp256k1_scalar_eq(&n, &s));
 379     }
 380
 381 #ifndef USE_NUM_NONE
 382     {
 383         /* Test that adding the scalars together is equal to adding their numbers together modulo the order. */
 384         secp256k1_num_t rnum;
 385         secp256k1_num_t r2num;
 386         secp256k1_scalar_t r;
 387         secp256k1_num_add(&rnum, &snum, &s2num);
 388         secp256k1_num_mod(&rnum, &order);
 389         secp256k1_scalar_add(&r, &s, &s2);
 390         secp256k1_scalar_get_num(&r2num, &r);
 391         CHECK(secp256k1_num_eq(&rnum, &r2num));
 392     }
 393
 394     {
 395         /* Test that multipying the scalars is equal to multiplying their numbers modulo the order. */
 396         secp256k1_scalar_t r;
 397         secp256k1_num_t r2num;
 398         secp256k1_num_t rnum;
 399         secp256k1_num_mul(&rnum, &snum, &s2num);
 400         secp256k1_num_mod(&rnum, &order);
 401         secp256k1_scalar_mul(&r, &s, &s2);
 402         secp256k1_scalar_get_num(&r2num, &r);
 403         CHECK(secp256k1_num_eq(&rnum, &r2num));
 404         /* The result can only be zero if at least one of the factors was zero. */
 405         CHECK(secp256k1_scalar_is_zero(&r) == (secp256k1_scalar_is_zero(&s) || secp256k1_scalar_is_zero(&s2)));
 406         /* The results can only be equal to one of the factors if that factor was zero, or the other factor was one. */
 407         CHECK(secp256k1_num_eq(&rnum, &snum) == (secp256k1_scalar_is_zero(&s) || secp256k1_scalar_is_one(&s2)));
 408         CHECK(secp256k1_num_eq(&rnum, &s2num) == (secp256k1_scalar_is_zero(&s2) || secp256k1_scalar_is_one(&s)));
 409     }
 410
 411     {
 412         secp256k1_scalar_t neg;
 413         secp256k1_num_t negnum;
 414         secp256k1_num_t negnum2;
 415         /* Check that comparison with zero matches comparison with zero on the number. */
 416         CHECK(secp256k1_num_is_zero(&snum) == secp256k1_scalar_is_zero(&s));
 417         /* Check that comparison with the half order is equal to testing for high scalar. */
 418         CHECK(secp256k1_scalar_is_high(&s) == (secp256k1_num_cmp(&snum, &half_order) > 0));
 419         secp256k1_scalar_negate(&neg, &s);
 420         secp256k1_num_sub(&negnum, &order, &snum);
 421         secp256k1_num_mod(&negnum, &order);
 422         /* Check that comparison with the half order is equal to testing for high scalar after negation. */
 423         CHECK(secp256k1_scalar_is_high(&neg) == (secp256k1_num_cmp(&negnum, &half_order) > 0));
 424         /* Negating should change the high property, unless the value was already zero. */
 425         CHECK((secp256k1_scalar_is_high(&s) == secp256k1_scalar_is_high(&neg)) == secp256k1_scalar_is_zero(&s));
 426         secp256k1_scalar_get_num(&negnum2, &neg);
 427         /* Negating a scalar should be equal to (order - n) mod order on the number. */
 428         CHECK(secp256k1_num_eq(&negnum, &negnum2));
 429         secp256k1_scalar_add(&neg, &neg, &s);
 430         /* Adding a number to its negation should result in zero. */
 431         CHECK(secp256k1_scalar_is_zero(&neg));
 432         secp256k1_scalar_negate(&neg, &neg);
 433         /* Negating zero should still result in zero. */
 434         CHECK(secp256k1_scalar_is_zero(&neg));
 435     }
 436
 437     {
 438         /* Test secp256k1_scalar_mul_shift_var. */
 439         secp256k1_scalar_t r;
 440         secp256k1_num_t one;
 441         secp256k1_num_t rnum;
 442         secp256k1_num_t rnum2;
 443         unsigned char cone[1] = {0x01};
 444         unsigned int shift = 256 + (secp256k1_rand32() % 257);
 445         secp256k1_scalar_mul_shift_var(&r, &s1, &s2, shift);
 446         secp256k1_num_mul(&rnum, &s1num, &s2num);
 447         secp256k1_num_shift(&rnum, shift - 1);
 448         secp256k1_num_set_bin(&one, cone, 1);
 449         secp256k1_num_add(&rnum, &rnum, &one);
 450         secp256k1_num_shift(&rnum, 1);
 451         secp256k1_scalar_get_num(&rnum2, &r);
 452         CHECK(secp256k1_num_eq(&rnum, &rnum2));
 453     }
 454 #endif
 455
 456     {
 457         /* Test that scalar inverses are equal to the inverse of their number modulo the order. */
 458         if (!secp256k1_scalar_is_zero(&s)) {
 459             secp256k1_scalar_t inv;
 460 #ifndef USE_NUM_NONE
 461             secp256k1_num_t invnum;
 462             secp256k1_num_t invnum2;
 463 #endif
 464             secp256k1_scalar_inverse(&inv, &s);
 465 #ifndef USE_NUM_NONE
 466             secp256k1_num_mod_inverse(&invnum, &snum, &order);
 467             secp256k1_scalar_get_num(&invnum2, &inv);
 468             CHECK(secp256k1_num_eq(&invnum, &invnum2));
 469 #endif
 470             secp256k1_scalar_mul(&inv, &inv, &s);
 471             /* Multiplying a scalar with its inverse must result in one. */
 472             CHECK(secp256k1_scalar_is_one(&inv));
 473             secp256k1_scalar_inverse(&inv, &inv);
 474             /* Inverting one must result in one. */
 475             CHECK(secp256k1_scalar_is_one(&inv));
 476         }
 477     }
 478
 479     {
 480         /* Test commutativity of add. */
 481         secp256k1_scalar_t r1, r2;
 482         secp256k1_scalar_add(&r1, &s1, &s2);
 483         secp256k1_scalar_add(&r2, &s2, &s1);
 484         CHECK(secp256k1_scalar_eq(&r1, &r2));
 485     }
 486
 487     {
 488         secp256k1_scalar_t r1, r2;
 489         secp256k1_scalar_t b;
 490         int i;
 491         /* Test add_bit. */
 492         int bit = secp256k1_rand32() % 256;
 493         secp256k1_scalar_set_int(&b, 1);
 494         CHECK(secp256k1_scalar_is_one(&b));
 495         for (i = 0; i < bit; i++) {
 496             secp256k1_scalar_add(&b, &b, &b);
 497         }
 498         r1 = s1;
 499         r2 = s1;
 500         if (!secp256k1_scalar_add(&r1, &r1, &b)) {
 501             /* No overflow happened. */
 502             secp256k1_scalar_add_bit(&r2, bit);
 503             CHECK(secp256k1_scalar_eq(&r1, &r2));
 504         }
 505     }
 506
 507     {
 508         /* Test commutativity of mul. */
 509         secp256k1_scalar_t r1, r2;
 510         secp256k1_scalar_mul(&r1, &s1, &s2);
 511         secp256k1_scalar_mul(&r2, &s2, &s1);
 512         CHECK(secp256k1_scalar_eq(&r1, &r2));
 513     }
 514
 515     {
 516         /* Test associativity of add. */
 517         secp256k1_scalar_t r1, r2;
 518         secp256k1_scalar_add(&r1, &s1, &s2);
 519         secp256k1_scalar_add(&r1, &r1, &s);
 520         secp256k1_scalar_add(&r2, &s2, &s);
 521         secp256k1_scalar_add(&r2, &s1, &r2);
 522         CHECK(secp256k1_scalar_eq(&r1, &r2));
 523     }
 524
 525     {
 526         /* Test associativity of mul. */
 527         secp256k1_scalar_t r1, r2;
 528         secp256k1_scalar_mul(&r1, &s1, &s2);
 529         secp256k1_scalar_mul(&r1, &r1, &s);
 530         secp256k1_scalar_mul(&r2, &s2, &s);
 531         secp256k1_scalar_mul(&r2, &s1, &r2);
 532         CHECK(secp256k1_scalar_eq(&r1, &r2));
 533     }
 534
 535     {
 536         /* Test distributitivity of mul over add. */
 537         secp256k1_scalar_t r1, r2, t;
 538         secp256k1_scalar_add(&r1, &s1, &s2);
 539         secp256k1_scalar_mul(&r1, &r1, &s);
 540         secp256k1_scalar_mul(&r2, &s1, &s);
 541         secp256k1_scalar_mul(&t, &s2, &s);
 542         secp256k1_scalar_add(&r2, &r2, &t);
 543         CHECK(secp256k1_scalar_eq(&r1, &r2));
 544     }
 545
 546     {
 547         /* Test square. */
 548         secp256k1_scalar_t r1, r2;
 549         secp256k1_scalar_sqr(&r1, &s1);
 550         secp256k1_scalar_mul(&r2, &s1, &s1);
 551         CHECK(secp256k1_scalar_eq(&r1, &r2));
 552     }
 553
 554     {
 555         /* Test multiplicative identity. */
 556         secp256k1_scalar_t r1, v1;
 557         secp256k1_scalar_set_int(&v1,1);
 558         secp256k1_scalar_mul(&r1, &s1, &v1);
 559         CHECK(secp256k1_scalar_eq(&r1, &s1));
 560     }
 561
 562     {
 563         /* Test additive identity. */
 564         secp256k1_scalar_t r1, v0;
 565         secp256k1_scalar_set_int(&v0,0);
 566         secp256k1_scalar_add(&r1, &s1, &v0);
 567         CHECK(secp256k1_scalar_eq(&r1, &s1));
 568     }
 569
 570     {
 571         /* Test zero product property. */
 572         secp256k1_scalar_t r1, v0;
 573         secp256k1_scalar_set_int(&v0,0);
 574         secp256k1_scalar_mul(&r1, &s1, &v0);
 575         CHECK(secp256k1_scalar_eq(&r1, &v0));
 576     }
 577
 578 }
 579
 580 void run_scalar_tests(void) {
 581     int i;
 582     for (i = 0; i < 128 * count; i++) {
 583         scalar_test();
 584     }
 585
 586     {
 587         /* (-1)+1 should be zero. */
 588         secp256k1_scalar_t s, o;
 589         secp256k1_scalar_set_int(&s, 1);
 590         CHECK(secp256k1_scalar_is_one(&s));
 591         secp256k1_scalar_negate(&o, &s);
 592         secp256k1_scalar_add(&o, &o, &s);
 593         CHECK(secp256k1_scalar_is_zero(&o));
 594         secp256k1_scalar_negate(&o, &o);
 595         CHECK(secp256k1_scalar_is_zero(&o));
 596     }
 597
 598 #ifndef USE_NUM_NONE
 599     {
 600         /* A scalar with value of the curve order should be 0. */
 601         secp256k1_num_t order;
 602         secp256k1_scalar_t zero;
 603         unsigned char bin[32];
 604         int overflow = 0;
 605         secp256k1_scalar_order_get_num(&order);
 606         secp256k1_num_get_bin(bin, 32, &order);
 607         secp256k1_scalar_set_b32(&zero, bin, &overflow);
 608         CHECK(overflow == 1);
 609         CHECK(secp256k1_scalar_is_zero(&zero));
 610     }
 611 #endif
 612 }
 613
 614 /***** FIELD TESTS *****/
 615
 616 void random_fe(secp256k1_fe_t *x) {
 617     unsigned char bin[32];
 618     do {
 619         secp256k1_rand256(bin);
 620         if (secp256k1_fe_set_b32(x, bin)) {
 621             return;
 622         }
 623     } while(1);
 624 }
 625
 626 void random_fe_non_zero(secp256k1_fe_t *nz) {
 627     int tries = 10;
 628     while (--tries >= 0) {
 629         random_fe(nz);
 630         secp256k1_fe_normalize(nz);
 631         if (!secp256k1_fe_is_zero(nz)) {
 632             break;
 633         }
 634     }
 635     /* Infinitesimal probability of spurious failure here */
 636     CHECK(tries >= 0);
 637 }
 638
 639 void random_fe_non_square(secp256k1_fe_t *ns) {
 640     secp256k1_fe_t r;
 641     random_fe_non_zero(ns);
 642     if (secp256k1_fe_sqrt_var(&r, ns)) {
 643         secp256k1_fe_negate(ns, ns, 1);
 644     }
 645 }
 646
 647 int check_fe_equal(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
 648     secp256k1_fe_t an = *a;
 649     secp256k1_fe_t bn = *b;
 650     secp256k1_fe_normalize_weak(&an);
 651     secp256k1_fe_normalize_var(&bn);
 652     return secp256k1_fe_equal_var(&an, &bn);
 653 }
 654
 655 int check_fe_inverse(const secp256k1_fe_t *a, const secp256k1_fe_t *ai) {
 656     secp256k1_fe_t x;
 657     secp256k1_fe_t one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1);
 658     secp256k1_fe_mul(&x, a, ai);
 659     return check_fe_equal(&x, &one);
 660 }
 661
 662 void run_field_convert(void) {
 663     static const unsigned char b32[32] = {
 664         0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
 665         0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18,
 666         0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29,
 667         0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x40
 668     };
 669     static const secp256k1_fe_storage_t fes = SECP256K1_FE_STORAGE_CONST(
 670         0x00010203UL, 0x04050607UL, 0x11121314UL, 0x15161718UL,
 671         0x22232425UL, 0x26272829UL, 0x33343536UL, 0x37383940UL
 672     );
 673     static const secp256k1_fe_t fe = SECP256K1_FE_CONST(
 674         0x00010203UL, 0x04050607UL, 0x11121314UL, 0x15161718UL,
 675         0x22232425UL, 0x26272829UL, 0x33343536UL, 0x37383940UL
 676     );
 677     secp256k1_fe_t fe2;
 678     unsigned char b322[32];
 679     secp256k1_fe_storage_t fes2;
 680     /* Check conversions to fe. */
 681     CHECK(secp256k1_fe_set_b32(&fe2, b32));
 682     CHECK(secp256k1_fe_equal_var(&fe, &fe2));
 683     secp256k1_fe_from_storage(&fe2, &fes);
 684     CHECK(secp256k1_fe_equal_var(&fe, &fe2));
 685     /* Check conversion from fe. */
 686     secp256k1_fe_get_b32(b322, &fe);
 687     CHECK(memcmp(b322, b32, 32) == 0);
 688     secp256k1_fe_to_storage(&fes2, &fe);
 689     CHECK(memcmp(&fes2, &fes, sizeof(fes)) == 0);
 690 }
 691
 692 void run_field_misc(void) {
 693     secp256k1_fe_t x;
 694     secp256k1_fe_t y;
 695     secp256k1_fe_t z;
 696     secp256k1_fe_t q;
 697     secp256k1_fe_t fe5 = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 5);
 698     int i;
 699     for (i = 0; i < 5*count; i++) {
 700         secp256k1_fe_storage_t xs, ys, zs;
 701         random_fe(&x);
 702         random_fe_non_zero(&y);
 703         /* Test the fe equality and comparison operations. */
 704         CHECK(secp256k1_fe_cmp_var(&x, &x) == 0);
 705         CHECK(secp256k1_fe_equal_var(&x, &x));
 706         z = x;
 707         secp256k1_fe_add(&z,&y);
 708         secp256k1_fe_normalize(&z);
 709         /* Test storage conversion and conditional moves. */
 710         secp256k1_fe_to_storage(&xs, &x);
 711         secp256k1_fe_to_storage(&ys, &y);
 712         secp256k1_fe_to_storage(&zs, &z);
 713         secp256k1_fe_storage_cmov(&zs, &xs, 0);
 714         CHECK(memcmp(&xs, &zs, sizeof(xs)) != 0);
 715         secp256k1_fe_storage_cmov(&ys, &xs, 1);
 716         CHECK(memcmp(&xs, &ys, sizeof(xs)) == 0);
 717         secp256k1_fe_from_storage(&x, &xs);
 718         secp256k1_fe_from_storage(&y, &ys);
 719         secp256k1_fe_from_storage(&z, &zs);
 720         /* Test that mul_int, mul, and add agree. */
 721         secp256k1_fe_add(&y, &x);
 722         secp256k1_fe_add(&y, &x);
 723         z = x;
 724         secp256k1_fe_mul_int(&z, 3);
 725         CHECK(check_fe_equal(&y, &z));
 726         secp256k1_fe_add(&y, &x);
 727         secp256k1_fe_add(&z, &x);
 728         CHECK(check_fe_equal(&z, &y));
 729         z = x;
 730         secp256k1_fe_mul_int(&z, 5);
 731         secp256k1_fe_mul(&q, &x, &fe5);
 732         CHECK(check_fe_equal(&z, &q));
 733         secp256k1_fe_negate(&x, &x, 1);
 734         secp256k1_fe_add(&z, &x);
 735         secp256k1_fe_add(&q, &x);
 736         CHECK(check_fe_equal(&y, &z));
 737         CHECK(check_fe_equal(&q, &y));
 738     }
 739 }
 740
 741 void run_field_inv(void) {
 742     secp256k1_fe_t x, xi, xii;
 743     int i;
 744     for (i = 0; i < 10*count; i++) {
 745         random_fe_non_zero(&x);
 746         secp256k1_fe_inv(&xi, &x);
 747         CHECK(check_fe_inverse(&x, &xi));
 748         secp256k1_fe_inv(&xii, &xi);
 749         CHECK(check_fe_equal(&x, &xii));
 750     }
 751 }
 752
 753 void run_field_inv_var(void) {
 754     secp256k1_fe_t x, xi, xii;
 755     int i;
 756     for (i = 0; i < 10*count; i++) {
 757         random_fe_non_zero(&x);
 758         secp256k1_fe_inv_var(&xi, &x);
 759         CHECK(check_fe_inverse(&x, &xi));
 760         secp256k1_fe_inv_var(&xii, &xi);
 761         CHECK(check_fe_equal(&x, &xii));
 762     }
 763 }
 764
 765 void run_field_inv_all_var(void) {
 766     secp256k1_fe_t x[16], xi[16], xii[16];
 767     int i;
 768     /* Check it's safe to call for 0 elements */
 769     secp256k1_fe_inv_all_var(0, xi, x);
 770     for (i = 0; i < count; i++) {
 771         size_t j;
 772         size_t len = (secp256k1_rand32() & 15) + 1;
 773         for (j = 0; j < len; j++) {
 774             random_fe_non_zero(&x[j]);
 775         }
 776         secp256k1_fe_inv_all_var(len, xi, x);
 777         for (j = 0; j < len; j++) {
 778             CHECK(check_fe_inverse(&x[j], &xi[j]));
 779         }
 780         secp256k1_fe_inv_all_var(len, xii, xi);
 781         for (j = 0; j < len; j++) {
 782             CHECK(check_fe_equal(&x[j], &xii[j]));
 783         }
 784     }
 785 }
 786
 787 void run_sqr(void) {
 788     secp256k1_fe_t x, s;
 789
 790     {
 791         int i;
 792         secp256k1_fe_set_int(&x, 1);
 793         secp256k1_fe_negate(&x, &x, 1);
 794
 795         for (i = 1; i <= 512; ++i) {
 796             secp256k1_fe_mul_int(&x, 2);
 797             secp256k1_fe_normalize(&x);
 798             secp256k1_fe_sqr(&s, &x);
 799         }
 800     }
 801 }
 802
 803 void test_sqrt(const secp256k1_fe_t *a, const secp256k1_fe_t *k) {
 804     secp256k1_fe_t r1, r2;
 805     int v = secp256k1_fe_sqrt_var(&r1, a);
 806     CHECK((v == 0) == (k == NULL));
 807
 808     if (k != NULL) {
 809         /* Check that the returned root is +/- the given known answer */
 810         secp256k1_fe_negate(&r2, &r1, 1);
 811         secp256k1_fe_add(&r1, k); secp256k1_fe_add(&r2, k);
 812         secp256k1_fe_normalize(&r1); secp256k1_fe_normalize(&r2);
 813         CHECK(secp256k1_fe_is_zero(&r1) || secp256k1_fe_is_zero(&r2));
 814     }
 815 }
 816
 817 void run_sqrt(void) {
 818     secp256k1_fe_t ns, x, s, t;
 819     int i;
 820
 821     /* Check sqrt(0) is 0 */
 822     secp256k1_fe_set_int(&x, 0);
 823     secp256k1_fe_sqr(&s, &x);
 824     test_sqrt(&s, &x);
 825
 826     /* Check sqrt of small squares (and their negatives) */
 827     for (i = 1; i <= 100; i++) {
 828         secp256k1_fe_set_int(&x, i);
 829         secp256k1_fe_sqr(&s, &x);
 830         test_sqrt(&s, &x);
 831         secp256k1_fe_negate(&t, &s, 1);
 832         test_sqrt(&t, NULL);
 833     }
 834
 835     /* Consistency checks for large random values */
 836     for (i = 0; i < 10; i++) {
 837         int j;
 838         random_fe_non_square(&ns);
 839         for (j = 0; j < count; j++) {
 840             random_fe(&x);
 841             secp256k1_fe_sqr(&s, &x);
 842             test_sqrt(&s, &x);
 843             secp256k1_fe_negate(&t, &s, 1);
 844             test_sqrt(&t, NULL);
 845             secp256k1_fe_mul(&t, &s, &ns);
 846             test_sqrt(&t, NULL);
 847         }
 848     }
 849 }
 850
 851 /***** GROUP TESTS *****/
 852
 853 void ge_equals_ge(const secp256k1_ge_t *a, const secp256k1_ge_t *b) {
 854     CHECK(a->infinity == b->infinity);
 855     if (a->infinity) {
 856         return;
 857     }
 858     CHECK(secp256k1_fe_equal_var(&a->x, &b->x));
 859     CHECK(secp256k1_fe_equal_var(&b->y, &b->y));
 860 }
 861
 862 void ge_equals_gej(const secp256k1_ge_t *a, const secp256k1_gej_t *b) {
 863     secp256k1_fe_t z2s;
 864     secp256k1_fe_t u1, u2, s1, s2;
 865     CHECK(a->infinity == b->infinity);
 866     if (a->infinity) {
 867         return;
 868     }
 869     /* Check a.x * b.z^2 == b.x && a.y * b.z^3 == b.y, to avoid inverses. */
 870     secp256k1_fe_sqr(&z2s, &b->z);
 871     secp256k1_fe_mul(&u1, &a->x, &z2s);
 872     u2 = b->x; secp256k1_fe_normalize_weak(&u2);
 873     secp256k1_fe_mul(&s1, &a->y, &z2s); secp256k1_fe_mul(&s1, &s1, &b->z);
 874     s2 = b->y; secp256k1_fe_normalize_weak(&s2);
 875     CHECK(secp256k1_fe_equal_var(&u1, &u2));
 876     CHECK(secp256k1_fe_equal_var(&s1, &s2));
 877 }
 878
 879 void test_ge(void) {
 880     int i, i1;
 881     int runs = 4;
 882     /* Points: (infinity, p1, p1, -p1, -p1, p2, p2, -p2, -p2, p3, p3, -p3, -p3, p4, p4, -p4, -p4).
 883      * The second in each pair of identical points uses a random Z coordinate in the Jacobian form.
 884      * All magnitudes are randomized.
 885      * All 17*17 combinations of points are added to eachother, using all applicable methods.
 886      */
 887     secp256k1_ge_t *ge = (secp256k1_ge_t *)malloc(sizeof(secp256k1_ge_t) * (1 + 4 * runs));
 888     secp256k1_gej_t *gej = (secp256k1_gej_t *)malloc(sizeof(secp256k1_gej_t) * (1 + 4 * runs));
 889     secp256k1_gej_set_infinity(&gej[0]);
 890     secp256k1_ge_clear(&ge[0]);
 891     secp256k1_ge_set_gej_var(&ge[0], &gej[0]);
 892     for (i = 0; i < runs; i++) {
 893         int j;
 894         secp256k1_ge_t g;
 895         random_group_element_test(&g);
 896         ge[1 + 4 * i] = g;
 897         ge[2 + 4 * i] = g;
 898         secp256k1_ge_neg(&ge[3 + 4 * i], &g);
 899         secp256k1_ge_neg(&ge[4 + 4 * i], &g);
 900         secp256k1_gej_set_ge(&gej[1 + 4 * i], &ge[1 + 4 * i]);
 901         random_group_element_jacobian_test(&gej[2 + 4 * i], &ge[2 + 4 * i]);
 902         secp256k1_gej_set_ge(&gej[3 + 4 * i], &ge[3 + 4 * i]);
 903         random_group_element_jacobian_test(&gej[4 + 4 * i], &ge[4 + 4 * i]);
 904         for (j = 0; j < 4; j++) {
 905             random_field_element_magnitude(&ge[1 + j + 4 * i].x);
 906             random_field_element_magnitude(&ge[1 + j + 4 * i].y);
 907             random_field_element_magnitude(&gej[1 + j + 4 * i].x);
 908             random_field_element_magnitude(&gej[1 + j + 4 * i].y);
 909             random_field_element_magnitude(&gej[1 + j + 4 * i].z);
 910         }
 911     }
 912
 913     for (i1 = 0; i1 < 1 + 4 * runs; i1++) {
 914         int i2;
 915         for (i2 = 0; i2 < 1 + 4 * runs; i2++) {
 916             /* Compute reference result using gej + gej (var). */
 917             secp256k1_gej_t refj, resj;
 918             secp256k1_ge_t ref;
 919             secp256k1_gej_add_var(&refj, &gej[i1], &gej[i2]);
 920             secp256k1_ge_set_gej_var(&ref, &refj);
 921
 922             /* Test gej + ge (var). */
 923             secp256k1_gej_add_ge_var(&resj, &gej[i1], &ge[i2]);
 924             ge_equals_gej(&ref, &resj);
 925
 926             /* Test gej + ge (const). */
 927             if (i2 != 0) {
 928                 /* secp256k1_gej_add_ge does not support its second argument being infinity. */
 929                 secp256k1_gej_add_ge(&resj, &gej[i1], &ge[i2]);
 930                 ge_equals_gej(&ref, &resj);
 931             }
 932
 933             /* Test doubling (var). */
 934             if ((i1 == 0 && i2 == 0) || ((i1 + 3)/4 == (i2 + 3)/4 && ((i1 + 3)%4)/2 == ((i2 + 3)%4)/2)) {
 935                 /* Normal doubling. */
 936                 secp256k1_gej_double_var(&resj, &gej[i1]);
 937                 ge_equals_gej(&ref, &resj);
 938                 secp256k1_gej_double_var(&resj, &gej[i2]);
 939                 ge_equals_gej(&ref, &resj);
 940             }
 941
 942             /* Test adding opposites. */
 943             if ((i1 == 0 && i2 == 0) || ((i1 + 3)/4 == (i2 + 3)/4 && ((i1 + 3)%4)/2 != ((i2 + 3)%4)/2)) {
 944                 CHECK(secp256k1_ge_is_infinity(&ref));
 945             }
 946
 947             /* Test adding infinity. */
 948             if (i1 == 0) {
 949                 CHECK(secp256k1_ge_is_infinity(&ge[i1]));
 950                 CHECK(secp256k1_gej_is_infinity(&gej[i1]));
 951                 ge_equals_gej(&ref, &gej[i2]);
 952             }
 953             if (i2 == 0) {
 954                 CHECK(secp256k1_ge_is_infinity(&ge[i2]));
 955                 CHECK(secp256k1_gej_is_infinity(&gej[i2]));
 956                 ge_equals_gej(&ref, &gej[i1]);
 957             }
 958         }
 959     }
 960
 961     /* Test adding all points together in random order equals infinity. */
 962     {
 963         secp256k1_gej_t sum = SECP256K1_GEJ_CONST_INFINITY;
 964         secp256k1_gej_t *gej_shuffled = (secp256k1_gej_t *)malloc((4 * runs + 1) * sizeof(secp256k1_gej_t));
 965         for (i = 0; i < 4 * runs + 1; i++) {
 966             gej_shuffled[i] = gej[i];
 967         }
 968         for (i = 0; i < 4 * runs + 1; i++) {
 969             int swap = i + secp256k1_rand32() % (4 * runs + 1 - i);
 970             if (swap != i) {
 971                 secp256k1_gej_t t = gej_shuffled[i];
 972                 gej_shuffled[i] = gej_shuffled[swap];
 973                 gej_shuffled[swap] = t;
 974             }
 975         }
 976         for (i = 0; i < 4 * runs + 1; i++) {
 977             secp256k1_gej_add_var(&sum, &sum, &gej_shuffled[i]);
 978         }
 979         CHECK(secp256k1_gej_is_infinity(&sum));
 980         free(gej_shuffled);
 981     }
 982
 983     /* Test batch gej -> ge conversion. */
 984     {
 985         secp256k1_ge_t *ge_set_all = (secp256k1_ge_t *)malloc((4 * runs + 1) * sizeof(secp256k1_ge_t));
 986         secp256k1_ge_set_all_gej_var(4 * runs + 1, ge_set_all, gej);
 987         for (i = 0; i < 4 * runs + 1; i++) {
 988             ge_equals_gej(&ge_set_all[i], &gej[i]);
 989         }
 990         free(ge_set_all);
 991     }
 992
 993     free(ge);
 994     free(gej);
 995 }
 996
 997 void run_ge(void) {
 998     int i;
 999     for (i = 0; i < count * 32; i++) {
1000         test_ge();
1001     }
1002 }
1003
1004 /***** ECMULT TESTS *****/
1005
1006 void run_ecmult_chain(void) {
1007     /* random starting point A (on the curve) */
1008     secp256k1_gej_t a = SECP256K1_GEJ_CONST(
1009         0x8b30bbe9, 0xae2a9906, 0x96b22f67, 0x0709dff3,
1010         0x727fd8bc, 0x04d3362c, 0x6c7bf458, 0xe2846004,
1011         0xa357ae91, 0x5c4a6528, 0x1309edf2, 0x0504740f,
1012         0x0eb33439, 0x90216b4f, 0x81063cb6, 0x5f2f7e0f
1013     );
1014     /* two random initial factors xn and gn */
1015     secp256k1_scalar_t xn = SECP256K1_SCALAR_CONST(
1016         0x84cc5452, 0xf7fde1ed, 0xb4d38a8c, 0xe9b1b84c,
1017         0xcef31f14, 0x6e569be9, 0x705d357a, 0x42985407
1018     );
1019     secp256k1_scalar_t gn = SECP256K1_SCALAR_CONST(
1020         0xa1e58d22, 0x553dcd42, 0xb2398062, 0x5d4c57a9,
1021         0x6e9323d4, 0x2b3152e5, 0xca2c3990, 0xedc7c9de
1022     );
1023     /* two small multipliers to be applied to xn and gn in every iteration: */
1024     static const secp256k1_scalar_t xf = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0x1337);
1025     static const secp256k1_scalar_t gf = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0x7113);
1026     /* accumulators with the resulting coefficients to A and G */
1027     secp256k1_scalar_t ae = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1);
1028     secp256k1_scalar_t ge = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
1029     /* actual points */
1030     secp256k1_gej_t x = a;
1031     secp256k1_gej_t x2;
1032     int i;
1033
1034     /* the point being computed */
1035     x = a;
1036     for (i = 0; i < 200*count; i++) {
1037         /* in each iteration, compute X = xn*X + gn*G; */
1038         secp256k1_ecmult(&x, &x, &xn, &gn);
1039         /* also compute ae and ge: the actual accumulated factors for A and G */
1040         /* if X was (ae*A+ge*G), xn*X + gn*G results in (xn*ae*A + (xn*ge+gn)*G) */
1041         secp256k1_scalar_mul(&ae, &ae, &xn);
1042         secp256k1_scalar_mul(&ge, &ge, &xn);
1043         secp256k1_scalar_add(&ge, &ge, &gn);
1044         /* modify xn and gn */
1045         secp256k1_scalar_mul(&xn, &xn, &xf);
1046         secp256k1_scalar_mul(&gn, &gn, &gf);
1047
1048         /* verify */
1049         if (i == 19999) {
1050             /* expected result after 19999 iterations */
1051             secp256k1_gej_t rp = SECP256K1_GEJ_CONST(
1052                 0xD6E96687, 0xF9B10D09, 0x2A6F3543, 0x9D86CEBE,
1053                 0xA4535D0D, 0x409F5358, 0x6440BD74, 0xB933E830,
1054                 0xB95CBCA2, 0xC77DA786, 0x539BE8FD, 0x53354D2D,
1055                 0x3B4F566A, 0xE6580454, 0x07ED6015, 0xEE1B2A88
1056             );
1057
1058             secp256k1_gej_neg(&rp, &rp);
1059             secp256k1_gej_add_var(&rp, &rp, &x);
1060             CHECK(secp256k1_gej_is_infinity(&rp));
1061         }
1062     }
1063     /* redo the computation, but directly with the resulting ae and ge coefficients: */
1064     secp256k1_ecmult(&x2, &a, &ae, &ge);
1065     secp256k1_gej_neg(&x2, &x2);
1066     secp256k1_gej_add_var(&x2, &x2, &x);
1067     CHECK(secp256k1_gej_is_infinity(&x2));
1068 }
1069
1070 void test_point_times_order(const secp256k1_gej_t *point) {
1071     /* X * (point + G) + (order-X) * (pointer + G) = 0 */
1072     secp256k1_scalar_t x;
1073     secp256k1_scalar_t nx;
1074     secp256k1_gej_t res1, res2;
1075     secp256k1_ge_t res3;
1076     unsigned char pub[65];
1077     int psize = 65;
1078     random_scalar_order_test(&x);
1079     secp256k1_scalar_negate(&nx, &x);
1080     secp256k1_ecmult(&res1, point, &x, &x); /* calc res1 = x * point + x * G; */
1081     secp256k1_ecmult(&res2, point, &nx, &nx); /* calc res2 = (order - x) * point + (order - x) * G; */
1082     secp256k1_gej_add_var(&res1, &res1, &res2);
1083     CHECK(secp256k1_gej_is_infinity(&res1));
1084     CHECK(secp256k1_gej_is_valid_var(&res1) == 0);
1085     secp256k1_ge_set_gej(&res3, &res1);
1086     CHECK(secp256k1_ge_is_infinity(&res3));
1087     CHECK(secp256k1_ge_is_valid_var(&res3) == 0);
1088     CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 0) == 0);
1089     psize = 65;
1090     CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 1) == 0);
1091 }
1092
1093 void run_point_times_order(void) {
1094     int i;
1095     secp256k1_fe_t x = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 2);
1096     static const secp256k1_fe_t xr = SECP256K1_FE_CONST(
1097         0x7603CB59, 0xB0EF6C63, 0xFE608479, 0x2A0C378C,
1098         0xDB3233A8, 0x0F8A9A09, 0xA877DEAD, 0x31B38C45
1099     );
1100     for (i = 0; i < 500; i++) {
1101         secp256k1_ge_t p;
1102         if (secp256k1_ge_set_xo_var(&p, &x, 1)) {
1103             secp256k1_gej_t j;
1104             CHECK(secp256k1_ge_is_valid_var(&p));
1105             secp256k1_gej_set_ge(&j, &p);
1106             CHECK(secp256k1_gej_is_valid_var(&j));
1107             test_point_times_order(&j);
1108         }
1109         secp256k1_fe_sqr(&x, &x);
1110     }
1111     secp256k1_fe_normalize_var(&x);
1112     CHECK(secp256k1_fe_equal_var(&x, &xr));
1113 }
1114
1115 void test_wnaf(const secp256k1_scalar_t *number, int w) {
1116     secp256k1_scalar_t x, two, t;
1117     int wnaf[256];
1118     int zeroes = -1;
1119     int i;
1120     int bits;
1121     secp256k1_scalar_set_int(&x, 0);
1122     secp256k1_scalar_set_int(&two, 2);
1123     bits = secp256k1_ecmult_wnaf(wnaf, number, w);
1124     CHECK(bits <= 256);
1125     for (i = bits-1; i >= 0; i--) {
1126         int v = wnaf[i];
1127         secp256k1_scalar_mul(&x, &x, &two);
1128         if (v) {
1129             CHECK(zeroes == -1 || zeroes >= w-1); /* check that distance between non-zero elements is at least w-1 */
1130             zeroes=0;
1131             CHECK((v & 1) == 1); /* check non-zero elements are odd */
1132             CHECK(v <= (1 << (w-1)) - 1); /* check range below */
1133             CHECK(v >= -(1 << (w-1)) - 1); /* check range above */
1134         } else {
1135             CHECK(zeroes != -1); /* check that no unnecessary zero padding exists */
1136             zeroes++;
1137         }
1138         if (v >= 0) {
1139             secp256k1_scalar_set_int(&t, v);
1140         } else {
1141             secp256k1_scalar_set_int(&t, -v);
1142             secp256k1_scalar_negate(&t, &t);
1143         }
1144         secp256k1_scalar_add(&x, &x, &t);
1145     }
1146     CHECK(secp256k1_scalar_eq(&x, number)); /* check that wnaf represents number */
1147 }
1148
1149 void run_wnaf(void) {
1150     int i;
1151     secp256k1_scalar_t n;
1152     for (i = 0; i < count; i++) {
1153         random_scalar_order(&n);
1154         test_wnaf(&n, 4+(i%10));
1155     }
1156 }
1157
1158 void random_sign(secp256k1_ecdsa_sig_t *sig, const secp256k1_scalar_t *key, const secp256k1_scalar_t *msg, int *recid) {
1159     secp256k1_scalar_t nonce;
1160     do {
1161         random_scalar_order_test(&nonce);
1162     } while(!secp256k1_ecdsa_sig_sign(sig, key, msg, &nonce, recid));
1163 }
1164
1165 void test_ecdsa_sign_verify(void) {
1166     secp256k1_gej_t pubj;
1167     secp256k1_ge_t pub;
1168     secp256k1_scalar_t one;
1169     secp256k1_scalar_t msg, key;
1170     secp256k1_ecdsa_sig_t sig;
1171     int recid;
1172     int getrec;
1173     random_scalar_order_test(&msg);
1174     random_scalar_order_test(&key);
1175     secp256k1_ecmult_gen(&pubj, &key);
1176     secp256k1_ge_set_gej(&pub, &pubj);
1177     getrec = secp256k1_rand32()&1;
1178     random_sign(&sig, &key, &msg, getrec?&recid:NULL);
1179     if (getrec) {
1180         CHECK(recid >= 0 && recid < 4);
1181     }
1182     CHECK(secp256k1_ecdsa_sig_verify(&sig, &pub, &msg));
1183     secp256k1_scalar_set_int(&one, 1);
1184     secp256k1_scalar_add(&msg, &msg, &one);
1185     CHECK(!secp256k1_ecdsa_sig_verify(&sig, &pub, &msg));
1186 }
1187
1188 void run_ecdsa_sign_verify(void) {
1189     int i;
1190     for (i = 0; i < 10*count; i++) {
1191         test_ecdsa_sign_verify();
1192     }
1193 }
1194
1195 /** Dummy nonce generation function that just uses a precomputed nonce, and fails if it is not accepted. Use only for testing. */
1196 static int precomputed_nonce_function(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, unsigned int counter, const void *data) {
1197     (void)msg32;
1198     (void)key32;
1199     memcpy(nonce32, data, 32);
1200     return (counter == 0);
1201 }
1202
1203 static int nonce_function_test_fail(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, unsigned int counter, const void *data) {
1204    /* Dummy nonce generator that has a fatal error on the first counter value. */
1205    if (counter == 0) {
1206        return 0;
1207    }
1208    return nonce_function_rfc6979(nonce32, msg32, key32, counter - 1, data);
1209 }
1210
1211 static int nonce_function_test_retry(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, unsigned int counter, const void *data) {
1212    /* Dummy nonce generator that produces unacceptable nonces for the first several counter values. */
1213    if (counter < 3) {
1214        memset(nonce32, counter==0 ? 0 : 255, 32);
1215        if (counter == 2) {
1216            nonce32[31]--;
1217        }
1218        return 1;
1219    }
1220    if (counter < 5) {
1221        static const unsigned char order[] = {
1222            0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
1223            0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
1224            0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
1225            0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x41
1226        };
1227        memcpy(nonce32, order, 32);
1228        if (counter == 4) {
1229            nonce32[31]++;
1230        }
1231        return 1;
1232    }
1233    /* Retry rate of 6979 is negligible esp. as we only call this in determinstic tests. */
1234    /* If someone does fine a case where it retries for secp256k1, we'd like to know. */
1235    if (counter > 5) {
1236        return 0;
1237    }
1238    return nonce_function_rfc6979(nonce32, msg32, key32, counter - 5, data);
1239 }
1240
1241 int is_empty_compact_signature(const unsigned char *sig64) {
1242     static const unsigned char res[64] = {0};
1243     return memcmp(sig64, res, 64) == 0;
1244 }
1245
1246 void test_ecdsa_end_to_end(void) {
1247     unsigned char extra[32] = {0x00};
1248     unsigned char privkey[32];
1249     unsigned char message[32];
1250     unsigned char privkey2[32];
1251     unsigned char csignature[64];
1252     unsigned char signature[72];
1253     unsigned char signature2[72];
1254     unsigned char signature3[72];
1255     unsigned char signature4[72];
1256     unsigned char pubkey[65];
1257     unsigned char recpubkey[65];
1258     unsigned char seckey[300];
1259     int signaturelen = 72;
1260     int signaturelen2 = 72;
1261     int signaturelen3 = 72;
1262     int signaturelen4 = 72;
1263     int recid = 0;
1264     int recpubkeylen = 0;
1265     int pubkeylen = 65;
1266     int seckeylen = 300;
1267
1268     /* Generate a random key and message. */
1269     {
1270         secp256k1_scalar_t msg, key;
1271         random_scalar_order_test(&msg);
1272         random_scalar_order_test(&key);
1273         secp256k1_scalar_get_b32(privkey, &key);
1274         secp256k1_scalar_get_b32(message, &msg);
1275     }
1276
1277     /* Construct and verify corresponding public key. */
1278     CHECK(secp256k1_ec_seckey_verify(privkey) == 1);
1279     CHECK(secp256k1_ec_pubkey_create(pubkey, &pubkeylen, privkey, (secp256k1_rand32() & 3) != 0) == 1);
1280     if (secp256k1_rand32() & 1) {
1281         CHECK(secp256k1_ec_pubkey_decompress(pubkey, &pubkeylen));
1282     }
1283     CHECK(secp256k1_ec_pubkey_verify(pubkey, pubkeylen));
1284
1285     /* Verify private key import and export. */
1286     CHECK(secp256k1_ec_privkey_export(privkey, seckey, &seckeylen, secp256k1_rand32() % 2) == 1);
1287     CHECK(secp256k1_ec_privkey_import(privkey2, seckey, seckeylen) == 1);
1288     CHECK(memcmp(privkey, privkey2, 32) == 0);
1289
1290     /* Optionally tweak the keys using addition. */
1291     if (secp256k1_rand32() % 3 == 0) {
1292         int ret1;
1293         int ret2;
1294         unsigned char rnd[32];
1295         unsigned char pubkey2[65];
1296         int pubkeylen2 = 65;
1297         secp256k1_rand256_test(rnd);
1298         ret1 = secp256k1_ec_privkey_tweak_add(privkey, rnd);
1299         ret2 = secp256k1_ec_pubkey_tweak_add(pubkey, pubkeylen, rnd);
1300         CHECK(ret1 == ret2);
1301         if (ret1 == 0) {
1302             return;
1303         }
1304         CHECK(secp256k1_ec_pubkey_create(pubkey2, &pubkeylen2, privkey, pubkeylen == 33) == 1);
1305         CHECK(memcmp(pubkey, pubkey2, pubkeylen) == 0);
1306     }
1307
1308     /* Optionally tweak the keys using multiplication. */
1309     if (secp256k1_rand32() % 3 == 0) {
1310         int ret1;
1311         int ret2;
1312         unsigned char rnd[32];
1313         unsigned char pubkey2[65];
1314         int pubkeylen2 = 65;
1315         secp256k1_rand256_test(rnd);
1316         ret1 = secp256k1_ec_privkey_tweak_mul(privkey, rnd);
1317         ret2 = secp256k1_ec_pubkey_tweak_mul(pubkey, pubkeylen, rnd);
1318         CHECK(ret1 == ret2);
1319         if (ret1 == 0) {
1320             return;
1321         }
1322         CHECK(secp256k1_ec_pubkey_create(pubkey2, &pubkeylen2, privkey, pubkeylen == 33) == 1);
1323         CHECK(memcmp(pubkey, pubkey2, pubkeylen) == 0);
1324     }
1325
1326     /* Sign. */
1327     CHECK(secp256k1_ecdsa_sign(message, signature, &signaturelen, privkey, NULL, NULL) == 1);
1328     CHECK(signaturelen > 0);
1329     CHECK(secp256k1_ecdsa_sign(message, signature2, &signaturelen2, privkey, NULL, extra) == 1);
1330     CHECK(signaturelen2 > 0);
1331     extra[31] = 1;
1332     CHECK(secp256k1_ecdsa_sign(message, signature3, &signaturelen3, privkey, NULL, extra) == 1);
1333     CHECK(signaturelen3 > 0);
1334     extra[31] = 0;
1335     extra[0] = 1;
1336     CHECK(secp256k1_ecdsa_sign(message, signature4, &signaturelen4, privkey, NULL, extra) == 1);
1337     CHECK(signaturelen3 > 0);
1338     CHECK((signaturelen != signaturelen2) || (memcmp(signature, signature2, signaturelen) != 0));
1339     CHECK((signaturelen != signaturelen3) || (memcmp(signature, signature3, signaturelen) != 0));
1340     CHECK((signaturelen3 != signaturelen2) || (memcmp(signature3, signature2, signaturelen3) != 0));
1341     CHECK((signaturelen4 != signaturelen3) || (memcmp(signature4, signature3, signaturelen4) != 0));
1342     CHECK((signaturelen4 != signaturelen2) || (memcmp(signature4, signature2, signaturelen4) != 0));
1343     CHECK((signaturelen4 != signaturelen) || (memcmp(signature4, signature, signaturelen4) != 0));
1344     /* Verify. */
1345     CHECK(secp256k1_ecdsa_verify(message, signature, signaturelen, pubkey, pubkeylen) == 1);
1346     CHECK(secp256k1_ecdsa_verify(message, signature2, signaturelen2, pubkey, pubkeylen) == 1);
1347     CHECK(secp256k1_ecdsa_verify(message, signature3, signaturelen3, pubkey, pubkeylen) == 1);
1348     CHECK(secp256k1_ecdsa_verify(message, signature4, signaturelen4, pubkey, pubkeylen) == 1);
1349     /* Destroy signature and verify again. */
1350     signature[signaturelen - 1 - secp256k1_rand32() % 20] += 1 + (secp256k1_rand32() % 255);
1351     CHECK(secp256k1_ecdsa_verify(message, signature, signaturelen, pubkey, pubkeylen) != 1);
1352
1353     /* Compact sign. */
1354     CHECK(secp256k1_ecdsa_sign_compact(message, csignature, privkey, NULL, NULL, &recid) == 1);
1355     CHECK(!is_empty_compact_signature(csignature));
1356     /* Recover. */
1357     CHECK(secp256k1_ecdsa_recover_compact(message, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) == 1);
1358     CHECK(recpubkeylen == pubkeylen);
1359     CHECK(memcmp(pubkey, recpubkey, pubkeylen) == 0);
1360     /* Destroy signature and verify again. */
1361     csignature[secp256k1_rand32() % 64] += 1 + (secp256k1_rand32() % 255);
1362     CHECK(secp256k1_ecdsa_recover_compact(message, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) != 1 ||
1363           memcmp(pubkey, recpubkey, pubkeylen) != 0);
1364     CHECK(recpubkeylen == pubkeylen);
1365
1366 }
1367
1368 void test_random_pubkeys(void) {
1369     secp256k1_ge_t elem;
1370     secp256k1_ge_t elem2;
1371     unsigned char in[65];
1372     /* Generate some randomly sized pubkeys. */
1373     uint32_t r = secp256k1_rand32();
1374     int len = (r & 3) == 0 ? 65 : 33;
1375     r>>=2;
1376     if ((r & 3) == 0) {
1377         len = (r & 252) >> 3;
1378     }
1379     r>>=8;
1380     if (len == 65) {
1381       in[0] = (r & 2) ? 4 : (r & 1? 6 : 7);
1382     } else {
1383       in[0] = (r & 1) ? 2 : 3;
1384     }
1385     r>>=2;
1386     if ((r & 7) == 0) {
1387         in[0] = (r & 2040) >> 3;
1388     }
1389     r>>=11;
1390     if (len > 1) {
1391         secp256k1_rand256(&in[1]);
1392     }
1393     if (len > 33) {
1394         secp256k1_rand256(&in[33]);
1395     }
1396     if (secp256k1_eckey_pubkey_parse(&elem, in, len)) {
1397         unsigned char out[65];
1398         unsigned char firstb;
1399         int res;
1400         int size = len;
1401         firstb = in[0];
1402         /* If the pubkey can be parsed, it should round-trip... */
1403         CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, len == 33));
1404         CHECK(size == len);
1405         CHECK(memcmp(&in[1], &out[1], len-1) == 0);
1406         /* ... except for the type of hybrid inputs. */
1407         if ((in[0] != 6) && (in[0] != 7)) {
1408             CHECK(in[0] == out[0]);
1409         }
1410         size = 65;
1411         CHECK(secp256k1_eckey_pubkey_serialize(&elem, in, &size, 0));
1412         CHECK(size == 65);
1413         CHECK(secp256k1_eckey_pubkey_parse(&elem2, in, size));
1414         ge_equals_ge(&elem,&elem2);
1415         /* Check that the X9.62 hybrid type is checked. */
1416         in[0] = (r & 1) ? 6 : 7;
1417         res = secp256k1_eckey_pubkey_parse(&elem2, in, size);
1418         if (firstb == 2 || firstb == 3) {
1419             if (in[0] == firstb + 4) {
1420               CHECK(res);
1421             } else {
1422               CHECK(!res);
1423             }
1424         }
1425         if (res) {
1426             ge_equals_ge(&elem,&elem2);
1427             CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, 0));
1428             CHECK(memcmp(&in[1], &out[1], 64) == 0);
1429         }
1430     }
1431 }
1432
1433 void run_random_pubkeys(void) {
1434     int i;
1435     for (i = 0; i < 10*count; i++) {
1436         test_random_pubkeys();
1437     }
1438 }
1439
1440 void run_ecdsa_end_to_end(void) {
1441     int i;
1442     for (i = 0; i < 64*count; i++) {
1443         test_ecdsa_end_to_end();
1444     }
1445 }
1446
1447 /* Tests several edge cases. */
1448 void test_ecdsa_edge_cases(void) {
1449     const unsigned char msg32[32] = {
1450         'T', 'h', 'i', 's', ' ', 'i', 's', ' ',
1451         'a', ' ', 'v', 'e', 'r', 'y', ' ', 's',
1452         'e', 'c', 'r', 'e', 't', ' ', 'm', 'e',
1453         's', 's', 'a', 'g', 'e', '.', '.', '.'
1454     };
1455     const unsigned char sig64[64] = {
1456         /* Generated by signing the above message with nonce 'This is the nonce we will use...'
1457          * and secret key 0 (which is not valid), resulting in recid 0. */
1458         0x67, 0xCB, 0x28, 0x5F, 0x9C, 0xD1, 0x94, 0xE8,
1459         0x40, 0xD6, 0x29, 0x39, 0x7A, 0xF5, 0x56, 0x96,
1460         0x62, 0xFD, 0xE4, 0x46, 0x49, 0x99, 0x59, 0x63,
1461         0x17, 0x9A, 0x7D, 0xD1, 0x7B, 0xD2, 0x35, 0x32,
1462         0x4B, 0x1B, 0x7D, 0xF3, 0x4C, 0xE1, 0xF6, 0x8E,
1463         0x69, 0x4F, 0xF6, 0xF1, 0x1A, 0xC7, 0x51, 0xDD,
1464         0x7D, 0xD7, 0x3E, 0x38, 0x7E, 0xE4, 0xFC, 0x86,
1465         0x6E, 0x1B, 0xE8, 0xEC, 0xC7, 0xDD, 0x95, 0x57
1466     };
1467     unsigned char pubkey[65];
1468     int t;
1469     int pubkeylen = 65;
1470     /* signature (r,s) = (4,4), which can be recovered with all 4 recids. */
1471     const unsigned char sigb64[64] = {
1472         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1473         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1474         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1475         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
1476         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1477         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1478         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1479         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
1480     };
1481     unsigned char pubkeyb[33];
1482     int pubkeyblen = 33;
1483     int recid;
1484
1485     CHECK(!secp256k1_ecdsa_recover_compact(msg32, sig64, pubkey, &pubkeylen, 0, 0));
1486     CHECK(secp256k1_ecdsa_recover_compact(msg32, sig64, pubkey, &pubkeylen, 0, 1));
1487     CHECK(!secp256k1_ecdsa_recover_compact(msg32, sig64, pubkey, &pubkeylen, 0, 2));
1488     CHECK(!secp256k1_ecdsa_recover_compact(msg32, sig64, pubkey, &pubkeylen, 0, 3));
1489
1490     for (recid = 0; recid < 4; recid++) {
1491         int i;
1492         int recid2;
1493         /* (4,4) encoded in DER. */
1494         unsigned char sigbder[8] = {0x30, 0x06, 0x02, 0x01, 0x04, 0x02, 0x01, 0x04};
1495         unsigned char sigcder_zr[7] = {0x30, 0x05, 0x02, 0x00, 0x02, 0x01, 0x01};
1496         unsigned char sigcder_zs[7] = {0x30, 0x05, 0x02, 0x01, 0x01, 0x02, 0x00};
1497         unsigned char sigbderalt1[39] = {
1498             0x30, 0x25, 0x02, 0x20, 0x00, 0x00, 0x00, 0x00,
1499             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1500             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1501             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1502             0x00, 0x00, 0x00, 0x04, 0x02, 0x01, 0x04,
1503         };
1504         unsigned char sigbderalt2[39] = {
1505             0x30, 0x25, 0x02, 0x01, 0x04, 0x02, 0x20, 0x00,
1506             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1507             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1508             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1509             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
1510         };
1511         unsigned char sigbderalt3[40] = {
1512             0x30, 0x26, 0x02, 0x21, 0x00, 0x00, 0x00, 0x00,
1513             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1514             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1515             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1516             0x00, 0x00, 0x00, 0x00, 0x04, 0x02, 0x01, 0x04,
1517         };
1518         unsigned char sigbderalt4[40] = {
1519             0x30, 0x26, 0x02, 0x01, 0x04, 0x02, 0x21, 0x00,
1520             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1521             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1522             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1523             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
1524         };
1525         /* (order + r,4) encoded in DER. */
1526         unsigned char sigbderlong[40] = {
1527             0x30, 0x26, 0x02, 0x21, 0x00, 0xFF, 0xFF, 0xFF,
1528             0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
1529             0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xBA, 0xAE, 0xDC,
1530             0xE6, 0xAF, 0x48, 0xA0, 0x3B, 0xBF, 0xD2, 0x5E,
1531             0x8C, 0xD0, 0x36, 0x41, 0x45, 0x02, 0x01, 0x04
1532         };
1533         CHECK(secp256k1_ecdsa_recover_compact(msg32, sigb64, pubkeyb, &pubkeyblen, 1, recid));
1534         CHECK(secp256k1_ecdsa_verify(msg32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) == 1);
1535         for (recid2 = 0; recid2 < 4; recid2++) {
1536             unsigned char pubkey2b[33];
1537             int pubkey2blen = 33;
1538             CHECK(secp256k1_ecdsa_recover_compact(msg32, sigb64, pubkey2b, &pubkey2blen, 1, recid2));
1539             /* Verifying with (order + r,4) should always fail. */
1540             CHECK(secp256k1_ecdsa_verify(msg32, sigbderlong, sizeof(sigbderlong), pubkey2b, pubkey2blen) != 1);
1541         }
1542         /* DER parsing tests. */
1543         /* Zero length r/s. */
1544         CHECK(secp256k1_ecdsa_verify(msg32, sigcder_zr, sizeof(sigcder_zr), pubkeyb, pubkeyblen) == -2);
1545         CHECK(secp256k1_ecdsa_verify(msg32, sigcder_zs, sizeof(sigcder_zs), pubkeyb, pubkeyblen) == -2);
1546         /* Leading zeros. */
1547         CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt1, sizeof(sigbderalt1), pubkeyb, pubkeyblen) == 1);
1548         CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt2, sizeof(sigbderalt2), pubkeyb, pubkeyblen) == 1);
1549         CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt3, sizeof(sigbderalt3), pubkeyb, pubkeyblen) == 1);
1550         CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt4, sizeof(sigbderalt4), pubkeyb, pubkeyblen) == 1);
1551         sigbderalt3[4] = 1;
1552         CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt3, sizeof(sigbderalt3), pubkeyb, pubkeyblen) == -2);
1553         sigbderalt4[7] = 1;
1554         CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt4, sizeof(sigbderalt4), pubkeyb, pubkeyblen) == -2);
1555         /* Damage signature. */
1556         sigbder[7]++;
1557         CHECK(secp256k1_ecdsa_verify(msg32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) == 0);
1558         sigbder[7]--;
1559         CHECK(secp256k1_ecdsa_verify(msg32, sigbder, 6, pubkeyb, pubkeyblen) == -2);
1560         CHECK(secp256k1_ecdsa_verify(msg32, sigbder, sizeof(sigbder)-1, pubkeyb, pubkeyblen) == -2);
1561         for(i = 0; i < 8; i++) {
1562             int c;
1563             unsigned char orig = sigbder[i];
1564             /*Try every single-byte change.*/
1565             for (c = 0; c < 256; c++) {
1566                 if (c == orig ) {
1567                     continue;
1568                 }
1569                 sigbder[i] = c;
1570                 CHECK(secp256k1_ecdsa_verify(msg32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) ==
1571                   (i==4 || i==7) ? 0 : -2 );
1572             }
1573             sigbder[i] = orig;
1574         }
1575     }
1576
1577     /* Test the case where ECDSA recomputes a point that is infinity. */
1578     {
1579         secp256k1_gej_t keyj;
1580         secp256k1_ge_t key;
1581         secp256k1_scalar_t msg;
1582         secp256k1_ecdsa_sig_t sig;
1583         secp256k1_scalar_set_int(&sig.s, 1);
1584         secp256k1_scalar_negate(&sig.s, &sig.s);
1585         secp256k1_scalar_inverse(&sig.s, &sig.s);
1586         secp256k1_scalar_set_int(&sig.r, 1);
1587         secp256k1_ecmult_gen(&keyj, &sig.r);
1588         secp256k1_ge_set_gej(&key, &keyj);
1589         msg = sig.s;
1590         CHECK(secp256k1_ecdsa_sig_verify(&sig, &key, &msg) == 0);
1591     }
1592
1593     /* Test r/s equal to zero */
1594     {
1595         /* (1,1) encoded in DER. */
1596         unsigned char sigcder[8] = {0x30, 0x06, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01};
1597         unsigned char sigc64[64] = {
1598             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1599             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1600             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1601             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
1602             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1603             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1604             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1605             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
1606         };
1607         unsigned char pubkeyc[65];
1608         int pubkeyclen = 65;
1609         CHECK(secp256k1_ecdsa_recover_compact(msg32, sigc64, pubkeyc, &pubkeyclen, 0, 0) == 1);
1610         CHECK(secp256k1_ecdsa_verify(msg32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 1);
1611         sigcder[4] = 0;
1612         sigc64[31] = 0;
1613         CHECK(secp256k1_ecdsa_recover_compact(msg32, sigc64, pubkeyb, &pubkeyblen, 1, 0) == 0);
1614         CHECK(secp256k1_ecdsa_verify(msg32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 0);
1615         sigcder[4] = 1;
1616         sigcder[7] = 0;
1617         sigc64[31] = 1;
1618         sigc64[63] = 0;
1619         CHECK(secp256k1_ecdsa_recover_compact(msg32, sigc64, pubkeyb, &pubkeyblen, 1, 0) == 0);
1620         CHECK(secp256k1_ecdsa_verify(msg32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 0);
1621     }
1622
1623     /*Signature where s would be zero.*/
1624     {
1625         const unsigned char nonce[32] = {
1626             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1627             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1628             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1629             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
1630         };
1631         static const unsigned char nonce2[32] = {
1632             0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
1633             0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
1634             0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
1635             0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x40
1636         };
1637         const unsigned char key[32] = {
1638             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1639             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1640             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1641             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
1642         };
1643         unsigned char msg[32] = {
1644             0x86, 0x41, 0x99, 0x81, 0x06, 0x23, 0x44, 0x53,
1645             0xaa, 0x5f, 0x9d, 0x6a, 0x31, 0x78, 0xf4, 0xf7,
1646             0xb8, 0x12, 0xe0, 0x0b, 0x81, 0x7a, 0x77, 0x62,
1647             0x65, 0xdf, 0xdd, 0x31, 0xb9, 0x3e, 0x29, 0xa9,
1648         };
1649         unsigned char sig[72];
1650         int siglen = 72;
1651         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce) == 0);
1652         CHECK(siglen == 0);
1653         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce2) == 0);
1654         CHECK(siglen == 0);
1655         msg[31] = 0xaa;
1656         siglen = 72;
1657         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce) == 1);
1658         CHECK(siglen > 0);
1659         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce2) == 1);
1660         CHECK(siglen > 0);
1661         siglen = 10;
1662         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce) != 1);
1663         CHECK(siglen == 0);
1664     }
1665
1666     /* Nonce function corner cases. */
1667     for (t = 0; t < 2; t++) {
1668         static const unsigned char zero[32] = {0x00};
1669         int i;
1670         unsigned char key[32];
1671         unsigned char msg[32];
1672         unsigned char sig[72];
1673         unsigned char sig2[72];
1674         secp256k1_ecdsa_sig_t s[512];
1675         int siglen = 72;
1676         int siglen2 = 72;
1677         int recid2;
1678         const unsigned char *extra;
1679         extra = t == 0 ? NULL : zero;
1680         memset(msg, 0, 32);
1681         msg[31] = 1;
1682         /* High key results in signature failure. */
1683         memset(key, 0xFF, 32);
1684         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, NULL, extra) == 0);
1685         CHECK(siglen == 0);
1686         /* Zero key results in signature failure. */
1687         memset(key, 0, 32);
1688         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, NULL, extra) == 0);
1689         CHECK(siglen == 0);
1690         /* Nonce function failure results in signature failure. */
1691         key[31] = 1;
1692         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, nonce_function_test_fail, extra) == 0);
1693         CHECK(siglen == 0);
1694         CHECK(secp256k1_ecdsa_sign_compact(msg, sig, key, nonce_function_test_fail, extra, &recid) == 0);
1695         CHECK(is_empty_compact_signature(sig));
1696         /* The retry loop successfully makes its way to the first good value. */
1697         siglen = 72;
1698         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, nonce_function_test_retry, extra) == 1);
1699         CHECK(siglen > 0);
1700         CHECK(secp256k1_ecdsa_sign(msg, sig2, &siglen2, key, nonce_function_rfc6979, extra) == 1);
1701         CHECK(siglen > 0);
1702         CHECK((siglen == siglen2) && (memcmp(sig, sig2, siglen) == 0));
1703         CHECK(secp256k1_ecdsa_sign_compact(msg, sig, key, nonce_function_test_retry, extra, &recid) == 1);
1704         CHECK(!is_empty_compact_signature(sig));
1705         CHECK(secp256k1_ecdsa_sign_compact(msg, sig2, key, nonce_function_rfc6979, extra, &recid2) == 1);
1706         CHECK(!is_empty_compact_signature(sig2));
1707         CHECK((recid == recid2) && (memcmp(sig, sig2, 64) == 0));
1708         /* The default nonce function is determinstic. */
1709         siglen = 72;
1710         siglen2 = 72;
1711         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, NULL, extra) == 1);
1712         CHECK(siglen > 0);
1713         CHECK(secp256k1_ecdsa_sign(msg, sig2, &siglen2, key, NULL, extra) == 1);
1714         CHECK(siglen2 > 0);
1715         CHECK((siglen == siglen2) && (memcmp(sig, sig2, siglen) == 0));
1716         CHECK(secp256k1_ecdsa_sign_compact(msg, sig, key, NULL, extra, &recid) == 1);
1717         CHECK(!is_empty_compact_signature(sig));
1718         CHECK(secp256k1_ecdsa_sign_compact(msg, sig2, key, NULL, extra, &recid2) == 1);
1719         CHECK(!is_empty_compact_signature(sig));
1720         CHECK((recid == recid2) && (memcmp(sig, sig2, 64) == 0));
1721         /* The default nonce function changes output with different messages. */
1722         for(i = 0; i < 256; i++) {
1723             int j;
1724             siglen2 = 72;
1725             msg[0] = i;
1726             CHECK(secp256k1_ecdsa_sign(msg, sig2, &siglen2, key, NULL, extra) == 1);
1727             CHECK(!is_empty_compact_signature(sig));
1728             CHECK(secp256k1_ecdsa_sig_parse(&s[i], sig2, siglen2));
1729             for (j = 0; j < i; j++) {
1730                 CHECK(!secp256k1_scalar_eq(&s[i].r, &s[j].r));
1731             }
1732         }
1733         msg[0] = 0;
1734         msg[31] = 2;
1735         /* The default nonce function changes output with different keys. */
1736         for(i = 256; i < 512; i++) {
1737             int j;
1738             siglen2 = 72;
1739             key[0] = i - 256;
1740             CHECK(secp256k1_ecdsa_sign(msg, sig2, &siglen2, key, NULL, extra) == 1);
1741             CHECK(secp256k1_ecdsa_sig_parse(&s[i], sig2, siglen2));
1742             for (j = 0; j < i; j++) {
1743                 CHECK(!secp256k1_scalar_eq(&s[i].r, &s[j].r));
1744             }
1745         }
1746         key[0] = 0;
1747     }
1748
1749     /* Privkey export where pubkey is the point at infinity. */
1750     {
1751         unsigned char privkey[300];
1752         unsigned char seckey[32] = {
1753             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1754             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
1755             0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
1756             0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41,
1757         };
1758         int outlen = 300;
1759         CHECK(!secp256k1_ec_privkey_export(seckey, privkey, &outlen, 0));
1760         CHECK(!secp256k1_ec_privkey_export(seckey, privkey, &outlen, 1));
1761     }
1762 }
1763
1764 void run_ecdsa_edge_cases(void) {
1765     test_ecdsa_edge_cases();
1766 }
1767
1768 #ifdef ENABLE_OPENSSL_TESTS
1769 EC_KEY *get_openssl_key(const secp256k1_scalar_t *key) {
1770     unsigned char privkey[300];
1771     int privkeylen;
1772     const unsigned char* pbegin = privkey;
1773     int compr = secp256k1_rand32() & 1;
1774     EC_KEY *ec_key = EC_KEY_new_by_curve_name(NID_secp256k1);
1775     CHECK(secp256k1_eckey_privkey_serialize(privkey, &privkeylen, key, compr));
1776     CHECK(d2i_ECPrivateKey(&ec_key, &pbegin, privkeylen));
1777     CHECK(EC_KEY_check_key(ec_key));
1778     return ec_key;
1779 }
1780
1781 void test_ecdsa_openssl(void) {
1782     secp256k1_gej_t qj;
1783     secp256k1_ge_t q;
1784     secp256k1_ecdsa_sig_t sig;
1785     secp256k1_scalar_t one;
1786     secp256k1_scalar_t msg2;
1787     secp256k1_scalar_t key, msg;
1788     EC_KEY *ec_key;
1789     unsigned int sigsize = 80;
1790     int secp_sigsize = 80;
1791     unsigned char message[32];
1792     unsigned char signature[80];
1793     secp256k1_rand256_test(message);
1794     secp256k1_scalar_set_b32(&msg, message, NULL);
1795     random_scalar_order_test(&key);
1796     secp256k1_ecmult_gen(&qj, &key);
1797     secp256k1_ge_set_gej(&q, &qj);
1798     ec_key = get_openssl_key(&key);
1799     CHECK(ec_key);
1800     CHECK(ECDSA_sign(0, message, sizeof(message), signature, &sigsize, ec_key));
1801     CHECK(secp256k1_ecdsa_sig_parse(&sig, signature, sigsize));
1802     CHECK(secp256k1_ecdsa_sig_verify(&sig, &q, &msg));
1803     secp256k1_scalar_set_int(&one, 1);
1804     secp256k1_scalar_add(&msg2, &msg, &one);
1805     CHECK(!secp256k1_ecdsa_sig_verify(&sig, &q, &msg2));
1806
1807     random_sign(&sig, &key, &msg, NULL);
1808     CHECK(secp256k1_ecdsa_sig_serialize(signature, &secp_sigsize, &sig));
1809     CHECK(ECDSA_verify(0, message, sizeof(message), signature, secp_sigsize, ec_key) == 1);
1810
1811     EC_KEY_free(ec_key);
1812 }
1813
1814 void run_ecdsa_openssl(void) {
1815     int i;
1816     for (i = 0; i < 10*count; i++) {
1817         test_ecdsa_openssl();
1818     }
1819 }
1820 #endif
1821
1822 int main(int argc, char **argv) {
1823     unsigned char seed16[16] = {0};
1824     unsigned char run32[32] = {0};
1825     /* find iteration count */
1826     if (argc > 1) {
1827         count = strtol(argv[1], NULL, 0);
1828     }
1829
1830     /* find random seed */
1831     if (argc > 2) {
1832         int pos = 0;
1833         const char* ch = argv[2];
1834         while (pos < 16 && ch[0] != 0 && ch[1] != 0) {
1835             unsigned short sh;
1836             if (sscanf(ch, "%2hx", &sh)) {
1837                 seed16[pos] = sh;
1838             } else {
1839                 break;
1840             }
1841             ch += 2;
1842             pos++;
1843         }
1844     } else {
1845         FILE *frand = fopen("/dev/urandom", "r");
1846         if (!frand || !fread(&seed16, sizeof(seed16), 1, frand)) {
1847             uint64_t t = time(NULL) * (uint64_t)1337;
1848             seed16[0] ^= t;
1849             seed16[1] ^= t >> 8;
1850             seed16[2] ^= t >> 16;
1851             seed16[3] ^= t >> 24;
1852             seed16[4] ^= t >> 32;
1853             seed16[5] ^= t >> 40;
1854             seed16[6] ^= t >> 48;
1855             seed16[7] ^= t >> 56;
1856         }
1857         fclose(frand);
1858     }
1859     secp256k1_rand_seed(seed16);
1860
1861     printf("test count = %i\n", count);
1862     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]);
1863
1864     /* initialize */
1865     secp256k1_start(SECP256K1_START_SIGN | SECP256K1_START_VERIFY);
1866
1867     /* initializing a second time shouldn't cause any harm or memory leaks. */
1868     secp256k1_start(SECP256K1_START_SIGN | SECP256K1_START_VERIFY);
1869
1870     run_sha256_tests();
1871     run_hmac_sha256_tests();
1872     run_rfc6979_hmac_sha256_tests();
1873
1874 #ifndef USE_NUM_NONE
1875     /* num tests */
1876     run_num_smalltests();
1877 #endif
1878
1879     /* scalar tests */
1880     run_scalar_tests();
1881
1882     /* field tests */
1883     run_field_inv();
1884     run_field_inv_var();
1885     run_field_inv_all_var();
1886     run_field_misc();
1887     run_field_convert();
1888     run_sqr();
1889     run_sqrt();
1890
1891     /* group tests */
1892     run_ge();
1893
1894     /* ecmult tests */
1895     run_wnaf();
1896     run_point_times_order();
1897     run_ecmult_chain();
1898
1899     /* ecdsa tests */
1900     run_random_pubkeys();
1901     run_ecdsa_sign_verify();
1902     run_ecdsa_end_to_end();
1903     run_ecdsa_edge_cases();
1904 #ifdef ENABLE_OPENSSL_TESTS
1905     run_ecdsa_openssl();
1906 #endif
1907
1908     secp256k1_rand256(run32);
1909     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]);
1910
1911     /* shutdown */
1912     secp256k1_stop();
1913
1914     /* shutting down twice shouldn't cause any double frees. */
1915     secp256k1_stop();
1916     return 0;
1917 }