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, rmod, 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         rmod = BN_mod_word(&b, s);
 532         r = BN_div_word(&b, s);
 533
 534         if (rmod != r) {
 535             fprintf(stderr, "Mod (word) test failed!\n");
 536             return 0;
 537         }
 538
 539         if (bp != NULL) {
 540             if (!results) {
 541                 BN_print(bp, &a);
 542                 BIO_puts(bp, " / ");
 543                 print_word(bp, s);
 544                 BIO_puts(bp, " - ");
 545             }
 546             BN_print(bp, &b);
 547             BIO_puts(bp, "\n");
 548
 549             if (!results) {
 550                 BN_print(bp, &a);
 551                 BIO_puts(bp, " % ");
 552                 print_word(bp, s);
 553                 BIO_puts(bp, " - ");
 554             }
 555             print_word(bp, r);
 556             BIO_puts(bp, "\n");
 557         }
 558         BN_mul_word(&b, s);
 559         BN_add_word(&b, r);
 560         BN_sub(&b, &a, &b);
 561         if (!BN_is_zero(&b)) {
 562             fprintf(stderr, "Division (word) test failed!\n");
 563             return 0;
 564         }
 565     }
 566     BN_free(&a);
 567     BN_free(&b);
 568     return (1);
 569 }
 570
 571 int test_div_recp(BIO *bp, BN_CTX *ctx)
 572 {
 573     BIGNUM a, b, c, d, e;
 574     BN_RECP_CTX recp;
 575     int i;
 576
 577     BN_RECP_CTX_init(&recp);
 578     BN_init(&a);
 579     BN_init(&b);
 580     BN_init(&c);
 581     BN_init(&d);
 582     BN_init(&e);
 583
 584     for (i = 0; i < num0 + num1; i++) {
 585         if (i < num1) {
 586             BN_bntest_rand(&a, 400, 0, 0);
 587             BN_copy(&b, &a);
 588             BN_lshift(&a, &a, i);
 589             BN_add_word(&a, i);
 590         } else
 591             BN_bntest_rand(&b, 50 + 3 * (i - num1), 0, 0);
 592         a.neg = rand_neg();
 593         b.neg = rand_neg();
 594         BN_RECP_CTX_set(&recp, &b, ctx);
 595         BN_div_recp(&d, &c, &a, &recp, ctx);
 596         if (bp != NULL) {
 597             if (!results) {
 598                 BN_print(bp, &a);
 599                 BIO_puts(bp, " / ");
 600                 BN_print(bp, &b);
 601                 BIO_puts(bp, " - ");
 602             }
 603             BN_print(bp, &d);
 604             BIO_puts(bp, "\n");
 605
 606             if (!results) {
 607                 BN_print(bp, &a);
 608                 BIO_puts(bp, " % ");
 609                 BN_print(bp, &b);
 610                 BIO_puts(bp, " - ");
 611             }
 612             BN_print(bp, &c);
 613             BIO_puts(bp, "\n");
 614         }
 615         BN_mul(&e, &d, &b, ctx);
 616         BN_add(&d, &e, &c);
 617         BN_sub(&d, &d, &a);
 618         if (!BN_is_zero(&d)) {
 619             fprintf(stderr, "Reciprocal division test failed!\n");
 620             fprintf(stderr, "a=");
 621             BN_print_fp(stderr, &a);
 622             fprintf(stderr, "\nb=");
 623             BN_print_fp(stderr, &b);
 624             fprintf(stderr, "\n");
 625             return 0;
 626         }
 627     }
 628     BN_free(&a);
 629     BN_free(&b);
 630     BN_free(&c);
 631     BN_free(&d);
 632     BN_free(&e);
 633     BN_RECP_CTX_free(&recp);
 634     return (1);
 635 }
 636
 637 int test_mul(BIO *bp)
 638 {
 639     BIGNUM a, b, c, d, e;
 640     int i;
 641     BN_CTX *ctx;
 642
 643     ctx = BN_CTX_new();
 644     if (ctx == NULL)
 645         EXIT(1);
 646
 647     BN_init(&a);
 648     BN_init(&b);
 649     BN_init(&c);
 650     BN_init(&d);
 651     BN_init(&e);
 652
 653     for (i = 0; i < num0 + num1; i++) {
 654         if (i <= num1) {
 655             BN_bntest_rand(&a, 100, 0, 0);
 656             BN_bntest_rand(&b, 100, 0, 0);
 657         } else
 658             BN_bntest_rand(&b, i - num1, 0, 0);
 659         a.neg = rand_neg();
 660         b.neg = rand_neg();
 661         BN_mul(&c, &a, &b, ctx);
 662         if (bp != NULL) {
 663             if (!results) {
 664                 BN_print(bp, &a);
 665                 BIO_puts(bp, " * ");
 666                 BN_print(bp, &b);
 667                 BIO_puts(bp, " - ");
 668             }
 669             BN_print(bp, &c);
 670             BIO_puts(bp, "\n");
 671         }
 672         BN_div(&d, &e, &c, &a, ctx);
 673         BN_sub(&d, &d, &b);
 674         if (!BN_is_zero(&d) || !BN_is_zero(&e)) {
 675             fprintf(stderr, "Multiplication test failed!\n");
 676             return 0;
 677         }
 678     }
 679     BN_free(&a);
 680     BN_free(&b);
 681     BN_free(&c);
 682     BN_free(&d);
 683     BN_free(&e);
 684     BN_CTX_free(ctx);
 685     return (1);
 686 }
 687
 688 int test_sqr(BIO *bp, BN_CTX *ctx)
 689 {
 690     BIGNUM *a, *c, *d, *e;
 691     int i, ret = 0;
 692
 693     a = BN_new();
 694     c = BN_new();
 695     d = BN_new();
 696     e = BN_new();
 697     if (a == NULL || c == NULL || d == NULL || e == NULL) {
 698         goto err;
 699     }
 700
 701     for (i = 0; i < num0; i++) {
 702         BN_bntest_rand(a, 40 + i * 10, 0, 0);
 703         a->neg = rand_neg();
 704         BN_sqr(c, a, ctx);
 705         if (bp != NULL) {
 706             if (!results) {
 707                 BN_print(bp, a);
 708                 BIO_puts(bp, " * ");
 709                 BN_print(bp, a);
 710                 BIO_puts(bp, " - ");
 711             }
 712             BN_print(bp, c);
 713             BIO_puts(bp, "\n");
 714         }
 715         BN_div(d, e, c, a, ctx);
 716         BN_sub(d, d, a);
 717         if (!BN_is_zero(d) || !BN_is_zero(e)) {
 718             fprintf(stderr, "Square test failed!\n");
 719             goto err;
 720         }
 721     }
 722
 723     /* Regression test for a BN_sqr overflow bug. */
 724     BN_hex2bn(&a,
 725               "80000000000000008000000000000001"
 726               "FFFFFFFFFFFFFFFE0000000000000000");
 727     BN_sqr(c, a, ctx);
 728     if (bp != NULL) {
 729         if (!results) {
 730             BN_print(bp, a);
 731             BIO_puts(bp, " * ");
 732             BN_print(bp, a);
 733             BIO_puts(bp, " - ");
 734         }
 735         BN_print(bp, c);
 736         BIO_puts(bp, "\n");
 737     }
 738     BN_mul(d, a, a, ctx);
 739     if (BN_cmp(c, d)) {
 740         fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce "
 741                 "different results!\n");
 742         goto err;
 743     }
 744
 745     /* Regression test for a BN_sqr overflow bug. */
 746     BN_hex2bn(&a,
 747               "80000000000000000000000080000001"
 748               "FFFFFFFE000000000000000000000000");
 749     BN_sqr(c, a, ctx);
 750     if (bp != NULL) {
 751         if (!results) {
 752             BN_print(bp, a);
 753             BIO_puts(bp, " * ");
 754             BN_print(bp, a);
 755             BIO_puts(bp, " - ");
 756         }
 757         BN_print(bp, c);
 758         BIO_puts(bp, "\n");
 759     }
 760     BN_mul(d, a, a, ctx);
 761     if (BN_cmp(c, d)) {
 762         fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce "
 763                 "different results!\n");
 764         goto err;
 765     }
 766     ret = 1;
 767  err:
 768     if (a != NULL)
 769         BN_free(a);
 770     if (c != NULL)
 771         BN_free(c);
 772     if (d != NULL)
 773         BN_free(d);
 774     if (e != NULL)
 775         BN_free(e);
 776     return ret;
 777 }
 778
 779 int test_mont(BIO *bp, BN_CTX *ctx)
 780 {
 781     BIGNUM a, b, c, d, A, B;
 782     BIGNUM n;
 783     int i;
 784     BN_MONT_CTX *mont;
 785
 786     BN_init(&a);
 787     BN_init(&b);
 788     BN_init(&c);
 789     BN_init(&d);
 790     BN_init(&A);
 791     BN_init(&B);
 792     BN_init(&n);
 793
 794     mont = BN_MONT_CTX_new();
 795     if (mont == NULL)
 796         return 0;
 797
 798     BN_zero(&n);
 799     if (BN_MONT_CTX_set(mont, &n, ctx)) {
 800         fprintf(stderr, "BN_MONT_CTX_set succeeded for zero modulus!\n");
 801         return 0;
 802     }
 803
 804     BN_set_word(&n, 16);
 805     if (BN_MONT_CTX_set(mont, &n, ctx)) {
 806         fprintf(stderr, "BN_MONT_CTX_set succeeded for even modulus!\n");
 807         return 0;
 808     }
 809
 810     BN_bntest_rand(&a, 100, 0, 0);
 811     BN_bntest_rand(&b, 100, 0, 0);
 812     for (i = 0; i < num2; i++) {
 813         int bits = (200 * (i + 1)) / num2;
 814
 815         if (bits == 0)
 816             continue;
 817         BN_bntest_rand(&n, bits, 0, 1);
 818         BN_MONT_CTX_set(mont, &n, ctx);
 819
 820         BN_nnmod(&a, &a, &n, ctx);
 821         BN_nnmod(&b, &b, &n, ctx);
 822
 823         BN_to_montgomery(&A, &a, mont, ctx);
 824         BN_to_montgomery(&B, &b, mont, ctx);
 825
 826         BN_mod_mul_montgomery(&c, &A, &B, mont, ctx);
 827         BN_from_montgomery(&A, &c, mont, ctx);
 828         if (bp != NULL) {
 829             if (!results) {
 830 #ifdef undef
 831                 fprintf(stderr, "%d * %d %% %d\n",
 832                         BN_num_bits(&a),
 833                         BN_num_bits(&b), BN_num_bits(mont->N));
 834 #endif
 835                 BN_print(bp, &a);
 836                 BIO_puts(bp, " * ");
 837                 BN_print(bp, &b);
 838                 BIO_puts(bp, " % ");
 839                 BN_print(bp, &(mont->N));
 840                 BIO_puts(bp, " - ");
 841             }
 842             BN_print(bp, &A);
 843             BIO_puts(bp, "\n");
 844         }
 845         BN_mod_mul(&d, &a, &b, &n, ctx);
 846         BN_sub(&d, &d, &A);
 847         if (!BN_is_zero(&d)) {
 848             fprintf(stderr, "Montgomery multiplication test failed!\n");
 849             return 0;
 850         }
 851     }
 852     BN_MONT_CTX_free(mont);
 853     BN_free(&a);
 854     BN_free(&b);
 855     BN_free(&c);
 856     BN_free(&d);
 857     BN_free(&A);
 858     BN_free(&B);
 859     BN_free(&n);
 860     return (1);
 861 }
 862
 863 int test_mod(BIO *bp, BN_CTX *ctx)
 864 {
 865     BIGNUM *a, *b, *c, *d, *e;
 866     int i;
 867
 868     a = BN_new();
 869     b = BN_new();
 870     c = BN_new();
 871     d = BN_new();
 872     e = BN_new();
 873
 874     BN_bntest_rand(a, 1024, 0, 0);
 875     for (i = 0; i < num0; i++) {
 876         BN_bntest_rand(b, 450 + i * 10, 0, 0);
 877         a->neg = rand_neg();
 878         b->neg = rand_neg();
 879         BN_mod(c, a, b, ctx);
 880         if (bp != NULL) {
 881             if (!results) {
 882                 BN_print(bp, a);
 883                 BIO_puts(bp, " % ");
 884                 BN_print(bp, b);
 885                 BIO_puts(bp, " - ");
 886             }
 887             BN_print(bp, c);
 888             BIO_puts(bp, "\n");
 889         }
 890         BN_div(d, e, a, b, ctx);
 891         BN_sub(e, e, c);
 892         if (!BN_is_zero(e)) {
 893             fprintf(stderr, "Modulo test failed!\n");
 894             return 0;
 895         }
 896     }
 897     BN_free(a);
 898     BN_free(b);
 899     BN_free(c);
 900     BN_free(d);
 901     BN_free(e);
 902     return (1);
 903 }
 904
 905 int test_mod_mul(BIO *bp, BN_CTX *ctx)
 906 {
 907     BIGNUM *a, *b, *c, *d, *e;
 908     int i, j;
 909
 910     a = BN_new();
 911     b = BN_new();
 912     c = BN_new();
 913     d = BN_new();
 914     e = BN_new();
 915
 916     BN_one(a);
 917     BN_one(b);
 918     BN_zero(c);
 919     if (BN_mod_mul(e, a, b, c, ctx)) {
 920         fprintf(stderr, "BN_mod_mul with zero modulus succeeded!\n");
 921         return 0;
 922     }
 923
 924     for (j = 0; j < 3; j++) {
 925         BN_bntest_rand(c, 1024, 0, 0);
 926         for (i = 0; i < num0; i++) {
 927             BN_bntest_rand(a, 475 + i * 10, 0, 0);
 928             BN_bntest_rand(b, 425 + i * 11, 0, 0);
 929             a->neg = rand_neg();
 930             b->neg = rand_neg();
 931             if (!BN_mod_mul(e, a, b, c, ctx)) {
 932                 unsigned long l;
 933
 934                 while ((l = ERR_get_error()))
 935                     fprintf(stderr, "ERROR:%s\n", ERR_error_string(l, NULL));
 936                 EXIT(1);
 937             }
 938             if (bp != NULL) {
 939                 if (!results) {
 940                     BN_print(bp, a);
 941                     BIO_puts(bp, " * ");
 942                     BN_print(bp, b);
 943                     BIO_puts(bp, " % ");
 944                     BN_print(bp, c);
 945                     if ((a->neg ^ b->neg) && !BN_is_zero(e)) {
 946                         /*
 947                          * If (a*b) % c is negative, c must be added in order
 948                          * to obtain the normalized remainder (new with
 949                          * OpenSSL 0.9.7, previous versions of BN_mod_mul
 950                          * could generate negative results)
 951                          */
 952                         BIO_puts(bp, " + ");
 953                         BN_print(bp, c);
 954                     }
 955                     BIO_puts(bp, " - ");
 956                 }
 957                 BN_print(bp, e);
 958                 BIO_puts(bp, "\n");
 959             }
 960             BN_mul(d, a, b, ctx);
 961             BN_sub(d, d, e);
 962             BN_div(a, b, d, c, ctx);
 963             if (!BN_is_zero(b)) {
 964                 fprintf(stderr, "Modulo multiply test failed!\n");
 965                 ERR_print_errors_fp(stderr);
 966                 return 0;
 967             }
 968         }
 969     }
 970     BN_free(a);
 971     BN_free(b);
 972     BN_free(c);
 973     BN_free(d);
 974     BN_free(e);
 975     return (1);
 976 }
 977
 978 int test_mod_exp(BIO *bp, BN_CTX *ctx)
 979 {
 980     BIGNUM *a, *b, *c, *d, *e;
 981     int i;
 982
 983     a = BN_new();
 984     b = BN_new();
 985     c = BN_new();
 986     d = BN_new();
 987     e = BN_new();
 988
 989     BN_one(a);
 990     BN_one(b);
 991     BN_zero(c);
 992     if (BN_mod_exp(d, a, b, c, ctx)) {
 993         fprintf(stderr, "BN_mod_exp with zero modulus succeeded!\n");
 994         return 0;
 995     }
 996
 997     BN_bntest_rand(c, 30, 0, 1); /* must be odd for montgomery */
 998     for (i = 0; i < num2; i++) {
 999         BN_bntest_rand(a, 20 + i * 5, 0, 0);
1000         BN_bntest_rand(b, 2 + i, 0, 0);
1001
1002         if (!BN_mod_exp(d, a, b, c, ctx))
1003             return (0);
1004
1005         if (bp != NULL) {
1006             if (!results) {
1007                 BN_print(bp, a);
1008                 BIO_puts(bp, " ^ ");
1009                 BN_print(bp, b);
1010                 BIO_puts(bp, " % ");
1011                 BN_print(bp, c);
1012                 BIO_puts(bp, " - ");
1013             }
1014             BN_print(bp, d);
1015             BIO_puts(bp, "\n");
1016         }
1017         BN_exp(e, a, b, ctx);
1018         BN_sub(e, e, d);
1019         BN_div(a, b, e, c, ctx);
1020         if (!BN_is_zero(b)) {
1021             fprintf(stderr, "Modulo exponentiation test failed!\n");
1022             return 0;
1023         }
1024     }
1025
1026     /* Regression test for carry propagation bug in sqr8x_reduction */
1027     BN_hex2bn(&a, "050505050505");
1028     BN_hex2bn(&b, "02");
1029     BN_hex2bn(&c,
1030         "4141414141414141414141274141414141414141414141414141414141414141"
1031         "4141414141414141414141414141414141414141414141414141414141414141"
1032         "4141414141414141414141800000000000000000000000000000000000000000"
1033         "0000000000000000000000000000000000000000000000000000000000000000"
1034         "0000000000000000000000000000000000000000000000000000000000000000"
1035         "0000000000000000000000000000000000000000000000000000000001");
1036     BN_mod_exp(d, a, b, c, ctx);
1037     BN_mul(e, a, a, ctx);
1038     if (BN_cmp(d, e)) {
1039         fprintf(stderr, "BN_mod_exp and BN_mul produce different results!\n");
1040         return 0;
1041     }
1042
1043     BN_free(a);
1044     BN_free(b);
1045     BN_free(c);
1046     BN_free(d);
1047     BN_free(e);
1048     return (1);
1049 }
1050
1051 int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx)
1052 {
1053     BIGNUM *a, *b, *c, *d, *e;
1054     int i;
1055
1056     a = BN_new();
1057     b = BN_new();
1058     c = BN_new();
1059     d = BN_new();
1060     e = BN_new();
1061
1062     BN_one(a);
1063     BN_one(b);
1064     BN_zero(c);
1065     if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1066         fprintf(stderr, "BN_mod_exp_mont_consttime with zero modulus "
1067                 "succeeded\n");
1068         return 0;
1069     }
1070
1071     BN_set_word(c, 16);
1072     if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1073         fprintf(stderr, "BN_mod_exp_mont_consttime with even modulus "
1074                 "succeeded\n");
1075         return 0;
1076     }
1077
1078     BN_bntest_rand(c, 30, 0, 1); /* must be odd for montgomery */
1079     for (i = 0; i < num2; i++) {
1080         BN_bntest_rand(a, 20 + i * 5, 0, 0);
1081         BN_bntest_rand(b, 2 + i, 0, 0);
1082
1083         if (!BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL))
1084             return (00);
1085
1086         if (bp != NULL) {
1087             if (!results) {
1088                 BN_print(bp, a);
1089                 BIO_puts(bp, " ^ ");
1090                 BN_print(bp, b);
1091                 BIO_puts(bp, " % ");
1092                 BN_print(bp, c);
1093                 BIO_puts(bp, " - ");
1094             }
1095             BN_print(bp, d);
1096             BIO_puts(bp, "\n");
1097         }
1098         BN_exp(e, a, b, ctx);
1099         BN_sub(e, e, d);
1100         BN_div(a, b, e, c, ctx);
1101         if (!BN_is_zero(b)) {
1102             fprintf(stderr, "Modulo exponentiation test failed!\n");
1103             return 0;
1104         }
1105     }
1106     BN_free(a);
1107     BN_free(b);
1108     BN_free(c);
1109     BN_free(d);
1110     BN_free(e);
1111     return (1);
1112 }
1113
1114 /*
1115  * Test constant-time modular exponentiation with 1024-bit inputs, which on
1116  * x86_64 cause a different code branch to be taken.
1117  */
1118 int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx)
1119 {
1120     BIGNUM *a, *p, *m, *d, *e;
1121     BN_MONT_CTX *mont;
1122
1123     a = BN_new();
1124     p = BN_new();
1125     m = BN_new();
1126     d = BN_new();
1127     e = BN_new();
1128     mont = BN_MONT_CTX_new();
1129
1130     BN_bntest_rand(m, 1024, 0, 1); /* must be odd for montgomery */
1131     /* Zero exponent */
1132     BN_bntest_rand(a, 1024, 0, 0);
1133     BN_zero(p);
1134     if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
1135         return 0;
1136     if (!BN_is_one(d)) {
1137         fprintf(stderr, "Modular exponentiation test failed!\n");
1138         return 0;
1139     }
1140     /* Zero input */
1141     BN_bntest_rand(p, 1024, 0, 0);
1142     BN_zero(a);
1143     if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
1144         return 0;
1145     if (!BN_is_zero(d)) {
1146         fprintf(stderr, "Modular exponentiation test failed!\n");
1147         return 0;
1148     }
1149     /*
1150      * Craft an input whose Montgomery representation is 1, i.e., shorter
1151      * than the modulus m, in order to test the const time precomputation
1152      * scattering/gathering.
1153      */
1154     BN_one(a);
1155     BN_MONT_CTX_set(mont, m, ctx);
1156     if (!BN_from_montgomery(e, a, mont, ctx))
1157         return 0;
1158     if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
1159         return 0;
1160     if (!BN_mod_exp_simple(a, e, p, m, ctx))
1161         return 0;
1162     if (BN_cmp(a, d) != 0) {
1163         fprintf(stderr, "Modular exponentiation test failed!\n");
1164         return 0;
1165     }
1166     /* Finally, some regular test vectors. */
1167     BN_bntest_rand(e, 1024, 0, 0);
1168     if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
1169         return 0;
1170     if (!BN_mod_exp_simple(a, e, p, m, ctx))
1171         return 0;
1172     if (BN_cmp(a, d) != 0) {
1173         fprintf(stderr, "Modular exponentiation test failed!\n");
1174         return 0;
1175     }
1176     BN_MONT_CTX_free(mont);
1177     BN_free(a);
1178     BN_free(p);
1179     BN_free(m);
1180     BN_free(d);
1181     BN_free(e);
1182     return (1);
1183 }
1184
1185 int test_exp(BIO *bp, BN_CTX *ctx)
1186 {
1187     BIGNUM *a, *b, *d, *e, *one;
1188     int i;
1189
1190     a = BN_new();
1191     b = BN_new();
1192     d = BN_new();
1193     e = BN_new();
1194     one = BN_new();
1195     BN_one(one);
1196
1197     for (i = 0; i < num2; i++) {
1198         BN_bntest_rand(a, 20 + i * 5, 0, 0);
1199         BN_bntest_rand(b, 2 + i, 0, 0);
1200
1201         if (BN_exp(d, a, b, ctx) <= 0)
1202             return (0);
1203
1204         if (bp != NULL) {
1205             if (!results) {
1206                 BN_print(bp, a);
1207                 BIO_puts(bp, " ^ ");
1208                 BN_print(bp, b);
1209                 BIO_puts(bp, " - ");
1210             }
1211             BN_print(bp, d);
1212             BIO_puts(bp, "\n");
1213         }
1214         BN_one(e);
1215         for (; !BN_is_zero(b); BN_sub(b, b, one))
1216             BN_mul(e, e, a, ctx);
1217         BN_sub(e, e, d);
1218         if (!BN_is_zero(e)) {
1219             fprintf(stderr, "Exponentiation test failed!\n");
1220             return 0;
1221         }
1222     }
1223     BN_free(a);
1224     BN_free(b);
1225     BN_free(d);
1226     BN_free(e);
1227     BN_free(one);
1228     return (1);
1229 }
1230
1231 #ifndef OPENSSL_NO_EC2M
1232 int test_gf2m_add(BIO *bp)
1233 {
1234     BIGNUM a, b, c;
1235     int i, ret = 0;
1236
1237     BN_init(&a);
1238     BN_init(&b);
1239     BN_init(&c);
1240
1241     for (i = 0; i < num0; i++) {
1242         BN_rand(&a, 512, 0, 0);
1243         BN_copy(&b, BN_value_one());
1244         a.neg = rand_neg();
1245         b.neg = rand_neg();
1246         BN_GF2m_add(&c, &a, &b);
1247 # if 0                          /* make test uses ouput in bc but bc can't
1248                                  * handle GF(2^m) arithmetic */
1249         if (bp != NULL) {
1250             if (!results) {
1251                 BN_print(bp, &a);
1252                 BIO_puts(bp, " ^ ");
1253                 BN_print(bp, &b);
1254                 BIO_puts(bp, " = ");
1255             }
1256             BN_print(bp, &c);
1257             BIO_puts(bp, "\n");
1258         }
1259 # endif
1260         /* Test that two added values have the correct parity. */
1261         if ((BN_is_odd(&a) && BN_is_odd(&c))
1262             || (!BN_is_odd(&a) && !BN_is_odd(&c))) {
1263             fprintf(stderr, "GF(2^m) addition test (a) failed!\n");
1264             goto err;
1265         }
1266         BN_GF2m_add(&c, &c, &c);
1267         /* Test that c + c = 0. */
1268         if (!BN_is_zero(&c)) {
1269             fprintf(stderr, "GF(2^m) addition test (b) failed!\n");
1270             goto err;
1271         }
1272     }
1273     ret = 1;
1274  err:
1275     BN_free(&a);
1276     BN_free(&b);
1277     BN_free(&c);
1278     return ret;
1279 }
1280
1281 int test_gf2m_mod(BIO *bp)
1282 {
1283     BIGNUM *a, *b[2], *c, *d, *e;
1284     int i, j, ret = 0;
1285     int p0[] = { 163, 7, 6, 3, 0, -1 };
1286     int p1[] = { 193, 15, 0, -1 };
1287
1288     a = BN_new();
1289     b[0] = BN_new();
1290     b[1] = BN_new();
1291     c = BN_new();
1292     d = BN_new();
1293     e = BN_new();
1294
1295     BN_GF2m_arr2poly(p0, b[0]);
1296     BN_GF2m_arr2poly(p1, b[1]);
1297
1298     for (i = 0; i < num0; i++) {
1299         BN_bntest_rand(a, 1024, 0, 0);
1300         for (j = 0; j < 2; j++) {
1301             BN_GF2m_mod(c, a, b[j]);
1302 # if 0                          /* make test uses ouput in bc but bc can't
1303                                  * handle GF(2^m) arithmetic */
1304             if (bp != NULL) {
1305                 if (!results) {
1306                     BN_print(bp, a);
1307                     BIO_puts(bp, " % ");
1308                     BN_print(bp, b[j]);
1309                     BIO_puts(bp, " - ");
1310                     BN_print(bp, c);
1311                     BIO_puts(bp, "\n");
1312                 }
1313             }
1314 # endif
1315             BN_GF2m_add(d, a, c);
1316             BN_GF2m_mod(e, d, b[j]);
1317             /* Test that a + (a mod p) mod p == 0. */
1318             if (!BN_is_zero(e)) {
1319                 fprintf(stderr, "GF(2^m) modulo test failed!\n");
1320                 goto err;
1321             }
1322         }
1323     }
1324     ret = 1;
1325  err:
1326     BN_free(a);
1327     BN_free(b[0]);
1328     BN_free(b[1]);
1329     BN_free(c);
1330     BN_free(d);
1331     BN_free(e);
1332     return ret;
1333 }
1334
1335 int test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx)
1336 {
1337     BIGNUM *a, *b[2], *c, *d, *e, *f, *g, *h;
1338     int i, j, ret = 0;
1339     int p0[] = { 163, 7, 6, 3, 0, -1 };
1340     int p1[] = { 193, 15, 0, -1 };
1341
1342     a = BN_new();
1343     b[0] = BN_new();
1344     b[1] = BN_new();
1345     c = BN_new();
1346     d = BN_new();
1347     e = BN_new();
1348     f = BN_new();
1349     g = BN_new();
1350     h = BN_new();
1351
1352     BN_GF2m_arr2poly(p0, b[0]);
1353     BN_GF2m_arr2poly(p1, b[1]);
1354
1355     for (i = 0; i < num0; i++) {
1356         BN_bntest_rand(a, 1024, 0, 0);
1357         BN_bntest_rand(c, 1024, 0, 0);
1358         BN_bntest_rand(d, 1024, 0, 0);
1359         for (j = 0; j < 2; j++) {
1360             BN_GF2m_mod_mul(e, a, c, b[j], ctx);
1361 # if 0                          /* make test uses ouput in bc but bc can't
1362                                  * handle GF(2^m) arithmetic */
1363             if (bp != NULL) {
1364                 if (!results) {
1365                     BN_print(bp, a);
1366                     BIO_puts(bp, " * ");
1367                     BN_print(bp, c);
1368                     BIO_puts(bp, " % ");
1369                     BN_print(bp, b[j]);
1370                     BIO_puts(bp, " - ");
1371                     BN_print(bp, e);
1372                     BIO_puts(bp, "\n");
1373                 }
1374             }
1375 # endif
1376             BN_GF2m_add(f, a, d);
1377             BN_GF2m_mod_mul(g, f, c, b[j], ctx);
1378             BN_GF2m_mod_mul(h, d, c, b[j], ctx);
1379             BN_GF2m_add(f, e, g);
1380             BN_GF2m_add(f, f, h);
1381             /* Test that (a+d)*c = a*c + d*c. */
1382             if (!BN_is_zero(f)) {
1383                 fprintf(stderr,
1384                         "GF(2^m) modular multiplication test failed!\n");
1385                 goto err;
1386             }
1387         }
1388     }
1389     ret = 1;
1390  err:
1391     BN_free(a);
1392     BN_free(b[0]);
1393     BN_free(b[1]);
1394     BN_free(c);
1395     BN_free(d);
1396     BN_free(e);
1397     BN_free(f);
1398     BN_free(g);
1399     BN_free(h);
1400     return ret;
1401 }
1402
1403 int test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx)
1404 {
1405     BIGNUM *a, *b[2], *c, *d;
1406     int i, j, ret = 0;
1407     int p0[] = { 163, 7, 6, 3, 0, -1 };
1408     int p1[] = { 193, 15, 0, -1 };
1409
1410     a = BN_new();
1411     b[0] = BN_new();
1412     b[1] = BN_new();
1413     c = BN_new();
1414     d = BN_new();
1415
1416     BN_GF2m_arr2poly(p0, b[0]);
1417     BN_GF2m_arr2poly(p1, b[1]);
1418
1419     for (i = 0; i < num0; i++) {
1420         BN_bntest_rand(a, 1024, 0, 0);
1421         for (j = 0; j < 2; j++) {
1422             BN_GF2m_mod_sqr(c, a, b[j], ctx);
1423             BN_copy(d, a);
1424             BN_GF2m_mod_mul(d, a, d, b[j], ctx);
1425 # if 0                          /* make test uses ouput in bc but bc can't
1426                                  * handle GF(2^m) arithmetic */
1427             if (bp != NULL) {
1428                 if (!results) {
1429                     BN_print(bp, a);
1430                     BIO_puts(bp, " ^ 2 % ");
1431                     BN_print(bp, b[j]);
1432                     BIO_puts(bp, " = ");
1433                     BN_print(bp, c);
1434                     BIO_puts(bp, "; a * a = ");
1435                     BN_print(bp, d);
1436                     BIO_puts(bp, "\n");
1437                 }
1438             }
1439 # endif
1440             BN_GF2m_add(d, c, d);
1441             /* Test that a*a = a^2. */
1442             if (!BN_is_zero(d)) {
1443                 fprintf(stderr, "GF(2^m) modular squaring test failed!\n");
1444                 goto err;
1445             }
1446         }
1447     }
1448     ret = 1;
1449  err:
1450     BN_free(a);
1451     BN_free(b[0]);
1452     BN_free(b[1]);
1453     BN_free(c);
1454     BN_free(d);
1455     return ret;
1456 }
1457
1458 int test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx)
1459 {
1460     BIGNUM *a, *b[2], *c, *d;
1461     int i, j, ret = 0;
1462     int p0[] = { 163, 7, 6, 3, 0, -1 };
1463     int p1[] = { 193, 15, 0, -1 };
1464
1465     a = BN_new();
1466     b[0] = BN_new();
1467     b[1] = BN_new();
1468     c = BN_new();
1469     d = BN_new();
1470
1471     BN_GF2m_arr2poly(p0, b[0]);
1472     BN_GF2m_arr2poly(p1, b[1]);
1473
1474     for (i = 0; i < num0; i++) {
1475         BN_bntest_rand(a, 512, 0, 0);
1476         for (j = 0; j < 2; j++) {
1477             BN_GF2m_mod_inv(c, a, b[j], ctx);
1478             BN_GF2m_mod_mul(d, a, c, b[j], ctx);
1479 # if 0                          /* make test uses ouput in bc but bc can't
1480                                  * handle GF(2^m) arithmetic */
1481             if (bp != NULL) {
1482                 if (!results) {
1483                     BN_print(bp, a);
1484                     BIO_puts(bp, " * ");
1485                     BN_print(bp, c);
1486                     BIO_puts(bp, " - 1 % ");
1487                     BN_print(bp, b[j]);
1488                     BIO_puts(bp, "\n");
1489                 }
1490             }
1491 # endif
1492             /* Test that ((1/a)*a) = 1. */
1493             if (!BN_is_one(d)) {
1494                 fprintf(stderr, "GF(2^m) modular inversion test failed!\n");
1495                 goto err;
1496             }
1497         }
1498     }
1499     ret = 1;
1500  err:
1501     BN_free(a);
1502     BN_free(b[0]);
1503     BN_free(b[1]);
1504     BN_free(c);
1505     BN_free(d);
1506     return ret;
1507 }
1508
1509 int test_gf2m_mod_div(BIO *bp, BN_CTX *ctx)
1510 {
1511     BIGNUM *a, *b[2], *c, *d, *e, *f;
1512     int i, j, ret = 0;
1513     int p0[] = { 163, 7, 6, 3, 0, -1 };
1514     int p1[] = { 193, 15, 0, -1 };
1515
1516     a = BN_new();
1517     b[0] = BN_new();
1518     b[1] = BN_new();
1519     c = BN_new();
1520     d = BN_new();
1521     e = BN_new();
1522     f = BN_new();
1523
1524     BN_GF2m_arr2poly(p0, b[0]);
1525     BN_GF2m_arr2poly(p1, b[1]);
1526
1527     for (i = 0; i < num0; i++) {
1528         BN_bntest_rand(a, 512, 0, 0);
1529         BN_bntest_rand(c, 512, 0, 0);
1530         for (j = 0; j < 2; j++) {
1531             BN_GF2m_mod_div(d, a, c, b[j], ctx);
1532             BN_GF2m_mod_mul(e, d, c, b[j], ctx);
1533             BN_GF2m_mod_div(f, a, e, b[j], ctx);
1534 # if 0                          /* make test uses ouput in bc but bc can't
1535                                  * handle GF(2^m) arithmetic */
1536             if (bp != NULL) {
1537                 if (!results) {
1538                     BN_print(bp, a);
1539                     BIO_puts(bp, " = ");
1540                     BN_print(bp, c);
1541                     BIO_puts(bp, " * ");
1542                     BN_print(bp, d);
1543                     BIO_puts(bp, " % ");
1544                     BN_print(bp, b[j]);
1545                     BIO_puts(bp, "\n");
1546                 }
1547             }
1548 # endif
1549             /* Test that ((a/c)*c)/a = 1. */
1550             if (!BN_is_one(f)) {
1551                 fprintf(stderr, "GF(2^m) modular division test failed!\n");
1552                 goto err;
1553             }
1554         }
1555     }
1556     ret = 1;
1557  err:
1558     BN_free(a);
1559     BN_free(b[0]);
1560     BN_free(b[1]);
1561     BN_free(c);
1562     BN_free(d);
1563     BN_free(e);
1564     BN_free(f);
1565     return ret;
1566 }
1567
1568 int test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx)
1569 {
1570     BIGNUM *a, *b[2], *c, *d, *e, *f;
1571     int i, j, ret = 0;
1572     int p0[] = { 163, 7, 6, 3, 0, -1 };
1573     int p1[] = { 193, 15, 0, -1 };
1574
1575     a = BN_new();
1576     b[0] = BN_new();
1577     b[1] = BN_new();
1578     c = BN_new();
1579     d = BN_new();
1580     e = BN_new();
1581     f = BN_new();
1582
1583     BN_GF2m_arr2poly(p0, b[0]);
1584     BN_GF2m_arr2poly(p1, b[1]);
1585
1586     for (i = 0; i < num0; i++) {
1587         BN_bntest_rand(a, 512, 0, 0);
1588         BN_bntest_rand(c, 512, 0, 0);
1589         BN_bntest_rand(d, 512, 0, 0);
1590         for (j = 0; j < 2; j++) {
1591             BN_GF2m_mod_exp(e, a, c, b[j], ctx);
1592             BN_GF2m_mod_exp(f, a, d, b[j], ctx);
1593             BN_GF2m_mod_mul(e, e, f, b[j], ctx);
1594             BN_add(f, c, d);
1595             BN_GF2m_mod_exp(f, a, f, b[j], ctx);
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                     BN_print(bp, a);
1601                     BIO_puts(bp, " ^ (");
1602                     BN_print(bp, c);
1603                     BIO_puts(bp, " + ");
1604                     BN_print(bp, d);
1605                     BIO_puts(bp, ") = ");
1606                     BN_print(bp, e);
1607                     BIO_puts(bp, "; - ");
1608                     BN_print(bp, f);
1609                     BIO_puts(bp, " % ");
1610                     BN_print(bp, b[j]);
1611                     BIO_puts(bp, "\n");
1612                 }
1613             }
1614 # endif
1615             BN_GF2m_add(f, e, f);
1616             /* Test that a^(c+d)=a^c*a^d. */
1617             if (!BN_is_zero(f)) {
1618                 fprintf(stderr,
1619                         "GF(2^m) modular exponentiation test failed!\n");
1620                 goto err;
1621             }
1622         }
1623     }
1624     ret = 1;
1625  err:
1626     BN_free(a);
1627     BN_free(b[0]);
1628     BN_free(b[1]);
1629     BN_free(c);
1630     BN_free(d);
1631     BN_free(e);
1632     BN_free(f);
1633     return ret;
1634 }
1635
1636 int test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx)
1637 {
1638     BIGNUM *a, *b[2], *c, *d, *e, *f;
1639     int i, j, ret = 0;
1640     int p0[] = { 163, 7, 6, 3, 0, -1 };
1641     int p1[] = { 193, 15, 0, -1 };
1642
1643     a = BN_new();
1644     b[0] = BN_new();
1645     b[1] = BN_new();
1646     c = BN_new();
1647     d = BN_new();
1648     e = BN_new();
1649     f = BN_new();
1650
1651     BN_GF2m_arr2poly(p0, b[0]);
1652     BN_GF2m_arr2poly(p1, b[1]);
1653
1654     for (i = 0; i < num0; i++) {
1655         BN_bntest_rand(a, 512, 0, 0);
1656         for (j = 0; j < 2; j++) {
1657             BN_GF2m_mod(c, a, b[j]);
1658             BN_GF2m_mod_sqrt(d, a, b[j], ctx);
1659             BN_GF2m_mod_sqr(e, d, b[j], ctx);
1660 # if 0                          /* make test uses ouput in bc but bc can't
1661                                  * handle GF(2^m) arithmetic */
1662             if (bp != NULL) {
1663                 if (!results) {
1664                     BN_print(bp, d);
1665                     BIO_puts(bp, " ^ 2 - ");
1666                     BN_print(bp, a);
1667                     BIO_puts(bp, "\n");
1668                 }
1669             }
1670 # endif
1671             BN_GF2m_add(f, c, e);
1672             /* Test that d^2 = a, where d = sqrt(a). */
1673             if (!BN_is_zero(f)) {
1674                 fprintf(stderr, "GF(2^m) modular square root test failed!\n");
1675                 goto err;
1676             }
1677         }
1678     }
1679     ret = 1;
1680  err:
1681     BN_free(a);
1682     BN_free(b[0]);
1683     BN_free(b[1]);
1684     BN_free(c);
1685     BN_free(d);
1686     BN_free(e);
1687     BN_free(f);
1688     return ret;
1689 }
1690
1691 int test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx)
1692 {
1693     BIGNUM *a, *b[2], *c, *d, *e;
1694     int i, j, s = 0, t, ret = 0;
1695     int p0[] = { 163, 7, 6, 3, 0, -1 };
1696     int p1[] = { 193, 15, 0, -1 };
1697
1698     a = BN_new();
1699     b[0] = BN_new();
1700     b[1] = BN_new();
1701     c = BN_new();
1702     d = BN_new();
1703     e = BN_new();
1704
1705     BN_GF2m_arr2poly(p0, b[0]);
1706     BN_GF2m_arr2poly(p1, b[1]);
1707
1708     for (i = 0; i < num0; i++) {
1709         BN_bntest_rand(a, 512, 0, 0);
1710         for (j = 0; j < 2; j++) {
1711             t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
1712             if (t) {
1713                 s++;
1714                 BN_GF2m_mod_sqr(d, c, b[j], ctx);
1715                 BN_GF2m_add(d, c, d);
1716                 BN_GF2m_mod(e, a, b[j]);
1717 # if 0                          /* make test uses ouput in bc but bc can't
1718                                  * handle GF(2^m) arithmetic */
1719                 if (bp != NULL) {
1720                     if (!results) {
1721                         BN_print(bp, c);
1722                         BIO_puts(bp, " is root of z^2 + z = ");
1723                         BN_print(bp, a);
1724                         BIO_puts(bp, " % ");
1725                         BN_print(bp, b[j]);
1726                         BIO_puts(bp, "\n");
1727                     }
1728                 }
1729 # endif
1730                 BN_GF2m_add(e, e, d);
1731                 /*
1732                  * Test that solution of quadratic c satisfies c^2 + c = a.
1733                  */
1734                 if (!BN_is_zero(e)) {
1735                     fprintf(stderr,
1736                             "GF(2^m) modular solve quadratic test failed!\n");
1737                     goto err;
1738                 }
1739
1740             } else {
1741 # if 0                          /* make test uses ouput in bc but bc can't
1742                                  * handle GF(2^m) arithmetic */
1743                 if (bp != NULL) {
1744                     if (!results) {
1745                         BIO_puts(bp, "There are no roots of z^2 + z = ");
1746                         BN_print(bp, a);
1747                         BIO_puts(bp, " % ");
1748                         BN_print(bp, b[j]);
1749                         BIO_puts(bp, "\n");
1750                     }
1751                 }
1752 # endif
1753             }
1754         }
1755     }
1756     if (s == 0) {
1757         fprintf(stderr,
1758                 "All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n",
1759                 num0);
1760         fprintf(stderr,
1761                 "this is very unlikely and probably indicates an error.\n");
1762         goto err;
1763     }
1764     ret = 1;
1765  err:
1766     BN_free(a);
1767     BN_free(b[0]);
1768     BN_free(b[1]);
1769     BN_free(c);
1770     BN_free(d);
1771     BN_free(e);
1772     return ret;
1773 }
1774 #endif
1775 static int genprime_cb(int p, int n, BN_GENCB *arg)
1776 {
1777     char c = '*';
1778
1779     if (p == 0)
1780         c = '.';
1781     if (p == 1)
1782         c = '+';
1783     if (p == 2)
1784         c = '*';
1785     if (p == 3)
1786         c = '\n';
1787     putc(c, stderr);
1788     fflush(stderr);
1789     return 1;
1790 }
1791
1792 int test_kron(BIO *bp, BN_CTX *ctx)
1793 {
1794     BN_GENCB cb;
1795     BIGNUM *a, *b, *r, *t;
1796     int i;
1797     int legendre, kronecker;
1798     int ret = 0;
1799
1800     a = BN_new();
1801     b = BN_new();
1802     r = BN_new();
1803     t = BN_new();
1804     if (a == NULL || b == NULL || r == NULL || t == NULL)
1805         goto err;
1806
1807     BN_GENCB_set(&cb, genprime_cb, NULL);
1808
1809     /*
1810      * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
1811      * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
1812      * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
1813      * generate a random prime b and compare these values for a number of
1814      * random a's.  (That is, we run the Solovay-Strassen primality test to
1815      * confirm that b is prime, except that we don't want to test whether b
1816      * is prime but whether BN_kronecker works.)
1817      */
1818
1819     if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb))
1820         goto err;
1821     b->neg = rand_neg();
1822     putc('\n', stderr);
1823
1824     for (i = 0; i < num0; i++) {
1825         if (!BN_bntest_rand(a, 512, 0, 0))
1826             goto err;
1827         a->neg = rand_neg();
1828
1829         /* t := (|b|-1)/2  (note that b is odd) */
1830         if (!BN_copy(t, b))
1831             goto err;
1832         t->neg = 0;
1833         if (!BN_sub_word(t, 1))
1834             goto err;
1835         if (!BN_rshift1(t, t))
1836             goto err;
1837         /* r := a^t mod b */
1838         b->neg = 0;
1839
1840         if (!BN_mod_exp_recp(r, a, t, b, ctx))
1841             goto err;
1842         b->neg = 1;
1843
1844         if (BN_is_word(r, 1))
1845             legendre = 1;
1846         else if (BN_is_zero(r))
1847             legendre = 0;
1848         else {
1849             if (!BN_add_word(r, 1))
1850                 goto err;
1851             if (0 != BN_ucmp(r, b)) {
1852                 fprintf(stderr, "Legendre symbol computation failed\n");
1853                 goto err;
1854             }
1855             legendre = -1;
1856         }
1857
1858         kronecker = BN_kronecker(a, b, ctx);
1859         if (kronecker < -1)
1860             goto err;
1861         /* we actually need BN_kronecker(a, |b|) */
1862         if (a->neg && b->neg)
1863             kronecker = -kronecker;
1864
1865         if (legendre != kronecker) {
1866             fprintf(stderr, "legendre != kronecker; a = ");
1867             BN_print_fp(stderr, a);
1868             fprintf(stderr, ", b = ");
1869             BN_print_fp(stderr, b);
1870             fprintf(stderr, "\n");
1871             goto err;
1872         }
1873
1874         putc('.', stderr);
1875         fflush(stderr);
1876     }
1877
1878     putc('\n', stderr);
1879     fflush(stderr);
1880     ret = 1;
1881  err:
1882     if (a != NULL)
1883         BN_free(a);
1884     if (b != NULL)
1885         BN_free(b);
1886     if (r != NULL)
1887         BN_free(r);
1888     if (t != NULL)
1889         BN_free(t);
1890     return ret;
1891 }
1892
1893 int test_sqrt(BIO *bp, BN_CTX *ctx)
1894 {
1895     BN_GENCB cb;
1896     BIGNUM *a, *p, *r;
1897     int i, j;
1898     int ret = 0;
1899
1900     a = BN_new();
1901     p = BN_new();
1902     r = BN_new();
1903     if (a == NULL || p == NULL || r == NULL)
1904         goto err;
1905
1906     BN_GENCB_set(&cb, genprime_cb, NULL);
1907
1908     for (i = 0; i < 16; i++) {
1909         if (i < 8) {
1910             unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
1911
1912             if (!BN_set_word(p, primes[i]))
1913                 goto err;
1914         } else {
1915             if (!BN_set_word(a, 32))
1916                 goto err;
1917             if (!BN_set_word(r, 2 * i + 1))
1918                 goto err;
1919
1920             if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb))
1921                 goto err;
1922             putc('\n', stderr);
1923         }
1924         p->neg = rand_neg();
1925
1926         for (j = 0; j < num2; j++) {
1927             /*
1928              * construct 'a' such that it is a square modulo p, but in
1929              * general not a proper square and not reduced modulo p
1930              */
1931             if (!BN_bntest_rand(r, 256, 0, 3))
1932                 goto err;
1933             if (!BN_nnmod(r, r, p, ctx))
1934                 goto err;
1935             if (!BN_mod_sqr(r, r, p, ctx))
1936                 goto err;
1937             if (!BN_bntest_rand(a, 256, 0, 3))
1938                 goto err;
1939             if (!BN_nnmod(a, a, p, ctx))
1940                 goto err;
1941             if (!BN_mod_sqr(a, a, p, ctx))
1942                 goto err;
1943             if (!BN_mul(a, a, r, ctx))
1944                 goto err;
1945             if (rand_neg())
1946                 if (!BN_sub(a, a, p))
1947                     goto err;
1948
1949             if (!BN_mod_sqrt(r, a, p, ctx))
1950                 goto err;
1951             if (!BN_mod_sqr(r, r, p, ctx))
1952                 goto err;
1953
1954             if (!BN_nnmod(a, a, p, ctx))
1955                 goto err;
1956
1957             if (BN_cmp(a, r) != 0) {
1958                 fprintf(stderr, "BN_mod_sqrt failed: a = ");
1959                 BN_print_fp(stderr, a);
1960                 fprintf(stderr, ", r = ");
1961                 BN_print_fp(stderr, r);
1962                 fprintf(stderr, ", p = ");
1963                 BN_print_fp(stderr, p);
1964                 fprintf(stderr, "\n");
1965                 goto err;
1966             }
1967
1968             putc('.', stderr);
1969             fflush(stderr);
1970         }
1971
1972         putc('\n', stderr);
1973         fflush(stderr);
1974     }
1975     ret = 1;
1976  err:
1977     if (a != NULL)
1978         BN_free(a);
1979     if (p != NULL)
1980         BN_free(p);
1981     if (r != NULL)
1982         BN_free(r);
1983     return ret;
1984 }
1985
1986 int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_)
1987 {
1988     BIGNUM *a, *b, *c, *d;
1989     int i;
1990
1991     b = BN_new();
1992     c = BN_new();
1993     d = BN_new();
1994     BN_one(c);
1995
1996     if (a_)
1997         a = a_;
1998     else {
1999         a = BN_new();
2000         BN_bntest_rand(a, 200, 0, 0);
2001         a->neg = rand_neg();
2002     }
2003     for (i = 0; i < num0; i++) {
2004         BN_lshift(b, a, i + 1);
2005         BN_add(c, c, c);
2006         if (bp != NULL) {
2007             if (!results) {
2008                 BN_print(bp, a);
2009                 BIO_puts(bp, " * ");
2010                 BN_print(bp, c);
2011                 BIO_puts(bp, " - ");
2012             }
2013             BN_print(bp, b);
2014             BIO_puts(bp, "\n");
2015         }
2016         BN_mul(d, a, c, ctx);
2017         BN_sub(d, d, b);
2018         if (!BN_is_zero(d)) {
2019             fprintf(stderr, "Left shift test failed!\n");
2020             fprintf(stderr, "a=");
2021             BN_print_fp(stderr, a);
2022             fprintf(stderr, "\nb=");
2023             BN_print_fp(stderr, b);
2024             fprintf(stderr, "\nc=");
2025             BN_print_fp(stderr, c);
2026             fprintf(stderr, "\nd=");
2027             BN_print_fp(stderr, d);
2028             fprintf(stderr, "\n");
2029             return 0;
2030         }
2031     }
2032     BN_free(a);
2033     BN_free(b);
2034     BN_free(c);
2035     BN_free(d);
2036     return (1);
2037 }
2038
2039 int test_lshift1(BIO *bp)
2040 {
2041     BIGNUM *a, *b, *c;
2042     int i;
2043
2044     a = BN_new();
2045     b = BN_new();
2046     c = BN_new();
2047
2048     BN_bntest_rand(a, 200, 0, 0);
2049     a->neg = rand_neg();
2050     for (i = 0; i < num0; i++) {
2051         BN_lshift1(b, a);
2052         if (bp != NULL) {
2053             if (!results) {
2054                 BN_print(bp, a);
2055                 BIO_puts(bp, " * 2");
2056                 BIO_puts(bp, " - ");
2057             }
2058             BN_print(bp, b);
2059             BIO_puts(bp, "\n");
2060         }
2061         BN_add(c, a, a);
2062         BN_sub(a, b, c);
2063         if (!BN_is_zero(a)) {
2064             fprintf(stderr, "Left shift one test failed!\n");
2065             return 0;
2066         }
2067
2068         BN_copy(a, b);
2069     }
2070     BN_free(a);
2071     BN_free(b);
2072     BN_free(c);
2073     return (1);
2074 }
2075
2076 int test_rshift(BIO *bp, BN_CTX *ctx)
2077 {
2078     BIGNUM *a, *b, *c, *d, *e;
2079     int i;
2080
2081     a = BN_new();
2082     b = BN_new();
2083     c = BN_new();
2084     d = BN_new();
2085     e = BN_new();
2086     BN_one(c);
2087
2088     BN_bntest_rand(a, 200, 0, 0);
2089     a->neg = rand_neg();
2090     for (i = 0; i < num0; i++) {
2091         BN_rshift(b, a, i + 1);
2092         BN_add(c, c, c);
2093         if (bp != NULL) {
2094             if (!results) {
2095                 BN_print(bp, a);
2096                 BIO_puts(bp, " / ");
2097                 BN_print(bp, c);
2098                 BIO_puts(bp, " - ");
2099             }
2100             BN_print(bp, b);
2101             BIO_puts(bp, "\n");
2102         }
2103         BN_div(d, e, a, c, ctx);
2104         BN_sub(d, d, b);
2105         if (!BN_is_zero(d)) {
2106             fprintf(stderr, "Right shift test failed!\n");
2107             return 0;
2108         }
2109     }
2110     BN_free(a);
2111     BN_free(b);
2112     BN_free(c);
2113     BN_free(d);
2114     BN_free(e);
2115     return (1);
2116 }
2117
2118 int test_rshift1(BIO *bp)
2119 {
2120     BIGNUM *a, *b, *c;
2121     int i;
2122
2123     a = BN_new();
2124     b = BN_new();
2125     c = BN_new();
2126
2127     BN_bntest_rand(a, 200, 0, 0);
2128     a->neg = rand_neg();
2129     for (i = 0; i < num0; i++) {
2130         BN_rshift1(b, a);
2131         if (bp != NULL) {
2132             if (!results) {
2133                 BN_print(bp, a);
2134                 BIO_puts(bp, " / 2");
2135                 BIO_puts(bp, " - ");
2136             }
2137             BN_print(bp, b);
2138             BIO_puts(bp, "\n");
2139         }
2140         BN_sub(c, a, b);
2141         BN_sub(c, c, b);
2142         if (!BN_is_zero(c) && !BN_abs_is_word(c, 1)) {
2143             fprintf(stderr, "Right shift one test failed!\n");
2144             return 0;
2145         }
2146         BN_copy(a, b);
2147     }
2148     BN_free(a);
2149     BN_free(b);
2150     BN_free(c);
2151     return (1);
2152 }
2153
2154 int rand_neg(void)
2155 {
2156     static unsigned int neg = 0;
2157     static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };
2158
2159     return (sign[(neg++) % 8]);
2160 }