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