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