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