test/bntest.c

   1 /*
   2  * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the Apache License 2.0 (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 #ifdef __TANDEM
  14 # include <strings.h> /* strcasecmp */
  15 #endif
  16 #include <ctype.h>
  17
  18 #include <openssl/bn.h>
  19 #include <openssl/crypto.h>
  20 #include <openssl/err.h>
  21 #include <openssl/rand.h>
  22 #include "internal/nelem.h"
  23 #include "internal/numbers.h"
  24 #include "testutil.h"
  25
  26 /*
  27  * Things in boring, not in openssl.
  28  */
  29 #define HAVE_BN_SQRT 0
  30
  31 typedef struct filetest_st {
  32     const char *name;
  33     int (*func)(STANZA *s);
  34 } FILETEST;
  35
  36 typedef struct mpitest_st {
  37     const char *base10;
  38     const char *mpi;
  39     size_t mpi_len;
  40 } MPITEST;
  41
  42 static const int NUM0 = 100;           /* number of tests */
  43 static const int NUM1 = 50;            /* additional tests for some functions */
  44 static const int NUM_PRIME_TESTS = 20;
  45 static BN_CTX *ctx;
  46
  47 /*
  48  * Polynomial coefficients used in GFM tests.
  49  */
  50 #ifndef OPENSSL_NO_EC2M
  51 static int p0[] = { 163, 7, 6, 3, 0, -1 };
  52 static int p1[] = { 193, 15, 0, -1 };
  53 #endif
  54
  55 /*
  56  * Look for |key| in the stanza and return it or NULL if not found.
  57  */
  58 static const char *findattr(STANZA *s, const char *key)
  59 {
  60     int i = s->numpairs;
  61     PAIR *pp = s->pairs;
  62
  63     for ( ; --i >= 0; pp++)
  64         if (OPENSSL_strcasecmp(pp->key, key) == 0)
  65             return pp->value;
  66     return NULL;
  67 }
  68
  69 /*
  70  * Parse BIGNUM from sparse hex-strings, return |BN_hex2bn| result.
  71  */
  72 static int parse_bigBN(BIGNUM **out, const char *bn_strings[])
  73 {
  74     char *bigstring = glue_strings(bn_strings, NULL);
  75     int ret = BN_hex2bn(out, bigstring);
  76
  77     OPENSSL_free(bigstring);
  78     return ret;
  79 }
  80
  81 /*
  82  * Parse BIGNUM, return number of bytes parsed.
  83  */
  84 static int parseBN(BIGNUM **out, const char *in)
  85 {
  86     *out = NULL;
  87     return BN_hex2bn(out, in);
  88 }
  89
  90 static int parsedecBN(BIGNUM **out, const char *in)
  91 {
  92     *out = NULL;
  93     return BN_dec2bn(out, in);
  94 }
  95
  96 static BIGNUM *getBN(STANZA *s, const char *attribute)
  97 {
  98     const char *hex;
  99     BIGNUM *ret = NULL;
 100
 101     if ((hex = findattr(s, attribute)) == NULL) {
 102         TEST_error("%s:%d: Can't find %s", s->test_file, s->start, attribute);
 103         return NULL;
 104     }
 105
 106     if (parseBN(&ret, hex) != (int)strlen(hex)) {
 107         TEST_error("Could not decode '%s'", hex);
 108         return NULL;
 109     }
 110     return ret;
 111 }
 112
 113 static int getint(STANZA *s, int *out, const char *attribute)
 114 {
 115     BIGNUM *ret;
 116     BN_ULONG word;
 117     int st = 0;
 118
 119     if (!TEST_ptr(ret = getBN(s, attribute))
 120             || !TEST_ulong_le(word = BN_get_word(ret), INT_MAX))
 121         goto err;
 122
 123     *out = (int)word;
 124     st = 1;
 125  err:
 126     BN_free(ret);
 127     return st;
 128 }
 129
 130 static int equalBN(const char *op, const BIGNUM *expected, const BIGNUM *actual)
 131 {
 132     if (BN_cmp(expected, actual) == 0)
 133         return 1;
 134
 135     TEST_error("unexpected %s value", op);
 136     TEST_BN_eq(expected, actual);
 137     return 0;
 138 }
 139
 140 /*
 141  * Return a "random" flag for if a BN should be negated.
 142  */
 143 static int rand_neg(void)
 144 {
 145     static unsigned int neg = 0;
 146     static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };
 147
 148     return sign[(neg++) % 8];
 149 }
 150
 151 static int test_swap(void)
 152 {
 153     BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
 154     int top, cond, st = 0;
 155
 156     if (!TEST_ptr(a = BN_new())
 157             || !TEST_ptr(b = BN_new())
 158             || !TEST_ptr(c = BN_new())
 159             || !TEST_ptr(d = BN_new()))
 160         goto err;
 161
 162     if (!(TEST_true(BN_bntest_rand(a, 1024, 1, 0))
 163             && TEST_true(BN_bntest_rand(b, 1024, 1, 0))
 164             && TEST_ptr(BN_copy(c, a))
 165             && TEST_ptr(BN_copy(d, b))))
 166         goto err;
 167     top = BN_num_bits(a) / BN_BITS2;
 168
 169     /* regular swap */
 170     BN_swap(a, b);
 171     if (!equalBN("swap", a, d)
 172             || !equalBN("swap", b, c))
 173         goto err;
 174
 175     /* regular swap: same pointer */
 176     BN_swap(a, a);
 177     if (!equalBN("swap with same pointer", a, d))
 178         goto err;
 179
 180     /* conditional swap: true */
 181     cond = 1;
 182     BN_consttime_swap(cond, a, b, top);
 183     if (!equalBN("cswap true", a, c)
 184             || !equalBN("cswap true", b, d))
 185         goto err;
 186
 187     /* conditional swap: true, same pointer */
 188     BN_consttime_swap(cond, a, a, top);
 189     if (!equalBN("cswap true", a, c))
 190         goto err;
 191
 192     /* conditional swap: false */
 193     cond = 0;
 194     BN_consttime_swap(cond, a, b, top);
 195     if (!equalBN("cswap false", a, c)
 196             || !equalBN("cswap false", b, d))
 197         goto err;
 198
 199     /* conditional swap: false, same pointer */
 200     BN_consttime_swap(cond, a, a, top);
 201     if (!equalBN("cswap false", a, c))
 202         goto err;
 203
 204     /* same tests but checking flag swap */
 205     BN_set_flags(a, BN_FLG_CONSTTIME);
 206
 207     BN_swap(a, b);
 208     if (!equalBN("swap, flags", a, d)
 209             || !equalBN("swap, flags", b, c)
 210             || !TEST_true(BN_get_flags(b, BN_FLG_CONSTTIME))
 211             || !TEST_false(BN_get_flags(a, BN_FLG_CONSTTIME)))
 212         goto err;
 213
 214     cond = 1;
 215     BN_consttime_swap(cond, a, b, top);
 216     if (!equalBN("cswap true, flags", a, c)
 217             || !equalBN("cswap true, flags", b, d)
 218             || !TEST_true(BN_get_flags(a, BN_FLG_CONSTTIME))
 219             || !TEST_false(BN_get_flags(b, BN_FLG_CONSTTIME)))
 220         goto err;
 221
 222     cond = 0;
 223     BN_consttime_swap(cond, a, b, top);
 224     if (!equalBN("cswap false, flags", a, c)
 225             || !equalBN("cswap false, flags", b, d)
 226             || !TEST_true(BN_get_flags(a, BN_FLG_CONSTTIME))
 227             || !TEST_false(BN_get_flags(b, BN_FLG_CONSTTIME)))
 228         goto err;
 229
 230     st = 1;
 231  err:
 232     BN_free(a);
 233     BN_free(b);
 234     BN_free(c);
 235     BN_free(d);
 236     return st;
 237 }
 238
 239 static int test_sub(void)
 240 {
 241     BIGNUM *a = NULL, *b = NULL, *c = NULL;
 242     int i, st = 0;
 243
 244     if (!TEST_ptr(a = BN_new())
 245             || !TEST_ptr(b = BN_new())
 246             || !TEST_ptr(c = BN_new()))
 247         goto err;
 248
 249     for (i = 0; i < NUM0 + NUM1; i++) {
 250         if (i < NUM1) {
 251             if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0)))
 252                     && TEST_ptr(BN_copy(b, a))
 253                     && TEST_int_ne(BN_set_bit(a, i), 0)
 254                     && TEST_true(BN_add_word(b, i)))
 255                 goto err;
 256         } else {
 257             if (!TEST_true(BN_bntest_rand(b, 400 + i - NUM1, 0, 0)))
 258                 goto err;
 259             BN_set_negative(a, rand_neg());
 260             BN_set_negative(b, rand_neg());
 261         }
 262         if (!(TEST_true(BN_sub(c, a, b))
 263                 && TEST_true(BN_add(c, c, b))
 264                 && TEST_true(BN_sub(c, c, a))
 265                 && TEST_BN_eq_zero(c)))
 266             goto err;
 267     }
 268     st = 1;
 269  err:
 270     BN_free(a);
 271     BN_free(b);
 272     BN_free(c);
 273     return st;
 274 }
 275
 276 static int test_div_recip(void)
 277 {
 278     BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
 279     BN_RECP_CTX *recp = NULL;
 280     int st = 0, i;
 281
 282     if (!TEST_ptr(a = BN_new())
 283             || !TEST_ptr(b = BN_new())
 284             || !TEST_ptr(c = BN_new())
 285             || !TEST_ptr(d = BN_new())
 286             || !TEST_ptr(e = BN_new())
 287             || !TEST_ptr(recp = BN_RECP_CTX_new()))
 288         goto err;
 289
 290     for (i = 0; i < NUM0 + NUM1; i++) {
 291         if (i < NUM1) {
 292             if (!(TEST_true(BN_bntest_rand(a, 400, 0, 0))
 293                     && TEST_ptr(BN_copy(b, a))
 294                     && TEST_true(BN_lshift(a, a, i))
 295                     && TEST_true(BN_add_word(a, i))))
 296                 goto err;
 297         } else {
 298             if (!(TEST_true(BN_bntest_rand(b, 50 + 3 * (i - NUM1), 0, 0))))
 299                 goto err;
 300         }
 301         BN_set_negative(a, rand_neg());
 302         BN_set_negative(b, rand_neg());
 303         if (!(TEST_true(BN_RECP_CTX_set(recp, b, ctx))
 304                 && TEST_true(BN_div_recp(d, c, a, recp, ctx))
 305                 && TEST_true(BN_mul(e, d, b, ctx))
 306                 && TEST_true(BN_add(d, e, c))
 307                 && TEST_true(BN_sub(d, d, a))
 308                 && TEST_BN_eq_zero(d)))
 309             goto err;
 310     }
 311     st = 1;
 312  err:
 313     BN_free(a);
 314     BN_free(b);
 315     BN_free(c);
 316     BN_free(d);
 317     BN_free(e);
 318     BN_RECP_CTX_free(recp);
 319     return st;
 320 }
 321
 322 static struct {
 323     int n, divisor, result, remainder;
 324 } signed_mod_tests[] = {
 325     {  10,   3,   3,   1 },
 326     { -10,   3,  -3,  -1 },
 327     {  10,  -3,  -3,   1 },
 328     { -10,  -3,   3,  -1 },
 329 };
 330
 331 static BIGNUM *set_signed_bn(int value)
 332 {
 333     BIGNUM *bn = BN_new();
 334
 335     if (bn == NULL)
 336         return NULL;
 337     if (!BN_set_word(bn, value < 0 ? -value : value)) {
 338         BN_free(bn);
 339         return NULL;
 340     }
 341     BN_set_negative(bn, value < 0);
 342     return bn;
 343 }
 344
 345 static int test_signed_mod_replace_ab(int n)
 346 {
 347     BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
 348     int st = 0;
 349
 350     if (!TEST_ptr(a = set_signed_bn(signed_mod_tests[n].n))
 351             || !TEST_ptr(b = set_signed_bn(signed_mod_tests[n].divisor))
 352             || !TEST_ptr(c = set_signed_bn(signed_mod_tests[n].result))
 353             || !TEST_ptr(d = set_signed_bn(signed_mod_tests[n].remainder)))
 354         goto err;
 355
 356     if (TEST_true(BN_div(a, b, a, b, ctx))
 357             && TEST_BN_eq(a, c)
 358             && TEST_BN_eq(b, d))
 359         st = 1;
 360  err:
 361     BN_free(a);
 362     BN_free(b);
 363     BN_free(c);
 364     BN_free(d);
 365     return st;
 366 }
 367
 368 static int test_signed_mod_replace_ba(int n)
 369 {
 370     BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
 371     int st = 0;
 372
 373     if (!TEST_ptr(a = set_signed_bn(signed_mod_tests[n].n))
 374             || !TEST_ptr(b = set_signed_bn(signed_mod_tests[n].divisor))
 375             || !TEST_ptr(c = set_signed_bn(signed_mod_tests[n].result))
 376             || !TEST_ptr(d = set_signed_bn(signed_mod_tests[n].remainder)))
 377         goto err;
 378
 379     if (TEST_true(BN_div(b, a, a, b, ctx))
 380             && TEST_BN_eq(b, c)
 381             && TEST_BN_eq(a, d))
 382         st = 1;
 383  err:
 384     BN_free(a);
 385     BN_free(b);
 386     BN_free(c);
 387     BN_free(d);
 388     return st;
 389 }
 390
 391 static int test_mod(void)
 392 {
 393     BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL;
 394     int st = 0, i;
 395
 396     if (!TEST_ptr(a = BN_new())
 397             || !TEST_ptr(b = BN_new())
 398             || !TEST_ptr(c = BN_new())
 399             || !TEST_ptr(d = BN_new())
 400             || !TEST_ptr(e = BN_new()))
 401         goto err;
 402
 403     if (!(TEST_true(BN_bntest_rand(a, 1024, 0, 0))))
 404         goto err;
 405     for (i = 0; i < NUM0; i++) {
 406         if (!(TEST_true(BN_bntest_rand(b, 450 + i * 10, 0, 0))))
 407             goto err;
 408         BN_set_negative(a, rand_neg());
 409         BN_set_negative(b, rand_neg());
 410         if (!(TEST_true(BN_mod(c, a, b, ctx))
 411                 && TEST_true(BN_div(d, e, a, b, ctx))
 412                 && TEST_BN_eq(e, c)
 413                 && TEST_true(BN_mul(c, d, b, ctx))
 414                 && TEST_true(BN_add(d, c, e))
 415                 && TEST_BN_eq(d, a)))
 416             goto err;
 417     }
 418     st = 1;
 419  err:
 420     BN_free(a);
 421     BN_free(b);
 422     BN_free(c);
 423     BN_free(d);
 424     BN_free(e);
 425     return st;
 426 }
 427
 428 static const char *bn1strings[] = {
 429     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 430     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 431     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 432     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 433     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 434     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 435     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 436     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF00",
 437     "0000000000000000000000000000000000000000000000000000000000000000",
 438     "0000000000000000000000000000000000000000000000000000000000000000",
 439     "0000000000000000000000000000000000000000000000000000000000000000",
 440     "0000000000000000000000000000000000000000000000000000000000000000",
 441     "0000000000000000000000000000000000000000000000000000000000000000",
 442     "0000000000000000000000000000000000000000000000000000000000000000",
 443     "0000000000000000000000000000000000000000000000000000000000000000",
 444     "00000000000000000000000000000000000000000000000000FFFFFFFFFFFFFF",
 445     NULL
 446 };
 447
 448 static const char *bn2strings[] = {
 449     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 450     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 451     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 452     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 453     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 454     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 455     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 456     "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF0000000000",
 457     "0000000000000000000000000000000000000000000000000000000000000000",
 458     "0000000000000000000000000000000000000000000000000000000000000000",
 459     "0000000000000000000000000000000000000000000000000000000000000000",
 460     "0000000000000000000000000000000000000000000000000000000000000000",
 461     "0000000000000000000000000000000000000000000000000000000000000000",
 462     "0000000000000000000000000000000000000000000000000000000000000000",
 463     "0000000000000000000000000000000000000000000000000000000000000000",
 464     "000000000000000000000000000000000000000000FFFFFFFFFFFFFF00000000",
 465     NULL
 466 };
 467
 468 /*
 469  * Test constant-time modular exponentiation with 1024-bit inputs, which on
 470  * x86_64 cause a different code branch to be taken.
 471  */
 472 static int test_modexp_mont5(void)
 473 {
 474     BIGNUM *a = NULL, *p = NULL, *m = NULL, *d = NULL, *e = NULL;
 475     BIGNUM *b = NULL, *n = NULL, *c = NULL;
 476     BN_MONT_CTX *mont = NULL;
 477     int st = 0;
 478
 479     if (!TEST_ptr(a = BN_new())
 480             || !TEST_ptr(p = BN_new())
 481             || !TEST_ptr(m = BN_new())
 482             || !TEST_ptr(d = BN_new())
 483             || !TEST_ptr(e = BN_new())
 484             || !TEST_ptr(b = BN_new())
 485             || !TEST_ptr(n = BN_new())
 486             || !TEST_ptr(c = BN_new())
 487             || !TEST_ptr(mont = BN_MONT_CTX_new()))
 488         goto err;
 489
 490     /* must be odd for montgomery */
 491     if (!(TEST_true(BN_bntest_rand(m, 1024, 0, 1))
 492             /* Zero exponent */
 493             && TEST_true(BN_bntest_rand(a, 1024, 0, 0))))
 494         goto err;
 495     BN_zero(p);
 496
 497     if (!TEST_true(BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)))
 498         goto err;
 499     if (!TEST_BN_eq_one(d))
 500         goto err;
 501
 502     /* Regression test for carry bug in mulx4x_mont */
 503     if (!(TEST_true(BN_hex2bn(&a,
 504         "7878787878787878787878787878787878787878787878787878787878787878"
 505         "7878787878787878787878787878787878787878787878787878787878787878"
 506         "7878787878787878787878787878787878787878787878787878787878787878"
 507         "7878787878787878787878787878787878787878787878787878787878787878"))
 508         && TEST_true(BN_hex2bn(&b,
 509         "095D72C08C097BA488C5E439C655A192EAFB6380073D8C2664668EDDB4060744"
 510         "E16E57FB4EDB9AE10A0CEFCDC28A894F689A128379DB279D48A2E20849D68593"
 511         "9B7803BCF46CEBF5C533FB0DD35B080593DE5472E3FE5DB951B8BFF9B4CB8F03"
 512         "9CC638A5EE8CDD703719F8000E6A9F63BEED5F2FCD52FF293EA05A251BB4AB81"))
 513         && TEST_true(BN_hex2bn(&n,
 514         "D78AF684E71DB0C39CFF4E64FB9DB567132CB9C50CC98009FEB820B26F2DED9B"
 515         "91B9B5E2B83AE0AE4EB4E0523CA726BFBE969B89FD754F674CE99118C3F2D1C5"
 516         "D81FDC7C54E02B60262B241D53C040E99E45826ECA37A804668E690E1AFC1CA4"
 517         "2C9A15D84D4954425F0B7642FC0BD9D7B24E2618D2DCC9B729D944BADACFDDAF"))))
 518         goto err;
 519
 520     if (!(TEST_true(BN_MONT_CTX_set(mont, n, ctx))
 521             && TEST_true(BN_mod_mul_montgomery(c, a, b, mont, ctx))
 522             && TEST_true(BN_mod_mul_montgomery(d, b, a, mont, ctx))
 523             && TEST_BN_eq(c, d)))
 524         goto err;
 525
 526     /* Regression test for carry bug in sqr[x]8x_mont */
 527     if (!(TEST_true(parse_bigBN(&n, bn1strings))
 528             && TEST_true(parse_bigBN(&a, bn2strings))))
 529         goto err;
 530     BN_free(b);
 531     if (!(TEST_ptr(b = BN_dup(a))
 532             && TEST_true(BN_MONT_CTX_set(mont, n, ctx))
 533             && TEST_true(BN_mod_mul_montgomery(c, a, a, mont, ctx))
 534             && TEST_true(BN_mod_mul_montgomery(d, a, b, mont, ctx))
 535             && TEST_BN_eq(c, d)))
 536         goto err;
 537
 538     /* Regression test for carry bug in bn_sqrx8x_internal */
 539     {
 540         static const char *ahex[] = {
 541                       "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 542             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 543             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 544             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 545             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8FFEADBCFC4DAE7FFF908E92820306B",
 546             "9544D954000000006C0000000000000000000000000000000000000000000000",
 547             "00000000000000000000FF030202FFFFF8FFEBDBCFC4DAE7FFF908E92820306B",
 548             "9544D954000000006C000000FF0302030000000000FFFFFFFFFFFFFFFFFFFFFF",
 549             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF01FC00FF02FFFFFFFF",
 550             "00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00FCFD",
 551             "FCFFFFFFFFFF000000000000000000FF0302030000000000FFFFFFFFFFFFFFFF",
 552             "FF00FCFDFDFF030202FF00000000FFFFFFFFFFFFFFFFFF00FCFDFCFFFFFFFFFF",
 553             NULL
 554         };
 555         static const char *nhex[] = {
 556                       "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 557             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 558             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 559             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 560             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8F8F8F8000000",
 561             "00000010000000006C0000000000000000000000000000000000000000000000",
 562             "00000000000000000000000000000000000000FFFFFFFFFFFFF8F8F8F8000000",
 563             "00000010000000006C000000000000000000000000FFFFFFFFFFFFFFFFFFFFFF",
 564             "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 565             "00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 566             "FFFFFFFFFFFF000000000000000000000000000000000000FFFFFFFFFFFFFFFF",
 567             "FFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 568             NULL
 569         };
 570
 571         if (!(TEST_true(parse_bigBN(&a, ahex))
 572                 && TEST_true(parse_bigBN(&n, nhex))))
 573             goto err;
 574     }
 575     BN_free(b);
 576     if (!(TEST_ptr(b = BN_dup(a))
 577             && TEST_true(BN_MONT_CTX_set(mont, n, ctx))))
 578         goto err;
 579
 580     if (!TEST_true(BN_mod_mul_montgomery(c, a, a, mont, ctx))
 581             || !TEST_true(BN_mod_mul_montgomery(d, a, b, mont, ctx))
 582             || !TEST_BN_eq(c, d))
 583         goto err;
 584
 585     /* Regression test for bug in BN_from_montgomery_word */
 586     if (!(TEST_true(BN_hex2bn(&a,
 587         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 588         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 589         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"))
 590          && TEST_true(BN_hex2bn(&n,
 591         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 592         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"))
 593         && TEST_true(BN_MONT_CTX_set(mont, n, ctx))
 594         && TEST_false(BN_mod_mul_montgomery(d, a, a, mont, ctx))))
 595         goto err;
 596
 597     /* Regression test for bug in rsaz_1024_mul_avx2 */
 598     if (!(TEST_true(BN_hex2bn(&a,
 599         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 600         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 601         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 602         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF"))
 603         && TEST_true(BN_hex2bn(&b,
 604         "2020202020202020202020202020202020202020202020202020202020202020"
 605         "2020202020202020202020202020202020202020202020202020202020202020"
 606         "20202020202020FF202020202020202020202020202020202020202020202020"
 607         "2020202020202020202020202020202020202020202020202020202020202020"))
 608         && TEST_true(BN_hex2bn(&n,
 609         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 610         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 611         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 612         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020FF"))
 613         && TEST_true(BN_MONT_CTX_set(mont, n, ctx))
 614         && TEST_true(BN_mod_exp_mont_consttime(c, a, b, n, ctx, mont))
 615         && TEST_true(BN_mod_exp_mont(d, a, b, n, ctx, mont))
 616         && TEST_BN_eq(c, d)))
 617         goto err;
 618
 619     /*
 620      * rsaz_1024_mul_avx2 expects fully-reduced inputs.
 621      * BN_mod_exp_mont_consttime should reduce the input first.
 622      */
 623     if (!(TEST_true(BN_hex2bn(&a,
 624         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 625         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 626         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 627         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF"))
 628         && TEST_true(BN_hex2bn(&b,
 629         "1FA53F26F8811C58BE0357897AA5E165693230BC9DF5F01DFA6A2D59229EC69D"
 630         "9DE6A89C36E3B6957B22D6FAAD5A3C73AE587B710DBE92E83D3A9A3339A085CB"
 631         "B58F508CA4F837924BB52CC1698B7FDC2FD74362456A595A5B58E38E38E38E38"
 632         "E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E"))
 633         && TEST_true(BN_hex2bn(&n,
 634         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 635         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 636         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
 637         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF"))
 638         && TEST_true(BN_MONT_CTX_set(mont, n, ctx))
 639         && TEST_true(BN_mod_exp_mont_consttime(c, a, b, n, ctx, mont))))
 640         goto err;
 641     BN_zero(d);
 642     if (!TEST_BN_eq(c, d))
 643         goto err;
 644
 645     /*
 646      * Regression test for overflow bug in bn_sqr_comba4/8 for
 647      * mips-linux-gnu and mipsel-linux-gnu 32bit targets.
 648      */
 649     {
 650         static const char *ehex[] = {
 651             "95564994a96c45954227b845a1e99cb939d5a1da99ee91acc962396ae999a9ee",
 652             "38603790448f2f7694c242a875f0cad0aae658eba085f312d2febbbd128dd2b5",
 653             "8f7d1149f03724215d704344d0d62c587ae3c5939cba4b9b5f3dc5e8e911ef9a",
 654             "5ce1a5a749a4989d0d8368f6e1f8cdf3a362a6c97fb02047ff152b480a4ad985",
 655             "2d45efdf0770542992afca6a0590d52930434bba96017afbc9f99e112950a8b1",
 656             "a359473ec376f329bdae6a19f503be6d4be7393c4e43468831234e27e3838680",
 657             "b949390d2e416a3f9759e5349ab4c253f6f29f819a6fe4cbfd27ada34903300e",
 658             "da021f62839f5878a36f1bc3085375b00fd5fa3e68d316c0fdace87a97558465",
 659             NULL};
 660         static const char *phex[] = {
 661             "f95dc0f980fbd22e90caa5a387cc4a369f3f830d50dd321c40db8c09a7e1a241",
 662             "a536e096622d3280c0c1ba849c1f4a79bf490f60006d081e8cf69960189f0d31",
 663             "2cd9e17073a3fba7881b21474a13b334116cb2f5dbf3189a6de3515d0840f053",
 664             "c776d3982d391b6d04d642dda5cc6d1640174c09875addb70595658f89efb439",
 665             "dc6fbd55f903aadd307982d3f659207f265e1ec6271b274521b7a5e28e8fd7a5",
 666             "5df089292820477802a43cf5b6b94e999e8c9944ddebb0d0e95a60f88cb7e813",
 667             "ba110d20e1024774107dd02949031864923b3cb8c3f7250d6d1287b0a40db6a4",
 668             "7bd5a469518eb65aa207ddc47d8c6e5fc8e0c105be8fc1d4b57b2e27540471d5",
 669             NULL};
 670         static const char *mhex[] = {
 671             "fef15d5ce4625f1bccfbba49fc8439c72bf8202af039a2259678941b60bb4a8f",
 672             "2987e965d58fd8cf86a856674d519763d0e1211cc9f8596971050d56d9b35db3",
 673             "785866cfbca17cfdbed6060be3629d894f924a89fdc1efc624f80d41a22f1900",
 674             "9503fcc3824ef62ccb9208430c26f2d8ceb2c63488ec4c07437aa4c96c43dd8b",
 675             "9289ed00a712ff66ee195dc71f5e4ead02172b63c543d69baf495f5fd63ba7bc",
 676             "c633bd309c016e37736da92129d0b053d4ab28d21ad7d8b6fab2a8bbdc8ee647",
 677             "d2fbcf2cf426cf892e6f5639e0252993965dfb73ccd277407014ea784aaa280c",
 678             "b7b03972bc8b0baa72360bdb44b82415b86b2f260f877791cd33ba8f2d65229b",
 679             NULL};
 680
 681         if (!TEST_true(parse_bigBN(&e, ehex))
 682                 || !TEST_true(parse_bigBN(&p, phex))
 683                 || !TEST_true(parse_bigBN(&m, mhex))
 684                 || !TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
 685                 || !TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))
 686                 || !TEST_BN_eq(a, d))
 687             goto err;
 688     }
 689
 690     /* Zero input */
 691     if (!TEST_true(BN_bntest_rand(p, 1024, 0, 0)))
 692         goto err;
 693     BN_zero(a);
 694     if (!TEST_true(BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
 695             || !TEST_BN_eq_zero(d))
 696         goto err;
 697
 698     /*
 699      * Craft an input whose Montgomery representation is 1, i.e., shorter
 700      * than the modulus m, in order to test the const time precomputation
 701      * scattering/gathering.
 702      */
 703     if (!(TEST_true(BN_one(a))
 704             && TEST_true(BN_MONT_CTX_set(mont, m, ctx))))
 705         goto err;
 706     if (!TEST_true(BN_from_montgomery(e, a, mont, ctx))
 707             || !TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
 708             || !TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))
 709             || !TEST_BN_eq(a, d))
 710         goto err;
 711
 712     /* Finally, some regular test vectors. */
 713     if (!(TEST_true(BN_bntest_rand(e, 1024, 0, 0))
 714             && TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
 715             && TEST_true(BN_mod_exp_simple(a, e, p, m, ctx))
 716             && TEST_BN_eq(a, d)))
 717         goto err;
 718
 719     st = 1;
 720
 721  err:
 722     BN_MONT_CTX_free(mont);
 723     BN_free(a);
 724     BN_free(p);
 725     BN_free(m);
 726     BN_free(d);
 727     BN_free(e);
 728     BN_free(b);
 729     BN_free(n);
 730     BN_free(c);
 731     return st;
 732 }
 733
 734 #ifndef OPENSSL_NO_EC2M
 735 static int test_gf2m_add(void)
 736 {
 737     BIGNUM *a = NULL, *b = NULL, *c = NULL;
 738     int i, st = 0;
 739
 740     if (!TEST_ptr(a = BN_new())
 741             || !TEST_ptr(b = BN_new())
 742             || !TEST_ptr(c = BN_new()))
 743         goto err;
 744
 745     for (i = 0; i < NUM0; i++) {
 746         if (!(TEST_true(BN_rand(a, 512, 0, 0))
 747                 && TEST_ptr(BN_copy(b, BN_value_one()))))
 748             goto err;
 749         BN_set_negative(a, rand_neg());
 750         BN_set_negative(b, rand_neg());
 751         if (!(TEST_true(BN_GF2m_add(c, a, b))
 752                 /* Test that two added values have the correct parity. */
 753                 && TEST_false((BN_is_odd(a) && BN_is_odd(c))
 754                         || (!BN_is_odd(a) && !BN_is_odd(c)))))
 755             goto err;
 756         if (!(TEST_true(BN_GF2m_add(c, c, c))
 757                 /* Test that c + c = 0. */
 758                 && TEST_BN_eq_zero(c)))
 759             goto err;
 760     }
 761     st = 1;
 762  err:
 763     BN_free(a);
 764     BN_free(b);
 765     BN_free(c);
 766     return st;
 767 }
 768
 769 static int test_gf2m_mod(void)
 770 {
 771     BIGNUM *a = NULL, *b[2] = {NULL, NULL}, *c = NULL, *d = NULL, *e = NULL;
 772     int i, j, st = 0;
 773
 774     if (!TEST_ptr(a = BN_new())
 775             || !TEST_ptr(b[0] = BN_new())
 776             || !TEST_ptr(b[1] = BN_new())
 777             || !TEST_ptr(c = BN_new())
 778             || !TEST_ptr(d = BN_new())
 779             || !TEST_ptr(e = BN_new()))
 780         goto err;
 781
 782     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
 783             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
 784         goto err;
 785
 786     for (i = 0; i < NUM0; i++) {
 787         if (!TEST_true(BN_bntest_rand(a, 1024, 0, 0)))
 788             goto err;
 789         for (j = 0; j < 2; j++) {
 790             if (!(TEST_true(BN_GF2m_mod(c, a, b[j]))
 791                     && TEST_true(BN_GF2m_add(d, a, c))
 792                     && TEST_true(BN_GF2m_mod(e, d, b[j]))
 793                     /* Test that a + (a mod p) mod p == 0. */
 794                     && TEST_BN_eq_zero(e)))
 795                 goto err;
 796         }
 797     }
 798     st = 1;
 799  err:
 800     BN_free(a);
 801     BN_free(b[0]);
 802     BN_free(b[1]);
 803     BN_free(c);
 804     BN_free(d);
 805     BN_free(e);
 806     return st;
 807 }
 808
 809 static int test_gf2m_mul(void)
 810 {
 811     BIGNUM *a, *b[2] = {NULL, NULL}, *c = NULL, *d = NULL;
 812     BIGNUM *e = NULL, *f = NULL, *g = NULL, *h = NULL;
 813     int i, j, st = 0;
 814
 815     if (!TEST_ptr(a = BN_new())
 816             || !TEST_ptr(b[0] = BN_new())
 817             || !TEST_ptr(b[1] = BN_new())
 818             || !TEST_ptr(c = BN_new())
 819             || !TEST_ptr(d = BN_new())
 820             || !TEST_ptr(e = BN_new())
 821             || !TEST_ptr(f = BN_new())
 822             || !TEST_ptr(g = BN_new())
 823             || !TEST_ptr(h = BN_new()))
 824         goto err;
 825
 826     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
 827             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
 828         goto err;
 829
 830     for (i = 0; i < NUM0; i++) {
 831         if (!(TEST_true(BN_bntest_rand(a, 1024, 0, 0))
 832                 && TEST_true(BN_bntest_rand(c, 1024, 0, 0))
 833                 && TEST_true(BN_bntest_rand(d, 1024, 0, 0))))
 834             goto err;
 835         for (j = 0; j < 2; j++) {
 836             if (!(TEST_true(BN_GF2m_mod_mul(e, a, c, b[j], ctx))
 837                     && TEST_true(BN_GF2m_add(f, a, d))
 838                     && TEST_true(BN_GF2m_mod_mul(g, f, c, b[j], ctx))
 839                     && TEST_true(BN_GF2m_mod_mul(h, d, c, b[j], ctx))
 840                     && TEST_true(BN_GF2m_add(f, e, g))
 841                     && TEST_true(BN_GF2m_add(f, f, h))
 842                     /* Test that (a+d)*c = a*c + d*c. */
 843                     && TEST_BN_eq_zero(f)))
 844                 goto err;
 845         }
 846     }
 847     st = 1;
 848
 849  err:
 850     BN_free(a);
 851     BN_free(b[0]);
 852     BN_free(b[1]);
 853     BN_free(c);
 854     BN_free(d);
 855     BN_free(e);
 856     BN_free(f);
 857     BN_free(g);
 858     BN_free(h);
 859     return st;
 860 }
 861
 862 static int test_gf2m_sqr(void)
 863 {
 864     BIGNUM *a = NULL, *b[2] = {NULL, NULL}, *c = NULL, *d = NULL;
 865     int i, j, st = 0;
 866
 867     if (!TEST_ptr(a = BN_new())
 868             || !TEST_ptr(b[0] = BN_new())
 869             || !TEST_ptr(b[1] = BN_new())
 870             || !TEST_ptr(c = BN_new())
 871             || !TEST_ptr(d = BN_new()))
 872         goto err;
 873
 874     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
 875             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
 876         goto err;
 877
 878     for (i = 0; i < NUM0; i++) {
 879         if (!TEST_true(BN_bntest_rand(a, 1024, 0, 0)))
 880                 goto err;
 881         for (j = 0; j < 2; j++) {
 882             if (!(TEST_true(BN_GF2m_mod_sqr(c, a, b[j], ctx))
 883                     && TEST_true(BN_copy(d, a))
 884                     && TEST_true(BN_GF2m_mod_mul(d, a, d, b[j], ctx))
 885                     && TEST_true(BN_GF2m_add(d, c, d))
 886                     /* Test that a*a = a^2. */
 887                     && TEST_BN_eq_zero(d)))
 888                 goto err;
 889         }
 890     }
 891     st = 1;
 892  err:
 893     BN_free(a);
 894     BN_free(b[0]);
 895     BN_free(b[1]);
 896     BN_free(c);
 897     BN_free(d);
 898     return st;
 899 }
 900
 901 static int test_gf2m_modinv(void)
 902 {
 903     BIGNUM *a = NULL, *b[2] = {NULL, NULL}, *c = NULL, *d = NULL;
 904     int i, j, st = 0;
 905
 906     if (!TEST_ptr(a = BN_new())
 907             || !TEST_ptr(b[0] = BN_new())
 908             || !TEST_ptr(b[1] = BN_new())
 909             || !TEST_ptr(c = BN_new())
 910             || !TEST_ptr(d = BN_new()))
 911         goto err;
 912
 913     /* Test that a non-sensical, too small value causes a failure */
 914     if (!TEST_true(BN_one(b[0])))
 915         goto err;
 916     if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
 917         goto err;
 918     if (!TEST_false(BN_GF2m_mod_inv(c, a, b[0], ctx)))
 919         goto err;
 920
 921     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
 922             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
 923         goto err;
 924
 925     for (i = 0; i < NUM0; i++) {
 926         if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
 927             goto err;
 928         for (j = 0; j < 2; j++) {
 929             if (!(TEST_true(BN_GF2m_mod_inv(c, a, b[j], ctx))
 930                     && TEST_true(BN_GF2m_mod_mul(d, a, c, b[j], ctx))
 931                     /* Test that ((1/a)*a) = 1. */
 932                     && TEST_BN_eq_one(d)))
 933                 goto err;
 934         }
 935     }
 936     st = 1;
 937  err:
 938     BN_free(a);
 939     BN_free(b[0]);
 940     BN_free(b[1]);
 941     BN_free(c);
 942     BN_free(d);
 943     return st;
 944 }
 945
 946 static int test_gf2m_moddiv(void)
 947 {
 948     BIGNUM *a = NULL, *b[2] = {NULL, NULL}, *c = NULL, *d = NULL;
 949     BIGNUM *e = NULL, *f = NULL;
 950     int i, j, st = 0;
 951
 952     if (!TEST_ptr(a = BN_new())
 953             || !TEST_ptr(b[0] = BN_new())
 954             || !TEST_ptr(b[1] = BN_new())
 955             || !TEST_ptr(c = BN_new())
 956             || !TEST_ptr(d = BN_new())
 957             || !TEST_ptr(e = BN_new())
 958             || !TEST_ptr(f = BN_new()))
 959         goto err;
 960
 961     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
 962             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
 963         goto err;
 964
 965     for (i = 0; i < NUM0; i++) {
 966         if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0))
 967                 && TEST_true(BN_bntest_rand(c, 512, 0, 0))))
 968             goto err;
 969         for (j = 0; j < 2; j++) {
 970             if (!(TEST_true(BN_GF2m_mod_div(d, a, c, b[j], ctx))
 971                     && TEST_true(BN_GF2m_mod_mul(e, d, c, b[j], ctx))
 972                     && TEST_true(BN_GF2m_mod_div(f, a, e, b[j], ctx))
 973                     /* Test that ((a/c)*c)/a = 1. */
 974                     && TEST_BN_eq_one(f)))
 975                 goto err;
 976         }
 977     }
 978     st = 1;
 979  err:
 980     BN_free(a);
 981     BN_free(b[0]);
 982     BN_free(b[1]);
 983     BN_free(c);
 984     BN_free(d);
 985     BN_free(e);
 986     BN_free(f);
 987     return st;
 988 }
 989
 990 static int test_gf2m_modexp(void)
 991 {
 992     BIGNUM *a = NULL, *b[2] = {NULL, NULL}, *c = NULL, *d = NULL;
 993     BIGNUM *e = NULL, *f = NULL;
 994     int i, j, st = 0;
 995
 996     if (!TEST_ptr(a = BN_new())
 997             || !TEST_ptr(b[0] = BN_new())
 998             || !TEST_ptr(b[1] = BN_new())
 999             || !TEST_ptr(c = BN_new())
1000             || !TEST_ptr(d = BN_new())
1001             || !TEST_ptr(e = BN_new())
1002             || !TEST_ptr(f = BN_new()))
1003         goto err;
1004
1005     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
1006             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
1007         goto err;
1008
1009     for (i = 0; i < NUM0; i++) {
1010         if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0))
1011                 && TEST_true(BN_bntest_rand(c, 512, 0, 0))
1012                 && TEST_true(BN_bntest_rand(d, 512, 0, 0))))
1013             goto err;
1014         for (j = 0; j < 2; j++) {
1015             if (!(TEST_true(BN_GF2m_mod_exp(e, a, c, b[j], ctx))
1016                     && TEST_true(BN_GF2m_mod_exp(f, a, d, b[j], ctx))
1017                     && TEST_true(BN_GF2m_mod_mul(e, e, f, b[j], ctx))
1018                     && TEST_true(BN_add(f, c, d))
1019                     && TEST_true(BN_GF2m_mod_exp(f, a, f, b[j], ctx))
1020                     && TEST_true(BN_GF2m_add(f, e, f))
1021                     /* Test that a^(c+d)=a^c*a^d. */
1022                     && TEST_BN_eq_zero(f)))
1023                 goto err;
1024         }
1025     }
1026     st = 1;
1027  err:
1028     BN_free(a);
1029     BN_free(b[0]);
1030     BN_free(b[1]);
1031     BN_free(c);
1032     BN_free(d);
1033     BN_free(e);
1034     BN_free(f);
1035     return st;
1036 }
1037
1038 static int test_gf2m_modsqrt(void)
1039 {
1040     BIGNUM *a = NULL, *b[2] = {NULL, NULL}, *c = NULL, *d = NULL;
1041     BIGNUM *e = NULL, *f = NULL;
1042     int i, j, st = 0;
1043
1044     if (!TEST_ptr(a = BN_new())
1045             || !TEST_ptr(b[0] = BN_new())
1046             || !TEST_ptr(b[1] = BN_new())
1047             || !TEST_ptr(c = BN_new())
1048             || !TEST_ptr(d = BN_new())
1049             || !TEST_ptr(e = BN_new())
1050             || !TEST_ptr(f = BN_new()))
1051         goto err;
1052
1053     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
1054             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
1055         goto err;
1056
1057     for (i = 0; i < NUM0; i++) {
1058         if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
1059             goto err;
1060
1061         for (j = 0; j < 2; j++) {
1062             if (!(TEST_true(BN_GF2m_mod(c, a, b[j]))
1063                     && TEST_true(BN_GF2m_mod_sqrt(d, a, b[j], ctx))
1064                     && TEST_true(BN_GF2m_mod_sqr(e, d, b[j], ctx))
1065                     && TEST_true(BN_GF2m_add(f, c, e))
1066                     /* Test that d^2 = a, where d = sqrt(a). */
1067                     && TEST_BN_eq_zero(f)))
1068                 goto err;
1069         }
1070     }
1071     st = 1;
1072  err:
1073     BN_free(a);
1074     BN_free(b[0]);
1075     BN_free(b[1]);
1076     BN_free(c);
1077     BN_free(d);
1078     BN_free(e);
1079     BN_free(f);
1080     return st;
1081 }
1082
1083 static int test_gf2m_modsolvequad(void)
1084 {
1085     BIGNUM *a = NULL, *b[2] = {NULL, NULL}, *c = NULL, *d = NULL;
1086     BIGNUM *e = NULL;
1087     int i, j, s = 0, t, st = 0;
1088
1089     if (!TEST_ptr(a = BN_new())
1090             || !TEST_ptr(b[0] = BN_new())
1091             || !TEST_ptr(b[1] = BN_new())
1092             || !TEST_ptr(c = BN_new())
1093             || !TEST_ptr(d = BN_new())
1094             || !TEST_ptr(e = BN_new()))
1095         goto err;
1096
1097     if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0]))
1098             && TEST_true(BN_GF2m_arr2poly(p1, b[1]))))
1099         goto err;
1100
1101     for (i = 0; i < NUM0; i++) {
1102         if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
1103             goto err;
1104         for (j = 0; j < 2; j++) {
1105             t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
1106             if (t) {
1107                 s++;
1108                 if (!(TEST_true(BN_GF2m_mod_sqr(d, c, b[j], ctx))
1109                         && TEST_true(BN_GF2m_add(d, c, d))
1110                         && TEST_true(BN_GF2m_mod(e, a, b[j]))
1111                         && TEST_true(BN_GF2m_add(e, e, d))
1112                         /*
1113                          * Test that solution of quadratic c
1114                          * satisfies c^2 + c = a.
1115                          */
1116                         && TEST_BN_eq_zero(e)))
1117                     goto err;
1118             }
1119         }
1120     }
1121     if (!TEST_int_ge(s, 0)) {
1122         TEST_info("%d tests found no roots; probably an error", NUM0);
1123         goto err;
1124     }
1125     st = 1;
1126  err:
1127     BN_free(a);
1128     BN_free(b[0]);
1129     BN_free(b[1]);
1130     BN_free(c);
1131     BN_free(d);
1132     BN_free(e);
1133     return st;
1134 }
1135 #endif
1136
1137 static int test_kronecker(void)
1138 {
1139     BIGNUM *a = NULL, *b = NULL, *r = NULL, *t = NULL;
1140     int i, legendre, kronecker, st = 0;
1141
1142     if (!TEST_ptr(a = BN_new())
1143             || !TEST_ptr(b = BN_new())
1144             || !TEST_ptr(r = BN_new())
1145             || !TEST_ptr(t = BN_new()))
1146         goto err;
1147
1148     /*
1149      * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
1150      * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
1151      * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
1152      * generate a random prime b and compare these values for a number of
1153      * random a's.  (That is, we run the Solovay-Strassen primality test to
1154      * confirm that b is prime, except that we don't want to test whether b
1155      * is prime but whether BN_kronecker works.)
1156      */
1157
1158     if (!TEST_true(BN_generate_prime_ex(b, 512, 0, NULL, NULL, NULL)))
1159         goto err;
1160     BN_set_negative(b, rand_neg());
1161
1162     for (i = 0; i < NUM0; i++) {
1163         if (!TEST_true(BN_bntest_rand(a, 512, 0, 0)))
1164             goto err;
1165         BN_set_negative(a, rand_neg());
1166
1167         /* t := (|b|-1)/2  (note that b is odd) */
1168         if (!TEST_true(BN_copy(t, b)))
1169             goto err;
1170         BN_set_negative(t, 0);
1171         if (!TEST_true(BN_sub_word(t, 1)))
1172             goto err;
1173         if (!TEST_true(BN_rshift1(t, t)))
1174             goto err;
1175         /* r := a^t mod b */
1176         BN_set_negative(b, 0);
1177
1178         if (!TEST_true(BN_mod_exp_recp(r, a, t, b, ctx)))
1179             goto err;
1180         BN_set_negative(b, 1);
1181
1182         if (BN_is_word(r, 1))
1183             legendre = 1;
1184         else if (BN_is_zero(r))
1185             legendre = 0;
1186         else {
1187             if (!TEST_true(BN_add_word(r, 1)))
1188                 goto err;
1189             if (!TEST_int_eq(BN_ucmp(r, b), 0)) {
1190                 TEST_info("Legendre symbol computation failed");
1191                 goto err;
1192             }
1193             legendre = -1;
1194         }
1195
1196         if (!TEST_int_ge(kronecker = BN_kronecker(a, b, ctx), -1))
1197             goto err;
1198         /* we actually need BN_kronecker(a, |b|) */
1199         if (BN_is_negative(a) && BN_is_negative(b))
1200             kronecker = -kronecker;
1201
1202         if (!TEST_int_eq(legendre, kronecker))
1203             goto err;
1204     }
1205
1206     st = 1;
1207  err:
1208     BN_free(a);
1209     BN_free(b);
1210     BN_free(r);
1211     BN_free(t);
1212     return st;
1213 }
1214
1215 static int file_sum(STANZA *s)
1216 {
1217     BIGNUM *a = NULL, *b = NULL, *sum = NULL, *ret = NULL;
1218     BN_ULONG b_word;
1219     int st = 0;
1220
1221     if (!TEST_ptr(a = getBN(s, "A"))
1222             || !TEST_ptr(b = getBN(s, "B"))
1223             || !TEST_ptr(sum = getBN(s, "Sum"))
1224             || !TEST_ptr(ret = BN_new()))
1225         goto err;
1226
1227     if (!TEST_true(BN_add(ret, a, b))
1228             || !equalBN("A + B", sum, ret)
1229             || !TEST_true(BN_sub(ret, sum, a))
1230             || !equalBN("Sum - A", b, ret)
1231             || !TEST_true(BN_sub(ret, sum, b))
1232             || !equalBN("Sum - B", a, ret))
1233         goto err;
1234
1235     /*
1236      * Test that the functions work when |r| and |a| point to the same BIGNUM,
1237      * or when |r| and |b| point to the same BIGNUM.
1238      * There is no test for all of |r|, |a|, and |b| pointint to the same BIGNUM.
1239      */
1240     if (!TEST_true(BN_copy(ret, a))
1241             || !TEST_true(BN_add(ret, ret, b))
1242             || !equalBN("A + B (r is a)", sum, ret)
1243             || !TEST_true(BN_copy(ret, b))
1244             || !TEST_true(BN_add(ret, a, ret))
1245             || !equalBN("A + B (r is b)", sum, ret)
1246             || !TEST_true(BN_copy(ret, sum))
1247             || !TEST_true(BN_sub(ret, ret, a))
1248             || !equalBN("Sum - A (r is a)", b, ret)
1249             || !TEST_true(BN_copy(ret, a))
1250             || !TEST_true(BN_sub(ret, sum, ret))
1251             || !equalBN("Sum - A (r is b)", b, ret)
1252             || !TEST_true(BN_copy(ret, sum))
1253             || !TEST_true(BN_sub(ret, ret, b))
1254             || !equalBN("Sum - B (r is a)", a, ret)
1255             || !TEST_true(BN_copy(ret, b))
1256             || !TEST_true(BN_sub(ret, sum, ret))
1257             || !equalBN("Sum - B (r is b)", a, ret))
1258         goto err;
1259
1260     /*
1261      * Test BN_uadd() and BN_usub() with the prerequisites they are
1262      * documented as having. Note that these functions are frequently used
1263      * when the prerequisites don't hold. In those cases, they are supposed
1264      * to work as if the prerequisite hold, but we don't test that yet.
1265      */
1266     if (!BN_is_negative(a) && !BN_is_negative(b) && BN_cmp(a, b) >= 0) {
1267         if (!TEST_true(BN_uadd(ret, a, b))
1268                 || !equalBN("A +u B", sum, ret)
1269                 || !TEST_true(BN_usub(ret, sum, a))
1270                 || !equalBN("Sum -u A", b, ret)
1271                 || !TEST_true(BN_usub(ret, sum, b))
1272                 || !equalBN("Sum -u B", a, ret))
1273             goto err;
1274         /*
1275          * Test that the functions work when |r| and |a| point to the same
1276          * BIGNUM, or when |r| and |b| point to the same BIGNUM.
1277          * There is no test for all of |r|, |a|, and |b| pointint to the same
1278          * BIGNUM.
1279          */
1280         if (!TEST_true(BN_copy(ret, a))
1281                 || !TEST_true(BN_uadd(ret, ret, b))
1282                 || !equalBN("A +u B (r is a)", sum, ret)
1283                 || !TEST_true(BN_copy(ret, b))
1284                 || !TEST_true(BN_uadd(ret, a, ret))
1285                 || !equalBN("A +u B (r is b)", sum, ret)
1286                 || !TEST_true(BN_copy(ret, sum))
1287                 || !TEST_true(BN_usub(ret, ret, a))
1288                 || !equalBN("Sum -u A (r is a)", b, ret)
1289                 || !TEST_true(BN_copy(ret, a))
1290                 || !TEST_true(BN_usub(ret, sum, ret))
1291                 || !equalBN("Sum -u A (r is b)", b, ret)
1292                 || !TEST_true(BN_copy(ret, sum))
1293                 || !TEST_true(BN_usub(ret, ret, b))
1294                 || !equalBN("Sum -u B (r is a)", a, ret)
1295                 || !TEST_true(BN_copy(ret, b))
1296                 || !TEST_true(BN_usub(ret, sum, ret))
1297                 || !equalBN("Sum -u B (r is b)", a, ret))
1298             goto err;
1299     }
1300
1301     /*
1302      * Test with BN_add_word() and BN_sub_word() if |b| is small enough.
1303      */
1304     b_word = BN_get_word(b);
1305     if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
1306         if (!TEST_true(BN_copy(ret, a))
1307                 || !TEST_true(BN_add_word(ret, b_word))
1308                 || !equalBN("A + B (word)", sum, ret)
1309                 || !TEST_true(BN_copy(ret, sum))
1310                 || !TEST_true(BN_sub_word(ret, b_word))
1311                 || !equalBN("Sum - B (word)", a, ret))
1312             goto err;
1313     }
1314     st = 1;
1315
1316  err:
1317     BN_free(a);
1318     BN_free(b);
1319     BN_free(sum);
1320     BN_free(ret);
1321     return st;
1322 }
1323
1324 static int file_lshift1(STANZA *s)
1325 {
1326     BIGNUM *a = NULL, *lshift1 = NULL, *zero = NULL, *ret = NULL;
1327     BIGNUM *two = NULL, *remainder = NULL;
1328     int st = 0;
1329
1330     if (!TEST_ptr(a = getBN(s, "A"))
1331             || !TEST_ptr(lshift1 = getBN(s, "LShift1"))
1332             || !TEST_ptr(zero = BN_new())
1333             || !TEST_ptr(ret = BN_new())
1334             || !TEST_ptr(two = BN_new())
1335             || !TEST_ptr(remainder = BN_new()))
1336         goto err;
1337
1338     BN_zero(zero);
1339
1340     if (!TEST_true(BN_set_word(two, 2))
1341             || !TEST_true(BN_add(ret, a, a))
1342             || !equalBN("A + A", lshift1, ret)
1343             || !TEST_true(BN_mul(ret, a, two, ctx))
1344             || !equalBN("A * 2", lshift1, ret)
1345             || !TEST_true(BN_div(ret, remainder, lshift1, two, ctx))
1346             || !equalBN("LShift1 / 2", a, ret)
1347             || !equalBN("LShift1 % 2", zero, remainder)
1348             || !TEST_true(BN_lshift1(ret, a))
1349             || !equalBN("A << 1", lshift1, ret)
1350             || !TEST_true(BN_rshift1(ret, lshift1))
1351             || !equalBN("LShift >> 1", a, ret)
1352             || !TEST_true(BN_rshift1(ret, lshift1))
1353             || !equalBN("LShift >> 1", a, ret))
1354         goto err;
1355
1356     /* Set the LSB to 1 and test rshift1 again. */
1357     if (!TEST_true(BN_set_bit(lshift1, 0))
1358             || !TEST_true(BN_div(ret, NULL /* rem */ , lshift1, two, ctx))
1359             || !equalBN("(LShift1 | 1) / 2", a, ret)
1360             || !TEST_true(BN_rshift1(ret, lshift1))
1361             || !equalBN("(LShift | 1) >> 1", a, ret))
1362         goto err;
1363
1364     st = 1;
1365  err:
1366     BN_free(a);
1367     BN_free(lshift1);
1368     BN_free(zero);
1369     BN_free(ret);
1370     BN_free(two);
1371     BN_free(remainder);
1372
1373     return st;
1374 }
1375
1376 static int file_lshift(STANZA *s)
1377 {
1378     BIGNUM *a = NULL, *lshift = NULL, *ret = NULL;
1379     int n = 0, st = 0;
1380
1381     if (!TEST_ptr(a = getBN(s, "A"))
1382             || !TEST_ptr(lshift = getBN(s, "LShift"))
1383             || !TEST_ptr(ret = BN_new())
1384             || !getint(s, &n, "N"))
1385         goto err;
1386
1387     if (!TEST_true(BN_lshift(ret, a, n))
1388             || !equalBN("A << N", lshift, ret)
1389             || !TEST_true(BN_rshift(ret, lshift, n))
1390             || !equalBN("A >> N", a, ret))
1391         goto err;
1392
1393     st = 1;
1394  err:
1395     BN_free(a);
1396     BN_free(lshift);
1397     BN_free(ret);
1398     return st;
1399 }
1400
1401 static int file_rshift(STANZA *s)
1402 {
1403     BIGNUM *a = NULL, *rshift = NULL, *ret = NULL;
1404     int n = 0, st = 0;
1405
1406     if (!TEST_ptr(a = getBN(s, "A"))
1407             || !TEST_ptr(rshift = getBN(s, "RShift"))
1408             || !TEST_ptr(ret = BN_new())
1409             || !getint(s, &n, "N"))
1410         goto err;
1411
1412     if (!TEST_true(BN_rshift(ret, a, n))
1413             || !equalBN("A >> N", rshift, ret))
1414         goto err;
1415
1416     /* If N == 1, try with rshift1 as well */
1417     if (n == 1) {
1418         if (!TEST_true(BN_rshift1(ret, a))
1419                 || !equalBN("A >> 1 (rshift1)", rshift, ret))
1420             goto err;
1421     }
1422     st = 1;
1423
1424  err:
1425     BN_free(a);
1426     BN_free(rshift);
1427     BN_free(ret);
1428     return st;
1429 }
1430
1431 static int file_square(STANZA *s)
1432 {
1433     BIGNUM *a = NULL, *square = NULL, *zero = NULL, *ret = NULL;
1434     BIGNUM *remainder = NULL, *tmp = NULL;
1435     int st = 0;
1436
1437     if (!TEST_ptr(a = getBN(s, "A"))
1438             || !TEST_ptr(square = getBN(s, "Square"))
1439             || !TEST_ptr(zero = BN_new())
1440             || !TEST_ptr(ret = BN_new())
1441             || !TEST_ptr(remainder = BN_new()))
1442         goto err;
1443
1444     BN_zero(zero);
1445     if (!TEST_true(BN_sqr(ret, a, ctx))
1446             || !equalBN("A^2", square, ret)
1447             || !TEST_true(BN_mul(ret, a, a, ctx))
1448             || !equalBN("A * A", square, ret)
1449             || !TEST_true(BN_div(ret, remainder, square, a, ctx))
1450             || !equalBN("Square / A", a, ret)
1451             || !equalBN("Square % A", zero, remainder))
1452         goto err;
1453
1454 #if HAVE_BN_SQRT
1455     BN_set_negative(a, 0);
1456     if (!TEST_true(BN_sqrt(ret, square, ctx))
1457             || !equalBN("sqrt(Square)", a, ret))
1458         goto err;
1459
1460     /* BN_sqrt should fail on non-squares and negative numbers. */
1461     if (!TEST_BN_eq_zero(square)) {
1462         if (!TEST_ptr(tmp = BN_new())
1463                 || !TEST_true(BN_copy(tmp, square)))
1464             goto err;
1465         BN_set_negative(tmp, 1);
1466
1467         if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx), 0))
1468             goto err;
1469         ERR_clear_error();
1470
1471         BN_set_negative(tmp, 0);
1472         if (BN_add(tmp, tmp, BN_value_one()))
1473             goto err;
1474         if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx)))
1475             goto err;
1476         ERR_clear_error();
1477     }
1478 #endif
1479
1480     st = 1;
1481  err:
1482     BN_free(a);
1483     BN_free(square);
1484     BN_free(zero);
1485     BN_free(ret);
1486     BN_free(remainder);
1487     BN_free(tmp);
1488     return st;
1489 }
1490
1491 static int file_product(STANZA *s)
1492 {
1493     BIGNUM *a = NULL, *b = NULL, *product = NULL, *ret = NULL;
1494     BIGNUM *remainder = NULL, *zero = NULL;
1495     int st = 0;
1496
1497     if (!TEST_ptr(a = getBN(s, "A"))
1498             || !TEST_ptr(b = getBN(s, "B"))
1499             || !TEST_ptr(product = getBN(s, "Product"))
1500             || !TEST_ptr(ret = BN_new())
1501             || !TEST_ptr(remainder = BN_new())
1502             || !TEST_ptr(zero = BN_new()))
1503         goto err;
1504
1505     BN_zero(zero);
1506
1507     if (!TEST_true(BN_mul(ret, a, b, ctx))
1508             || !equalBN("A * B", product, ret)
1509             || !TEST_true(BN_div(ret, remainder, product, a, ctx))
1510             || !equalBN("Product / A", b, ret)
1511             || !equalBN("Product % A", zero, remainder)
1512             || !TEST_true(BN_div(ret, remainder, product, b, ctx))
1513             || !equalBN("Product / B", a, ret)
1514             || !equalBN("Product % B", zero, remainder))
1515         goto err;
1516
1517     st = 1;
1518  err:
1519     BN_free(a);
1520     BN_free(b);
1521     BN_free(product);
1522     BN_free(ret);
1523     BN_free(remainder);
1524     BN_free(zero);
1525     return st;
1526 }
1527
1528 static int file_quotient(STANZA *s)
1529 {
1530     BIGNUM *a = NULL, *b = NULL, *quotient = NULL, *remainder = NULL;
1531     BIGNUM *ret = NULL, *ret2 = NULL, *nnmod = NULL;
1532     BN_ULONG b_word, ret_word;
1533     int st = 0;
1534
1535     if (!TEST_ptr(a = getBN(s, "A"))
1536             || !TEST_ptr(b = getBN(s, "B"))
1537             || !TEST_ptr(quotient = getBN(s, "Quotient"))
1538             || !TEST_ptr(remainder = getBN(s, "Remainder"))
1539             || !TEST_ptr(ret = BN_new())
1540             || !TEST_ptr(ret2 = BN_new())
1541             || !TEST_ptr(nnmod = BN_new()))
1542         goto err;
1543
1544     if (!TEST_true(BN_div(ret, ret2, a, b, ctx))
1545             || !equalBN("A / B", quotient, ret)
1546             || !equalBN("A % B", remainder, ret2)
1547             || !TEST_true(BN_mul(ret, quotient, b, ctx))
1548             || !TEST_true(BN_add(ret, ret, remainder))
1549             || !equalBN("Quotient * B + Remainder", a, ret))
1550         goto err;
1551
1552     /*
1553      * Test with BN_mod_word() and BN_div_word() if the divisor is
1554      * small enough.
1555      */
1556     b_word = BN_get_word(b);
1557     if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) {
1558         BN_ULONG remainder_word = BN_get_word(remainder);
1559
1560         assert(remainder_word != (BN_ULONG)-1);
1561         if (!TEST_ptr(BN_copy(ret, a)))
1562             goto err;
1563         ret_word = BN_div_word(ret, b_word);
1564         if (ret_word != remainder_word) {
1565 #ifdef BN_DEC_FMT1
1566             TEST_error(
1567                     "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1,
1568                     ret_word, remainder_word);
1569 #else
1570             TEST_error("Got A %% B (word) mismatch");
1571 #endif
1572             goto err;
1573         }
1574         if (!equalBN ("A / B (word)", quotient, ret))
1575             goto err;
1576
1577         ret_word = BN_mod_word(a, b_word);
1578         if (ret_word != remainder_word) {
1579 #ifdef BN_DEC_FMT1
1580             TEST_error(
1581                     "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1 "",
1582                     ret_word, remainder_word);
1583 #else
1584             TEST_error("Got A %% B (word) mismatch");
1585 #endif
1586             goto err;
1587         }
1588     }
1589
1590     /* Test BN_nnmod. */
1591     if (!BN_is_negative(b)) {
1592         if (!TEST_true(BN_copy(nnmod, remainder))
1593                 || (BN_is_negative(nnmod)
1594                         && !TEST_true(BN_add(nnmod, nnmod, b)))
1595                 || !TEST_true(BN_nnmod(ret, a, b, ctx))
1596                 || !equalBN("A % B (non-negative)", nnmod, ret))
1597             goto err;
1598     }
1599
1600     st = 1;
1601  err:
1602     BN_free(a);
1603     BN_free(b);
1604     BN_free(quotient);
1605     BN_free(remainder);
1606     BN_free(ret);
1607     BN_free(ret2);
1608     BN_free(nnmod);
1609     return st;
1610 }
1611
1612 static int file_modmul(STANZA *s)
1613 {
1614     BIGNUM *a = NULL, *b = NULL, *m = NULL, *mod_mul = NULL, *ret = NULL;
1615     int st = 0;
1616
1617     if (!TEST_ptr(a = getBN(s, "A"))
1618             || !TEST_ptr(b = getBN(s, "B"))
1619             || !TEST_ptr(m = getBN(s, "M"))
1620             || !TEST_ptr(mod_mul = getBN(s, "ModMul"))
1621             || !TEST_ptr(ret = BN_new()))
1622         goto err;
1623
1624     if (!TEST_true(BN_mod_mul(ret, a, b, m, ctx))
1625             || !equalBN("A * B (mod M)", mod_mul, ret))
1626         goto err;
1627
1628     if (BN_is_odd(m)) {
1629         /* Reduce |a| and |b| and test the Montgomery version. */
1630         BN_MONT_CTX *mont = BN_MONT_CTX_new();
1631         BIGNUM *a_tmp = BN_new();
1632         BIGNUM *b_tmp = BN_new();
1633
1634         if (mont == NULL || a_tmp == NULL || b_tmp == NULL
1635                 || !TEST_true(BN_MONT_CTX_set(mont, m, ctx))
1636                 || !TEST_true(BN_nnmod(a_tmp, a, m, ctx))
1637                 || !TEST_true(BN_nnmod(b_tmp, b, m, ctx))
1638                 || !TEST_true(BN_to_montgomery(a_tmp, a_tmp, mont, ctx))
1639                 || !TEST_true(BN_to_montgomery(b_tmp, b_tmp, mont, ctx))
1640                 || !TEST_true(BN_mod_mul_montgomery(ret, a_tmp, b_tmp,
1641                                                     mont, ctx))
1642                 || !TEST_true(BN_from_montgomery(ret, ret, mont, ctx))
1643                 || !equalBN("A * B (mod M) (mont)", mod_mul, ret))
1644             st = 0;
1645         else
1646             st = 1;
1647         BN_MONT_CTX_free(mont);
1648         BN_free(a_tmp);
1649         BN_free(b_tmp);
1650         if (st == 0)
1651             goto err;
1652     }
1653
1654     st = 1;
1655  err:
1656     BN_free(a);
1657     BN_free(b);
1658     BN_free(m);
1659     BN_free(mod_mul);
1660     BN_free(ret);
1661     return st;
1662 }
1663
1664 static int file_modexp(STANZA *s)
1665 {
1666     BIGNUM *a = NULL, *e = NULL, *m = NULL, *mod_exp = NULL, *ret = NULL;
1667     BIGNUM *b = NULL, *c = NULL, *d = NULL;
1668     int st = 0;
1669
1670     if (!TEST_ptr(a = getBN(s, "A"))
1671             || !TEST_ptr(e = getBN(s, "E"))
1672             || !TEST_ptr(m = getBN(s, "M"))
1673             || !TEST_ptr(mod_exp = getBN(s, "ModExp"))
1674             || !TEST_ptr(ret = BN_new())
1675             || !TEST_ptr(d = BN_new()))
1676         goto err;
1677
1678     if (!TEST_true(BN_mod_exp(ret, a, e, m, ctx))
1679             || !equalBN("A ^ E (mod M)", mod_exp, ret))
1680         goto err;
1681
1682     if (BN_is_odd(m)) {
1683         if (!TEST_true(BN_mod_exp_mont(ret, a, e, m, ctx, NULL))
1684                 || !equalBN("A ^ E (mod M) (mont)", mod_exp, ret)
1685                 || !TEST_true(BN_mod_exp_mont_consttime(ret, a, e, m,
1686                                                         ctx, NULL))
1687                 || !equalBN("A ^ E (mod M) (mont const", mod_exp, ret))
1688             goto err;
1689     }
1690
1691     /* Regression test for carry propagation bug in sqr8x_reduction */
1692     BN_hex2bn(&a, "050505050505");
1693     BN_hex2bn(&b, "02");
1694     BN_hex2bn(&c,
1695         "4141414141414141414141274141414141414141414141414141414141414141"
1696         "4141414141414141414141414141414141414141414141414141414141414141"
1697         "4141414141414141414141800000000000000000000000000000000000000000"
1698         "0000000000000000000000000000000000000000000000000000000000000000"
1699         "0000000000000000000000000000000000000000000000000000000000000000"
1700         "0000000000000000000000000000000000000000000000000000000001");
1701     if (!TEST_true(BN_mod_exp(d, a, b, c, ctx))
1702         || !TEST_true(BN_mul(e, a, a, ctx))
1703         || !TEST_BN_eq(d, e))
1704         goto err;
1705
1706     st = 1;
1707  err:
1708     BN_free(a);
1709     BN_free(b);
1710     BN_free(c);
1711     BN_free(d);
1712     BN_free(e);
1713     BN_free(m);
1714     BN_free(mod_exp);
1715     BN_free(ret);
1716     return st;
1717 }
1718
1719 static int file_exp(STANZA *s)
1720 {
1721     BIGNUM *a = NULL, *e = NULL, *exp = NULL, *ret = NULL;
1722     int st = 0;
1723
1724     if (!TEST_ptr(a = getBN(s, "A"))
1725             || !TEST_ptr(e = getBN(s, "E"))
1726             || !TEST_ptr(exp = getBN(s, "Exp"))
1727             || !TEST_ptr(ret = BN_new()))
1728         goto err;
1729
1730     if (!TEST_true(BN_exp(ret, a, e, ctx))
1731             || !equalBN("A ^ E", exp, ret))
1732         goto err;
1733
1734     st = 1;
1735  err:
1736     BN_free(a);
1737     BN_free(e);
1738     BN_free(exp);
1739     BN_free(ret);
1740     return st;
1741 }
1742
1743 static int file_modsqrt(STANZA *s)
1744 {
1745     BIGNUM *a = NULL, *p = NULL, *mod_sqrt = NULL, *ret = NULL, *ret2 = NULL;
1746     int st = 0;
1747
1748     if (!TEST_ptr(a = getBN(s, "A"))
1749             || !TEST_ptr(p = getBN(s, "P"))
1750             || !TEST_ptr(mod_sqrt = getBN(s, "ModSqrt"))
1751             || !TEST_ptr(ret = BN_new())
1752             || !TEST_ptr(ret2 = BN_new()))
1753         goto err;
1754
1755     if (BN_is_negative(mod_sqrt)) {
1756         /* A negative testcase */
1757         if (!TEST_ptr_null(BN_mod_sqrt(ret, a, p, ctx)))
1758             goto err;
1759
1760         st = 1;
1761         goto err;
1762     }
1763
1764     /* There are two possible answers. */
1765     if (!TEST_ptr(BN_mod_sqrt(ret, a, p, ctx))
1766             || !TEST_true(BN_sub(ret2, p, ret)))
1767         goto err;
1768
1769     /* The first condition should NOT be a test. */
1770     if (BN_cmp(ret2, mod_sqrt) != 0
1771             && !equalBN("sqrt(A) (mod P)", mod_sqrt, ret))
1772         goto err;
1773
1774     st = 1;
1775  err:
1776     BN_free(a);
1777     BN_free(p);
1778     BN_free(mod_sqrt);
1779     BN_free(ret);
1780     BN_free(ret2);
1781     return st;
1782 }
1783
1784 static int file_gcd(STANZA *s)
1785 {
1786     BIGNUM *a = NULL, *b = NULL, *gcd = NULL, *ret = NULL;
1787     int st = 0;
1788
1789     if (!TEST_ptr(a = getBN(s, "A"))
1790             || !TEST_ptr(b = getBN(s, "B"))
1791             || !TEST_ptr(gcd = getBN(s, "GCD"))
1792             || !TEST_ptr(ret = BN_new()))
1793         goto err;
1794
1795     if (!TEST_true(BN_gcd(ret, a, b, ctx))
1796             || !equalBN("gcd(A,B)", gcd, ret))
1797         goto err;
1798
1799     st = 1;
1800  err:
1801     BN_free(a);
1802     BN_free(b);
1803     BN_free(gcd);
1804     BN_free(ret);
1805     return st;
1806 }
1807
1808 static int test_bn2padded(void)
1809 {
1810     uint8_t zeros[256], out[256], reference[128];
1811     size_t bytes;
1812     BIGNUM *n;
1813     int st = 0;
1814
1815     /* Test edge case at 0. */
1816     if (!TEST_ptr((n = BN_new())))
1817         goto err;
1818     if (!TEST_int_eq(BN_bn2binpad(n, NULL, 0), 0))
1819         goto err;
1820     memset(out, -1, sizeof(out));
1821     if (!TEST_int_eq(BN_bn2binpad(n, out, sizeof(out)), sizeof(out)))
1822         goto err;
1823     memset(zeros, 0, sizeof(zeros));
1824     if (!TEST_mem_eq(zeros, sizeof(zeros), out, sizeof(out)))
1825         goto err;
1826
1827     /* Test a random numbers at various byte lengths. */
1828     for (bytes = 128 - 7; bytes <= 128; bytes++) {
1829 # define TOP_BIT_ON 0
1830 # define BOTTOM_BIT_NOTOUCH 0
1831         if (!TEST_true(BN_rand(n, bytes * 8, TOP_BIT_ON, BOTTOM_BIT_NOTOUCH)))
1832             goto err;
1833         if (!TEST_int_eq(BN_num_bytes(n), bytes)
1834                 || !TEST_int_eq(BN_bn2bin(n, reference), bytes))
1835             goto err;
1836         /* Empty buffer should fail. */
1837         if (!TEST_int_eq(BN_bn2binpad(n, NULL, 0), -1))
1838             goto err;
1839         /* One byte short should fail. */
1840         if (!TEST_int_eq(BN_bn2binpad(n, out, bytes - 1), -1))
1841             goto err;
1842         /* Exactly right size should encode. */
1843         if (!TEST_int_eq(BN_bn2binpad(n, out, bytes), bytes)
1844                 || !TEST_mem_eq(out, bytes, reference, bytes))
1845             goto err;
1846         /* Pad up one byte extra. */
1847         if (!TEST_int_eq(BN_bn2binpad(n, out, bytes + 1), bytes + 1)
1848                 || !TEST_mem_eq(out + 1, bytes, reference, bytes)
1849                 || !TEST_mem_eq(out, 1, zeros, 1))
1850             goto err;
1851         /* Pad up to 256. */
1852         if (!TEST_int_eq(BN_bn2binpad(n, out, sizeof(out)), sizeof(out))
1853                 || !TEST_mem_eq(out + sizeof(out) - bytes, bytes,
1854                                 reference, bytes)
1855                 || !TEST_mem_eq(out, sizeof(out) - bytes,
1856                                 zeros, sizeof(out) - bytes))
1857             goto err;
1858     }
1859
1860     st = 1;
1861  err:
1862     BN_free(n);
1863     return st;
1864 }
1865
1866 static const MPITEST kSignedTests_BE[] = {
1867     {"-1", "\xff", 1},
1868     {"0", "", 0},
1869     {"1", "\x01", 1},
1870     /*
1871      * The above cover the basics, now let's go for possible bignum
1872      * chunk edges and other word edges (for a broad definition of
1873      * "word", i.e. 1 byte included).
1874      */
1875     /* 1 byte edge */
1876     {"127", "\x7f", 1},
1877     {"-127", "\x81", 1},
1878     {"128", "\x00\x80", 2},
1879     {"-128", "\x80", 1},
1880     {"129", "\x00\x81", 2},
1881     {"-129", "\xff\x7f", 2},
1882     {"255", "\x00\xff", 2},
1883     {"-255", "\xff\x01", 2},
1884     {"256", "\x01\x00", 2},
1885     {"-256", "\xff\x00", 2},
1886     /* 2 byte edge */
1887     {"32767", "\x7f\xff", 2},
1888     {"-32767", "\x80\x01", 2},
1889     {"32768", "\x00\x80\x00", 3},
1890     {"-32768", "\x80\x00", 2},
1891     {"32769", "\x00\x80\x01", 3},
1892     {"-32769", "\xff\x7f\xff", 3},
1893     {"65535", "\x00\xff\xff", 3},
1894     {"-65535", "\xff\x00\x01", 3},
1895     {"65536", "\x01\x00\x00", 3},
1896     {"-65536", "\xff\x00\x00", 3},
1897     /* 4 byte edge */
1898     {"2147483647", "\x7f\xff\xff\xff", 4},
1899     {"-2147483647", "\x80\x00\x00\x01", 4},
1900     {"2147483648", "\x00\x80\x00\x00\x00", 5},
1901     {"-2147483648", "\x80\x00\x00\x00", 4},
1902     {"2147483649", "\x00\x80\x00\x00\x01", 5},
1903     {"-2147483649", "\xff\x7f\xff\xff\xff", 5},
1904     {"4294967295", "\x00\xff\xff\xff\xff", 5},
1905     {"-4294967295", "\xff\x00\x00\x00\x01", 5},
1906     {"4294967296", "\x01\x00\x00\x00\x00", 5},
1907     {"-4294967296", "\xff\x00\x00\x00\x00", 5},
1908     /* 8 byte edge */
1909     {"9223372036854775807", "\x7f\xff\xff\xff\xff\xff\xff\xff", 8},
1910     {"-9223372036854775807", "\x80\x00\x00\x00\x00\x00\x00\x01", 8},
1911     {"9223372036854775808", "\x00\x80\x00\x00\x00\x00\x00\x00\x00", 9},
1912     {"-9223372036854775808", "\x80\x00\x00\x00\x00\x00\x00\x00", 8},
1913     {"9223372036854775809", "\x00\x80\x00\x00\x00\x00\x00\x00\x01", 9},
1914     {"-9223372036854775809", "\xff\x7f\xff\xff\xff\xff\xff\xff\xff", 9},
1915     {"18446744073709551615", "\x00\xff\xff\xff\xff\xff\xff\xff\xff", 9},
1916     {"-18446744073709551615", "\xff\x00\x00\x00\x00\x00\x00\x00\x01", 9},
1917     {"18446744073709551616", "\x01\x00\x00\x00\x00\x00\x00\x00\x00", 9},
1918     {"-18446744073709551616", "\xff\x00\x00\x00\x00\x00\x00\x00\x00", 9},
1919 };
1920
1921 static int copy_reversed(uint8_t *dst, uint8_t *src, size_t len)
1922 {
1923     for (dst += len - 1; len > 0; src++, dst--, len--)
1924         *dst = *src;
1925     return 1;
1926 }
1927
1928 static int test_bn2signed(int i)
1929 {
1930     uint8_t scratch[10], reversed[10];
1931     const MPITEST *test = &kSignedTests_BE[i];
1932     BIGNUM *bn = NULL, *bn2 = NULL;
1933     int st = 0;
1934
1935     if (!TEST_ptr(bn = BN_new())
1936         || !TEST_true(BN_asc2bn(&bn, test->base10)))
1937         goto err;
1938
1939     /*
1940      * Check BN_signed_bn2bin() / BN_signed_bin2bn()
1941      * The interesting stuff happens in the last bytes of the buffers,
1942      * the beginning is just padding (i.e. sign extension).
1943      */
1944     i = sizeof(scratch) - test->mpi_len;
1945     if (!TEST_int_eq(BN_signed_bn2bin(bn, scratch, sizeof(scratch)),
1946                      sizeof(scratch))
1947         || !TEST_true(copy_reversed(reversed, scratch, sizeof(scratch)))
1948         || !TEST_mem_eq(test->mpi, test->mpi_len, scratch + i, test->mpi_len))
1949         goto err;
1950
1951     if (!TEST_ptr(bn2 = BN_signed_bin2bn(scratch, sizeof(scratch), NULL))
1952         || !TEST_BN_eq(bn, bn2))
1953         goto err;
1954
1955     BN_free(bn2);
1956     bn2 = NULL;
1957
1958     /* Check that a parse of the reversed buffer works too */
1959     if (!TEST_ptr(bn2 = BN_signed_lebin2bn(reversed, sizeof(reversed), NULL))
1960         || !TEST_BN_eq(bn, bn2))
1961         goto err;
1962
1963     BN_free(bn2);
1964     bn2 = NULL;
1965
1966     /*
1967      * Check BN_signed_bn2lebin() / BN_signed_lebin2bn()
1968      * The interesting stuff happens in the first bytes of the buffers,
1969      * the end is just padding (i.e. sign extension).
1970      */
1971     i = sizeof(reversed) - test->mpi_len;
1972     if (!TEST_int_eq(BN_signed_bn2lebin(bn, scratch, sizeof(scratch)),
1973                      sizeof(scratch))
1974         || !TEST_true(copy_reversed(reversed, scratch, sizeof(scratch)))
1975         || !TEST_mem_eq(test->mpi, test->mpi_len, reversed + i, test->mpi_len))
1976         goto err;
1977
1978     if (!TEST_ptr(bn2 = BN_signed_lebin2bn(scratch, sizeof(scratch), NULL))
1979         || !TEST_BN_eq(bn, bn2))
1980         goto err;
1981
1982     BN_free(bn2);
1983     bn2 = NULL;
1984
1985     /* Check that a parse of the reversed buffer works too */
1986     if (!TEST_ptr(bn2 = BN_signed_bin2bn(reversed, sizeof(reversed), NULL))
1987         || !TEST_BN_eq(bn, bn2))
1988         goto err;
1989
1990     st = 1;
1991  err:
1992     BN_free(bn2);
1993     BN_free(bn);
1994     return st;
1995 }
1996
1997 static int test_dec2bn(void)
1998 {
1999     BIGNUM *bn = NULL;
2000     int st = 0;
2001
2002     if (!TEST_int_eq(parsedecBN(&bn, "0"), 1)
2003             || !TEST_BN_eq_word(bn, 0)
2004             || !TEST_BN_eq_zero(bn)
2005             || !TEST_BN_le_zero(bn)
2006             || !TEST_BN_ge_zero(bn)
2007             || !TEST_BN_even(bn))
2008         goto err;
2009     BN_free(bn);
2010     bn = NULL;
2011
2012     if (!TEST_int_eq(parsedecBN(&bn, "256"), 3)
2013             || !TEST_BN_eq_word(bn, 256)
2014             || !TEST_BN_ge_zero(bn)
2015             || !TEST_BN_gt_zero(bn)
2016             || !TEST_BN_ne_zero(bn)
2017             || !TEST_BN_even(bn))
2018         goto err;
2019     BN_free(bn);
2020     bn = NULL;
2021
2022     if (!TEST_int_eq(parsedecBN(&bn, "-42"), 3)
2023             || !TEST_BN_abs_eq_word(bn, 42)
2024             || !TEST_BN_lt_zero(bn)
2025             || !TEST_BN_le_zero(bn)
2026             || !TEST_BN_ne_zero(bn)
2027             || !TEST_BN_even(bn))
2028         goto err;
2029     BN_free(bn);
2030     bn = NULL;
2031
2032     if (!TEST_int_eq(parsedecBN(&bn, "1"), 1)
2033             || !TEST_BN_eq_word(bn, 1)
2034             || !TEST_BN_ne_zero(bn)
2035             || !TEST_BN_gt_zero(bn)
2036             || !TEST_BN_ge_zero(bn)
2037             || !TEST_BN_eq_one(bn)
2038             || !TEST_BN_odd(bn))
2039         goto err;
2040     BN_free(bn);
2041     bn = NULL;
2042
2043     if (!TEST_int_eq(parsedecBN(&bn, "-0"), 2)
2044             || !TEST_BN_eq_zero(bn)
2045             || !TEST_BN_ge_zero(bn)
2046             || !TEST_BN_le_zero(bn)
2047             || !TEST_BN_even(bn))
2048         goto err;
2049     BN_free(bn);
2050     bn = NULL;
2051
2052     if (!TEST_int_eq(parsedecBN(&bn, "42trailing garbage is ignored"), 2)
2053             || !TEST_BN_abs_eq_word(bn, 42)
2054             || !TEST_BN_ge_zero(bn)
2055             || !TEST_BN_gt_zero(bn)
2056             || !TEST_BN_ne_zero(bn)
2057             || !TEST_BN_even(bn))
2058         goto err;
2059
2060     st = 1;
2061  err:
2062     BN_free(bn);
2063     return st;
2064 }
2065
2066 static int test_hex2bn(void)
2067 {
2068     BIGNUM *bn = NULL;
2069     int st = 0;
2070
2071     if (!TEST_int_eq(parseBN(&bn, "0"), 1)
2072             || !TEST_BN_eq_zero(bn)
2073             || !TEST_BN_ge_zero(bn)
2074             || !TEST_BN_even(bn))
2075         goto err;
2076     BN_free(bn);
2077     bn = NULL;
2078
2079     if (!TEST_int_eq(parseBN(&bn, "256"), 3)
2080             || !TEST_BN_eq_word(bn, 0x256)
2081             || !TEST_BN_ge_zero(bn)
2082             || !TEST_BN_gt_zero(bn)
2083             || !TEST_BN_ne_zero(bn)
2084             || !TEST_BN_even(bn))
2085         goto err;
2086     BN_free(bn);
2087     bn = NULL;
2088
2089     if (!TEST_int_eq(parseBN(&bn, "-42"), 3)
2090             || !TEST_BN_abs_eq_word(bn, 0x42)
2091             || !TEST_BN_lt_zero(bn)
2092             || !TEST_BN_le_zero(bn)
2093             || !TEST_BN_ne_zero(bn)
2094             || !TEST_BN_even(bn))
2095         goto err;
2096     BN_free(bn);
2097     bn = NULL;
2098
2099     if (!TEST_int_eq(parseBN(&bn, "cb"), 2)
2100             || !TEST_BN_eq_word(bn, 0xCB)
2101             || !TEST_BN_ge_zero(bn)
2102             || !TEST_BN_gt_zero(bn)
2103             || !TEST_BN_ne_zero(bn)
2104             || !TEST_BN_odd(bn))
2105         goto err;
2106     BN_free(bn);
2107     bn = NULL;
2108
2109     if (!TEST_int_eq(parseBN(&bn, "-0"), 2)
2110             || !TEST_BN_eq_zero(bn)
2111             || !TEST_BN_ge_zero(bn)
2112             || !TEST_BN_le_zero(bn)
2113             || !TEST_BN_even(bn))
2114         goto err;
2115     BN_free(bn);
2116     bn = NULL;
2117
2118     if (!TEST_int_eq(parseBN(&bn, "abctrailing garbage is ignored"), 3)
2119             || !TEST_BN_eq_word(bn, 0xabc)
2120             || !TEST_BN_ge_zero(bn)
2121             || !TEST_BN_gt_zero(bn)
2122             || !TEST_BN_ne_zero(bn)
2123             || !TEST_BN_even(bn))
2124         goto err;
2125     st = 1;
2126
2127  err:
2128     BN_free(bn);
2129     return st;
2130 }
2131
2132 static int test_asc2bn(void)
2133 {
2134     BIGNUM *bn = NULL;
2135     int st = 0;
2136
2137     if (!TEST_ptr(bn = BN_new()))
2138         goto err;
2139
2140     if (!TEST_true(BN_asc2bn(&bn, "0"))
2141             || !TEST_BN_eq_zero(bn)
2142             || !TEST_BN_ge_zero(bn))
2143         goto err;
2144
2145     if (!TEST_true(BN_asc2bn(&bn, "256"))
2146             || !TEST_BN_eq_word(bn, 256)
2147             || !TEST_BN_ge_zero(bn))
2148         goto err;
2149
2150     if (!TEST_true(BN_asc2bn(&bn, "-42"))
2151             || !TEST_BN_abs_eq_word(bn, 42)
2152             || !TEST_BN_lt_zero(bn))
2153         goto err;
2154
2155     if (!TEST_true(BN_asc2bn(&bn, "0x1234"))
2156             || !TEST_BN_eq_word(bn, 0x1234)
2157             || !TEST_BN_ge_zero(bn))
2158         goto err;
2159
2160     if (!TEST_true(BN_asc2bn(&bn, "0X1234"))
2161             || !TEST_BN_eq_word(bn, 0x1234)
2162             || !TEST_BN_ge_zero(bn))
2163         goto err;
2164
2165     if (!TEST_true(BN_asc2bn(&bn, "-0xabcd"))
2166             || !TEST_BN_abs_eq_word(bn, 0xabcd)
2167             || !TEST_BN_lt_zero(bn))
2168         goto err;
2169
2170     if (!TEST_true(BN_asc2bn(&bn, "-0"))
2171             || !TEST_BN_eq_zero(bn)
2172             || !TEST_BN_ge_zero(bn))
2173         goto err;
2174
2175     if (!TEST_true(BN_asc2bn(&bn, "123trailing garbage is ignored"))
2176             || !TEST_BN_eq_word(bn, 123)
2177             || !TEST_BN_ge_zero(bn))
2178         goto err;
2179
2180     st = 1;
2181  err:
2182     BN_free(bn);
2183     return st;
2184 }
2185
2186 static const MPITEST kMPITests[] = {
2187     {"0", "\x00\x00\x00\x00", 4},
2188     {"1", "\x00\x00\x00\x01\x01", 5},
2189     {"-1", "\x00\x00\x00\x01\x81", 5},
2190     {"128", "\x00\x00\x00\x02\x00\x80", 6},
2191     {"256", "\x00\x00\x00\x02\x01\x00", 6},
2192     {"-256", "\x00\x00\x00\x02\x81\x00", 6},
2193 };
2194
2195 static int test_mpi(int i)
2196 {
2197     uint8_t scratch[8];
2198     const MPITEST *test = &kMPITests[i];
2199     size_t mpi_len, mpi_len2;
2200     BIGNUM *bn = NULL;
2201     BIGNUM *bn2 = NULL;
2202     int st = 0;
2203
2204     if (!TEST_ptr(bn = BN_new())
2205             || !TEST_true(BN_asc2bn(&bn, test->base10)))
2206         goto err;
2207     mpi_len = BN_bn2mpi(bn, NULL);
2208     if (!TEST_size_t_le(mpi_len, sizeof(scratch)))
2209         goto err;
2210
2211     if (!TEST_size_t_eq(mpi_len2 = BN_bn2mpi(bn, scratch), mpi_len)
2212             || !TEST_mem_eq(test->mpi, test->mpi_len, scratch, mpi_len))
2213         goto err;
2214
2215     if (!TEST_ptr(bn2 = BN_mpi2bn(scratch, mpi_len, NULL)))
2216         goto err;
2217
2218     if (!TEST_BN_eq(bn, bn2)) {
2219         BN_free(bn2);
2220         goto err;
2221     }
2222     BN_free(bn2);
2223
2224     st = 1;
2225  err:
2226     BN_free(bn);
2227     return st;
2228 }
2229
2230 static int test_bin2zero(void)
2231 {
2232     unsigned char input[] = { 0 };
2233     BIGNUM *zbn = NULL;
2234     int ret = 0;
2235
2236     if (!TEST_ptr(zbn = BN_new()))
2237         goto err;
2238
2239 #define zerotest(fn)                           \
2240     if (!TEST_ptr(fn(input, 1, zbn))    \
2241         || !TEST_true(BN_is_zero(zbn))   \
2242         || !TEST_ptr(fn(input, 0, zbn)) \
2243         || !TEST_true(BN_is_zero(zbn))   \
2244         || !TEST_ptr(fn(NULL, 0, zbn))  \
2245         || !TEST_true(BN_is_zero(zbn)))  \
2246         goto err
2247
2248     zerotest(BN_bin2bn);
2249     zerotest(BN_signed_bin2bn);
2250     zerotest(BN_lebin2bn);
2251     zerotest(BN_signed_lebin2bn);
2252 #undef zerotest
2253
2254     ret = 1;
2255  err:
2256     BN_free(zbn);
2257     return ret;
2258 }
2259
2260 static int test_bin2bn_lengths(void)
2261 {
2262     unsigned char input[] = { 1, 2 };
2263     BIGNUM *bn_be = NULL, *bn_expected_be = NULL;
2264     BIGNUM *bn_le = NULL, *bn_expected_le = NULL;
2265     int ret = 0;
2266
2267     if (!TEST_ptr(bn_be = BN_new())
2268         || !TEST_ptr(bn_expected_be = BN_new())
2269         || !TEST_true(BN_set_word(bn_expected_be, 0x102))
2270         || !TEST_ptr(bn_le = BN_new())
2271         || !TEST_ptr(bn_expected_le = BN_new())
2272         || !TEST_true(BN_set_word(bn_expected_le, 0x201)))
2273         goto err;
2274
2275 #define lengthtest(fn, e)                                       \
2276     if (!TEST_ptr_null(fn(input, -1, bn_##e))                   \
2277         || !TEST_ptr(fn(input, 0, bn_##e))                      \
2278         || !TEST_true(BN_is_zero(bn_##e))                       \
2279         || !TEST_ptr(fn(input, 2, bn_##e))                      \
2280         || !TEST_int_eq(BN_cmp(bn_##e, bn_expected_##e), 0))    \
2281         goto err
2282
2283     lengthtest(BN_bin2bn, be);
2284     lengthtest(BN_signed_bin2bn, be);
2285     lengthtest(BN_lebin2bn, le);
2286     lengthtest(BN_signed_lebin2bn, le);
2287 #undef lengthtest
2288
2289     ret = 1;
2290  err:
2291     BN_free(bn_be);
2292     BN_free(bn_expected_be);
2293     BN_free(bn_le);
2294     BN_free(bn_expected_le);
2295     return ret;
2296 }
2297
2298 static int test_rand(void)
2299 {
2300     BIGNUM *bn = NULL;
2301     int st = 0;
2302
2303     if (!TEST_ptr(bn = BN_new()))
2304         return 0;
2305
2306     /* Test BN_rand for degenerate cases with |top| and |bottom| parameters. */
2307     if (!TEST_false(BN_rand(bn, 0, 0 /* top */ , 0 /* bottom */ ))
2308             || !TEST_false(BN_rand(bn, 0, 1 /* top */ , 1 /* bottom */ ))
2309             || !TEST_true(BN_rand(bn, 1, 0 /* top */ , 0 /* bottom */ ))
2310             || !TEST_BN_eq_one(bn)
2311             || !TEST_false(BN_rand(bn, 1, 1 /* top */ , 0 /* bottom */ ))
2312             || !TEST_true(BN_rand(bn, 1, -1 /* top */ , 1 /* bottom */ ))
2313             || !TEST_BN_eq_one(bn)
2314             || !TEST_true(BN_rand(bn, 2, 1 /* top */ , 0 /* bottom */ ))
2315             || !TEST_BN_eq_word(bn, 3))
2316         goto err;
2317
2318     st = 1;
2319  err:
2320     BN_free(bn);
2321     return st;
2322 }
2323
2324 /*
2325  * Run some statistical tests to provide a degree confidence that the
2326  * BN_rand_range() function works as expected.  The test cases and
2327  * critical values are generated by the bn_rand_range script.
2328  *
2329  * Each individual test is a Chi^2 goodness of fit for a specified number
2330  * of samples and range.  The samples are assumed to be independent and
2331  * that they are from a discrete uniform distribution.
2332  *
2333  * Some of these individual tests are expected to fail, the success/failure
2334  * of each is an independent Bernoulli trial.  The number of such successes
2335  * will form a binomial distribution.  The count of the successes is compared
2336  * against a precomputed critical value to determine the overall outcome.
2337  */
2338 struct rand_range_case {
2339     unsigned int range;
2340     unsigned int iterations;
2341     double critical;
2342 };
2343
2344 #include "bn_rand_range.h"
2345
2346 static int test_rand_range_single(size_t n)
2347 {
2348     const unsigned int range = rand_range_cases[n].range;
2349     const unsigned int iterations = rand_range_cases[n].iterations;
2350     const double critical = rand_range_cases[n].critical;
2351     const double expected = iterations / (double)range;
2352     double sum = 0;
2353     BIGNUM *rng = NULL, *val = NULL;
2354     size_t *counts;
2355     unsigned int i, v;
2356     int res = 0;
2357
2358     if (!TEST_ptr(counts = OPENSSL_zalloc(sizeof(*counts) * range))
2359         || !TEST_ptr(rng = BN_new())
2360         || !TEST_ptr(val = BN_new())
2361         || !TEST_true(BN_set_word(rng, range)))
2362         goto err;
2363     for (i = 0; i < iterations; i++) {
2364         if (!TEST_true(BN_rand_range(val, rng))
2365             || !TEST_uint_lt(v = (unsigned int)BN_get_word(val), range))
2366             goto err;
2367         counts[v]++;
2368     }
2369
2370     for (i = 0; i < range; i++) {
2371         const double delta = counts[i] - expected;
2372         sum += delta * delta;
2373     }
2374     sum /= expected;
2375
2376     if (sum > critical) {
2377         TEST_info("Chi^2 test negative %.4f > %4.f", sum, critical);
2378         TEST_note("test case %zu  range %u  iterations %u", n + 1, range,
2379                   iterations);
2380         goto err;
2381     }
2382
2383     res = 1;
2384 err:
2385     BN_free(rng);
2386     BN_free(val);
2387     OPENSSL_free(counts);
2388     return res;
2389 }
2390
2391 static int test_rand_range(void)
2392 {
2393     int n_success = 0;
2394     size_t i;
2395
2396     for (i = 0; i < OSSL_NELEM(rand_range_cases); i++)
2397         n_success += test_rand_range_single(i);
2398     if (TEST_int_ge(n_success, binomial_critical))
2399         return 1;
2400     TEST_note("This test is expected to fail by chance 0.01%% of the time.");
2401     return 0;
2402 }
2403
2404 static int test_negzero(void)
2405 {
2406     BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL;
2407     BIGNUM *numerator = NULL, *denominator = NULL;
2408     int consttime, st = 0;
2409
2410     if (!TEST_ptr(a = BN_new())
2411             || !TEST_ptr(b = BN_new())
2412             || !TEST_ptr(c = BN_new())
2413             || !TEST_ptr(d = BN_new()))
2414         goto err;
2415
2416     /* Test that BN_mul never gives negative zero. */
2417     if (!TEST_true(BN_set_word(a, 1)))
2418         goto err;
2419     BN_set_negative(a, 1);
2420     BN_zero(b);
2421     if (!TEST_true(BN_mul(c, a, b, ctx)))
2422         goto err;
2423     if (!TEST_BN_eq_zero(c)
2424             || !TEST_BN_ge_zero(c))
2425         goto err;
2426
2427     for (consttime = 0; consttime < 2; consttime++) {
2428         if (!TEST_ptr(numerator = BN_new())
2429                 || !TEST_ptr(denominator = BN_new()))
2430             goto err;
2431         if (consttime) {
2432             BN_set_flags(numerator, BN_FLG_CONSTTIME);
2433             BN_set_flags(denominator, BN_FLG_CONSTTIME);
2434         }
2435         /* Test that BN_div never gives negative zero in the quotient. */
2436         if (!TEST_true(BN_set_word(numerator, 1))
2437                 || !TEST_true(BN_set_word(denominator, 2)))
2438             goto err;
2439         BN_set_negative(numerator, 1);
2440         if (!TEST_true(BN_div(a, b, numerator, denominator, ctx))
2441                 || !TEST_BN_eq_zero(a)
2442                 || !TEST_BN_ge_zero(a))
2443             goto err;
2444
2445         /* Test that BN_div never gives negative zero in the remainder. */
2446         if (!TEST_true(BN_set_word(denominator, 1))
2447                 || !TEST_true(BN_div(a, b, numerator, denominator, ctx))
2448                 || !TEST_BN_eq_zero(b)
2449                 || !TEST_BN_ge_zero(b))
2450             goto err;
2451         BN_free(numerator);
2452         BN_free(denominator);
2453         numerator = denominator = NULL;
2454     }
2455
2456     /* Test that BN_set_negative will not produce a negative zero. */
2457     BN_zero(a);
2458     BN_set_negative(a, 1);
2459     if (BN_is_negative(a))
2460         goto err;
2461     st = 1;
2462
2463  err:
2464     BN_free(a);
2465     BN_free(b);
2466     BN_free(c);
2467     BN_free(d);
2468     BN_free(numerator);
2469     BN_free(denominator);
2470     return st;
2471 }
2472
2473 static int test_badmod(void)
2474 {
2475     BIGNUM *a = NULL, *b = NULL, *zero = NULL;
2476     BN_MONT_CTX *mont = NULL;
2477     int st = 0;
2478
2479     if (!TEST_ptr(a = BN_new())
2480             || !TEST_ptr(b = BN_new())
2481             || !TEST_ptr(zero = BN_new())
2482             || !TEST_ptr(mont = BN_MONT_CTX_new()))
2483         goto err;
2484     BN_zero(zero);
2485
2486     if (!TEST_false(BN_div(a, b, BN_value_one(), zero, ctx)))
2487         goto err;
2488     ERR_clear_error();
2489
2490     if (!TEST_false(BN_mod_mul(a, BN_value_one(), BN_value_one(), zero, ctx)))
2491         goto err;
2492     ERR_clear_error();
2493
2494     if (!TEST_false(BN_mod_exp(a, BN_value_one(), BN_value_one(), zero, ctx)))
2495         goto err;
2496     ERR_clear_error();
2497
2498     if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(),
2499                                     zero, ctx, NULL)))
2500         goto err;
2501     ERR_clear_error();
2502
2503     if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
2504                                               zero, ctx, NULL)))
2505         goto err;
2506     ERR_clear_error();
2507
2508     if (!TEST_false(BN_MONT_CTX_set(mont, zero, ctx)))
2509         goto err;
2510     ERR_clear_error();
2511
2512     /* Some operations also may not be used with an even modulus. */
2513     if (!TEST_true(BN_set_word(b, 16)))
2514         goto err;
2515
2516     if (!TEST_false(BN_MONT_CTX_set(mont, b, ctx)))
2517         goto err;
2518     ERR_clear_error();
2519
2520     if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(),
2521                                     b, ctx, NULL)))
2522         goto err;
2523     ERR_clear_error();
2524
2525     if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(),
2526                                               b, ctx, NULL)))
2527         goto err;
2528     ERR_clear_error();
2529
2530     st = 1;
2531  err:
2532     BN_free(a);
2533     BN_free(b);
2534     BN_free(zero);
2535     BN_MONT_CTX_free(mont);
2536     return st;
2537 }
2538
2539 static int test_expmodzero(void)
2540 {
2541     BIGNUM *a = NULL, *r = NULL, *zero = NULL;
2542     int st = 0;
2543
2544     if (!TEST_ptr(zero = BN_new())
2545             || !TEST_ptr(a = BN_new())
2546             || !TEST_ptr(r = BN_new()))
2547         goto err;
2548     BN_zero(zero);
2549
2550     if (!TEST_true(BN_mod_exp(r, a, zero, BN_value_one(), NULL))
2551             || !TEST_BN_eq_zero(r)
2552             || !TEST_true(BN_mod_exp_mont(r, a, zero, BN_value_one(),
2553                                           NULL, NULL))
2554             || !TEST_BN_eq_zero(r)
2555             || !TEST_true(BN_mod_exp_mont_consttime(r, a, zero,
2556                                                     BN_value_one(),
2557                                                     NULL, NULL))
2558             || !TEST_BN_eq_zero(r)
2559             || !TEST_true(BN_mod_exp_mont_word(r, 42, zero,
2560                                                BN_value_one(), NULL, NULL))
2561             || !TEST_BN_eq_zero(r))
2562         goto err;
2563
2564     st = 1;
2565  err:
2566     BN_free(zero);
2567     BN_free(a);
2568     BN_free(r);
2569     return st;
2570 }
2571
2572 static int test_expmodone(void)
2573 {
2574     int ret = 0, i;
2575     BIGNUM *r = BN_new();
2576     BIGNUM *a = BN_new();
2577     BIGNUM *p = BN_new();
2578     BIGNUM *m = BN_new();
2579
2580     if (!TEST_ptr(r)
2581             || !TEST_ptr(a)
2582             || !TEST_ptr(p)
2583             || !TEST_ptr(p)
2584             || !TEST_ptr(m)
2585             || !TEST_true(BN_set_word(a, 1))
2586             || !TEST_true(BN_set_word(p, 0))
2587             || !TEST_true(BN_set_word(m, 1)))
2588         goto err;
2589
2590     /* Calculate r = 1 ^ 0 mod 1, and check the result is always 0 */
2591     for (i = 0; i < 2; i++) {
2592         if (!TEST_true(BN_mod_exp(r, a, p, m, NULL))
2593                 || !TEST_BN_eq_zero(r)
2594                 || !TEST_true(BN_mod_exp_mont(r, a, p, m, NULL, NULL))
2595                 || !TEST_BN_eq_zero(r)
2596                 || !TEST_true(BN_mod_exp_mont_consttime(r, a, p, m, NULL, NULL))
2597                 || !TEST_BN_eq_zero(r)
2598                 || !TEST_true(BN_mod_exp_mont_word(r, 1, p, m, NULL, NULL))
2599                 || !TEST_BN_eq_zero(r)
2600                 || !TEST_true(BN_mod_exp_simple(r, a, p, m, NULL))
2601                 || !TEST_BN_eq_zero(r)
2602                 || !TEST_true(BN_mod_exp_recp(r, a, p, m, NULL))
2603                 || !TEST_BN_eq_zero(r))
2604             goto err;
2605         /* Repeat for r = 1 ^ 0 mod -1 */
2606         if (i == 0)
2607             BN_set_negative(m, 1);
2608     }
2609
2610     ret = 1;
2611  err:
2612     BN_free(r);
2613     BN_free(a);
2614     BN_free(p);
2615     BN_free(m);
2616     return ret;
2617 }
2618
2619 static int test_smallprime(int kBits)
2620 {
2621     BIGNUM *r;
2622     int st = 0;
2623
2624     if (!TEST_ptr(r = BN_new()))
2625         goto err;
2626
2627     if (kBits <= 1) {
2628         if (!TEST_false(BN_generate_prime_ex(r, kBits, 0,
2629                                              NULL, NULL, NULL)))
2630             goto err;
2631     } else {
2632         if (!TEST_true(BN_generate_prime_ex(r, kBits, 0,
2633                                             NULL, NULL, NULL))
2634                 || !TEST_int_eq(BN_num_bits(r), kBits))
2635             goto err;
2636     }
2637
2638     st = 1;
2639  err:
2640     BN_free(r);
2641     return st;
2642 }
2643
2644 static int test_smallsafeprime(int kBits)
2645 {
2646     BIGNUM *r;
2647     int st = 0;
2648
2649     if (!TEST_ptr(r = BN_new()))
2650         goto err;
2651
2652     if (kBits <= 5 && kBits != 3) {
2653         if (!TEST_false(BN_generate_prime_ex(r, kBits, 1,
2654                                              NULL, NULL, NULL)))
2655             goto err;
2656     } else {
2657         if (!TEST_true(BN_generate_prime_ex(r, kBits, 1,
2658                                             NULL, NULL, NULL))
2659                 || !TEST_int_eq(BN_num_bits(r), kBits))
2660             goto err;
2661     }
2662
2663     st = 1;
2664  err:
2665     BN_free(r);
2666     return st;
2667 }
2668
2669 static int primes[] = { 2, 3, 5, 7, 17863 };
2670
2671 static int test_is_prime(int i)
2672 {
2673     int ret = 0;
2674     BIGNUM *r = NULL;
2675     int trial;
2676
2677     if (!TEST_ptr(r = BN_new()))
2678         goto err;
2679
2680     for (trial = 0; trial <= 1; ++trial) {
2681         if (!TEST_true(BN_set_word(r, primes[i]))
2682                 || !TEST_int_eq(BN_check_prime(r, ctx, NULL),
2683                                 1))
2684             goto err;
2685     }
2686
2687     ret = 1;
2688  err:
2689     BN_free(r);
2690     return ret;
2691 }
2692
2693 static int not_primes[] = { -1, 0, 1, 4 };
2694
2695 static int test_not_prime(int i)
2696 {
2697     int ret = 0;
2698     BIGNUM *r = NULL;
2699     int trial;
2700
2701     if (!TEST_ptr(r = BN_new()))
2702         goto err;
2703
2704     for (trial = 0; trial <= 1; ++trial) {
2705         if (!TEST_true(BN_set_word(r, not_primes[i]))
2706                 || !TEST_false(BN_check_prime(r, ctx, NULL)))
2707             goto err;
2708     }
2709
2710     ret = 1;
2711  err:
2712     BN_free(r);
2713     return ret;
2714 }
2715
2716 static int test_ctx_set_ct_flag(BN_CTX *c)
2717 {
2718     int st = 0;
2719     size_t i;
2720     BIGNUM *b[15];
2721
2722     BN_CTX_start(c);
2723     for (i = 0; i < OSSL_NELEM(b); i++) {
2724         if (!TEST_ptr(b[i] = BN_CTX_get(c)))
2725             goto err;
2726         if (i % 2 == 1)
2727             BN_set_flags(b[i], BN_FLG_CONSTTIME);
2728     }
2729
2730     st = 1;
2731  err:
2732     BN_CTX_end(c);
2733     return st;
2734 }
2735
2736 static int test_ctx_check_ct_flag(BN_CTX *c)
2737 {
2738     int st = 0;
2739     size_t i;
2740     BIGNUM *b[30];
2741
2742     BN_CTX_start(c);
2743     for (i = 0; i < OSSL_NELEM(b); i++) {
2744         if (!TEST_ptr(b[i] = BN_CTX_get(c)))
2745             goto err;
2746         if (!TEST_false(BN_get_flags(b[i], BN_FLG_CONSTTIME)))
2747             goto err;
2748     }
2749
2750     st = 1;
2751  err:
2752     BN_CTX_end(c);
2753     return st;
2754 }
2755
2756 static int test_ctx_consttime_flag(void)
2757 {
2758     /*-
2759      * The constant-time flag should not "leak" among BN_CTX frames:
2760      *
2761      * - test_ctx_set_ct_flag() starts a frame in the given BN_CTX and
2762      *   sets the BN_FLG_CONSTTIME flag on some of the BIGNUMs obtained
2763      *   from the frame before ending it.
2764      * - test_ctx_check_ct_flag() then starts a new frame and gets a
2765      *   number of BIGNUMs from it. In absence of leaks, none of the
2766      *   BIGNUMs in the new frame should have BN_FLG_CONSTTIME set.
2767      *
2768      * In actual BN_CTX usage inside libcrypto the leak could happen at
2769      * any depth level in the BN_CTX stack, with varying results
2770      * depending on the patterns of sibling trees of nested function
2771      * calls sharing the same BN_CTX object, and the effect of
2772      * unintended BN_FLG_CONSTTIME on the called BN_* functions.
2773      *
2774      * This simple unit test abstracts away this complexity and verifies
2775      * that the leak does not happen between two sibling functions
2776      * sharing the same BN_CTX object at the same level of nesting.
2777      *
2778      */
2779     BN_CTX *nctx = NULL;
2780     BN_CTX *sctx = NULL;
2781     size_t i = 0;
2782     int st = 0;
2783
2784     if (!TEST_ptr(nctx = BN_CTX_new())
2785             || !TEST_ptr(sctx = BN_CTX_secure_new()))
2786         goto err;
2787
2788     for (i = 0; i < 2; i++) {
2789         BN_CTX *c = i == 0 ? nctx : sctx;
2790         if (!TEST_true(test_ctx_set_ct_flag(c))
2791                 || !TEST_true(test_ctx_check_ct_flag(c)))
2792             goto err;
2793     }
2794
2795     st = 1;
2796  err:
2797     BN_CTX_free(nctx);
2798     BN_CTX_free(sctx);
2799     return st;
2800 }
2801
2802 static int test_coprime(void)
2803 {
2804     BIGNUM *a = NULL, *b = NULL;
2805     int ret = 0;
2806
2807     ret = TEST_ptr(a = BN_new())
2808           && TEST_ptr(b = BN_new())
2809           && TEST_true(BN_set_word(a, 66))
2810           && TEST_true(BN_set_word(b, 99))
2811           && TEST_int_eq(BN_are_coprime(a, b, ctx), 0)
2812           && TEST_int_eq(BN_are_coprime(b, a, ctx), 0)
2813           && TEST_true(BN_set_word(a, 67))
2814           && TEST_int_eq(BN_are_coprime(a, b, ctx), 1)
2815           && TEST_int_eq(BN_are_coprime(b, a, ctx), 1);
2816     BN_free(a);
2817     BN_free(b);
2818     return ret;
2819 }
2820
2821 static int test_gcd_prime(void)
2822 {
2823     BIGNUM *a = NULL, *b = NULL, *gcd = NULL;
2824     int i, st = 0;
2825
2826     if (!TEST_ptr(a = BN_new())
2827             || !TEST_ptr(b = BN_new())
2828             || !TEST_ptr(gcd = BN_new()))
2829         goto err;
2830
2831     if (!TEST_true(BN_generate_prime_ex(a, 1024, 0, NULL, NULL, NULL)))
2832             goto err;
2833     for (i = 0; i < NUM_PRIME_TESTS; i++) {
2834         if (!TEST_true(BN_generate_prime_ex(b, 1024, 0,
2835                                             NULL, NULL, NULL))
2836                 || !TEST_true(BN_gcd(gcd, a, b, ctx))
2837                 || !TEST_true(BN_is_one(gcd))
2838                 || !TEST_true(BN_are_coprime(a, b, ctx)))
2839             goto err;
2840     }
2841
2842     st = 1;
2843  err:
2844     BN_free(a);
2845     BN_free(b);
2846     BN_free(gcd);
2847     return st;
2848 }
2849
2850 typedef struct mod_exp_test_st
2851 {
2852   const char *base;
2853   const char *exp;
2854   const char *mod;
2855   const char *res;
2856 } MOD_EXP_TEST;
2857
2858 static const MOD_EXP_TEST ModExpTests[] = {
2859    /* original test vectors for rsaz_512_sqr bug, by OSS-Fuzz */
2860    {
2861        "1166180238001879113042182292626169621106255558914000595999312084"
2862        "4627946820899490684928760491249738643524880720584249698100907201"
2863        "002086675047927600340800371",
2864        "8000000000000000000000000000000000000000000000000000000000000000"
2865        "0000000000000000000000000000000000000000000000000000000000000000"
2866        "00000000",
2867        "1340780792684523720980737645613191762604395855615117867483316354"
2868        "3294276330515137663421134775482798690129946803802212663956180562"
2869        "088664022929883876655300863",
2870        "8243904058268085430037326628480645845409758077568738532059032482"
2871        "8294114415890603594730158120426756266457928475330450251339773498"
2872        "26758407619521544102068438"
2873    },
2874    {
2875        "4974270041410803822078866696159586946995877618987010219312844726"
2876        "0284386121835740784990869050050504348861513337232530490826340663"
2877        "197278031692737429054",
2878        "4974270041410803822078866696159586946995877428188754995041148539"
2879        "1663243362592271353668158565195557417149981094324650322556843202"
2880        "946445882670777892608",
2881        "1340780716511420227215592830971452482815377482627251725537099028"
2882        "4429769497230131760206012644403029349547320953206103351725462999"
2883        "947509743623340557059752191",
2884        "5296244594780707015616522701706118082963369547253192207884519362"
2885        "1767869984947542695665420219028522815539559194793619684334900442"
2886        "49304558011362360473525933"
2887    },
2888    /* test vectors for rsaz_512_srq bug, with rcx/rbx=1 */
2889    {   /* between first and second iteration */
2890        "5148719036160389201525610950887605325980251964889646556085286545"
2891        "3931548809178823413169359635978762036512397113080988070677858033"
2892        "36463909753993540214027190",
2893        "6703903964971298549787012499102923063739682910296196688861780721"
2894        "8608820150367734884009371490834517138450159290932430254268769414"
2895        "05973284973216824503042158",
2896        "6703903964971298549787012499102923063739682910296196688861780721"
2897        "8608820150367734884009371490834517138450159290932430254268769414"
2898        "05973284973216824503042159",
2899        "1"
2900    },
2901    {   /* between second and third iteration */
2902        "8908340854353752577419678771330460827942371434853054158622636544"
2903        "8151360109722890949471912566649465436296659601091730745087014189"
2904        "2672764191218875181826063",
2905        "6703903964971298549787012499102923063739682910296196688861780721"
2906        "8608820150367734884009371490834517138450159290932430254268769414"
2907        "05973284973216824503042158",
2908        "6703903964971298549787012499102923063739682910296196688861780721"
2909        "8608820150367734884009371490834517138450159290932430254268769414"
2910        "05973284973216824503042159",
2911        "1"
2912    },
2913    {   /* between third and fourth iteration */
2914        "3427446396505596330634350984901719674479522569002785244080234738"
2915        "4288743635435746136297299366444548736533053717416735379073185344"
2916        "26985272974404612945608761",
2917        "6703903964971298549787012499102923063739682910296196688861780721"
2918        "8608820150367734884009371490834517138450159290932430254268769414"
2919        "05973284973216824503042158",
2920        "6703903964971298549787012499102923063739682910296196688861780721"
2921        "8608820150367734884009371490834517138450159290932430254268769414"
2922        "05973284973216824503042159",
2923        "1"
2924    },
2925    {   /* between fourth and fifth iteration */
2926        "3472743044917564564078857826111874560045331237315597383869652985"
2927        "6919870028890895988478351133601517365908445058405433832718206902"
2928        "4088133164805266956353542",
2929        "6703903964971298549787012499102923063739682910296196688861780721"
2930        "8608820150367734884009371490834517138450159290932430254268769414"
2931        "05973284973216824503042158",
2932        "6703903964971298549787012499102923063739682910296196688861780721"
2933        "8608820150367734884009371490834517138450159290932430254268769414"
2934        "05973284973216824503042159",
2935        "1"
2936    },
2937    {   /* between fifth and sixth iteration */
2938        "3608632990153469264412378349742339216742409743898601587274768025"
2939        "0110772032985643555192767717344946174122842255204082586753499651"
2940        "14483434992887431333675068",
2941        "6703903964971298549787012499102923063739682910296196688861780721"
2942        "8608820150367734884009371490834517138450159290932430254268769414"
2943        "05973284973216824503042158",
2944        "6703903964971298549787012499102923063739682910296196688861780721"
2945        "8608820150367734884009371490834517138450159290932430254268769414"
2946        "05973284973216824503042159",
2947        "1"
2948    },
2949    {   /* between sixth and seventh iteration */
2950        "8455374370234070242910508226941981520235709767260723212165264877"
2951        "8689064388017521524568434328264431772644802567028663962962025746"
2952        "9283458217850119569539086",
2953        "6703903964971298549787012499102923063739682910296196688861780721"
2954        "8608820150367734884009371490834517138450159290932430254268769414"
2955        "05973284973216824503042158",
2956        "6703903964971298549787012499102923063739682910296196688861780721"
2957        "8608820150367734884009371490834517138450159290932430254268769414"
2958        "05973284973216824503042159",
2959        "1"
2960    },
2961    {   /* between seventh and eighth iteration */
2962        "5155371529688532178421209781159131443543419764974688878527112131"
2963        "7446518205609427412336183157918981038066636807317733319323257603"
2964        "04416292040754017461076359",
2965        "1005585594745694782468051874865438459560952436544429503329267108"
2966        "2791323022555160232601405723625177570767523893639864538140315412"
2967        "108959927459825236754563832",
2968        "1005585594745694782468051874865438459560952436544429503329267108"
2969        "2791323022555160232601405723625177570767523893639864538140315412"
2970        "108959927459825236754563833",
2971        "1"
2972    },
2973    /* test vectors for rsaz_512_srq bug, with rcx/rbx=2 */
2974    {   /* between first and second iteration */
2975        "3155666506033786929967309937640790361084670559125912405342594979"
2976        "4345142818528956285490897841406338022378565972533508820577760065"
2977        "58494345853302083699912572",
2978        "6703903964971298549787012499102923063739682910296196688861780721"
2979        "8608820150367734884009371490834517138450159290932430254268769414"
2980        "05973284973216824503042158",
2981        "6703903964971298549787012499102923063739682910296196688861780721"
2982        "8608820150367734884009371490834517138450159290932430254268769414"
2983        "05973284973216824503042159",
2984        "1"
2985    },
2986    {   /* between second and third iteration */
2987        "3789819583801342198190405714582958759005991915505282362397087750"
2988        "4213544724644823098843135685133927198668818185338794377239590049"
2989        "41019388529192775771488319",
2990        "6703903964971298549787012499102923063739682910296196688861780721"
2991        "8608820150367734884009371490834517138450159290932430254268769414"
2992        "05973284973216824503042158",
2993        "6703903964971298549787012499102923063739682910296196688861780721"
2994        "8608820150367734884009371490834517138450159290932430254268769414"
2995        "05973284973216824503042159",
2996        "1"
2997    },
2998    {   /* between third and forth iteration */
2999        "4695752552040706867080542538786056470322165281761525158189220280"
3000        "4025547447667484759200742764246905647644662050122968912279199065"
3001        "48065034299166336940507214",
3002        "6703903964971298549787012499102923063739682910296196688861780721"
3003        "8608820150367734884009371490834517138450159290932430254268769414"
3004        "05973284973216824503042158",
3005        "6703903964971298549787012499102923063739682910296196688861780721"
3006        "8608820150367734884009371490834517138450159290932430254268769414"
3007        "05973284973216824503042159",
3008        "1"
3009    },
3010    {   /* between forth and fifth iteration */
3011        "2159140240970485794188159431017382878636879856244045329971239574"
3012        "8919691133560661162828034323196457386059819832804593989740268964"
3013        "74502911811812651475927076",
3014        "6703903964971298549787012499102923063739682910296196688861780721"
3015        "8608820150367734884009371490834517138450159290932430254268769414"
3016        "05973284973216824503042158",
3017        "6703903964971298549787012499102923063739682910296196688861780721"
3018        "8608820150367734884009371490834517138450159290932430254268769414"
3019        "05973284973216824503042159",
3020        "1"
3021    },
3022    {   /* between fifth and sixth iteration */
3023        "5239312332984325668414624633307915097111691815000872662334695514"
3024        "5436533521392362443557163429336808208137221322444780490437871903"
3025        "99972784701334569424519255",
3026        "6703903964971298549787012499102923063739682910296196688861780721"
3027        "8608820150367734884009371490834517138450159290932430254268769414"
3028        "05973284973216824503042158",
3029        "6703903964971298549787012499102923063739682910296196688861780721"
3030        "8608820150367734884009371490834517138450159290932430254268769414"
3031        "05973284973216824503042159",
3032        "1"
3033    },
3034    {   /* between sixth and seventh iteration */
3035        "1977953647322612860406858017869125467496941904523063466791308891"
3036        "1172796739058531929470539758361774569875505293428856181093904091"
3037        "33788264851714311303725089",
3038        "6703903964971298549787012499102923063739682910296196688861780721"
3039        "8608820150367734884009371490834517138450159290932430254268769414"
3040        "05973284973216824503042158",
3041        "6703903964971298549787012499102923063739682910296196688861780721"
3042        "8608820150367734884009371490834517138450159290932430254268769414"
3043        "05973284973216824503042159",
3044        "1"
3045    },
3046    {   /* between seventh and eighth iteration */
3047        "6456987954117763835533395796948878140715006860263624787492985786"
3048        "8514630216966738305923915688821526449499763719943997120302368211"
3049        "04813318117996225041943964",
3050        "1340780792994259709957402499820584612747936582059239337772356144"
3051        "3721764030073546976801874298166903427690031858186486050853753882"
3052        "811946551499689575296532556",
3053        "1340780792994259709957402499820584612747936582059239337772356144"
3054        "3721764030073546976801874298166903427690031858186486050853753882"
3055        "811946551499689575296532557",
3056        "1"
3057    }
3058 };
3059
3060 static int test_mod_exp(int i)
3061 {
3062     const MOD_EXP_TEST *test = &ModExpTests[i];
3063     int res = 0;
3064     BIGNUM* result = NULL;
3065     BIGNUM *base = NULL, *exponent = NULL, *modulo = NULL;
3066     char *s = NULL;
3067
3068     if (!TEST_ptr(result = BN_new())
3069             || !TEST_true(BN_dec2bn(&base, test->base))
3070             || !TEST_true(BN_dec2bn(&exponent, test->exp))
3071             || !TEST_true(BN_dec2bn(&modulo, test->mod)))
3072         goto err;
3073
3074     if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1))
3075         goto err;
3076
3077     if (!TEST_ptr(s = BN_bn2dec(result)))
3078         goto err;
3079
3080     if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res)))
3081         goto err;
3082
3083     res = 1;
3084
3085  err:
3086     OPENSSL_free(s);
3087     BN_free(result);
3088     BN_free(base);
3089     BN_free(exponent);
3090     BN_free(modulo);
3091     return res;
3092 }
3093
3094 static int test_mod_exp_consttime(int i)
3095 {
3096     const MOD_EXP_TEST *test = &ModExpTests[i];
3097     int res = 0;
3098     BIGNUM* result = NULL;
3099     BIGNUM *base = NULL, *exponent = NULL, *modulo = NULL;
3100     char *s = NULL;
3101
3102     if (!TEST_ptr(result = BN_new())
3103             || !TEST_true(BN_dec2bn(&base, test->base))
3104             || !TEST_true(BN_dec2bn(&exponent, test->exp))
3105             || !TEST_true(BN_dec2bn(&modulo, test->mod)))
3106         goto err;
3107
3108     BN_set_flags(base, BN_FLG_CONSTTIME);
3109     BN_set_flags(exponent, BN_FLG_CONSTTIME);
3110     BN_set_flags(modulo, BN_FLG_CONSTTIME);
3111
3112     if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1))
3113         goto err;
3114
3115     if (!TEST_ptr(s = BN_bn2dec(result)))
3116         goto err;
3117
3118     if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res)))
3119         goto err;
3120
3121     res = 1;
3122
3123  err:
3124     OPENSSL_free(s);
3125     BN_free(result);
3126     BN_free(base);
3127     BN_free(exponent);
3128     BN_free(modulo);
3129     return res;
3130 }
3131
3132 /*
3133  * Regression test to ensure BN_mod_exp2_mont fails safely if argument m is
3134  * zero.
3135  */
3136 static int test_mod_exp2_mont(void)
3137 {
3138     int res = 0;
3139     BIGNUM *exp_result = NULL;
3140     BIGNUM *exp_a1 = NULL, *exp_p1 = NULL, *exp_a2 = NULL, *exp_p2 = NULL,
3141            *exp_m = NULL;
3142
3143     if (!TEST_ptr(exp_result = BN_new())
3144             || !TEST_ptr(exp_a1 = BN_new())
3145             || !TEST_ptr(exp_p1 = BN_new())
3146             || !TEST_ptr(exp_a2 = BN_new())
3147             || !TEST_ptr(exp_p2 = BN_new())
3148             || !TEST_ptr(exp_m = BN_new()))
3149         goto err;
3150
3151     if (!TEST_true(BN_one(exp_a1))
3152             || !TEST_true(BN_one(exp_p1))
3153             || !TEST_true(BN_one(exp_a2))
3154             || !TEST_true(BN_one(exp_p2)))
3155         goto err;
3156
3157     BN_zero(exp_m);
3158
3159     /* input of 0 is even, so must fail */
3160     if (!TEST_int_eq(BN_mod_exp2_mont(exp_result, exp_a1, exp_p1, exp_a2,
3161                 exp_p2, exp_m, ctx, NULL), 0))
3162         goto err;
3163
3164     res = 1;
3165
3166 err:
3167     BN_free(exp_result);
3168     BN_free(exp_a1);
3169     BN_free(exp_p1);
3170     BN_free(exp_a2);
3171     BN_free(exp_p2);
3172     BN_free(exp_m);
3173     return res;
3174 }
3175
3176 static int test_mod_inverse(void)
3177 {
3178     int res = 0;
3179     char *str = NULL;
3180     BIGNUM *a = NULL;
3181     BIGNUM *b = NULL;
3182     BIGNUM *r = NULL;
3183
3184     if (!TEST_true(BN_dec2bn(&a, "5193817943")))
3185         goto err;
3186     if (!TEST_true(BN_dec2bn(&b, "3259122431")))
3187         goto err;
3188     if (!TEST_ptr(r = BN_new()))
3189         goto err;
3190     if (!TEST_ptr_eq(BN_mod_inverse(r, a, b, ctx), r))
3191         goto err;
3192     if (!TEST_ptr_ne(str = BN_bn2dec(r), NULL))
3193         goto err;
3194     if (!TEST_int_eq(strcmp(str, "2609653924"), 0))
3195         goto err;
3196
3197     /* Note that this aliases the result with the modulus. */
3198     if (!TEST_ptr_null(BN_mod_inverse(b, a, b, ctx)))
3199         goto err;
3200
3201     res = 1;
3202
3203 err:
3204     BN_free(a);
3205     BN_free(b);
3206     BN_free(r);
3207     OPENSSL_free(str);
3208     return res;
3209 }
3210
3211 static int test_mod_exp_alias(int idx)
3212 {
3213     int res = 0;
3214     char *str = NULL;
3215     BIGNUM *a = NULL;
3216     BIGNUM *b = NULL;
3217     BIGNUM *c = NULL;
3218     BIGNUM *r = NULL;
3219
3220     if (!TEST_true(BN_dec2bn(&a, "15")))
3221         goto err;
3222     if (!TEST_true(BN_dec2bn(&b, "10")))
3223         goto err;
3224     if (!TEST_true(BN_dec2bn(&c, "39")))
3225         goto err;
3226     if (!TEST_ptr(r = BN_new()))
3227         goto err;
3228
3229     if (!TEST_int_eq((idx == 0 ? BN_mod_exp_simple
3230                                : BN_mod_exp_recp)(r, a, b, c, ctx), 1))
3231         goto err;
3232     if (!TEST_ptr_ne(str = BN_bn2dec(r), NULL))
3233         goto err;
3234     if (!TEST_str_eq(str, "36"))
3235         goto err;
3236
3237     OPENSSL_free(str);
3238     str = NULL;
3239
3240     BN_copy(r, b);
3241
3242     /* Aliasing with exponent must work. */
3243     if (!TEST_int_eq((idx == 0 ? BN_mod_exp_simple
3244                                : BN_mod_exp_recp)(r, a, r, c, ctx), 1))
3245         goto err;
3246     if (!TEST_ptr_ne(str = BN_bn2dec(r), NULL))
3247         goto err;
3248     if (!TEST_str_eq(str, "36"))
3249         goto err;
3250
3251     OPENSSL_free(str);
3252     str = NULL;
3253
3254     /* Aliasing with modulus should return failure for the simple call. */
3255     if (idx == 0) {
3256         if (!TEST_int_eq(BN_mod_exp_simple(c, a, b, c, ctx), 0))
3257             goto err;
3258     } else {
3259         if (!TEST_int_eq(BN_mod_exp_recp(c, a, b, c, ctx), 1))
3260             goto err;
3261         if (!TEST_ptr_ne(str = BN_bn2dec(c), NULL))
3262             goto err;
3263         if (!TEST_str_eq(str, "36"))
3264             goto err;
3265     }
3266
3267     res = 1;
3268
3269 err:
3270     BN_free(a);
3271     BN_free(b);
3272     BN_free(c);
3273     BN_free(r);
3274     OPENSSL_free(str);
3275     return res;
3276 }
3277
3278 static int file_test_run(STANZA *s)
3279 {
3280     static const FILETEST filetests[] = {
3281         {"Sum", file_sum},
3282         {"LShift1", file_lshift1},
3283         {"LShift", file_lshift},
3284         {"RShift", file_rshift},
3285         {"Square", file_square},
3286         {"Product", file_product},
3287         {"Quotient", file_quotient},
3288         {"ModMul", file_modmul},
3289         {"ModExp", file_modexp},
3290         {"Exp", file_exp},
3291         {"ModSqrt", file_modsqrt},
3292         {"GCD", file_gcd},
3293     };
3294     int numtests = OSSL_NELEM(filetests);
3295     const FILETEST *tp = filetests;
3296
3297     for ( ; --numtests >= 0; tp++) {
3298         if (findattr(s, tp->name) != NULL) {
3299             if (!tp->func(s)) {
3300                 TEST_info("%s:%d: Failed %s test",
3301                           s->test_file, s->start, tp->name);
3302                 return 0;
3303             }
3304             return 1;
3305         }
3306     }
3307     TEST_info("%s:%d: Unknown test", s->test_file, s->start);
3308     return 0;
3309 }
3310
3311 static int run_file_tests(int i)
3312 {
3313     STANZA *s = NULL;
3314     char *testfile = test_get_argument(i);
3315     int c;
3316
3317     if (!TEST_ptr(s = OPENSSL_zalloc(sizeof(*s))))
3318         return 0;
3319     if (!test_start_file(s, testfile)) {
3320         OPENSSL_free(s);
3321         return 0;
3322     }
3323
3324     /* Read test file. */
3325     while (!BIO_eof(s->fp) && test_readstanza(s)) {
3326         if (s->numpairs == 0)
3327             continue;
3328         if (!file_test_run(s))
3329             s->errors++;
3330         s->numtests++;
3331         test_clearstanza(s);
3332     }
3333     test_end_file(s);
3334     c = s->errors;
3335     OPENSSL_free(s);
3336
3337     return c == 0;
3338 }
3339
3340 typedef enum OPTION_choice {
3341     OPT_ERR = -1,
3342     OPT_EOF = 0,
3343     OPT_STOCHASTIC_TESTS,
3344     OPT_TEST_ENUM
3345 } OPTION_CHOICE;
3346
3347 const OPTIONS *test_get_options(void)
3348 {
3349     static const OPTIONS test_options[] = {
3350         OPT_TEST_OPTIONS_WITH_EXTRA_USAGE("[file...]\n"),
3351         { "stochastic", OPT_STOCHASTIC_TESTS, '-', "Run stochastic tests" },
3352         { OPT_HELP_STR, 1, '-',
3353           "file\tFile to run tests on. Normal tests are not run\n" },
3354         { NULL }
3355     };
3356     return test_options;
3357 }
3358
3359 int setup_tests(void)
3360 {
3361     OPTION_CHOICE o;
3362     int n, stochastic = 0;
3363
3364     while ((o = opt_next()) != OPT_EOF) {
3365         switch (o) {
3366         case OPT_STOCHASTIC_TESTS:
3367             stochastic = 1;
3368             break;
3369         case OPT_TEST_CASES:
3370            break;
3371         default:
3372         case OPT_ERR:
3373             return 0;
3374         }
3375     }
3376     n  = test_get_argument_count();
3377
3378     if (!TEST_ptr(ctx = BN_CTX_new()))
3379         return 0;
3380
3381     if (n == 0) {
3382         ADD_TEST(test_sub);
3383         ADD_TEST(test_div_recip);
3384         ADD_ALL_TESTS(test_signed_mod_replace_ab, OSSL_NELEM(signed_mod_tests));
3385         ADD_ALL_TESTS(test_signed_mod_replace_ba, OSSL_NELEM(signed_mod_tests));
3386         ADD_TEST(test_mod);
3387         ADD_TEST(test_mod_inverse);
3388         ADD_ALL_TESTS(test_mod_exp_alias, 2);
3389         ADD_TEST(test_modexp_mont5);
3390         ADD_TEST(test_kronecker);
3391         ADD_TEST(test_rand);
3392         ADD_TEST(test_bn2padded);
3393         ADD_TEST(test_dec2bn);
3394         ADD_TEST(test_hex2bn);
3395         ADD_TEST(test_asc2bn);
3396         ADD_TEST(test_bin2zero);
3397         ADD_TEST(test_bin2bn_lengths);
3398         ADD_ALL_TESTS(test_mpi, (int)OSSL_NELEM(kMPITests));
3399         ADD_ALL_TESTS(test_bn2signed, (int)OSSL_NELEM(kSignedTests_BE));
3400         ADD_TEST(test_negzero);
3401         ADD_TEST(test_badmod);
3402         ADD_TEST(test_expmodzero);
3403         ADD_TEST(test_expmodone);
3404         ADD_ALL_TESTS(test_smallprime, 16);
3405         ADD_ALL_TESTS(test_smallsafeprime, 16);
3406         ADD_TEST(test_swap);
3407         ADD_TEST(test_ctx_consttime_flag);
3408 #ifndef OPENSSL_NO_EC2M
3409         ADD_TEST(test_gf2m_add);
3410         ADD_TEST(test_gf2m_mod);
3411         ADD_TEST(test_gf2m_mul);
3412         ADD_TEST(test_gf2m_sqr);
3413         ADD_TEST(test_gf2m_modinv);
3414         ADD_TEST(test_gf2m_moddiv);
3415         ADD_TEST(test_gf2m_modexp);
3416         ADD_TEST(test_gf2m_modsqrt);
3417         ADD_TEST(test_gf2m_modsolvequad);
3418 #endif
3419         ADD_ALL_TESTS(test_is_prime, (int)OSSL_NELEM(primes));
3420         ADD_ALL_TESTS(test_not_prime, (int)OSSL_NELEM(not_primes));
3421         ADD_TEST(test_gcd_prime);
3422         ADD_TEST(test_coprime);
3423         ADD_ALL_TESTS(test_mod_exp, (int)OSSL_NELEM(ModExpTests));
3424         ADD_ALL_TESTS(test_mod_exp_consttime, (int)OSSL_NELEM(ModExpTests));
3425         ADD_TEST(test_mod_exp2_mont);
3426         if (stochastic)
3427             ADD_TEST(test_rand_range);
3428     } else {
3429         ADD_ALL_TESTS(run_file_tests, n);
3430     }
3431     return 1;
3432 }
3433
3434 void cleanup_tests(void)
3435 {
3436     BN_CTX_free(ctx);
3437 }