crypto/bn/bntest.c

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