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 "secp256k1.c"
  15 #include "testrand_impl.h"
  16
  17 #ifdef ENABLE_OPENSSL_TESTS
  18 #include "openssl/bn.h"
  19 #include "openssl/ec.h"
  20 #include "openssl/ecdsa.h"
  21 #include "openssl/obj_mac.h"
  22 #endif
  23
  24 static int count = 64;
  25
  26 /***** NUM TESTS *****/
  27
  28 void random_num_negate(secp256k1_num_t *num) {
  29     if (secp256k1_rand32() & 1)
  30         secp256k1_num_negate(num);
  31 }
  32
  33 void random_field_element_test(secp256k1_fe_t *fe) {
  34     do {
  35         unsigned char b32[32];
  36         secp256k1_rand256_test(b32);
  37         secp256k1_num_t num;
  38         secp256k1_num_set_bin(&num, b32, 32);
  39         if (secp256k1_num_cmp(&num, &secp256k1_fe_consts->p) >= 0)
  40             continue;
  41         VERIFY_CHECK(secp256k1_fe_set_b32(fe, b32));
  42         break;
  43     } while(1);
  44 }
  45
  46 void random_field_element_magnitude(secp256k1_fe_t *fe) {
  47     secp256k1_fe_normalize(fe);
  48     int n = secp256k1_rand32() % 4;
  49     for (int i = 0; i < n; i++) {
  50         secp256k1_fe_negate(fe, fe, 1 + 2*i);
  51         secp256k1_fe_negate(fe, fe, 2 + 2*i);
  52     }
  53 }
  54
  55 void random_group_element_test(secp256k1_ge_t *ge) {
  56     secp256k1_fe_t fe;
  57     do {
  58         random_field_element_test(&fe);
  59         if (secp256k1_ge_set_xo(ge, &fe, secp256k1_rand32() & 1))
  60             break;
  61     } while(1);
  62 }
  63
  64 void random_group_element_jacobian_test(secp256k1_gej_t *gej, const secp256k1_ge_t *ge) {
  65     do {
  66         random_field_element_test(&gej->z);
  67         if (!secp256k1_fe_is_zero(&gej->z)) {
  68             break;
  69         }
  70     } while(1);
  71     secp256k1_fe_t z2; secp256k1_fe_sqr(&z2, &gej->z);
  72     secp256k1_fe_t z3; secp256k1_fe_mul(&z3, &z2, &gej->z);
  73     secp256k1_fe_mul(&gej->x, &ge->x, &z2);
  74     secp256k1_fe_mul(&gej->y, &ge->y, &z3);
  75     gej->infinity = ge->infinity;
  76 }
  77
  78 void random_num_order_test(secp256k1_num_t *num) {
  79     do {
  80         unsigned char b32[32];
  81         secp256k1_rand256_test(b32);
  82         secp256k1_num_set_bin(num, b32, 32);
  83         if (secp256k1_num_is_zero(num))
  84             continue;
  85         if (secp256k1_num_cmp(num, &secp256k1_ge_consts->order) >= 0)
  86             continue;
  87         break;
  88     } while(1);
  89 }
  90
  91 void random_scalar_order_test(secp256k1_scalar_t *num) {
  92     do {
  93         unsigned char b32[32];
  94         secp256k1_rand256_test(b32);
  95         int overflow = 0;
  96         secp256k1_scalar_set_b32(num, b32, &overflow);
  97         if (overflow || secp256k1_scalar_is_zero(num))
  98             continue;
  99         break;
 100     } while(1);
 101 }
 102
 103 void random_num_order(secp256k1_num_t *num) {
 104     do {
 105         unsigned char b32[32];
 106         secp256k1_rand256(b32);
 107         secp256k1_num_set_bin(num, b32, 32);
 108         if (secp256k1_num_is_zero(num))
 109             continue;
 110         if (secp256k1_num_cmp(num, &secp256k1_ge_consts->order) >= 0)
 111             continue;
 112         break;
 113     } while(1);
 114 }
 115
 116 void test_num_copy_inc_cmp(void) {
 117     secp256k1_num_t n1,n2;
 118     random_num_order(&n1);
 119     secp256k1_num_copy(&n2, &n1);
 120     CHECK(secp256k1_num_eq(&n1, &n2));
 121     CHECK(secp256k1_num_eq(&n2, &n1));
 122     secp256k1_num_inc(&n2);
 123     CHECK(!secp256k1_num_eq(&n1, &n2));
 124     CHECK(!secp256k1_num_eq(&n2, &n1));
 125 }
 126
 127
 128 void test_num_get_set_hex(void) {
 129     secp256k1_num_t n1,n2;
 130     random_num_order_test(&n1);
 131     char c[64];
 132     secp256k1_num_get_hex(c, 64, &n1);
 133     secp256k1_num_set_hex(&n2, c, 64);
 134     CHECK(secp256k1_num_eq(&n1, &n2));
 135     for (int i=0; i<64; i++) {
 136         /* check whether the lower 4 bits correspond to the last hex character */
 137         int low1 = secp256k1_num_shift(&n1, 4);
 138         int lowh = c[63];
 139         int low2 = ((lowh>>6)*9+(lowh-'0'))&15;
 140         CHECK(low1 == low2);
 141         /* shift bits off the hex representation, and compare */
 142         memmove(c+1, c, 63);
 143         c[0] = '0';
 144         secp256k1_num_set_hex(&n2, c, 64);
 145         CHECK(secp256k1_num_eq(&n1, &n2));
 146     }
 147 }
 148
 149 void test_num_get_set_bin(void) {
 150     secp256k1_num_t n1,n2;
 151     random_num_order_test(&n1);
 152     unsigned char c[32];
 153     secp256k1_num_get_bin(c, 32, &n1);
 154     secp256k1_num_set_bin(&n2, c, 32);
 155     CHECK(secp256k1_num_eq(&n1, &n2));
 156     for (int i=0; i<32; i++) {
 157         /* check whether the lower 8 bits correspond to the last byte */
 158         int low1 = secp256k1_num_shift(&n1, 8);
 159         int low2 = c[31];
 160         CHECK(low1 == low2);
 161         /* shift bits off the byte representation, and compare */
 162         memmove(c+1, c, 31);
 163         c[0] = 0;
 164         secp256k1_num_set_bin(&n2, c, 32);
 165         CHECK(secp256k1_num_eq(&n1, &n2));
 166     }
 167 }
 168
 169 void run_num_int(void) {
 170     secp256k1_num_t n1;
 171     for (int i=-255; i<256; i++) {
 172         unsigned char c1[3] = {};
 173         c1[2] = abs(i);
 174         unsigned char c2[3] = {0x11,0x22,0x33};
 175         secp256k1_num_set_int(&n1, i);
 176         secp256k1_num_get_bin(c2, 3, &n1);
 177         CHECK(memcmp(c1, c2, 3) == 0);
 178     }
 179 }
 180
 181 void test_num_negate(void) {
 182     secp256k1_num_t n1;
 183     secp256k1_num_t n2;
 184     random_num_order_test(&n1); /* n1 = R */
 185     random_num_negate(&n1);
 186     secp256k1_num_copy(&n2, &n1); /* n2 = R */
 187     secp256k1_num_sub(&n1, &n2, &n1); /* n1 = n2-n1 = 0 */
 188     CHECK(secp256k1_num_is_zero(&n1));
 189     secp256k1_num_copy(&n1, &n2); /* n1 = R */
 190     secp256k1_num_negate(&n1); /* n1 = -R */
 191     CHECK(!secp256k1_num_is_zero(&n1));
 192     secp256k1_num_add(&n1, &n2, &n1); /* n1 = n2+n1 = 0 */
 193     CHECK(secp256k1_num_is_zero(&n1));
 194     secp256k1_num_copy(&n1, &n2); /* n1 = R */
 195     secp256k1_num_negate(&n1); /* n1 = -R */
 196     CHECK(secp256k1_num_is_neg(&n1) != secp256k1_num_is_neg(&n2));
 197     secp256k1_num_negate(&n1); /* n1 = R */
 198     CHECK(secp256k1_num_eq(&n1, &n2));
 199 }
 200
 201 void test_num_add_sub(void) {
 202     int r = secp256k1_rand32();
 203     secp256k1_num_t n1;
 204     secp256k1_num_t n2;
 205     random_num_order_test(&n1); /* n1 = R1 */
 206     if (r & 1) {
 207         random_num_negate(&n1);
 208     }
 209     random_num_order_test(&n2); /* n2 = R2 */
 210     if (r & 2) {
 211         random_num_negate(&n2);
 212     }
 213     secp256k1_num_t n1p2, n2p1, n1m2, n2m1;
 214     secp256k1_num_add(&n1p2, &n1, &n2); /* n1p2 = R1 + R2 */
 215     secp256k1_num_add(&n2p1, &n2, &n1); /* n2p1 = R2 + R1 */
 216     secp256k1_num_sub(&n1m2, &n1, &n2); /* n1m2 = R1 - R2 */
 217     secp256k1_num_sub(&n2m1, &n2, &n1); /* n2m1 = R2 - R1 */
 218     CHECK(secp256k1_num_eq(&n1p2, &n2p1));
 219     CHECK(!secp256k1_num_eq(&n1p2, &n1m2));
 220     secp256k1_num_negate(&n2m1); /* n2m1 = -R2 + R1 */
 221     CHECK(secp256k1_num_eq(&n2m1, &n1m2));
 222     CHECK(!secp256k1_num_eq(&n2m1, &n1));
 223     secp256k1_num_add(&n2m1, &n2m1, &n2); /* n2m1 = -R2 + R1 + R2 = R1 */
 224     CHECK(secp256k1_num_eq(&n2m1, &n1));
 225     CHECK(!secp256k1_num_eq(&n2p1, &n1));
 226     secp256k1_num_sub(&n2p1, &n2p1, &n2); /* n2p1 = R2 + R1 - R2 = R1 */
 227     CHECK(secp256k1_num_eq(&n2p1, &n1));
 228 }
 229
 230 void run_num_smalltests(void) {
 231     for (int i=0; i<100*count; i++) {
 232         test_num_copy_inc_cmp();
 233         test_num_get_set_hex();
 234         test_num_get_set_bin();
 235         test_num_negate();
 236         test_num_add_sub();
 237     }
 238     run_num_int();
 239 }
 240
 241 /***** SCALAR TESTS *****/
 242
 243 int secp256k1_scalar_eq(const secp256k1_scalar_t *s1, const secp256k1_scalar_t *s2) {
 244     secp256k1_scalar_t t;
 245     secp256k1_scalar_negate(&t, s2);
 246     secp256k1_scalar_add(&t, &t, s1);
 247     int ret = secp256k1_scalar_is_zero(&t);
 248     return ret;
 249 }
 250
 251 void scalar_test(void) {
 252     unsigned char c[32];
 253
 254     /* Set 's' to a random scalar, with value 'snum'. */
 255     secp256k1_rand256_test(c);
 256     secp256k1_scalar_t s;
 257     secp256k1_scalar_set_b32(&s, c, NULL);
 258     secp256k1_num_t snum;
 259     secp256k1_num_set_bin(&snum, c, 32);
 260     secp256k1_num_mod(&snum, &secp256k1_ge_consts->order);
 261
 262     /* Set 's1' to a random scalar, with value 's1num'. */
 263     secp256k1_rand256_test(c);
 264     secp256k1_scalar_t s1;
 265     secp256k1_scalar_set_b32(&s1, c, NULL);
 266     secp256k1_num_t s1num;
 267     secp256k1_num_set_bin(&s1num, c, 32);
 268     secp256k1_num_mod(&s1num, &secp256k1_ge_consts->order);
 269
 270     /* Set 's2' to a random scalar, with value 'snum2', and byte array representation 'c'. */
 271     secp256k1_rand256_test(c);
 272     secp256k1_scalar_t s2;
 273     int overflow = 0;
 274     secp256k1_scalar_set_b32(&s2, c, &overflow);
 275     secp256k1_num_t s2num;
 276     secp256k1_num_set_bin(&s2num, c, 32);
 277     secp256k1_num_mod(&s2num, &secp256k1_ge_consts->order);
 278
 279     {
 280         /* Test that fetching groups of 4 bits from a scalar and recursing n(i)=16*n(i-1)+p(i) reconstructs it. */
 281         secp256k1_num_t n, t, m;
 282         secp256k1_num_set_int(&n, 0);
 283         secp256k1_num_set_int(&m, 16);
 284         for (int i = 0; i < 256; i += 4) {
 285             secp256k1_num_set_int(&t, secp256k1_scalar_get_bits(&s, 256 - 4 - i, 4));
 286             secp256k1_num_mul(&n, &n, &m);
 287             secp256k1_num_add(&n, &n, &t);
 288         }
 289         CHECK(secp256k1_num_eq(&n, &snum));
 290     }
 291
 292     {
 293         /* Test that get_b32 returns the same as get_bin on the number. */
 294         unsigned char r1[32];
 295         secp256k1_scalar_get_b32(r1, &s2);
 296         unsigned char r2[32];
 297         secp256k1_num_get_bin(r2, 32, &s2num);
 298         CHECK(memcmp(r1, r2, 32) == 0);
 299         /* If no overflow occurred when assigning, it should also be equal to the original byte array. */
 300         CHECK((memcmp(r1, c, 32) == 0) == (overflow == 0));
 301     }
 302
 303     {
 304         /* Test that adding the scalars together is equal to adding their numbers together modulo the order. */
 305         secp256k1_num_t rnum;
 306         secp256k1_num_add(&rnum, &snum, &s2num);
 307         secp256k1_num_mod(&rnum, &secp256k1_ge_consts->order);
 308         secp256k1_scalar_t r;
 309         secp256k1_scalar_add(&r, &s, &s2);
 310         secp256k1_num_t r2num;
 311         secp256k1_scalar_get_num(&r2num, &r);
 312         CHECK(secp256k1_num_eq(&rnum, &r2num));
 313     }
 314
 315     {
 316         /* Test that multipying the scalars is equal to multiplying their numbers modulo the order. */
 317         secp256k1_num_t rnum;
 318         secp256k1_num_mul(&rnum, &snum, &s2num);
 319         secp256k1_num_mod(&rnum, &secp256k1_ge_consts->order);
 320         secp256k1_scalar_t r;
 321         secp256k1_scalar_mul(&r, &s, &s2);
 322         secp256k1_num_t r2num;
 323         secp256k1_scalar_get_num(&r2num, &r);
 324         CHECK(secp256k1_num_eq(&rnum, &r2num));
 325         /* The result can only be zero if at least one of the factors was zero. */
 326         CHECK(secp256k1_scalar_is_zero(&r) == (secp256k1_scalar_is_zero(&s) || secp256k1_scalar_is_zero(&s2)));
 327         /* The results can only be equal to one of the factors if that factor was zero, or the other factor was one. */
 328         CHECK(secp256k1_num_eq(&rnum, &snum) == (secp256k1_scalar_is_zero(&s) || secp256k1_scalar_is_one(&s2)));
 329         CHECK(secp256k1_num_eq(&rnum, &s2num) == (secp256k1_scalar_is_zero(&s2) || secp256k1_scalar_is_one(&s)));
 330     }
 331
 332     {
 333         /* Check that comparison with zero matches comparison with zero on the number. */
 334         CHECK(secp256k1_num_is_zero(&snum) == secp256k1_scalar_is_zero(&s));
 335         /* Check that comparison with the half order is equal to testing for high scalar. */
 336         CHECK(secp256k1_scalar_is_high(&s) == (secp256k1_num_cmp(&snum, &secp256k1_ge_consts->half_order) > 0));
 337         secp256k1_scalar_t neg;
 338         secp256k1_scalar_negate(&neg, &s);
 339         secp256k1_num_t negnum;
 340         secp256k1_num_sub(&negnum, &secp256k1_ge_consts->order, &snum);
 341         secp256k1_num_mod(&negnum, &secp256k1_ge_consts->order);
 342         /* Check that comparison with the half order is equal to testing for high scalar after negation. */
 343         CHECK(secp256k1_scalar_is_high(&neg) == (secp256k1_num_cmp(&negnum, &secp256k1_ge_consts->half_order) > 0));
 344         /* Negating should change the high property, unless the value was already zero. */
 345         CHECK((secp256k1_scalar_is_high(&s) == secp256k1_scalar_is_high(&neg)) == secp256k1_scalar_is_zero(&s));
 346         secp256k1_num_t negnum2;
 347         secp256k1_scalar_get_num(&negnum2, &neg);
 348         /* Negating a scalar should be equal to (order - n) mod order on the number. */
 349         CHECK(secp256k1_num_eq(&negnum, &negnum2));
 350         secp256k1_scalar_add(&neg, &neg, &s);
 351         /* Adding a number to its negation should result in zero. */
 352         CHECK(secp256k1_scalar_is_zero(&neg));
 353         secp256k1_scalar_negate(&neg, &neg);
 354         /* Negating zero should still result in zero. */
 355         CHECK(secp256k1_scalar_is_zero(&neg));
 356     }
 357
 358     {
 359         /* Test that scalar inverses are equal to the inverse of their number modulo the order. */
 360         if (!secp256k1_scalar_is_zero(&s)) {
 361             secp256k1_scalar_t inv;
 362             secp256k1_scalar_inverse(&inv, &s);
 363             secp256k1_num_t invnum;
 364             secp256k1_num_mod_inverse(&invnum, &snum, &secp256k1_ge_consts->order);
 365             secp256k1_num_t invnum2;
 366             secp256k1_scalar_get_num(&invnum2, &inv);
 367             CHECK(secp256k1_num_eq(&invnum, &invnum2));
 368             secp256k1_scalar_mul(&inv, &inv, &s);
 369             /* Multiplying a scalar with its inverse must result in one. */
 370             CHECK(secp256k1_scalar_is_one(&inv));
 371             secp256k1_scalar_inverse(&inv, &inv);
 372             /* Inverting one must result in one. */
 373             CHECK(secp256k1_scalar_is_one(&inv));
 374         }
 375     }
 376
 377     {
 378         /* Test commutativity of add. */
 379         secp256k1_scalar_t r1, r2;
 380         secp256k1_scalar_add(&r1, &s1, &s2);
 381         secp256k1_scalar_add(&r2, &s2, &s1);
 382         CHECK(secp256k1_scalar_eq(&r1, &r2));
 383     }
 384
 385     {
 386         /* Test commutativity of mul. */
 387         secp256k1_scalar_t r1, r2;
 388         secp256k1_scalar_mul(&r1, &s1, &s2);
 389         secp256k1_scalar_mul(&r2, &s2, &s1);
 390         CHECK(secp256k1_scalar_eq(&r1, &r2));
 391     }
 392
 393     {
 394         /* Test associativity of add. */
 395         secp256k1_scalar_t r1, r2;
 396         secp256k1_scalar_add(&r1, &s1, &s2);
 397         secp256k1_scalar_add(&r1, &r1, &s);
 398         secp256k1_scalar_add(&r2, &s2, &s);
 399         secp256k1_scalar_add(&r2, &s1, &r2);
 400         CHECK(secp256k1_scalar_eq(&r1, &r2));
 401     }
 402
 403     {
 404         /* Test associativity of mul. */
 405         secp256k1_scalar_t r1, r2;
 406         secp256k1_scalar_mul(&r1, &s1, &s2);
 407         secp256k1_scalar_mul(&r1, &r1, &s);
 408         secp256k1_scalar_mul(&r2, &s2, &s);
 409         secp256k1_scalar_mul(&r2, &s1, &r2);
 410         CHECK(secp256k1_scalar_eq(&r1, &r2));
 411     }
 412
 413     {
 414         /* Test distributitivity of mul over add. */
 415         secp256k1_scalar_t r1, r2, t;
 416         secp256k1_scalar_add(&r1, &s1, &s2);
 417         secp256k1_scalar_mul(&r1, &r1, &s);
 418         secp256k1_scalar_mul(&r2, &s1, &s);
 419         secp256k1_scalar_mul(&t, &s2, &s);
 420         secp256k1_scalar_add(&r2, &r2, &t);
 421         CHECK(secp256k1_scalar_eq(&r1, &r2));
 422     }
 423
 424     {
 425         /* Test square. */
 426         secp256k1_scalar_t r1, r2;
 427         secp256k1_scalar_sqr(&r1, &s1);
 428         secp256k1_scalar_mul(&r2, &s1, &s1);
 429         CHECK(secp256k1_scalar_eq(&r1, &r2));
 430     }
 431 }
 432
 433 void run_scalar_tests(void) {
 434     for (int i = 0; i < 128 * count; i++) {
 435         scalar_test();
 436     }
 437 }
 438
 439 /***** FIELD TESTS *****/
 440
 441 void random_fe(secp256k1_fe_t *x) {
 442     unsigned char bin[32];
 443     do {
 444         secp256k1_rand256(bin);
 445         if (secp256k1_fe_set_b32(x, bin)) {
 446             return;
 447         }
 448     } while(1);
 449 }
 450
 451 void random_fe_non_zero(secp256k1_fe_t *nz) {
 452     int tries = 10;
 453     while (--tries >= 0) {
 454         random_fe(nz);
 455         secp256k1_fe_normalize(nz);
 456         if (!secp256k1_fe_is_zero(nz))
 457             break;
 458     }
 459     /* Infinitesimal probability of spurious failure here */
 460     CHECK(tries >= 0);
 461 }
 462
 463 void random_fe_non_square(secp256k1_fe_t *ns) {
 464     random_fe_non_zero(ns);
 465     secp256k1_fe_t r;
 466     if (secp256k1_fe_sqrt(&r, ns)) {
 467         secp256k1_fe_negate(ns, ns, 1);
 468     }
 469 }
 470
 471 int check_fe_equal(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
 472     secp256k1_fe_t an = *a; secp256k1_fe_normalize(&an);
 473     secp256k1_fe_t bn = *b; secp256k1_fe_normalize(&bn);
 474     return secp256k1_fe_equal(&an, &bn);
 475 }
 476
 477 int check_fe_inverse(const secp256k1_fe_t *a, const secp256k1_fe_t *ai) {
 478     secp256k1_fe_t x; secp256k1_fe_mul(&x, a, ai);
 479     secp256k1_fe_t one; secp256k1_fe_set_int(&one, 1);
 480     return check_fe_equal(&x, &one);
 481 }
 482
 483 void run_field_inv(void) {
 484     secp256k1_fe_t x, xi, xii;
 485     for (int i=0; i<10*count; i++) {
 486         random_fe_non_zero(&x);
 487         secp256k1_fe_inv(&xi, &x);
 488         CHECK(check_fe_inverse(&x, &xi));
 489         secp256k1_fe_inv(&xii, &xi);
 490         CHECK(check_fe_equal(&x, &xii));
 491     }
 492 }
 493
 494 void run_field_inv_var(void) {
 495     secp256k1_fe_t x, xi, xii;
 496     for (int i=0; i<10*count; i++) {
 497         random_fe_non_zero(&x);
 498         secp256k1_fe_inv_var(&xi, &x);
 499         CHECK(check_fe_inverse(&x, &xi));
 500         secp256k1_fe_inv_var(&xii, &xi);
 501         CHECK(check_fe_equal(&x, &xii));
 502     }
 503 }
 504
 505 void run_field_inv_all(void) {
 506     secp256k1_fe_t x[16], xi[16], xii[16];
 507     /* Check it's safe to call for 0 elements */
 508     secp256k1_fe_inv_all(0, xi, x);
 509     for (int i=0; i<count; i++) {
 510         size_t len = (secp256k1_rand32() & 15) + 1;
 511         for (size_t j=0; j<len; j++)
 512             random_fe_non_zero(&x[j]);
 513         secp256k1_fe_inv_all(len, xi, x);
 514         for (size_t j=0; j<len; j++)
 515             CHECK(check_fe_inverse(&x[j], &xi[j]));
 516         secp256k1_fe_inv_all(len, xii, xi);
 517         for (size_t j=0; j<len; j++)
 518             CHECK(check_fe_equal(&x[j], &xii[j]));
 519     }
 520 }
 521
 522 void run_field_inv_all_var(void) {
 523     secp256k1_fe_t x[16], xi[16], xii[16];
 524     /* Check it's safe to call for 0 elements */
 525     secp256k1_fe_inv_all_var(0, xi, x);
 526     for (int i=0; i<count; i++) {
 527         size_t len = (secp256k1_rand32() & 15) + 1;
 528         for (size_t j=0; j<len; j++)
 529             random_fe_non_zero(&x[j]);
 530         secp256k1_fe_inv_all_var(len, xi, x);
 531         for (size_t j=0; j<len; j++)
 532             CHECK(check_fe_inverse(&x[j], &xi[j]));
 533         secp256k1_fe_inv_all_var(len, xii, xi);
 534         for (size_t j=0; j<len; j++)
 535             CHECK(check_fe_equal(&x[j], &xii[j]));
 536     }
 537 }
 538
 539 void run_sqr(void) {
 540     secp256k1_fe_t x, s;
 541
 542     {
 543         secp256k1_fe_set_int(&x, 1);
 544         secp256k1_fe_negate(&x, &x, 1);
 545
 546         for (int i=1; i<=512; ++i) {
 547             secp256k1_fe_mul_int(&x, 2);
 548             secp256k1_fe_normalize(&x);
 549             secp256k1_fe_sqr(&s, &x);
 550         }
 551     }
 552 }
 553
 554 void test_sqrt(const secp256k1_fe_t *a, const secp256k1_fe_t *k) {
 555     secp256k1_fe_t r1, r2;
 556     int v = secp256k1_fe_sqrt(&r1, a);
 557     CHECK((v == 0) == (k == NULL));
 558
 559     if (k != NULL) {
 560         /* Check that the returned root is +/- the given known answer */
 561         secp256k1_fe_negate(&r2, &r1, 1);
 562         secp256k1_fe_add(&r1, k); secp256k1_fe_add(&r2, k);
 563         secp256k1_fe_normalize(&r1); secp256k1_fe_normalize(&r2);
 564         CHECK(secp256k1_fe_is_zero(&r1) || secp256k1_fe_is_zero(&r2));
 565     }
 566 }
 567
 568 void run_sqrt(void) {
 569     secp256k1_fe_t ns, x, s, t;
 570
 571     /* Check sqrt(0) is 0 */
 572     secp256k1_fe_set_int(&x, 0);
 573     secp256k1_fe_sqr(&s, &x);
 574     test_sqrt(&s, &x);
 575
 576     /* Check sqrt of small squares (and their negatives) */
 577     for (int i=1; i<=100; i++) {
 578         secp256k1_fe_set_int(&x, i);
 579         secp256k1_fe_sqr(&s, &x);
 580         test_sqrt(&s, &x);
 581         secp256k1_fe_negate(&t, &s, 1);
 582         test_sqrt(&t, NULL);
 583     }
 584
 585     /* Consistency checks for large random values */
 586     for (int i=0; i<10; i++) {
 587         random_fe_non_square(&ns);
 588         for (int j=0; j<count; j++) {
 589             random_fe(&x);
 590             secp256k1_fe_sqr(&s, &x);
 591             test_sqrt(&s, &x);
 592             secp256k1_fe_negate(&t, &s, 1);
 593             test_sqrt(&t, NULL);
 594             secp256k1_fe_mul(&t, &s, &ns);
 595             test_sqrt(&t, NULL);
 596         }
 597     }
 598 }
 599
 600 /***** GROUP TESTS *****/
 601
 602 int ge_equals_ge(const secp256k1_ge_t *a, const secp256k1_ge_t *b) {
 603     if (a->infinity && b->infinity)
 604         return 1;
 605     return check_fe_equal(&a->x, &b->x) && check_fe_equal(&a->y, &b->y);
 606 }
 607
 608 void ge_equals_gej(const secp256k1_ge_t *a, const secp256k1_gej_t *b) {
 609     secp256k1_ge_t bb;
 610     secp256k1_gej_t bj = *b;
 611     secp256k1_ge_set_gej_var(&bb, &bj);
 612     CHECK(ge_equals_ge(a, &bb));
 613 }
 614
 615 void gej_equals_gej(const secp256k1_gej_t *a, const secp256k1_gej_t *b) {
 616     secp256k1_ge_t aa, bb;
 617     secp256k1_gej_t aj = *a, bj = *b;
 618     secp256k1_ge_set_gej_var(&aa, &aj);
 619     secp256k1_ge_set_gej_var(&bb, &bj);
 620     CHECK(ge_equals_ge(&aa, &bb));
 621 }
 622
 623 void test_ge(void) {
 624     secp256k1_ge_t a, b, i, n;
 625     random_group_element_test(&a);
 626     random_group_element_test(&b);
 627     n = a;
 628     secp256k1_fe_normalize(&a.y);
 629     secp256k1_fe_negate(&n.y, &a.y, 1);
 630     secp256k1_ge_set_infinity(&i);
 631     random_field_element_magnitude(&a.x);
 632     random_field_element_magnitude(&a.y);
 633     random_field_element_magnitude(&b.x);
 634     random_field_element_magnitude(&b.y);
 635     random_field_element_magnitude(&n.x);
 636     random_field_element_magnitude(&n.y);
 637
 638     secp256k1_gej_t aj, bj, ij, nj;
 639     random_group_element_jacobian_test(&aj, &a);
 640     random_group_element_jacobian_test(&bj, &b);
 641     secp256k1_gej_set_infinity(&ij);
 642     random_group_element_jacobian_test(&nj, &n);
 643     random_field_element_magnitude(&aj.x);
 644     random_field_element_magnitude(&aj.y);
 645     random_field_element_magnitude(&aj.z);
 646     random_field_element_magnitude(&bj.x);
 647     random_field_element_magnitude(&bj.y);
 648     random_field_element_magnitude(&bj.z);
 649     random_field_element_magnitude(&nj.x);
 650     random_field_element_magnitude(&nj.y);
 651     random_field_element_magnitude(&nj.z);
 652
 653     /* gej + gej adds */
 654     secp256k1_gej_t aaj; secp256k1_gej_add_var(&aaj, &aj, &aj);
 655     secp256k1_gej_t abj; secp256k1_gej_add_var(&abj, &aj, &bj);
 656     secp256k1_gej_t aij; secp256k1_gej_add_var(&aij, &aj, &ij);
 657     secp256k1_gej_t anj; secp256k1_gej_add_var(&anj, &aj, &nj);
 658     secp256k1_gej_t iaj; secp256k1_gej_add_var(&iaj, &ij, &aj);
 659     secp256k1_gej_t iij; secp256k1_gej_add_var(&iij, &ij, &ij);
 660
 661     /* gej + ge adds */
 662     secp256k1_gej_t aa; secp256k1_gej_add_ge_var(&aa, &aj, &a);
 663     secp256k1_gej_t ab; secp256k1_gej_add_ge_var(&ab, &aj, &b);
 664     secp256k1_gej_t ai; secp256k1_gej_add_ge_var(&ai, &aj, &i);
 665     secp256k1_gej_t an; secp256k1_gej_add_ge_var(&an, &aj, &n);
 666     secp256k1_gej_t ia; secp256k1_gej_add_ge_var(&ia, &ij, &a);
 667     secp256k1_gej_t ii; secp256k1_gej_add_ge_var(&ii, &ij, &i);
 668
 669     /* const gej + ge adds */
 670     secp256k1_gej_t aac; secp256k1_gej_add_ge(&aac, &aj, &a);
 671     secp256k1_gej_t abc; secp256k1_gej_add_ge(&abc, &aj, &b);
 672     secp256k1_gej_t anc; secp256k1_gej_add_ge(&anc, &aj, &n);
 673     secp256k1_gej_t iac; secp256k1_gej_add_ge(&iac, &ij, &a);
 674
 675     CHECK(secp256k1_gej_is_infinity(&an));
 676     CHECK(secp256k1_gej_is_infinity(&anj));
 677     CHECK(secp256k1_gej_is_infinity(&anc));
 678     gej_equals_gej(&aa, &aaj);
 679     gej_equals_gej(&aa, &aac);
 680     gej_equals_gej(&ab, &abj);
 681     gej_equals_gej(&ab, &abc);
 682     gej_equals_gej(&an, &anj);
 683     gej_equals_gej(&an, &anc);
 684     gej_equals_gej(&ia, &iaj);
 685     gej_equals_gej(&ai, &aij);
 686     gej_equals_gej(&ii, &iij);
 687     ge_equals_gej(&a, &ai);
 688     ge_equals_gej(&a, &ai);
 689     ge_equals_gej(&a, &iaj);
 690     ge_equals_gej(&a, &iaj);
 691     ge_equals_gej(&a, &iac);
 692 }
 693
 694 void run_ge(void) {
 695     for (int i = 0; i < 2000*count; i++) {
 696         test_ge();
 697     }
 698 }
 699
 700 /***** ECMULT TESTS *****/
 701
 702 void run_ecmult_chain(void) {
 703     /* random starting point A (on the curve) */
 704     secp256k1_fe_t ax; VERIFY_CHECK(secp256k1_fe_set_hex(&ax, "8b30bbe9ae2a990696b22f670709dff3727fd8bc04d3362c6c7bf458e2846004", 64));
 705     secp256k1_fe_t ay; VERIFY_CHECK(secp256k1_fe_set_hex(&ay, "a357ae915c4a65281309edf20504740f0eb3343990216b4f81063cb65f2f7e0f", 64));
 706     secp256k1_gej_t a; secp256k1_gej_set_xy(&a, &ax, &ay);
 707     /* two random initial factors xn and gn */
 708     secp256k1_num_t xn;
 709     secp256k1_num_set_hex(&xn, "84cc5452f7fde1edb4d38a8ce9b1b84ccef31f146e569be9705d357a42985407", 64);
 710     secp256k1_num_t gn;
 711     secp256k1_num_set_hex(&gn, "a1e58d22553dcd42b23980625d4c57a96e9323d42b3152e5ca2c3990edc7c9de", 64);
 712     /* two small multipliers to be applied to xn and gn in every iteration: */
 713     secp256k1_num_t xf;
 714     secp256k1_num_set_hex(&xf, "1337", 4);
 715     secp256k1_num_t gf;
 716     secp256k1_num_set_hex(&gf, "7113", 4);
 717     /* accumulators with the resulting coefficients to A and G */
 718     secp256k1_num_t ae;
 719     secp256k1_num_set_int(&ae, 1);
 720     secp256k1_num_t ge;
 721     secp256k1_num_set_int(&ge, 0);
 722     /* the point being computed */
 723     secp256k1_gej_t x = a;
 724     const secp256k1_num_t *order = &secp256k1_ge_consts->order;
 725     for (int i=0; i<200*count; i++) {
 726         /* in each iteration, compute X = xn*X + gn*G; */
 727         secp256k1_ecmult(&x, &x, &xn, &gn);
 728         /* also compute ae and ge: the actual accumulated factors for A and G */
 729         /* if X was (ae*A+ge*G), xn*X + gn*G results in (xn*ae*A + (xn*ge+gn)*G) */
 730         secp256k1_num_mod_mul(&ae, &ae, &xn, order);
 731         secp256k1_num_mod_mul(&ge, &ge, &xn, order);
 732         secp256k1_num_add(&ge, &ge, &gn);
 733         secp256k1_num_mod(&ge, order);
 734         /* modify xn and gn */
 735         secp256k1_num_mod_mul(&xn, &xn, &xf, order);
 736         secp256k1_num_mod_mul(&gn, &gn, &gf, order);
 737
 738         /* verify */
 739         if (i == 19999) {
 740             char res[132]; int resl = 132;
 741             secp256k1_gej_get_hex(res, &resl, &x);
 742             CHECK(strcmp(res, "(D6E96687F9B10D092A6F35439D86CEBEA4535D0D409F53586440BD74B933E830,B95CBCA2C77DA786539BE8FD53354D2D3B4F566AE658045407ED6015EE1B2A88)") == 0);
 743         }
 744     }
 745     /* redo the computation, but directly with the resulting ae and ge coefficients: */
 746     secp256k1_gej_t x2; secp256k1_ecmult(&x2, &a, &ae, &ge);
 747     char res[132]; int resl = 132;
 748     char res2[132]; int resl2 = 132;
 749     secp256k1_gej_get_hex(res, &resl, &x);
 750     secp256k1_gej_get_hex(res2, &resl2, &x2);
 751     CHECK(strcmp(res, res2) == 0);
 752     CHECK(strlen(res) == 131);
 753 }
 754
 755 void test_point_times_order(const secp256k1_gej_t *point) {
 756     /* multiplying a point by the order results in O */
 757     const secp256k1_num_t *order = &secp256k1_ge_consts->order;
 758     secp256k1_num_t zero;
 759     secp256k1_num_set_int(&zero, 0);
 760     secp256k1_gej_t res;
 761     secp256k1_ecmult(&res, point, order, order); /* calc res = order * point + order * G; */
 762     CHECK(secp256k1_gej_is_infinity(&res));
 763 }
 764
 765 void run_point_times_order(void) {
 766     secp256k1_fe_t x; VERIFY_CHECK(secp256k1_fe_set_hex(&x, "02", 2));
 767     for (int i=0; i<500; i++) {
 768         secp256k1_ge_t p;
 769         if (secp256k1_ge_set_xo(&p, &x, 1)) {
 770             CHECK(secp256k1_ge_is_valid(&p));
 771             secp256k1_gej_t j;
 772             secp256k1_gej_set_ge(&j, &p);
 773             CHECK(secp256k1_gej_is_valid(&j));
 774             test_point_times_order(&j);
 775         }
 776         secp256k1_fe_sqr(&x, &x);
 777     }
 778     char c[65]; int cl=65;
 779     secp256k1_fe_get_hex(c, &cl, &x);
 780     CHECK(strcmp(c, "7603CB59B0EF6C63FE6084792A0C378CDB3233A80F8A9A09A877DEAD31B38C45") == 0);
 781 }
 782
 783 void test_wnaf(const secp256k1_num_t *number, int w) {
 784     secp256k1_num_t x, two, t;
 785     secp256k1_num_set_int(&x, 0);
 786     secp256k1_num_set_int(&two, 2);
 787     int wnaf[257];
 788     int bits = secp256k1_ecmult_wnaf(wnaf, number, w);
 789     int zeroes = -1;
 790     for (int i=bits-1; i>=0; i--) {
 791         secp256k1_num_mul(&x, &x, &two);
 792         int v = wnaf[i];
 793         if (v) {
 794             CHECK(zeroes == -1 || zeroes >= w-1); /* check that distance between non-zero elements is at least w-1 */
 795             zeroes=0;
 796             CHECK((v & 1) == 1); /* check non-zero elements are odd */
 797             CHECK(v <= (1 << (w-1)) - 1); /* check range below */
 798             CHECK(v >= -(1 << (w-1)) - 1); /* check range above */
 799         } else {
 800             CHECK(zeroes != -1); /* check that no unnecessary zero padding exists */
 801             zeroes++;
 802         }
 803         secp256k1_num_set_int(&t, v);
 804         secp256k1_num_add(&x, &x, &t);
 805     }
 806     CHECK(secp256k1_num_eq(&x, number)); /* check that wnaf represents number */
 807 }
 808
 809 void run_wnaf(void) {
 810     secp256k1_num_t n;
 811     for (int i=0; i<count; i++) {
 812         random_num_order(&n);
 813         if (i % 1)
 814             secp256k1_num_negate(&n);
 815         test_wnaf(&n, 4+(i%10));
 816     }
 817 }
 818
 819 void random_sign(secp256k1_ecdsa_sig_t *sig, const secp256k1_scalar_t *key, const secp256k1_scalar_t *msg, int *recid) {
 820     secp256k1_scalar_t nonce;
 821     do {
 822         random_scalar_order_test(&nonce);
 823     } while(!secp256k1_ecdsa_sig_sign(sig, key, msg, &nonce, recid));
 824 }
 825
 826 void test_ecdsa_sign_verify(void) {
 827     secp256k1_scalar_t msg, key;
 828     random_scalar_order_test(&msg);
 829     random_scalar_order_test(&key);
 830     secp256k1_gej_t pubj; secp256k1_ecmult_gen(&pubj, &key);
 831     secp256k1_ge_t pub; secp256k1_ge_set_gej(&pub, &pubj);
 832     secp256k1_ecdsa_sig_t sig;
 833     random_sign(&sig, &key, &msg, NULL);
 834     secp256k1_num_t msg_num;
 835     secp256k1_scalar_get_num(&msg_num, &msg);
 836     CHECK(secp256k1_ecdsa_sig_verify(&sig, &pub, &msg_num));
 837     secp256k1_num_inc(&msg_num);
 838     CHECK(!secp256k1_ecdsa_sig_verify(&sig, &pub, &msg_num));
 839 }
 840
 841 void run_ecdsa_sign_verify(void) {
 842     for (int i=0; i<10*count; i++) {
 843         test_ecdsa_sign_verify();
 844     }
 845 }
 846
 847 void test_ecdsa_end_to_end(void) {
 848     unsigned char privkey[32];
 849     unsigned char message[32];
 850
 851     /* Generate a random key and message. */
 852     {
 853         secp256k1_num_t msg, key;
 854         random_num_order_test(&msg);
 855         random_num_order_test(&key);
 856         secp256k1_num_get_bin(privkey, 32, &key);
 857         secp256k1_num_get_bin(message, 32, &msg);
 858     }
 859
 860     /* Construct and verify corresponding public key. */
 861     CHECK(secp256k1_ec_seckey_verify(privkey) == 1);
 862     unsigned char pubkey[65]; int pubkeylen = 65;
 863     CHECK(secp256k1_ec_pubkey_create(pubkey, &pubkeylen, privkey, secp256k1_rand32() % 2) == 1);
 864     CHECK(secp256k1_ec_pubkey_verify(pubkey, pubkeylen));
 865
 866     /* Verify private key import and export. */
 867     unsigned char seckey[300]; int seckeylen = 300;
 868     CHECK(secp256k1_ec_privkey_export(privkey, seckey, &seckeylen, secp256k1_rand32() % 2) == 1);
 869     unsigned char privkey2[32];
 870     CHECK(secp256k1_ec_privkey_import(privkey2, seckey, seckeylen) == 1);
 871     CHECK(memcmp(privkey, privkey2, 32) == 0);
 872
 873     /* Optionally tweak the keys using addition. */
 874     if (secp256k1_rand32() % 3 == 0) {
 875         unsigned char rnd[32];
 876         secp256k1_rand256_test(rnd);
 877         int ret1 = secp256k1_ec_privkey_tweak_add(privkey, rnd);
 878         int ret2 = secp256k1_ec_pubkey_tweak_add(pubkey, pubkeylen, rnd);
 879         CHECK(ret1 == ret2);
 880         if (ret1 == 0) return;
 881         unsigned char pubkey2[65]; int pubkeylen2 = 65;
 882         CHECK(secp256k1_ec_pubkey_create(pubkey2, &pubkeylen2, privkey, pubkeylen == 33) == 1);
 883         CHECK(memcmp(pubkey, pubkey2, pubkeylen) == 0);
 884     }
 885
 886     /* Optionally tweak the keys using multiplication. */
 887     if (secp256k1_rand32() % 3 == 0) {
 888         unsigned char rnd[32];
 889         secp256k1_rand256_test(rnd);
 890         int ret1 = secp256k1_ec_privkey_tweak_mul(privkey, rnd);
 891         int ret2 = secp256k1_ec_pubkey_tweak_mul(pubkey, pubkeylen, rnd);
 892         CHECK(ret1 == ret2);
 893         if (ret1 == 0) return;
 894         unsigned char pubkey2[65]; int pubkeylen2 = 65;
 895         CHECK(secp256k1_ec_pubkey_create(pubkey2, &pubkeylen2, privkey, pubkeylen == 33) == 1);
 896         CHECK(memcmp(pubkey, pubkey2, pubkeylen) == 0);
 897     }
 898
 899     /* Sign. */
 900     unsigned char signature[72]; int signaturelen = 72;
 901     while(1) {
 902         unsigned char rnd[32];
 903         secp256k1_rand256_test(rnd);
 904         if (secp256k1_ecdsa_sign(message, 32, signature, &signaturelen, privkey, rnd) == 1) {
 905             break;
 906         }
 907     }
 908     /* Verify. */
 909     CHECK(secp256k1_ecdsa_verify(message, 32, signature, signaturelen, pubkey, pubkeylen) == 1);
 910     /* Destroy signature and verify again. */
 911     signature[signaturelen - 1 - secp256k1_rand32() % 20] += 1 + (secp256k1_rand32() % 255);
 912     CHECK(secp256k1_ecdsa_verify(message, 32, signature, signaturelen, pubkey, pubkeylen) != 1);
 913
 914     /* Compact sign. */
 915     unsigned char csignature[64]; int recid = 0;
 916     while(1) {
 917         unsigned char rnd[32];
 918         secp256k1_rand256_test(rnd);
 919         if (secp256k1_ecdsa_sign_compact(message, 32, csignature, privkey, rnd, &recid) == 1) {
 920             break;
 921         }
 922     }
 923     /* Recover. */
 924     unsigned char recpubkey[65]; int recpubkeylen = 0;
 925     CHECK(secp256k1_ecdsa_recover_compact(message, 32, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) == 1);
 926     CHECK(recpubkeylen == pubkeylen);
 927     CHECK(memcmp(pubkey, recpubkey, pubkeylen) == 0);
 928     /* Destroy signature and verify again. */
 929     csignature[secp256k1_rand32() % 64] += 1 + (secp256k1_rand32() % 255);
 930     CHECK(secp256k1_ecdsa_recover_compact(message, 32, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) != 1 ||
 931           memcmp(pubkey, recpubkey, pubkeylen) != 0);
 932     CHECK(recpubkeylen == pubkeylen);
 933
 934 }
 935
 936 void run_ecdsa_end_to_end(void) {
 937     for (int i=0; i<64*count; i++) {
 938         test_ecdsa_end_to_end();
 939     }
 940 }
 941
 942 /* Tests several edge cases. */
 943 void test_ecdsa_edge_cases(void) {
 944     const unsigned char msg32[32] = {
 945         'T', 'h', 'i', 's', ' ', 'i', 's', ' ',
 946         'a', ' ', 'v', 'e', 'r', 'y', ' ', 's',
 947         'e', 'c', 'r', 'e', 't', ' ', 'm', 'e',
 948         's', 's', 'a', 'g', 'e', '.', '.', '.'
 949     };
 950     const unsigned char sig64[64] = {
 951         /* Generated by signing the above message with nonce 'This is the nonce we will use...'
 952          * and secret key 0 (which is not valid), resulting in recid 0. */
 953         0x67, 0xCB, 0x28, 0x5F, 0x9C, 0xD1, 0x94, 0xE8,
 954         0x40, 0xD6, 0x29, 0x39, 0x7A, 0xF5, 0x56, 0x96,
 955         0x62, 0xFD, 0xE4, 0x46, 0x49, 0x99, 0x59, 0x63,
 956         0x17, 0x9A, 0x7D, 0xD1, 0x7B, 0xD2, 0x35, 0x32,
 957         0x4B, 0x1B, 0x7D, 0xF3, 0x4C, 0xE1, 0xF6, 0x8E,
 958         0x69, 0x4F, 0xF6, 0xF1, 0x1A, 0xC7, 0x51, 0xDD,
 959         0x7D, 0xD7, 0x3E, 0x38, 0x7E, 0xE4, 0xFC, 0x86,
 960         0x6E, 0x1B, 0xE8, 0xEC, 0xC7, 0xDD, 0x95, 0x57
 961     };
 962     unsigned char pubkey[65];
 963     int pubkeylen = 65;
 964     CHECK(!secp256k1_ecdsa_recover_compact(msg32, 32, sig64, pubkey, &pubkeylen, 0, 0));
 965     CHECK(secp256k1_ecdsa_recover_compact(msg32, 32, sig64, pubkey, &pubkeylen, 0, 1));
 966     CHECK(!secp256k1_ecdsa_recover_compact(msg32, 32, sig64, pubkey, &pubkeylen, 0, 2));
 967     CHECK(!secp256k1_ecdsa_recover_compact(msg32, 32, sig64, pubkey, &pubkeylen, 0, 3));
 968
 969     /* signature (r,s) = (4,4), which can be recovered with all 4 recids. */
 970     const unsigned char sigb64[64] = {
 971         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 972         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 973         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 974         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
 975         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 976         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 977         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 978         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
 979     };
 980     unsigned char pubkeyb[33];
 981     int pubkeyblen = 33;
 982     for (int recid = 0; recid < 4; recid++) {
 983         unsigned char sigbder[8] = {0x30, 0x06, 0x02, 0x01, 0x04, 0x02, 0x01, 0x04};
 984         CHECK(secp256k1_ecdsa_recover_compact(msg32, 32, sigb64, pubkeyb, &pubkeyblen, 1, recid));
 985         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) == 1);
 986         /* Damage signature. */
 987         sigbder[7]++;
 988         CHECK(secp256k1_ecdsa_verify(msg32, 32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) == 0);
 989     }
 990 }
 991
 992 void run_ecdsa_edge_cases(void) {
 993     test_ecdsa_edge_cases();
 994 }
 995
 996 #ifdef ENABLE_OPENSSL_TESTS
 997 EC_KEY *get_openssl_key(const secp256k1_scalar_t *key) {
 998     unsigned char privkey[300];
 999     int privkeylen;
1000     int compr = secp256k1_rand32() & 1;
1001     const unsigned char* pbegin = privkey;
1002     EC_KEY *ec_key = EC_KEY_new_by_curve_name(NID_secp256k1);
1003     CHECK(secp256k1_eckey_privkey_serialize(privkey, &privkeylen, key, compr));
1004     CHECK(d2i_ECPrivateKey(&ec_key, &pbegin, privkeylen));
1005     CHECK(EC_KEY_check_key(ec_key));
1006     return ec_key;
1007 }
1008
1009 void test_ecdsa_openssl(void) {
1010     secp256k1_scalar_t key, msg;
1011     unsigned char message[32];
1012     secp256k1_rand256_test(message);
1013     secp256k1_scalar_set_b32(&msg, message, NULL);
1014     random_scalar_order_test(&key);
1015     secp256k1_gej_t qj;
1016     secp256k1_ecmult_gen(&qj, &key);
1017     secp256k1_ge_t q;
1018     secp256k1_ge_set_gej(&q, &qj);
1019     EC_KEY *ec_key = get_openssl_key(&key);
1020     CHECK(ec_key);
1021     unsigned char signature[80];
1022     unsigned int sigsize = 80;
1023     CHECK(ECDSA_sign(0, message, sizeof(message), signature, &sigsize, ec_key));
1024     secp256k1_ecdsa_sig_t sig;
1025     CHECK(secp256k1_ecdsa_sig_parse(&sig, signature, sigsize));
1026     secp256k1_num_t msg_num;
1027     secp256k1_scalar_get_num(&msg_num, &msg);
1028     CHECK(secp256k1_ecdsa_sig_verify(&sig, &q, &msg_num));
1029     secp256k1_num_inc(&sig.r);
1030     CHECK(!secp256k1_ecdsa_sig_verify(&sig, &q, &msg_num));
1031
1032     random_sign(&sig, &key, &msg, NULL);
1033     int secp_sigsize = 80;
1034     CHECK(secp256k1_ecdsa_sig_serialize(signature, &secp_sigsize, &sig));
1035     CHECK(ECDSA_verify(0, message, sizeof(message), signature, secp_sigsize, ec_key) == 1);
1036
1037     EC_KEY_free(ec_key);
1038 }
1039
1040 void run_ecdsa_openssl(void) {
1041     for (int i=0; i<10*count; i++) {
1042         test_ecdsa_openssl();
1043     }
1044 }
1045 #endif
1046
1047 int main(int argc, char **argv) {
1048     /* find iteration count */
1049     if (argc > 1) {
1050         count = strtol(argv[1], NULL, 0);
1051     }
1052
1053     /* find random seed */
1054     uint64_t seed;
1055     if (argc > 2) {
1056         seed = strtoull(argv[2], NULL, 0);
1057     } else {
1058         FILE *frand = fopen("/dev/urandom", "r");
1059         if (!frand || !fread(&seed, sizeof(seed), 1, frand)) {
1060             seed = time(NULL) * 1337;
1061         }
1062         fclose(frand);
1063     }
1064     secp256k1_rand_seed(seed);
1065
1066     printf("test count = %i\n", count);
1067     printf("random seed = %llu\n", (unsigned long long)seed);
1068
1069     /* initialize */
1070     secp256k1_start(SECP256K1_START_SIGN | SECP256K1_START_VERIFY);
1071
1072     /* num tests */
1073     run_num_smalltests();
1074
1075     /* scalar tests */
1076     run_scalar_tests();
1077
1078     /* field tests */
1079     run_field_inv();
1080     run_field_inv_var();
1081     run_field_inv_all();
1082     run_field_inv_all_var();
1083     run_sqr();
1084     run_sqrt();
1085
1086     /* group tests */
1087     run_ge();
1088
1089     /* ecmult tests */
1090     run_wnaf();
1091     run_point_times_order();
1092     run_ecmult_chain();
1093
1094     /* ecdsa tests */
1095     run_ecdsa_sign_verify();
1096     run_ecdsa_end_to_end();
1097     run_ecdsa_edge_cases();
1098 #ifdef ENABLE_OPENSSL_TESTS
1099     run_ecdsa_openssl();
1100 #endif
1101
1102     printf("random run = %llu\n", (unsigned long long)secp256k1_rand32() + ((unsigned long long)secp256k1_rand32() << 32));
1103
1104     /* shutdown */
1105     secp256k1_stop();
1106     return 0;
1107 }