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_normalize(fe);
  40     int n = secp256k1_rand32() % 4;
  41     for (int i = 0; i < n; i++) {
  42         secp256k1_fe_negate(fe, fe, 1 + 2*i);
  43         secp256k1_fe_negate(fe, fe, 2 + 2*i);
  44     }
  45 }
  46
  47 void random_group_element_test(secp256k1_ge_t *ge) {
  48     secp256k1_fe_t fe;
  49     do {
  50         random_field_element_test(&fe);
  51         if (secp256k1_ge_set_xo_var(ge, &fe, secp256k1_rand32() & 1))
  52             break;
  53     } while(1);
  54 }
  55
  56 void random_group_element_jacobian_test(secp256k1_gej_t *gej, const secp256k1_ge_t *ge) {
  57     do {
  58         random_field_element_test(&gej->z);
  59         if (!secp256k1_fe_is_zero(&gej->z)) {
  60             break;
  61         }
  62     } while(1);
  63     secp256k1_fe_t z2; secp256k1_fe_sqr(&z2, &gej->z);
  64     secp256k1_fe_t z3; secp256k1_fe_mul(&z3, &z2, &gej->z);
  65     secp256k1_fe_mul(&gej->x, &ge->x, &z2);
  66     secp256k1_fe_mul(&gej->y, &ge->y, &z3);
  67     gej->infinity = ge->infinity;
  68 }
  69
  70 void random_scalar_order_test(secp256k1_scalar_t *num) {
  71     do {
  72         unsigned char b32[32];
  73         secp256k1_rand256_test(b32);
  74         int overflow = 0;
  75         secp256k1_scalar_set_b32(num, b32, &overflow);
  76         if (overflow || secp256k1_scalar_is_zero(num))
  77             continue;
  78         break;
  79     } while(1);
  80 }
  81
  82 void random_scalar_order(secp256k1_scalar_t *num) {
  83     do {
  84         unsigned char b32[32];
  85         secp256k1_rand256(b32);
  86         int overflow = 0;
  87         secp256k1_scalar_set_b32(num, b32, &overflow);
  88         if (overflow || secp256k1_scalar_is_zero(num))
  89             continue;
  90         break;
  91     } while(1);
  92 }
  93
  94 /***** NUM TESTS *****/
  95
  96 #ifndef USE_NUM_NONE
  97 void random_num_negate(secp256k1_num_t *num) {
  98     if (secp256k1_rand32() & 1)
  99         secp256k1_num_negate(num);
 100 }
 101
 102 void random_num_order_test(secp256k1_num_t *num) {
 103     secp256k1_scalar_t sc;
 104     random_scalar_order_test(&sc);
 105     secp256k1_scalar_get_num(num, &sc);
 106 }
 107
 108 void random_num_order(secp256k1_num_t *num) {
 109     secp256k1_scalar_t sc;
 110     random_scalar_order(&sc);
 111     secp256k1_scalar_get_num(num, &sc);
 112 }
 113
 114 void test_num_negate(void) {
 115     secp256k1_num_t n1;
 116     secp256k1_num_t n2;
 117     random_num_order_test(&n1); /* n1 = R */
 118     random_num_negate(&n1);
 119     secp256k1_num_copy(&n2, &n1); /* n2 = R */
 120     secp256k1_num_sub(&n1, &n2, &n1); /* n1 = n2-n1 = 0 */
 121     CHECK(secp256k1_num_is_zero(&n1));
 122     secp256k1_num_copy(&n1, &n2); /* n1 = R */
 123     secp256k1_num_negate(&n1); /* n1 = -R */
 124     CHECK(!secp256k1_num_is_zero(&n1));
 125     secp256k1_num_add(&n1, &n2, &n1); /* n1 = n2+n1 = 0 */
 126     CHECK(secp256k1_num_is_zero(&n1));
 127     secp256k1_num_copy(&n1, &n2); /* n1 = R */
 128     secp256k1_num_negate(&n1); /* n1 = -R */
 129     CHECK(secp256k1_num_is_neg(&n1) != secp256k1_num_is_neg(&n2));
 130     secp256k1_num_negate(&n1); /* n1 = R */
 131     CHECK(secp256k1_num_eq(&n1, &n2));
 132 }
 133
 134 void test_num_add_sub(void) {
 135     int r = secp256k1_rand32();
 136     secp256k1_num_t n1;
 137     secp256k1_num_t n2;
 138     random_num_order_test(&n1); /* n1 = R1 */
 139     if (r & 1) {
 140         random_num_negate(&n1);
 141     }
 142     random_num_order_test(&n2); /* n2 = R2 */
 143     if (r & 2) {
 144         random_num_negate(&n2);
 145     }
 146     secp256k1_num_t n1p2, n2p1, n1m2, n2m1;
 147     secp256k1_num_add(&n1p2, &n1, &n2); /* n1p2 = R1 + R2 */
 148     secp256k1_num_add(&n2p1, &n2, &n1); /* n2p1 = R2 + R1 */
 149     secp256k1_num_sub(&n1m2, &n1, &n2); /* n1m2 = R1 - R2 */
 150     secp256k1_num_sub(&n2m1, &n2, &n1); /* n2m1 = R2 - R1 */
 151     CHECK(secp256k1_num_eq(&n1p2, &n2p1));
 152     CHECK(!secp256k1_num_eq(&n1p2, &n1m2));
 153     secp256k1_num_negate(&n2m1); /* n2m1 = -R2 + R1 */
 154     CHECK(secp256k1_num_eq(&n2m1, &n1m2));
 155     CHECK(!secp256k1_num_eq(&n2m1, &n1));
 156     secp256k1_num_add(&n2m1, &n2m1, &n2); /* n2m1 = -R2 + R1 + R2 = R1 */
 157     CHECK(secp256k1_num_eq(&n2m1, &n1));
 158     CHECK(!secp256k1_num_eq(&n2p1, &n1));
 159     secp256k1_num_sub(&n2p1, &n2p1, &n2); /* n2p1 = R2 + R1 - R2 = R1 */
 160     CHECK(secp256k1_num_eq(&n2p1, &n1));
 161 }
 162
 163 void run_num_smalltests(void) {
 164     for (int i=0; i<100*count; i++) {
 165         test_num_negate();
 166         test_num_add_sub();
 167     }
 168 }
 169 #endif
 170
 171 /***** SCALAR TESTS *****/
 172
 173 void scalar_test(void) {
 174     unsigned char c[32];
 175
 176     /* Set 's' to a random scalar, with value 'snum'. */
 177     secp256k1_scalar_t s;
 178     random_scalar_order_test(&s);
 179
 180     /* Set 's1' to a random scalar, with value 's1num'. */
 181     secp256k1_scalar_t s1;
 182     random_scalar_order_test(&s1);
 183
 184     /* Set 's2' to a random scalar, with value 'snum2', and byte array representation 'c'. */
 185     secp256k1_scalar_t s2;
 186     random_scalar_order_test(&s2);
 187     secp256k1_scalar_get_b32(c, &s2);
 188
 189 #ifndef USE_NUM_NONE
 190     secp256k1_num_t snum, s1num, s2num;
 191     secp256k1_scalar_get_num(&snum, &s);
 192     secp256k1_scalar_get_num(&s1num, &s1);
 193     secp256k1_scalar_get_num(&s2num, &s2);
 194
 195     secp256k1_num_t order;
 196     secp256k1_scalar_order_get_num(&order);
 197     secp256k1_num_t half_order = order;
 198     secp256k1_num_shift(&half_order, 1);
 199 #endif
 200
 201     {
 202         /* Test that fetching groups of 4 bits from a scalar and recursing n(i)=16*n(i-1)+p(i) reconstructs it. */
 203         secp256k1_scalar_t n;
 204         secp256k1_scalar_set_int(&n, 0);
 205         for (int i = 0; i < 256; i += 4) {
 206             secp256k1_scalar_t t;
 207             secp256k1_scalar_set_int(&t, secp256k1_scalar_get_bits(&s, 256 - 4 - i, 4));
 208             for (int j = 0; j < 4; j++) {
 209                 secp256k1_scalar_add(&n, &n, &n);
 210             }
 211             secp256k1_scalar_add(&n, &n, &t);
 212         }
 213         CHECK(secp256k1_scalar_eq(&n, &s));
 214     }
 215
 216     {
 217         /* Test that fetching groups of randomly-sized bits from a scalar and recursing n(i)=b*n(i-1)+p(i) reconstructs it. */
 218         secp256k1_scalar_t n;
 219         secp256k1_scalar_set_int(&n, 0);
 220         int i = 0;
 221         while (i < 256) {
 222             int now = (secp256k1_rand32() % 15) + 1;
 223             if (now + i > 256) {
 224                 now = 256 - i;
 225             }
 226             secp256k1_scalar_t t;
 227             secp256k1_scalar_set_int(&t, secp256k1_scalar_get_bits_var(&s, 256 - now - i, now));
 228             for (int j = 0; j < now; j++) {
 229                 secp256k1_scalar_add(&n, &n, &n);
 230             }
 231             secp256k1_scalar_add(&n, &n, &t);
 232             i += now;
 233         }
 234         CHECK(secp256k1_scalar_eq(&n, &s));
 235     }
 236
 237 #ifndef USE_NUM_NONE
 238     {
 239         /* Test that adding the scalars together is equal to adding their numbers together modulo the order. */
 240         secp256k1_num_t rnum;
 241         secp256k1_num_add(&rnum, &snum, &s2num);
 242         secp256k1_num_mod(&rnum, &order);
 243         secp256k1_scalar_t r;
 244         secp256k1_scalar_add(&r, &s, &s2);
 245         secp256k1_num_t r2num;
 246         secp256k1_scalar_get_num(&r2num, &r);
 247         CHECK(secp256k1_num_eq(&rnum, &r2num));
 248     }
 249
 250     {
 251         /* Test that multipying the scalars is equal to multiplying their numbers modulo the order. */
 252         secp256k1_num_t rnum;
 253         secp256k1_num_mul(&rnum, &snum, &s2num);
 254         secp256k1_num_mod(&rnum, &order);
 255         secp256k1_scalar_t r;
 256         secp256k1_scalar_mul(&r, &s, &s2);
 257         secp256k1_num_t r2num;
 258         secp256k1_scalar_get_num(&r2num, &r);
 259         CHECK(secp256k1_num_eq(&rnum, &r2num));
 260         /* The result can only be zero if at least one of the factors was zero. */
 261         CHECK(secp256k1_scalar_is_zero(&r) == (secp256k1_scalar_is_zero(&s) || secp256k1_scalar_is_zero(&s2)));
 262         /* The results can only be equal to one of the factors if that factor was zero, or the other factor was one. */
 263         CHECK(secp256k1_num_eq(&rnum, &snum) == (secp256k1_scalar_is_zero(&s) || secp256k1_scalar_is_one(&s2)));
 264         CHECK(secp256k1_num_eq(&rnum, &s2num) == (secp256k1_scalar_is_zero(&s2) || secp256k1_scalar_is_one(&s)));
 265     }
 266
 267     {
 268         /* Check that comparison with zero matches comparison with zero on the number. */
 269         CHECK(secp256k1_num_is_zero(&snum) == secp256k1_scalar_is_zero(&s));
 270         /* Check that comparison with the half order is equal to testing for high scalar. */
 271         CHECK(secp256k1_scalar_is_high(&s) == (secp256k1_num_cmp(&snum, &half_order) > 0));
 272         secp256k1_scalar_t neg;
 273         secp256k1_scalar_negate(&neg, &s);
 274         secp256k1_num_t negnum;
 275         secp256k1_num_sub(&negnum, &order, &snum);
 276         secp256k1_num_mod(&negnum, &order);
 277         /* Check that comparison with the half order is equal to testing for high scalar after negation. */
 278         CHECK(secp256k1_scalar_is_high(&neg) == (secp256k1_num_cmp(&negnum, &half_order) > 0));
 279         /* Negating should change the high property, unless the value was already zero. */
 280         CHECK((secp256k1_scalar_is_high(&s) == secp256k1_scalar_is_high(&neg)) == secp256k1_scalar_is_zero(&s));
 281         secp256k1_num_t negnum2;
 282         secp256k1_scalar_get_num(&negnum2, &neg);
 283         /* Negating a scalar should be equal to (order - n) mod order on the number. */
 284         CHECK(secp256k1_num_eq(&negnum, &negnum2));
 285         secp256k1_scalar_add(&neg, &neg, &s);
 286         /* Adding a number to its negation should result in zero. */
 287         CHECK(secp256k1_scalar_is_zero(&neg));
 288         secp256k1_scalar_negate(&neg, &neg);
 289         /* Negating zero should still result in zero. */
 290         CHECK(secp256k1_scalar_is_zero(&neg));
 291     }
 292
 293     {
 294         /* Test secp256k1_scalar_mul_shift_var. */
 295         secp256k1_scalar_t r;
 296         unsigned int shift = 256 + (secp256k1_rand32() % 257);
 297         secp256k1_scalar_mul_shift_var(&r, &s1, &s2, shift);
 298         secp256k1_num_t rnum;
 299         secp256k1_num_mul(&rnum, &s1num, &s2num);
 300         secp256k1_num_shift(&rnum, shift - 1);
 301         secp256k1_num_t one;
 302         unsigned char cone[1] = {0x01};
 303         secp256k1_num_set_bin(&one, cone, 1);
 304         secp256k1_num_add(&rnum, &rnum, &one);
 305         secp256k1_num_shift(&rnum, 1);
 306         secp256k1_num_t rnum2;
 307         secp256k1_scalar_get_num(&rnum2, &r);
 308         CHECK(secp256k1_num_eq(&rnum, &rnum2));
 309     }
 310 #endif
 311
 312     {
 313         /* Test that scalar inverses are equal to the inverse of their number modulo the order. */
 314         if (!secp256k1_scalar_is_zero(&s)) {
 315             secp256k1_scalar_t inv;
 316             secp256k1_scalar_inverse(&inv, &s);
 317 #ifndef USE_NUM_NONE
 318             secp256k1_num_t invnum;
 319             secp256k1_num_mod_inverse(&invnum, &snum, &order);
 320             secp256k1_num_t invnum2;
 321             secp256k1_scalar_get_num(&invnum2, &inv);
 322             CHECK(secp256k1_num_eq(&invnum, &invnum2));
 323 #endif
 324             secp256k1_scalar_mul(&inv, &inv, &s);
 325             /* Multiplying a scalar with its inverse must result in one. */
 326             CHECK(secp256k1_scalar_is_one(&inv));
 327             secp256k1_scalar_inverse(&inv, &inv);
 328             /* Inverting one must result in one. */
 329             CHECK(secp256k1_scalar_is_one(&inv));
 330         }
 331     }
 332
 333     {
 334         /* Test commutativity of add. */
 335         secp256k1_scalar_t r1, r2;
 336         secp256k1_scalar_add(&r1, &s1, &s2);
 337         secp256k1_scalar_add(&r2, &s2, &s1);
 338         CHECK(secp256k1_scalar_eq(&r1, &r2));
 339     }
 340
 341     {
 342         /* Test add_bit. */
 343         int bit = secp256k1_rand32() % 256;
 344         secp256k1_scalar_t b;
 345         secp256k1_scalar_set_int(&b, 1);
 346         CHECK(secp256k1_scalar_is_one(&b));
 347         for (int i = 0; i < bit; i++) {
 348             secp256k1_scalar_add(&b, &b, &b);
 349         }
 350         secp256k1_scalar_t r1 = s1, r2 = s1;
 351         if (!secp256k1_scalar_add(&r1, &r1, &b)) {
 352             /* No overflow happened. */
 353             secp256k1_scalar_add_bit(&r2, bit);
 354             CHECK(secp256k1_scalar_eq(&r1, &r2));
 355         }
 356     }
 357
 358     {
 359         /* Test commutativity of mul. */
 360         secp256k1_scalar_t r1, r2;
 361         secp256k1_scalar_mul(&r1, &s1, &s2);
 362         secp256k1_scalar_mul(&r2, &s2, &s1);
 363         CHECK(secp256k1_scalar_eq(&r1, &r2));
 364     }
 365
 366     {
 367         /* Test associativity of add. */
 368         secp256k1_scalar_t r1, r2;
 369         secp256k1_scalar_add(&r1, &s1, &s2);
 370         secp256k1_scalar_add(&r1, &r1, &s);
 371         secp256k1_scalar_add(&r2, &s2, &s);
 372         secp256k1_scalar_add(&r2, &s1, &r2);
 373         CHECK(secp256k1_scalar_eq(&r1, &r2));
 374     }
 375
 376     {
 377         /* Test associativity of mul. */
 378         secp256k1_scalar_t r1, r2;
 379         secp256k1_scalar_mul(&r1, &s1, &s2);
 380         secp256k1_scalar_mul(&r1, &r1, &s);
 381         secp256k1_scalar_mul(&r2, &s2, &s);
 382         secp256k1_scalar_mul(&r2, &s1, &r2);
 383         CHECK(secp256k1_scalar_eq(&r1, &r2));
 384     }
 385
 386     {
 387         /* Test distributitivity of mul over add. */
 388         secp256k1_scalar_t r1, r2, t;
 389         secp256k1_scalar_add(&r1, &s1, &s2);
 390         secp256k1_scalar_mul(&r1, &r1, &s);
 391         secp256k1_scalar_mul(&r2, &s1, &s);
 392         secp256k1_scalar_mul(&t, &s2, &s);
 393         secp256k1_scalar_add(&r2, &r2, &t);
 394         CHECK(secp256k1_scalar_eq(&r1, &r2));
 395     }
 396
 397     {
 398         /* Test square. */
 399         secp256k1_scalar_t r1, r2;
 400         secp256k1_scalar_sqr(&r1, &s1);
 401         secp256k1_scalar_mul(&r2, &s1, &s1);
 402         CHECK(secp256k1_scalar_eq(&r1, &r2));
 403     }
 404
 405     {
 406         /* Test multiplicative identity. */
 407         secp256k1_scalar_t r1, v1;
 408         secp256k1_scalar_set_int(&v1,1);
 409         secp256k1_scalar_mul(&r1, &s1, &v1);
 410         CHECK(secp256k1_scalar_eq(&r1, &s1));
 411     }
 412
 413     {
 414         /* Test additive identity. */
 415         secp256k1_scalar_t r1, v0;
 416         secp256k1_scalar_set_int(&v0,0);
 417         secp256k1_scalar_add(&r1, &s1, &v0);
 418         CHECK(secp256k1_scalar_eq(&r1, &s1));
 419     }
 420
 421     {
 422         /* Test zero product property. */
 423         secp256k1_scalar_t r1, v0;
 424         secp256k1_scalar_set_int(&v0,0);
 425         secp256k1_scalar_mul(&r1, &s1, &v0);
 426         CHECK(secp256k1_scalar_eq(&r1, &v0));
 427     }
 428
 429 }
 430
 431 void run_scalar_tests(void) {
 432     for (int i = 0; i < 128 * count; i++) {
 433         scalar_test();
 434     }
 435
 436     {
 437         /* (-1)+1 should be zero. */
 438         secp256k1_scalar_t s, o;
 439         secp256k1_scalar_set_int(&s, 1);
 440         CHECK(secp256k1_scalar_is_one(&s));
 441         secp256k1_scalar_negate(&o, &s);
 442         secp256k1_scalar_add(&o, &o, &s);
 443         CHECK(secp256k1_scalar_is_zero(&o));
 444         secp256k1_scalar_negate(&o, &o);
 445         CHECK(secp256k1_scalar_is_zero(&o));
 446     }
 447
 448 #ifndef USE_NUM_NONE
 449     {
 450         /* A scalar with value of the curve order should be 0. */
 451         secp256k1_num_t order;
 452         secp256k1_scalar_order_get_num(&order);
 453         unsigned char bin[32];
 454         secp256k1_num_get_bin(bin, 32, &order);
 455         secp256k1_scalar_t zero;
 456         int overflow = 0;
 457         secp256k1_scalar_set_b32(&zero, bin, &overflow);
 458         CHECK(overflow == 1);
 459         CHECK(secp256k1_scalar_is_zero(&zero));
 460     }
 461 #endif
 462 }
 463
 464 /***** FIELD TESTS *****/
 465
 466 void random_fe(secp256k1_fe_t *x) {
 467     unsigned char bin[32];
 468     do {
 469         secp256k1_rand256(bin);
 470         if (secp256k1_fe_set_b32(x, bin)) {
 471             return;
 472         }
 473     } while(1);
 474 }
 475
 476 void random_fe_non_zero(secp256k1_fe_t *nz) {
 477     int tries = 10;
 478     while (--tries >= 0) {
 479         random_fe(nz);
 480         secp256k1_fe_normalize(nz);
 481         if (!secp256k1_fe_is_zero(nz))
 482             break;
 483     }
 484     /* Infinitesimal probability of spurious failure here */
 485     CHECK(tries >= 0);
 486 }
 487
 488 void random_fe_non_square(secp256k1_fe_t *ns) {
 489     random_fe_non_zero(ns);
 490     secp256k1_fe_t r;
 491     if (secp256k1_fe_sqrt_var(&r, ns)) {
 492         secp256k1_fe_negate(ns, ns, 1);
 493     }
 494 }
 495
 496 int check_fe_equal(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
 497     secp256k1_fe_t an = *a; secp256k1_fe_normalize(&an);
 498     secp256k1_fe_t bn = *b; secp256k1_fe_normalize_var(&bn);
 499     return secp256k1_fe_equal(&an, &bn);
 500 }
 501
 502 int check_fe_inverse(const secp256k1_fe_t *a, const secp256k1_fe_t *ai) {
 503     secp256k1_fe_t x; secp256k1_fe_mul(&x, a, ai);
 504     secp256k1_fe_t one; secp256k1_fe_set_int(&one, 1);
 505     return check_fe_equal(&x, &one);
 506 }
 507
 508 void run_field_misc(void) {
 509     const unsigned char f32_5[32] = {
 510         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 511         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 512         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 513         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x05,
 514     };
 515     secp256k1_fe_t x;
 516     secp256k1_fe_t y;
 517     secp256k1_fe_t z;
 518     secp256k1_fe_t q;
 519     secp256k1_fe_t fe5;
 520     CHECK(secp256k1_fe_set_b32(&fe5, f32_5));
 521     for (int i=0; i<5*count; i++) {
 522         random_fe(&x);
 523         random_fe_non_zero(&y);
 524         /* Test the fe equality and comparison operations. */
 525         CHECK(secp256k1_fe_cmp_var(&x, &x) == 0);
 526         CHECK(secp256k1_fe_equal(&x, &x));
 527         z = x;
 528         secp256k1_fe_add(&z,&y);
 529         secp256k1_fe_normalize(&z);
 530         /* Test the conditional move. */
 531         secp256k1_fe_cmov(&z, &x, 0);
 532         CHECK(secp256k1_fe_equal(&x, &z) == 0);
 533         CHECK(secp256k1_fe_cmp_var(&x, &z) != 0);
 534         secp256k1_fe_cmov(&y, &x, 1);
 535         CHECK(secp256k1_fe_equal(&x, &y));
 536         /* Test that mul_int, mul, and add agree. */
 537         secp256k1_fe_add(&y, &x);
 538         secp256k1_fe_add(&y, &x);
 539         z = x;
 540         secp256k1_fe_mul_int(&z, 3);
 541         CHECK(check_fe_equal(&y, &z));
 542         secp256k1_fe_add(&y, &x);
 543         secp256k1_fe_add(&z, &x);
 544         CHECK(check_fe_equal(&z, &y));
 545         z = x;
 546         secp256k1_fe_mul_int(&z, 5);
 547         secp256k1_fe_mul(&q, &x, &fe5);
 548         CHECK(check_fe_equal(&z, &q));
 549         secp256k1_fe_negate(&x, &x, 1);
 550         secp256k1_fe_add(&z, &x);
 551         secp256k1_fe_add(&q, &x);
 552         CHECK(check_fe_equal(&y, &z));
 553         CHECK(check_fe_equal(&q, &y));
 554     }
 555 }
 556
 557 void run_field_inv(void) {
 558     secp256k1_fe_t x, xi, xii;
 559     for (int i=0; i<10*count; i++) {
 560         random_fe_non_zero(&x);
 561         secp256k1_fe_inv(&xi, &x);
 562         CHECK(check_fe_inverse(&x, &xi));
 563         secp256k1_fe_inv(&xii, &xi);
 564         CHECK(check_fe_equal(&x, &xii));
 565     }
 566 }
 567
 568 void run_field_inv_var(void) {
 569     secp256k1_fe_t x, xi, xii;
 570     for (int i=0; i<10*count; i++) {
 571         random_fe_non_zero(&x);
 572         secp256k1_fe_inv_var(&xi, &x);
 573         CHECK(check_fe_inverse(&x, &xi));
 574         secp256k1_fe_inv_var(&xii, &xi);
 575         CHECK(check_fe_equal(&x, &xii));
 576     }
 577 }
 578
 579 void run_field_inv_all_var(void) {
 580     secp256k1_fe_t x[16], xi[16], xii[16];
 581     /* Check it's safe to call for 0 elements */
 582     secp256k1_fe_inv_all_var(0, xi, x);
 583     for (int i=0; i<count; i++) {
 584         size_t len = (secp256k1_rand32() & 15) + 1;
 585         for (size_t j=0; j<len; j++)
 586             random_fe_non_zero(&x[j]);
 587         secp256k1_fe_inv_all_var(len, xi, x);
 588         for (size_t j=0; j<len; j++)
 589             CHECK(check_fe_inverse(&x[j], &xi[j]));
 590         secp256k1_fe_inv_all_var(len, xii, xi);
 591         for (size_t j=0; j<len; j++)
 592             CHECK(check_fe_equal(&x[j], &xii[j]));
 593     }
 594 }
 595
 596 void run_sqr(void) {
 597     secp256k1_fe_t x, s;
 598
 599     {
 600         secp256k1_fe_set_int(&x, 1);
 601         secp256k1_fe_negate(&x, &x, 1);
 602
 603         for (int i=1; i<=512; ++i) {
 604             secp256k1_fe_mul_int(&x, 2);
 605             secp256k1_fe_normalize(&x);
 606             secp256k1_fe_sqr(&s, &x);
 607         }
 608     }
 609 }
 610
 611 void test_sqrt(const secp256k1_fe_t *a, const secp256k1_fe_t *k) {
 612     secp256k1_fe_t r1, r2;
 613     int v = secp256k1_fe_sqrt_var(&r1, a);
 614     CHECK((v == 0) == (k == NULL));
 615
 616     if (k != NULL) {
 617         /* Check that the returned root is +/- the given known answer */
 618         secp256k1_fe_negate(&r2, &r1, 1);
 619         secp256k1_fe_add(&r1, k); secp256k1_fe_add(&r2, k);
 620         secp256k1_fe_normalize(&r1); secp256k1_fe_normalize(&r2);
 621         CHECK(secp256k1_fe_is_zero(&r1) || secp256k1_fe_is_zero(&r2));
 622     }
 623 }
 624
 625 void run_sqrt(void) {
 626     secp256k1_fe_t ns, x, s, t;
 627
 628     /* Check sqrt(0) is 0 */
 629     secp256k1_fe_set_int(&x, 0);
 630     secp256k1_fe_sqr(&s, &x);
 631     test_sqrt(&s, &x);
 632
 633     /* Check sqrt of small squares (and their negatives) */
 634     for (int i=1; i<=100; i++) {
 635         secp256k1_fe_set_int(&x, i);
 636         secp256k1_fe_sqr(&s, &x);
 637         test_sqrt(&s, &x);
 638         secp256k1_fe_negate(&t, &s, 1);
 639         test_sqrt(&t, NULL);
 640     }
 641
 642     /* Consistency checks for large random values */
 643     for (int i=0; i<10; i++) {
 644         random_fe_non_square(&ns);
 645         for (int j=0; j<count; j++) {
 646             random_fe(&x);
 647             secp256k1_fe_sqr(&s, &x);
 648             test_sqrt(&s, &x);
 649             secp256k1_fe_negate(&t, &s, 1);
 650             test_sqrt(&t, NULL);
 651             secp256k1_fe_mul(&t, &s, &ns);
 652             test_sqrt(&t, NULL);
 653         }
 654     }
 655 }
 656
 657 /***** GROUP TESTS *****/
 658
 659 int ge_equals_ge(const secp256k1_ge_t *a, const secp256k1_ge_t *b) {
 660     if (a->infinity && b->infinity)
 661         return 1;
 662     return check_fe_equal(&a->x, &b->x) && check_fe_equal(&a->y, &b->y);
 663 }
 664
 665 void ge_equals_gej(const secp256k1_ge_t *a, const secp256k1_gej_t *b) {
 666     secp256k1_ge_t bb;
 667     secp256k1_gej_t bj = *b;
 668     secp256k1_ge_set_gej_var(&bb, &bj);
 669     CHECK(ge_equals_ge(a, &bb));
 670 }
 671
 672 void gej_equals_gej(const secp256k1_gej_t *a, const secp256k1_gej_t *b) {
 673     secp256k1_ge_t aa, bb;
 674     secp256k1_gej_t aj = *a, bj = *b;
 675     secp256k1_ge_set_gej_var(&aa, &aj);
 676     secp256k1_ge_set_gej_var(&bb, &bj);
 677     CHECK(ge_equals_ge(&aa, &bb));
 678 }
 679
 680 void test_ge(void) {
 681     char ca[135];
 682     char cb[68];
 683     int rlen;
 684     secp256k1_ge_t a, b, i, n;
 685     random_group_element_test(&a);
 686     random_group_element_test(&b);
 687     rlen = sizeof(ca);
 688     secp256k1_ge_get_hex(ca,&rlen,&a);
 689     CHECK(rlen > 4 && rlen <= (int)sizeof(ca));
 690     rlen = sizeof(cb);
 691     secp256k1_ge_get_hex(cb,&rlen,&b); /* Intentionally undersized buffer. */
 692     n = a;
 693     secp256k1_fe_normalize(&a.y);
 694     secp256k1_fe_negate(&n.y, &a.y, 1);
 695     secp256k1_ge_set_infinity(&i);
 696     random_field_element_magnitude(&a.x);
 697     random_field_element_magnitude(&a.y);
 698     random_field_element_magnitude(&b.x);
 699     random_field_element_magnitude(&b.y);
 700     random_field_element_magnitude(&n.x);
 701     random_field_element_magnitude(&n.y);
 702
 703     secp256k1_gej_t aj, bj, ij, nj;
 704     random_group_element_jacobian_test(&aj, &a);
 705     random_group_element_jacobian_test(&bj, &b);
 706     secp256k1_gej_set_infinity(&ij);
 707     random_group_element_jacobian_test(&nj, &n);
 708     random_field_element_magnitude(&aj.x);
 709     random_field_element_magnitude(&aj.y);
 710     random_field_element_magnitude(&aj.z);
 711     random_field_element_magnitude(&bj.x);
 712     random_field_element_magnitude(&bj.y);
 713     random_field_element_magnitude(&bj.z);
 714     random_field_element_magnitude(&nj.x);
 715     random_field_element_magnitude(&nj.y);
 716     random_field_element_magnitude(&nj.z);
 717
 718     /* gej + gej adds */
 719     secp256k1_gej_t aaj; secp256k1_gej_add_var(&aaj, &aj, &aj);
 720     secp256k1_gej_t abj; secp256k1_gej_add_var(&abj, &aj, &bj);
 721     secp256k1_gej_t aij; secp256k1_gej_add_var(&aij, &aj, &ij);
 722     secp256k1_gej_t anj; secp256k1_gej_add_var(&anj, &aj, &nj);
 723     secp256k1_gej_t iaj; secp256k1_gej_add_var(&iaj, &ij, &aj);
 724     secp256k1_gej_t iij; secp256k1_gej_add_var(&iij, &ij, &ij);
 725
 726     /* gej + ge adds */
 727     secp256k1_gej_t aa; secp256k1_gej_add_ge_var(&aa, &aj, &a);
 728     secp256k1_gej_t ab; secp256k1_gej_add_ge_var(&ab, &aj, &b);
 729     secp256k1_gej_t ai; secp256k1_gej_add_ge_var(&ai, &aj, &i);
 730     secp256k1_gej_t an; secp256k1_gej_add_ge_var(&an, &aj, &n);
 731     secp256k1_gej_t ia; secp256k1_gej_add_ge_var(&ia, &ij, &a);
 732     secp256k1_gej_t ii; secp256k1_gej_add_ge_var(&ii, &ij, &i);
 733
 734     /* const gej + ge adds */
 735     secp256k1_gej_t aac; secp256k1_gej_add_ge(&aac, &aj, &a);
 736     secp256k1_gej_t abc; secp256k1_gej_add_ge(&abc, &aj, &b);
 737     secp256k1_gej_t anc; secp256k1_gej_add_ge(&anc, &aj, &n);
 738     secp256k1_gej_t iac; secp256k1_gej_add_ge(&iac, &ij, &a);
 739
 740     CHECK(secp256k1_gej_is_infinity(&an));
 741     CHECK(secp256k1_gej_is_infinity(&anj));
 742     CHECK(secp256k1_gej_is_infinity(&anc));
 743     gej_equals_gej(&aa, &aaj);
 744     gej_equals_gej(&aa, &aac);
 745     gej_equals_gej(&ab, &abj);
 746     gej_equals_gej(&ab, &abc);
 747     gej_equals_gej(&an, &anj);
 748     gej_equals_gej(&an, &anc);
 749     gej_equals_gej(&ia, &iaj);
 750     gej_equals_gej(&ai, &aij);
 751     gej_equals_gej(&ii, &iij);
 752     ge_equals_gej(&a, &ai);
 753     ge_equals_gej(&a, &ai);
 754     ge_equals_gej(&a, &iaj);
 755     ge_equals_gej(&a, &iaj);
 756     ge_equals_gej(&a, &iac);
 757 }
 758
 759 void run_ge(void) {
 760     for (int i = 0; i < 2000*count; i++) {
 761         test_ge();
 762     }
 763 }
 764
 765 /***** ECMULT TESTS *****/
 766
 767 void run_ecmult_chain(void) {
 768     /* random starting point A (on the curve) */
 769     secp256k1_fe_t ax; VERIFY_CHECK(secp256k1_fe_set_hex(&ax, "8b30bbe9ae2a990696b22f670709dff3727fd8bc04d3362c6c7bf458e2846004", 64));
 770     secp256k1_fe_t ay; VERIFY_CHECK(secp256k1_fe_set_hex(&ay, "a357ae915c4a65281309edf20504740f0eb3343990216b4f81063cb65f2f7e0f", 64));
 771     secp256k1_gej_t a; secp256k1_gej_set_xy(&a, &ax, &ay);
 772     /* two random initial factors xn and gn */
 773     static const unsigned char xni[32] = {
 774         0x84, 0xcc, 0x54, 0x52, 0xf7, 0xfd, 0xe1, 0xed,
 775         0xb4, 0xd3, 0x8a, 0x8c, 0xe9, 0xb1, 0xb8, 0x4c,
 776         0xce, 0xf3, 0x1f, 0x14, 0x6e, 0x56, 0x9b, 0xe9,
 777         0x70, 0x5d, 0x35, 0x7a, 0x42, 0x98, 0x54, 0x07
 778     };
 779     secp256k1_scalar_t xn;
 780     secp256k1_scalar_set_b32(&xn, xni, NULL);
 781     static const unsigned char gni[32] = {
 782         0xa1, 0xe5, 0x8d, 0x22, 0x55, 0x3d, 0xcd, 0x42,
 783         0xb2, 0x39, 0x80, 0x62, 0x5d, 0x4c, 0x57, 0xa9,
 784         0x6e, 0x93, 0x23, 0xd4, 0x2b, 0x31, 0x52, 0xe5,
 785         0xca, 0x2c, 0x39, 0x90, 0xed, 0xc7, 0xc9, 0xde
 786     };
 787     secp256k1_scalar_t gn;
 788     secp256k1_scalar_set_b32(&gn, gni, NULL);
 789     /* two small multipliers to be applied to xn and gn in every iteration: */
 790     static const unsigned char xfi[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0x13,0x37};
 791     secp256k1_scalar_t xf;
 792     secp256k1_scalar_set_b32(&xf, xfi, NULL);
 793     static const unsigned char gfi[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0x71,0x13};
 794     secp256k1_scalar_t gf;
 795     secp256k1_scalar_set_b32(&gf, gfi, NULL);
 796     /* accumulators with the resulting coefficients to A and G */
 797     secp256k1_scalar_t ae;
 798     secp256k1_scalar_set_int(&ae, 1);
 799     secp256k1_scalar_t ge;
 800     secp256k1_scalar_set_int(&ge, 0);
 801     /* the point being computed */
 802     secp256k1_gej_t x = a;
 803     for (int i=0; i<200*count; i++) {
 804         /* in each iteration, compute X = xn*X + gn*G; */
 805         secp256k1_ecmult(&x, &x, &xn, &gn);
 806         /* also compute ae and ge: the actual accumulated factors for A and G */
 807         /* if X was (ae*A+ge*G), xn*X + gn*G results in (xn*ae*A + (xn*ge+gn)*G) */
 808         secp256k1_scalar_mul(&ae, &ae, &xn);
 809         secp256k1_scalar_mul(&ge, &ge, &xn);
 810         secp256k1_scalar_add(&ge, &ge, &gn);
 811         /* modify xn and gn */
 812         secp256k1_scalar_mul(&xn, &xn, &xf);
 813         secp256k1_scalar_mul(&gn, &gn, &gf);
 814
 815         /* verify */
 816         if (i == 19999) {
 817             char res[132]; int resl = 132;
 818             secp256k1_gej_get_hex(res, &resl, &x);
 819             CHECK(strcmp(res, "(D6E96687F9B10D092A6F35439D86CEBEA4535D0D409F53586440BD74B933E830,B95CBCA2C77DA786539BE8FD53354D2D3B4F566AE658045407ED6015EE1B2A88)") == 0);
 820         }
 821     }
 822     /* redo the computation, but directly with the resulting ae and ge coefficients: */
 823     secp256k1_gej_t x2; secp256k1_ecmult(&x2, &a, &ae, &ge);
 824     char res[132]; int resl = 132;
 825     char res2[132]; int resl2 = 132;
 826     secp256k1_gej_get_hex(res, &resl, &x);
 827     secp256k1_gej_get_hex(res2, &resl2, &x2);
 828     CHECK(strcmp(res, res2) == 0);
 829     CHECK(strlen(res) == 131);
 830 }
 831
 832 void test_point_times_order(const secp256k1_gej_t *point) {
 833     unsigned char pub[65];
 834     /* X * (point + G) + (order-X) * (pointer + G) = 0 */
 835     secp256k1_scalar_t x;
 836     random_scalar_order_test(&x);
 837     secp256k1_scalar_t nx;
 838     secp256k1_scalar_negate(&nx, &x);
 839     secp256k1_gej_t res1, res2;
 840     secp256k1_ecmult(&res1, point, &x, &x); /* calc res1 = x * point + x * G; */
 841     secp256k1_ecmult(&res2, point, &nx, &nx); /* calc res2 = (order - x) * point + (order - x) * G; */
 842     secp256k1_gej_add_var(&res1, &res1, &res2);
 843     CHECK(secp256k1_gej_is_infinity(&res1));
 844     CHECK(secp256k1_gej_is_valid_var(&res1) == 0);
 845     secp256k1_ge_t res3;
 846     secp256k1_ge_set_gej(&res3, &res1);
 847     CHECK(secp256k1_ge_is_infinity(&res3));
 848     CHECK(secp256k1_ge_is_valid_var(&res3) == 0);
 849     int psize = 65;
 850     CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 0) == 0);
 851     psize = 65;
 852     CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 1) == 0);
 853 }
 854
 855 void run_point_times_order(void) {
 856     secp256k1_fe_t x; VERIFY_CHECK(secp256k1_fe_set_hex(&x, "02", 2));
 857     for (int i=0; i<500; i++) {
 858         secp256k1_ge_t p;
 859         if (secp256k1_ge_set_xo_var(&p, &x, 1)) {
 860             CHECK(secp256k1_ge_is_valid_var(&p));
 861             secp256k1_gej_t j;
 862             secp256k1_gej_set_ge(&j, &p);
 863             CHECK(secp256k1_gej_is_valid_var(&j));
 864             test_point_times_order(&j);
 865         }
 866         secp256k1_fe_sqr(&x, &x);
 867     }
 868     char c[65];
 869     int cl = 1;
 870     c[1] = 123;
 871     secp256k1_fe_get_hex(c, &cl, &x); /* Check that fe_get_hex handles a too short input. */
 872     CHECK(c[1] == 123);
 873     cl = 65;
 874     secp256k1_fe_get_hex(c, &cl, &x);
 875     CHECK(strcmp(c, "7603CB59B0EF6C63FE6084792A0C378CDB3233A80F8A9A09A877DEAD31B38C45") == 0);
 876 }
 877
 878 void test_wnaf(const secp256k1_scalar_t *number, int w) {
 879     secp256k1_scalar_t x, two, t;
 880     secp256k1_scalar_set_int(&x, 0);
 881     secp256k1_scalar_set_int(&two, 2);
 882     int wnaf[256];
 883     int bits = secp256k1_ecmult_wnaf(wnaf, number, w);
 884     CHECK(bits <= 256);
 885     int zeroes = -1;
 886     for (int i=bits-1; i>=0; i--) {
 887         secp256k1_scalar_mul(&x, &x, &two);
 888         int v = wnaf[i];
 889         if (v) {
 890             CHECK(zeroes == -1 || zeroes >= w-1); /* check that distance between non-zero elements is at least w-1 */
 891             zeroes=0;
 892             CHECK((v & 1) == 1); /* check non-zero elements are odd */
 893             CHECK(v <= (1 << (w-1)) - 1); /* check range below */
 894             CHECK(v >= -(1 << (w-1)) - 1); /* check range above */
 895         } else {
 896             CHECK(zeroes != -1); /* check that no unnecessary zero padding exists */
 897             zeroes++;
 898         }
 899         if (v >= 0) {
 900             secp256k1_scalar_set_int(&t, v);
 901         } else {
 902             secp256k1_scalar_set_int(&t, -v);
 903             secp256k1_scalar_negate(&t, &t);
 904         }
 905         secp256k1_scalar_add(&x, &x, &t);
 906     }
 907     CHECK(secp256k1_scalar_eq(&x, number)); /* check that wnaf represents number */
 908 }
 909
 910 void run_wnaf(void) {
 911     secp256k1_scalar_t n;
 912     for (int i=0; i<count; i++) {
 913         random_scalar_order(&n);
 914         if (i % 1)
 915             secp256k1_scalar_negate(&n, &n);
 916         test_wnaf(&n, 4+(i%10));
 917     }
 918 }
 919
 920 void random_sign(secp256k1_ecdsa_sig_t *sig, const secp256k1_scalar_t *key, const secp256k1_scalar_t *msg, int *recid) {
 921     secp256k1_scalar_t nonce;
 922     do {
 923         random_scalar_order_test(&nonce);
 924     } while(!secp256k1_ecdsa_sig_sign(sig, key, msg, &nonce, recid));
 925 }
 926
 927 void test_ecdsa_sign_verify(void) {
 928     int recid;
 929     int getrec;
 930     secp256k1_scalar_t msg, key;
 931     random_scalar_order_test(&msg);
 932     random_scalar_order_test(&key);
 933     secp256k1_gej_t pubj; secp256k1_ecmult_gen(&pubj, &key);
 934     secp256k1_ge_t pub; secp256k1_ge_set_gej(&pub, &pubj);
 935     secp256k1_ecdsa_sig_t sig;
 936     getrec = secp256k1_rand32()&1;
 937     random_sign(&sig, &key, &msg, getrec?&recid:NULL);
 938     if (getrec) CHECK(recid >= 0 && recid < 4);
 939     CHECK(secp256k1_ecdsa_sig_verify(&sig, &pub, &msg));
 940     secp256k1_scalar_t one;
 941     secp256k1_scalar_set_int(&one, 1);
 942     secp256k1_scalar_add(&msg, &msg, &one);
 943     CHECK(!secp256k1_ecdsa_sig_verify(&sig, &pub, &msg));
 944 }
 945
 946 void run_ecdsa_sign_verify(void) {
 947     for (int i=0; i<10*count; i++) {
 948         test_ecdsa_sign_verify();
 949     }
 950 }
 951
 952 void test_ecdsa_end_to_end(void) {
 953     unsigned char privkey[32];
 954     unsigned char message[32];
 955
 956     /* Generate a random key and message. */
 957     {
 958         secp256k1_scalar_t msg, key;
 959         random_scalar_order_test(&msg);
 960         random_scalar_order_test(&key);
 961         secp256k1_scalar_get_b32(privkey, &key);
 962         secp256k1_scalar_get_b32(message, &msg);
 963     }
 964
 965     /* Construct and verify corresponding public key. */
 966     CHECK(secp256k1_ec_seckey_verify(privkey) == 1);
 967     unsigned char pubkey[65]; int pubkeylen = 65;
 968     CHECK(secp256k1_ec_pubkey_create(pubkey, &pubkeylen, privkey, (secp256k1_rand32() & 3) != 0) == 1);
 969     if (secp256k1_rand32() & 1) {
 970         CHECK(secp256k1_ec_pubkey_decompress(pubkey, &pubkeylen));
 971     }
 972     CHECK(secp256k1_ec_pubkey_verify(pubkey, pubkeylen));
 973
 974     /* Verify private key import and export. */
 975     unsigned char seckey[300]; int seckeylen = 300;
 976     CHECK(secp256k1_ec_privkey_export(privkey, seckey, &seckeylen, secp256k1_rand32() % 2) == 1);
 977     unsigned char privkey2[32];
 978     CHECK(secp256k1_ec_privkey_import(privkey2, seckey, seckeylen) == 1);
 979     CHECK(memcmp(privkey, privkey2, 32) == 0);
 980
 981     /* Optionally tweak the keys using addition. */
 982     if (secp256k1_rand32() % 3 == 0) {
 983         unsigned char rnd[32];
 984         secp256k1_rand256_test(rnd);
 985         int ret1 = secp256k1_ec_privkey_tweak_add(privkey, rnd);
 986         int ret2 = secp256k1_ec_pubkey_tweak_add(pubkey, pubkeylen, rnd);
 987         CHECK(ret1 == ret2);
 988         if (ret1 == 0) return;
 989         unsigned char pubkey2[65]; int pubkeylen2 = 65;
 990         CHECK(secp256k1_ec_pubkey_create(pubkey2, &pubkeylen2, privkey, pubkeylen == 33) == 1);
 991         CHECK(memcmp(pubkey, pubkey2, pubkeylen) == 0);
 992     }
 993
 994     /* Optionally tweak the keys using multiplication. */
 995     if (secp256k1_rand32() % 3 == 0) {
 996         unsigned char rnd[32];
 997         secp256k1_rand256_test(rnd);
 998         int ret1 = secp256k1_ec_privkey_tweak_mul(privkey, rnd);
 999         int ret2 = secp256k1_ec_pubkey_tweak_mul(pubkey, pubkeylen, rnd);
1000         CHECK(ret1 == ret2);
1001         if (ret1 == 0) return;
1002         unsigned char pubkey2[65]; int pubkeylen2 = 65;
1003         CHECK(secp256k1_ec_pubkey_create(pubkey2, &pubkeylen2, privkey, pubkeylen == 33) == 1);
1004         CHECK(memcmp(pubkey, pubkey2, pubkeylen) == 0);
1005     }
1006
1007     /* Sign. */
1008     unsigned char signature[72]; int signaturelen = 72;
1009     while(1) {
1010         unsigned char rnd[32];
1011         secp256k1_rand256_test(rnd);
1012         if (secp256k1_ecdsa_sign(message, 32, signature, &signaturelen, privkey, rnd) == 1) {
1013             break;
1014         }
1015     }
1016     /* Verify. */
1017     CHECK(secp256k1_ecdsa_verify(message, 32, signature, signaturelen, pubkey, pubkeylen) == 1);
1018     /* Destroy signature and verify again. */
1019     signature[signaturelen - 1 - secp256k1_rand32() % 20] += 1 + (secp256k1_rand32() % 255);
1020     CHECK(secp256k1_ecdsa_verify(message, 32, signature, signaturelen, pubkey, pubkeylen) != 1);
1021
1022     /* Compact sign. */
1023     unsigned char csignature[64]; int recid = 0;
1024     while(1) {
1025         unsigned char rnd[32];
1026         secp256k1_rand256_test(rnd);
1027         if (secp256k1_ecdsa_sign_compact(message, 32, csignature, privkey, rnd, &recid) == 1) {
1028             break;
1029         }
1030     }
1031     /* Recover. */
1032     unsigned char recpubkey[65]; int recpubkeylen = 0;
1033     CHECK(secp256k1_ecdsa_recover_compact(message, 32, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) == 1);
1034     CHECK(recpubkeylen == pubkeylen);
1035     CHECK(memcmp(pubkey, recpubkey, pubkeylen) == 0);
1036     /* Destroy signature and verify again. */
1037     csignature[secp256k1_rand32() % 64] += 1 + (secp256k1_rand32() % 255);
1038     CHECK(secp256k1_ecdsa_recover_compact(message, 32, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) != 1 ||
1039           memcmp(pubkey, recpubkey, pubkeylen) != 0);
1040     CHECK(recpubkeylen == pubkeylen);
1041
1042 }
1043
1044 void test_random_pubkeys(void) {
1045     unsigned char in[65];
1046     /* Generate some randomly sized pubkeys. */
1047     uint32_t r = secp256k1_rand32();
1048     int len = (r & 3) == 0 ? 65 : 33;
1049     r>>=2;
1050     if ((r & 3) == 0) len = (r & 252) >> 3;
1051     r>>=8;
1052     if (len == 65) {
1053       in[0] = (r & 2) ? 4 : (r & 1? 6 : 7);
1054     } else {
1055       in[0] = (r & 1) ? 2 : 3;
1056     }
1057     r>>=2;
1058     if ((r & 7) == 0) in[0] = (r & 2040) >> 3;
1059     r>>=11;
1060     if (len > 1) secp256k1_rand256(&in[1]);
1061     if (len > 33) secp256k1_rand256(&in[33]);
1062     secp256k1_ge_t elem;
1063     secp256k1_ge_t elem2;
1064     if (secp256k1_eckey_pubkey_parse(&elem, in, len)) {
1065         unsigned char out[65];
1066         unsigned char firstb;
1067         int res;
1068         int size = len;
1069         firstb = in[0];
1070         /* If the pubkey can be parsed, it should round-trip... */
1071         CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, len == 33));
1072         CHECK(size == len);
1073         CHECK(memcmp(&in[1], &out[1], len-1) == 0);
1074         /* ... except for the type of hybrid inputs. */
1075         if ((in[0] != 6) && (in[0] != 7)) CHECK(in[0] == out[0]);
1076         size = 65;
1077         CHECK(secp256k1_eckey_pubkey_serialize(&elem, in, &size, 0));
1078         CHECK(size == 65);
1079         CHECK(secp256k1_eckey_pubkey_parse(&elem2, in, size));
1080         CHECK(ge_equals_ge(&elem,&elem2));
1081         /* Check that the X9.62 hybrid type is checked. */
1082         in[0] = (r & 1) ? 6 : 7;
1083         res = secp256k1_eckey_pubkey_parse(&elem2, in, size);
1084         if (firstb == 2 || firstb == 3) {
1085             if (in[0] == firstb + 4) CHECK(res);
1086             else CHECK(!res);
1087         }
1088         if (res) {
1089             CHECK(ge_equals_ge(&elem,&elem2));
1090             CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, 0));
1091             CHECK(memcmp(&in[1], &out[1], 64) == 0);
1092         }
1093     }
1094 }
1095
1096 void run_random_pubkeys(void) {
1097     for (int i=0; i<10*count; i++) {
1098         test_random_pubkeys();
1099     }
1100 }
1101
1102 void run_ecdsa_end_to_end(void) {
1103     for (int i=0; i<64*count; i++) {
1104         test_ecdsa_end_to_end();
1105     }
1106 }
1107
1108 /* Tests several edge cases. */
1109 void test_ecdsa_edge_cases(void) {
1110     const unsigned char msg32[32] = {
1111         'T', 'h', 'i', 's', ' ', 'i', 's', ' ',
1112         'a', ' ', 'v', 'e', 'r', 'y', ' ', 's',
1113         'e', 'c', 'r', 'e', 't', ' ', 'm', 'e',
1114         's', 's', 'a', 'g', 'e', '.', '.', '.'
1115     };
1116     const unsigned char sig64[64] = {
1117         /* Generated by signing the above message with nonce 'This is the nonce we will use...'
1118          * and secret key 0 (which is not valid), resulting in recid 0. */
1119         0x67, 0xCB, 0x28, 0x5F, 0x9C, 0xD1, 0x94, 0xE8,
1120         0x40, 0xD6, 0x29, 0x39, 0x7A, 0xF5, 0x56, 0x96,
1121         0x62, 0xFD, 0xE4, 0x46, 0x49, 0x99, 0x59, 0x63,
1122         0x17, 0x9A, 0x7D, 0xD1, 0x7B, 0xD2, 0x35, 0x32,
1123         0x4B, 0x1B, 0x7D, 0xF3, 0x4C, 0xE1, 0xF6, 0x8E,
1124         0x69, 0x4F, 0xF6, 0xF1, 0x1A, 0xC7, 0x51, 0xDD,
1125         0x7D, 0xD7, 0x3E, 0x38, 0x7E, 0xE4, 0xFC, 0x86,
1126         0x6E, 0x1B, 0xE8, 0xEC, 0xC7, 0xDD, 0x95, 0x57
1127     };
1128     unsigned char pubkey[65];
1129     int pubkeylen = 65;
1130     CHECK(!secp256k1_ecdsa_recover_compact(msg32, 32, sig64, pubkey, &pubkeylen, 0, 0));
1131     CHECK(secp256k1_ecdsa_recover_compact(msg32, 32, sig64, pubkey, &pubkeylen, 0, 1));
1132     CHECK(!secp256k1_ecdsa_recover_compact(msg32, 32, sig64, pubkey, &pubkeylen, 0, 2));
1133     CHECK(!secp256k1_ecdsa_recover_compact(msg32, 32, sig64, pubkey, &pubkeylen, 0, 3));
1134
1135     /* signature (r,s) = (4,4), which can be recovered with all 4 recids. */
1136     const unsigned char sigb64[64] = {
1137         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1138         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1139         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1140         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
1141         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1142         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1143         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1144         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
1145     };
1146     unsigned char pubkeyb[33];
1147     int pubkeyblen = 33;
1148     for (int recid = 0; recid < 4; recid++) {
1149         /* (4,4) encoded in DER. */
1150         unsigned char sigbder[8] = {0x30, 0x06, 0x02, 0x01, 0x04, 0x02, 0x01, 0x04};
1151         unsigned char sigcder_zr[7] = {0x30, 0x05, 0x02, 0x00, 0x02, 0x01, 0x01};
1152         unsigned char sigcder_zs[7] = {0x30, 0x05, 0x02, 0x01, 0x01, 0x02, 0x00};
1153         unsigned char sigbderalt1[39] = {
1154             0x30, 0x25, 0x02, 0x20, 0x00, 0x00, 0x00, 0x00,
1155             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1156             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1157             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1158             0x00, 0x00, 0x00, 0x04, 0x02, 0x01, 0x04,
1159         };
1160         unsigned char sigbderalt2[39] = {
1161             0x30, 0x25, 0x02, 0x01, 0x04, 0x02, 0x20, 0x00,
1162             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1163             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1164             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1165             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
1166         };
1167         unsigned char sigbderalt3[40] = {
1168             0x30, 0x26, 0x02, 0x21, 0x00, 0x00, 0x00, 0x00,
1169             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1170             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1171             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1172             0x00, 0x00, 0x00, 0x00, 0x04, 0x02, 0x01, 0x04,
1173         };
1174         unsigned char sigbderalt4[40] = {
1175             0x30, 0x26, 0x02, 0x01, 0x04, 0x02, 0x21, 0x00,
1176             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1177             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1178             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1179             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
1180         };
1181         /* (order + r,4) encoded in DER. */
1182         unsigned char sigbderlong[40] = {
1183             0x30, 0x26, 0x02, 0x21, 0x00, 0xFF, 0xFF, 0xFF,
1184             0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
1185             0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xBA, 0xAE, 0xDC,
1186             0xE6, 0xAF, 0x48, 0xA0, 0x3B, 0xBF, 0xD2, 0x5E,
1187             0x8C, 0xD0, 0x36, 0x41, 0x45, 0x02, 0x01, 0x04
1188         };
1189         CHECK(secp256k1_ecdsa_recover_compact(msg32, 32, sigb64, pubkeyb, &pubkeyblen, 1, recid));
1190         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) == 1);
1191         for (int recid2 = 0; recid2 < 4; recid2++) {
1192             unsigned char pubkey2b[33];
1193             int pubkey2blen = 33;
1194             CHECK(secp256k1_ecdsa_recover_compact(msg32, 32, sigb64, pubkey2b, &pubkey2blen, 1, recid2));
1195             /* Verifying with (order + r,4) should always fail. */
1196             CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbderlong, sizeof(sigbderlong), pubkey2b, pubkey2blen) != 1);
1197         }
1198         /* DER parsing tests. */
1199         /* Zero length r/s. */
1200         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigcder_zr, sizeof(sigcder_zr), pubkeyb, pubkeyblen) == -2);
1201         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigcder_zs, sizeof(sigcder_zs), pubkeyb, pubkeyblen) == -2);
1202         /* Leading zeros. */
1203         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbderalt1, sizeof(sigbderalt1), pubkeyb, pubkeyblen) == 1);
1204         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbderalt2, sizeof(sigbderalt2), pubkeyb, pubkeyblen) == 1);
1205         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbderalt3, sizeof(sigbderalt3), pubkeyb, pubkeyblen) == 1);
1206         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbderalt4, sizeof(sigbderalt4), pubkeyb, pubkeyblen) == 1);
1207         sigbderalt3[4] = 1;
1208         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbderalt3, sizeof(sigbderalt3), pubkeyb, pubkeyblen) == -2);
1209         sigbderalt4[7] = 1;
1210         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbderalt4, sizeof(sigbderalt4), pubkeyb, pubkeyblen) == -2);
1211         /* Damage signature. */
1212         sigbder[7]++;
1213         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) == 0);
1214         sigbder[7]--;
1215         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbder, 6, pubkeyb, pubkeyblen) == -2);
1216         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbder, sizeof(sigbder)-1, pubkeyb, pubkeyblen) == -2);
1217         for(int i = 0; i<8; i++) {
1218             unsigned char orig = sigbder[i];
1219             /*Try every single-byte change.*/
1220             for (int c=0; c<256; c++) {
1221                 if (c == orig ) continue;
1222                 sigbder[i] = c;
1223                 CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) ==
1224                   (i==4 || i==7) ? 0 : -2 );
1225             }
1226             sigbder[i] = orig;
1227         }
1228     }
1229
1230     /* Test the case where ECDSA recomputes a point that is infinity. */
1231     {
1232         secp256k1_ecdsa_sig_t sig;
1233         secp256k1_scalar_set_int(&sig.s, 1);
1234         secp256k1_scalar_negate(&sig.s, &sig.s);
1235         secp256k1_scalar_inverse(&sig.s, &sig.s);
1236         secp256k1_scalar_set_int(&sig.r, 1);
1237         secp256k1_gej_t keyj;
1238         secp256k1_ecmult_gen(&keyj, &sig.r);
1239         secp256k1_ge_t key;
1240         secp256k1_ge_set_gej(&key, &keyj);
1241         secp256k1_scalar_t msg = sig.s;
1242         CHECK(secp256k1_ecdsa_sig_verify(&sig, &key, &msg) == 0);
1243     }
1244
1245     /* Test r/s equal to zero */
1246     {
1247         /* (1,1) encoded in DER. */
1248         unsigned char sigcder[8] = {0x30, 0x06, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01};
1249         unsigned char sigc64[64] = {
1250             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1251             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1252             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1253             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
1254             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1255             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1256             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1257             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
1258         };
1259         unsigned char pubkeyc[65];
1260         int pubkeyclen = 65;
1261         CHECK(secp256k1_ecdsa_recover_compact(msg32, 32, sigc64, pubkeyc, &pubkeyclen, 0, 0) == 1);
1262         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 1);
1263         sigcder[4] = 0;
1264         sigc64[31] = 0;
1265         CHECK(secp256k1_ecdsa_recover_compact(msg32, 32, sigc64, pubkeyb, &pubkeyblen, 1, 0) == 0);
1266         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 0);
1267         sigcder[4] = 1;
1268         sigcder[7] = 0;
1269         sigc64[31] = 1;
1270         sigc64[63] = 0;
1271         CHECK(secp256k1_ecdsa_recover_compact(msg32, 32, sigc64, pubkeyb, &pubkeyblen, 1, 0) == 0);
1272         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 0);
1273     }
1274
1275     /*Signature where s would be zero.*/
1276     {
1277         const unsigned char nonce[32] = {
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, 0x01,
1282         };
1283         const unsigned char key[32] = {
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, 0x01,
1288         };
1289         unsigned char msg[32] = {
1290             0x86, 0x41, 0x99, 0x81, 0x06, 0x23, 0x44, 0x53,
1291             0xaa, 0x5f, 0x9d, 0x6a, 0x31, 0x78, 0xf4, 0xf7,
1292             0xb8, 0x12, 0xe0, 0x0b, 0x81, 0x7a, 0x77, 0x62,
1293             0x65, 0xdf, 0xdd, 0x31, 0xb9, 0x3e, 0x29, 0xa9,
1294         };
1295         unsigned char sig[72];
1296         int siglen = 72;
1297         CHECK(secp256k1_ecdsa_sign(msg, 32, sig, &siglen, key, nonce) == 0);
1298         msg[31] = 0xaa;
1299         siglen = 72;
1300         CHECK(secp256k1_ecdsa_sign(msg, 32, sig, &siglen, key, nonce) == 1);
1301     }
1302
1303     /* Privkey export where pubkey is the point at infinity. */
1304     {
1305         unsigned char privkey[300];
1306         unsigned char seckey[32] = {
1307             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1308             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
1309             0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
1310             0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41,
1311         };
1312         int outlen = 300;
1313         CHECK(!secp256k1_ec_privkey_export(seckey, privkey, &outlen, 0));
1314         CHECK(!secp256k1_ec_privkey_export(seckey, privkey, &outlen, 1));
1315     }
1316 }
1317
1318 void run_ecdsa_edge_cases(void) {
1319     test_ecdsa_edge_cases();
1320 }
1321
1322 #ifdef ENABLE_OPENSSL_TESTS
1323 EC_KEY *get_openssl_key(const secp256k1_scalar_t *key) {
1324     unsigned char privkey[300];
1325     int privkeylen;
1326     int compr = secp256k1_rand32() & 1;
1327     const unsigned char* pbegin = privkey;
1328     EC_KEY *ec_key = EC_KEY_new_by_curve_name(NID_secp256k1);
1329     CHECK(secp256k1_eckey_privkey_serialize(privkey, &privkeylen, key, compr));
1330     CHECK(d2i_ECPrivateKey(&ec_key, &pbegin, privkeylen));
1331     CHECK(EC_KEY_check_key(ec_key));
1332     return ec_key;
1333 }
1334
1335 void test_ecdsa_openssl(void) {
1336     secp256k1_scalar_t key, msg;
1337     unsigned char message[32];
1338     secp256k1_rand256_test(message);
1339     secp256k1_scalar_set_b32(&msg, message, NULL);
1340     random_scalar_order_test(&key);
1341     secp256k1_gej_t qj;
1342     secp256k1_ecmult_gen(&qj, &key);
1343     secp256k1_ge_t q;
1344     secp256k1_ge_set_gej(&q, &qj);
1345     EC_KEY *ec_key = get_openssl_key(&key);
1346     CHECK(ec_key);
1347     unsigned char signature[80];
1348     unsigned int sigsize = 80;
1349     CHECK(ECDSA_sign(0, message, sizeof(message), signature, &sigsize, ec_key));
1350     secp256k1_ecdsa_sig_t sig;
1351     CHECK(secp256k1_ecdsa_sig_parse(&sig, signature, sigsize));
1352     CHECK(secp256k1_ecdsa_sig_verify(&sig, &q, &msg));
1353     secp256k1_scalar_t one;
1354     secp256k1_scalar_set_int(&one, 1);
1355     secp256k1_scalar_t msg2;
1356     secp256k1_scalar_add(&msg2, &msg, &one);
1357     CHECK(!secp256k1_ecdsa_sig_verify(&sig, &q, &msg2));
1358
1359     random_sign(&sig, &key, &msg, NULL);
1360     int secp_sigsize = 80;
1361     CHECK(secp256k1_ecdsa_sig_serialize(signature, &secp_sigsize, &sig));
1362     CHECK(ECDSA_verify(0, message, sizeof(message), signature, secp_sigsize, ec_key) == 1);
1363
1364     EC_KEY_free(ec_key);
1365 }
1366
1367 void run_ecdsa_openssl(void) {
1368     for (int i=0; i<10*count; i++) {
1369         test_ecdsa_openssl();
1370     }
1371 }
1372 #endif
1373
1374 int main(int argc, char **argv) {
1375     /* find iteration count */
1376     if (argc > 1) {
1377         count = strtol(argv[1], NULL, 0);
1378     }
1379
1380     /* find random seed */
1381     uint64_t seed;
1382     if (argc > 2) {
1383         seed = strtoull(argv[2], NULL, 0);
1384     } else {
1385         FILE *frand = fopen("/dev/urandom", "r");
1386         if (!frand || !fread(&seed, sizeof(seed), 1, frand)) {
1387             seed = time(NULL) * 1337;
1388         }
1389         fclose(frand);
1390     }
1391     secp256k1_rand_seed(seed);
1392
1393     printf("test count = %i\n", count);
1394     printf("random seed = %llu\n", (unsigned long long)seed);
1395
1396     /* initialize */
1397     secp256k1_start(SECP256K1_START_SIGN | SECP256K1_START_VERIFY);
1398
1399     /* initializing a second time shouldn't cause any harm or memory leaks. */
1400     secp256k1_start(SECP256K1_START_SIGN | SECP256K1_START_VERIFY);
1401
1402     /* Likewise, re-running the internal init functions should be harmless. */
1403     secp256k1_fe_start();
1404     secp256k1_ge_start();
1405     secp256k1_scalar_start();
1406     secp256k1_ecdsa_start();
1407
1408 #ifndef USE_NUM_NONE
1409     /* num tests */
1410     run_num_smalltests();
1411 #endif
1412
1413     /* scalar tests */
1414     run_scalar_tests();
1415
1416     /* field tests */
1417     run_field_inv();
1418     run_field_inv_var();
1419     run_field_inv_all_var();
1420     run_field_misc();
1421     run_sqr();
1422     run_sqrt();
1423
1424     /* group tests */
1425     run_ge();
1426
1427     /* ecmult tests */
1428     run_wnaf();
1429     run_point_times_order();
1430     run_ecmult_chain();
1431
1432     /* ecdsa tests */
1433     run_random_pubkeys();
1434     run_ecdsa_sign_verify();
1435     run_ecdsa_end_to_end();
1436     run_ecdsa_edge_cases();
1437 #ifdef ENABLE_OPENSSL_TESTS
1438     run_ecdsa_openssl();
1439 #endif
1440
1441     printf("random run = %llu\n", (unsigned long long)secp256k1_rand32() + ((unsigned long long)secp256k1_rand32() << 32));
1442
1443     /* shutdown */
1444     secp256k1_stop();
1445
1446     /* shutting down twice shouldn't cause any double frees. */
1447     secp256k1_stop();
1448
1449     /* Same for the internal shutdown functions. */
1450     secp256k1_fe_stop();
1451     secp256k1_ge_stop();
1452     secp256k1_scalar_stop();
1453     secp256k1_ecdsa_stop();
1454     return 0;
1455 }