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