src/tests.c

   1 // Copyright (c) 2013 Pieter Wuille
   2 // Distributed under the MIT/X11 software license, see the accompanying
   3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   4
   5 #if defined HAVE_CONFIG_H
   6 #include "libsecp256k1-config.h"
   7 #endif
   8
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11
  12 #include "util_impl.h"
  13 #include "secp256k1.c"
  14
  15 #ifdef ENABLE_OPENSSL_TESTS
  16 #include "openssl/bn.h"
  17 #include "openssl/ec.h"
  18 #include "openssl/ecdsa.h"
  19 #include "openssl/obj_mac.h"
  20 #endif
  21
  22 static int count = 64;
  23
  24 /***** NUM TESTS *****/
  25
  26 void random_num_negate(secp256k1_num_t *num) {
  27     if (secp256k1_rand32() & 1)
  28         secp256k1_num_negate(num);
  29 }
  30
  31 void random_num_order_test(secp256k1_num_t *num) {
  32     do {
  33         unsigned char b32[32];
  34         secp256k1_rand256_test(b32);
  35         secp256k1_num_set_bin(num, b32, 32);
  36         if (secp256k1_num_is_zero(num))
  37             continue;
  38         if (secp256k1_num_cmp(num, &secp256k1_ge_consts->order) >= 0)
  39             continue;
  40         break;
  41     } while(1);
  42 }
  43
  44 void random_scalar_order_test(secp256k1_scalar_t *num) {
  45     do {
  46         unsigned char b32[32];
  47         secp256k1_rand256_test(b32);
  48         int overflow = 0;
  49         secp256k1_scalar_set_b32(num, b32, &overflow);
  50         if (overflow || secp256k1_scalar_is_zero(num))
  51             continue;
  52         break;
  53     } while(1);
  54 }
  55
  56 void random_num_order(secp256k1_num_t *num) {
  57     do {
  58         unsigned char b32[32];
  59         secp256k1_rand256(b32);
  60         secp256k1_num_set_bin(num, b32, 32);
  61         if (secp256k1_num_is_zero(num))
  62             continue;
  63         if (secp256k1_num_cmp(num, &secp256k1_ge_consts->order) >= 0)
  64             continue;
  65         break;
  66     } while(1);
  67 }
  68
  69 void test_num_copy_inc_cmp() {
  70     secp256k1_num_t n1,n2;
  71     random_num_order(&n1);
  72     secp256k1_num_copy(&n2, &n1);
  73     CHECK(secp256k1_num_eq(&n1, &n2));
  74     CHECK(secp256k1_num_eq(&n2, &n1));
  75     secp256k1_num_inc(&n2);
  76     CHECK(!secp256k1_num_eq(&n1, &n2));
  77     CHECK(!secp256k1_num_eq(&n2, &n1));
  78 }
  79
  80
  81 void test_num_get_set_hex() {
  82     secp256k1_num_t n1,n2;
  83     random_num_order_test(&n1);
  84     char c[64];
  85     secp256k1_num_get_hex(c, 64, &n1);
  86     secp256k1_num_set_hex(&n2, c, 64);
  87     CHECK(secp256k1_num_eq(&n1, &n2));
  88     for (int i=0; i<64; i++) {
  89         // check whether the lower 4 bits correspond to the last hex character
  90         int low1 = secp256k1_num_shift(&n1, 4);
  91         int lowh = c[63];
  92         int low2 = (lowh>>6)*9+(lowh-'0')&15;
  93         CHECK(low1 == low2);
  94         // shift bits off the hex representation, and compare
  95         memmove(c+1, c, 63);
  96         c[0] = '0';
  97         secp256k1_num_set_hex(&n2, c, 64);
  98         CHECK(secp256k1_num_eq(&n1, &n2));
  99     }
 100 }
 101
 102 void test_num_get_set_bin() {
 103     secp256k1_num_t n1,n2;
 104     random_num_order_test(&n1);
 105     unsigned char c[32];
 106     secp256k1_num_get_bin(c, 32, &n1);
 107     secp256k1_num_set_bin(&n2, c, 32);
 108     CHECK(secp256k1_num_eq(&n1, &n2));
 109     for (int i=0; i<32; i++) {
 110         // check whether the lower 8 bits correspond to the last byte
 111         int low1 = secp256k1_num_shift(&n1, 8);
 112         int low2 = c[31];
 113         CHECK(low1 == low2);
 114         // shift bits off the byte representation, and compare
 115         memmove(c+1, c, 31);
 116         c[0] = 0;
 117         secp256k1_num_set_bin(&n2, c, 32);
 118         CHECK(secp256k1_num_eq(&n1, &n2));
 119     }
 120 }
 121
 122 void run_num_int() {
 123     secp256k1_num_t n1;
 124     for (int i=-255; i<256; i++) {
 125         unsigned char c1[3] = {};
 126         c1[2] = abs(i);
 127         unsigned char c2[3] = {0x11,0x22,0x33};
 128         secp256k1_num_set_int(&n1, i);
 129         secp256k1_num_get_bin(c2, 3, &n1);
 130         CHECK(memcmp(c1, c2, 3) == 0);
 131     }
 132 }
 133
 134 void test_num_negate() {
 135     secp256k1_num_t n1;
 136     secp256k1_num_t n2;
 137     random_num_order_test(&n1); // n1 = R
 138     random_num_negate(&n1);
 139     secp256k1_num_copy(&n2, &n1); // n2 = R
 140     secp256k1_num_sub(&n1, &n2, &n1); // n1 = n2-n1 = 0
 141     CHECK(secp256k1_num_is_zero(&n1));
 142     secp256k1_num_copy(&n1, &n2); // n1 = R
 143     secp256k1_num_negate(&n1); // n1 = -R
 144     CHECK(!secp256k1_num_is_zero(&n1));
 145     secp256k1_num_add(&n1, &n2, &n1); // n1 = n2+n1 = 0
 146     CHECK(secp256k1_num_is_zero(&n1));
 147     secp256k1_num_copy(&n1, &n2); // n1 = R
 148     secp256k1_num_negate(&n1); // n1 = -R
 149     CHECK(secp256k1_num_is_neg(&n1) != secp256k1_num_is_neg(&n2));
 150     secp256k1_num_negate(&n1); // n1 = R
 151     CHECK(secp256k1_num_eq(&n1, &n2));
 152 }
 153
 154 void test_num_add_sub() {
 155     int r = secp256k1_rand32();
 156     secp256k1_num_t n1;
 157     secp256k1_num_t n2;
 158     random_num_order_test(&n1); // n1 = R1
 159     if (r & 1) {
 160         random_num_negate(&n1);
 161     }
 162     random_num_order_test(&n2); // n2 = R2
 163     if (r & 2) {
 164         random_num_negate(&n2);
 165     }
 166     secp256k1_num_t n1p2, n2p1, n1m2, n2m1;
 167     secp256k1_num_add(&n1p2, &n1, &n2); // n1p2 = R1 + R2
 168     secp256k1_num_add(&n2p1, &n2, &n1); // n2p1 = R2 + R1
 169     secp256k1_num_sub(&n1m2, &n1, &n2); // n1m2 = R1 - R2
 170     secp256k1_num_sub(&n2m1, &n2, &n1); // n2m1 = R2 - R1
 171     CHECK(secp256k1_num_eq(&n1p2, &n2p1));
 172     CHECK(!secp256k1_num_eq(&n1p2, &n1m2));
 173     secp256k1_num_negate(&n2m1); // n2m1 = -R2 + R1
 174     CHECK(secp256k1_num_eq(&n2m1, &n1m2));
 175     CHECK(!secp256k1_num_eq(&n2m1, &n1));
 176     secp256k1_num_add(&n2m1, &n2m1, &n2); // n2m1 = -R2 + R1 + R2 = R1
 177     CHECK(secp256k1_num_eq(&n2m1, &n1));
 178     CHECK(!secp256k1_num_eq(&n2p1, &n1));
 179     secp256k1_num_sub(&n2p1, &n2p1, &n2); // n2p1 = R2 + R1 - R2 = R1
 180     CHECK(secp256k1_num_eq(&n2p1, &n1));
 181 }
 182
 183 void run_num_smalltests() {
 184     for (int i=0; i<100*count; i++) {
 185         test_num_copy_inc_cmp();
 186         test_num_get_set_hex();
 187         test_num_get_set_bin();
 188         test_num_negate();
 189         test_num_add_sub();
 190     }
 191     run_num_int();
 192 }
 193
 194 /***** SCALAR TESTS *****/
 195
 196 int secp256k1_scalar_eq(const secp256k1_scalar_t *s1, const secp256k1_scalar_t *s2) {
 197     secp256k1_scalar_t t;
 198     secp256k1_scalar_negate(&t, s2);
 199     secp256k1_scalar_add(&t, &t, s1);
 200     int ret = secp256k1_scalar_is_zero(&t);
 201     return ret;
 202 }
 203
 204 void scalar_test(void) {
 205     unsigned char c[32];
 206
 207     // Set 's' to a random scalar, with value 'snum'.
 208     secp256k1_rand256_test(c);
 209     secp256k1_scalar_t s;
 210     secp256k1_scalar_set_b32(&s, c, NULL);
 211     secp256k1_num_t snum;
 212     secp256k1_num_set_bin(&snum, c, 32);
 213     secp256k1_num_mod(&snum, &secp256k1_ge_consts->order);
 214
 215     // Set 's1' to a random scalar, with value 's1num'.
 216     secp256k1_rand256_test(c);
 217     secp256k1_scalar_t s1;
 218     secp256k1_scalar_set_b32(&s1, c, NULL);
 219     secp256k1_num_t s1num;
 220     secp256k1_num_set_bin(&s1num, c, 32);
 221     secp256k1_num_mod(&s1num, &secp256k1_ge_consts->order);
 222
 223     // Set 's2' to a random scalar, with value 'snum2', and byte array representation 'c'.
 224     secp256k1_rand256_test(c);
 225     secp256k1_scalar_t s2;
 226     int overflow = 0;
 227     secp256k1_scalar_set_b32(&s2, c, &overflow);
 228     secp256k1_num_t s2num;
 229     secp256k1_num_set_bin(&s2num, c, 32);
 230     secp256k1_num_mod(&s2num, &secp256k1_ge_consts->order);
 231
 232     {
 233         // Test that fetching groups of 4 bits from a scalar and recursing n(i)=16*n(i-1)+p(i) reconstructs it.
 234         secp256k1_num_t n, t, m;
 235         secp256k1_num_set_int(&n, 0);
 236         secp256k1_num_set_int(&m, 16);
 237         for (int i = 0; i < 256; i += 4) {
 238             secp256k1_num_set_int(&t, secp256k1_scalar_get_bits(&s, 256 - 4 - i, 4));
 239             secp256k1_num_mul(&n, &n, &m);
 240             secp256k1_num_add(&n, &n, &t);
 241         }
 242         CHECK(secp256k1_num_eq(&n, &snum));
 243     }
 244
 245     {
 246         // Test that get_b32 returns the same as get_bin on the number.
 247         unsigned char r1[32];
 248         secp256k1_scalar_get_b32(r1, &s2);
 249         unsigned char r2[32];
 250         secp256k1_num_get_bin(r2, 32, &s2num);
 251         CHECK(memcmp(r1, r2, 32) == 0);
 252         // If no overflow occurred when assigning, it should also be equal to the original byte array.
 253         CHECK((memcmp(r1, c, 32) == 0) == (overflow == 0));
 254     }
 255
 256     {
 257         // Test that adding the scalars together is equal to adding their numbers together modulo the order.
 258         secp256k1_num_t rnum;
 259         secp256k1_num_add(&rnum, &snum, &s2num);
 260         secp256k1_num_mod(&rnum, &secp256k1_ge_consts->order);
 261         secp256k1_scalar_t r;
 262         secp256k1_scalar_add(&r, &s, &s2);
 263         secp256k1_num_t r2num;
 264         secp256k1_scalar_get_num(&r2num, &r);
 265         CHECK(secp256k1_num_eq(&rnum, &r2num));
 266     }
 267
 268     {
 269         // Test that multipying the scalars is equal to multiplying their numbers modulo the order.
 270         secp256k1_num_t rnum;
 271         secp256k1_num_mul(&rnum, &snum, &s2num);
 272         secp256k1_num_mod(&rnum, &secp256k1_ge_consts->order);
 273         secp256k1_scalar_t r;
 274         secp256k1_scalar_mul(&r, &s, &s2);
 275         secp256k1_num_t r2num;
 276         secp256k1_scalar_get_num(&r2num, &r);
 277         CHECK(secp256k1_num_eq(&rnum, &r2num));
 278         // The result can only be zero if at least one of the factors was zero.
 279         CHECK(secp256k1_scalar_is_zero(&r) == (secp256k1_scalar_is_zero(&s) || secp256k1_scalar_is_zero(&s2)));
 280         // The results can only be equal to one of the factors if that factor was zero, or the other factor was one.
 281         CHECK(secp256k1_num_eq(&rnum, &snum) == (secp256k1_scalar_is_zero(&s) || secp256k1_scalar_is_one(&s2)));
 282         CHECK(secp256k1_num_eq(&rnum, &s2num) == (secp256k1_scalar_is_zero(&s2) || secp256k1_scalar_is_one(&s)));
 283     }
 284
 285     {
 286         // Check that comparison with zero matches comparison with zero on the number.
 287         CHECK(secp256k1_num_is_zero(&snum) == secp256k1_scalar_is_zero(&s));
 288         // Check that comparison with the half order is equal to testing for high scalar.
 289         CHECK(secp256k1_scalar_is_high(&s) == (secp256k1_num_cmp(&snum, &secp256k1_ge_consts->half_order) > 0));
 290         secp256k1_scalar_t neg;
 291         secp256k1_scalar_negate(&neg, &s);
 292         secp256k1_num_t negnum;
 293         secp256k1_num_sub(&negnum, &secp256k1_ge_consts->order, &snum);
 294         secp256k1_num_mod(&negnum, &secp256k1_ge_consts->order);
 295         // Check that comparison with the half order is equal to testing for high scalar after negation.
 296         CHECK(secp256k1_scalar_is_high(&neg) == (secp256k1_num_cmp(&negnum, &secp256k1_ge_consts->half_order) > 0));
 297         // Negating should change the high property, unless the value was already zero.
 298         CHECK((secp256k1_scalar_is_high(&s) == secp256k1_scalar_is_high(&neg)) == secp256k1_scalar_is_zero(&s));
 299         secp256k1_num_t negnum2;
 300         secp256k1_scalar_get_num(&negnum2, &neg);
 301         // Negating a scalar should be equal to (order - n) mod order on the number.
 302         CHECK(secp256k1_num_eq(&negnum, &negnum2));
 303         secp256k1_scalar_add(&neg, &neg, &s);
 304         // Adding a number to its negation should result in zero.
 305         CHECK(secp256k1_scalar_is_zero(&neg));
 306         secp256k1_scalar_negate(&neg, &neg);
 307         // Negating zero should still result in zero.
 308         CHECK(secp256k1_scalar_is_zero(&neg));
 309     }
 310
 311     {
 312         // Test that scalar inverses are equal to the inverse of their number modulo the order.
 313         if (!secp256k1_scalar_is_zero(&s)) {
 314             secp256k1_scalar_t inv;
 315             secp256k1_scalar_inverse(&inv, &s);
 316             secp256k1_num_t invnum;
 317             secp256k1_num_mod_inverse(&invnum, &snum, &secp256k1_ge_consts->order);
 318             secp256k1_num_t invnum2;
 319             secp256k1_scalar_get_num(&invnum2, &inv);
 320             CHECK(secp256k1_num_eq(&invnum, &invnum2));
 321             secp256k1_scalar_mul(&inv, &inv, &s);
 322             // Multiplying a scalar with its inverse must result in one.
 323             CHECK(secp256k1_scalar_is_one(&inv));
 324             secp256k1_scalar_inverse(&inv, &inv);
 325             // Inverting one must result in one.
 326             CHECK(secp256k1_scalar_is_one(&inv));
 327         }
 328     }
 329
 330     {
 331         // Test commutativity of add.
 332         secp256k1_scalar_t r1, r2;
 333         secp256k1_scalar_add(&r1, &s1, &s2);
 334         secp256k1_scalar_add(&r2, &s2, &s1);
 335         CHECK(secp256k1_scalar_eq(&r1, &r2));
 336     }
 337
 338     {
 339         // Test commutativity of mul.
 340         secp256k1_scalar_t r1, r2;
 341         secp256k1_scalar_mul(&r1, &s1, &s2);
 342         secp256k1_scalar_mul(&r2, &s2, &s1);
 343         CHECK(secp256k1_scalar_eq(&r1, &r2));
 344     }
 345
 346     {
 347         // Test associativity of add.
 348         secp256k1_scalar_t r1, r2;
 349         secp256k1_scalar_add(&r1, &s1, &s2);
 350         secp256k1_scalar_add(&r1, &r1, &s);
 351         secp256k1_scalar_add(&r2, &s2, &s);
 352         secp256k1_scalar_add(&r2, &s1, &r2);
 353         CHECK(secp256k1_scalar_eq(&r1, &r2));
 354     }
 355
 356     {
 357         // Test associativity of mul.
 358         secp256k1_scalar_t r1, r2;
 359         secp256k1_scalar_mul(&r1, &s1, &s2);
 360         secp256k1_scalar_mul(&r1, &r1, &s);
 361         secp256k1_scalar_mul(&r2, &s2, &s);
 362         secp256k1_scalar_mul(&r2, &s1, &r2);
 363         CHECK(secp256k1_scalar_eq(&r1, &r2));
 364     }
 365
 366     {
 367         // Test distributitivity of mul over add.
 368         secp256k1_scalar_t r1, r2, t;
 369         secp256k1_scalar_add(&r1, &s1, &s2);
 370         secp256k1_scalar_mul(&r1, &r1, &s);
 371         secp256k1_scalar_mul(&r2, &s1, &s);
 372         secp256k1_scalar_mul(&t, &s2, &s);
 373         secp256k1_scalar_add(&r2, &r2, &t);
 374         CHECK(secp256k1_scalar_eq(&r1, &r2));
 375     }
 376
 377     {
 378         // Test square.
 379         secp256k1_scalar_t r1, r2;
 380         secp256k1_scalar_sqr(&r1, &s1);
 381         secp256k1_scalar_mul(&r2, &s1, &s1);
 382         CHECK(secp256k1_scalar_eq(&r1, &r2));
 383     }
 384 }
 385
 386 void run_scalar_tests(void) {
 387     for (int i = 0; i < 128 * count; i++) {
 388         scalar_test();
 389     }
 390 }
 391
 392 /***** FIELD TESTS *****/
 393
 394 void random_fe(secp256k1_fe_t *x) {
 395     unsigned char bin[32];
 396     secp256k1_rand256(bin);
 397     secp256k1_fe_set_b32(x, bin);
 398 }
 399
 400 void random_fe_non_zero(secp256k1_fe_t *nz) {
 401     int tries = 10;
 402     while (--tries >= 0) {
 403         random_fe(nz);
 404         secp256k1_fe_normalize(nz);
 405         if (!secp256k1_fe_is_zero(nz))
 406             break;
 407     }
 408     // Infinitesimal probability of spurious failure here
 409     CHECK(tries >= 0);
 410 }
 411
 412 void random_fe_non_square(secp256k1_fe_t *ns) {
 413     random_fe_non_zero(ns);
 414     secp256k1_fe_t r;
 415     if (secp256k1_fe_sqrt(&r, ns)) {
 416         secp256k1_fe_negate(ns, ns, 1);
 417     }
 418 }
 419
 420 int check_fe_equal(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
 421     secp256k1_fe_t an = *a; secp256k1_fe_normalize(&an);
 422     secp256k1_fe_t bn = *b; secp256k1_fe_normalize(&bn);
 423     return secp256k1_fe_equal(&an, &bn);
 424 }
 425
 426 int check_fe_inverse(const secp256k1_fe_t *a, const secp256k1_fe_t *ai) {
 427     secp256k1_fe_t x; secp256k1_fe_mul(&x, a, ai);
 428     secp256k1_fe_t one; secp256k1_fe_set_int(&one, 1);
 429     return check_fe_equal(&x, &one);
 430 }
 431
 432 void run_field_inv() {
 433     secp256k1_fe_t x, xi, xii;
 434     for (int i=0; i<10*count; i++) {
 435         random_fe_non_zero(&x);
 436         secp256k1_fe_inv(&xi, &x);
 437         CHECK(check_fe_inverse(&x, &xi));
 438         secp256k1_fe_inv(&xii, &xi);
 439         CHECK(check_fe_equal(&x, &xii));
 440     }
 441 }
 442
 443 void run_field_inv_var() {
 444     secp256k1_fe_t x, xi, xii;
 445     for (int i=0; i<10*count; i++) {
 446         random_fe_non_zero(&x);
 447         secp256k1_fe_inv_var(&xi, &x);
 448         CHECK(check_fe_inverse(&x, &xi));
 449         secp256k1_fe_inv_var(&xii, &xi);
 450         CHECK(check_fe_equal(&x, &xii));
 451     }
 452 }
 453
 454 void run_field_inv_all() {
 455     secp256k1_fe_t x[16], xi[16], xii[16];
 456     // Check it's safe to call for 0 elements
 457     secp256k1_fe_inv_all(0, xi, x);
 458     for (int i=0; i<count; i++) {
 459         size_t len = (secp256k1_rand32() & 15) + 1;
 460         for (int j=0; j<len; j++)
 461             random_fe_non_zero(&x[j]);
 462         secp256k1_fe_inv_all(len, xi, x);
 463         for (int j=0; j<len; j++)
 464             CHECK(check_fe_inverse(&x[j], &xi[j]));
 465         secp256k1_fe_inv_all(len, xii, xi);
 466         for (int j=0; j<len; j++)
 467             CHECK(check_fe_equal(&x[j], &xii[j]));
 468     }
 469 }
 470
 471 void run_field_inv_all_var() {
 472     secp256k1_fe_t x[16], xi[16], xii[16];
 473     // Check it's safe to call for 0 elements
 474     secp256k1_fe_inv_all_var(0, xi, x);
 475     for (int i=0; i<count; i++) {
 476         size_t len = (secp256k1_rand32() & 15) + 1;
 477         for (int j=0; j<len; j++)
 478             random_fe_non_zero(&x[j]);
 479         secp256k1_fe_inv_all_var(len, xi, x);
 480         for (int j=0; j<len; j++)
 481             CHECK(check_fe_inverse(&x[j], &xi[j]));
 482         secp256k1_fe_inv_all_var(len, xii, xi);
 483         for (int j=0; j<len; j++)
 484             CHECK(check_fe_equal(&x[j], &xii[j]));
 485     }
 486 }
 487
 488 void run_sqr() {
 489     secp256k1_fe_t x, s;
 490
 491     {
 492         secp256k1_fe_set_int(&x, 1);
 493         secp256k1_fe_negate(&x, &x, 1);
 494
 495         for (int i=1; i<=512; ++i) {
 496             secp256k1_fe_mul_int(&x, 2);
 497             secp256k1_fe_normalize(&x);
 498             secp256k1_fe_sqr(&s, &x);
 499         }
 500     }
 501 }
 502
 503 void test_sqrt(const secp256k1_fe_t *a, const secp256k1_fe_t *k) {
 504     secp256k1_fe_t r1, r2;
 505     int v = secp256k1_fe_sqrt(&r1, a);
 506     CHECK((v == 0) == (k == NULL));
 507
 508     if (k != NULL) {
 509         // Check that the returned root is +/- the given known answer
 510         secp256k1_fe_negate(&r2, &r1, 1);
 511         secp256k1_fe_add(&r1, k); secp256k1_fe_add(&r2, k);
 512         secp256k1_fe_normalize(&r1); secp256k1_fe_normalize(&r2);
 513         CHECK(secp256k1_fe_is_zero(&r1) || secp256k1_fe_is_zero(&r2));
 514     }
 515 }
 516
 517 void run_sqrt() {
 518     secp256k1_fe_t ns, x, s, t;
 519
 520     // Check sqrt(0) is 0
 521     secp256k1_fe_set_int(&x, 0);
 522     secp256k1_fe_sqr(&s, &x);
 523     test_sqrt(&s, &x);
 524
 525     // Check sqrt of small squares (and their negatives)
 526     for (int i=1; i<=100; i++) {
 527         secp256k1_fe_set_int(&x, i);
 528         secp256k1_fe_sqr(&s, &x);
 529         test_sqrt(&s, &x);
 530         secp256k1_fe_negate(&t, &s, 1);
 531         test_sqrt(&t, NULL);
 532     }
 533
 534     // Consistency checks for large random values
 535     for (int i=0; i<10; i++) {
 536         random_fe_non_square(&ns);
 537         for (int j=0; j<count; j++) {
 538             random_fe(&x);
 539             secp256k1_fe_sqr(&s, &x);
 540             test_sqrt(&s, &x);
 541             secp256k1_fe_negate(&t, &s, 1);
 542             test_sqrt(&t, NULL);
 543             secp256k1_fe_mul(&t, &s, &ns);
 544             test_sqrt(&t, NULL);
 545         }
 546     }
 547 }
 548
 549 /***** ECMULT TESTS *****/
 550
 551 void run_ecmult_chain() {
 552     // random starting point A (on the curve)
 553     secp256k1_fe_t ax; secp256k1_fe_set_hex(&ax, "8b30bbe9ae2a990696b22f670709dff3727fd8bc04d3362c6c7bf458e2846004", 64);
 554     secp256k1_fe_t ay; secp256k1_fe_set_hex(&ay, "a357ae915c4a65281309edf20504740f0eb3343990216b4f81063cb65f2f7e0f", 64);
 555     secp256k1_gej_t a; secp256k1_gej_set_xy(&a, &ax, &ay);
 556     // two random initial factors xn and gn
 557     secp256k1_num_t xn;
 558     secp256k1_num_set_hex(&xn, "84cc5452f7fde1edb4d38a8ce9b1b84ccef31f146e569be9705d357a42985407", 64);
 559     secp256k1_num_t gn;
 560     secp256k1_num_set_hex(&gn, "a1e58d22553dcd42b23980625d4c57a96e9323d42b3152e5ca2c3990edc7c9de", 64);
 561     // two small multipliers to be applied to xn and gn in every iteration:
 562     secp256k1_num_t xf;
 563     secp256k1_num_set_hex(&xf, "1337", 4);
 564     secp256k1_num_t gf;
 565     secp256k1_num_set_hex(&gf, "7113", 4);
 566     // accumulators with the resulting coefficients to A and G
 567     secp256k1_num_t ae;
 568     secp256k1_num_set_int(&ae, 1);
 569     secp256k1_num_t ge;
 570     secp256k1_num_set_int(&ge, 0);
 571     // the point being computed
 572     secp256k1_gej_t x = a;
 573     const secp256k1_num_t *order = &secp256k1_ge_consts->order;
 574     for (int i=0; i<200*count; i++) {
 575         // in each iteration, compute X = xn*X + gn*G;
 576         secp256k1_ecmult(&x, &x, &xn, &gn);
 577         // also compute ae and ge: the actual accumulated factors for A and G
 578         // if X was (ae*A+ge*G), xn*X + gn*G results in (xn*ae*A + (xn*ge+gn)*G)
 579         secp256k1_num_mod_mul(&ae, &ae, &xn, order);
 580         secp256k1_num_mod_mul(&ge, &ge, &xn, order);
 581         secp256k1_num_add(&ge, &ge, &gn);
 582         secp256k1_num_mod(&ge, order);
 583         // modify xn and gn
 584         secp256k1_num_mod_mul(&xn, &xn, &xf, order);
 585         secp256k1_num_mod_mul(&gn, &gn, &gf, order);
 586
 587         // verify
 588         if (i == 19999) {
 589             char res[132]; int resl = 132;
 590             secp256k1_gej_get_hex(res, &resl, &x);
 591             CHECK(strcmp(res, "(D6E96687F9B10D092A6F35439D86CEBEA4535D0D409F53586440BD74B933E830,B95CBCA2C77DA786539BE8FD53354D2D3B4F566AE658045407ED6015EE1B2A88)") == 0);
 592         }
 593     }
 594     // redo the computation, but directly with the resulting ae and ge coefficients:
 595     secp256k1_gej_t x2; secp256k1_ecmult(&x2, &a, &ae, &ge);
 596     char res[132]; int resl = 132;
 597     char res2[132]; int resl2 = 132;
 598     secp256k1_gej_get_hex(res, &resl, &x);
 599     secp256k1_gej_get_hex(res2, &resl2, &x2);
 600     CHECK(strcmp(res, res2) == 0);
 601     CHECK(strlen(res) == 131);
 602 }
 603
 604 void test_point_times_order(const secp256k1_gej_t *point) {
 605     // multiplying a point by the order results in O
 606     const secp256k1_num_t *order = &secp256k1_ge_consts->order;
 607     secp256k1_num_t zero;
 608     secp256k1_num_set_int(&zero, 0);
 609     secp256k1_gej_t res;
 610     secp256k1_ecmult(&res, point, order, order); // calc res = order * point + order * G;
 611     CHECK(secp256k1_gej_is_infinity(&res));
 612 }
 613
 614 void run_point_times_order() {
 615     secp256k1_fe_t x; secp256k1_fe_set_hex(&x, "02", 2);
 616     for (int i=0; i<500; i++) {
 617         secp256k1_ge_t p;
 618         if (secp256k1_ge_set_xo(&p, &x, 1)) {
 619             CHECK(secp256k1_ge_is_valid(&p));
 620             secp256k1_gej_t j;
 621             secp256k1_gej_set_ge(&j, &p);
 622             CHECK(secp256k1_gej_is_valid(&j));
 623             test_point_times_order(&j);
 624         }
 625         secp256k1_fe_sqr(&x, &x);
 626     }
 627     char c[65]; int cl=65;
 628     secp256k1_fe_get_hex(c, &cl, &x);
 629     CHECK(strcmp(c, "7603CB59B0EF6C63FE6084792A0C378CDB3233A80F8A9A09A877DEAD31B38C45") == 0);
 630 }
 631
 632 void test_wnaf(const secp256k1_num_t *number, int w) {
 633     secp256k1_num_t x, two, t;
 634     secp256k1_num_set_int(&x, 0);
 635     secp256k1_num_set_int(&two, 2);
 636     int wnaf[257];
 637     int bits = secp256k1_ecmult_wnaf(wnaf, number, w);
 638     int zeroes = -1;
 639     for (int i=bits-1; i>=0; i--) {
 640         secp256k1_num_mul(&x, &x, &two);
 641         int v = wnaf[i];
 642         if (v) {
 643             CHECK(zeroes == -1 || zeroes >= w-1); // check that distance between non-zero elements is at least w-1
 644             zeroes=0;
 645             CHECK((v & 1) == 1); // check non-zero elements are odd
 646             CHECK(v <= (1 << (w-1)) - 1); // check range below
 647             CHECK(v >= -(1 << (w-1)) - 1); // check range above
 648         } else {
 649             CHECK(zeroes != -1); // check that no unnecessary zero padding exists
 650             zeroes++;
 651         }
 652         secp256k1_num_set_int(&t, v);
 653         secp256k1_num_add(&x, &x, &t);
 654     }
 655     CHECK(secp256k1_num_eq(&x, number)); // check that wnaf represents number
 656 }
 657
 658 void run_wnaf() {
 659     secp256k1_num_t n;
 660     for (int i=0; i<count; i++) {
 661         random_num_order(&n);
 662         if (i % 1)
 663             secp256k1_num_negate(&n);
 664         test_wnaf(&n, 4+(i%10));
 665     }
 666 }
 667
 668 void random_sign(secp256k1_ecdsa_sig_t *sig, const secp256k1_scalar_t *key, const secp256k1_scalar_t *msg, int *recid) {
 669     secp256k1_scalar_t nonce;
 670     do {
 671         random_scalar_order_test(&nonce);
 672     } while(!secp256k1_ecdsa_sig_sign(sig, key, msg, &nonce, recid));
 673 }
 674
 675 void test_ecdsa_sign_verify() {
 676     const secp256k1_ge_consts_t *c = secp256k1_ge_consts;
 677     secp256k1_scalar_t msg, key;
 678     random_scalar_order_test(&msg);
 679     random_scalar_order_test(&key);
 680     secp256k1_gej_t pubj; secp256k1_ecmult_gen(&pubj, &key);
 681     secp256k1_ge_t pub; secp256k1_ge_set_gej(&pub, &pubj);
 682     secp256k1_ecdsa_sig_t sig;
 683     random_sign(&sig, &key, &msg, NULL);
 684     secp256k1_num_t msg_num;
 685     secp256k1_scalar_get_num(&msg_num, &msg);
 686     CHECK(secp256k1_ecdsa_sig_verify(&sig, &pub, &msg_num));
 687     secp256k1_num_inc(&msg_num);
 688     CHECK(!secp256k1_ecdsa_sig_verify(&sig, &pub, &msg_num));
 689 }
 690
 691 void run_ecdsa_sign_verify() {
 692     for (int i=0; i<10*count; i++) {
 693         test_ecdsa_sign_verify();
 694     }
 695 }
 696
 697 void test_ecdsa_end_to_end() {
 698     unsigned char privkey[32];
 699     unsigned char message[32];
 700
 701     // Generate a random key and message.
 702     {
 703         secp256k1_num_t msg, key;
 704         random_num_order_test(&msg);
 705         random_num_order_test(&key);
 706         secp256k1_num_get_bin(privkey, 32, &key);
 707         secp256k1_num_get_bin(message, 32, &msg);
 708     }
 709
 710     // Construct and verify corresponding public key.
 711     CHECK(secp256k1_ec_seckey_verify(privkey) == 1);
 712     char pubkey[65]; int pubkeylen = 65;
 713     CHECK(secp256k1_ec_pubkey_create(pubkey, &pubkeylen, privkey, secp256k1_rand32() % 2) == 1);
 714     CHECK(secp256k1_ec_pubkey_verify(pubkey, pubkeylen));
 715
 716     // Verify private key import and export.
 717     unsigned char seckey[300]; int seckeylen = 300;
 718     CHECK(secp256k1_ec_privkey_export(privkey, seckey, &seckeylen, secp256k1_rand32() % 2) == 1);
 719     unsigned char privkey2[32];
 720     CHECK(secp256k1_ec_privkey_import(privkey2, seckey, seckeylen) == 1);
 721     CHECK(memcmp(privkey, privkey2, 32) == 0);
 722
 723     // Optionally tweak the keys using addition.
 724     if (secp256k1_rand32() % 3 == 0) {
 725         unsigned char rnd[32];
 726         secp256k1_rand256_test(rnd);
 727         int ret1 = secp256k1_ec_privkey_tweak_add(privkey, rnd);
 728         int ret2 = secp256k1_ec_pubkey_tweak_add(pubkey, pubkeylen, rnd);
 729         CHECK(ret1 == ret2);
 730         if (ret1 == 0) return;
 731         char pubkey2[65]; int pubkeylen2 = 65;
 732         CHECK(secp256k1_ec_pubkey_create(pubkey2, &pubkeylen2, privkey, pubkeylen == 33) == 1);
 733         CHECK(memcmp(pubkey, pubkey2, pubkeylen) == 0);
 734     }
 735
 736     // Optionally tweak the keys using multiplication.
 737     if (secp256k1_rand32() % 3 == 0) {
 738         unsigned char rnd[32];
 739         secp256k1_rand256_test(rnd);
 740         int ret1 = secp256k1_ec_privkey_tweak_mul(privkey, rnd);
 741         int ret2 = secp256k1_ec_pubkey_tweak_mul(pubkey, pubkeylen, rnd);
 742         CHECK(ret1 == ret2);
 743         if (ret1 == 0) return;
 744         char pubkey2[65]; int pubkeylen2 = 65;
 745         CHECK(secp256k1_ec_pubkey_create(pubkey2, &pubkeylen2, privkey, pubkeylen == 33) == 1);
 746         CHECK(memcmp(pubkey, pubkey2, pubkeylen) == 0);
 747     }
 748
 749     // Sign.
 750     unsigned char signature[72]; unsigned int signaturelen = 72;
 751     while(1) {
 752         unsigned char rnd[32];
 753         secp256k1_rand256_test(rnd);
 754         if (secp256k1_ecdsa_sign(message, 32, signature, &signaturelen, privkey, rnd) == 1) {
 755             break;
 756         }
 757     }
 758     // Verify.
 759     CHECK(secp256k1_ecdsa_verify(message, 32, signature, signaturelen, pubkey, pubkeylen) == 1);
 760     // Destroy signature and verify again.
 761     signature[signaturelen - 1 - secp256k1_rand32() % 20] += 1 + (secp256k1_rand32() % 255);
 762     CHECK(secp256k1_ecdsa_verify(message, 32, signature, signaturelen, pubkey, pubkeylen) != 1);
 763
 764     // Compact sign.
 765     unsigned char csignature[64]; unsigned int recid = 0;
 766     while(1) {
 767         unsigned char rnd[32];
 768         secp256k1_rand256_test(rnd);
 769         if (secp256k1_ecdsa_sign_compact(message, 32, csignature, privkey, rnd, &recid) == 1) {
 770             break;
 771         }
 772     }
 773     // Recover.
 774     unsigned char recpubkey[65]; unsigned recpubkeylen = 0;
 775     CHECK(secp256k1_ecdsa_recover_compact(message, 32, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) == 1);
 776     CHECK(recpubkeylen == pubkeylen);
 777     CHECK(memcmp(pubkey, recpubkey, pubkeylen) == 0);
 778     // Destroy signature and verify again.
 779     csignature[secp256k1_rand32() % 64] += 1 + (secp256k1_rand32() % 255);
 780     CHECK(secp256k1_ecdsa_recover_compact(message, 32, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) != 1 ||
 781           memcmp(pubkey, recpubkey, pubkeylen) != 0);
 782     CHECK(recpubkeylen == pubkeylen);
 783
 784 }
 785
 786 void run_ecdsa_end_to_end() {
 787     for (int i=0; i<64*count; i++) {
 788         test_ecdsa_end_to_end();
 789     }
 790 }
 791
 792
 793 #ifdef ENABLE_OPENSSL_TESTS
 794 EC_KEY *get_openssl_key(const secp256k1_scalar_t *key) {
 795     unsigned char privkey[300];
 796     int privkeylen;
 797     int compr = secp256k1_rand32() & 1;
 798     const unsigned char* pbegin = privkey;
 799     EC_KEY *ec_key = EC_KEY_new_by_curve_name(NID_secp256k1);
 800     CHECK(secp256k1_eckey_privkey_serialize(privkey, &privkeylen, key, compr));
 801     CHECK(d2i_ECPrivateKey(&ec_key, &pbegin, privkeylen));
 802     CHECK(EC_KEY_check_key(ec_key));
 803     return ec_key;
 804 }
 805
 806 void test_ecdsa_openssl() {
 807     const secp256k1_ge_consts_t *c = secp256k1_ge_consts;
 808     secp256k1_scalar_t key, msg;
 809     unsigned char message[32];
 810     secp256k1_rand256_test(message);
 811     secp256k1_scalar_set_b32(&msg, message, NULL);
 812     random_scalar_order_test(&key);
 813     secp256k1_gej_t qj;
 814     secp256k1_ecmult_gen(&qj, &key);
 815     secp256k1_ge_t q;
 816     secp256k1_ge_set_gej(&q, &qj);
 817     EC_KEY *ec_key = get_openssl_key(&key);
 818     CHECK(ec_key);
 819     unsigned char signature[80];
 820     int sigsize = 80;
 821     CHECK(ECDSA_sign(0, message, sizeof(message), signature, &sigsize, ec_key));
 822     secp256k1_ecdsa_sig_t sig;
 823     CHECK(secp256k1_ecdsa_sig_parse(&sig, signature, sigsize));
 824     secp256k1_num_t msg_num;
 825     secp256k1_scalar_get_num(&msg_num, &msg);
 826     CHECK(secp256k1_ecdsa_sig_verify(&sig, &q, &msg_num));
 827     secp256k1_num_inc(&sig.r);
 828     CHECK(!secp256k1_ecdsa_sig_verify(&sig, &q, &msg_num));
 829
 830     random_sign(&sig, &key, &msg, NULL);
 831     sigsize = 80;
 832     CHECK(secp256k1_ecdsa_sig_serialize(signature, &sigsize, &sig));
 833     CHECK(ECDSA_verify(0, message, sizeof(message), signature, sigsize, ec_key) == 1);
 834
 835     EC_KEY_free(ec_key);
 836 }
 837
 838 void run_ecdsa_openssl() {
 839     for (int i=0; i<10*count; i++) {
 840         test_ecdsa_openssl();
 841     }
 842 }
 843 #endif
 844
 845 int main(int argc, char **argv) {
 846     // find iteration count
 847     if (argc > 1) {
 848         count = strtol(argv[1], NULL, 0);
 849     }
 850
 851     // find random seed
 852     uint64_t seed;
 853     if (argc > 2) {
 854         seed = strtoull(argv[2], NULL, 0);
 855     } else {
 856         FILE *frand = fopen("/dev/urandom", "r");
 857         if (!frand || !fread(&seed, sizeof(seed), 1, frand)) {
 858             seed = time(NULL) * 1337;
 859         }
 860         fclose(frand);
 861     }
 862     secp256k1_rand_seed(seed);
 863
 864     printf("test count = %i\n", count);
 865     printf("random seed = %llu\n", (unsigned long long)seed);
 866
 867     // initialize
 868     secp256k1_start(SECP256K1_START_SIGN | SECP256K1_START_VERIFY);
 869
 870     // num tests
 871     run_num_smalltests();
 872
 873     // scalar tests
 874     run_scalar_tests();
 875
 876     // field tests
 877     run_field_inv();
 878     run_field_inv_var();
 879     run_field_inv_all();
 880     run_field_inv_all_var();
 881     run_sqr();
 882     run_sqrt();
 883
 884     // ecmult tests
 885     run_wnaf();
 886     run_point_times_order();
 887     run_ecmult_chain();
 888
 889     // ecdsa tests
 890     run_ecdsa_sign_verify();
 891     run_ecdsa_end_to_end();
 892 #ifdef ENABLE_OPENSSL_TESTS
 893     run_ecdsa_openssl();
 894 #endif
 895
 896     printf("random run = %llu\n", (unsigned long long)secp256k1_rand32() + (unsigned long long)secp256k1_rand32() << 32);
 897
 898     // shutdown
 899     secp256k1_stop();
 900     return 0;
 901 }