test/bntest.c

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