test/bntest.c

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