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