test/bntest.c

   1 /*
   2  * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9 #include <assert.h>
  10 #include <errno.h>
  11 #include <stdio.h>
  12 #include <string.h>
  13 #include <ctype.h>
  14
  15 #include "e_os.h"
  16 #include <internal/numbers.h>
  17 #include <openssl/bn.h>
  18 #include <openssl/crypto.h>
  19 #include <openssl/err.h>
  20 #include <openssl/rand.h>
  21 #include "testutil.h"
  22
  23 /*
  24  * In bn_lcl.h, bn_expand() is defined as a static ossl_inline function.
  25  * This is fine in itself, it will end up as an unused static function in
  26  * the worst case.  However, it references bn_expand2(), which is a private
  27  * function in libcrypto and therefore unavailable on some systems.  This
  28  * may result in a linker error because of unresolved symbols.
  29  *
  30  * To avoid this, we define a dummy variant of bn_expand2() here, and to
  31  * avoid possible clashes with libcrypto, we rename it first, using a macro.
  32  */
  33 #define bn_expand2 dummy_bn_expand2
  34 BIGNUM *bn_expand2(BIGNUM *b, int words);
  35 BIGNUM *bn_expand2(BIGNUM *b, int words) { return NULL; }
  36 #include "../crypto/bn/bn_lcl.h"
  37
  38 #define MAXPAIRS        20
  39
  40 /*
  41  * Things in boring, not in openssl.  TODO we should add them.
  42  */
  43 #define HAVE_BN_PADDED 0
  44 #define HAVE_BN_SQRT 0
  45
  46 typedef struct pair_st {
  47     char *key;
  48     char *value;
  49 } PAIR;
  50
  51 typedef struct stanza_st {
  52     int start;
  53     int numpairs;
  54     PAIR pairs[MAXPAIRS];
  55 } STANZA;
  56
  57 typedef struct filetest_st {
  58     const char *name;
  59     int (*func)(STANZA *s);
  60 } FILETEST;
  61
  62 typedef struct mpitest_st {
  63     const char *base10;
  64     const char *mpi;
  65     size_t mpi_len;
  66 } MPITEST;
  67
  68 static const int NUM0 = 100;           /* number of tests */
  69 static const int NUM1 = 50;            /* additional tests for some functions */
  70 static FILE *fp;
  71 static BN_CTX *ctx;
  72
  73
  74 /*
  75  * Look for |key| in the stanza and return it or NULL if not found.
  76  */
  77 static const char *findattr(STANZA *s, const char *key)
  78 {
  79     int i = s->numpairs;
  80     PAIR *pp = s->pairs;
  81
  82     for ( ; --i >= 0; pp++)
  83         if (strcasecmp(pp->key, key) == 0)
  84             return pp->value;
  85     return NULL;
  86 }
  87
  88 /*
  89  * Parse BIGNUM, return number of bytes parsed.
  90  */
  91 static int parseBN(BIGNUM **out, const char *in)
  92 {
  93     *out = NULL;
  94     return BN_hex2bn(out, in);
  95 }
  96
  97 static int parsedecBN(BIGNUM **out, const char *in)
  98 {
  99     *out = NULL;
 100     return BN_dec2bn(out, in);
 101 }
 102
 103 static BIGNUM *getBN(STANZA *s, const char *attribute)
 104 {
 105     const char *hex;
 106     BIGNUM *ret = NULL;
 107
 108     if ((hex = findattr(s, attribute)) == NULL) {
 109         fprintf(stderr, "Can't find %s in test at line %d\n",
 110                 attribute, s->start);
 111         return NULL;
 112     }
 113
 114     if (parseBN(&ret, hex) != (int)strlen(hex)) {
 115         fprintf(stderr, "Could not decode '%s'.\n", hex);
 116         return NULL;
 117     }
 118     return ret;
 119 }
 120
 121 static int getint(STANZA *s, int *out, const char *attribute)
 122 {
 123     BIGNUM *ret = getBN(s, attribute);
 124     BN_ULONG word;
 125     int st = 0;
 126
 127     if (ret == NULL)
 128         goto err;
 129
 130     if ((word = BN_get_word(ret)) > INT_MAX)
 131         goto err;
 132
 133     *out = (int)word;
 134     st = 1;
 135 err:
 136     BN_free(ret);
 137     return st;
 138 }
 139
 140 static int equalBN(const char *op, const BIGNUM *expected, const BIGNUM *actual)
 141 {
 142     char *exstr = NULL;
 143     char *actstr = NULL;
 144
 145     if (BN_cmp(expected, actual) == 0)
 146         return 1;
 147
 148     if (BN_is_zero(expected) && BN_is_negative(expected))
 149         exstr = OPENSSL_strdup("-0");
 150     else
 151         exstr = BN_bn2hex(expected);
 152     if (BN_is_zero(actual) && BN_is_negative(actual))
 153         actstr = OPENSSL_strdup("-0");
 154     else
 155         actstr = BN_bn2hex(actual);
 156     if (exstr == NULL || actstr == NULL)
 157         goto err;
 158
 159     fprintf(stderr, "Got %s =\n", op);
 160     fprintf(stderr, "\t%s\n", actstr);
 161     fprintf(stderr, "wanted:\n");
 162     fprintf(stderr, "\t%s\n", exstr);
 163
 164 err:
 165     OPENSSL_free(exstr);
 166     OPENSSL_free(actstr);
 167     return 0;
 168 }
 169
 170
 171 /*
 172  * Return a "random" flag for if a BN should be negated.
 173  */
 174 static int rand_neg(void)
 175 {
 176     static unsigned int neg = 0;
 177     static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };
 178
 179     return sign[(neg++) % 8];
 180 }
 181
 182
 183 static int test_sub()
 184 {
 185     BIGNUM *a, *b, *c;
 186     int i;
 187
 188     a = BN_new();
 189     b = BN_new();
 190     c = BN_new();
 191
 192     for (i = 0; i < NUM0 + NUM1; i++) {
 193         if (i < NUM1) {
 194             BN_bntest_rand(a, 512, 0, 0);
 195             BN_copy(b, a);
 196             if (BN_set_bit(a, i) == 0)
 197                 return 0;
 198             BN_add_word(b, i);
 199         } else {
 200             BN_bntest_rand(b, 400 + i - NUM1, 0, 0);
 201             a->neg = rand_neg();
 202             b->neg = rand_neg();
 203         }
 204         BN_sub(c, a, b);
 205         BN_add(c, c, b);
 206         BN_sub(c, c, a);
 207         if (!BN_is_zero(c)) {
 208             printf("Subtract test failed!\n");
 209             return 0;
 210         }
 211     }
 212     BN_free(a);
 213     BN_free(b);
 214     BN_free(c);
 215     return 1;
 216 }
 217
 218
 219 static int test_div_recip()
 220 {
 221     BIGNUM *a, *b, *c, *d, *e;
 222     BN_RECP_CTX *recp;
 223     int i;
 224
 225     recp = BN_RECP_CTX_new();
 226     a = BN_new();
 227     b = BN_new();
 228     c = BN_new();
 229     d = BN_new();
 230     e = BN_new();
 231
 232     for (i = 0; i < NUM0 + NUM1; i++) {
 233         if (i < NUM1) {
 234             BN_bntest_rand(a, 400, 0, 0);
 235             BN_copy(b, a);
 236             BN_lshift(a, a, i);
 237             BN_add_word(a, i);
 238         } else
 239             BN_bntest_rand(b, 50 + 3 * (i - NUM1), 0, 0);
 240         a->neg = rand_neg();
 241         b->neg = rand_neg();
 242         BN_RECP_CTX_set(recp, b, ctx);
 243         BN_div_recp(d, c, a, recp, ctx);
 244         BN_mul(e, d, b, ctx);
 245         BN_add(d, e, c);
 246         BN_sub(d, d, a);
 247         if (!BN_is_zero(d)) {
 248             printf("Reciprocal division test failed!\n");
 249             printf("a=");
 250             BN_print_fp(stdout, a);
 251             printf("\nb=");
 252             BN_print_fp(stdout, b);
 253             printf("\n");
 254             return 0;
 255         }
 256     }
 257     BN_free(a);
 258     BN_free(b);
 259     BN_free(c);
 260     BN_free(d);
 261     BN_free(e);
 262     BN_RECP_CTX_free(recp);
 263     return 1;
 264 }
 265
 266
 267 static int test_mod()
 268 {
 269     BIGNUM *a, *b, *c, *d, *e;
 270     int i;
 271
 272     a = BN_new();
 273     b = BN_new();
 274     c = BN_new();
 275     d = BN_new();
 276     e = BN_new();
 277
 278     BN_bntest_rand(a, 1024, 0, 0);
 279     for (i = 0; i < NUM0; i++) {
 280         BN_bntest_rand(b, 450 + i * 10, 0, 0);
 281         a->neg = rand_neg();
 282         b->neg = rand_neg();
 283         BN_mod(c, a, b, ctx);
 284         BN_div(d, e, a, b, ctx);
 285         BN_sub(e, e, c);
 286         if (!BN_is_zero(e)) {
 287             printf("Modulo test failed!\n");
 288             return 0;
 289         }
 290     }
 291     BN_free(a);
 292     BN_free(b);
 293     BN_free(c);
 294     BN_free(d);
 295     BN_free(e);
 296     return 1;
 297 }
 298
 299 static const char *bn1strings[] = {
 300     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 301     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 302     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 303     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 304     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 305     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 306     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 307     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF00",
 308     "0000000000000000000000000000000000000000000000000000000000000000",
 309     "0000000000000000000000000000000000000000000000000000000000000000",
 310     "0000000000000000000000000000000000000000000000000000000000000000",
 311     "0000000000000000000000000000000000000000000000000000000000000000",
 312     "0000000000000000000000000000000000000000000000000000000000000000",
 313     "0000000000000000000000000000000000000000000000000000000000000000",
 314     "0000000000000000000000000000000000000000000000000000000000000000",
 315     "00000000000000000000000000000000000000000000000000FFFFFFFFFFFFFF",
 316     NULL
 317 };
 318
 319 static const char *bn2strings[] = {
 320     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 321     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 322     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 323     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 324     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 325     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 326     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 327     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF0000000000",
 328     "0000000000000000000000000000000000000000000000000000000000000000",
 329     "0000000000000000000000000000000000000000000000000000000000000000",
 330     "0000000000000000000000000000000000000000000000000000000000000000",
 331     "0000000000000000000000000000000000000000000000000000000000000000",
 332     "0000000000000000000000000000000000000000000000000000000000000000",
 333     "0000000000000000000000000000000000000000000000000000000000000000",
 334     "0000000000000000000000000000000000000000000000000000000000000000",
 335     "000000000000000000000000000000000000000000FFFFFFFFFFFFFF00000000",
 336     NULL
 337 };
 338
 339 static char *glue(const char *list[])
 340 {
 341     size_t len = 0;
 342     char *p, *save;
 343     int i;
 344
 345     for (i = 0; list[i] != NULL; i++)
 346         len += strlen(list[i]);
 347     p = save = OPENSSL_malloc(len + 1);
 348     if (p != NULL) {
 349         for (i = 0; list[i] != NULL; i++)
 350             p += strlen(strcpy(p, list[i]));
 351     }
 352     return save;
 353 }
 354
 355 /*
 356  * Test constant-time modular exponentiation with 1024-bit inputs, which on
 357  * x86_64 cause a different code branch to be taken.
 358  */
 359 static int test_modexp_mont5()
 360 {
 361     BIGNUM *a, *p, *m, *d, *e, *b, *n, *c;
 362     BN_MONT_CTX *mont;
 363     char *bigstring;
 364
 365     a = BN_new();
 366     p = BN_new();
 367     m = BN_new();
 368     d = BN_new();
 369     e = BN_new();
 370     b = BN_new();
 371     n = BN_new();
 372     c = BN_new();
 373     mont = BN_MONT_CTX_new();
 374
 375     BN_bntest_rand(m, 1024, 0, 1); /* must be odd for montgomery */
 376     /* Zero exponent */
 377     BN_bntest_rand(a, 1024, 0, 0);
 378     BN_zero(p);
 379     if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
 380         return 0;
 381     if (!BN_is_one(d)) {
 382         printf("Modular exponentiation test failed!\n");
 383         return 0;
 384     }
 385
 386     /* Regression test for carry bug in mulx4x_mont */
 387     BN_hex2bn(&a,
 388         "7878787878787878787878787878787878787878787878787878787878787878"
 389         "7878787878787878787878787878787878787878787878787878787878787878"
 390         "7878787878787878787878787878787878787878787878787878787878787878"
 391         "7878787878787878787878787878787878787878787878787878787878787878");
 392     BN_hex2bn(&b,
 393         "095D72C08C097BA488C5E439C655A192EAFB6380073D8C2664668EDDB4060744"
 394         "E16E57FB4EDB9AE10A0CEFCDC28A894F689A128379DB279D48A2E20849D68593"
 395         "9B7803BCF46CEBF5C533FB0DD35B080593DE5472E3FE5DB951B8BFF9B4CB8F03"
 396         "9CC638A5EE8CDD703719F8000E6A9F63BEED5F2FCD52FF293EA05A251BB4AB81");
 397     BN_hex2bn(&n,
 398         "D78AF684E71DB0C39CFF4E64FB9DB567132CB9C50CC98009FEB820B26F2DED9B"
 399         "91B9B5E2B83AE0AE4EB4E0523CA726BFBE969B89FD754F674CE99118C3F2D1C5"
 400         "D81FDC7C54E02B60262B241D53C040E99E45826ECA37A804668E690E1AFC1CA4"
 401         "2C9A15D84D4954425F0B7642FC0BD9D7B24E2618D2DCC9B729D944BADACFDDAF");
 402     BN_MONT_CTX_set(mont, n, ctx);
 403     BN_mod_mul_montgomery(c, a, b, mont, ctx);
 404     BN_mod_mul_montgomery(d, b, a, mont, ctx);
 405     if (BN_cmp(c, d)) {
 406         fprintf(stderr, "Montgomery multiplication test failed:"
 407                         " a*b != b*a.\n");
 408         return 0;
 409     }
 410
 411     /* Regression test for carry bug in sqr[x]8x_mont */
 412     bigstring = glue(bn1strings);
 413     BN_hex2bn(&n, bigstring);
 414     OPENSSL_free(bigstring);
 415     bigstring = glue(bn2strings);
 416     BN_hex2bn(&a, bigstring);
 417     OPENSSL_free(bigstring);
 418     BN_free(b);
 419     b = BN_dup(a);
 420     BN_MONT_CTX_set(mont, n, ctx);
 421     BN_mod_mul_montgomery(c, a, a, mont, ctx);
 422     BN_mod_mul_montgomery(d, a, b, mont, ctx);
 423     if (BN_cmp(c, d)) {
 424         fprintf(stderr, "Montgomery multiplication test failed:"
 425                         " a**2 != a*a.\n");
 426         return 0;
 427     }
 428
 429     /* Zero input */
 430     BN_bntest_rand(p, 1024, 0, 0);
 431     BN_zero(a);
 432     if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
 433         return 0;
 434     if (!BN_is_zero(d)) {
 435         fprintf(stderr, "Modular exponentiation test failed!\n");
 436         return 0;
 437     }
 438     /*
 439      * Craft an input whose Montgomery representation is 1, i.e., shorter
 440      * than the modulus m, in order to test the const time precomputation
 441      * scattering/gathering.
 442      */
 443     BN_one(a);
 444     BN_MONT_CTX_set(mont, m, ctx);
 445     if (!BN_from_montgomery(e, a, mont, ctx))
 446         return 0;
 447     if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
 448         return 0;
 449     if (!BN_mod_exp_simple(a, e, p, m, ctx))
 450         return 0;
 451     if (BN_cmp(a, d) != 0) {
 452         printf("Modular exponentiation test failed!\n");
 453         return 0;
 454     }
 455     /* Finally, some regular test vectors. */
 456     BN_bntest_rand(e, 1024, 0, 0);
 457     if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
 458         return 0;
 459     if (!BN_mod_exp_simple(a, e, p, m, ctx))
 460         return 0;
 461     if (BN_cmp(a, d) != 0) {
 462         printf("Modular exponentiation test failed!\n");
 463         return 0;
 464     }
 465     BN_MONT_CTX_free(mont);
 466     BN_free(a);
 467     BN_free(p);
 468     BN_free(m);
 469     BN_free(d);
 470     BN_free(e);
 471     BN_free(b);
 472     BN_free(n);
 473     BN_free(c);
 474     return 1;
 475 }
 476
 477 #ifndef OPENSSL_NO_EC2M
 478 static int test_gf2m_add()
 479 {
 480     BIGNUM *a, *b, *c;
 481     int i, st = 0;
 482
 483     a = BN_new();
 484     b = BN_new();
 485     c = BN_new();
 486
 487     for (i = 0; i < NUM0; i++) {
 488         BN_rand(a, 512, 0, 0);
 489         BN_copy(b, BN_value_one());
 490         a->neg = rand_neg();
 491         b->neg = rand_neg();
 492         BN_GF2m_add(c, a, b);
 493         /* Test that two added values have the correct parity. */
 494         if ((BN_is_odd(a) && BN_is_odd(c))
 495             || (!BN_is_odd(a) && !BN_is_odd(c))) {
 496             printf("GF(2^m) addition test (a) failed!\n");
 497             goto err;
 498         }
 499         BN_GF2m_add(c, c, c);
 500         /* Test that c + c = 0. */
 501         if (!BN_is_zero(c)) {
 502             printf("GF(2^m) addition test (b) failed!\n");
 503             goto err;
 504         }
 505     }
 506     st = 1;
 507  err:
 508     BN_free(a);
 509     BN_free(b);
 510     BN_free(c);
 511     return st;
 512 }
 513
 514 static int test_gf2m_mod()
 515 {
 516     static int p0[] = { 163, 7, 6, 3, 0, -1 };
 517     static int p1[] = { 193, 15, 0, -1 };
 518     BIGNUM *a, *b[2], *c, *d, *e;
 519     int i, j, st = 0;
 520
 521     a = BN_new();
 522     b[0] = BN_new();
 523     b[1] = BN_new();
 524     c = BN_new();
 525     d = BN_new();
 526     e = BN_new();
 527
 528     BN_GF2m_arr2poly(p0, b[0]);
 529     BN_GF2m_arr2poly(p1, b[1]);
 530
 531     for (i = 0; i < NUM0; i++) {
 532         BN_bntest_rand(a, 1024, 0, 0);
 533         for (j = 0; j < 2; j++) {
 534             BN_GF2m_mod(c, a, b[j]);
 535             BN_GF2m_add(d, a, c);
 536             BN_GF2m_mod(e, d, b[j]);
 537             /* Test that a + (a mod p) mod p == 0. */
 538             if (!BN_is_zero(e)) {
 539                 printf("GF(2^m) modulo test failed!\n");
 540                 goto err;
 541             }
 542         }
 543     }
 544     st = 1;
 545  err:
 546     BN_free(a);
 547     BN_free(b[0]);
 548     BN_free(b[1]);
 549     BN_free(c);
 550     BN_free(d);
 551     BN_free(e);
 552     return st;
 553 }
 554
 555 static int test_gf2m_mul()
 556 {
 557     BIGNUM *a, *b[2], *c, *d, *e, *f, *g, *h;
 558     int i, j, st = 0;
 559     int p0[] = { 163, 7, 6, 3, 0, -1 };
 560     int p1[] = { 193, 15, 0, -1 };
 561
 562     a = BN_new();
 563     b[0] = BN_new();
 564     b[1] = BN_new();
 565     c = BN_new();
 566     d = BN_new();
 567     e = BN_new();
 568     f = BN_new();
 569     g = BN_new();
 570     h = BN_new();
 571
 572     BN_GF2m_arr2poly(p0, b[0]);
 573     BN_GF2m_arr2poly(p1, b[1]);
 574
 575     for (i = 0; i < NUM0; i++) {
 576         BN_bntest_rand(a, 1024, 0, 0);
 577         BN_bntest_rand(c, 1024, 0, 0);
 578         BN_bntest_rand(d, 1024, 0, 0);
 579         for (j = 0; j < 2; j++) {
 580             BN_GF2m_mod_mul(e, a, c, b[j], ctx);
 581             BN_GF2m_add(f, a, d);
 582             BN_GF2m_mod_mul(g, f, c, b[j], ctx);
 583             BN_GF2m_mod_mul(h, d, c, b[j], ctx);
 584             BN_GF2m_add(f, e, g);
 585             BN_GF2m_add(f, f, h);
 586             /* Test that (a+d)*c = a*c + d*c. */
 587             if (!BN_is_zero(f)) {
 588                 printf("GF(2^m) modular multiplication test failed!\n");
 589                 goto err;
 590             }
 591         }
 592     }
 593     st = 1;
 594  err:
 595     BN_free(a);
 596     BN_free(b[0]);
 597     BN_free(b[1]);
 598     BN_free(c);
 599     BN_free(d);
 600     BN_free(e);
 601     BN_free(f);
 602     BN_free(g);
 603     BN_free(h);
 604     return st;
 605 }
 606
 607 static int test_gf2m_sqr()
 608 {
 609     BIGNUM *a, *b[2], *c, *d;
 610     int i, j, st = 0;
 611     int p0[] = { 163, 7, 6, 3, 0, -1 };
 612     int p1[] = { 193, 15, 0, -1 };
 613
 614     a = BN_new();
 615     b[0] = BN_new();
 616     b[1] = BN_new();
 617     c = BN_new();
 618     d = BN_new();
 619
 620     BN_GF2m_arr2poly(p0, b[0]);
 621     BN_GF2m_arr2poly(p1, b[1]);
 622
 623     for (i = 0; i < NUM0; i++) {
 624         BN_bntest_rand(a, 1024, 0, 0);
 625         for (j = 0; j < 2; j++) {
 626             BN_GF2m_mod_sqr(c, a, b[j], ctx);
 627             BN_copy(d, a);
 628             BN_GF2m_mod_mul(d, a, d, b[j], ctx);
 629             BN_GF2m_add(d, c, d);
 630             /* Test that a*a = a^2. */
 631             if (!BN_is_zero(d)) {
 632                 printf("GF(2^m) modular squaring test failed!\n");
 633                 goto err;
 634             }
 635         }
 636     }
 637     st = 1;
 638  err:
 639     BN_free(a);
 640     BN_free(b[0]);
 641     BN_free(b[1]);
 642     BN_free(c);
 643     BN_free(d);
 644     return st;
 645 }
 646
 647 static int test_gf2m_modinv()
 648 {
 649     BIGNUM *a, *b[2], *c, *d;
 650     int i, j, st = 0;
 651     int p0[] = { 163, 7, 6, 3, 0, -1 };
 652     int p1[] = { 193, 15, 0, -1 };
 653
 654     a = BN_new();
 655     b[0] = BN_new();
 656     b[1] = BN_new();
 657     c = BN_new();
 658     d = BN_new();
 659
 660     BN_GF2m_arr2poly(p0, b[0]);
 661     BN_GF2m_arr2poly(p1, b[1]);
 662
 663     for (i = 0; i < NUM0; i++) {
 664         BN_bntest_rand(a, 512, 0, 0);
 665         for (j = 0; j < 2; j++) {
 666             BN_GF2m_mod_inv(c, a, b[j], ctx);
 667             BN_GF2m_mod_mul(d, a, c, b[j], ctx);
 668             /* Test that ((1/a)*a) = 1. */
 669             if (!BN_is_one(d)) {
 670                 printf("GF(2^m) modular inversion test failed!\n");
 671                 goto err;
 672             }
 673         }
 674     }
 675     st = 1;
 676  err:
 677     BN_free(a);
 678     BN_free(b[0]);
 679     BN_free(b[1]);
 680     BN_free(c);
 681     BN_free(d);
 682     return st;
 683 }
 684
 685 static int test_gf2m_moddiv()
 686 {
 687     BIGNUM *a, *b[2], *c, *d, *e, *f;
 688     int i, j, st = 0;
 689     int p0[] = { 163, 7, 6, 3, 0, -1 };
 690     int p1[] = { 193, 15, 0, -1 };
 691
 692     a = BN_new();
 693     b[0] = BN_new();
 694     b[1] = BN_new();
 695     c = BN_new();
 696     d = BN_new();
 697     e = BN_new();
 698     f = BN_new();
 699
 700     BN_GF2m_arr2poly(p0, b[0]);
 701     BN_GF2m_arr2poly(p1, b[1]);
 702
 703     for (i = 0; i < NUM0; i++) {
 704         BN_bntest_rand(a, 512, 0, 0);
 705         BN_bntest_rand(c, 512, 0, 0);
 706         for (j = 0; j < 2; j++) {
 707             BN_GF2m_mod_div(d, a, c, b[j], ctx);
 708             BN_GF2m_mod_mul(e, d, c, b[j], ctx);
 709             BN_GF2m_mod_div(f, a, e, b[j], ctx);
 710             /* Test that ((a/c)*c)/a = 1. */
 711             if (!BN_is_one(f)) {
 712                 printf("GF(2^m) modular division test failed!\n");
 713                 goto err;
 714             }
 715         }
 716     }
 717     st = 1;
 718  err:
 719     BN_free(a);
 720     BN_free(b[0]);
 721     BN_free(b[1]);
 722     BN_free(c);
 723     BN_free(d);
 724     BN_free(e);
 725     BN_free(f);
 726     return st;
 727 }
 728
 729 static int test_gf2m_modexp()
 730 {
 731     BIGNUM *a, *b[2], *c, *d, *e, *f;
 732     int i, j, st = 0;
 733     int p0[] = { 163, 7, 6, 3, 0, -1 };
 734     int p1[] = { 193, 15, 0, -1 };
 735
 736     a = BN_new();
 737     b[0] = BN_new();
 738     b[1] = BN_new();
 739     c = BN_new();
 740     d = BN_new();
 741     e = BN_new();
 742     f = BN_new();
 743
 744     BN_GF2m_arr2poly(p0, b[0]);
 745     BN_GF2m_arr2poly(p1, b[1]);
 746
 747     for (i = 0; i < NUM0; i++) {
 748         BN_bntest_rand(a, 512, 0, 0);
 749         BN_bntest_rand(c, 512, 0, 0);
 750         BN_bntest_rand(d, 512, 0, 0);
 751         for (j = 0; j < 2; j++) {
 752             BN_GF2m_mod_exp(e, a, c, b[j], ctx);
 753             BN_GF2m_mod_exp(f, a, d, b[j], ctx);
 754             BN_GF2m_mod_mul(e, e, f, b[j], ctx);
 755             BN_add(f, c, d);
 756             BN_GF2m_mod_exp(f, a, f, b[j], ctx);
 757             BN_GF2m_add(f, e, f);
 758             /* Test that a^(c+d)=a^c*a^d. */
 759             if (!BN_is_zero(f)) {
 760                 printf("GF(2^m) modular exponentiation test failed!\n");
 761                 goto err;
 762             }
 763         }
 764     }
 765     st = 1;
 766  err:
 767     BN_free(a);
 768     BN_free(b[0]);
 769     BN_free(b[1]);
 770     BN_free(c);
 771     BN_free(d);
 772     BN_free(e);
 773     BN_free(f);
 774     return st;
 775 }
 776
 777 static int test_gf2m_modsqrt()
 778 {
 779     BIGNUM *a, *b[2], *c, *d, *e, *f;
 780     int i, j, st = 0;
 781     int p0[] = { 163, 7, 6, 3, 0, -1 };
 782     int p1[] = { 193, 15, 0, -1 };
 783
 784     a = BN_new();
 785     b[0] = BN_new();
 786     b[1] = BN_new();
 787     c = BN_new();
 788     d = BN_new();
 789     e = BN_new();
 790     f = BN_new();
 791
 792     BN_GF2m_arr2poly(p0, b[0]);
 793     BN_GF2m_arr2poly(p1, b[1]);
 794
 795     for (i = 0; i < NUM0; i++) {
 796         BN_bntest_rand(a, 512, 0, 0);
 797         for (j = 0; j < 2; j++) {
 798             BN_GF2m_mod(c, a, b[j]);
 799             BN_GF2m_mod_sqrt(d, a, b[j], ctx);
 800             BN_GF2m_mod_sqr(e, d, b[j], ctx);
 801             BN_GF2m_add(f, c, e);
 802             /* Test that d^2 = a, where d = sqrt(a). */
 803             if (!BN_is_zero(f)) {
 804                 printf("GF(2^m) modular square root test failed!\n");
 805                 goto err;
 806             }
 807         }
 808     }
 809     st = 1;
 810  err:
 811     BN_free(a);
 812     BN_free(b[0]);
 813     BN_free(b[1]);
 814     BN_free(c);
 815     BN_free(d);
 816     BN_free(e);
 817     BN_free(f);
 818     return st;
 819 }
 820
 821 static int test_gf2m_modsolvequad()
 822 {
 823     BIGNUM *a, *b[2], *c, *d, *e;
 824     int i, j, s = 0, t, st = 0;
 825     int p0[] = { 163, 7, 6, 3, 0, -1 };
 826     int p1[] = { 193, 15, 0, -1 };
 827
 828     a = BN_new();
 829     b[0] = BN_new();
 830     b[1] = BN_new();
 831     c = BN_new();
 832     d = BN_new();
 833     e = BN_new();
 834
 835     BN_GF2m_arr2poly(p0, b[0]);
 836     BN_GF2m_arr2poly(p1, b[1]);
 837
 838     for (i = 0; i < NUM0; i++) {
 839         BN_bntest_rand(a, 512, 0, 0);
 840         for (j = 0; j < 2; j++) {
 841             t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
 842             if (t) {
 843                 s++;
 844                 BN_GF2m_mod_sqr(d, c, b[j], ctx);
 845                 BN_GF2m_add(d, c, d);
 846                 BN_GF2m_mod(e, a, b[j]);
 847                 BN_GF2m_add(e, e, d);
 848                 /*
 849                  * Test that solution of quadratic c satisfies c^2 + c = a.
 850                  */
 851                 if (!BN_is_zero(e)) {
 852                     printf("GF(2^m) modular solve quadratic test failed!\n");
 853                     goto err;
 854                 }
 855
 856             }
 857         }
 858     }
 859     if (s == 0) {
 860         printf("All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n",
 861                 NUM0);
 862         printf("this is very unlikely and probably indicates an error.\n");
 863         goto err;
 864     }
 865     st = 1;
 866  err:
 867     BN_free(a);
 868     BN_free(b[0]);
 869     BN_free(b[1]);
 870     BN_free(c);
 871     BN_free(d);
 872     BN_free(e);
 873     return st;
 874 }
 875 #endif
 876
 877 static int test_kronecker()
 878 {
 879     BIGNUM *a, *b, *r, *t;
 880     int i;
 881     int legendre, kronecker;
 882     int st = 0;
 883
 884     a = BN_new();
 885     b = BN_new();
 886     r = BN_new();
 887     t = BN_new();
 888     if (a == NULL || b == NULL || r == NULL || t == NULL)
 889         goto err;
 890
 891     /*
 892      * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
 893      * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
 894      * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
 895      * generate a random prime b and compare these values for a number of
 896      * random a's.  (That is, we run the Solovay-Strassen primality test to
 897      * confirm that b is prime, except that we don't want to test whether b
 898      * is prime but whether BN_kronecker works.)
 899      */
 900
 901     if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, NULL))
 902         goto err;
 903     b->neg = rand_neg();
 904
 905     for (i = 0; i < NUM0; i++) {
 906         if (!BN_bntest_rand(a, 512, 0, 0))
 907             goto err;
 908         a->neg = rand_neg();
 909
 910         /* t := (|b|-1)/2  (note that b is odd) */
 911         if (!BN_copy(t, b))
 912             goto err;
 913         t->neg = 0;
 914         if (!BN_sub_word(t, 1))
 915             goto err;
 916         if (!BN_rshift1(t, t))
 917             goto err;
 918         /* r := a^t mod b */
 919         b->neg = 0;
 920
 921         if (!BN_mod_exp_recp(r, a, t, b, ctx))
 922             goto err;
 923         b->neg = 1;
 924
 925         if (BN_is_word(r, 1))
 926             legendre = 1;
 927         else if (BN_is_zero(r))
 928             legendre = 0;
 929         else {
 930             if (!BN_add_word(r, 1))
 931                 goto err;
 932             if (0 != BN_ucmp(r, b)) {
 933                 printf("Legendre symbol computation failed\n");
 934                 goto err;
 935             }
 936             legendre = -1;
 937         }
 938
 939         kronecker = BN_kronecker(a, b, ctx);
 940         if (kronecker < -1)
 941             goto err;
 942         /* we actually need BN_kronecker(a, |b|) */
 943         if (a->neg && b->neg)
 944             kronecker = -kronecker;
 945
 946         if (legendre != kronecker) {
 947             printf("legendre != kronecker; a = ");
 948             BN_print_fp(stdout, a);
 949             printf(", b = ");
 950             BN_print_fp(stdout, b);
 951             printf("\n");
 952             goto err;
 953         }
 954     }
 955
 956     st = 1;
 957  err:
 958     BN_free(a);
 959     BN_free(b);
 960     BN_free(r);
 961     BN_free(t);
 962     return st;
 963 }
 964
 965 static int file_sum(STANZA *s)
 966 {
 967     BIGNUM *a = getBN(s, "A");
 968     BIGNUM *b = getBN(s, "B");
 969     BIGNUM *sum = getBN(s, "Sum");
 970     BIGNUM *ret = BN_new();
 971     BN_ULONG b_word;
 972     int st = 0;
 973
 974     if (a == NULL || b == NULL || sum == NULL || ret == NULL)
 975         goto err;
 976
 977     if (!BN_add(ret, a, b)
 978             || !equalBN("A + B", sum, ret)
 979             || !BN_sub(ret, sum, a)
 980             || !equalBN("Sum - A", b, ret)
 981             || !BN_sub(ret, sum, b)
 982             || !equalBN("Sum - B", a, ret))
 983         goto err;
 984
 985     /*
 986      * Test that the functions work when |r| and |a| point to the same BIGNUM,
 987      * or when |r| and |b| point to the same BIGNUM.
 988      * TODO: Test where all of |r|, |a|, and |b| point to the same BIGNUM.
 989      */
 990     if (!BN_copy(ret, a)
 991             || !BN_add(ret, ret, b)
 992             || !equalBN("A + B (r is a)", sum, ret)
 993             || !BN_copy(ret, b)
 994             || !BN_add(ret, a, ret)
 995             || !equalBN("A + B (r is b)", sum, ret)
 996             || !BN_copy(ret, sum)
 997             || !BN_sub(ret, ret, a)
 998             || !equalBN("Sum - A (r is a)", b, ret)
 999             || !BN_copy(ret, a)
1000             || !BN_sub(ret, sum, ret)
1001             || !equalBN("Sum - A (r is b)", b, ret)
1002             || !BN_copy(ret, sum)
1003             || !BN_sub(ret, ret, b)
1004             || !equalBN("Sum - B (r is a)", a, ret)
1005             || !BN_copy(ret, b)
1006             || !BN_sub(ret, sum, ret)
1007             || !equalBN("Sum - B (r is b)", a, ret))
1008         goto err;
1009
1010     /*
1011      * Test BN_uadd() and BN_usub() with the prerequisites they are
1012      * documented as having. Note that these functions are frequently used
1013      * when the prerequisites don't hold. In those cases, they are supposed
1014      * to work as if the prerequisite hold, but we don't test that yet.
1015      * TODO: test that.
1016      */
1017     if (!BN_is_negative(a) && !BN_is_negative(b) && BN_cmp(a, b) >= 0) {
1018         if (!BN_uadd(ret, a, b)
1019                 || !equalBN("A +u B", sum, ret)
1020                 || !BN_usub(ret, sum, a)
1021                 || !equalBN("Sum -u A", b, ret)
1022                 || !BN_usub(ret, sum, b)
1023                 || !equalBN("Sum -u B", a, ret))
1024             goto err;
1025         /*
1026          * Test that the functions work when |r| and |a| point to the same
1027          * BIGNUM, or when |r| and |b| point to the same BIGNUM.
1028          * TODO: Test where all of |r|, |a|, and |b| point to the same BIGNUM.
1029          */
1030         if (!BN_copy(ret, a)
1031                 || !BN_uadd(ret, ret, b)
1032                 || !equalBN("A +u B (r is a)", sum, ret)
1033                 || !BN_copy(ret, b)
1034                 || !BN_uadd(ret, a, ret)
1035                 || !equalBN("A +u B (r is b)", sum, ret)
1036                 || !BN_copy(ret, sum)
1037                 || !BN_usub(ret, ret, a)
1038                 || !equalBN("Sum -u A (r is a)", b, ret)
1039                 || !BN_copy(ret, a)
1040                 || !BN_usub(ret, sum, ret)
1041                 || !equalBN("Sum -u A (r is b)", b, ret)
1042                 || !BN_copy(ret, sum)
1043                 || !BN_usub(ret, ret, b)
1044                 || !equalBN("Sum -u B (r is a)", a, ret)
1045                 || !BN_copy(ret, b)
1046                 || !BN_usub(ret, sum, ret)
1047                 || !equalBN("Sum -u B (r is b)", a, ret))
1048             goto err;
1049     }
1050
1051     /*
1052      * Test with BN_add_word() and BN_sub_word() if |b| is small enough.
1053      */
1054     b_word = BN_get_word(b);
1055     if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
1056         if (!BN_copy(ret, a)
1057                 || !BN_add_word(ret, b_word)
1058                 || !equalBN("A + B (word)", sum, ret)
1059                 || !BN_copy(ret, sum)
1060                 || !BN_sub_word(ret, b_word)
1061                 || !equalBN("Sum - B (word)", a, ret))
1062             goto err;
1063     }
1064     st = 1;
1065
1066 err:
1067     BN_free(a);
1068     BN_free(b);
1069     BN_free(sum);
1070     BN_free(ret);
1071     return st;
1072 }
1073
1074 static int file_lshift1(STANZA *s)
1075 {
1076     BIGNUM *a = getBN(s, "A");
1077     BIGNUM *lshift1 = getBN(s, "LShift1");
1078     BIGNUM *zero = BN_new();
1079     BIGNUM *ret = BN_new();
1080     BIGNUM *two = BN_new();
1081     BIGNUM *remainder = BN_new();
1082     int st = 0;
1083
1084     if (a == NULL || lshift1 == NULL || zero == NULL
1085             || ret == NULL || two == NULL || remainder == NULL)
1086         goto err;
1087
1088     BN_zero(zero);
1089
1090     if (!BN_set_word(two, 2)
1091             || !BN_add(ret, a, a)
1092             || !equalBN("A + A", lshift1, ret)
1093             || !BN_mul(ret, a, two, ctx)
1094             || !equalBN("A * 2", lshift1, ret)
1095             || !BN_div(ret, remainder, lshift1, two, ctx)
1096             || !equalBN("LShift1 / 2", a, ret)
1097             || !equalBN("LShift1 % 2", zero, remainder)
1098             || !BN_lshift1(ret, a)
1099             || !equalBN("A << 1", lshift1, ret)
1100             || !BN_rshift1(ret, lshift1)
1101             || !equalBN("LShift >> 1", a, ret)
1102             || !BN_rshift1(ret, lshift1)
1103             || !equalBN("LShift >> 1", a, ret))
1104         goto err;
1105
1106     /* Set the LSB to 1 and test rshift1 again. */
1107     if (!BN_set_bit(lshift1, 0)
1108             || !BN_div(ret, NULL /* rem */ , lshift1, two, ctx)
1109             || !equalBN("(LShift1 | 1) / 2", a, ret)
1110             || !BN_rshift1(ret, lshift1)
1111             || !equalBN("(LShift | 1) >> 1", a, ret))
1112         goto err;
1113
1114     st = 1;
1115 err:
1116     BN_free(a);
1117     BN_free(lshift1);
1118     BN_free(zero);
1119     BN_free(ret);
1120     BN_free(two);
1121     BN_free(remainder);
1122
1123     return st;
1124 }
1125
1126 static int file_lshift(STANZA *s)
1127 {
1128     BIGNUM *a = getBN(s, "A");
1129     BIGNUM *lshift = getBN(s, "LShift");
1130     BIGNUM *ret = BN_new();
1131     int n = 0;
1132     int st = 0;
1133
1134     if (a == NULL || lshift == NULL || ret == NULL || !getint(s, &n, "N"))
1135         goto err;
1136
1137     if (!BN_lshift(ret, a, n)
1138             || !equalBN("A << N", lshift, ret)
1139             || !BN_rshift(ret, lshift, n)
1140             || !equalBN("A >> N", a, ret))
1141         goto err;
1142
1143     st = 1;
1144 err:
1145     BN_free(a);
1146     BN_free(lshift);
1147     BN_free(ret);
1148     return st;
1149 }
1150
1151 static int file_rshift(STANZA *s)
1152 {
1153     BIGNUM *a = getBN(s, "A");
1154     BIGNUM *rshift = getBN(s, "RShift");
1155     BIGNUM *ret = BN_new();
1156     int n = 0;
1157     int errcnt = 1;
1158
1159     if (a == NULL || rshift == NULL || ret == NULL || !getint(s, &n, "N"))
1160         goto err;
1161
1162     errcnt = 0;
1163     if (!BN_rshift(ret, a, n)
1164             || !equalBN("A >> N", rshift, ret))
1165         errcnt++;
1166
1167     /* If N == 1, try with rshift1 as well */
1168     if (n == 1) {
1169         if (!BN_rshift1(ret, a)
1170                 || !equalBN("A >> 1 (rshift1)", rshift, ret))
1171             errcnt++;
1172     }
1173
1174 err:
1175     BN_free(a);
1176     BN_free(rshift);
1177     BN_free(ret);
1178     return errcnt == 0;
1179 }
1180
1181 static int file_square(STANZA *s)
1182 {
1183     BIGNUM *a = getBN(s, "A");
1184     BIGNUM *square = getBN(s, "Square");
1185     BIGNUM *zero = BN_new();
1186     BIGNUM *ret = BN_new();
1187     BIGNUM *remainder = BN_new();
1188     BIGNUM *tmp = NULL;
1189     int st = 0;
1190
1191     if (a == NULL || square == NULL || zero == NULL || ret == NULL
1192             || remainder == NULL)
1193         goto err;
1194
1195     BN_zero(zero);
1196
1197     if (!BN_sqr(ret, a, ctx)
1198             || !equalBN("A^2", square, ret)
1199             || !BN_mul(ret, a, a, ctx)
1200             || !equalBN("A * A", square, ret)
1201             || !BN_div(ret, remainder, square, a, ctx)
1202             || !equalBN("Square / A", a, ret)
1203             || !equalBN("Square % A", zero, remainder))
1204         goto err;
1205
1206 #if HAVE_BN_SQRT
1207     BN_set_negative(a, 0);
1208     if (!BN_sqrt(ret, square, ctx)
1209             || !equalBN("sqrt(Square)", a, ret))
1210         goto err;
1211
1212     /* BN_sqrt should fail on non-squares and negative numbers. */
1213     if (!BN_is_zero(square)) {
1214         tmp = BN_new();
1215         if (tmp == NULL || !BN_copy(tmp, square))
1216             goto err;
1217         BN_set_negative(tmp, 1);
1218
1219         if (BN_sqrt(ret, tmp, ctx)) {
1220             fprintf(stderr, "BN_sqrt succeeded on a negative number");
1221             goto err;
1222         }
1223         ERR_clear_error();
1224
1225         BN_set_negative(tmp, 0);
1226         if (BN_add(tmp, tmp, BN_value_one()))
1227             goto err;
1228         if (BN_sqrt(ret, tmp, ctx)) {
1229             fprintf(stderr, "BN_sqrt succeeded on a non-square");
1230             goto err;
1231         }
1232         ERR_clear_error();
1233     }
1234 #endif
1235
1236     st = 1;
1237 err:
1238     BN_free(a);
1239     BN_free(square);
1240     BN_free(zero);
1241     BN_free(ret);
1242     BN_free(remainder);
1243     BN_free(tmp);
1244     return st;
1245 }
1246
1247 static int file_product(STANZA *s)
1248 {
1249     BIGNUM *a = getBN(s, "A");
1250     BIGNUM *b = getBN(s, "B");
1251     BIGNUM *product = getBN(s, "Product");
1252     BIGNUM *ret = BN_new();
1253     BIGNUM *remainder = BN_new();
1254     BIGNUM *zero = BN_new();
1255     int st = 0;
1256
1257     if (a == NULL || b == NULL || product == NULL || ret == NULL
1258             || remainder == NULL || zero == NULL)
1259         goto err;
1260
1261     BN_zero(zero);
1262
1263     if (!BN_mul(ret, a, b, ctx)
1264             || !equalBN("A * B", product, ret)
1265             || !BN_div(ret, remainder, product, a, ctx)
1266             || !equalBN("Product / A", b, ret)
1267             || !equalBN("Product % A", zero, remainder)
1268             || !BN_div(ret, remainder, product, b, ctx)
1269             || !equalBN("Product / B", a, ret)
1270             || !equalBN("Product % B", zero, remainder))
1271         goto err;
1272
1273     st = 1;
1274 err:
1275     BN_free(a);
1276     BN_free(b);
1277     BN_free(product);
1278     BN_free(ret);
1279     BN_free(remainder);
1280     BN_free(zero);
1281     return st;
1282 }
1283
1284 static int file_quotient(STANZA *s)
1285 {
1286     BIGNUM *a = getBN(s, "A");
1287     BIGNUM *b = getBN(s, "B");
1288     BIGNUM *quotient = getBN(s, "Quotient");
1289     BIGNUM *remainder = getBN(s, "Remainder");
1290     BIGNUM *ret = BN_new();
1291     BIGNUM *ret2 = BN_new();
1292     BIGNUM *nnmod = BN_new();
1293     BN_ULONG b_word, ret_word;
1294     int st = 0;
1295
1296     if (a == NULL || b == NULL || quotient == NULL || remainder == NULL
1297             || ret == NULL || ret2 == NULL || nnmod == NULL)
1298         goto err;
1299
1300     if (!BN_div(ret, ret2, a, b, ctx)
1301             || !equalBN("A / B", quotient, ret)
1302             || !equalBN("A % B", remainder, ret2)
1303             || !BN_mul(ret, quotient, b, ctx)
1304             || !BN_add(ret, ret, remainder)
1305             || !equalBN("Quotient * B + Remainder", a, ret))
1306         goto err;
1307
1308     /*
1309      * Test with BN_mod_word() and BN_div_word() if the divisor is
1310      * small enough.
1311      */
1312     b_word = BN_get_word(b);
1313     if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
1314         BN_ULONG remainder_word = BN_get_word(remainder);
1315
1316         assert(remainder_word != (BN_ULONG)-1);
1317         if (!BN_copy(ret, a))
1318             goto err;
1319         ret_word = BN_div_word(ret, b_word);
1320         if (ret_word != remainder_word) {
1321 #ifdef BN_DEC_FMT1
1322             fprintf(stderr,
1323                     "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1 "\n",
1324                     ret_word, remainder_word);
1325 #else
1326             fprintf(stderr, "Got A %% B (word) mismatch\n");
1327 #endif
1328             goto err;
1329         }
1330         if (!equalBN ("A / B (word)", quotient, ret))
1331             goto err;
1332
1333         ret_word = BN_mod_word(a, b_word);
1334         if (ret_word != remainder_word) {
1335 #ifdef BN_DEC_FMT1
1336             fprintf(stderr,
1337                     "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1 "\n",
1338                     ret_word, remainder_word);
1339 #else
1340             fprintf(stderr, "Got A %% B (word) mismatch\n");
1341 #endif
1342             goto err;
1343         }
1344     }
1345
1346     /* Test BN_nnmod. */
1347     if (!BN_is_negative(b)) {
1348         if (!BN_copy(nnmod, remainder)
1349                 || (BN_is_negative(nnmod) && !BN_add(nnmod, nnmod, b))
1350                 || !BN_nnmod(ret, a, b, ctx)
1351                 || !equalBN("A % B (non-negative)", nnmod, ret))
1352             goto err;
1353     }
1354
1355     st = 1;
1356 err:
1357     BN_free(a);
1358     BN_free(b);
1359     BN_free(quotient);
1360     BN_free(remainder);
1361     BN_free(ret);
1362     BN_free(ret2);
1363     BN_free(nnmod);
1364     return st;
1365 }
1366
1367 static int file_modmul(STANZA *s)
1368 {
1369     BIGNUM *a = getBN(s, "A");
1370     BIGNUM *b = getBN(s, "B");
1371     BIGNUM *m = getBN(s, "M");
1372     BIGNUM *mod_mul = getBN(s, "ModMul");
1373     BIGNUM *ret = BN_new();
1374     int st = 0;
1375
1376     if (a == NULL || b == NULL || m == NULL || mod_mul == NULL || ret == NULL)
1377         goto err;
1378
1379     if (!BN_mod_mul(ret, a, b, m, ctx)
1380             || !equalBN("A * B (mod M)", mod_mul, ret))
1381         goto err;
1382
1383     if (BN_is_odd(m)) {
1384         /* Reduce |a| and |b| and test the Montgomery version. */
1385         BN_MONT_CTX *mont = BN_MONT_CTX_new();
1386         BIGNUM *a_tmp = BN_new();
1387         BIGNUM *b_tmp = BN_new();
1388         if (mont == NULL || a_tmp == NULL || b_tmp == NULL
1389                 || !BN_MONT_CTX_set(mont, m, ctx)
1390                 || !BN_nnmod(a_tmp, a, m, ctx)
1391                 || !BN_nnmod(b_tmp, b, m, ctx)
1392                 || !BN_to_montgomery(a_tmp, a_tmp, mont, ctx)
1393                 || !BN_to_montgomery(b_tmp, b_tmp, mont, ctx)
1394                 || !BN_mod_mul_montgomery(ret, a_tmp, b_tmp, mont, ctx)
1395                 || !BN_from_montgomery(ret, ret, mont, ctx)
1396                 || !equalBN("A * B (mod M) (mont)", mod_mul, ret)) {
1397             st = 0;
1398         } else {
1399             st = 1;
1400         }
1401         BN_MONT_CTX_free(mont);
1402         BN_free(a_tmp);
1403         BN_free(b_tmp);
1404         if (st == 0)
1405             goto err;
1406     }
1407
1408     st = 1;
1409 err:
1410     BN_free(a);
1411     BN_free(b);
1412     BN_free(m);
1413     BN_free(mod_mul);
1414     BN_free(ret);
1415     return st;
1416 }
1417
1418 static int file_modexp(STANZA *s)
1419 {
1420     BIGNUM *a = getBN(s, "A");
1421     BIGNUM *e = getBN(s, "E");
1422     BIGNUM *m = getBN(s, "M");
1423     BIGNUM *mod_exp = getBN(s, "ModExp");
1424     BIGNUM *ret = BN_new();
1425     BIGNUM *b = NULL, *c = NULL, *d = BN_new();
1426     int st = 0;
1427
1428     if (a == NULL || e == NULL || m == NULL || mod_exp == NULL || ret == NULL)
1429         goto err;
1430
1431     if (!BN_mod_exp(ret, a, e, m, ctx)
1432             || !equalBN("A ^ E (mod M)", mod_exp, ret))
1433         goto err;
1434
1435     if (BN_is_odd(m)) {
1436         if (!BN_mod_exp_mont(ret, a, e, m, ctx, NULL)
1437                 || !equalBN("A ^ E (mod M) (mont)", mod_exp, ret)
1438                 || !BN_mod_exp_mont_consttime(ret, a, e, m, ctx, NULL)
1439                 || !equalBN("A ^ E (mod M) (mont const", mod_exp, ret))
1440             goto err;
1441     }
1442
1443     /* Regression test for carry propagation bug in sqr8x_reduction */
1444     BN_hex2bn(&a, "050505050505");
1445     BN_hex2bn(&b, "02");
1446     BN_hex2bn(&c,
1447         "4141414141414141414141274141414141414141414141414141414141414141"
1448         "4141414141414141414141414141414141414141414141414141414141414141"
1449         "4141414141414141414141800000000000000000000000000000000000000000"
1450         "0000000000000000000000000000000000000000000000000000000000000000"
1451         "0000000000000000000000000000000000000000000000000000000000000000"
1452         "0000000000000000000000000000000000000000000000000000000001");
1453     BN_mod_exp(d, a, b, c, ctx);
1454     BN_mul(e, a, a, ctx);
1455     if (BN_cmp(d, e)) {
1456         fprintf(stderr, "BN_mod_exp and BN_mul produce different results!\n");
1457         goto err;
1458     }
1459
1460     st = 1;
1461 err:
1462     BN_free(a);
1463     BN_free(b);
1464     BN_free(c);
1465     BN_free(d);
1466     BN_free(e);
1467     BN_free(m);
1468     BN_free(mod_exp);
1469     BN_free(ret);
1470     return st;
1471 }
1472
1473 static int file_exp(STANZA *s)
1474 {
1475     BIGNUM *a = getBN(s, "A");
1476     BIGNUM *e = getBN(s, "E");
1477     BIGNUM *exp = getBN(s, "Exp");
1478     BIGNUM *ret = BN_new();
1479     int st = 0;
1480
1481     if (a == NULL || e == NULL || exp == NULL || ret == NULL)
1482         goto err;
1483
1484     if (!BN_exp(ret, a, e, ctx)
1485             || !equalBN("A ^ E", exp, ret))
1486         goto err;
1487
1488     st = 1;
1489 err:
1490     BN_free(a);
1491     BN_free(e);
1492     BN_free(exp);
1493     BN_free(ret);
1494     return st;
1495 }
1496
1497 static int file_modsqrt(STANZA *s)
1498 {
1499     BIGNUM *a = getBN(s, "A");
1500     BIGNUM *p = getBN(s, "P");
1501     BIGNUM *mod_sqrt = getBN(s, "ModSqrt");
1502     BIGNUM *ret = BN_new();
1503     BIGNUM *ret2 = BN_new();
1504     int st = 0;
1505
1506     if (a == NULL || p == NULL || mod_sqrt == NULL
1507             || ret == NULL || ret2 == NULL)
1508         goto err;
1509
1510     /* There are two possible answers. */
1511     if (!BN_mod_sqrt(ret, a, p, ctx) || !BN_sub(ret2, p, ret))
1512         goto err;
1513
1514     if (BN_cmp(ret2, mod_sqrt) != 0
1515             && !equalBN("sqrt(A) (mod P)", mod_sqrt, ret))
1516         goto err;
1517
1518     st = 1;
1519 err:
1520     BN_free(a);
1521     BN_free(p);
1522     BN_free(mod_sqrt);
1523     BN_free(ret);
1524     BN_free(ret2);
1525     return st;
1526 }
1527
1528 static int test_bn2padded()
1529 {
1530 #if HAVE_BN_PADDED
1531     uint8_t zeros[256], out[256], reference[128];
1532     BIGNUM *n = BN_new();
1533     int st = 0;
1534
1535     /* Test edge case at 0. */
1536     if (n == NULL)
1537         goto err;
1538     if (!BN_bn2bin_padded(NULL, 0, n)) {
1539         fprintf(stderr,
1540                 "BN_bn2bin_padded failed to encode 0 in an empty buffer.\n");
1541         goto err;
1542     }
1543     memset(out, -1, sizeof(out));
1544     if (!BN_bn2bin_padded(out, sizeof(out), n)) {
1545         fprintf(stderr,
1546                 "BN_bn2bin_padded failed to encode 0 in a non-empty buffer.\n");
1547         goto err;
1548     }
1549     memset(zeros, 0, sizeof(zeros));
1550     if (memcmp(zeros, out, sizeof(out))) {
1551         fprintf(stderr, "BN_bn2bin_padded did not zero buffer.\n");
1552         goto err;
1553     }
1554
1555     /* Test a random numbers at various byte lengths. */
1556     for (size_t bytes = 128 - 7; bytes <= 128; bytes++) {
1557 #define TOP_BIT_ON 0
1558 #define BOTTOM_BIT_NOTOUCH 0
1559         if (!BN_rand(n, bytes * 8, TOP_BIT_ON, BOTTOM_BIT_NOTOUCH)) {
1560             ERR_print_errors_fp(stderr);
1561             goto err;
1562         }
1563         if (BN_num_bytes(n) != bytes
1564                 || BN_bn2bin(n, reference) != bytes) {
1565             fprintf(stderr, "Bad result from BN_rand; bytes.\n");
1566             goto err;
1567         }
1568         /* Empty buffer should fail. */
1569         if (BN_bn2bin_padded(NULL, 0, n)) {
1570             fprintf(stderr,
1571                     "BN_bn2bin_padded incorrectly succeeded on empty buffer.\n");
1572             goto err;
1573         }
1574         /* One byte short should fail. */
1575         if (BN_bn2bin_padded(out, bytes - 1, n)) {
1576             fprintf(stderr,
1577                     "BN_bn2bin_padded incorrectly succeeded on short.\n");
1578             goto err;
1579         }
1580         /* Exactly right size should encode. */
1581         if (!BN_bn2bin_padded(out, bytes, n)
1582                 || memcmp(out, reference, bytes) != 0) {
1583             fprintf(stderr,
1584                     "BN_bn2bin_padded gave a bad result.\n");
1585             goto err;
1586         }
1587         /* Pad up one byte extra. */
1588         if (!BN_bn2bin_padded(out, bytes + 1, n)
1589                 || memcmp(out + 1, reference, bytes)
1590                 || memcmp(out, zeros, 1)) {
1591             fprintf(stderr,
1592                     "BN_bn2bin_padded gave a bad result.\n");
1593             goto err;
1594         }
1595         /* Pad up to 256. */
1596         if (!BN_bn2bin_padded(out, sizeof(out), n)
1597                 || memcmp(out + sizeof(out) - bytes, reference, bytes)
1598                 || memcmp(out, zeros, sizeof(out) - bytes)) {
1599             fprintf(stderr,
1600                     "BN_bn2bin_padded gave a bad result.\n");
1601             goto err;
1602         }
1603     }
1604
1605     st = 1;
1606 err:
1607     BN_free(n);
1608     return st;
1609 #else
1610     return ctx != NULL;
1611 #endif
1612 }
1613
1614 static int test_dec2bn()
1615 {
1616     BIGNUM *bn = NULL;
1617     int st = 0;
1618
1619     int ret = parsedecBN(&bn, "0");
1620     if (ret != 1 || !BN_is_zero(bn) || BN_is_negative(bn)) {
1621         fprintf(stderr, "BN_dec2bn(0) gave a bad result.\n");
1622         goto err;
1623     }
1624     BN_free(bn);
1625
1626     ret = parsedecBN(&bn, "256");
1627     if (ret != 3 || !BN_is_word(bn, 256) || BN_is_negative(bn)) {
1628         fprintf(stderr, "BN_dec2bn(256) gave a bad result.\n");
1629         goto err;
1630     }
1631     BN_free(bn);
1632
1633     ret = parsedecBN(&bn, "-42");
1634     if (ret != 3 || !BN_abs_is_word(bn, 42) || !BN_is_negative(bn)) {
1635         fprintf(stderr, "BN_dec2bn(42) gave a bad result.\n");
1636         goto err;
1637     }
1638     BN_free(bn);
1639
1640     ret = parsedecBN(&bn, "-0");
1641     if (ret != 2 || !BN_is_zero(bn) || BN_is_negative(bn)) {
1642         fprintf(stderr, "BN_dec2bn(-0) gave a bad result.\n");
1643         goto err;
1644     }
1645     BN_free(bn);
1646
1647     ret = parsedecBN(&bn, "42trailing garbage is ignored");
1648     if (ret != 2 || !BN_abs_is_word(bn, 42)
1649             || BN_is_negative(bn)) {
1650         fprintf(stderr, "BN_dec2bn(42trailing...) gave a bad result.\n");
1651         goto err;
1652     }
1653
1654     st = 1;
1655 err:
1656     BN_free(bn);
1657     return st;
1658 }
1659
1660 static int test_hex2bn()
1661 {
1662     BIGNUM *bn = NULL;
1663     int ret, st = 0;
1664
1665     ret = parseBN(&bn, "0");
1666     if (ret != 1 || !BN_is_zero(bn) || BN_is_negative(bn)) {
1667         fprintf(stderr, "BN_hex2bn(0) gave a bad result.\n");
1668         goto err;
1669     }
1670     BN_free(bn);
1671
1672     ret = parseBN(&bn, "256");
1673     if (ret != 3 || !BN_is_word(bn, 0x256) || BN_is_negative(bn)) {
1674         fprintf(stderr, "BN_hex2bn(256) gave a bad result.\n");
1675         goto err;
1676     }
1677     BN_free(bn);
1678
1679     ret = parseBN(&bn, "-42");
1680     if (ret != 3 || !BN_abs_is_word(bn, 0x42) || !BN_is_negative(bn)) {
1681         fprintf(stderr, "BN_hex2bn(-42) gave a bad result.\n");
1682         goto err;
1683     }
1684     BN_free(bn);
1685
1686     ret = parseBN(&bn, "-0");
1687     if (ret != 2 || !BN_is_zero(bn) || BN_is_negative(bn)) {
1688         fprintf(stderr, "BN_hex2bn(-0) gave a bad result.\n");
1689         goto err;
1690     }
1691     BN_free(bn);
1692
1693     ret = parseBN(&bn, "abctrailing garbage is ignored");
1694     if (ret != 3 || !BN_is_word(bn, 0xabc) || BN_is_negative(bn)) {
1695         fprintf(stderr, "BN_hex2bn(abctrail...) gave a bad result.\n");
1696         goto err;
1697     }
1698     st = 1;
1699
1700 err:
1701     BN_free(bn);
1702     return st;
1703 }
1704
1705 static int test_asc2bn()
1706 {
1707     BIGNUM *bn = BN_new();
1708     int st = 0;
1709
1710     if (!BN_asc2bn(&bn, "0") || !BN_is_zero(bn) || BN_is_negative(bn)) {
1711         fprintf(stderr, "BN_asc2bn(0) gave a bad result.\n");
1712         goto err;
1713     }
1714
1715     if (!BN_asc2bn(&bn, "256") || !BN_is_word(bn, 256) || BN_is_negative(bn)) {
1716         fprintf(stderr, "BN_asc2bn(256) gave a bad result.\n");
1717         goto err;
1718     }
1719
1720     if (!BN_asc2bn(&bn, "-42")
1721             || !BN_abs_is_word(bn, 42) || !BN_is_negative(bn)) {
1722         fprintf(stderr, "BN_asc2bn(-42) gave a bad result.\n");
1723         goto err;
1724     }
1725
1726     if (!BN_asc2bn(&bn, "0x1234")
1727             || !BN_is_word(bn, 0x1234) || BN_is_negative(bn)) {
1728         fprintf(stderr, "BN_asc2bn(0x1234) gave a bad result.\n");
1729         goto err;
1730     }
1731
1732     if (!BN_asc2bn(&bn, "0X1234")
1733             || !BN_is_word(bn, 0x1234) || BN_is_negative(bn)) {
1734         fprintf(stderr, "BN_asc2bn(0X1234) gave a bad result.\n");
1735         goto err;
1736     }
1737
1738     if (!BN_asc2bn(&bn, "-0xabcd")
1739             || !BN_abs_is_word(bn, 0xabcd) || !BN_is_negative(bn)) {
1740         fprintf(stderr, "BN_asc2bn(-0xabcd) gave a bad result.\n");
1741         goto err;
1742     }
1743
1744     if (!BN_asc2bn(&bn, "-0") || !BN_is_zero(bn) || BN_is_negative(bn)) {
1745         fprintf(stderr, "BN_asc2bn(-0) gave a bad result.\n");
1746         goto err;
1747     }
1748
1749     if (!BN_asc2bn(&bn, "123trailing garbage is ignored")
1750             || !BN_is_word(bn, 123) || BN_is_negative(bn)) {
1751         fprintf(stderr, "BN_asc2bn(123trail...) gave a bad result.\n");
1752         goto err;
1753     }
1754
1755     st = 1;
1756 err:
1757     BN_free(bn);
1758     return st;
1759 }
1760
1761 static const MPITEST kMPITests[] = {
1762     {"0", "\x00\x00\x00\x00", 4},
1763     {"1", "\x00\x00\x00\x01\x01", 5},
1764     {"-1", "\x00\x00\x00\x01\x81", 5},
1765     {"128", "\x00\x00\x00\x02\x00\x80", 6},
1766     {"256", "\x00\x00\x00\x02\x01\x00", 6},
1767     {"-256", "\x00\x00\x00\x02\x81\x00", 6},
1768 };
1769
1770 static int test_mpi()
1771 {
1772     uint8_t scratch[8];
1773     int i = (int)sizeof(kMPITests) / sizeof(kMPITests[0]);
1774     const MPITEST *test = kMPITests;
1775     size_t mpi_len, mpi_len2;
1776     BIGNUM *bn = BN_new();
1777     BIGNUM *bn2 = NULL;
1778     int st = 0;
1779
1780     for ( ; --i >= 0; test++) {
1781         if (!BN_asc2bn(&bn, test->base10)) {
1782             fprintf(stderr, "Can't convert %s\n", test->base10);
1783             goto err;
1784         }
1785         mpi_len = BN_bn2mpi(bn, NULL);
1786         if (mpi_len > sizeof (scratch)) {
1787             fprintf(stderr,
1788                     "MPI test #%u: MPI size is too large to test.\n",
1789                     (unsigned)i);
1790             goto err;
1791         }
1792
1793         mpi_len2 = BN_bn2mpi(bn, scratch);
1794         if (mpi_len != mpi_len2) {
1795             fprintf(stderr, "MPI test #%u: length changes.\n",
1796                     (unsigned)i);
1797             goto err;
1798         }
1799
1800         if (mpi_len != test->mpi_len
1801                 || memcmp(test->mpi, scratch, mpi_len) != 0) {
1802             fprintf(stderr, "MPI test #%u failed:\n", (unsigned)i);
1803             goto err;
1804         }
1805
1806         bn2 = BN_mpi2bn(scratch, mpi_len, NULL);
1807         if (bn2 == NULL) {
1808             fprintf(stderr, "MPI test #%u: failed to parse\n",
1809                     (unsigned)i);
1810             goto err;
1811         }
1812
1813         if (BN_cmp(bn, bn2) != 0) {
1814             fprintf(stderr, "MPI test #%u: wrong result\n",
1815                     (unsigned)i);
1816             BN_free(bn2);
1817             goto err;
1818         }
1819         BN_free(bn2);
1820     }
1821
1822     st = 1;
1823 err:
1824     BN_free(bn);
1825     return st;
1826 }
1827
1828 static int test_rand()
1829 {
1830     BIGNUM *bn = BN_new();
1831     int st = 0;
1832
1833     if (bn == NULL)
1834         return 0;
1835
1836     /*
1837      * Test BN_rand for degenerate cases with |top| and |bottom| parameters.
1838      */
1839     if (BN_rand(bn, 0, 0 /* top */ , 0 /* bottom */ )) {
1840         fprintf(stderr, "BN_rand1 gave a bad result.\n");
1841         goto err;
1842     }
1843     if (BN_rand(bn, 0, 1 /* top */ , 1 /* bottom */ )) {
1844         fprintf(stderr, "BN_rand2 gave a bad result.\n");
1845         goto err;
1846     }
1847
1848     if (!BN_rand(bn, 1, 0 /* top */ , 0 /* bottom */ ) || !BN_is_word(bn, 1)) {
1849         fprintf(stderr, "BN_rand3 gave a bad result.\n");
1850         goto err;
1851     }
1852     if (BN_rand(bn, 1, 1 /* top */ , 0 /* bottom */ )) {
1853         fprintf(stderr, "BN_rand4 gave a bad result.\n");
1854         goto err;
1855     }
1856     if (!BN_rand(bn, 1, -1 /* top */ , 1 /* bottom */ ) || !BN_is_word(bn, 1)) {
1857         fprintf(stderr, "BN_rand5 gave a bad result.\n");
1858         goto err;
1859     }
1860
1861     if (!BN_rand(bn, 2, 1 /* top */ , 0 /* bottom */ ) || !BN_is_word(bn, 3)) {
1862         fprintf(stderr, "BN_rand6 gave a bad result.\n");
1863         goto err;
1864     }
1865
1866     st = 1;
1867 err:
1868     BN_free(bn);
1869     return st;
1870 }
1871
1872 static int test_negzero()
1873 {
1874     BIGNUM *a = BN_new();
1875     BIGNUM *b = BN_new();
1876     BIGNUM *c = BN_new();
1877     BIGNUM *d = BN_new();
1878     BIGNUM *numerator = NULL, *denominator = NULL;
1879     int consttime, st = 0;
1880
1881     if (a == NULL || b == NULL || c == NULL || d == NULL)
1882         goto err;
1883
1884     /* Test that BN_mul never gives negative zero. */
1885     if (!BN_set_word(a, 1))
1886         goto err;
1887     BN_set_negative(a, 1);
1888     BN_zero(b);
1889     if (!BN_mul(c, a, b, ctx))
1890         goto err;
1891     if (!BN_is_zero(c) || BN_is_negative(c)) {
1892         fprintf(stderr, "Multiplication test failed!\n");
1893         goto err;
1894     }
1895
1896     for (consttime = 0; consttime < 2; consttime++) {
1897         numerator = BN_new();
1898         denominator = BN_new();
1899         if (numerator == NULL || denominator == NULL)
1900             goto err;
1901         if (consttime) {
1902             BN_set_flags(numerator, BN_FLG_CONSTTIME);
1903             BN_set_flags(denominator, BN_FLG_CONSTTIME);
1904         }
1905         /* Test that BN_div never gives negative zero in the quotient. */
1906         if (!BN_set_word(numerator, 1) || !BN_set_word(denominator, 2))
1907             goto err;
1908         BN_set_negative(numerator, 1);
1909         if (!BN_div(a, b, numerator, denominator, ctx))
1910             goto err;
1911         if (!BN_is_zero(a) || BN_is_negative(a)) {
1912             fprintf(stderr, "Incorrect quotient (consttime = %d).\n",
1913                     consttime);
1914             goto err;
1915         }
1916
1917         /* Test that BN_div never gives negative zero in the remainder. */
1918         if (!BN_set_word(denominator, 1))
1919             goto err;
1920         if (!BN_div(a, b, numerator, denominator, ctx))
1921             goto err;
1922         if (!BN_is_zero(b) || BN_is_negative(b)) {
1923             fprintf(stderr, "Incorrect remainder (consttime = %d).\n",
1924                     consttime);
1925             goto err;
1926         }
1927         BN_free(numerator);
1928         BN_free(denominator);
1929         numerator = denominator = NULL;
1930     }
1931
1932     /* Test that BN_set_negative will not produce a negative zero. */
1933     BN_zero(a);
1934     BN_set_negative(a, 1);
1935     if (BN_is_negative(a)) {
1936         fprintf(stderr, "BN_set_negative produced a negative zero.\n");
1937         goto err;
1938     }
1939
1940     st = 1;
1941 err:
1942     BN_free(a);
1943     BN_free(b);
1944     BN_free(c);
1945     BN_free(d);
1946     BN_free(numerator);
1947     BN_free(denominator);
1948     return st;
1949 }
1950
1951 static int test_badmod()
1952 {
1953     BIGNUM *a = BN_new();
1954     BIGNUM *b = BN_new();
1955     BIGNUM *zero = BN_new();
1956     BN_MONT_CTX *mont = BN_MONT_CTX_new();
1957     int st = 0;
1958
1959     if (a == NULL || b == NULL || zero == NULL || mont == NULL)
1960         goto err;
1961     BN_zero(zero);
1962
1963     if (BN_div(a, b, BN_value_one(), zero, ctx)) {
1964         fprintf(stderr, "Division by zero succeeded!\n");
1965         goto err;
1966     }
1967     ERR_clear_error();
1968
1969     if (BN_mod_mul(a, BN_value_one(), BN_value_one(), zero, ctx)) {
1970         fprintf(stderr, "BN_mod_mul with zero modulus succeeded!\n");
1971         goto err;
1972     }
1973     ERR_clear_error();
1974
1975     if (BN_mod_exp(a, BN_value_one(), BN_value_one(), zero, ctx)) {
1976         fprintf(stderr, "BN_mod_exp with zero modulus succeeded!\n");
1977         goto err;
1978     }
1979     ERR_clear_error();
1980
1981     if (BN_mod_exp_mont(a, BN_value_one(), BN_value_one(), zero, ctx, NULL)) {
1982         fprintf(stderr, "BN_mod_exp_mont with zero modulus succeeded!\n");
1983         goto err;
1984     }
1985     ERR_clear_error();
1986
1987     if (BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
1988                                   zero, ctx, NULL)) {
1989         fprintf(stderr,
1990                 "BN_mod_exp_mont_consttime with zero modulus succeeded!\n");
1991         goto err;
1992     }
1993     ERR_clear_error();
1994
1995     if (BN_MONT_CTX_set(mont, zero, ctx)) {
1996         fprintf(stderr, "BN_MONT_CTX_set succeeded for zero modulus!\n");
1997         goto err;
1998     }
1999     ERR_clear_error();
2000
2001     /* Some operations also may not be used with an even modulus. */
2002     if (!BN_set_word(b, 16))
2003         goto err;
2004
2005     if (BN_MONT_CTX_set(mont, b, ctx)) {
2006         fprintf(stderr,
2007                 "BN_MONT_CTX_set succeeded for even modulus!\n");
2008         goto err;
2009     }
2010     ERR_clear_error();
2011
2012     if (BN_mod_exp_mont(a, BN_value_one(), BN_value_one(), b, ctx, NULL)) {
2013         fprintf(stderr,
2014                 "BN_mod_exp_mont with even modulus succeeded!\n");
2015         goto err;
2016     }
2017     ERR_clear_error();
2018
2019     if (BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
2020                                   b, ctx, NULL)) {
2021         fprintf(stderr,
2022                 "BN_mod_exp_mont_consttime with even modulus succeeded!\n");
2023         goto err;
2024     }
2025     ERR_clear_error();
2026
2027     st = 1;
2028 err:
2029     BN_free(a);
2030     BN_free(b);
2031     BN_free(zero);
2032     BN_MONT_CTX_free(mont);
2033     return st;
2034 }
2035
2036 static int test_expmodzero()
2037 {
2038     BIGNUM *zero = BN_new();
2039     BIGNUM *a = BN_new();
2040     BIGNUM *r = BN_new();
2041     int st = 0;
2042
2043     if (zero == NULL || a == NULL || r == NULL || !BN_rand(a, 1024, 0, 0))
2044         goto err;
2045     BN_zero(zero);
2046
2047     if (!BN_mod_exp(r, a, zero, BN_value_one(), NULL)
2048             || !BN_is_zero(r)
2049             || !BN_mod_exp_mont(r, a, zero, BN_value_one(), NULL, NULL)
2050             || !BN_is_zero(r)
2051             || !BN_mod_exp_mont_consttime(r, a, zero, BN_value_one(), NULL, NULL)
2052             || !BN_is_zero(r)
2053             || !BN_mod_exp_mont_word(r, 42, zero, BN_value_one(), NULL, NULL)
2054             || !BN_is_zero(r))
2055         goto err;
2056
2057     st = 1;
2058 err:
2059     BN_free(zero);
2060     BN_free(a);
2061     BN_free(r);
2062     return st;
2063 }
2064
2065 static int test_smallprime()
2066 {
2067     static const int kBits = 10;
2068     BIGNUM *r = BN_new();
2069     int st = 0;
2070
2071     if (r == NULL
2072             || !BN_generate_prime_ex(r, (int)kBits, 0, NULL, NULL, NULL))
2073         goto err;
2074     if (BN_num_bits(r) != kBits) {
2075         fprintf(stderr, "Expected %u bit prime, got %u bit number\n",
2076                 kBits, BN_num_bits(r));
2077         goto err;
2078     }
2079
2080     st = 1;
2081 err:
2082     BN_free(r);
2083     return st;
2084 }
2085
2086 static int test_3_is_prime()
2087 {
2088     int ret = 0;
2089     BIGNUM *r = BN_new();
2090
2091     /* For a long time, small primes were not considered prime when
2092      * do_trial_division was set. */
2093     if (r == NULL ||
2094         !BN_set_word(r, 3) ||
2095         BN_is_prime_fasttest_ex(r, 3 /* nchecks */, ctx,
2096                                 0 /* do_trial_division */, NULL) != 1 ||
2097         BN_is_prime_fasttest_ex(r, 3 /* nchecks */, ctx,
2098                                 1 /* do_trial_division */, NULL) != 1) {
2099         goto err;
2100     }
2101
2102     ret = 1;
2103
2104 err:
2105     BN_free(r);
2106     return ret;
2107 }
2108
2109
2110 /* Delete leading and trailing spaces from a string */
2111 static char *strip_spaces(char *p)
2112 {
2113     char *q;
2114
2115     /* Skip over leading spaces */
2116     while (*p && isspace(*p))
2117         p++;
2118     if (!*p)
2119         return NULL;
2120
2121     for (q = p + strlen(p) - 1; q != p && isspace(*q); )
2122         *q-- = '\0';
2123     return *p ? p : NULL;
2124 }
2125
2126 /*
2127  * Read next test stanza; return 1 if found, 0 on EOF or error.
2128  */
2129 static int readstanza(STANZA *s, int *linesread)
2130 {
2131     PAIR *pp = s->pairs;
2132     char *p, *equals, *key, *value;
2133     char buff[1024];
2134
2135     while (fgets(buff, sizeof(buff), fp) != NULL) {
2136         (*linesread)++;
2137         if ((p = strchr(buff, '\n')) == NULL) {
2138             fprintf(stderr, "Line %d too long.\n", s->start);
2139             return 0;
2140         }
2141         *p = '\0';
2142
2143         /* Blank line marks end of tests. */
2144         if (buff[0] == '\0')
2145             break;
2146
2147         /* Lines starting with a pound sign are ignored. */
2148         if (buff[0] == '#')
2149             continue;
2150
2151         if ((equals = strchr(buff, '=')) == NULL) {
2152             fprintf(stderr, "Line %d missing equals.\n", s->start);
2153             return 0;
2154         }
2155         *equals++ = '\0';
2156
2157         key = strip_spaces(buff);
2158         value = strip_spaces(equals);
2159         if (key == NULL || value == NULL) {
2160             fprintf(stderr, "Line %d missing field.\n", s->start);
2161             return 0;
2162         }
2163         s->numpairs++;
2164         if (s->numpairs >= MAXPAIRS) {
2165             fprintf(stderr, "Line %d too many lines\n", s->start);
2166             return 0;
2167         }
2168         pp->key = OPENSSL_strdup(key);
2169         pp->value = OPENSSL_strdup(value);
2170         pp++;
2171     }
2172
2173     /* If we read anything, return ok. */
2174     return 1;
2175 }
2176
2177 static void clearstanza(STANZA *s)
2178 {
2179     PAIR *pp = s->pairs;
2180     int i = s->numpairs;
2181     int start = s->start;
2182
2183     for ( ; --i >= 0; pp++) {
2184         OPENSSL_free(pp->key);
2185         OPENSSL_free(pp->value);
2186     }
2187     memset(s, 0, sizeof(*s));
2188     s->start = start;
2189 }
2190
2191 static int file_test_run(STANZA *s)
2192 {
2193     static const FILETEST filetests[] = {
2194         {"Sum", file_sum},
2195         {"LShift1", file_lshift1},
2196         {"LShift", file_lshift},
2197         {"RShift", file_rshift},
2198         {"Square", file_square},
2199         {"Product", file_product},
2200         {"Quotient", file_quotient},
2201         {"ModMul", file_modmul},
2202         {"ModExp", file_modexp},
2203         {"Exp", file_exp},
2204         {"ModSqrt", file_modsqrt},
2205     };
2206     int numtests = OSSL_NELEM(filetests);
2207     const FILETEST *tp = filetests;
2208
2209     for ( ; --numtests >= 0; tp++) {
2210         if (findattr(s, tp->name) != NULL)
2211             return tp->func(s);
2212     }
2213     fprintf(stderr, "Unknown test at %d\n", s->start);
2214     return 0;
2215 }
2216
2217 static int file_tests()
2218 {
2219     STANZA s;
2220     int linesread = 0, errcnt = 0;
2221
2222     /* Read test file. */
2223     memset(&s, 0, sizeof(s));
2224     while (!feof(fp) && readstanza(&s, &linesread)) {
2225         if (s.numpairs == 0)
2226             continue;
2227         if (!file_test_run(&s)) {
2228             fprintf(stderr, "Test at %d failed\n", s.start);
2229             errcnt++;
2230         }
2231         clearstanza(&s);
2232         s.start = linesread;
2233     }
2234
2235     return errcnt == 0;
2236 }
2237
2238 int test_main(int argc, char *argv[])
2239 {
2240     static const char rnd_seed[] =
2241         "If not seeded, BN_generate_prime might fail";
2242     int result = 0;
2243
2244     if (argc != 2) {
2245         fprintf(stderr, "%s TEST_FILE\n", argv[0]);
2246         return 1;
2247     }
2248
2249     ADD_TEST(test_sub);
2250     ADD_TEST(test_div_recip);
2251     ADD_TEST(test_mod);
2252     ADD_TEST(test_modexp_mont5);
2253     ADD_TEST(test_kronecker);
2254     ADD_TEST(test_rand);
2255     ADD_TEST(test_bn2padded);
2256     ADD_TEST(test_dec2bn);
2257     ADD_TEST(test_hex2bn);
2258     ADD_TEST(test_asc2bn);
2259     ADD_TEST(test_mpi);
2260     ADD_TEST(test_negzero);
2261     ADD_TEST(test_badmod);
2262     ADD_TEST(test_expmodzero);
2263     ADD_TEST(test_smallprime);
2264 #ifndef OPENSSL_NO_EC2M
2265     ADD_TEST(test_gf2m_add);
2266     ADD_TEST(test_gf2m_mod);
2267     ADD_TEST(test_gf2m_mul);
2268     ADD_TEST(test_gf2m_sqr);
2269     ADD_TEST(test_gf2m_modinv);
2270     ADD_TEST(test_gf2m_moddiv);
2271     ADD_TEST(test_gf2m_modexp);
2272     ADD_TEST(test_gf2m_modsqrt);
2273     ADD_TEST(test_gf2m_modsolvequad);
2274 #endif
2275     ADD_TEST(test_3_is_prime);
2276     ADD_TEST(file_tests);
2277
2278     RAND_seed(rnd_seed, sizeof rnd_seed);
2279     ctx = BN_CTX_new();
2280     TEST_check(ctx != NULL);
2281
2282     fp = fopen(argv[1], "r");
2283     TEST_check(fp != NULL);
2284     result = run_tests(argv[0]);
2285     fclose(fp);
2286
2287     BN_CTX_free(ctx);
2288     return result;
2289 }