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