test/bntest.c

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