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