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