crypto/openssl-0.9.7e/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 #include <stdio.h>
  60 #include <stdlib.h>
  61 #include <string.h>
  62
  63 #include "e_os.h"
  64
  65 #include <openssl/bio.h>
  66 #include <openssl/bn.h>
  67 #include <openssl/rand.h>
  68 #include <openssl/x509.h>
  69 #include <openssl/err.h>
  70
  71 const int num0 = 100; /* number of tests */
  72 const int num1 = 50;  /* additional tests for some functions */
  73 const int num2 = 5;   /* number of tests for slow functions */
  74
  75 int test_add(BIO *bp);
  76 int test_sub(BIO *bp);
  77 int test_lshift1(BIO *bp);
  78 int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_);
  79 int test_rshift1(BIO *bp);
  80 int test_rshift(BIO *bp,BN_CTX *ctx);
  81 int test_div(BIO *bp,BN_CTX *ctx);
  82 int test_div_recp(BIO *bp,BN_CTX *ctx);
  83 int test_mul(BIO *bp);
  84 int test_sqr(BIO *bp,BN_CTX *ctx);
  85 int test_mont(BIO *bp,BN_CTX *ctx);
  86 int test_mod(BIO *bp,BN_CTX *ctx);
  87 int test_mod_mul(BIO *bp,BN_CTX *ctx);
  88 int test_mod_exp(BIO *bp,BN_CTX *ctx);
  89 int test_exp(BIO *bp,BN_CTX *ctx);
  90 int test_kron(BIO *bp,BN_CTX *ctx);
  91 int test_sqrt(BIO *bp,BN_CTX *ctx);
  92 int rand_neg(void);
  93 static int results=0;
  94
  95 static unsigned char lst[]="\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9"
  96 "\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0";
  97
  98 static const char rnd_seed[] = "string to make the random number generator think it has entropy";
  99
 100 static void message(BIO *out, char *m)
 101         {
 102         fprintf(stderr, "test %s\n", m);
 103         BIO_puts(out, "print \"test ");
 104         BIO_puts(out, m);
 105         BIO_puts(out, "\\n\"\n");
 106         }
 107
 108 int main(int argc, char *argv[])
 109         {
 110         BN_CTX *ctx;
 111         BIO *out;
 112         char *outfile=NULL;
 113
 114         results = 0;
 115
 116         RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_generate_prime may fail */
 117
 118         argc--;
 119         argv++;
 120         while (argc >= 1)
 121                 {
 122                 if (strcmp(*argv,"-results") == 0)
 123                         results=1;
 124                 else if (strcmp(*argv,"-out") == 0)
 125                         {
 126                         if (--argc < 1) break;
 127                         outfile= *(++argv);
 128                         }
 129                 argc--;
 130                 argv++;
 131                 }
 132
 133
 134         ctx=BN_CTX_new();
 135         if (ctx == NULL) EXIT(1);
 136
 137         out=BIO_new(BIO_s_file());
 138         if (out == NULL) EXIT(1);
 139         if (outfile == NULL)
 140                 {
 141                 BIO_set_fp(out,stdout,BIO_NOCLOSE);
 142                 }
 143         else
 144                 {
 145                 if (!BIO_write_filename(out,outfile))
 146                         {
 147                         perror(outfile);
 148                         EXIT(1);
 149                         }
 150                 }
 151
 152         if (!results)
 153                 BIO_puts(out,"obase=16\nibase=16\n");
 154
 155         message(out,"BN_add");
 156         if (!test_add(out)) goto err;
 157         BIO_flush(out);
 158
 159         message(out,"BN_sub");
 160         if (!test_sub(out)) goto err;
 161         BIO_flush(out);
 162
 163         message(out,"BN_lshift1");
 164         if (!test_lshift1(out)) goto err;
 165         BIO_flush(out);
 166
 167         message(out,"BN_lshift (fixed)");
 168         if (!test_lshift(out,ctx,BN_bin2bn(lst,sizeof(lst)-1,NULL)))
 169             goto err;
 170         BIO_flush(out);
 171
 172         message(out,"BN_lshift");
 173         if (!test_lshift(out,ctx,NULL)) goto err;
 174         BIO_flush(out);
 175
 176         message(out,"BN_rshift1");
 177         if (!test_rshift1(out)) goto err;
 178         BIO_flush(out);
 179
 180         message(out,"BN_rshift");
 181         if (!test_rshift(out,ctx)) goto err;
 182         BIO_flush(out);
 183
 184         message(out,"BN_sqr");
 185         if (!test_sqr(out,ctx)) goto err;
 186         BIO_flush(out);
 187
 188         message(out,"BN_mul");
 189         if (!test_mul(out)) goto err;
 190         BIO_flush(out);
 191
 192         message(out,"BN_div");
 193         if (!test_div(out,ctx)) goto err;
 194         BIO_flush(out);
 195
 196         message(out,"BN_div_recp");
 197         if (!test_div_recp(out,ctx)) goto err;
 198         BIO_flush(out);
 199
 200         message(out,"BN_mod");
 201         if (!test_mod(out,ctx)) goto err;
 202         BIO_flush(out);
 203
 204         message(out,"BN_mod_mul");
 205         if (!test_mod_mul(out,ctx)) goto err;
 206         BIO_flush(out);
 207
 208         message(out,"BN_mont");
 209         if (!test_mont(out,ctx)) goto err;
 210         BIO_flush(out);
 211
 212         message(out,"BN_mod_exp");
 213         if (!test_mod_exp(out,ctx)) goto err;
 214         BIO_flush(out);
 215
 216         message(out,"BN_exp");
 217         if (!test_exp(out,ctx)) goto err;
 218         BIO_flush(out);
 219
 220         message(out,"BN_kronecker");
 221         if (!test_kron(out,ctx)) goto err;
 222         BIO_flush(out);
 223
 224         message(out,"BN_mod_sqrt");
 225         if (!test_sqrt(out,ctx)) goto err;
 226         BIO_flush(out);
 227
 228         BN_CTX_free(ctx);
 229         BIO_free(out);
 230
 231 /**/
 232         EXIT(0);
 233 err:
 234         BIO_puts(out,"1\n"); /* make sure the Perl script fed by bc notices
 235                               * the failure, see test_bn in test/Makefile */
 236         BIO_flush(out);
 237         ERR_load_crypto_strings();
 238         ERR_print_errors_fp(stderr);
 239         EXIT(1);
 240         return(1);
 241         }
 242
 243 int test_add(BIO *bp)
 244         {
 245         BIGNUM a,b,c;
 246         int i;
 247
 248         BN_init(&a);
 249         BN_init(&b);
 250         BN_init(&c);
 251
 252         BN_bntest_rand(&a,512,0,0);
 253         for (i=0; i<num0; i++)
 254                 {
 255                 BN_bntest_rand(&b,450+i,0,0);
 256                 a.neg=rand_neg();
 257                 b.neg=rand_neg();
 258                 BN_add(&c,&a,&b);
 259                 if (bp != NULL)
 260                         {
 261                         if (!results)
 262                                 {
 263                                 BN_print(bp,&a);
 264                                 BIO_puts(bp," + ");
 265                                 BN_print(bp,&b);
 266                                 BIO_puts(bp," - ");
 267                                 }
 268                         BN_print(bp,&c);
 269                         BIO_puts(bp,"\n");
 270                         }
 271                 a.neg=!a.neg;
 272                 b.neg=!b.neg;
 273                 BN_add(&c,&c,&b);
 274                 BN_add(&c,&c,&a);
 275                 if(!BN_is_zero(&c))
 276                     {
 277                     fprintf(stderr,"Add test failed!\n");
 278                     return 0;
 279                     }
 280                 }
 281         BN_free(&a);
 282         BN_free(&b);
 283         BN_free(&c);
 284         return(1);
 285         }
 286
 287 int test_sub(BIO *bp)
 288         {
 289         BIGNUM a,b,c;
 290         int i;
 291
 292         BN_init(&a);
 293         BN_init(&b);
 294         BN_init(&c);
 295
 296         for (i=0; i<num0+num1; i++)
 297                 {
 298                 if (i < num1)
 299                         {
 300                         BN_bntest_rand(&a,512,0,0);
 301                         BN_copy(&b,&a);
 302                         if (BN_set_bit(&a,i)==0) return(0);
 303                         BN_add_word(&b,i);
 304                         }
 305                 else
 306                         {
 307                         BN_bntest_rand(&b,400+i-num1,0,0);
 308                         a.neg=rand_neg();
 309                         b.neg=rand_neg();
 310                         }
 311                 BN_sub(&c,&a,&b);
 312                 if (bp != NULL)
 313                         {
 314                         if (!results)
 315                                 {
 316                                 BN_print(bp,&a);
 317                                 BIO_puts(bp," - ");
 318                                 BN_print(bp,&b);
 319                                 BIO_puts(bp," - ");
 320                                 }
 321                         BN_print(bp,&c);
 322                         BIO_puts(bp,"\n");
 323                         }
 324                 BN_add(&c,&c,&b);
 325                 BN_sub(&c,&c,&a);
 326                 if(!BN_is_zero(&c))
 327                     {
 328                     fprintf(stderr,"Subtract test failed!\n");
 329                     return 0;
 330                     }
 331                 }
 332         BN_free(&a);
 333         BN_free(&b);
 334         BN_free(&c);
 335         return(1);
 336         }
 337
 338 int test_div(BIO *bp, BN_CTX *ctx)
 339         {
 340         BIGNUM a,b,c,d,e;
 341         int i;
 342
 343         BN_init(&a);
 344         BN_init(&b);
 345         BN_init(&c);
 346         BN_init(&d);
 347         BN_init(&e);
 348
 349         for (i=0; i<num0+num1; i++)
 350                 {
 351                 if (i < num1)
 352                         {
 353                         BN_bntest_rand(&a,400,0,0);
 354                         BN_copy(&b,&a);
 355                         BN_lshift(&a,&a,i);
 356                         BN_add_word(&a,i);
 357                         }
 358                 else
 359                         BN_bntest_rand(&b,50+3*(i-num1),0,0);
 360                 a.neg=rand_neg();
 361                 b.neg=rand_neg();
 362                 BN_div(&d,&c,&a,&b,ctx);
 363                 if (bp != NULL)
 364                         {
 365                         if (!results)
 366                                 {
 367                                 BN_print(bp,&a);
 368                                 BIO_puts(bp," / ");
 369                                 BN_print(bp,&b);
 370                                 BIO_puts(bp," - ");
 371                                 }
 372                         BN_print(bp,&d);
 373                         BIO_puts(bp,"\n");
 374
 375                         if (!results)
 376                                 {
 377                                 BN_print(bp,&a);
 378                                 BIO_puts(bp," % ");
 379                                 BN_print(bp,&b);
 380                                 BIO_puts(bp," - ");
 381                                 }
 382                         BN_print(bp,&c);
 383                         BIO_puts(bp,"\n");
 384                         }
 385                 BN_mul(&e,&d,&b,ctx);
 386                 BN_add(&d,&e,&c);
 387                 BN_sub(&d,&d,&a);
 388                 if(!BN_is_zero(&d))
 389                     {
 390                     fprintf(stderr,"Division test failed!\n");
 391                     return 0;
 392                     }
 393                 }
 394         BN_free(&a);
 395         BN_free(&b);
 396         BN_free(&c);
 397         BN_free(&d);
 398         BN_free(&e);
 399         return(1);
 400         }
 401
 402 int test_div_recp(BIO *bp, BN_CTX *ctx)
 403         {
 404         BIGNUM a,b,c,d,e;
 405         BN_RECP_CTX recp;
 406         int i;
 407
 408         BN_RECP_CTX_init(&recp);
 409         BN_init(&a);
 410         BN_init(&b);
 411         BN_init(&c);
 412         BN_init(&d);
 413         BN_init(&e);
 414
 415         for (i=0; i<num0+num1; i++)
 416                 {
 417                 if (i < num1)
 418                         {
 419                         BN_bntest_rand(&a,400,0,0);
 420                         BN_copy(&b,&a);
 421                         BN_lshift(&a,&a,i);
 422                         BN_add_word(&a,i);
 423                         }
 424                 else
 425                         BN_bntest_rand(&b,50+3*(i-num1),0,0);
 426                 a.neg=rand_neg();
 427                 b.neg=rand_neg();
 428                 BN_RECP_CTX_set(&recp,&b,ctx);
 429                 BN_div_recp(&d,&c,&a,&recp,ctx);
 430                 if (bp != NULL)
 431                         {
 432                         if (!results)
 433                                 {
 434                                 BN_print(bp,&a);
 435                                 BIO_puts(bp," / ");
 436                                 BN_print(bp,&b);
 437                                 BIO_puts(bp," - ");
 438                                 }
 439                         BN_print(bp,&d);
 440                         BIO_puts(bp,"\n");
 441
 442                         if (!results)
 443                                 {
 444                                 BN_print(bp,&a);
 445                                 BIO_puts(bp," % ");
 446                                 BN_print(bp,&b);
 447                                 BIO_puts(bp," - ");
 448                                 }
 449                         BN_print(bp,&c);
 450                         BIO_puts(bp,"\n");
 451                         }
 452                 BN_mul(&e,&d,&b,ctx);
 453                 BN_add(&d,&e,&c);
 454                 BN_sub(&d,&d,&a);
 455                 if(!BN_is_zero(&d))
 456                     {
 457                     fprintf(stderr,"Reciprocal division test failed!\n");
 458                     fprintf(stderr,"a=");
 459                     BN_print_fp(stderr,&a);
 460                     fprintf(stderr,"\nb=");
 461                     BN_print_fp(stderr,&b);
 462                     fprintf(stderr,"\n");
 463                     return 0;
 464                     }
 465                 }
 466         BN_free(&a);
 467         BN_free(&b);
 468         BN_free(&c);
 469         BN_free(&d);
 470         BN_free(&e);
 471         BN_RECP_CTX_free(&recp);
 472         return(1);
 473         }
 474
 475 int test_mul(BIO *bp)
 476         {
 477         BIGNUM a,b,c,d,e;
 478         int i;
 479         BN_CTX *ctx;
 480
 481         ctx = BN_CTX_new();
 482         if (ctx == NULL) EXIT(1);
 483
 484         BN_init(&a);
 485         BN_init(&b);
 486         BN_init(&c);
 487         BN_init(&d);
 488         BN_init(&e);
 489
 490         for (i=0; i<num0+num1; i++)
 491                 {
 492                 if (i <= num1)
 493                         {
 494                         BN_bntest_rand(&a,100,0,0);
 495                         BN_bntest_rand(&b,100,0,0);
 496                         }
 497                 else
 498                         BN_bntest_rand(&b,i-num1,0,0);
 499                 a.neg=rand_neg();
 500                 b.neg=rand_neg();
 501                 BN_mul(&c,&a,&b,ctx);
 502                 if (bp != NULL)
 503                         {
 504                         if (!results)
 505                                 {
 506                                 BN_print(bp,&a);
 507                                 BIO_puts(bp," * ");
 508                                 BN_print(bp,&b);
 509                                 BIO_puts(bp," - ");
 510                                 }
 511                         BN_print(bp,&c);
 512                         BIO_puts(bp,"\n");
 513                         }
 514                 BN_div(&d,&e,&c,&a,ctx);
 515                 BN_sub(&d,&d,&b);
 516                 if(!BN_is_zero(&d) || !BN_is_zero(&e))
 517                     {
 518                     fprintf(stderr,"Multiplication test failed!\n");
 519                     return 0;
 520                     }
 521                 }
 522         BN_free(&a);
 523         BN_free(&b);
 524         BN_free(&c);
 525         BN_free(&d);
 526         BN_free(&e);
 527         BN_CTX_free(ctx);
 528         return(1);
 529         }
 530
 531 int test_sqr(BIO *bp, BN_CTX *ctx)
 532         {
 533         BIGNUM a,c,d,e;
 534         int i;
 535
 536         BN_init(&a);
 537         BN_init(&c);
 538         BN_init(&d);
 539         BN_init(&e);
 540
 541         for (i=0; i<num0; i++)
 542                 {
 543                 BN_bntest_rand(&a,40+i*10,0,0);
 544                 a.neg=rand_neg();
 545                 BN_sqr(&c,&a,ctx);
 546                 if (bp != NULL)
 547                         {
 548                         if (!results)
 549                                 {
 550                                 BN_print(bp,&a);
 551                                 BIO_puts(bp," * ");
 552                                 BN_print(bp,&a);
 553                                 BIO_puts(bp," - ");
 554                                 }
 555                         BN_print(bp,&c);
 556                         BIO_puts(bp,"\n");
 557                         }
 558                 BN_div(&d,&e,&c,&a,ctx);
 559                 BN_sub(&d,&d,&a);
 560                 if(!BN_is_zero(&d) || !BN_is_zero(&e))
 561                     {
 562                     fprintf(stderr,"Square test failed!\n");
 563                     return 0;
 564                     }
 565                 }
 566         BN_free(&a);
 567         BN_free(&c);
 568         BN_free(&d);
 569         BN_free(&e);
 570         return(1);
 571         }
 572
 573 int test_mont(BIO *bp, BN_CTX *ctx)
 574         {
 575         BIGNUM a,b,c,d,A,B;
 576         BIGNUM n;
 577         int i;
 578         BN_MONT_CTX *mont;
 579
 580         BN_init(&a);
 581         BN_init(&b);
 582         BN_init(&c);
 583         BN_init(&d);
 584         BN_init(&A);
 585         BN_init(&B);
 586         BN_init(&n);
 587
 588         mont=BN_MONT_CTX_new();
 589
 590         BN_bntest_rand(&a,100,0,0); /**/
 591         BN_bntest_rand(&b,100,0,0); /**/
 592         for (i=0; i<num2; i++)
 593                 {
 594                 int bits = (200*(i+1))/num2;
 595
 596                 if (bits == 0)
 597                         continue;
 598                 BN_bntest_rand(&n,bits,0,1);
 599                 BN_MONT_CTX_set(mont,&n,ctx);
 600
 601                 BN_nnmod(&a,&a,&n,ctx);
 602                 BN_nnmod(&b,&b,&n,ctx);
 603
 604                 BN_to_montgomery(&A,&a,mont,ctx);
 605                 BN_to_montgomery(&B,&b,mont,ctx);
 606
 607                 BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/
 608                 BN_from_montgomery(&A,&c,mont,ctx);/**/
 609                 if (bp != NULL)
 610                         {
 611                         if (!results)
 612                                 {
 613 #ifdef undef
 614 fprintf(stderr,"%d * %d %% %d\n",
 615 BN_num_bits(&a),
 616 BN_num_bits(&b),
 617 BN_num_bits(mont->N));
 618 #endif
 619                                 BN_print(bp,&a);
 620                                 BIO_puts(bp," * ");
 621                                 BN_print(bp,&b);
 622                                 BIO_puts(bp," % ");
 623                                 BN_print(bp,&(mont->N));
 624                                 BIO_puts(bp," - ");
 625                                 }
 626                         BN_print(bp,&A);
 627                         BIO_puts(bp,"\n");
 628                         }
 629                 BN_mod_mul(&d,&a,&b,&n,ctx);
 630                 BN_sub(&d,&d,&A);
 631                 if(!BN_is_zero(&d))
 632                     {
 633                     fprintf(stderr,"Montgomery multiplication test failed!\n");
 634                     return 0;
 635                     }
 636                 }
 637         BN_MONT_CTX_free(mont);
 638         BN_free(&a);
 639         BN_free(&b);
 640         BN_free(&c);
 641         BN_free(&d);
 642         BN_free(&A);
 643         BN_free(&B);
 644         BN_free(&n);
 645         return(1);
 646         }
 647
 648 int test_mod(BIO *bp, BN_CTX *ctx)
 649         {
 650         BIGNUM *a,*b,*c,*d,*e;
 651         int i;
 652
 653         a=BN_new();
 654         b=BN_new();
 655         c=BN_new();
 656         d=BN_new();
 657         e=BN_new();
 658
 659         BN_bntest_rand(a,1024,0,0); /**/
 660         for (i=0; i<num0; i++)
 661                 {
 662                 BN_bntest_rand(b,450+i*10,0,0); /**/
 663                 a->neg=rand_neg();
 664                 b->neg=rand_neg();
 665                 BN_mod(c,a,b,ctx);/**/
 666                 if (bp != NULL)
 667                         {
 668                         if (!results)
 669                                 {
 670                                 BN_print(bp,a);
 671                                 BIO_puts(bp," % ");
 672                                 BN_print(bp,b);
 673                                 BIO_puts(bp," - ");
 674                                 }
 675                         BN_print(bp,c);
 676                         BIO_puts(bp,"\n");
 677                         }
 678                 BN_div(d,e,a,b,ctx);
 679                 BN_sub(e,e,c);
 680                 if(!BN_is_zero(e))
 681                     {
 682                     fprintf(stderr,"Modulo test failed!\n");
 683                     return 0;
 684                     }
 685                 }
 686         BN_free(a);
 687         BN_free(b);
 688         BN_free(c);
 689         BN_free(d);
 690         BN_free(e);
 691         return(1);
 692         }
 693
 694 int test_mod_mul(BIO *bp, BN_CTX *ctx)
 695         {
 696         BIGNUM *a,*b,*c,*d,*e;
 697         int i,j;
 698
 699         a=BN_new();
 700         b=BN_new();
 701         c=BN_new();
 702         d=BN_new();
 703         e=BN_new();
 704
 705         for (j=0; j<3; j++) {
 706         BN_bntest_rand(c,1024,0,0); /**/
 707         for (i=0; i<num0; i++)
 708                 {
 709                 BN_bntest_rand(a,475+i*10,0,0); /**/
 710                 BN_bntest_rand(b,425+i*11,0,0); /**/
 711                 a->neg=rand_neg();
 712                 b->neg=rand_neg();
 713                 if (!BN_mod_mul(e,a,b,c,ctx))
 714                         {
 715                         unsigned long l;
 716
 717                         while ((l=ERR_get_error()))
 718                                 fprintf(stderr,"ERROR:%s\n",
 719                                         ERR_error_string(l,NULL));
 720                         EXIT(1);
 721                         }
 722                 if (bp != NULL)
 723                         {
 724                         if (!results)
 725                                 {
 726                                 BN_print(bp,a);
 727                                 BIO_puts(bp," * ");
 728                                 BN_print(bp,b);
 729                                 BIO_puts(bp," % ");
 730                                 BN_print(bp,c);
 731                                 if ((a->neg ^ b->neg) && !BN_is_zero(e))
 732                                         {
 733                                         /* If  (a*b) % c  is negative,  c  must be added
 734                                          * in order to obtain the normalized remainder
 735                                          * (new with OpenSSL 0.9.7, previous versions of
 736                                          * BN_mod_mul could generate negative results)
 737                                          */
 738                                         BIO_puts(bp," + ");
 739                                         BN_print(bp,c);
 740                                         }
 741                                 BIO_puts(bp," - ");
 742                                 }
 743                         BN_print(bp,e);
 744                         BIO_puts(bp,"\n");
 745                         }
 746                 BN_mul(d,a,b,ctx);
 747                 BN_sub(d,d,e);
 748                 BN_div(a,b,d,c,ctx);
 749                 if(!BN_is_zero(b))
 750                     {
 751                     fprintf(stderr,"Modulo multiply test failed!\n");
 752                     ERR_print_errors_fp(stderr);
 753                     return 0;
 754                     }
 755                 }
 756         }
 757         BN_free(a);
 758         BN_free(b);
 759         BN_free(c);
 760         BN_free(d);
 761         BN_free(e);
 762         return(1);
 763         }
 764
 765 int test_mod_exp(BIO *bp, BN_CTX *ctx)
 766         {
 767         BIGNUM *a,*b,*c,*d,*e;
 768         int i;
 769
 770         a=BN_new();
 771         b=BN_new();
 772         c=BN_new();
 773         d=BN_new();
 774         e=BN_new();
 775
 776         BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
 777         for (i=0; i<num2; i++)
 778                 {
 779                 BN_bntest_rand(a,20+i*5,0,0); /**/
 780                 BN_bntest_rand(b,2+i,0,0); /**/
 781
 782                 if (!BN_mod_exp(d,a,b,c,ctx))
 783                         return(00);
 784
 785                 if (bp != NULL)
 786                         {
 787                         if (!results)
 788                                 {
 789                                 BN_print(bp,a);
 790                                 BIO_puts(bp," ^ ");
 791                                 BN_print(bp,b);
 792                                 BIO_puts(bp," % ");
 793                                 BN_print(bp,c);
 794                                 BIO_puts(bp," - ");
 795                                 }
 796                         BN_print(bp,d);
 797                         BIO_puts(bp,"\n");
 798                         }
 799                 BN_exp(e,a,b,ctx);
 800                 BN_sub(e,e,d);
 801                 BN_div(a,b,e,c,ctx);
 802                 if(!BN_is_zero(b))
 803                     {
 804                     fprintf(stderr,"Modulo exponentiation test failed!\n");
 805                     return 0;
 806                     }
 807                 }
 808         BN_free(a);
 809         BN_free(b);
 810         BN_free(c);
 811         BN_free(d);
 812         BN_free(e);
 813         return(1);
 814         }
 815
 816 int test_exp(BIO *bp, BN_CTX *ctx)
 817         {
 818         BIGNUM *a,*b,*d,*e,*one;
 819         int i;
 820
 821         a=BN_new();
 822         b=BN_new();
 823         d=BN_new();
 824         e=BN_new();
 825         one=BN_new();
 826         BN_one(one);
 827
 828         for (i=0; i<num2; i++)
 829                 {
 830                 BN_bntest_rand(a,20+i*5,0,0); /**/
 831                 BN_bntest_rand(b,2+i,0,0); /**/
 832
 833                 if (!BN_exp(d,a,b,ctx))
 834                         return(00);
 835
 836                 if (bp != NULL)
 837                         {
 838                         if (!results)
 839                                 {
 840                                 BN_print(bp,a);
 841                                 BIO_puts(bp," ^ ");
 842                                 BN_print(bp,b);
 843                                 BIO_puts(bp," - ");
 844                                 }
 845                         BN_print(bp,d);
 846                         BIO_puts(bp,"\n");
 847                         }
 848                 BN_one(e);
 849                 for( ; !BN_is_zero(b) ; BN_sub(b,b,one))
 850                     BN_mul(e,e,a,ctx);
 851                 BN_sub(e,e,d);
 852                 if(!BN_is_zero(e))
 853                     {
 854                     fprintf(stderr,"Exponentiation test failed!\n");
 855                     return 0;
 856                     }
 857                 }
 858         BN_free(a);
 859         BN_free(b);
 860         BN_free(d);
 861         BN_free(e);
 862         BN_free(one);
 863         return(1);
 864         }
 865
 866 static void genprime_cb(int p, int n, void *arg)
 867         {
 868         char c='*';
 869
 870         if (p == 0) c='.';
 871         if (p == 1) c='+';
 872         if (p == 2) c='*';
 873         if (p == 3) c='\n';
 874         putc(c, stderr);
 875         fflush(stderr);
 876         (void)n;
 877         (void)arg;
 878         }
 879
 880 int test_kron(BIO *bp, BN_CTX *ctx)
 881         {
 882         BIGNUM *a,*b,*r,*t;
 883         int i;
 884         int legendre, kronecker;
 885         int ret = 0;
 886
 887         a = BN_new();
 888         b = BN_new();
 889         r = BN_new();
 890         t = BN_new();
 891         if (a == NULL || b == NULL || r == NULL || t == NULL) goto err;
 892
 893         /* We test BN_kronecker(a, b, ctx) just for  b  odd (Jacobi symbol).
 894          * In this case we know that if  b  is prime, then BN_kronecker(a, b, ctx)
 895          * is congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol).
 896          * So we generate a random prime  b  and compare these values
 897          * for a number of random  a's.  (That is, we run the Solovay-Strassen
 898          * primality test to confirm that  b  is prime, except that we
 899          * don't want to test whether  b  is prime but whether BN_kronecker
 900          * works.) */
 901
 902         if (!BN_generate_prime(b, 512, 0, NULL, NULL, genprime_cb, NULL)) goto err;
 903         b->neg = rand_neg();
 904         putc('\n', stderr);
 905
 906         for (i = 0; i < num0; i++)
 907                 {
 908                 if (!BN_bntest_rand(a, 512, 0, 0)) goto err;
 909                 a->neg = rand_neg();
 910
 911                 /* t := (|b|-1)/2  (note that b is odd) */
 912                 if (!BN_copy(t, b)) goto err;
 913                 t->neg = 0;
 914                 if (!BN_sub_word(t, 1)) goto err;
 915                 if (!BN_rshift1(t, t)) goto err;
 916                 /* r := a^t mod b */
 917                 b->neg=0;
 918
 919                 if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err;
 920                 b->neg=1;
 921
 922                 if (BN_is_word(r, 1))
 923                         legendre = 1;
 924                 else if (BN_is_zero(r))
 925                         legendre = 0;
 926                 else
 927                         {
 928                         if (!BN_add_word(r, 1)) goto err;
 929                         if (0 != BN_ucmp(r, b))
 930                                 {
 931                                 fprintf(stderr, "Legendre symbol computation failed\n");
 932                                 goto err;
 933                                 }
 934                         legendre = -1;
 935                         }
 936
 937                 kronecker = BN_kronecker(a, b, ctx);
 938                 if (kronecker < -1) goto err;
 939                 /* we actually need BN_kronecker(a, |b|) */
 940                 if (a->neg && b->neg)
 941                         kronecker = -kronecker;
 942
 943                 if (legendre != kronecker)
 944                         {
 945                         fprintf(stderr, "legendre != kronecker; a = ");
 946                         BN_print_fp(stderr, a);
 947                         fprintf(stderr, ", b = ");
 948                         BN_print_fp(stderr, b);
 949                         fprintf(stderr, "\n");
 950                         goto err;
 951                         }
 952
 953                 putc('.', stderr);
 954                 fflush(stderr);
 955                 }
 956
 957         putc('\n', stderr);
 958         fflush(stderr);
 959         ret = 1;
 960  err:
 961         if (a != NULL) BN_free(a);
 962         if (b != NULL) BN_free(b);
 963         if (r != NULL) BN_free(r);
 964         if (t != NULL) BN_free(t);
 965         return ret;
 966         }
 967
 968 int test_sqrt(BIO *bp, BN_CTX *ctx)
 969         {
 970         BIGNUM *a,*p,*r;
 971         int i, j;
 972         int ret = 0;
 973
 974         a = BN_new();
 975         p = BN_new();
 976         r = BN_new();
 977         if (a == NULL || p == NULL || r == NULL) goto err;
 978
 979         for (i = 0; i < 16; i++)
 980                 {
 981                 if (i < 8)
 982                         {
 983                         unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
 984
 985                         if (!BN_set_word(p, primes[i])) goto err;
 986                         }
 987                 else
 988                         {
 989                         if (!BN_set_word(a, 32)) goto err;
 990                         if (!BN_set_word(r, 2*i + 1)) goto err;
 991
 992                         if (!BN_generate_prime(p, 256, 0, a, r, genprime_cb, NULL)) goto err;
 993                         putc('\n', stderr);
 994                         }
 995                 p->neg = rand_neg();
 996
 997                 for (j = 0; j < num2; j++)
 998                         {
 999                         /* construct 'a' such that it is a square modulo p,
1000                          * but in general not a proper square and not reduced modulo p */
1001                         if (!BN_bntest_rand(r, 256, 0, 3)) goto err;
1002                         if (!BN_nnmod(r, r, p, ctx)) goto err;
1003                         if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1004                         if (!BN_bntest_rand(a, 256, 0, 3)) goto err;
1005                         if (!BN_nnmod(a, a, p, ctx)) goto err;
1006                         if (!BN_mod_sqr(a, a, p, ctx)) goto err;
1007                         if (!BN_mul(a, a, r, ctx)) goto err;
1008                         if (rand_neg())
1009                                 if (!BN_sub(a, a, p)) goto err;
1010
1011                         if (!BN_mod_sqrt(r, a, p, ctx)) goto err;
1012                         if (!BN_mod_sqr(r, r, p, ctx)) goto err;
1013
1014                         if (!BN_nnmod(a, a, p, ctx)) goto err;
1015
1016                         if (BN_cmp(a, r) != 0)
1017                                 {
1018                                 fprintf(stderr, "BN_mod_sqrt failed: a = ");
1019                                 BN_print_fp(stderr, a);
1020                                 fprintf(stderr, ", r = ");
1021                                 BN_print_fp(stderr, r);
1022                                 fprintf(stderr, ", p = ");
1023                                 BN_print_fp(stderr, p);
1024                                 fprintf(stderr, "\n");
1025                                 goto err;
1026                                 }
1027
1028                         putc('.', stderr);
1029                         fflush(stderr);
1030                         }
1031
1032                 putc('\n', stderr);
1033                 fflush(stderr);
1034                 }
1035         ret = 1;
1036  err:
1037         if (a != NULL) BN_free(a);
1038         if (p != NULL) BN_free(p);
1039         if (r != NULL) BN_free(r);
1040         return ret;
1041         }
1042
1043 int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_)
1044         {
1045         BIGNUM *a,*b,*c,*d;
1046         int i;
1047
1048         b=BN_new();
1049         c=BN_new();
1050         d=BN_new();
1051         BN_one(c);
1052
1053         if(a_)
1054             a=a_;
1055         else
1056             {
1057             a=BN_new();
1058             BN_bntest_rand(a,200,0,0); /**/
1059             a->neg=rand_neg();
1060             }
1061         for (i=0; i<num0; i++)
1062                 {
1063                 BN_lshift(b,a,i+1);
1064                 BN_add(c,c,c);
1065                 if (bp != NULL)
1066                         {
1067                         if (!results)
1068                                 {
1069                                 BN_print(bp,a);
1070                                 BIO_puts(bp," * ");
1071                                 BN_print(bp,c);
1072                                 BIO_puts(bp," - ");
1073                                 }
1074                         BN_print(bp,b);
1075                         BIO_puts(bp,"\n");
1076                         }
1077                 BN_mul(d,a,c,ctx);
1078                 BN_sub(d,d,b);
1079                 if(!BN_is_zero(d))
1080                     {
1081                     fprintf(stderr,"Left shift test failed!\n");
1082                     fprintf(stderr,"a=");
1083                     BN_print_fp(stderr,a);
1084                     fprintf(stderr,"\nb=");
1085                     BN_print_fp(stderr,b);
1086                     fprintf(stderr,"\nc=");
1087                     BN_print_fp(stderr,c);
1088                     fprintf(stderr,"\nd=");
1089                     BN_print_fp(stderr,d);
1090                     fprintf(stderr,"\n");
1091                     return 0;
1092                     }
1093                 }
1094         BN_free(a);
1095         BN_free(b);
1096         BN_free(c);
1097         BN_free(d);
1098         return(1);
1099         }
1100
1101 int test_lshift1(BIO *bp)
1102         {
1103         BIGNUM *a,*b,*c;
1104         int i;
1105
1106         a=BN_new();
1107         b=BN_new();
1108         c=BN_new();
1109
1110         BN_bntest_rand(a,200,0,0); /**/
1111         a->neg=rand_neg();
1112         for (i=0; i<num0; i++)
1113                 {
1114                 BN_lshift1(b,a);
1115                 if (bp != NULL)
1116                         {
1117                         if (!results)
1118                                 {
1119                                 BN_print(bp,a);
1120                                 BIO_puts(bp," * 2");
1121                                 BIO_puts(bp," - ");
1122                                 }
1123                         BN_print(bp,b);
1124                         BIO_puts(bp,"\n");
1125                         }
1126                 BN_add(c,a,a);
1127                 BN_sub(a,b,c);
1128                 if(!BN_is_zero(a))
1129                     {
1130                     fprintf(stderr,"Left shift one test failed!\n");
1131                     return 0;
1132                     }
1133
1134                 BN_copy(a,b);
1135                 }
1136         BN_free(a);
1137         BN_free(b);
1138         BN_free(c);
1139         return(1);
1140         }
1141
1142 int test_rshift(BIO *bp,BN_CTX *ctx)
1143         {
1144         BIGNUM *a,*b,*c,*d,*e;
1145         int i;
1146
1147         a=BN_new();
1148         b=BN_new();
1149         c=BN_new();
1150         d=BN_new();
1151         e=BN_new();
1152         BN_one(c);
1153
1154         BN_bntest_rand(a,200,0,0); /**/
1155         a->neg=rand_neg();
1156         for (i=0; i<num0; i++)
1157                 {
1158                 BN_rshift(b,a,i+1);
1159                 BN_add(c,c,c);
1160                 if (bp != NULL)
1161                         {
1162                         if (!results)
1163                                 {
1164                                 BN_print(bp,a);
1165                                 BIO_puts(bp," / ");
1166                                 BN_print(bp,c);
1167                                 BIO_puts(bp," - ");
1168                                 }
1169                         BN_print(bp,b);
1170                         BIO_puts(bp,"\n");
1171                         }
1172                 BN_div(d,e,a,c,ctx);
1173                 BN_sub(d,d,b);
1174                 if(!BN_is_zero(d))
1175                     {
1176                     fprintf(stderr,"Right shift test failed!\n");
1177                     return 0;
1178                     }
1179                 }
1180         BN_free(a);
1181         BN_free(b);
1182         BN_free(c);
1183         BN_free(d);
1184         BN_free(e);
1185         return(1);
1186         }
1187
1188 int test_rshift1(BIO *bp)
1189         {
1190         BIGNUM *a,*b,*c;
1191         int i;
1192
1193         a=BN_new();
1194         b=BN_new();
1195         c=BN_new();
1196
1197         BN_bntest_rand(a,200,0,0); /**/
1198         a->neg=rand_neg();
1199         for (i=0; i<num0; i++)
1200                 {
1201                 BN_rshift1(b,a);
1202                 if (bp != NULL)
1203                         {
1204                         if (!results)
1205                                 {
1206                                 BN_print(bp,a);
1207                                 BIO_puts(bp," / 2");
1208                                 BIO_puts(bp," - ");
1209                                 }
1210                         BN_print(bp,b);
1211                         BIO_puts(bp,"\n");
1212                         }
1213                 BN_sub(c,a,b);
1214                 BN_sub(c,c,b);
1215                 if(!BN_is_zero(c) && !BN_abs_is_word(c, 1))
1216                     {
1217                     fprintf(stderr,"Right shift one test failed!\n");
1218                     return 0;
1219                     }
1220                 BN_copy(a,b);
1221                 }
1222         BN_free(a);
1223         BN_free(b);
1224         BN_free(c);
1225         return(1);
1226         }
1227
1228 int rand_neg(void)
1229         {
1230         static unsigned int neg=0;
1231         static int sign[8]={0,0,0,1,1,0,1,1};
1232
1233         return(sign[(neg++)%8]);
1234         }