crypto/openssl/crypto/bn/bntest.c

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