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