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
1024         BN_MONT_CTX *mont;
1025
1026         a=BN_new();
1027         p=BN_new();
1028         m=BN_new();
1029         d=BN_new();
1030         e=BN_new();
1031
1032         mont = BN_MONT_CTX_new();
1033
1034         BN_bntest_rand(m,1024,0,1); /* must be odd for montgomery */
1035         /* Zero exponent */
1036         BN_bntest_rand(a,1024,0,0);
1037         BN_zero(p);
1038         if(!BN_mod_exp_mont_consttime(d,a,p,m,ctx,NULL))
1039                 return 0;
1040         if(!BN_is_one(d))
1041                 {
1042                 fprintf(stderr, "Modular exponentiation test failed!\n");
1043                 return 0;
1044                 }
1045         /* Zero input */
1046         BN_bntest_rand(p,1024,0,0);
1047         BN_zero(a);
1048         if(!BN_mod_exp_mont_consttime(d,a,p,m,ctx,NULL))
1049                 return 0;
1050         if(!BN_is_zero(d))
1051                 {
1052                 fprintf(stderr, "Modular exponentiation test failed!\n");
1053                 return 0;
1054                 }
1055         /* Craft an input whose Montgomery representation is 1,
1056          * i.e., shorter than the modulus m, in order to test
1057          * the const time precomputation scattering/gathering.
1058          */
1059         BN_one(a);
1060         BN_MONT_CTX_set(mont,m,ctx);
1061         if(!BN_from_montgomery(e,a,mont,ctx))
1062                 return 0;
1063         if(!BN_mod_exp_mont_consttime(d,e,p,m,ctx,NULL))
1064                 return 0;
1065         if(!BN_mod_exp_simple(a,e,p,m,ctx))
1066                 return 0;
1067         if(BN_cmp(a,d) != 0)
1068                 {
1069                 fprintf(stderr,"Modular exponentiation test failed!\n");
1070                 return 0;
1071                 }
1072         /* Finally, some regular test vectors. */
1073         BN_bntest_rand(e,1024,0,0);
1074         if(!BN_mod_exp_mont_consttime(d,e,p,m,ctx,NULL))
1075                 return 0;
1076         if(!BN_mod_exp_simple(a,e,p,m,ctx))
1077                 return 0;
1078         if(BN_cmp(a,d) != 0)
1079                 {
1080                 fprintf(stderr,"Modular exponentiation test failed!\n");
1081                 return 0;
1082                 }
1083         BN_free(a);
1084         BN_free(p);
1085         BN_free(m);
1086         BN_free(d);
1087         BN_free(e);
1088         return(1);
1089         }
1090
1091 int test_exp(BIO *bp, BN_CTX *ctx)
1092         {
1093         BIGNUM *a,*b,*d,*e,*one;
1094         int i;
1095
1096         a=BN_new();
1097         b=BN_new();
1098         d=BN_new();
1099         e=BN_new();
1100         one=BN_new();
1101         BN_one(one);
1102
1103         for (i=0; i<num2; i++)
1104                 {
1105                 BN_bntest_rand(a,20+i*5,0,0); /**/
1106                 BN_bntest_rand(b,2+i,0,0); /**/
1107
1108                 if (BN_exp(d,a,b,ctx) <= 0)
1109                         return(0);
1110
1111                 if (bp != NULL)
1112                         {
1113                         if (!results)
1114                                 {
1115                                 BN_print(bp,a);
1116                                 BIO_puts(bp," ^ ");
1117                                 BN_print(bp,b);
1118                                 BIO_puts(bp," - ");
1119                                 }
1120                         BN_print(bp,d);
1121                         BIO_puts(bp,"\n");
1122                         }
1123                 BN_one(e);
1124                 for( ; !BN_is_zero(b) ; BN_sub(b,b,one))
1125                     BN_mul(e,e,a,ctx);
1126                 BN_sub(e,e,d);
1127                 if(!BN_is_zero(e))
1128                     {
1129                     fprintf(stderr,"Exponentiation test failed!\n");
1130                     return 0;
1131                     }
1132                 }
1133         BN_free(a);
1134         BN_free(b);
1135         BN_free(d);
1136         BN_free(e);
1137         BN_free(one);
1138         return(1);
1139         }
1140 #ifndef OPENSSL_NO_EC2M
1141 int test_gf2m_add(BIO *bp)
1142         {
1143         BIGNUM a,b,c;
1144         int i, ret = 0;
1145
1146         BN_init(&a);
1147         BN_init(&b);
1148         BN_init(&c);
1149
1150         for (i=0; i<num0; i++)
1151                 {
1152                 BN_rand(&a,512,0,0);
1153                 BN_copy(&b, BN_value_one());
1154                 a.neg=rand_neg();
1155                 b.neg=rand_neg();
1156                 BN_GF2m_add(&c,&a,&b);
1157 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1158                 if (bp != NULL)
1159                         {
1160                         if (!results)
1161                                 {
1162                                 BN_print(bp,&a);
1163                                 BIO_puts(bp," ^ ");
1164                                 BN_print(bp,&b);
1165                                 BIO_puts(bp," = ");
1166                                 }
1167                         BN_print(bp,&c);
1168                         BIO_puts(bp,"\n");
1169                         }
1170 #endif
1171                 /* Test that two added values have the correct parity. */
1172                 if((BN_is_odd(&a) && BN_is_odd(&c)) || (!BN_is_odd(&a) && !BN_is_odd(&c)))
1173                         {
1174                     fprintf(stderr,"GF(2^m) addition test (a) failed!\n");
1175                         goto err;
1176                         }
1177                 BN_GF2m_add(&c,&c,&c);
1178                 /* Test that c + c = 0. */
1179                 if(!BN_is_zero(&c))
1180                     {
1181                     fprintf(stderr,"GF(2^m) addition test (b) failed!\n");
1182                         goto err;
1183                     }
1184                 }
1185         ret = 1;
1186   err:
1187         BN_free(&a);
1188         BN_free(&b);
1189         BN_free(&c);
1190         return ret;
1191         }
1192
1193 int test_gf2m_mod(BIO *bp)
1194         {
1195         BIGNUM *a,*b[2],*c,*d,*e;
1196         int i, j, ret = 0;
1197         int p0[] = {163,7,6,3,0,-1};
1198         int p1[] = {193,15,0,-1};
1199
1200         a=BN_new();
1201         b[0]=BN_new();
1202         b[1]=BN_new();
1203         c=BN_new();
1204         d=BN_new();
1205         e=BN_new();
1206
1207         BN_GF2m_arr2poly(p0, b[0]);
1208         BN_GF2m_arr2poly(p1, b[1]);
1209
1210         for (i=0; i<num0; i++)
1211                 {
1212                 BN_bntest_rand(a, 1024, 0, 0);
1213                 for (j=0; j < 2; j++)
1214                         {
1215                         BN_GF2m_mod(c, a, b[j]);
1216 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1217                         if (bp != NULL)
1218                                 {
1219                                 if (!results)
1220                                         {
1221                                         BN_print(bp,a);
1222                                         BIO_puts(bp," % ");
1223                                         BN_print(bp,b[j]);
1224                                         BIO_puts(bp," - ");
1225                                         BN_print(bp,c);
1226                                         BIO_puts(bp,"\n");
1227                                         }
1228                                 }
1229 #endif
1230                         BN_GF2m_add(d, a, c);
1231                         BN_GF2m_mod(e, d, b[j]);
1232                         /* Test that a + (a mod p) mod p == 0. */
1233                         if(!BN_is_zero(e))
1234                                 {
1235                                 fprintf(stderr,"GF(2^m) modulo test failed!\n");
1236                                 goto err;
1237                                 }
1238                         }
1239                 }
1240         ret = 1;
1241   err:
1242         BN_free(a);
1243         BN_free(b[0]);
1244         BN_free(b[1]);
1245         BN_free(c);
1246         BN_free(d);
1247         BN_free(e);
1248         return ret;
1249         }
1250
1251 int test_gf2m_mod_mul(BIO *bp,BN_CTX *ctx)
1252         {
1253         BIGNUM *a,*b[2],*c,*d,*e,*f,*g,*h;
1254         int i, j, ret = 0;
1255         int p0[] = {163,7,6,3,0,-1};
1256         int p1[] = {193,15,0,-1};
1257
1258         a=BN_new();
1259         b[0]=BN_new();
1260         b[1]=BN_new();
1261         c=BN_new();
1262         d=BN_new();
1263         e=BN_new();
1264         f=BN_new();
1265         g=BN_new();
1266         h=BN_new();
1267
1268         BN_GF2m_arr2poly(p0, b[0]);
1269         BN_GF2m_arr2poly(p1, b[1]);
1270
1271         for (i=0; i<num0; i++)
1272                 {
1273                 BN_bntest_rand(a, 1024, 0, 0);
1274                 BN_bntest_rand(c, 1024, 0, 0);
1275                 BN_bntest_rand(d, 1024, 0, 0);
1276                 for (j=0; j < 2; j++)
1277                         {
1278                         BN_GF2m_mod_mul(e, a, c, b[j], ctx);
1279 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1280                         if (bp != NULL)
1281                                 {
1282                                 if (!results)
1283                                         {
1284                                         BN_print(bp,a);
1285                                         BIO_puts(bp," * ");
1286                                         BN_print(bp,c);
1287                                         BIO_puts(bp," % ");
1288                                         BN_print(bp,b[j]);
1289                                         BIO_puts(bp," - ");
1290                                         BN_print(bp,e);
1291                                         BIO_puts(bp,"\n");
1292                                         }
1293                                 }
1294 #endif
1295                         BN_GF2m_add(f, a, d);
1296                         BN_GF2m_mod_mul(g, f, c, b[j], ctx);
1297                         BN_GF2m_mod_mul(h, d, c, b[j], ctx);
1298                         BN_GF2m_add(f, e, g);
1299                         BN_GF2m_add(f, f, h);
1300                         /* Test that (a+d)*c = a*c + d*c. */
1301                         if(!BN_is_zero(f))
1302                                 {
1303                                 fprintf(stderr,"GF(2^m) modular multiplication test failed!\n");
1304                                 goto err;
1305                                 }
1306                         }
1307                 }
1308         ret = 1;
1309   err:
1310         BN_free(a);
1311         BN_free(b[0]);
1312         BN_free(b[1]);
1313         BN_free(c);
1314         BN_free(d);
1315         BN_free(e);
1316         BN_free(f);
1317         BN_free(g);
1318         BN_free(h);
1319         return ret;
1320         }
1321
1322 int test_gf2m_mod_sqr(BIO *bp,BN_CTX *ctx)
1323         {
1324         BIGNUM *a,*b[2],*c,*d;
1325         int i, j, ret = 0;
1326         int p0[] = {163,7,6,3,0,-1};
1327         int p1[] = {193,15,0,-1};
1328
1329         a=BN_new();
1330         b[0]=BN_new();
1331         b[1]=BN_new();
1332         c=BN_new();
1333         d=BN_new();
1334
1335         BN_GF2m_arr2poly(p0, b[0]);
1336         BN_GF2m_arr2poly(p1, b[1]);
1337
1338         for (i=0; i<num0; i++)
1339                 {
1340                 BN_bntest_rand(a, 1024, 0, 0);
1341                 for (j=0; j < 2; j++)
1342                         {
1343                         BN_GF2m_mod_sqr(c, a, b[j], ctx);
1344                         BN_copy(d, a);
1345                         BN_GF2m_mod_mul(d, a, d, b[j], ctx);
1346 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1347                         if (bp != NULL)
1348                                 {
1349                                 if (!results)
1350                                         {
1351                                         BN_print(bp,a);
1352                                         BIO_puts(bp," ^ 2 % ");
1353                                         BN_print(bp,b[j]);
1354                                         BIO_puts(bp, " = ");
1355                                         BN_print(bp,c);
1356                                         BIO_puts(bp,"; a * a = ");
1357                                         BN_print(bp,d);
1358                                         BIO_puts(bp,"\n");
1359                                         }
1360                                 }
1361 #endif
1362                         BN_GF2m_add(d, c, d);
1363                         /* Test that a*a = a^2. */
1364                         if(!BN_is_zero(d))
1365                                 {
1366                                 fprintf(stderr,"GF(2^m) modular squaring test failed!\n");
1367                                 goto err;
1368                                 }
1369                         }
1370                 }
1371         ret = 1;
1372   err:
1373         BN_free(a);
1374         BN_free(b[0]);
1375         BN_free(b[1]);
1376         BN_free(c);
1377         BN_free(d);
1378         return ret;
1379         }
1380
1381 int test_gf2m_mod_inv(BIO *bp,BN_CTX *ctx)
1382         {
1383         BIGNUM *a,*b[2],*c,*d;
1384         int i, j, ret = 0;
1385         int p0[] = {163,7,6,3,0,-1};
1386         int p1[] = {193,15,0,-1};
1387
1388         a=BN_new();
1389         b[0]=BN_new();
1390         b[1]=BN_new();
1391         c=BN_new();
1392         d=BN_new();
1393
1394         BN_GF2m_arr2poly(p0, b[0]);
1395         BN_GF2m_arr2poly(p1, b[1]);
1396
1397         for (i=0; i<num0; i++)
1398                 {
1399                 BN_bntest_rand(a, 512, 0, 0);
1400                 for (j=0; j < 2; j++)
1401                         {
1402                         BN_GF2m_mod_inv(c, a, b[j], ctx);
1403                         BN_GF2m_mod_mul(d, a, c, b[j], ctx);
1404 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1405                         if (bp != NULL)
1406                                 {
1407                                 if (!results)
1408                                         {
1409                                         BN_print(bp,a);
1410                                         BIO_puts(bp, " * ");
1411                                         BN_print(bp,c);
1412                                         BIO_puts(bp," - 1 % ");
1413                                         BN_print(bp,b[j]);
1414                                         BIO_puts(bp,"\n");
1415                                         }
1416                                 }
1417 #endif
1418                         /* Test that ((1/a)*a) = 1. */
1419                         if(!BN_is_one(d))
1420                                 {
1421                                 fprintf(stderr,"GF(2^m) modular inversion test failed!\n");
1422                                 goto err;
1423                                 }
1424                         }
1425                 }
1426         ret = 1;
1427   err:
1428         BN_free(a);
1429         BN_free(b[0]);
1430         BN_free(b[1]);
1431         BN_free(c);
1432         BN_free(d);
1433         return ret;
1434         }
1435
1436 int test_gf2m_mod_div(BIO *bp,BN_CTX *ctx)
1437         {
1438         BIGNUM *a,*b[2],*c,*d,*e,*f;
1439         int i, j, ret = 0;
1440         int p0[] = {163,7,6,3,0,-1};
1441         int p1[] = {193,15,0,-1};
1442
1443         a=BN_new();
1444         b[0]=BN_new();
1445         b[1]=BN_new();
1446         c=BN_new();
1447         d=BN_new();
1448         e=BN_new();
1449         f=BN_new();
1450
1451         BN_GF2m_arr2poly(p0, b[0]);
1452         BN_GF2m_arr2poly(p1, b[1]);
1453
1454         for (i=0; i<num0; i++)
1455                 {
1456                 BN_bntest_rand(a, 512, 0, 0);
1457                 BN_bntest_rand(c, 512, 0, 0);
1458                 for (j=0; j < 2; j++)
1459                         {
1460                         BN_GF2m_mod_div(d, a, c, b[j], ctx);
1461                         BN_GF2m_mod_mul(e, d, c, b[j], ctx);
1462                         BN_GF2m_mod_div(f, a, e, b[j], ctx);
1463 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1464                         if (bp != NULL)
1465                                 {
1466                                 if (!results)
1467                                         {
1468                                         BN_print(bp,a);
1469                                         BIO_puts(bp, " = ");
1470                                         BN_print(bp,c);
1471                                         BIO_puts(bp," * ");
1472                                         BN_print(bp,d);
1473                                         BIO_puts(bp, " % ");
1474                                         BN_print(bp,b[j]);
1475                                         BIO_puts(bp,"\n");
1476                                         }
1477                                 }
1478 #endif
1479                         /* Test that ((a/c)*c)/a = 1. */
1480                         if(!BN_is_one(f))
1481                                 {
1482                                 fprintf(stderr,"GF(2^m) modular division test failed!\n");
1483                                 goto err;
1484                                 }
1485                         }
1486                 }
1487         ret = 1;
1488   err:
1489         BN_free(a);
1490         BN_free(b[0]);
1491         BN_free(b[1]);
1492         BN_free(c);
1493         BN_free(d);
1494         BN_free(e);
1495         BN_free(f);
1496         return ret;
1497         }
1498
1499 int test_gf2m_mod_exp(BIO *bp,BN_CTX *ctx)
1500         {
1501         BIGNUM *a,*b[2],*c,*d,*e,*f;
1502         int i, j, ret = 0;
1503         int p0[] = {163,7,6,3,0,-1};
1504         int p1[] = {193,15,0,-1};
1505
1506         a=BN_new();
1507         b[0]=BN_new();
1508         b[1]=BN_new();
1509         c=BN_new();
1510         d=BN_new();
1511         e=BN_new();
1512         f=BN_new();
1513
1514         BN_GF2m_arr2poly(p0, b[0]);
1515         BN_GF2m_arr2poly(p1, b[1]);
1516
1517         for (i=0; i<num0; i++)
1518                 {
1519                 BN_bntest_rand(a, 512, 0, 0);
1520                 BN_bntest_rand(c, 512, 0, 0);
1521                 BN_bntest_rand(d, 512, 0, 0);
1522                 for (j=0; j < 2; j++)
1523                         {
1524                         BN_GF2m_mod_exp(e, a, c, b[j], ctx);
1525                         BN_GF2m_mod_exp(f, a, d, b[j], ctx);
1526                         BN_GF2m_mod_mul(e, e, f, b[j], ctx);
1527                         BN_add(f, c, d);
1528                         BN_GF2m_mod_exp(f, a, f, b[j], ctx);
1529 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1530                         if (bp != NULL)
1531                                 {
1532                                 if (!results)
1533                                         {
1534                                         BN_print(bp,a);
1535                                         BIO_puts(bp, " ^ (");
1536                                         BN_print(bp,c);
1537                                         BIO_puts(bp," + ");
1538                                         BN_print(bp,d);
1539                                         BIO_puts(bp, ") = ");
1540                                         BN_print(bp,e);
1541                                         BIO_puts(bp, "; - ");
1542                                         BN_print(bp,f);
1543                                         BIO_puts(bp, " % ");
1544                                         BN_print(bp,b[j]);
1545                                         BIO_puts(bp,"\n");
1546                                         }
1547                                 }
1548 #endif
1549                         BN_GF2m_add(f, e, f);
1550                         /* Test that a^(c+d)=a^c*a^d. */
1551                         if(!BN_is_zero(f))
1552                                 {
1553                                 fprintf(stderr,"GF(2^m) modular exponentiation test failed!\n");
1554                                 goto err;
1555                                 }
1556                         }
1557                 }
1558         ret = 1;
1559   err:
1560         BN_free(a);
1561         BN_free(b[0]);
1562         BN_free(b[1]);
1563         BN_free(c);
1564         BN_free(d);
1565         BN_free(e);
1566         BN_free(f);
1567         return ret;
1568         }
1569
1570 int test_gf2m_mod_sqrt(BIO *bp,BN_CTX *ctx)
1571         {
1572         BIGNUM *a,*b[2],*c,*d,*e,*f;
1573         int i, j, ret = 0;
1574         int p0[] = {163,7,6,3,0,-1};
1575         int p1[] = {193,15,0,-1};
1576
1577         a=BN_new();
1578         b[0]=BN_new();
1579         b[1]=BN_new();
1580         c=BN_new();
1581         d=BN_new();
1582         e=BN_new();
1583         f=BN_new();
1584
1585         BN_GF2m_arr2poly(p0, b[0]);
1586         BN_GF2m_arr2poly(p1, b[1]);
1587
1588         for (i=0; i<num0; i++)
1589                 {
1590                 BN_bntest_rand(a, 512, 0, 0);
1591                 for (j=0; j < 2; j++)
1592                         {
1593                         BN_GF2m_mod(c, a, b[j]);
1594                         BN_GF2m_mod_sqrt(d, a, b[j], ctx);
1595                         BN_GF2m_mod_sqr(e, d, b[j], ctx);
1596 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1597                         if (bp != NULL)
1598                                 {
1599                                 if (!results)
1600                                         {
1601                                         BN_print(bp,d);
1602                                         BIO_puts(bp, " ^ 2 - ");
1603                                         BN_print(bp,a);
1604                                         BIO_puts(bp,"\n");
1605                                         }
1606                                 }
1607 #endif
1608                         BN_GF2m_add(f, c, e);
1609                         /* Test that d^2 = a, where d = sqrt(a). */
1610                         if(!BN_is_zero(f))
1611                                 {
1612                                 fprintf(stderr,"GF(2^m) modular square root test failed!\n");
1613                                 goto err;
1614                                 }
1615                         }
1616                 }
1617         ret = 1;
1618   err:
1619         BN_free(a);
1620         BN_free(b[0]);
1621         BN_free(b[1]);
1622         BN_free(c);
1623         BN_free(d);
1624         BN_free(e);
1625         BN_free(f);
1626         return ret;
1627         }
1628
1629 int test_gf2m_mod_solve_quad(BIO *bp,BN_CTX *ctx)
1630         {
1631         BIGNUM *a,*b[2],*c,*d,*e;
1632         int i, j, s = 0, t, ret = 0;
1633         int p0[] = {163,7,6,3,0,-1};
1634         int p1[] = {193,15,0,-1};
1635
1636         a=BN_new();
1637         b[0]=BN_new();
1638         b[1]=BN_new();
1639         c=BN_new();
1640         d=BN_new();
1641         e=BN_new();
1642
1643         BN_GF2m_arr2poly(p0, b[0]);
1644         BN_GF2m_arr2poly(p1, b[1]);
1645
1646         for (i=0; i<num0; i++)
1647                 {
1648                 BN_bntest_rand(a, 512, 0, 0);
1649                 for (j=0; j < 2; j++)
1650                         {
1651                         t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
1652                         if (t)
1653                                 {
1654                                 s++;
1655                                 BN_GF2m_mod_sqr(d, c, b[j], ctx);
1656                                 BN_GF2m_add(d, c, d);
1657                                 BN_GF2m_mod(e, a, b[j]);
1658 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1659                                 if (bp != NULL)
1660                                         {
1661                                         if (!results)
1662                                                 {
1663                                                 BN_print(bp,c);
1664                                                 BIO_puts(bp, " is root of z^2 + z = ");
1665                                                 BN_print(bp,a);
1666                                                 BIO_puts(bp, " % ");
1667                                                 BN_print(bp,b[j]);
1668                                                 BIO_puts(bp, "\n");
1669                                                 }
1670                                         }
1671 #endif
1672                                 BN_GF2m_add(e, e, d);
1673                                 /* Test that solution of quadratic c satisfies c^2 + c = a. */
1674                                 if(!BN_is_zero(e))
1675                                         {
1676                                         fprintf(stderr,"GF(2^m) modular solve quadratic test failed!\n");
1677                                         goto err;
1678                                         }
1679
1680                                 }
1681                         else
1682                                 {
1683 #if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
1684                                 if (bp != NULL)
1685                                         {
1686                                         if (!results)
1687                                                 {
1688                                                 BIO_puts(bp, "There are no roots of z^2 + z = ");
1689                                                 BN_print(bp,a);
1690                                                 BIO_puts(bp, " % ");
1691                                                 BN_print(bp,b[j]);
1692                                                 BIO_puts(bp, "\n");
1693                                                 }
1694                                         }
1695 #endif
1696                                 }
1697                         }
1698                 }
1699         if (s == 0)
1700                 {
1701                 fprintf(stderr,"All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n", num0);
1702                 fprintf(stderr,"this is very unlikely and probably indicates an error.\n");
1703                 goto err;
1704                 }
1705         ret = 1;
1706   err:
1707         BN_free(a);
1708         BN_free(b[0]);
1709         BN_free(b[1]);
1710         BN_free(c);
1711         BN_free(d);
1712         BN_free(e);
1713         return ret;
1714         }
1715 #endif
1716 static int genprime_cb(int p, int n, BN_GENCB *arg)
1717         {
1718         char c='*';
1719
1720         if (p == 0) c='.';
1721         if (p == 1) c='+';
1722         if (p == 2) c='*';
1723         if (p == 3) c='\n';
1724         putc(c, stderr);
1725         fflush(stderr);
1726         return 1;
1727         }
1728
1729 int test_kron(BIO *bp, BN_CTX *ctx)
1730         {
1731         BN_GENCB cb;
1732         BIGNUM *a,*b,*r,*t;
1733         int i;
1734         int legendre, kronecker;
1735         int ret = 0;
1736
1737         a = BN_new();
1738         b = BN_new();
1739         r = BN_new();
1740         t = BN_new();
1741         if (a == NULL || b == NULL || r == NULL || t == NULL) goto err;
1742
1743         BN_GENCB_set(&cb, genprime_cb, NULL);
1744
1745         /* We test BN_kronecker(a, b, ctx) just for  b  odd (Jacobi symbol).
1746          * In this case we know that if  b  is prime, then BN_kronecker(a, b, ctx)
1747          * is congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol).
1748          * So we generate a random prime  b  and compare these values
1749          * for a number of random  a's.  (That is, we run the Solovay-Strassen
1750          * primality test to confirm that  b  is prime, except that we
1751          * don't want to test whether  b  is prime but whether BN_kronecker
1752          * works.) */
1753
1754         if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb)) goto err;
1755         b->neg = rand_neg();
1756         putc('\n', stderr);
1757
1758         for (i = 0; i < num0; i++)
1759                 {
1760                 if (!BN_bntest_rand(a, 512, 0, 0)) goto err;
1761                 a->neg = rand_neg();
1762
1763                 /* t := (|b|-1)/2  (note that b is odd) */
1764                 if (!BN_copy(t, b)) goto err;
1765                 t->neg = 0;
1766                 if (!BN_sub_word(t, 1)) goto err;
1767                 if (!BN_rshift1(t, t)) goto err;
1768                 /* r := a^t mod b */
1769                 b->neg=0;
1770
1771                 if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err;
1772                 b->neg=1;
1773
1774                 if (BN_is_word(r, 1))
1775                         legendre = 1;
1776                 else if (BN_is_zero(r))
1777                         legendre = 0;
1778                 else
1779                         {
1780                         if (!BN_add_word(r, 1)) goto err;
1781                         if (0 != BN_ucmp(r, b))
1782                                 {
1783                                 fprintf(stderr, "Legendre symbol computation failed\n");
1784                                 goto err;
1785                                 }
1786                         legendre = -1;
1787                         }
1788
1789                 kronecker = BN_kronecker(a, b, ctx);
1790                 if (kronecker < -1) goto err;
1791                 /* we actually need BN_kronecker(a, |b|) */
1792                 if (a->neg && b->neg)
1793                         kronecker = -kronecker;
1794
1795                 if (legendre != kronecker)
1796                         {
1797                         fprintf(stderr, "legendre != kronecker; a = ");
1798                         BN_print_fp(stderr, a);
1799                         fprintf(stderr, ", b = ");
1800                         BN_print_fp(stderr, b);
1801                         fprintf(stderr, "\n");
1802                         goto err;
1803                         }
1804
1805                 putc('.', stderr);
1806                 fflush(stderr);
1807                 }
1808
1809         putc('\n', stderr);
1810         fflush(stderr);
1811         ret = 1;
1812  err:
1813         if (a != NULL) BN_free(a);
1814         if (b != NULL) BN_free(b);
1815         if (r != NULL) BN_free(r);
1816         if (t != NULL) BN_free(t);
1817         return ret;
1818         }
1819
1820 int test_sqrt(BIO *bp, BN_CTX *ctx)
1821         {
1822         BN_GENCB cb;
1823         BIGNUM *a,*p,*r;
1824         int i, j;
1825         int ret = 0;
1826
1827         a = BN_new();
1828         p = BN_new();
1829         r = BN_new();
1830         if (a == NULL || p == NULL || r == NULL) goto err;
1831
1832         BN_GENCB_set(&cb, genprime_cb, NULL);
1833
1834         for (i = 0; i < 16; i++)
1835                 {
1836                 if (i < 8)
1837                         {
1838                         unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
1839
1840                         if (!BN_set_word(p, primes[i])) goto err;
1841                         }
1842                 else
1843                         {
1844                         if (!BN_set_word(a, 32)) goto err;
1845                         if (!BN_set_word(r, 2*i + 1)) goto err;
1846
1847                         if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb)) goto err;
1848                         putc('\n', stderr);
1849                         }
1850                 p->neg = rand_neg();
1851
1852                 for (j = 0; j < num2; j++)
1853                         {
1854                         /* construct 'a' such that it is a square modulo p,
1855                          * but in general not a proper square and not reduced modulo p */
1856                         if (!BN_bntest_rand(r, 256, 0, 3)) goto err;
1857                         if (!BN_nnmod(r, r, p, ctx)) goto err;
1858                         if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1859                         if (!BN_bntest_rand(a, 256, 0, 3)) goto err;
1860                         if (!BN_nnmod(a, a, p, ctx)) goto err;
1861                         if (!BN_mod_sqr(a, a, p, ctx)) goto err;
1862                         if (!BN_mul(a, a, r, ctx)) goto err;
1863                         if (rand_neg())
1864                                 if (!BN_sub(a, a, p)) goto err;
1865
1866                         if (!BN_mod_sqrt(r, a, p, ctx)) goto err;
1867                         if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1868
1869                         if (!BN_nnmod(a, a, p, ctx)) goto err;
1870
1871                         if (BN_cmp(a, r) != 0)
1872                                 {
1873                                 fprintf(stderr, "BN_mod_sqrt failed: a = ");
1874                                 BN_print_fp(stderr, a);
1875                                 fprintf(stderr, ", r = ");
1876                                 BN_print_fp(stderr, r);
1877                                 fprintf(stderr, ", p = ");
1878                                 BN_print_fp(stderr, p);
1879                                 fprintf(stderr, "\n");
1880                                 goto err;
1881                                 }
1882
1883                         putc('.', stderr);
1884                         fflush(stderr);
1885                         }
1886
1887                 putc('\n', stderr);
1888                 fflush(stderr);
1889                 }
1890         ret = 1;
1891  err:
1892         if (a != NULL) BN_free(a);
1893         if (p != NULL) BN_free(p);
1894         if (r != NULL) BN_free(r);
1895         return ret;
1896         }
1897
1898 int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_)
1899         {
1900         BIGNUM *a,*b,*c,*d;
1901         int i;
1902
1903         b=BN_new();
1904         c=BN_new();
1905         d=BN_new();
1906         BN_one(c);
1907
1908         if(a_)
1909             a=a_;
1910         else
1911             {
1912             a=BN_new();
1913             BN_bntest_rand(a,200,0,0); /**/
1914             a->neg=rand_neg();
1915             }
1916         for (i=0; i<num0; i++)
1917                 {
1918                 BN_lshift(b,a,i+1);
1919                 BN_add(c,c,c);
1920                 if (bp != NULL)
1921                         {
1922                         if (!results)
1923                                 {
1924                                 BN_print(bp,a);
1925                                 BIO_puts(bp," * ");
1926                                 BN_print(bp,c);
1927                                 BIO_puts(bp," - ");
1928                                 }
1929                         BN_print(bp,b);
1930                         BIO_puts(bp,"\n");
1931                         }
1932                 BN_mul(d,a,c,ctx);
1933                 BN_sub(d,d,b);
1934                 if(!BN_is_zero(d))
1935                     {
1936                     fprintf(stderr,"Left shift test failed!\n");
1937                     fprintf(stderr,"a=");
1938                     BN_print_fp(stderr,a);
1939                     fprintf(stderr,"\nb=");
1940                     BN_print_fp(stderr,b);
1941                     fprintf(stderr,"\nc=");
1942                     BN_print_fp(stderr,c);
1943                     fprintf(stderr,"\nd=");
1944                     BN_print_fp(stderr,d);
1945                     fprintf(stderr,"\n");
1946                     return 0;
1947                     }
1948                 }
1949         BN_free(a);
1950         BN_free(b);
1951         BN_free(c);
1952         BN_free(d);
1953         return(1);
1954         }
1955
1956 int test_lshift1(BIO *bp)
1957         {
1958         BIGNUM *a,*b,*c;
1959         int i;
1960
1961         a=BN_new();
1962         b=BN_new();
1963         c=BN_new();
1964
1965         BN_bntest_rand(a,200,0,0); /**/
1966         a->neg=rand_neg();
1967         for (i=0; i<num0; i++)
1968                 {
1969                 BN_lshift1(b,a);
1970                 if (bp != NULL)
1971                         {
1972                         if (!results)
1973                                 {
1974                                 BN_print(bp,a);
1975                                 BIO_puts(bp," * 2");
1976                                 BIO_puts(bp," - ");
1977                                 }
1978                         BN_print(bp,b);
1979                         BIO_puts(bp,"\n");
1980                         }
1981                 BN_add(c,a,a);
1982                 BN_sub(a,b,c);
1983                 if(!BN_is_zero(a))
1984                     {
1985                     fprintf(stderr,"Left shift one test failed!\n");
1986                     return 0;
1987                     }
1988
1989                 BN_copy(a,b);
1990                 }
1991         BN_free(a);
1992         BN_free(b);
1993         BN_free(c);
1994         return(1);
1995         }
1996
1997 int test_rshift(BIO *bp,BN_CTX *ctx)
1998         {
1999         BIGNUM *a,*b,*c,*d,*e;
2000         int i;
2001
2002         a=BN_new();
2003         b=BN_new();
2004         c=BN_new();
2005         d=BN_new();
2006         e=BN_new();
2007         BN_one(c);
2008
2009         BN_bntest_rand(a,200,0,0); /**/
2010         a->neg=rand_neg();
2011         for (i=0; i<num0; i++)
2012                 {
2013                 BN_rshift(b,a,i+1);
2014                 BN_add(c,c,c);
2015                 if (bp != NULL)
2016                         {
2017                         if (!results)
2018                                 {
2019                                 BN_print(bp,a);
2020                                 BIO_puts(bp," / ");
2021                                 BN_print(bp,c);
2022                                 BIO_puts(bp," - ");
2023                                 }
2024                         BN_print(bp,b);
2025                         BIO_puts(bp,"\n");
2026                         }
2027                 BN_div(d,e,a,c,ctx);
2028                 BN_sub(d,d,b);
2029                 if(!BN_is_zero(d))
2030                     {
2031                     fprintf(stderr,"Right shift test failed!\n");
2032                     return 0;
2033                     }
2034                 }
2035         BN_free(a);
2036         BN_free(b);
2037         BN_free(c);
2038         BN_free(d);
2039         BN_free(e);
2040         return(1);
2041         }
2042
2043 int test_rshift1(BIO *bp)
2044         {
2045         BIGNUM *a,*b,*c;
2046         int i;
2047
2048         a=BN_new();
2049         b=BN_new();
2050         c=BN_new();
2051
2052         BN_bntest_rand(a,200,0,0); /**/
2053         a->neg=rand_neg();
2054         for (i=0; i<num0; i++)
2055                 {
2056                 BN_rshift1(b,a);
2057                 if (bp != NULL)
2058                         {
2059                         if (!results)
2060                                 {
2061                                 BN_print(bp,a);
2062                                 BIO_puts(bp," / 2");
2063                                 BIO_puts(bp," - ");
2064                                 }
2065                         BN_print(bp,b);
2066                         BIO_puts(bp,"\n");
2067                         }
2068                 BN_sub(c,a,b);
2069                 BN_sub(c,c,b);
2070                 if(!BN_is_zero(c) && !BN_abs_is_word(c, 1))
2071                     {
2072                     fprintf(stderr,"Right shift one test failed!\n");
2073                     return 0;
2074                     }
2075                 BN_copy(a,b);
2076                 }
2077         BN_free(a);
2078         BN_free(b);
2079         BN_free(c);
2080         return(1);
2081         }
2082
2083 int rand_neg(void)
2084         {
2085         static unsigned int neg=0;
2086         static int sign[8]={0,0,0,1,1,0,1,1};
2087
2088         return(sign[(neg++)%8]);
2089         }