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