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