test/bntest.c

   1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   2  * All rights reserved.
   3  *
   4  * This package is an SSL implementation written
   5  * by Eric Young (eay@cryptsoft.com).
   6  * The implementation was written so as to conform with Netscapes SSL.
   7  *
   8  * This library is free for commercial and non-commercial use as long as
   9  * the following conditions are aheared to.  The following conditions
  10  * apply to all code found in this distribution, be it the RC4, RSA,
  11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  12  * included with this distribution is covered by the same copyright terms
  13  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  14  *
  15  * Copyright remains Eric Young's, and as such any Copyright notices in
  16  * the code are not to be removed.
  17  * If this package is used in a product, Eric Young should be given attribution
  18  * as the author of the parts of the library used.
  19  * This can be in the form of a textual message at program startup or
  20  * in documentation (online or textual) provided with the package.
  21  *
  22  * Redistribution and use in source and binary forms, with or without
  23  * modification, are permitted provided that the following conditions
  24  * are met:
  25  * 1. Redistributions of source code must retain the copyright
  26  *    notice, this list of conditions and the following disclaimer.
  27  * 2. Redistributions in binary form must reproduce the above copyright
  28  *    notice, this list of conditions and the following disclaimer in the
  29  *    documentation and/or other materials provided with the distribution.
  30  * 3. All advertising materials mentioning features or use of this software
  31  *    must display the following acknowledgement:
  32  *    "This product includes cryptographic software written by
  33  *     Eric Young (eay@cryptsoft.com)"
  34  *    The word 'cryptographic' can be left out if the rouines from the library
  35  *    being used are not cryptographic related :-).
  36  * 4. If you include any Windows specific code (or a derivative thereof) from
  37  *    the apps directory (application code) you must include an acknowledgement:
  38  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  39  *
  40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  50  * SUCH DAMAGE.
  51  *
  52  * The licence and distribution terms for any publically available version or
  53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  54  * copied and put under another distribution licence
  55  * [including the GNU Public Licence.]
  56  */
  57 /* ====================================================================
  58  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  59  *
  60  * Portions of the attached software ("Contribution") are developed by
  61  * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
  62  *
  63  * The Contribution is licensed pursuant to the Eric Young open source
  64  * license provided above.
  65  *
  66  * The binary polynomial arithmetic software is originally written by
  67  * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems Laboratories.
  68  *
  69  */
  70
  71 #include <stdio.h>
  72 #include <stdlib.h>
  73 #include <string.h>
  74
  75 #include "e_os.h"
  76
  77 #include <openssl/bio.h>
  78 #include <openssl/bn.h>
  79 #include <openssl/rand.h>
  80 #include <openssl/x509.h>
  81 #include <openssl/err.h>
  82
  83 /*
  84  * In bn_lcl.h, bn_expand() is defined as a static ossl_inline function.
  85  * This is fine in itself, it will end up as an unused static function in
  86  * the worst case.  However, it referenses bn_expand2(), which is a private
  87  * function in libcrypto and therefore unavailable on some systems.  This
  88  * may result in a linker error because of unresolved symbols.
  89  *
  90  * To avoid this, we define a dummy variant of bn_expand2() here, and to
  91  * avoid possible clashes with libcrypto, we rename it first, using a macro.
  92  */
  93 #define bn_expand2 dummy_bn_expand2
  94 BIGNUM *bn_expand2(BIGNUM *b, int words);
  95 BIGNUM *bn_expand2(BIGNUM *b, int words) { return NULL; }
  96
  97 #include "../crypto/bn/bn_lcl.h"
  98
  99 static const int num0 = 100;           /* number of tests */
 100 static const int num1 = 50;            /* additional tests for some functions */
 101 static const int num2 = 5;             /* number of tests for slow functions */
 102
 103 int test_add(BIO *bp);
 104 int test_sub(BIO *bp);
 105 int test_lshift1(BIO *bp);
 106 int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_);
 107 int test_rshift1(BIO *bp);
 108 int test_rshift(BIO *bp, BN_CTX *ctx);
 109 int test_div(BIO *bp, BN_CTX *ctx);
 110 int test_div_word(BIO *bp);
 111 int test_div_recp(BIO *bp, BN_CTX *ctx);
 112 int test_mul(BIO *bp);
 113 int test_sqr(BIO *bp, BN_CTX *ctx);
 114 int test_mont(BIO *bp, BN_CTX *ctx);
 115 int test_mod(BIO *bp, BN_CTX *ctx);
 116 int test_mod_mul(BIO *bp, BN_CTX *ctx);
 117 int test_mod_exp(BIO *bp, BN_CTX *ctx);
 118 int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx);
 119 int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx);
 120 int test_exp(BIO *bp, BN_CTX *ctx);
 121 int test_gf2m_add(BIO *bp);
 122 int test_gf2m_mod(BIO *bp);
 123 int test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx);
 124 int test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx);
 125 int test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx);
 126 int test_gf2m_mod_div(BIO *bp, BN_CTX *ctx);
 127 int test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx);
 128 int test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx);
 129 int test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx);
 130 int test_kron(BIO *bp, BN_CTX *ctx);
 131 int test_sqrt(BIO *bp, BN_CTX *ctx);
 132 int test_small_prime(BIO *bp, BN_CTX *ctx);
 133 int rand_neg(void);
 134 static int results = 0;
 135
 136 static unsigned char lst[] =
 137     "\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9"
 138     "\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0";
 139
 140 static const char rnd_seed[] =
 141     "string to make the random number generator think it has entropy";
 142
 143 static void message(BIO *out, char *m)
 144 {
 145     fprintf(stderr, "test %s\n", m);
 146     BIO_puts(out, "print \"test ");
 147     BIO_puts(out, m);
 148     BIO_puts(out, "\\n\"\n");
 149 }
 150
 151 int main(int argc, char *argv[])
 152 {
 153     BN_CTX *ctx;
 154     BIO *out;
 155     char *outfile = NULL;
 156
 157     results = 0;
 158
 159     RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_generate_prime may fail */
 160
 161     argc--;
 162     argv++;
 163     while (argc >= 1) {
 164         if (strcmp(*argv, "-results") == 0)
 165             results = 1;
 166         else if (strcmp(*argv, "-out") == 0) {
 167             if (--argc < 1)
 168                 break;
 169             outfile = *(++argv);
 170         }
 171         argc--;
 172         argv++;
 173     }
 174
 175     ctx = BN_CTX_new();
 176     if (ctx == NULL)
 177         EXIT(1);
 178
 179     out = BIO_new(BIO_s_file());
 180     if (out == NULL)
 181         EXIT(1);
 182     if (outfile == NULL) {
 183         BIO_set_fp(out, stdout, BIO_NOCLOSE | BIO_FP_TEXT);
 184     } else {
 185         if (!BIO_write_filename(out, outfile)) {
 186             perror(outfile);
 187             EXIT(1);
 188         }
 189     }
 190 #ifdef OPENSSL_SYS_VMS
 191     {
 192         BIO *tmpbio = BIO_new(BIO_f_linebuffer());
 193         out = BIO_push(tmpbio, out);
 194     }
 195 #endif
 196
 197     if (!results)
 198         BIO_puts(out, "obase=16\nibase=16\n");
 199
 200     message(out, "BN_add");
 201     if (!test_add(out))
 202         goto err;
 203     (void)BIO_flush(out);
 204
 205     message(out, "BN_sub");
 206     if (!test_sub(out))
 207         goto err;
 208     (void)BIO_flush(out);
 209
 210     message(out, "BN_lshift1");
 211     if (!test_lshift1(out))
 212         goto err;
 213     (void)BIO_flush(out);
 214
 215     message(out, "BN_lshift (fixed)");
 216     if (!test_lshift(out, ctx, BN_bin2bn(lst, sizeof(lst) - 1, NULL)))
 217         goto err;
 218     (void)BIO_flush(out);
 219
 220     message(out, "BN_lshift");
 221     if (!test_lshift(out, ctx, NULL))
 222         goto err;
 223     (void)BIO_flush(out);
 224
 225     message(out, "BN_rshift1");
 226     if (!test_rshift1(out))
 227         goto err;
 228     (void)BIO_flush(out);
 229
 230     message(out, "BN_rshift");
 231     if (!test_rshift(out, ctx))
 232         goto err;
 233     (void)BIO_flush(out);
 234
 235     message(out, "BN_sqr");
 236     if (!test_sqr(out, ctx))
 237         goto err;
 238     (void)BIO_flush(out);
 239
 240     message(out, "BN_mul");
 241     if (!test_mul(out))
 242         goto err;
 243     (void)BIO_flush(out);
 244
 245     message(out, "BN_div");
 246     if (!test_div(out, ctx))
 247         goto err;
 248     (void)BIO_flush(out);
 249
 250     message(out, "BN_div_word");
 251     if (!test_div_word(out))
 252         goto err;
 253     (void)BIO_flush(out);
 254
 255     message(out, "BN_div_recp");
 256     if (!test_div_recp(out, ctx))
 257         goto err;
 258     (void)BIO_flush(out);
 259
 260     message(out, "BN_mod");
 261     if (!test_mod(out, ctx))
 262         goto err;
 263     (void)BIO_flush(out);
 264
 265     message(out, "BN_mod_mul");
 266     if (!test_mod_mul(out, ctx))
 267         goto err;
 268     (void)BIO_flush(out);
 269
 270     message(out, "BN_mont");
 271     if (!test_mont(out, ctx))
 272         goto err;
 273     (void)BIO_flush(out);
 274
 275     message(out, "BN_mod_exp");
 276     if (!test_mod_exp(out, ctx))
 277         goto err;
 278     (void)BIO_flush(out);
 279
 280     message(out, "BN_mod_exp_mont_consttime");
 281     if (!test_mod_exp_mont_consttime(out, ctx))
 282         goto err;
 283     if (!test_mod_exp_mont5(out, ctx))
 284         goto err;
 285     (void)BIO_flush(out);
 286
 287     message(out, "BN_exp");
 288     if (!test_exp(out, ctx))
 289         goto err;
 290     (void)BIO_flush(out);
 291
 292     message(out, "BN_kronecker");
 293     if (!test_kron(out, ctx))
 294         goto err;
 295     (void)BIO_flush(out);
 296
 297     message(out, "BN_mod_sqrt");
 298     if (!test_sqrt(out, ctx))
 299         goto err;
 300     (void)BIO_flush(out);
 301
 302     message(out, "Small prime generation");
 303     if (!test_small_prime(out, ctx))
 304         goto err;
 305     (void)BIO_flush(out);
 306
 307 #ifndef OPENSSL_NO_EC2M
 308     message(out, "BN_GF2m_add");
 309     if (!test_gf2m_add(out))
 310         goto err;
 311     (void)BIO_flush(out);
 312
 313     message(out, "BN_GF2m_mod");
 314     if (!test_gf2m_mod(out))
 315         goto err;
 316     (void)BIO_flush(out);
 317
 318     message(out, "BN_GF2m_mod_mul");
 319     if (!test_gf2m_mod_mul(out, ctx))
 320         goto err;
 321     (void)BIO_flush(out);
 322
 323     message(out, "BN_GF2m_mod_sqr");
 324     if (!test_gf2m_mod_sqr(out, ctx))
 325         goto err;
 326     (void)BIO_flush(out);
 327
 328     message(out, "BN_GF2m_mod_inv");
 329     if (!test_gf2m_mod_inv(out, ctx))
 330         goto err;
 331     (void)BIO_flush(out);
 332
 333     message(out, "BN_GF2m_mod_div");
 334     if (!test_gf2m_mod_div(out, ctx))
 335         goto err;
 336     (void)BIO_flush(out);
 337
 338     message(out, "BN_GF2m_mod_exp");
 339     if (!test_gf2m_mod_exp(out, ctx))
 340         goto err;
 341     (void)BIO_flush(out);
 342
 343     message(out, "BN_GF2m_mod_sqrt");
 344     if (!test_gf2m_mod_sqrt(out, ctx))
 345         goto err;
 346     (void)BIO_flush(out);
 347
 348     message(out, "BN_GF2m_mod_solve_quad");
 349     if (!test_gf2m_mod_solve_quad(out, ctx))
 350         goto err;
 351     (void)BIO_flush(out);
 352 #endif
 353     BN_CTX_free(ctx);
 354     BIO_free(out);
 355
 356     EXIT(0);
 357  err:
 358     BIO_puts(out, "1\n");       /* make sure the Perl script fed by bc
 359                                  * notices the failure, see test_bn in
 360                                  * test/Makefile.ssl */
 361     (void)BIO_flush(out);
 362
 363     ERR_print_errors_fp(stderr);
 364     EXIT(1);
 365 }
 366
 367 int test_add(BIO *bp)
 368 {
 369     BIGNUM *a, *b, *c;
 370     int i;
 371
 372     a = BN_new();
 373     b = BN_new();
 374     c = BN_new();
 375
 376     BN_bntest_rand(a, 512, 0, 0);
 377     for (i = 0; i < num0; i++) {
 378         BN_bntest_rand(b, 450 + i, 0, 0);
 379         a->neg = rand_neg();
 380         b->neg = rand_neg();
 381         BN_add(c, a, b);
 382         if (bp != NULL) {
 383             if (!results) {
 384                 BN_print(bp, a);
 385                 BIO_puts(bp, " + ");
 386                 BN_print(bp, b);
 387                 BIO_puts(bp, " - ");
 388             }
 389             BN_print(bp, c);
 390             BIO_puts(bp, "\n");
 391         }
 392         a->neg = !a->neg;
 393         b->neg = !b->neg;
 394         BN_add(c, c, b);
 395         BN_add(c, c, a);
 396         if (!BN_is_zero(c)) {
 397             fprintf(stderr, "Add test failed!\n");
 398             return 0;
 399         }
 400     }
 401     BN_free(a);
 402     BN_free(b);
 403     BN_free(c);
 404     return (1);
 405 }
 406
 407 int test_sub(BIO *bp)
 408 {
 409     BIGNUM *a, *b, *c;
 410     int i;
 411
 412     a = BN_new();
 413     b = BN_new();
 414     c = BN_new();
 415
 416     for (i = 0; i < num0 + num1; i++) {
 417         if (i < num1) {
 418             BN_bntest_rand(a, 512, 0, 0);
 419             BN_copy(b, a);
 420             if (BN_set_bit(a, i) == 0)
 421                 return (0);
 422             BN_add_word(b, i);
 423         } else {
 424             BN_bntest_rand(b, 400 + i - num1, 0, 0);
 425             a->neg = rand_neg();
 426             b->neg = rand_neg();
 427         }
 428         BN_sub(c, a, b);
 429         if (bp != NULL) {
 430             if (!results) {
 431                 BN_print(bp, a);
 432                 BIO_puts(bp, " - ");
 433                 BN_print(bp, b);
 434                 BIO_puts(bp, " - ");
 435             }
 436             BN_print(bp, c);
 437             BIO_puts(bp, "\n");
 438         }
 439         BN_add(c, c, b);
 440         BN_sub(c, c, a);
 441         if (!BN_is_zero(c)) {
 442             fprintf(stderr, "Subtract test failed!\n");
 443             return 0;
 444         }
 445     }
 446     BN_free(a);
 447     BN_free(b);
 448     BN_free(c);
 449     return (1);
 450 }
 451
 452 int test_div(BIO *bp, BN_CTX *ctx)
 453 {
 454     BIGNUM *a, *b, *c, *d, *e;
 455     int i;
 456
 457     a = BN_new();
 458     b = BN_new();
 459     c = BN_new();
 460     d = BN_new();
 461     e = BN_new();
 462
 463     BN_one(a);
 464     BN_zero(b);
 465
 466     if (BN_div(d, c, a, b, ctx)) {
 467         fprintf(stderr, "Division by zero succeeded!\n");
 468         return 0;
 469     }
 470
 471     for (i = 0; i < num0 + num1; i++) {
 472         if (i < num1) {
 473             BN_bntest_rand(a, 400, 0, 0);
 474             BN_copy(b, a);
 475             BN_lshift(a, a, i);
 476             BN_add_word(a, i);
 477         } else
 478             BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0);
 479         a->neg = rand_neg();
 480         b->neg = rand_neg();
 481         BN_div(d, c, a, b, ctx);
 482         if (bp != NULL) {
 483             if (!results) {
 484                 BN_print(bp, a);
 485                 BIO_puts(bp, " / ");
 486                 BN_print(bp, b);
 487                 BIO_puts(bp, " - ");
 488             }
 489             BN_print(bp, d);
 490             BIO_puts(bp, "\n");
 491
 492             if (!results) {
 493                 BN_print(bp, a);
 494                 BIO_puts(bp, " % ");
 495                 BN_print(bp, b);
 496                 BIO_puts(bp, " - ");
 497             }
 498             BN_print(bp, c);
 499             BIO_puts(bp, "\n");
 500         }
 501         BN_mul(e, d, b, ctx);
 502         BN_add(d, e, c);
 503         BN_sub(d, d, a);
 504         if (!BN_is_zero(d)) {
 505             fprintf(stderr, "Division test failed!\n");
 506             return 0;
 507         }
 508     }
 509     BN_free(a);
 510     BN_free(b);
 511     BN_free(c);
 512     BN_free(d);
 513     BN_free(e);
 514     return (1);
 515 }
 516
 517 static void print_word(BIO *bp, BN_ULONG w)
 518 {
 519     int i = sizeof(w) * 8;
 520     char *fmt = NULL;
 521     unsigned char byte;
 522
 523     do {
 524         i -= 8;
 525         byte = (unsigned char)(w >> i);
 526         if (fmt == NULL)
 527             fmt = byte ? "%X" : NULL;
 528         else
 529             fmt = "%02X";
 530
 531         if (fmt != NULL)
 532             BIO_printf(bp, fmt, byte);
 533     } while (i);
 534
 535     /* If we haven't printed anything, at least print a zero! */
 536     if (fmt == NULL)
 537         BIO_printf(bp, "0");
 538 }
 539
 540 int test_div_word(BIO *bp)
 541 {
 542     BIGNUM *a, *b;
 543     BN_ULONG r, s;
 544     int i;
 545
 546     a = BN_new();
 547     b = BN_new();
 548
 549     for (i = 0; i < num0; i++) {
 550         do {
 551             BN_bntest_rand(a, 512, -1, 0);
 552             BN_bntest_rand(b, BN_BITS2, -1, 0);
 553         } while (BN_is_zero(b));
 554
 555         s = b->d[0];
 556         BN_copy(b, a);
 557         r = BN_div_word(b, s);
 558
 559         if (bp != NULL) {
 560             if (!results) {
 561                 BN_print(bp, a);
 562                 BIO_puts(bp, " / ");
 563                 print_word(bp, s);
 564                 BIO_puts(bp, " - ");
 565             }
 566             BN_print(bp, b);
 567             BIO_puts(bp, "\n");
 568
 569             if (!results) {
 570                 BN_print(bp, a);
 571                 BIO_puts(bp, " % ");
 572                 print_word(bp, s);
 573                 BIO_puts(bp, " - ");
 574             }
 575             print_word(bp, r);
 576             BIO_puts(bp, "\n");
 577         }
 578         BN_mul_word(b, s);
 579         BN_add_word(b, r);
 580         BN_sub(b, a, b);
 581         if (!BN_is_zero(b)) {
 582             fprintf(stderr, "Division (word) test failed!\n");
 583             return 0;
 584         }
 585     }
 586     BN_free(a);
 587     BN_free(b);
 588     return (1);
 589 }
 590
 591 int test_div_recp(BIO *bp, BN_CTX *ctx)
 592 {
 593     BIGNUM *a, *b, *c, *d, *e;
 594     BN_RECP_CTX *recp;
 595     int i;
 596
 597     recp = BN_RECP_CTX_new();
 598     a = BN_new();
 599     b = BN_new();
 600     c = BN_new();
 601     d = BN_new();
 602     e = BN_new();
 603
 604     for (i = 0; i < num0 + num1; i++) {
 605         if (i < num1) {
 606             BN_bntest_rand(a, 400, 0, 0);
 607             BN_copy(b, a);
 608             BN_lshift(a, a, i);
 609             BN_add_word(a, i);
 610         } else
 611             BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0);
 612         a->neg = rand_neg();
 613         b->neg = rand_neg();
 614         BN_RECP_CTX_set(recp, b, ctx);
 615         BN_div_recp(d, c, a, recp, ctx);
 616         if (bp != NULL) {
 617             if (!results) {
 618                 BN_print(bp, a);
 619                 BIO_puts(bp, " / ");
 620                 BN_print(bp, b);
 621                 BIO_puts(bp, " - ");
 622             }
 623             BN_print(bp, d);
 624             BIO_puts(bp, "\n");
 625
 626             if (!results) {
 627                 BN_print(bp, a);
 628                 BIO_puts(bp, " % ");
 629                 BN_print(bp, b);
 630                 BIO_puts(bp, " - ");
 631             }
 632             BN_print(bp, c);
 633             BIO_puts(bp, "\n");
 634         }
 635         BN_mul(e, d, b, ctx);
 636         BN_add(d, e, c);
 637         BN_sub(d, d, a);
 638         if (!BN_is_zero(d)) {
 639             fprintf(stderr, "Reciprocal division test failed!\n");
 640             fprintf(stderr, "a=");
 641             BN_print_fp(stderr, a);
 642             fprintf(stderr, "\nb=");
 643             BN_print_fp(stderr, b);
 644             fprintf(stderr, "\n");
 645             return 0;
 646         }
 647     }
 648     BN_free(a);
 649     BN_free(b);
 650     BN_free(c);
 651     BN_free(d);
 652     BN_free(e);
 653     BN_RECP_CTX_free(recp);
 654     return (1);
 655 }
 656
 657 int test_mul(BIO *bp)
 658 {
 659     BIGNUM *a, *b, *c, *d, *e;
 660     int i;
 661     BN_CTX *ctx;
 662
 663     ctx = BN_CTX_new();
 664     if (ctx == NULL)
 665         EXIT(1);
 666
 667     a = BN_new();
 668     b = BN_new();
 669     c = BN_new();
 670     d = BN_new();
 671     e = BN_new();
 672
 673     for (i = 0; i < num0 + num1; i++) {
 674         if (i <= num1) {
 675             BN_bntest_rand(a, 100, 0, 0);
 676             BN_bntest_rand(b, 100, 0, 0);
 677         } else
 678             BN_bntest_rand(b, i - num1, 0, 0);
 679         a->neg = rand_neg();
 680         b->neg = rand_neg();
 681         BN_mul(c, a, b, ctx);
 682         if (bp != NULL) {
 683             if (!results) {
 684                 BN_print(bp, a);
 685                 BIO_puts(bp, " * ");
 686                 BN_print(bp, b);
 687                 BIO_puts(bp, " - ");
 688             }
 689             BN_print(bp, c);
 690             BIO_puts(bp, "\n");
 691         }
 692         BN_div(d, e, c, a, ctx);
 693         BN_sub(d, d, b);
 694         if (!BN_is_zero(d) || !BN_is_zero(e)) {
 695             fprintf(stderr, "Multiplication test failed!\n");
 696             return 0;
 697         }
 698     }
 699     BN_free(a);
 700     BN_free(b);
 701     BN_free(c);
 702     BN_free(d);
 703     BN_free(e);
 704     BN_CTX_free(ctx);
 705     return (1);
 706 }
 707
 708 int test_sqr(BIO *bp, BN_CTX *ctx)
 709 {
 710     BIGNUM *a, *c, *d, *e;
 711     int i, ret = 0;
 712
 713     a = BN_new();
 714     c = BN_new();
 715     d = BN_new();
 716     e = BN_new();
 717     if (a == NULL || c == NULL || d == NULL || e == NULL) {
 718         goto err;
 719     }
 720
 721     for (i = 0; i < num0; i++) {
 722         BN_bntest_rand(a, 40 + i * 10, 0, 0);
 723         a->neg = rand_neg();
 724         BN_sqr(c, a, ctx);
 725         if (bp != NULL) {
 726             if (!results) {
 727                 BN_print(bp, a);
 728                 BIO_puts(bp, " * ");
 729                 BN_print(bp, a);
 730                 BIO_puts(bp, " - ");
 731             }
 732             BN_print(bp, c);
 733             BIO_puts(bp, "\n");
 734         }
 735         BN_div(d, e, c, a, ctx);
 736         BN_sub(d, d, a);
 737         if (!BN_is_zero(d) || !BN_is_zero(e)) {
 738             fprintf(stderr, "Square test failed!\n");
 739             goto err;
 740         }
 741     }
 742
 743     /* Regression test for a BN_sqr overflow bug. */
 744     BN_hex2bn(&a,
 745               "80000000000000008000000000000001"
 746               "FFFFFFFFFFFFFFFE0000000000000000");
 747     BN_sqr(c, a, ctx);
 748     if (bp != NULL) {
 749         if (!results) {
 750             BN_print(bp, a);
 751             BIO_puts(bp, " * ");
 752             BN_print(bp, a);
 753             BIO_puts(bp, " - ");
 754         }
 755         BN_print(bp, c);
 756         BIO_puts(bp, "\n");
 757     }
 758     BN_mul(d, a, a, ctx);
 759     if (BN_cmp(c, d)) {
 760         fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce "
 761                 "different results!\n");
 762         goto err;
 763     }
 764
 765     /* Regression test for a BN_sqr overflow bug. */
 766     BN_hex2bn(&a,
 767               "80000000000000000000000080000001"
 768               "FFFFFFFE000000000000000000000000");
 769     BN_sqr(c, a, ctx);
 770     if (bp != NULL) {
 771         if (!results) {
 772             BN_print(bp, a);
 773             BIO_puts(bp, " * ");
 774             BN_print(bp, a);
 775             BIO_puts(bp, " - ");
 776         }
 777         BN_print(bp, c);
 778         BIO_puts(bp, "\n");
 779     }
 780     BN_mul(d, a, a, ctx);
 781     if (BN_cmp(c, d)) {
 782         fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce "
 783                 "different results!\n");
 784         goto err;
 785     }
 786     ret = 1;
 787  err:
 788     BN_free(a);
 789     BN_free(c);
 790     BN_free(d);
 791     BN_free(e);
 792     return ret;
 793 }
 794
 795 int test_mont(BIO *bp, BN_CTX *ctx)
 796 {
 797     BIGNUM *a, *b, *c, *d, *A, *B;
 798     BIGNUM *n;
 799     int i;
 800     BN_MONT_CTX *mont;
 801
 802     a = BN_new();
 803     b = BN_new();
 804     c = BN_new();
 805     d = BN_new();
 806     A = BN_new();
 807     B = BN_new();
 808     n = BN_new();
 809
 810     mont = BN_MONT_CTX_new();
 811     if (mont == NULL)
 812         return 0;
 813
 814     BN_zero(n);
 815     if (BN_MONT_CTX_set(mont, n, ctx)) {
 816         fprintf(stderr, "BN_MONT_CTX_set succeeded for zero modulus!\n");
 817         return 0;
 818     }
 819
 820     BN_set_word(n, 16);
 821     if (BN_MONT_CTX_set(mont, n, ctx)) {
 822         fprintf(stderr, "BN_MONT_CTX_set succeeded for even modulus!\n");
 823         return 0;
 824     }
 825
 826     BN_bntest_rand(a, 100, 0, 0);
 827     BN_bntest_rand(b, 100, 0, 0);
 828     for (i = 0; i < num2; i++) {
 829         int bits = (200 * (i + 1)) / num2;
 830
 831         if (bits == 0)
 832             continue;
 833         BN_bntest_rand(n, bits, 0, 1);
 834         BN_MONT_CTX_set(mont, n, ctx);
 835
 836         BN_nnmod(a, a, n, ctx);
 837         BN_nnmod(b, b, n, ctx);
 838
 839         BN_to_montgomery(A, a, mont, ctx);
 840         BN_to_montgomery(B, b, mont, ctx);
 841
 842         BN_mod_mul_montgomery(c, A, B, mont, ctx);
 843         BN_from_montgomery(A, c, mont, ctx);
 844         if (bp != NULL) {
 845             if (!results) {
 846                 BN_print(bp, a);
 847                 BIO_puts(bp, " * ");
 848                 BN_print(bp, b);
 849                 BIO_puts(bp, " % ");
 850                 BN_print(bp, &mont->N);
 851                 BIO_puts(bp, " - ");
 852             }
 853             BN_print(bp, A);
 854             BIO_puts(bp, "\n");
 855         }
 856         BN_mod_mul(d, a, b, n, ctx);
 857         BN_sub(d, d, A);
 858         if (!BN_is_zero(d)) {
 859             fprintf(stderr, "Montgomery multiplication test failed!\n");
 860             return 0;
 861         }
 862     }
 863     BN_MONT_CTX_free(mont);
 864     BN_free(a);
 865     BN_free(b);
 866     BN_free(c);
 867     BN_free(d);
 868     BN_free(A);
 869     BN_free(B);
 870     BN_free(n);
 871     return (1);
 872 }
 873
 874 int test_mod(BIO *bp, BN_CTX *ctx)
 875 {
 876     BIGNUM *a, *b, *c, *d, *e;
 877     int i;
 878
 879     a = BN_new();
 880     b = BN_new();
 881     c = BN_new();
 882     d = BN_new();
 883     e = BN_new();
 884
 885     BN_bntest_rand(a, 1024, 0, 0);
 886     for (i = 0; i < num0; i++) {
 887         BN_bntest_rand(b, 450 + i * 10, 0, 0);
 888         a->neg = rand_neg();
 889         b->neg = rand_neg();
 890         BN_mod(c, a, b, ctx);
 891         if (bp != NULL) {
 892             if (!results) {
 893                 BN_print(bp, a);
 894                 BIO_puts(bp, " % ");
 895                 BN_print(bp, b);
 896                 BIO_puts(bp, " - ");
 897             }
 898             BN_print(bp, c);
 899             BIO_puts(bp, "\n");
 900         }
 901         BN_div(d, e, a, b, ctx);
 902         BN_sub(e, e, c);
 903         if (!BN_is_zero(e)) {
 904             fprintf(stderr, "Modulo test failed!\n");
 905             return 0;
 906         }
 907     }
 908     BN_free(a);
 909     BN_free(b);
 910     BN_free(c);
 911     BN_free(d);
 912     BN_free(e);
 913     return (1);
 914 }
 915
 916 int test_mod_mul(BIO *bp, BN_CTX *ctx)
 917 {
 918     BIGNUM *a, *b, *c, *d, *e;
 919     int i, j;
 920
 921     a = BN_new();
 922     b = BN_new();
 923     c = BN_new();
 924     d = BN_new();
 925     e = BN_new();
 926
 927     BN_one(a);
 928     BN_one(b);
 929     BN_zero(c);
 930     if (BN_mod_mul(e, a, b, c, ctx)) {
 931         fprintf(stderr, "BN_mod_mul with zero modulus succeeded!\n");
 932         return 0;
 933     }
 934
 935     for (j = 0; j < 3; j++) {
 936         BN_bntest_rand(c, 1024, 0, 0);
 937         for (i = 0; i < num0; i++) {
 938             BN_bntest_rand(a, 475 + i * 10, 0, 0);
 939             BN_bntest_rand(b, 425 + i * 11, 0, 0);
 940             a->neg = rand_neg();
 941             b->neg = rand_neg();
 942             if (!BN_mod_mul(e, a, b, c, ctx)) {
 943                 unsigned long l;
 944
 945                 while ((l = ERR_get_error()))
 946                     fprintf(stderr, "ERROR:%s\n", ERR_error_string(l, NULL));
 947                 EXIT(1);
 948             }
 949             if (bp != NULL) {
 950                 if (!results) {
 951                     BN_print(bp, a);
 952                     BIO_puts(bp, " * ");
 953                     BN_print(bp, b);
 954                     BIO_puts(bp, " % ");
 955                     BN_print(bp, c);
 956                     if ((a->neg ^ b->neg) && !BN_is_zero(e)) {
 957                         /*
 958                          * If (a*b) % c is negative, c must be added in order
 959                          * to obtain the normalized remainder (new with
 960                          * OpenSSL 0.9.7, previous versions of BN_mod_mul
 961                          * could generate negative results)
 962                          */
 963                         BIO_puts(bp, " + ");
 964                         BN_print(bp, c);
 965                     }
 966                     BIO_puts(bp, " - ");
 967                 }
 968                 BN_print(bp, e);
 969                 BIO_puts(bp, "\n");
 970             }
 971             BN_mul(d, a, b, ctx);
 972             BN_sub(d, d, e);
 973             BN_div(a, b, d, c, ctx);
 974             if (!BN_is_zero(b)) {
 975                 fprintf(stderr, "Modulo multiply test failed!\n");
 976                 ERR_print_errors_fp(stderr);
 977                 return 0;
 978             }
 979         }
 980     }
 981     BN_free(a);
 982     BN_free(b);
 983     BN_free(c);
 984     BN_free(d);
 985     BN_free(e);
 986     return (1);
 987 }
 988
 989 int test_mod_exp(BIO *bp, BN_CTX *ctx)
 990 {
 991     BIGNUM *a, *b, *c, *d, *e;
 992     int i;
 993
 994     a = BN_new();
 995     b = BN_new();
 996     c = BN_new();
 997     d = BN_new();
 998     e = BN_new();
 999
1000     BN_one(a);
1001     BN_one(b);
1002     BN_zero(c);
1003     if (BN_mod_exp(d, a, b, c, ctx)) {
1004         fprintf(stderr, "BN_mod_exp with zero modulus succeeded!\n");
1005         return 0;
1006     }
1007
1008     BN_bntest_rand(c, 30, 0, 1); /* must be odd for montgomery */
1009     for (i = 0; i < num2; i++) {
1010         BN_bntest_rand(a, 20 + i * 5, 0, 0);
1011         BN_bntest_rand(b, 2 + i, 0, 0);
1012
1013         if (!BN_mod_exp(d, a, b, c, ctx))
1014             return (0);
1015
1016         if (bp != NULL) {
1017             if (!results) {
1018                 BN_print(bp, a);
1019                 BIO_puts(bp, " ^ ");
1020                 BN_print(bp, b);
1021                 BIO_puts(bp, " % ");
1022                 BN_print(bp, c);
1023                 BIO_puts(bp, " - ");
1024             }
1025             BN_print(bp, d);
1026             BIO_puts(bp, "\n");
1027         }
1028         BN_exp(e, a, b, ctx);
1029         BN_sub(e, e, d);
1030         BN_div(a, b, e, c, ctx);
1031         if (!BN_is_zero(b)) {
1032             fprintf(stderr, "Modulo exponentiation test failed!\n");
1033             return 0;
1034         }
1035     }
1036
1037     /* Regression test for carry propagation bug in sqr8x_reduction */
1038     BN_hex2bn(&a, "050505050505");
1039     BN_hex2bn(&b, "02");
1040     BN_hex2bn(&c,
1041         "4141414141414141414141274141414141414141414141414141414141414141"
1042         "4141414141414141414141414141414141414141414141414141414141414141"
1043         "4141414141414141414141800000000000000000000000000000000000000000"
1044         "0000000000000000000000000000000000000000000000000000000000000000"
1045         "0000000000000000000000000000000000000000000000000000000000000000"
1046         "0000000000000000000000000000000000000000000000000000000001");
1047     BN_mod_exp(d, a, b, c, ctx);
1048     BN_mul(e, a, a, ctx);
1049     if (BN_cmp(d, e)) {
1050         fprintf(stderr, "BN_mod_exp and BN_mul produce different results!\n");
1051         return 0;
1052     }
1053
1054     BN_free(a);
1055     BN_free(b);
1056     BN_free(c);
1057     BN_free(d);
1058     BN_free(e);
1059     return (1);
1060 }
1061
1062 int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx)
1063 {
1064     BIGNUM *a, *b, *c, *d, *e;
1065     int i;
1066
1067     a = BN_new();
1068     b = BN_new();
1069     c = BN_new();
1070     d = BN_new();
1071     e = BN_new();
1072
1073     BN_one(a);
1074     BN_one(b);
1075     BN_zero(c);
1076     if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1077         fprintf(stderr, "BN_mod_exp_mont_consttime with zero modulus "
1078                 "succeeded\n");
1079         return 0;
1080     }
1081
1082     BN_set_word(c, 16);
1083     if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1084         fprintf(stderr, "BN_mod_exp_mont_consttime with even modulus "
1085                 "succeeded\n");
1086         return 0;
1087     }
1088
1089     BN_bntest_rand(c, 30, 0, 1); /* must be odd for montgomery */
1090     for (i = 0; i < num2; i++) {
1091         BN_bntest_rand(a, 20 + i * 5, 0, 0);
1092         BN_bntest_rand(b, 2 + i, 0, 0);
1093
1094         if (!BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL))
1095             return (00);
1096
1097         if (bp != NULL) {
1098             if (!results) {
1099                 BN_print(bp, a);
1100                 BIO_puts(bp, " ^ ");
1101                 BN_print(bp, b);
1102                 BIO_puts(bp, " % ");
1103                 BN_print(bp, c);
1104                 BIO_puts(bp, " - ");
1105             }
1106             BN_print(bp, d);
1107             BIO_puts(bp, "\n");
1108         }
1109         BN_exp(e, a, b, ctx);
1110         BN_sub(e, e, d);
1111         BN_div(a, b, e, c, ctx);
1112         if (!BN_is_zero(b)) {
1113             fprintf(stderr, "Modulo exponentiation test failed!\n");
1114             return 0;
1115         }
1116     }
1117     BN_free(a);
1118     BN_free(b);
1119     BN_free(c);
1120     BN_free(d);
1121     BN_free(e);
1122     return (1);
1123 }
1124
1125 /*
1126  * Test constant-time modular exponentiation with 1024-bit inputs, which on
1127  * x86_64 cause a different code branch to be taken.
1128  */
1129 int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx)
1130 {
1131     BIGNUM *a, *p, *m, *d, *e;
1132     BN_MONT_CTX *mont;
1133
1134     a = BN_new();
1135     p = BN_new();
1136     m = BN_new();
1137     d = BN_new();
1138     e = BN_new();
1139     mont = BN_MONT_CTX_new();
1140
1141     BN_bntest_rand(m, 1024, 0, 1); /* must be odd for montgomery */
1142     /* Zero exponent */
1143     BN_bntest_rand(a, 1024, 0, 0);
1144     BN_zero(p);
1145     if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
1146         return 0;
1147     if (!BN_is_one(d)) {
1148         fprintf(stderr, "Modular exponentiation test failed!\n");
1149         return 0;
1150     }
1151     /* Zero input */
1152     BN_bntest_rand(p, 1024, 0, 0);
1153     BN_zero(a);
1154     if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
1155         return 0;
1156     if (!BN_is_zero(d)) {
1157         fprintf(stderr, "Modular exponentiation test failed!\n");
1158         return 0;
1159     }
1160     /*
1161      * Craft an input whose Montgomery representation is 1, i.e., shorter
1162      * than the modulus m, in order to test the const time precomputation
1163      * scattering/gathering.
1164      */
1165     BN_one(a);
1166     BN_MONT_CTX_set(mont, m, ctx);
1167     if (!BN_from_montgomery(e, a, mont, ctx))
1168         return 0;
1169     if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
1170         return 0;
1171     if (!BN_mod_exp_simple(a, e, p, m, ctx))
1172         return 0;
1173     if (BN_cmp(a, d) != 0) {
1174         fprintf(stderr, "Modular exponentiation test failed!\n");
1175         return 0;
1176     }
1177     /* Finally, some regular test vectors. */
1178     BN_bntest_rand(e, 1024, 0, 0);
1179     if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
1180         return 0;
1181     if (!BN_mod_exp_simple(a, e, p, m, ctx))
1182         return 0;
1183     if (BN_cmp(a, d) != 0) {
1184         fprintf(stderr, "Modular exponentiation test failed!\n");
1185         return 0;
1186     }
1187     BN_MONT_CTX_free(mont);
1188     BN_free(a);
1189     BN_free(p);
1190     BN_free(m);
1191     BN_free(d);
1192     BN_free(e);
1193     return (1);
1194 }
1195
1196 int test_exp(BIO *bp, BN_CTX *ctx)
1197 {
1198     BIGNUM *a, *b, *d, *e, *one;
1199     int i;
1200
1201     a = BN_new();
1202     b = BN_new();
1203     d = BN_new();
1204     e = BN_new();
1205     one = BN_new();
1206     BN_one(one);
1207
1208     for (i = 0; i < num2; i++) {
1209         BN_bntest_rand(a, 20 + i * 5, 0, 0);
1210         BN_bntest_rand(b, 2 + i, 0, 0);
1211
1212         if (BN_exp(d, a, b, ctx) <= 0)
1213             return (0);
1214
1215         if (bp != NULL) {
1216             if (!results) {
1217                 BN_print(bp, a);
1218                 BIO_puts(bp, " ^ ");
1219                 BN_print(bp, b);
1220                 BIO_puts(bp, " - ");
1221             }
1222             BN_print(bp, d);
1223             BIO_puts(bp, "\n");
1224         }
1225         BN_one(e);
1226         for (; !BN_is_zero(b); BN_sub(b, b, one))
1227             BN_mul(e, e, a, ctx);
1228         BN_sub(e, e, d);
1229         if (!BN_is_zero(e)) {
1230             fprintf(stderr, "Exponentiation test failed!\n");
1231             return 0;
1232         }
1233     }
1234     BN_free(a);
1235     BN_free(b);
1236     BN_free(d);
1237     BN_free(e);
1238     BN_free(one);
1239     return (1);
1240 }
1241
1242 #ifndef OPENSSL_NO_EC2M
1243 int test_gf2m_add(BIO *bp)
1244 {
1245     BIGNUM *a, *b, *c;
1246     int i, ret = 0;
1247
1248     a = BN_new();
1249     b = BN_new();
1250     c = BN_new();
1251
1252     for (i = 0; i < num0; i++) {
1253         BN_rand(a, 512, 0, 0);
1254         BN_copy(b, BN_value_one());
1255         a->neg = rand_neg();
1256         b->neg = rand_neg();
1257         BN_GF2m_add(c, a, b);
1258         /* Test that two added values have the correct parity. */
1259         if ((BN_is_odd(a) && BN_is_odd(c))
1260             || (!BN_is_odd(a) && !BN_is_odd(c))) {
1261             fprintf(stderr, "GF(2^m) addition test (a) failed!\n");
1262             goto err;
1263         }
1264         BN_GF2m_add(c, c, c);
1265         /* Test that c + c = 0. */
1266         if (!BN_is_zero(c)) {
1267             fprintf(stderr, "GF(2^m) addition test (b) failed!\n");
1268             goto err;
1269         }
1270     }
1271     ret = 1;
1272  err:
1273     BN_free(a);
1274     BN_free(b);
1275     BN_free(c);
1276     return ret;
1277 }
1278
1279 int test_gf2m_mod(BIO *bp)
1280 {
1281     BIGNUM *a, *b[2], *c, *d, *e;
1282     int i, j, ret = 0;
1283     int p0[] = { 163, 7, 6, 3, 0, -1 };
1284     int p1[] = { 193, 15, 0, -1 };
1285
1286     a = BN_new();
1287     b[0] = BN_new();
1288     b[1] = BN_new();
1289     c = BN_new();
1290     d = BN_new();
1291     e = BN_new();
1292
1293     BN_GF2m_arr2poly(p0, b[0]);
1294     BN_GF2m_arr2poly(p1, b[1]);
1295
1296     for (i = 0; i < num0; i++) {
1297         BN_bntest_rand(a, 1024, 0, 0);
1298         for (j = 0; j < 2; j++) {
1299             BN_GF2m_mod(c, a, b[j]);
1300             BN_GF2m_add(d, a, c);
1301             BN_GF2m_mod(e, d, b[j]);
1302             /* Test that a + (a mod p) mod p == 0. */
1303             if (!BN_is_zero(e)) {
1304                 fprintf(stderr, "GF(2^m) modulo test failed!\n");
1305                 goto err;
1306             }
1307         }
1308     }
1309     ret = 1;
1310  err:
1311     BN_free(a);
1312     BN_free(b[0]);
1313     BN_free(b[1]);
1314     BN_free(c);
1315     BN_free(d);
1316     BN_free(e);
1317     return ret;
1318 }
1319
1320 int test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx)
1321 {
1322     BIGNUM *a, *b[2], *c, *d, *e, *f, *g, *h;
1323     int i, j, ret = 0;
1324     int p0[] = { 163, 7, 6, 3, 0, -1 };
1325     int p1[] = { 193, 15, 0, -1 };
1326
1327     a = BN_new();
1328     b[0] = BN_new();
1329     b[1] = BN_new();
1330     c = BN_new();
1331     d = BN_new();
1332     e = BN_new();
1333     f = BN_new();
1334     g = BN_new();
1335     h = BN_new();
1336
1337     BN_GF2m_arr2poly(p0, b[0]);
1338     BN_GF2m_arr2poly(p1, b[1]);
1339
1340     for (i = 0; i < num0; i++) {
1341         BN_bntest_rand(a, 1024, 0, 0);
1342         BN_bntest_rand(c, 1024, 0, 0);
1343         BN_bntest_rand(d, 1024, 0, 0);
1344         for (j = 0; j < 2; j++) {
1345             BN_GF2m_mod_mul(e, a, c, b[j], ctx);
1346             BN_GF2m_add(f, a, d);
1347             BN_GF2m_mod_mul(g, f, c, b[j], ctx);
1348             BN_GF2m_mod_mul(h, d, c, b[j], ctx);
1349             BN_GF2m_add(f, e, g);
1350             BN_GF2m_add(f, f, h);
1351             /* Test that (a+d)*c = a*c + d*c. */
1352             if (!BN_is_zero(f)) {
1353                 fprintf(stderr,
1354                         "GF(2^m) modular multiplication test failed!\n");
1355                 goto err;
1356             }
1357         }
1358     }
1359     ret = 1;
1360  err:
1361     BN_free(a);
1362     BN_free(b[0]);
1363     BN_free(b[1]);
1364     BN_free(c);
1365     BN_free(d);
1366     BN_free(e);
1367     BN_free(f);
1368     BN_free(g);
1369     BN_free(h);
1370     return ret;
1371 }
1372
1373 int test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx)
1374 {
1375     BIGNUM *a, *b[2], *c, *d;
1376     int i, j, ret = 0;
1377     int p0[] = { 163, 7, 6, 3, 0, -1 };
1378     int p1[] = { 193, 15, 0, -1 };
1379
1380     a = BN_new();
1381     b[0] = BN_new();
1382     b[1] = BN_new();
1383     c = BN_new();
1384     d = BN_new();
1385
1386     BN_GF2m_arr2poly(p0, b[0]);
1387     BN_GF2m_arr2poly(p1, b[1]);
1388
1389     for (i = 0; i < num0; i++) {
1390         BN_bntest_rand(a, 1024, 0, 0);
1391         for (j = 0; j < 2; j++) {
1392             BN_GF2m_mod_sqr(c, a, b[j], ctx);
1393             BN_copy(d, a);
1394             BN_GF2m_mod_mul(d, a, d, b[j], ctx);
1395             BN_GF2m_add(d, c, d);
1396             /* Test that a*a = a^2. */
1397             if (!BN_is_zero(d)) {
1398                 fprintf(stderr, "GF(2^m) modular squaring test failed!\n");
1399                 goto err;
1400             }
1401         }
1402     }
1403     ret = 1;
1404  err:
1405     BN_free(a);
1406     BN_free(b[0]);
1407     BN_free(b[1]);
1408     BN_free(c);
1409     BN_free(d);
1410     return ret;
1411 }
1412
1413 int test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx)
1414 {
1415     BIGNUM *a, *b[2], *c, *d;
1416     int i, j, ret = 0;
1417     int p0[] = { 163, 7, 6, 3, 0, -1 };
1418     int p1[] = { 193, 15, 0, -1 };
1419
1420     a = BN_new();
1421     b[0] = BN_new();
1422     b[1] = BN_new();
1423     c = BN_new();
1424     d = BN_new();
1425
1426     BN_GF2m_arr2poly(p0, b[0]);
1427     BN_GF2m_arr2poly(p1, b[1]);
1428
1429     for (i = 0; i < num0; i++) {
1430         BN_bntest_rand(a, 512, 0, 0);
1431         for (j = 0; j < 2; j++) {
1432             BN_GF2m_mod_inv(c, a, b[j], ctx);
1433             BN_GF2m_mod_mul(d, a, c, b[j], ctx);
1434             /* Test that ((1/a)*a) = 1. */
1435             if (!BN_is_one(d)) {
1436                 fprintf(stderr, "GF(2^m) modular inversion test failed!\n");
1437                 goto err;
1438             }
1439         }
1440     }
1441     ret = 1;
1442  err:
1443     BN_free(a);
1444     BN_free(b[0]);
1445     BN_free(b[1]);
1446     BN_free(c);
1447     BN_free(d);
1448     return ret;
1449 }
1450
1451 int test_gf2m_mod_div(BIO *bp, BN_CTX *ctx)
1452 {
1453     BIGNUM *a, *b[2], *c, *d, *e, *f;
1454     int i, j, ret = 0;
1455     int p0[] = { 163, 7, 6, 3, 0, -1 };
1456     int p1[] = { 193, 15, 0, -1 };
1457
1458     a = BN_new();
1459     b[0] = BN_new();
1460     b[1] = BN_new();
1461     c = BN_new();
1462     d = BN_new();
1463     e = BN_new();
1464     f = BN_new();
1465
1466     BN_GF2m_arr2poly(p0, b[0]);
1467     BN_GF2m_arr2poly(p1, b[1]);
1468
1469     for (i = 0; i < num0; i++) {
1470         BN_bntest_rand(a, 512, 0, 0);
1471         BN_bntest_rand(c, 512, 0, 0);
1472         for (j = 0; j < 2; j++) {
1473             BN_GF2m_mod_div(d, a, c, b[j], ctx);
1474             BN_GF2m_mod_mul(e, d, c, b[j], ctx);
1475             BN_GF2m_mod_div(f, a, e, b[j], ctx);
1476             /* Test that ((a/c)*c)/a = 1. */
1477             if (!BN_is_one(f)) {
1478                 fprintf(stderr, "GF(2^m) modular division test failed!\n");
1479                 goto err;
1480             }
1481         }
1482     }
1483     ret = 1;
1484  err:
1485     BN_free(a);
1486     BN_free(b[0]);
1487     BN_free(b[1]);
1488     BN_free(c);
1489     BN_free(d);
1490     BN_free(e);
1491     BN_free(f);
1492     return ret;
1493 }
1494
1495 int test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx)
1496 {
1497     BIGNUM *a, *b[2], *c, *d, *e, *f;
1498     int i, j, ret = 0;
1499     int p0[] = { 163, 7, 6, 3, 0, -1 };
1500     int p1[] = { 193, 15, 0, -1 };
1501
1502     a = BN_new();
1503     b[0] = BN_new();
1504     b[1] = BN_new();
1505     c = BN_new();
1506     d = BN_new();
1507     e = BN_new();
1508     f = BN_new();
1509
1510     BN_GF2m_arr2poly(p0, b[0]);
1511     BN_GF2m_arr2poly(p1, b[1]);
1512
1513     for (i = 0; i < num0; i++) {
1514         BN_bntest_rand(a, 512, 0, 0);
1515         BN_bntest_rand(c, 512, 0, 0);
1516         BN_bntest_rand(d, 512, 0, 0);
1517         for (j = 0; j < 2; j++) {
1518             BN_GF2m_mod_exp(e, a, c, b[j], ctx);
1519             BN_GF2m_mod_exp(f, a, d, b[j], ctx);
1520             BN_GF2m_mod_mul(e, e, f, b[j], ctx);
1521             BN_add(f, c, d);
1522             BN_GF2m_mod_exp(f, a, f, b[j], ctx);
1523             BN_GF2m_add(f, e, f);
1524             /* Test that a^(c+d)=a^c*a^d. */
1525             if (!BN_is_zero(f)) {
1526                 fprintf(stderr,
1527                         "GF(2^m) modular exponentiation test failed!\n");
1528                 goto err;
1529             }
1530         }
1531     }
1532     ret = 1;
1533  err:
1534     BN_free(a);
1535     BN_free(b[0]);
1536     BN_free(b[1]);
1537     BN_free(c);
1538     BN_free(d);
1539     BN_free(e);
1540     BN_free(f);
1541     return ret;
1542 }
1543
1544 int test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx)
1545 {
1546     BIGNUM *a, *b[2], *c, *d, *e, *f;
1547     int i, j, ret = 0;
1548     int p0[] = { 163, 7, 6, 3, 0, -1 };
1549     int p1[] = { 193, 15, 0, -1 };
1550
1551     a = BN_new();
1552     b[0] = BN_new();
1553     b[1] = BN_new();
1554     c = BN_new();
1555     d = BN_new();
1556     e = BN_new();
1557     f = BN_new();
1558
1559     BN_GF2m_arr2poly(p0, b[0]);
1560     BN_GF2m_arr2poly(p1, b[1]);
1561
1562     for (i = 0; i < num0; i++) {
1563         BN_bntest_rand(a, 512, 0, 0);
1564         for (j = 0; j < 2; j++) {
1565             BN_GF2m_mod(c, a, b[j]);
1566             BN_GF2m_mod_sqrt(d, a, b[j], ctx);
1567             BN_GF2m_mod_sqr(e, d, b[j], ctx);
1568             BN_GF2m_add(f, c, e);
1569             /* Test that d^2 = a, where d = sqrt(a). */
1570             if (!BN_is_zero(f)) {
1571                 fprintf(stderr, "GF(2^m) modular square root test failed!\n");
1572                 goto err;
1573             }
1574         }
1575     }
1576     ret = 1;
1577  err:
1578     BN_free(a);
1579     BN_free(b[0]);
1580     BN_free(b[1]);
1581     BN_free(c);
1582     BN_free(d);
1583     BN_free(e);
1584     BN_free(f);
1585     return ret;
1586 }
1587
1588 int test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx)
1589 {
1590     BIGNUM *a, *b[2], *c, *d, *e;
1591     int i, j, s = 0, t, ret = 0;
1592     int p0[] = { 163, 7, 6, 3, 0, -1 };
1593     int p1[] = { 193, 15, 0, -1 };
1594
1595     a = BN_new();
1596     b[0] = BN_new();
1597     b[1] = BN_new();
1598     c = BN_new();
1599     d = BN_new();
1600     e = BN_new();
1601
1602     BN_GF2m_arr2poly(p0, b[0]);
1603     BN_GF2m_arr2poly(p1, b[1]);
1604
1605     for (i = 0; i < num0; i++) {
1606         BN_bntest_rand(a, 512, 0, 0);
1607         for (j = 0; j < 2; j++) {
1608             t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
1609             if (t) {
1610                 s++;
1611                 BN_GF2m_mod_sqr(d, c, b[j], ctx);
1612                 BN_GF2m_add(d, c, d);
1613                 BN_GF2m_mod(e, a, b[j]);
1614                 BN_GF2m_add(e, e, d);
1615                 /*
1616                  * Test that solution of quadratic c satisfies c^2 + c = a.
1617                  */
1618                 if (!BN_is_zero(e)) {
1619                     fprintf(stderr,
1620                             "GF(2^m) modular solve quadratic test failed!\n");
1621                     goto err;
1622                 }
1623
1624             }
1625         }
1626     }
1627     if (s == 0) {
1628         fprintf(stderr,
1629                 "All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n",
1630                 num0);
1631         fprintf(stderr,
1632                 "this is very unlikely and probably indicates an error.\n");
1633         goto err;
1634     }
1635     ret = 1;
1636  err:
1637     BN_free(a);
1638     BN_free(b[0]);
1639     BN_free(b[1]);
1640     BN_free(c);
1641     BN_free(d);
1642     BN_free(e);
1643     return ret;
1644 }
1645 #endif
1646 static int genprime_cb(int p, int n, BN_GENCB *arg)
1647 {
1648     char c = '*';
1649
1650     if (p == 0)
1651         c = '.';
1652     if (p == 1)
1653         c = '+';
1654     if (p == 2)
1655         c = '*';
1656     if (p == 3)
1657         c = '\n';
1658     putc(c, stderr);
1659     fflush(stderr);
1660     return 1;
1661 }
1662
1663 int test_kron(BIO *bp, BN_CTX *ctx)
1664 {
1665     BN_GENCB cb;
1666     BIGNUM *a, *b, *r, *t;
1667     int i;
1668     int legendre, kronecker;
1669     int ret = 0;
1670
1671     a = BN_new();
1672     b = BN_new();
1673     r = BN_new();
1674     t = BN_new();
1675     if (a == NULL || b == NULL || r == NULL || t == NULL)
1676         goto err;
1677
1678     BN_GENCB_set(&cb, genprime_cb, NULL);
1679
1680     /*
1681      * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
1682      * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
1683      * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
1684      * generate a random prime b and compare these values for a number of
1685      * random a's.  (That is, we run the Solovay-Strassen primality test to
1686      * confirm that b is prime, except that we don't want to test whether b
1687      * is prime but whether BN_kronecker works.)
1688      */
1689
1690     if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb))
1691         goto err;
1692     b->neg = rand_neg();
1693     putc('\n', stderr);
1694
1695     for (i = 0; i < num0; i++) {
1696         if (!BN_bntest_rand(a, 512, 0, 0))
1697             goto err;
1698         a->neg = rand_neg();
1699
1700         /* t := (|b|-1)/2  (note that b is odd) */
1701         if (!BN_copy(t, b))
1702             goto err;
1703         t->neg = 0;
1704         if (!BN_sub_word(t, 1))
1705             goto err;
1706         if (!BN_rshift1(t, t))
1707             goto err;
1708         /* r := a^t mod b */
1709         b->neg = 0;
1710
1711         if (!BN_mod_exp_recp(r, a, t, b, ctx))
1712             goto err;
1713         b->neg = 1;
1714
1715         if (BN_is_word(r, 1))
1716             legendre = 1;
1717         else if (BN_is_zero(r))
1718             legendre = 0;
1719         else {
1720             if (!BN_add_word(r, 1))
1721                 goto err;
1722             if (0 != BN_ucmp(r, b)) {
1723                 fprintf(stderr, "Legendre symbol computation failed\n");
1724                 goto err;
1725             }
1726             legendre = -1;
1727         }
1728
1729         kronecker = BN_kronecker(a, b, ctx);
1730         if (kronecker < -1)
1731             goto err;
1732         /* we actually need BN_kronecker(a, |b|) */
1733         if (a->neg && b->neg)
1734             kronecker = -kronecker;
1735
1736         if (legendre != kronecker) {
1737             fprintf(stderr, "legendre != kronecker; a = ");
1738             BN_print_fp(stderr, a);
1739             fprintf(stderr, ", b = ");
1740             BN_print_fp(stderr, b);
1741             fprintf(stderr, "\n");
1742             goto err;
1743         }
1744
1745         putc('.', stderr);
1746         fflush(stderr);
1747     }
1748
1749     putc('\n', stderr);
1750     fflush(stderr);
1751     ret = 1;
1752  err:
1753     BN_free(a);
1754     BN_free(b);
1755     BN_free(r);
1756     BN_free(t);
1757     return ret;
1758 }
1759
1760 int test_sqrt(BIO *bp, BN_CTX *ctx)
1761 {
1762     BN_GENCB cb;
1763     BIGNUM *a, *p, *r;
1764     int i, j;
1765     int ret = 0;
1766
1767     a = BN_new();
1768     p = BN_new();
1769     r = BN_new();
1770     if (a == NULL || p == NULL || r == NULL)
1771         goto err;
1772
1773     BN_GENCB_set(&cb, genprime_cb, NULL);
1774
1775     for (i = 0; i < 16; i++) {
1776         if (i < 8) {
1777             unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
1778
1779             if (!BN_set_word(p, primes[i]))
1780                 goto err;
1781         } else {
1782             if (!BN_set_word(a, 32))
1783                 goto err;
1784             if (!BN_set_word(r, 2 * i + 1))
1785                 goto err;
1786
1787             if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb))
1788                 goto err;
1789             putc('\n', stderr);
1790         }
1791         p->neg = rand_neg();
1792
1793         for (j = 0; j < num2; j++) {
1794             /*
1795              * construct 'a' such that it is a square modulo p, but in
1796              * general not a proper square and not reduced modulo p
1797              */
1798             if (!BN_bntest_rand(r, 256, 0, 3))
1799                 goto err;
1800             if (!BN_nnmod(r, r, p, ctx))
1801                 goto err;
1802             if (!BN_mod_sqr(r, r, p, ctx))
1803                 goto err;
1804             if (!BN_bntest_rand(a, 256, 0, 3))
1805                 goto err;
1806             if (!BN_nnmod(a, a, p, ctx))
1807                 goto err;
1808             if (!BN_mod_sqr(a, a, p, ctx))
1809                 goto err;
1810             if (!BN_mul(a, a, r, ctx))
1811                 goto err;
1812             if (rand_neg())
1813                 if (!BN_sub(a, a, p))
1814                     goto err;
1815
1816             if (!BN_mod_sqrt(r, a, p, ctx))
1817                 goto err;
1818             if (!BN_mod_sqr(r, r, p, ctx))
1819                 goto err;
1820
1821             if (!BN_nnmod(a, a, p, ctx))
1822                 goto err;
1823
1824             if (BN_cmp(a, r) != 0) {
1825                 fprintf(stderr, "BN_mod_sqrt failed: a = ");
1826                 BN_print_fp(stderr, a);
1827                 fprintf(stderr, ", r = ");
1828                 BN_print_fp(stderr, r);
1829                 fprintf(stderr, ", p = ");
1830                 BN_print_fp(stderr, p);
1831                 fprintf(stderr, "\n");
1832                 goto err;
1833             }
1834
1835             putc('.', stderr);
1836             fflush(stderr);
1837         }
1838
1839         putc('\n', stderr);
1840         fflush(stderr);
1841     }
1842     ret = 1;
1843  err:
1844     BN_free(a);
1845     BN_free(p);
1846     BN_free(r);
1847     return ret;
1848 }
1849
1850 int test_small_prime(BIO *bp, BN_CTX *ctx)
1851 {
1852     static const int bits = 10;
1853     int ret = 0;
1854     BIGNUM *r;
1855
1856     r = BN_new();
1857     if (!BN_generate_prime_ex(r, bits, 0, NULL, NULL, NULL))
1858         goto err;
1859     if (BN_num_bits(r) != bits) {
1860         BIO_printf(bp, "Expected %d bit prime, got %d bit number\n", bits,
1861                    BN_num_bits(r));
1862         goto err;
1863     }
1864
1865     ret = 1;
1866
1867  err:
1868     BN_clear_free(r);
1869     return ret;
1870 }
1871
1872 int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_)
1873 {
1874     BIGNUM *a, *b, *c, *d;
1875     int i;
1876
1877     b = BN_new();
1878     c = BN_new();
1879     d = BN_new();
1880     BN_one(c);
1881
1882     if (a_)
1883         a = a_;
1884     else {
1885         a = BN_new();
1886         BN_bntest_rand(a, 200, 0, 0);
1887         a->neg = rand_neg();
1888     }
1889     for (i = 0; i < num0; i++) {
1890         BN_lshift(b, a, i + 1);
1891         BN_add(c, c, c);
1892         if (bp != NULL) {
1893             if (!results) {
1894                 BN_print(bp, a);
1895                 BIO_puts(bp, " * ");
1896                 BN_print(bp, c);
1897                 BIO_puts(bp, " - ");
1898             }
1899             BN_print(bp, b);
1900             BIO_puts(bp, "\n");
1901         }
1902         BN_mul(d, a, c, ctx);
1903         BN_sub(d, d, b);
1904         if (!BN_is_zero(d)) {
1905             fprintf(stderr, "Left shift test failed!\n");
1906             fprintf(stderr, "a=");
1907             BN_print_fp(stderr, a);
1908             fprintf(stderr, "\nb=");
1909             BN_print_fp(stderr, b);
1910             fprintf(stderr, "\nc=");
1911             BN_print_fp(stderr, c);
1912             fprintf(stderr, "\nd=");
1913             BN_print_fp(stderr, d);
1914             fprintf(stderr, "\n");
1915             return 0;
1916         }
1917     }
1918     BN_free(a);
1919     BN_free(b);
1920     BN_free(c);
1921     BN_free(d);
1922     return (1);
1923 }
1924
1925 int test_lshift1(BIO *bp)
1926 {
1927     BIGNUM *a, *b, *c;
1928     int i;
1929
1930     a = BN_new();
1931     b = BN_new();
1932     c = BN_new();
1933
1934     BN_bntest_rand(a, 200, 0, 0);
1935     a->neg = rand_neg();
1936     for (i = 0; i < num0; i++) {
1937         BN_lshift1(b, a);
1938         if (bp != NULL) {
1939             if (!results) {
1940                 BN_print(bp, a);
1941                 BIO_puts(bp, " * 2");
1942                 BIO_puts(bp, " - ");
1943             }
1944             BN_print(bp, b);
1945             BIO_puts(bp, "\n");
1946         }
1947         BN_add(c, a, a);
1948         BN_sub(a, b, c);
1949         if (!BN_is_zero(a)) {
1950             fprintf(stderr, "Left shift one test failed!\n");
1951             return 0;
1952         }
1953
1954         BN_copy(a, b);
1955     }
1956     BN_free(a);
1957     BN_free(b);
1958     BN_free(c);
1959     return (1);
1960 }
1961
1962 int test_rshift(BIO *bp, BN_CTX *ctx)
1963 {
1964     BIGNUM *a, *b, *c, *d, *e;
1965     int i;
1966
1967     a = BN_new();
1968     b = BN_new();
1969     c = BN_new();
1970     d = BN_new();
1971     e = BN_new();
1972     BN_one(c);
1973
1974     BN_bntest_rand(a, 200, 0, 0);
1975     a->neg = rand_neg();
1976     for (i = 0; i < num0; i++) {
1977         BN_rshift(b, a, i + 1);
1978         BN_add(c, c, c);
1979         if (bp != NULL) {
1980             if (!results) {
1981                 BN_print(bp, a);
1982                 BIO_puts(bp, " / ");
1983                 BN_print(bp, c);
1984                 BIO_puts(bp, " - ");
1985             }
1986             BN_print(bp, b);
1987             BIO_puts(bp, "\n");
1988         }
1989         BN_div(d, e, a, c, ctx);
1990         BN_sub(d, d, b);
1991         if (!BN_is_zero(d)) {
1992             fprintf(stderr, "Right shift test failed!\n");
1993             return 0;
1994         }
1995     }
1996     BN_free(a);
1997     BN_free(b);
1998     BN_free(c);
1999     BN_free(d);
2000     BN_free(e);
2001     return (1);
2002 }
2003
2004 int test_rshift1(BIO *bp)
2005 {
2006     BIGNUM *a, *b, *c;
2007     int i;
2008
2009     a = BN_new();
2010     b = BN_new();
2011     c = BN_new();
2012
2013     BN_bntest_rand(a, 200, 0, 0);
2014     a->neg = rand_neg();
2015     for (i = 0; i < num0; i++) {
2016         BN_rshift1(b, a);
2017         if (bp != NULL) {
2018             if (!results) {
2019                 BN_print(bp, a);
2020                 BIO_puts(bp, " / 2");
2021                 BIO_puts(bp, " - ");
2022             }
2023             BN_print(bp, b);
2024             BIO_puts(bp, "\n");
2025         }
2026         BN_sub(c, a, b);
2027         BN_sub(c, c, b);
2028         if (!BN_is_zero(c) && !BN_abs_is_word(c, 1)) {
2029             fprintf(stderr, "Right shift one test failed!\n");
2030             return 0;
2031         }
2032         BN_copy(a, b);
2033     }
2034     BN_free(a);
2035     BN_free(b);
2036     BN_free(c);
2037     return (1);
2038 }
2039
2040 int rand_neg(void)
2041 {
2042     static unsigned int neg = 0;
2043     static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };
2044
2045     return (sign[(neg++) % 8]);
2046 }