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