test/bntest.c

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