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