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