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