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