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
 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     int i = sizeof(w) * 8;
 506     char *fmt = NULL;
 507     unsigned char byte;
 508
 509     do {
 510         i -= 8;
 511         byte = (unsigned char)(w >> i);
 512         if (fmt == NULL)
 513             fmt = byte ? "%X" : NULL;
 514         else
 515             fmt = "%02X";
 516
 517         if (fmt != NULL)
 518             BIO_printf(bp, fmt, byte);
 519     } while (i);
 520
 521     /* If we haven't printed anything, at least print a zero! */
 522     if (fmt == NULL)
 523         BIO_printf(bp, "0");
 524 }
 525
 526 int test_div_word(BIO *bp)
 527 {
 528     BIGNUM *a, *b;
 529     BN_ULONG r, s;
 530     int i;
 531
 532     a = BN_new();
 533     b = BN_new();
 534
 535     for (i = 0; i < num0; i++) {
 536         do {
 537             BN_bntest_rand(a, 512, -1, 0);
 538             BN_bntest_rand(b, BN_BITS2, -1, 0);
 539         } while (BN_is_zero(b));
 540
 541         s = b->d[0];
 542         BN_copy(b, a);
 543         r = BN_div_word(b, s);
 544
 545         if (bp != NULL) {
 546             if (!results) {
 547                 BN_print(bp, a);
 548                 BIO_puts(bp, " / ");
 549                 print_word(bp, s);
 550                 BIO_puts(bp, " - ");
 551             }
 552             BN_print(bp, b);
 553             BIO_puts(bp, "\n");
 554
 555             if (!results) {
 556                 BN_print(bp, a);
 557                 BIO_puts(bp, " % ");
 558                 print_word(bp, s);
 559                 BIO_puts(bp, " - ");
 560             }
 561             print_word(bp, r);
 562             BIO_puts(bp, "\n");
 563         }
 564         BN_mul_word(b, s);
 565         BN_add_word(b, r);
 566         BN_sub(b, a, b);
 567         if (!BN_is_zero(b)) {
 568             fprintf(stderr, "Division (word) test failed!\n");
 569             return 0;
 570         }
 571     }
 572     BN_free(a);
 573     BN_free(b);
 574     return (1);
 575 }
 576
 577 int test_div_recp(BIO *bp, BN_CTX *ctx)
 578 {
 579     BIGNUM *a, *b, *c, *d, *e;
 580     BN_RECP_CTX *recp;
 581     int i;
 582
 583     recp = BN_RECP_CTX_new();
 584     a = BN_new();
 585     b = BN_new();
 586     c = BN_new();
 587     d = BN_new();
 588     e = BN_new();
 589
 590     for (i = 0; i < num0 + num1; i++) {
 591         if (i < num1) {
 592             BN_bntest_rand(a, 400, 0, 0);
 593             BN_copy(b, a);
 594             BN_lshift(a, a, i);
 595             BN_add_word(a, i);
 596         } else
 597             BN_bntest_rand(b, 50 + 3 * (i - num1), 0, 0);
 598         a->neg = rand_neg();
 599         b->neg = rand_neg();
 600         BN_RECP_CTX_set(recp, b, ctx);
 601         BN_div_recp(d, c, a, recp, ctx);
 602         if (bp != NULL) {
 603             if (!results) {
 604                 BN_print(bp, a);
 605                 BIO_puts(bp, " / ");
 606                 BN_print(bp, b);
 607                 BIO_puts(bp, " - ");
 608             }
 609             BN_print(bp, d);
 610             BIO_puts(bp, "\n");
 611
 612             if (!results) {
 613                 BN_print(bp, a);
 614                 BIO_puts(bp, " % ");
 615                 BN_print(bp, b);
 616                 BIO_puts(bp, " - ");
 617             }
 618             BN_print(bp, c);
 619             BIO_puts(bp, "\n");
 620         }
 621         BN_mul(e, d, b, ctx);
 622         BN_add(d, e, c);
 623         BN_sub(d, d, a);
 624         if (!BN_is_zero(d)) {
 625             fprintf(stderr, "Reciprocal division test failed!\n");
 626             fprintf(stderr, "a=");
 627             BN_print_fp(stderr, a);
 628             fprintf(stderr, "\nb=");
 629             BN_print_fp(stderr, b);
 630             fprintf(stderr, "\n");
 631             return 0;
 632         }
 633     }
 634     BN_free(a);
 635     BN_free(b);
 636     BN_free(c);
 637     BN_free(d);
 638     BN_free(e);
 639     BN_RECP_CTX_free(recp);
 640     return (1);
 641 }
 642
 643 int test_mul(BIO *bp)
 644 {
 645     BIGNUM *a, *b, *c, *d, *e;
 646     int i;
 647     BN_CTX *ctx;
 648
 649     ctx = BN_CTX_new();
 650     if (ctx == NULL)
 651         EXIT(1);
 652
 653     a = BN_new();
 654     b = BN_new();
 655     c = BN_new();
 656     d = BN_new();
 657     e = BN_new();
 658
 659     for (i = 0; i < num0 + num1; i++) {
 660         if (i <= num1) {
 661             BN_bntest_rand(a, 100, 0, 0);
 662             BN_bntest_rand(b, 100, 0, 0);
 663         } else
 664             BN_bntest_rand(b, i - num1, 0, 0);
 665         a->neg = rand_neg();
 666         b->neg = rand_neg();
 667         BN_mul(c, a, b, ctx);
 668         if (bp != NULL) {
 669             if (!results) {
 670                 BN_print(bp, a);
 671                 BIO_puts(bp, " * ");
 672                 BN_print(bp, b);
 673                 BIO_puts(bp, " - ");
 674             }
 675             BN_print(bp, c);
 676             BIO_puts(bp, "\n");
 677         }
 678         BN_div(d, e, c, a, ctx);
 679         BN_sub(d, d, b);
 680         if (!BN_is_zero(d) || !BN_is_zero(e)) {
 681             fprintf(stderr, "Multiplication test failed!\n");
 682             return 0;
 683         }
 684     }
 685     BN_free(a);
 686     BN_free(b);
 687     BN_free(c);
 688     BN_free(d);
 689     BN_free(e);
 690     BN_CTX_free(ctx);
 691     return (1);
 692 }
 693
 694 int test_sqr(BIO *bp, BN_CTX *ctx)
 695 {
 696     BIGNUM *a, *c, *d, *e;
 697     int i, ret = 0;
 698
 699     a = BN_new();
 700     c = BN_new();
 701     d = BN_new();
 702     e = BN_new();
 703     if (a == NULL || c == NULL || d == NULL || e == NULL) {
 704         goto err;
 705     }
 706
 707     for (i = 0; i < num0; i++) {
 708         BN_bntest_rand(a, 40 + i * 10, 0, 0);
 709         a->neg = rand_neg();
 710         BN_sqr(c, a, ctx);
 711         if (bp != NULL) {
 712             if (!results) {
 713                 BN_print(bp, a);
 714                 BIO_puts(bp, " * ");
 715                 BN_print(bp, a);
 716                 BIO_puts(bp, " - ");
 717             }
 718             BN_print(bp, c);
 719             BIO_puts(bp, "\n");
 720         }
 721         BN_div(d, e, c, a, ctx);
 722         BN_sub(d, d, a);
 723         if (!BN_is_zero(d) || !BN_is_zero(e)) {
 724             fprintf(stderr, "Square test failed!\n");
 725             goto err;
 726         }
 727     }
 728
 729     /* Regression test for a BN_sqr overflow bug. */
 730     BN_hex2bn(&a,
 731               "80000000000000008000000000000001"
 732               "FFFFFFFFFFFFFFFE0000000000000000");
 733     BN_sqr(c, a, ctx);
 734     if (bp != NULL) {
 735         if (!results) {
 736             BN_print(bp, a);
 737             BIO_puts(bp, " * ");
 738             BN_print(bp, a);
 739             BIO_puts(bp, " - ");
 740         }
 741         BN_print(bp, c);
 742         BIO_puts(bp, "\n");
 743     }
 744     BN_mul(d, a, a, ctx);
 745     if (BN_cmp(c, d)) {
 746         fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce "
 747                 "different results!\n");
 748         goto err;
 749     }
 750
 751     /* Regression test for a BN_sqr overflow bug. */
 752     BN_hex2bn(&a,
 753               "80000000000000000000000080000001"
 754               "FFFFFFFE000000000000000000000000");
 755     BN_sqr(c, a, ctx);
 756     if (bp != NULL) {
 757         if (!results) {
 758             BN_print(bp, a);
 759             BIO_puts(bp, " * ");
 760             BN_print(bp, a);
 761             BIO_puts(bp, " - ");
 762         }
 763         BN_print(bp, c);
 764         BIO_puts(bp, "\n");
 765     }
 766     BN_mul(d, a, a, ctx);
 767     if (BN_cmp(c, d)) {
 768         fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce "
 769                 "different results!\n");
 770         goto err;
 771     }
 772     ret = 1;
 773  err:
 774     BN_free(a);
 775     BN_free(c);
 776     BN_free(d);
 777     BN_free(e);
 778     return ret;
 779 }
 780
 781 int test_mont(BIO *bp, BN_CTX *ctx)
 782 {
 783     BIGNUM *a, *b, *c, *d, *A, *B;
 784     BIGNUM *n;
 785     int i;
 786     BN_MONT_CTX *mont;
 787
 788     a = BN_new();
 789     b = BN_new();
 790     c = BN_new();
 791     d = BN_new();
 792     A = BN_new();
 793     B = BN_new();
 794     n = BN_new();
 795
 796     mont = BN_MONT_CTX_new();
 797     if (mont == NULL)
 798         return 0;
 799
 800     BN_zero(n);
 801     if (BN_MONT_CTX_set(mont, n, ctx)) {
 802         fprintf(stderr, "BN_MONT_CTX_set succeeded for zero modulus!\n");
 803         return 0;
 804     }
 805
 806     BN_set_word(n, 16);
 807     if (BN_MONT_CTX_set(mont, n, ctx)) {
 808         fprintf(stderr, "BN_MONT_CTX_set succeeded for even modulus!\n");
 809         return 0;
 810     }
 811
 812     BN_bntest_rand(a, 100, 0, 0);
 813     BN_bntest_rand(b, 100, 0, 0);
 814     for (i = 0; i < num2; i++) {
 815         int bits = (200 * (i + 1)) / num2;
 816
 817         if (bits == 0)
 818             continue;
 819         BN_bntest_rand(n, bits, 0, 1);
 820         BN_MONT_CTX_set(mont, n, ctx);
 821
 822         BN_nnmod(a, a, n, ctx);
 823         BN_nnmod(b, b, n, ctx);
 824
 825         BN_to_montgomery(A, a, mont, ctx);
 826         BN_to_montgomery(B, b, mont, ctx);
 827
 828         BN_mod_mul_montgomery(c, A, B, mont, ctx);
 829         BN_from_montgomery(A, c, mont, ctx);
 830         if (bp != NULL) {
 831             if (!results) {
 832                 BN_print(bp, a);
 833                 BIO_puts(bp, " * ");
 834                 BN_print(bp, b);
 835                 BIO_puts(bp, " % ");
 836                 BN_print(bp, &mont->N);
 837                 BIO_puts(bp, " - ");
 838             }
 839             BN_print(bp, A);
 840             BIO_puts(bp, "\n");
 841         }
 842         BN_mod_mul(d, a, b, n, ctx);
 843         BN_sub(d, d, A);
 844         if (!BN_is_zero(d)) {
 845             fprintf(stderr, "Montgomery multiplication test failed!\n");
 846             return 0;
 847         }
 848     }
 849     BN_MONT_CTX_free(mont);
 850     BN_free(a);
 851     BN_free(b);
 852     BN_free(c);
 853     BN_free(d);
 854     BN_free(A);
 855     BN_free(B);
 856     BN_free(n);
 857     return (1);
 858 }
 859
 860 int test_mod(BIO *bp, BN_CTX *ctx)
 861 {
 862     BIGNUM *a, *b, *c, *d, *e;
 863     int i;
 864
 865     a = BN_new();
 866     b = BN_new();
 867     c = BN_new();
 868     d = BN_new();
 869     e = BN_new();
 870
 871     BN_bntest_rand(a, 1024, 0, 0);
 872     for (i = 0; i < num0; i++) {
 873         BN_bntest_rand(b, 450 + i * 10, 0, 0);
 874         a->neg = rand_neg();
 875         b->neg = rand_neg();
 876         BN_mod(c, a, b, ctx);
 877         if (bp != NULL) {
 878             if (!results) {
 879                 BN_print(bp, a);
 880                 BIO_puts(bp, " % ");
 881                 BN_print(bp, b);
 882                 BIO_puts(bp, " - ");
 883             }
 884             BN_print(bp, c);
 885             BIO_puts(bp, "\n");
 886         }
 887         BN_div(d, e, a, b, ctx);
 888         BN_sub(e, e, c);
 889         if (!BN_is_zero(e)) {
 890             fprintf(stderr, "Modulo test failed!\n");
 891             return 0;
 892         }
 893     }
 894     BN_free(a);
 895     BN_free(b);
 896     BN_free(c);
 897     BN_free(d);
 898     BN_free(e);
 899     return (1);
 900 }
 901
 902 int test_mod_mul(BIO *bp, BN_CTX *ctx)
 903 {
 904     BIGNUM *a, *b, *c, *d, *e;
 905     int i, j;
 906
 907     a = BN_new();
 908     b = BN_new();
 909     c = BN_new();
 910     d = BN_new();
 911     e = BN_new();
 912
 913     BN_one(a);
 914     BN_one(b);
 915     BN_zero(c);
 916     if (BN_mod_mul(e, a, b, c, ctx)) {
 917         fprintf(stderr, "BN_mod_mul with zero modulus succeeded!\n");
 918         return 0;
 919     }
 920
 921     for (j = 0; j < 3; j++) {
 922         BN_bntest_rand(c, 1024, 0, 0);
 923         for (i = 0; i < num0; i++) {
 924             BN_bntest_rand(a, 475 + i * 10, 0, 0);
 925             BN_bntest_rand(b, 425 + i * 11, 0, 0);
 926             a->neg = rand_neg();
 927             b->neg = rand_neg();
 928             if (!BN_mod_mul(e, a, b, c, ctx)) {
 929                 unsigned long l;
 930
 931                 while ((l = ERR_get_error()))
 932                     fprintf(stderr, "ERROR:%s\n", ERR_error_string(l, NULL));
 933                 EXIT(1);
 934             }
 935             if (bp != NULL) {
 936                 if (!results) {
 937                     BN_print(bp, a);
 938                     BIO_puts(bp, " * ");
 939                     BN_print(bp, b);
 940                     BIO_puts(bp, " % ");
 941                     BN_print(bp, c);
 942                     if ((a->neg ^ b->neg) && !BN_is_zero(e)) {
 943                         /*
 944                          * If (a*b) % c is negative, c must be added in order
 945                          * to obtain the normalized remainder (new with
 946                          * OpenSSL 0.9.7, previous versions of BN_mod_mul
 947                          * could generate negative results)
 948                          */
 949                         BIO_puts(bp, " + ");
 950                         BN_print(bp, c);
 951                     }
 952                     BIO_puts(bp, " - ");
 953                 }
 954                 BN_print(bp, e);
 955                 BIO_puts(bp, "\n");
 956             }
 957             BN_mul(d, a, b, ctx);
 958             BN_sub(d, d, e);
 959             BN_div(a, b, d, c, ctx);
 960             if (!BN_is_zero(b)) {
 961                 fprintf(stderr, "Modulo multiply test failed!\n");
 962                 ERR_print_errors_fp(stderr);
 963                 return 0;
 964             }
 965         }
 966     }
 967     BN_free(a);
 968     BN_free(b);
 969     BN_free(c);
 970     BN_free(d);
 971     BN_free(e);
 972     return (1);
 973 }
 974
 975 int test_mod_exp(BIO *bp, BN_CTX *ctx)
 976 {
 977     BIGNUM *a, *b, *c, *d, *e;
 978     int i;
 979
 980     a = BN_new();
 981     b = BN_new();
 982     c = BN_new();
 983     d = BN_new();
 984     e = BN_new();
 985
 986     BN_one(a);
 987     BN_one(b);
 988     BN_zero(c);
 989     if (BN_mod_exp(d, a, b, c, ctx)) {
 990         fprintf(stderr, "BN_mod_exp with zero modulus succeeded!\n");
 991         return 0;
 992     }
 993
 994     BN_bntest_rand(c, 30, 0, 1); /* must be odd for montgomery */
 995     for (i = 0; i < num2; i++) {
 996         BN_bntest_rand(a, 20 + i * 5, 0, 0);
 997         BN_bntest_rand(b, 2 + i, 0, 0);
 998
 999         if (!BN_mod_exp(d, a, b, c, ctx))
1000             return (0);
1001
1002         if (bp != NULL) {
1003             if (!results) {
1004                 BN_print(bp, a);
1005                 BIO_puts(bp, " ^ ");
1006                 BN_print(bp, b);
1007                 BIO_puts(bp, " % ");
1008                 BN_print(bp, c);
1009                 BIO_puts(bp, " - ");
1010             }
1011             BN_print(bp, d);
1012             BIO_puts(bp, "\n");
1013         }
1014         BN_exp(e, a, b, ctx);
1015         BN_sub(e, e, d);
1016         BN_div(a, b, e, c, ctx);
1017         if (!BN_is_zero(b)) {
1018             fprintf(stderr, "Modulo exponentiation test failed!\n");
1019             return 0;
1020         }
1021     }
1022
1023     /* Regression test for carry propagation bug in sqr8x_reduction */
1024     BN_hex2bn(&a, "050505050505");
1025     BN_hex2bn(&b, "02");
1026     BN_hex2bn(&c,
1027         "4141414141414141414141274141414141414141414141414141414141414141"
1028         "4141414141414141414141414141414141414141414141414141414141414141"
1029         "4141414141414141414141800000000000000000000000000000000000000000"
1030         "0000000000000000000000000000000000000000000000000000000000000000"
1031         "0000000000000000000000000000000000000000000000000000000000000000"
1032         "0000000000000000000000000000000000000000000000000000000001");
1033     BN_mod_exp(d, a, b, c, ctx);
1034     BN_mul(e, a, a, ctx);
1035     if (BN_cmp(d, e)) {
1036         fprintf(stderr, "BN_mod_exp and BN_mul produce different results!\n");
1037         return 0;
1038     }
1039
1040     BN_free(a);
1041     BN_free(b);
1042     BN_free(c);
1043     BN_free(d);
1044     BN_free(e);
1045     return (1);
1046 }
1047
1048 int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx)
1049 {
1050     BIGNUM *a, *b, *c, *d, *e;
1051     int i;
1052
1053     a = BN_new();
1054     b = BN_new();
1055     c = BN_new();
1056     d = BN_new();
1057     e = BN_new();
1058
1059     BN_one(a);
1060     BN_one(b);
1061     BN_zero(c);
1062     if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1063         fprintf(stderr, "BN_mod_exp_mont_consttime with zero modulus "
1064                 "succeeded\n");
1065         return 0;
1066     }
1067
1068     BN_set_word(c, 16);
1069     if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1070         fprintf(stderr, "BN_mod_exp_mont_consttime with even modulus "
1071                 "succeeded\n");
1072         return 0;
1073     }
1074
1075     BN_bntest_rand(c, 30, 0, 1); /* must be odd for montgomery */
1076     for (i = 0; i < num2; i++) {
1077         BN_bntest_rand(a, 20 + i * 5, 0, 0);
1078         BN_bntest_rand(b, 2 + i, 0, 0);
1079
1080         if (!BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL))
1081             return (00);
1082
1083         if (bp != NULL) {
1084             if (!results) {
1085                 BN_print(bp, a);
1086                 BIO_puts(bp, " ^ ");
1087                 BN_print(bp, b);
1088                 BIO_puts(bp, " % ");
1089                 BN_print(bp, c);
1090                 BIO_puts(bp, " - ");
1091             }
1092             BN_print(bp, d);
1093             BIO_puts(bp, "\n");
1094         }
1095         BN_exp(e, a, b, ctx);
1096         BN_sub(e, e, d);
1097         BN_div(a, b, e, c, ctx);
1098         if (!BN_is_zero(b)) {
1099             fprintf(stderr, "Modulo exponentiation test failed!\n");
1100             return 0;
1101         }
1102     }
1103     BN_free(a);
1104     BN_free(b);
1105     BN_free(c);
1106     BN_free(d);
1107     BN_free(e);
1108     return (1);
1109 }
1110
1111 /*
1112  * Test constant-time modular exponentiation with 1024-bit inputs, which on
1113  * x86_64 cause a different code branch to be taken.
1114  */
1115 int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx)
1116 {
1117     BIGNUM *a, *p, *m, *d, *e;
1118     BN_MONT_CTX *mont;
1119
1120     a = BN_new();
1121     p = BN_new();
1122     m = BN_new();
1123     d = BN_new();
1124     e = BN_new();
1125     mont = BN_MONT_CTX_new();
1126
1127     BN_bntest_rand(m, 1024, 0, 1); /* must be odd for montgomery */
1128     /* Zero exponent */
1129     BN_bntest_rand(a, 1024, 0, 0);
1130     BN_zero(p);
1131     if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
1132         return 0;
1133     if (!BN_is_one(d)) {
1134         fprintf(stderr, "Modular exponentiation test failed!\n");
1135         return 0;
1136     }
1137     /* Zero input */
1138     BN_bntest_rand(p, 1024, 0, 0);
1139     BN_zero(a);
1140     if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
1141         return 0;
1142     if (!BN_is_zero(d)) {
1143         fprintf(stderr, "Modular exponentiation test failed!\n");
1144         return 0;
1145     }
1146     /*
1147      * Craft an input whose Montgomery representation is 1, i.e., shorter
1148      * than the modulus m, in order to test the const time precomputation
1149      * scattering/gathering.
1150      */
1151     BN_one(a);
1152     BN_MONT_CTX_set(mont, m, ctx);
1153     if (!BN_from_montgomery(e, a, mont, ctx))
1154         return 0;
1155     if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
1156         return 0;
1157     if (!BN_mod_exp_simple(a, e, p, m, ctx))
1158         return 0;
1159     if (BN_cmp(a, d) != 0) {
1160         fprintf(stderr, "Modular exponentiation test failed!\n");
1161         return 0;
1162     }
1163     /* Finally, some regular test vectors. */
1164     BN_bntest_rand(e, 1024, 0, 0);
1165     if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
1166         return 0;
1167     if (!BN_mod_exp_simple(a, e, p, m, ctx))
1168         return 0;
1169     if (BN_cmp(a, d) != 0) {
1170         fprintf(stderr, "Modular exponentiation test failed!\n");
1171         return 0;
1172     }
1173     BN_MONT_CTX_free(mont);
1174     BN_free(a);
1175     BN_free(p);
1176     BN_free(m);
1177     BN_free(d);
1178     BN_free(e);
1179     return (1);
1180 }
1181
1182 int test_exp(BIO *bp, BN_CTX *ctx)
1183 {
1184     BIGNUM *a, *b, *d, *e, *one;
1185     int i;
1186
1187     a = BN_new();
1188     b = BN_new();
1189     d = BN_new();
1190     e = BN_new();
1191     one = BN_new();
1192     BN_one(one);
1193
1194     for (i = 0; i < num2; i++) {
1195         BN_bntest_rand(a, 20 + i * 5, 0, 0);
1196         BN_bntest_rand(b, 2 + i, 0, 0);
1197
1198         if (BN_exp(d, a, b, ctx) <= 0)
1199             return (0);
1200
1201         if (bp != NULL) {
1202             if (!results) {
1203                 BN_print(bp, a);
1204                 BIO_puts(bp, " ^ ");
1205                 BN_print(bp, b);
1206                 BIO_puts(bp, " - ");
1207             }
1208             BN_print(bp, d);
1209             BIO_puts(bp, "\n");
1210         }
1211         BN_one(e);
1212         for (; !BN_is_zero(b); BN_sub(b, b, one))
1213             BN_mul(e, e, a, ctx);
1214         BN_sub(e, e, d);
1215         if (!BN_is_zero(e)) {
1216             fprintf(stderr, "Exponentiation test failed!\n");
1217             return 0;
1218         }
1219     }
1220     BN_free(a);
1221     BN_free(b);
1222     BN_free(d);
1223     BN_free(e);
1224     BN_free(one);
1225     return (1);
1226 }
1227
1228 #ifndef OPENSSL_NO_EC2M
1229 int test_gf2m_add(BIO *bp)
1230 {
1231     BIGNUM *a, *b, *c;
1232     int i, ret = 0;
1233
1234     a = BN_new();
1235     b = BN_new();
1236     c = BN_new();
1237
1238     for (i = 0; i < num0; i++) {
1239         BN_rand(a, 512, 0, 0);
1240         BN_copy(b, BN_value_one());
1241         a->neg = rand_neg();
1242         b->neg = rand_neg();
1243         BN_GF2m_add(c, a, b);
1244         /* Test that two added values have the correct parity. */
1245         if ((BN_is_odd(a) && BN_is_odd(c))
1246             || (!BN_is_odd(a) && !BN_is_odd(c))) {
1247             fprintf(stderr, "GF(2^m) addition test (a) failed!\n");
1248             goto err;
1249         }
1250         BN_GF2m_add(c, c, c);
1251         /* Test that c + c = 0. */
1252         if (!BN_is_zero(c)) {
1253             fprintf(stderr, "GF(2^m) addition test (b) failed!\n");
1254             goto err;
1255         }
1256     }
1257     ret = 1;
1258  err:
1259     BN_free(a);
1260     BN_free(b);
1261     BN_free(c);
1262     return ret;
1263 }
1264
1265 int test_gf2m_mod(BIO *bp)
1266 {
1267     BIGNUM *a, *b[2], *c, *d, *e;
1268     int i, j, ret = 0;
1269     int p0[] = { 163, 7, 6, 3, 0, -1 };
1270     int p1[] = { 193, 15, 0, -1 };
1271
1272     a = BN_new();
1273     b[0] = BN_new();
1274     b[1] = BN_new();
1275     c = BN_new();
1276     d = BN_new();
1277     e = BN_new();
1278
1279     BN_GF2m_arr2poly(p0, b[0]);
1280     BN_GF2m_arr2poly(p1, b[1]);
1281
1282     for (i = 0; i < num0; i++) {
1283         BN_bntest_rand(a, 1024, 0, 0);
1284         for (j = 0; j < 2; j++) {
1285             BN_GF2m_mod(c, a, b[j]);
1286             BN_GF2m_add(d, a, c);
1287             BN_GF2m_mod(e, d, b[j]);
1288             /* Test that a + (a mod p) mod p == 0. */
1289             if (!BN_is_zero(e)) {
1290                 fprintf(stderr, "GF(2^m) modulo test failed!\n");
1291                 goto err;
1292             }
1293         }
1294     }
1295     ret = 1;
1296  err:
1297     BN_free(a);
1298     BN_free(b[0]);
1299     BN_free(b[1]);
1300     BN_free(c);
1301     BN_free(d);
1302     BN_free(e);
1303     return ret;
1304 }
1305
1306 int test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx)
1307 {
1308     BIGNUM *a, *b[2], *c, *d, *e, *f, *g, *h;
1309     int i, j, ret = 0;
1310     int p0[] = { 163, 7, 6, 3, 0, -1 };
1311     int p1[] = { 193, 15, 0, -1 };
1312
1313     a = BN_new();
1314     b[0] = BN_new();
1315     b[1] = BN_new();
1316     c = BN_new();
1317     d = BN_new();
1318     e = BN_new();
1319     f = BN_new();
1320     g = BN_new();
1321     h = BN_new();
1322
1323     BN_GF2m_arr2poly(p0, b[0]);
1324     BN_GF2m_arr2poly(p1, b[1]);
1325
1326     for (i = 0; i < num0; i++) {
1327         BN_bntest_rand(a, 1024, 0, 0);
1328         BN_bntest_rand(c, 1024, 0, 0);
1329         BN_bntest_rand(d, 1024, 0, 0);
1330         for (j = 0; j < 2; j++) {
1331             BN_GF2m_mod_mul(e, a, c, b[j], ctx);
1332             BN_GF2m_add(f, a, d);
1333             BN_GF2m_mod_mul(g, f, c, b[j], ctx);
1334             BN_GF2m_mod_mul(h, d, c, b[j], ctx);
1335             BN_GF2m_add(f, e, g);
1336             BN_GF2m_add(f, f, h);
1337             /* Test that (a+d)*c = a*c + d*c. */
1338             if (!BN_is_zero(f)) {
1339                 fprintf(stderr,
1340                         "GF(2^m) modular multiplication test failed!\n");
1341                 goto err;
1342             }
1343         }
1344     }
1345     ret = 1;
1346  err:
1347     BN_free(a);
1348     BN_free(b[0]);
1349     BN_free(b[1]);
1350     BN_free(c);
1351     BN_free(d);
1352     BN_free(e);
1353     BN_free(f);
1354     BN_free(g);
1355     BN_free(h);
1356     return ret;
1357 }
1358
1359 int test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx)
1360 {
1361     BIGNUM *a, *b[2], *c, *d;
1362     int i, j, ret = 0;
1363     int p0[] = { 163, 7, 6, 3, 0, -1 };
1364     int p1[] = { 193, 15, 0, -1 };
1365
1366     a = BN_new();
1367     b[0] = BN_new();
1368     b[1] = BN_new();
1369     c = BN_new();
1370     d = BN_new();
1371
1372     BN_GF2m_arr2poly(p0, b[0]);
1373     BN_GF2m_arr2poly(p1, b[1]);
1374
1375     for (i = 0; i < num0; i++) {
1376         BN_bntest_rand(a, 1024, 0, 0);
1377         for (j = 0; j < 2; j++) {
1378             BN_GF2m_mod_sqr(c, a, b[j], ctx);
1379             BN_copy(d, a);
1380             BN_GF2m_mod_mul(d, a, d, b[j], ctx);
1381             BN_GF2m_add(d, c, d);
1382             /* Test that a*a = a^2. */
1383             if (!BN_is_zero(d)) {
1384                 fprintf(stderr, "GF(2^m) modular squaring test failed!\n");
1385                 goto err;
1386             }
1387         }
1388     }
1389     ret = 1;
1390  err:
1391     BN_free(a);
1392     BN_free(b[0]);
1393     BN_free(b[1]);
1394     BN_free(c);
1395     BN_free(d);
1396     return ret;
1397 }
1398
1399 int test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx)
1400 {
1401     BIGNUM *a, *b[2], *c, *d;
1402     int i, j, ret = 0;
1403     int p0[] = { 163, 7, 6, 3, 0, -1 };
1404     int p1[] = { 193, 15, 0, -1 };
1405
1406     a = BN_new();
1407     b[0] = BN_new();
1408     b[1] = BN_new();
1409     c = BN_new();
1410     d = BN_new();
1411
1412     BN_GF2m_arr2poly(p0, b[0]);
1413     BN_GF2m_arr2poly(p1, b[1]);
1414
1415     for (i = 0; i < num0; i++) {
1416         BN_bntest_rand(a, 512, 0, 0);
1417         for (j = 0; j < 2; j++) {
1418             BN_GF2m_mod_inv(c, a, b[j], ctx);
1419             BN_GF2m_mod_mul(d, a, c, b[j], ctx);
1420             /* Test that ((1/a)*a) = 1. */
1421             if (!BN_is_one(d)) {
1422                 fprintf(stderr, "GF(2^m) modular inversion test failed!\n");
1423                 goto err;
1424             }
1425         }
1426     }
1427     ret = 1;
1428  err:
1429     BN_free(a);
1430     BN_free(b[0]);
1431     BN_free(b[1]);
1432     BN_free(c);
1433     BN_free(d);
1434     return ret;
1435 }
1436
1437 int test_gf2m_mod_div(BIO *bp, BN_CTX *ctx)
1438 {
1439     BIGNUM *a, *b[2], *c, *d, *e, *f;
1440     int i, j, ret = 0;
1441     int p0[] = { 163, 7, 6, 3, 0, -1 };
1442     int p1[] = { 193, 15, 0, -1 };
1443
1444     a = BN_new();
1445     b[0] = BN_new();
1446     b[1] = BN_new();
1447     c = BN_new();
1448     d = BN_new();
1449     e = BN_new();
1450     f = BN_new();
1451
1452     BN_GF2m_arr2poly(p0, b[0]);
1453     BN_GF2m_arr2poly(p1, b[1]);
1454
1455     for (i = 0; i < num0; i++) {
1456         BN_bntest_rand(a, 512, 0, 0);
1457         BN_bntest_rand(c, 512, 0, 0);
1458         for (j = 0; j < 2; j++) {
1459             BN_GF2m_mod_div(d, a, c, b[j], ctx);
1460             BN_GF2m_mod_mul(e, d, c, b[j], ctx);
1461             BN_GF2m_mod_div(f, a, e, b[j], ctx);
1462             /* Test that ((a/c)*c)/a = 1. */
1463             if (!BN_is_one(f)) {
1464                 fprintf(stderr, "GF(2^m) modular division test failed!\n");
1465                 goto err;
1466             }
1467         }
1468     }
1469     ret = 1;
1470  err:
1471     BN_free(a);
1472     BN_free(b[0]);
1473     BN_free(b[1]);
1474     BN_free(c);
1475     BN_free(d);
1476     BN_free(e);
1477     BN_free(f);
1478     return ret;
1479 }
1480
1481 int test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx)
1482 {
1483     BIGNUM *a, *b[2], *c, *d, *e, *f;
1484     int i, j, ret = 0;
1485     int p0[] = { 163, 7, 6, 3, 0, -1 };
1486     int p1[] = { 193, 15, 0, -1 };
1487
1488     a = BN_new();
1489     b[0] = BN_new();
1490     b[1] = BN_new();
1491     c = BN_new();
1492     d = BN_new();
1493     e = BN_new();
1494     f = BN_new();
1495
1496     BN_GF2m_arr2poly(p0, b[0]);
1497     BN_GF2m_arr2poly(p1, b[1]);
1498
1499     for (i = 0; i < num0; i++) {
1500         BN_bntest_rand(a, 512, 0, 0);
1501         BN_bntest_rand(c, 512, 0, 0);
1502         BN_bntest_rand(d, 512, 0, 0);
1503         for (j = 0; j < 2; j++) {
1504             BN_GF2m_mod_exp(e, a, c, b[j], ctx);
1505             BN_GF2m_mod_exp(f, a, d, b[j], ctx);
1506             BN_GF2m_mod_mul(e, e, f, b[j], ctx);
1507             BN_add(f, c, d);
1508             BN_GF2m_mod_exp(f, a, f, b[j], ctx);
1509             BN_GF2m_add(f, e, f);
1510             /* Test that a^(c+d)=a^c*a^d. */
1511             if (!BN_is_zero(f)) {
1512                 fprintf(stderr,
1513                         "GF(2^m) modular exponentiation test failed!\n");
1514                 goto err;
1515             }
1516         }
1517     }
1518     ret = 1;
1519  err:
1520     BN_free(a);
1521     BN_free(b[0]);
1522     BN_free(b[1]);
1523     BN_free(c);
1524     BN_free(d);
1525     BN_free(e);
1526     BN_free(f);
1527     return ret;
1528 }
1529
1530 int test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx)
1531 {
1532     BIGNUM *a, *b[2], *c, *d, *e, *f;
1533     int i, j, ret = 0;
1534     int p0[] = { 163, 7, 6, 3, 0, -1 };
1535     int p1[] = { 193, 15, 0, -1 };
1536
1537     a = BN_new();
1538     b[0] = BN_new();
1539     b[1] = BN_new();
1540     c = BN_new();
1541     d = BN_new();
1542     e = BN_new();
1543     f = BN_new();
1544
1545     BN_GF2m_arr2poly(p0, b[0]);
1546     BN_GF2m_arr2poly(p1, b[1]);
1547
1548     for (i = 0; i < num0; i++) {
1549         BN_bntest_rand(a, 512, 0, 0);
1550         for (j = 0; j < 2; j++) {
1551             BN_GF2m_mod(c, a, b[j]);
1552             BN_GF2m_mod_sqrt(d, a, b[j], ctx);
1553             BN_GF2m_mod_sqr(e, d, b[j], ctx);
1554             BN_GF2m_add(f, c, e);
1555             /* Test that d^2 = a, where d = sqrt(a). */
1556             if (!BN_is_zero(f)) {
1557                 fprintf(stderr, "GF(2^m) modular square root test failed!\n");
1558                 goto err;
1559             }
1560         }
1561     }
1562     ret = 1;
1563  err:
1564     BN_free(a);
1565     BN_free(b[0]);
1566     BN_free(b[1]);
1567     BN_free(c);
1568     BN_free(d);
1569     BN_free(e);
1570     BN_free(f);
1571     return ret;
1572 }
1573
1574 int test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx)
1575 {
1576     BIGNUM *a, *b[2], *c, *d, *e;
1577     int i, j, s = 0, t, ret = 0;
1578     int p0[] = { 163, 7, 6, 3, 0, -1 };
1579     int p1[] = { 193, 15, 0, -1 };
1580
1581     a = BN_new();
1582     b[0] = BN_new();
1583     b[1] = BN_new();
1584     c = BN_new();
1585     d = BN_new();
1586     e = BN_new();
1587
1588     BN_GF2m_arr2poly(p0, b[0]);
1589     BN_GF2m_arr2poly(p1, b[1]);
1590
1591     for (i = 0; i < num0; i++) {
1592         BN_bntest_rand(a, 512, 0, 0);
1593         for (j = 0; j < 2; j++) {
1594             t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
1595             if (t) {
1596                 s++;
1597                 BN_GF2m_mod_sqr(d, c, b[j], ctx);
1598                 BN_GF2m_add(d, c, d);
1599                 BN_GF2m_mod(e, a, b[j]);
1600                 BN_GF2m_add(e, e, d);
1601                 /*
1602                  * Test that solution of quadratic c satisfies c^2 + c = a.
1603                  */
1604                 if (!BN_is_zero(e)) {
1605                     fprintf(stderr,
1606                             "GF(2^m) modular solve quadratic test failed!\n");
1607                     goto err;
1608                 }
1609
1610             }
1611         }
1612     }
1613     if (s == 0) {
1614         fprintf(stderr,
1615                 "All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n",
1616                 num0);
1617         fprintf(stderr,
1618                 "this is very unlikely and probably indicates an error.\n");
1619         goto err;
1620     }
1621     ret = 1;
1622  err:
1623     BN_free(a);
1624     BN_free(b[0]);
1625     BN_free(b[1]);
1626     BN_free(c);
1627     BN_free(d);
1628     BN_free(e);
1629     return ret;
1630 }
1631 #endif
1632 static int genprime_cb(int p, int n, BN_GENCB *arg)
1633 {
1634     char c = '*';
1635
1636     if (p == 0)
1637         c = '.';
1638     if (p == 1)
1639         c = '+';
1640     if (p == 2)
1641         c = '*';
1642     if (p == 3)
1643         c = '\n';
1644     putc(c, stderr);
1645     fflush(stderr);
1646     return 1;
1647 }
1648
1649 int test_kron(BIO *bp, BN_CTX *ctx)
1650 {
1651     BN_GENCB cb;
1652     BIGNUM *a, *b, *r, *t;
1653     int i;
1654     int legendre, kronecker;
1655     int ret = 0;
1656
1657     a = BN_new();
1658     b = BN_new();
1659     r = BN_new();
1660     t = BN_new();
1661     if (a == NULL || b == NULL || r == NULL || t == NULL)
1662         goto err;
1663
1664     BN_GENCB_set(&cb, genprime_cb, NULL);
1665
1666     /*
1667      * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
1668      * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
1669      * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
1670      * generate a random prime b and compare these values for a number of
1671      * random a's.  (That is, we run the Solovay-Strassen primality test to
1672      * confirm that b is prime, except that we don't want to test whether b
1673      * is prime but whether BN_kronecker works.)
1674      */
1675
1676     if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb))
1677         goto err;
1678     b->neg = rand_neg();
1679     putc('\n', stderr);
1680
1681     for (i = 0; i < num0; i++) {
1682         if (!BN_bntest_rand(a, 512, 0, 0))
1683             goto err;
1684         a->neg = rand_neg();
1685
1686         /* t := (|b|-1)/2  (note that b is odd) */
1687         if (!BN_copy(t, b))
1688             goto err;
1689         t->neg = 0;
1690         if (!BN_sub_word(t, 1))
1691             goto err;
1692         if (!BN_rshift1(t, t))
1693             goto err;
1694         /* r := a^t mod b */
1695         b->neg = 0;
1696
1697         if (!BN_mod_exp_recp(r, a, t, b, ctx))
1698             goto err;
1699         b->neg = 1;
1700
1701         if (BN_is_word(r, 1))
1702             legendre = 1;
1703         else if (BN_is_zero(r))
1704             legendre = 0;
1705         else {
1706             if (!BN_add_word(r, 1))
1707                 goto err;
1708             if (0 != BN_ucmp(r, b)) {
1709                 fprintf(stderr, "Legendre symbol computation failed\n");
1710                 goto err;
1711             }
1712             legendre = -1;
1713         }
1714
1715         kronecker = BN_kronecker(a, b, ctx);
1716         if (kronecker < -1)
1717             goto err;
1718         /* we actually need BN_kronecker(a, |b|) */
1719         if (a->neg && b->neg)
1720             kronecker = -kronecker;
1721
1722         if (legendre != kronecker) {
1723             fprintf(stderr, "legendre != kronecker; a = ");
1724             BN_print_fp(stderr, a);
1725             fprintf(stderr, ", b = ");
1726             BN_print_fp(stderr, b);
1727             fprintf(stderr, "\n");
1728             goto err;
1729         }
1730
1731         putc('.', stderr);
1732         fflush(stderr);
1733     }
1734
1735     putc('\n', stderr);
1736     fflush(stderr);
1737     ret = 1;
1738  err:
1739     BN_free(a);
1740     BN_free(b);
1741     BN_free(r);
1742     BN_free(t);
1743     return ret;
1744 }
1745
1746 int test_sqrt(BIO *bp, BN_CTX *ctx)
1747 {
1748     BN_GENCB cb;
1749     BIGNUM *a, *p, *r;
1750     int i, j;
1751     int ret = 0;
1752
1753     a = BN_new();
1754     p = BN_new();
1755     r = BN_new();
1756     if (a == NULL || p == NULL || r == NULL)
1757         goto err;
1758
1759     BN_GENCB_set(&cb, genprime_cb, NULL);
1760
1761     for (i = 0; i < 16; i++) {
1762         if (i < 8) {
1763             unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
1764
1765             if (!BN_set_word(p, primes[i]))
1766                 goto err;
1767         } else {
1768             if (!BN_set_word(a, 32))
1769                 goto err;
1770             if (!BN_set_word(r, 2 * i + 1))
1771                 goto err;
1772
1773             if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb))
1774                 goto err;
1775             putc('\n', stderr);
1776         }
1777         p->neg = rand_neg();
1778
1779         for (j = 0; j < num2; j++) {
1780             /*
1781              * construct 'a' such that it is a square modulo p, but in
1782              * general not a proper square and not reduced modulo p
1783              */
1784             if (!BN_bntest_rand(r, 256, 0, 3))
1785                 goto err;
1786             if (!BN_nnmod(r, r, p, ctx))
1787                 goto err;
1788             if (!BN_mod_sqr(r, r, p, ctx))
1789                 goto err;
1790             if (!BN_bntest_rand(a, 256, 0, 3))
1791                 goto err;
1792             if (!BN_nnmod(a, a, p, ctx))
1793                 goto err;
1794             if (!BN_mod_sqr(a, a, p, ctx))
1795                 goto err;
1796             if (!BN_mul(a, a, r, ctx))
1797                 goto err;
1798             if (rand_neg())
1799                 if (!BN_sub(a, a, p))
1800                     goto err;
1801
1802             if (!BN_mod_sqrt(r, a, p, ctx))
1803                 goto err;
1804             if (!BN_mod_sqr(r, r, p, ctx))
1805                 goto err;
1806
1807             if (!BN_nnmod(a, a, p, ctx))
1808                 goto err;
1809
1810             if (BN_cmp(a, r) != 0) {
1811                 fprintf(stderr, "BN_mod_sqrt failed: a = ");
1812                 BN_print_fp(stderr, a);
1813                 fprintf(stderr, ", r = ");
1814                 BN_print_fp(stderr, r);
1815                 fprintf(stderr, ", p = ");
1816                 BN_print_fp(stderr, p);
1817                 fprintf(stderr, "\n");
1818                 goto err;
1819             }
1820
1821             putc('.', stderr);
1822             fflush(stderr);
1823         }
1824
1825         putc('\n', stderr);
1826         fflush(stderr);
1827     }
1828     ret = 1;
1829  err:
1830     BN_free(a);
1831     BN_free(p);
1832     BN_free(r);
1833     return ret;
1834 }
1835
1836 int test_small_prime(BIO *bp, BN_CTX *ctx)
1837 {
1838     static const int bits = 10;
1839     int ret = 0;
1840     BIGNUM *r;
1841
1842     r = BN_new();
1843     if (!BN_generate_prime_ex(r, bits, 0, NULL, NULL, NULL))
1844         goto err;
1845     if (BN_num_bits(r) != bits) {
1846         BIO_printf(bp, "Expected %d bit prime, got %d bit number\n", bits,
1847                    BN_num_bits(r));
1848         goto err;
1849     }
1850
1851     ret = 1;
1852
1853  err:
1854     BN_clear_free(r);
1855     return ret;
1856 }
1857
1858 int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_)
1859 {
1860     BIGNUM *a, *b, *c, *d;
1861     int i;
1862
1863     b = BN_new();
1864     c = BN_new();
1865     d = BN_new();
1866     BN_one(c);
1867
1868     if (a_)
1869         a = a_;
1870     else {
1871         a = BN_new();
1872         BN_bntest_rand(a, 200, 0, 0);
1873         a->neg = rand_neg();
1874     }
1875     for (i = 0; i < num0; i++) {
1876         BN_lshift(b, a, i + 1);
1877         BN_add(c, c, c);
1878         if (bp != NULL) {
1879             if (!results) {
1880                 BN_print(bp, a);
1881                 BIO_puts(bp, " * ");
1882                 BN_print(bp, c);
1883                 BIO_puts(bp, " - ");
1884             }
1885             BN_print(bp, b);
1886             BIO_puts(bp, "\n");
1887         }
1888         BN_mul(d, a, c, ctx);
1889         BN_sub(d, d, b);
1890         if (!BN_is_zero(d)) {
1891             fprintf(stderr, "Left shift test failed!\n");
1892             fprintf(stderr, "a=");
1893             BN_print_fp(stderr, a);
1894             fprintf(stderr, "\nb=");
1895             BN_print_fp(stderr, b);
1896             fprintf(stderr, "\nc=");
1897             BN_print_fp(stderr, c);
1898             fprintf(stderr, "\nd=");
1899             BN_print_fp(stderr, d);
1900             fprintf(stderr, "\n");
1901             return 0;
1902         }
1903     }
1904     BN_free(a);
1905     BN_free(b);
1906     BN_free(c);
1907     BN_free(d);
1908     return (1);
1909 }
1910
1911 int test_lshift1(BIO *bp)
1912 {
1913     BIGNUM *a, *b, *c;
1914     int i;
1915
1916     a = BN_new();
1917     b = BN_new();
1918     c = BN_new();
1919
1920     BN_bntest_rand(a, 200, 0, 0);
1921     a->neg = rand_neg();
1922     for (i = 0; i < num0; i++) {
1923         BN_lshift1(b, a);
1924         if (bp != NULL) {
1925             if (!results) {
1926                 BN_print(bp, a);
1927                 BIO_puts(bp, " * 2");
1928                 BIO_puts(bp, " - ");
1929             }
1930             BN_print(bp, b);
1931             BIO_puts(bp, "\n");
1932         }
1933         BN_add(c, a, a);
1934         BN_sub(a, b, c);
1935         if (!BN_is_zero(a)) {
1936             fprintf(stderr, "Left shift one test failed!\n");
1937             return 0;
1938         }
1939
1940         BN_copy(a, b);
1941     }
1942     BN_free(a);
1943     BN_free(b);
1944     BN_free(c);
1945     return (1);
1946 }
1947
1948 int test_rshift(BIO *bp, BN_CTX *ctx)
1949 {
1950     BIGNUM *a, *b, *c, *d, *e;
1951     int i;
1952
1953     a = BN_new();
1954     b = BN_new();
1955     c = BN_new();
1956     d = BN_new();
1957     e = BN_new();
1958     BN_one(c);
1959
1960     BN_bntest_rand(a, 200, 0, 0);
1961     a->neg = rand_neg();
1962     for (i = 0; i < num0; i++) {
1963         BN_rshift(b, a, i + 1);
1964         BN_add(c, c, c);
1965         if (bp != NULL) {
1966             if (!results) {
1967                 BN_print(bp, a);
1968                 BIO_puts(bp, " / ");
1969                 BN_print(bp, c);
1970                 BIO_puts(bp, " - ");
1971             }
1972             BN_print(bp, b);
1973             BIO_puts(bp, "\n");
1974         }
1975         BN_div(d, e, a, c, ctx);
1976         BN_sub(d, d, b);
1977         if (!BN_is_zero(d)) {
1978             fprintf(stderr, "Right shift test failed!\n");
1979             return 0;
1980         }
1981     }
1982     BN_free(a);
1983     BN_free(b);
1984     BN_free(c);
1985     BN_free(d);
1986     BN_free(e);
1987     return (1);
1988 }
1989
1990 int test_rshift1(BIO *bp)
1991 {
1992     BIGNUM *a, *b, *c;
1993     int i;
1994
1995     a = BN_new();
1996     b = BN_new();
1997     c = BN_new();
1998
1999     BN_bntest_rand(a, 200, 0, 0);
2000     a->neg = rand_neg();
2001     for (i = 0; i < num0; i++) {
2002         BN_rshift1(b, a);
2003         if (bp != NULL) {
2004             if (!results) {
2005                 BN_print(bp, a);
2006                 BIO_puts(bp, " / 2");
2007                 BIO_puts(bp, " - ");
2008             }
2009             BN_print(bp, b);
2010             BIO_puts(bp, "\n");
2011         }
2012         BN_sub(c, a, b);
2013         BN_sub(c, c, b);
2014         if (!BN_is_zero(c) && !BN_abs_is_word(c, 1)) {
2015             fprintf(stderr, "Right shift one test failed!\n");
2016             return 0;
2017         }
2018         BN_copy(a, b);
2019     }
2020     BN_free(a);
2021     BN_free(b);
2022     BN_free(c);
2023     return (1);
2024 }
2025
2026 int rand_neg(void)
2027 {
2028     static unsigned int neg = 0;
2029     static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };
2030
2031     return (sign[(neg++) % 8]);
2032 }