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