test/bntest.c

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