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
 840     /* Regression test for carry bug in mulx4x_mont */
 841     BN_hex2bn(&a,
 842         "7878787878787878787878787878787878787878787878787878787878787878"
 843         "7878787878787878787878787878787878787878787878787878787878787878"
 844         "7878787878787878787878787878787878787878787878787878787878787878"
 845         "7878787878787878787878787878787878787878787878787878787878787878");
 846     BN_hex2bn(&b,
 847         "095D72C08C097BA488C5E439C655A192EAFB6380073D8C2664668EDDB4060744"
 848         "E16E57FB4EDB9AE10A0CEFCDC28A894F689A128379DB279D48A2E20849D68593"
 849         "9B7803BCF46CEBF5C533FB0DD35B080593DE5472E3FE5DB951B8BFF9B4CB8F03"
 850         "9CC638A5EE8CDD703719F8000E6A9F63BEED5F2FCD52FF293EA05A251BB4AB81");
 851     BN_hex2bn(&n,
 852         "D78AF684E71DB0C39CFF4E64FB9DB567132CB9C50CC98009FEB820B26F2DED9B"
 853         "91B9B5E2B83AE0AE4EB4E0523CA726BFBE969B89FD754F674CE99118C3F2D1C5"
 854         "D81FDC7C54E02B60262B241D53C040E99E45826ECA37A804668E690E1AFC1CA4"
 855         "2C9A15D84D4954425F0B7642FC0BD9D7B24E2618D2DCC9B729D944BADACFDDAF");
 856     BN_MONT_CTX_set(mont, n, ctx);
 857     BN_mod_mul_montgomery(c, a, b, mont, ctx);
 858     BN_mod_mul_montgomery(d, b, a, mont, ctx);
 859     if (BN_cmp(c, d)) {
 860         fprintf(stderr, "Montgomery multiplication test failed:"
 861                         " a*b != b*a.\n");
 862         return 0;
 863     }
 864
 865     BN_MONT_CTX_free(mont);
 866     BN_free(a);
 867     BN_free(b);
 868     BN_free(c);
 869     BN_free(d);
 870     BN_free(A);
 871     BN_free(B);
 872     BN_free(n);
 873     return (1);
 874 }
 875
 876 int test_mod(BIO *bp, BN_CTX *ctx)
 877 {
 878     BIGNUM *a, *b, *c, *d, *e;
 879     int i;
 880
 881     a = BN_new();
 882     b = BN_new();
 883     c = BN_new();
 884     d = BN_new();
 885     e = BN_new();
 886
 887     BN_bntest_rand(a, 1024, 0, 0);
 888     for (i = 0; i < num0; i++) {
 889         BN_bntest_rand(b, 450 + i * 10, 0, 0);
 890         a->neg = rand_neg();
 891         b->neg = rand_neg();
 892         BN_mod(c, a, b, ctx);
 893         if (bp != NULL) {
 894             if (!results) {
 895                 BN_print(bp, a);
 896                 BIO_puts(bp, " % ");
 897                 BN_print(bp, b);
 898                 BIO_puts(bp, " - ");
 899             }
 900             BN_print(bp, c);
 901             BIO_puts(bp, "\n");
 902         }
 903         BN_div(d, e, a, b, ctx);
 904         BN_sub(e, e, c);
 905         if (!BN_is_zero(e)) {
 906             fprintf(stderr, "Modulo test failed!\n");
 907             return 0;
 908         }
 909     }
 910     BN_free(a);
 911     BN_free(b);
 912     BN_free(c);
 913     BN_free(d);
 914     BN_free(e);
 915     return (1);
 916 }
 917
 918 int test_mod_mul(BIO *bp, BN_CTX *ctx)
 919 {
 920     BIGNUM *a, *b, *c, *d, *e;
 921     int i, j;
 922
 923     a = BN_new();
 924     b = BN_new();
 925     c = BN_new();
 926     d = BN_new();
 927     e = BN_new();
 928
 929     BN_one(a);
 930     BN_one(b);
 931     BN_zero(c);
 932     if (BN_mod_mul(e, a, b, c, ctx)) {
 933         fprintf(stderr, "BN_mod_mul with zero modulus succeeded!\n");
 934         return 0;
 935     }
 936
 937     for (j = 0; j < 3; j++) {
 938         BN_bntest_rand(c, 1024, 0, 0);
 939         for (i = 0; i < num0; i++) {
 940             BN_bntest_rand(a, 475 + i * 10, 0, 0);
 941             BN_bntest_rand(b, 425 + i * 11, 0, 0);
 942             a->neg = rand_neg();
 943             b->neg = rand_neg();
 944             if (!BN_mod_mul(e, a, b, c, ctx)) {
 945                 unsigned long l;
 946
 947                 while ((l = ERR_get_error()))
 948                     fprintf(stderr, "ERROR:%s\n", ERR_error_string(l, NULL));
 949                 EXIT(1);
 950             }
 951             if (bp != NULL) {
 952                 if (!results) {
 953                     BN_print(bp, a);
 954                     BIO_puts(bp, " * ");
 955                     BN_print(bp, b);
 956                     BIO_puts(bp, " % ");
 957                     BN_print(bp, c);
 958                     if ((a->neg ^ b->neg) && !BN_is_zero(e)) {
 959                         /*
 960                          * If (a*b) % c is negative, c must be added in order
 961                          * to obtain the normalized remainder (new with
 962                          * OpenSSL 0.9.7, previous versions of BN_mod_mul
 963                          * could generate negative results)
 964                          */
 965                         BIO_puts(bp, " + ");
 966                         BN_print(bp, c);
 967                     }
 968                     BIO_puts(bp, " - ");
 969                 }
 970                 BN_print(bp, e);
 971                 BIO_puts(bp, "\n");
 972             }
 973             BN_mul(d, a, b, ctx);
 974             BN_sub(d, d, e);
 975             BN_div(a, b, d, c, ctx);
 976             if (!BN_is_zero(b)) {
 977                 fprintf(stderr, "Modulo multiply test failed!\n");
 978                 ERR_print_errors_fp(stderr);
 979                 return 0;
 980             }
 981         }
 982     }
 983     BN_free(a);
 984     BN_free(b);
 985     BN_free(c);
 986     BN_free(d);
 987     BN_free(e);
 988     return (1);
 989 }
 990
 991 int test_mod_exp(BIO *bp, BN_CTX *ctx)
 992 {
 993     BIGNUM *a, *b, *c, *d, *e;
 994     int i;
 995
 996     a = BN_new();
 997     b = BN_new();
 998     c = BN_new();
 999     d = BN_new();
1000     e = BN_new();
1001
1002     BN_one(a);
1003     BN_one(b);
1004     BN_zero(c);
1005     if (BN_mod_exp(d, a, b, c, ctx)) {
1006         fprintf(stderr, "BN_mod_exp with zero modulus succeeded!\n");
1007         return 0;
1008     }
1009
1010     BN_bntest_rand(c, 30, 0, 1); /* must be odd for montgomery */
1011     for (i = 0; i < num2; i++) {
1012         BN_bntest_rand(a, 20 + i * 5, 0, 0);
1013         BN_bntest_rand(b, 2 + i, 0, 0);
1014
1015         if (!BN_mod_exp(d, a, b, c, ctx))
1016             return (0);
1017
1018         if (bp != NULL) {
1019             if (!results) {
1020                 BN_print(bp, a);
1021                 BIO_puts(bp, " ^ ");
1022                 BN_print(bp, b);
1023                 BIO_puts(bp, " % ");
1024                 BN_print(bp, c);
1025                 BIO_puts(bp, " - ");
1026             }
1027             BN_print(bp, d);
1028             BIO_puts(bp, "\n");
1029         }
1030         BN_exp(e, a, b, ctx);
1031         BN_sub(e, e, d);
1032         BN_div(a, b, e, c, ctx);
1033         if (!BN_is_zero(b)) {
1034             fprintf(stderr, "Modulo exponentiation test failed!\n");
1035             return 0;
1036         }
1037     }
1038
1039     /* Regression test for carry propagation bug in sqr8x_reduction */
1040     BN_hex2bn(&a, "050505050505");
1041     BN_hex2bn(&b, "02");
1042     BN_hex2bn(&c,
1043         "4141414141414141414141274141414141414141414141414141414141414141"
1044         "4141414141414141414141414141414141414141414141414141414141414141"
1045         "4141414141414141414141800000000000000000000000000000000000000000"
1046         "0000000000000000000000000000000000000000000000000000000000000000"
1047         "0000000000000000000000000000000000000000000000000000000000000000"
1048         "0000000000000000000000000000000000000000000000000000000001");
1049     BN_mod_exp(d, a, b, c, ctx);
1050     BN_mul(e, a, a, ctx);
1051     if (BN_cmp(d, e)) {
1052         fprintf(stderr, "BN_mod_exp and BN_mul produce different results!\n");
1053         return 0;
1054     }
1055
1056     BN_free(a);
1057     BN_free(b);
1058     BN_free(c);
1059     BN_free(d);
1060     BN_free(e);
1061     return (1);
1062 }
1063
1064 int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx)
1065 {
1066     BIGNUM *a, *b, *c, *d, *e;
1067     int i;
1068
1069     a = BN_new();
1070     b = BN_new();
1071     c = BN_new();
1072     d = BN_new();
1073     e = BN_new();
1074
1075     BN_one(a);
1076     BN_one(b);
1077     BN_zero(c);
1078     if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1079         fprintf(stderr, "BN_mod_exp_mont_consttime with zero modulus "
1080                 "succeeded\n");
1081         return 0;
1082     }
1083
1084     BN_set_word(c, 16);
1085     if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) {
1086         fprintf(stderr, "BN_mod_exp_mont_consttime with even modulus "
1087                 "succeeded\n");
1088         return 0;
1089     }
1090
1091     BN_bntest_rand(c, 30, 0, 1); /* must be odd for montgomery */
1092     for (i = 0; i < num2; i++) {
1093         BN_bntest_rand(a, 20 + i * 5, 0, 0);
1094         BN_bntest_rand(b, 2 + i, 0, 0);
1095
1096         if (!BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL))
1097             return (00);
1098
1099         if (bp != NULL) {
1100             if (!results) {
1101                 BN_print(bp, a);
1102                 BIO_puts(bp, " ^ ");
1103                 BN_print(bp, b);
1104                 BIO_puts(bp, " % ");
1105                 BN_print(bp, c);
1106                 BIO_puts(bp, " - ");
1107             }
1108             BN_print(bp, d);
1109             BIO_puts(bp, "\n");
1110         }
1111         BN_exp(e, a, b, ctx);
1112         BN_sub(e, e, d);
1113         BN_div(a, b, e, c, ctx);
1114         if (!BN_is_zero(b)) {
1115             fprintf(stderr, "Modulo exponentiation test failed!\n");
1116             return 0;
1117         }
1118     }
1119     BN_free(a);
1120     BN_free(b);
1121     BN_free(c);
1122     BN_free(d);
1123     BN_free(e);
1124     return (1);
1125 }
1126
1127 /*
1128  * Test constant-time modular exponentiation with 1024-bit inputs, which on
1129  * x86_64 cause a different code branch to be taken.
1130  */
1131 int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx)
1132 {
1133     BIGNUM *a, *p, *m, *d, *e;
1134     BN_MONT_CTX *mont;
1135
1136     a = BN_new();
1137     p = BN_new();
1138     m = BN_new();
1139     d = BN_new();
1140     e = BN_new();
1141     mont = BN_MONT_CTX_new();
1142
1143     BN_bntest_rand(m, 1024, 0, 1); /* must be odd for montgomery */
1144     /* Zero exponent */
1145     BN_bntest_rand(a, 1024, 0, 0);
1146     BN_zero(p);
1147     if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
1148         return 0;
1149     if (!BN_is_one(d)) {
1150         fprintf(stderr, "Modular exponentiation test failed!\n");
1151         return 0;
1152     }
1153     /* Zero input */
1154     BN_bntest_rand(p, 1024, 0, 0);
1155     BN_zero(a);
1156     if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))
1157         return 0;
1158     if (!BN_is_zero(d)) {
1159         fprintf(stderr, "Modular exponentiation test failed!\n");
1160         return 0;
1161     }
1162     /*
1163      * Craft an input whose Montgomery representation is 1, i.e., shorter
1164      * than the modulus m, in order to test the const time precomputation
1165      * scattering/gathering.
1166      */
1167     BN_one(a);
1168     BN_MONT_CTX_set(mont, m, ctx);
1169     if (!BN_from_montgomery(e, a, mont, ctx))
1170         return 0;
1171     if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
1172         return 0;
1173     if (!BN_mod_exp_simple(a, e, p, m, ctx))
1174         return 0;
1175     if (BN_cmp(a, d) != 0) {
1176         fprintf(stderr, "Modular exponentiation test failed!\n");
1177         return 0;
1178     }
1179     /* Finally, some regular test vectors. */
1180     BN_bntest_rand(e, 1024, 0, 0);
1181     if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL))
1182         return 0;
1183     if (!BN_mod_exp_simple(a, e, p, m, ctx))
1184         return 0;
1185     if (BN_cmp(a, d) != 0) {
1186         fprintf(stderr, "Modular exponentiation test failed!\n");
1187         return 0;
1188     }
1189     BN_MONT_CTX_free(mont);
1190     BN_free(a);
1191     BN_free(p);
1192     BN_free(m);
1193     BN_free(d);
1194     BN_free(e);
1195     return (1);
1196 }
1197
1198 int test_exp(BIO *bp, BN_CTX *ctx)
1199 {
1200     BIGNUM *a, *b, *d, *e, *one;
1201     int i;
1202
1203     a = BN_new();
1204     b = BN_new();
1205     d = BN_new();
1206     e = BN_new();
1207     one = BN_new();
1208     BN_one(one);
1209
1210     for (i = 0; i < num2; i++) {
1211         BN_bntest_rand(a, 20 + i * 5, 0, 0);
1212         BN_bntest_rand(b, 2 + i, 0, 0);
1213
1214         if (BN_exp(d, a, b, ctx) <= 0)
1215             return (0);
1216
1217         if (bp != NULL) {
1218             if (!results) {
1219                 BN_print(bp, a);
1220                 BIO_puts(bp, " ^ ");
1221                 BN_print(bp, b);
1222                 BIO_puts(bp, " - ");
1223             }
1224             BN_print(bp, d);
1225             BIO_puts(bp, "\n");
1226         }
1227         BN_one(e);
1228         for (; !BN_is_zero(b); BN_sub(b, b, one))
1229             BN_mul(e, e, a, ctx);
1230         BN_sub(e, e, d);
1231         if (!BN_is_zero(e)) {
1232             fprintf(stderr, "Exponentiation test failed!\n");
1233             return 0;
1234         }
1235     }
1236     BN_free(a);
1237     BN_free(b);
1238     BN_free(d);
1239     BN_free(e);
1240     BN_free(one);
1241     return (1);
1242 }
1243
1244 #ifndef OPENSSL_NO_EC2M
1245 int test_gf2m_add(BIO *bp)
1246 {
1247     BIGNUM *a, *b, *c;
1248     int i, ret = 0;
1249
1250     a = BN_new();
1251     b = BN_new();
1252     c = BN_new();
1253
1254     for (i = 0; i < num0; i++) {
1255         BN_rand(a, 512, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY);
1256         BN_copy(b, BN_value_one());
1257         a->neg = rand_neg();
1258         b->neg = rand_neg();
1259         BN_GF2m_add(c, a, b);
1260         /* Test that two added values have the correct parity. */
1261         if ((BN_is_odd(a) && BN_is_odd(c))
1262             || (!BN_is_odd(a) && !BN_is_odd(c))) {
1263             fprintf(stderr, "GF(2^m) addition test (a) failed!\n");
1264             goto err;
1265         }
1266         BN_GF2m_add(c, c, c);
1267         /* Test that c + c = 0. */
1268         if (!BN_is_zero(c)) {
1269             fprintf(stderr, "GF(2^m) addition test (b) failed!\n");
1270             goto err;
1271         }
1272     }
1273     ret = 1;
1274  err:
1275     BN_free(a);
1276     BN_free(b);
1277     BN_free(c);
1278     return ret;
1279 }
1280
1281 int test_gf2m_mod(BIO *bp)
1282 {
1283     BIGNUM *a, *b[2], *c, *d, *e;
1284     int i, j, ret = 0;
1285     int p0[] = { 163, 7, 6, 3, 0, -1 };
1286     int p1[] = { 193, 15, 0, -1 };
1287
1288     a = BN_new();
1289     b[0] = BN_new();
1290     b[1] = BN_new();
1291     c = BN_new();
1292     d = BN_new();
1293     e = BN_new();
1294
1295     BN_GF2m_arr2poly(p0, b[0]);
1296     BN_GF2m_arr2poly(p1, b[1]);
1297
1298     for (i = 0; i < num0; i++) {
1299         BN_bntest_rand(a, 1024, 0, 0);
1300         for (j = 0; j < 2; j++) {
1301             BN_GF2m_mod(c, a, b[j]);
1302             BN_GF2m_add(d, a, c);
1303             BN_GF2m_mod(e, d, b[j]);
1304             /* Test that a + (a mod p) mod p == 0. */
1305             if (!BN_is_zero(e)) {
1306                 fprintf(stderr, "GF(2^m) modulo test failed!\n");
1307                 goto err;
1308             }
1309         }
1310     }
1311     ret = 1;
1312  err:
1313     BN_free(a);
1314     BN_free(b[0]);
1315     BN_free(b[1]);
1316     BN_free(c);
1317     BN_free(d);
1318     BN_free(e);
1319     return ret;
1320 }
1321
1322 int test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx)
1323 {
1324     BIGNUM *a, *b[2], *c, *d, *e, *f, *g, *h;
1325     int i, j, ret = 0;
1326     int p0[] = { 163, 7, 6, 3, 0, -1 };
1327     int p1[] = { 193, 15, 0, -1 };
1328
1329     a = BN_new();
1330     b[0] = BN_new();
1331     b[1] = BN_new();
1332     c = BN_new();
1333     d = BN_new();
1334     e = BN_new();
1335     f = BN_new();
1336     g = BN_new();
1337     h = BN_new();
1338
1339     BN_GF2m_arr2poly(p0, b[0]);
1340     BN_GF2m_arr2poly(p1, b[1]);
1341
1342     for (i = 0; i < num0; i++) {
1343         BN_bntest_rand(a, 1024, 0, 0);
1344         BN_bntest_rand(c, 1024, 0, 0);
1345         BN_bntest_rand(d, 1024, 0, 0);
1346         for (j = 0; j < 2; j++) {
1347             BN_GF2m_mod_mul(e, a, c, b[j], ctx);
1348             BN_GF2m_add(f, a, d);
1349             BN_GF2m_mod_mul(g, f, c, b[j], ctx);
1350             BN_GF2m_mod_mul(h, d, c, b[j], ctx);
1351             BN_GF2m_add(f, e, g);
1352             BN_GF2m_add(f, f, h);
1353             /* Test that (a+d)*c = a*c + d*c. */
1354             if (!BN_is_zero(f)) {
1355                 fprintf(stderr,
1356                         "GF(2^m) modular multiplication test failed!\n");
1357                 goto err;
1358             }
1359         }
1360     }
1361     ret = 1;
1362  err:
1363     BN_free(a);
1364     BN_free(b[0]);
1365     BN_free(b[1]);
1366     BN_free(c);
1367     BN_free(d);
1368     BN_free(e);
1369     BN_free(f);
1370     BN_free(g);
1371     BN_free(h);
1372     return ret;
1373 }
1374
1375 int test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx)
1376 {
1377     BIGNUM *a, *b[2], *c, *d;
1378     int i, j, ret = 0;
1379     int p0[] = { 163, 7, 6, 3, 0, -1 };
1380     int p1[] = { 193, 15, 0, -1 };
1381
1382     a = BN_new();
1383     b[0] = BN_new();
1384     b[1] = BN_new();
1385     c = BN_new();
1386     d = BN_new();
1387
1388     BN_GF2m_arr2poly(p0, b[0]);
1389     BN_GF2m_arr2poly(p1, b[1]);
1390
1391     for (i = 0; i < num0; i++) {
1392         BN_bntest_rand(a, 1024, 0, 0);
1393         for (j = 0; j < 2; j++) {
1394             BN_GF2m_mod_sqr(c, a, b[j], ctx);
1395             BN_copy(d, a);
1396             BN_GF2m_mod_mul(d, a, d, b[j], ctx);
1397             BN_GF2m_add(d, c, d);
1398             /* Test that a*a = a^2. */
1399             if (!BN_is_zero(d)) {
1400                 fprintf(stderr, "GF(2^m) modular squaring 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_inv(BIO *bp, BN_CTX *ctx)
1416 {
1417     BIGNUM *a, *b[2], *c, *d;
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
1428     BN_GF2m_arr2poly(p0, b[0]);
1429     BN_GF2m_arr2poly(p1, b[1]);
1430
1431     for (i = 0; i < num0; i++) {
1432         BN_bntest_rand(a, 512, 0, 0);
1433         for (j = 0; j < 2; j++) {
1434             BN_GF2m_mod_inv(c, a, b[j], ctx);
1435             BN_GF2m_mod_mul(d, a, c, b[j], ctx);
1436             /* Test that ((1/a)*a) = 1. */
1437             if (!BN_is_one(d)) {
1438                 fprintf(stderr, "GF(2^m) modular inversion test failed!\n");
1439                 goto err;
1440             }
1441         }
1442     }
1443     ret = 1;
1444  err:
1445     BN_free(a);
1446     BN_free(b[0]);
1447     BN_free(b[1]);
1448     BN_free(c);
1449     BN_free(d);
1450     return ret;
1451 }
1452
1453 int test_gf2m_mod_div(BIO *bp, BN_CTX *ctx)
1454 {
1455     BIGNUM *a, *b[2], *c, *d, *e, *f;
1456     int i, j, ret = 0;
1457     int p0[] = { 163, 7, 6, 3, 0, -1 };
1458     int p1[] = { 193, 15, 0, -1 };
1459
1460     a = BN_new();
1461     b[0] = BN_new();
1462     b[1] = BN_new();
1463     c = BN_new();
1464     d = BN_new();
1465     e = BN_new();
1466     f = BN_new();
1467
1468     BN_GF2m_arr2poly(p0, b[0]);
1469     BN_GF2m_arr2poly(p1, b[1]);
1470
1471     for (i = 0; i < num0; i++) {
1472         BN_bntest_rand(a, 512, 0, 0);
1473         BN_bntest_rand(c, 512, 0, 0);
1474         for (j = 0; j < 2; j++) {
1475             BN_GF2m_mod_div(d, a, c, b[j], ctx);
1476             BN_GF2m_mod_mul(e, d, c, b[j], ctx);
1477             BN_GF2m_mod_div(f, a, e, b[j], ctx);
1478             /* Test that ((a/c)*c)/a = 1. */
1479             if (!BN_is_one(f)) {
1480                 fprintf(stderr, "GF(2^m) modular division test failed!\n");
1481                 goto err;
1482             }
1483         }
1484     }
1485     ret = 1;
1486  err:
1487     BN_free(a);
1488     BN_free(b[0]);
1489     BN_free(b[1]);
1490     BN_free(c);
1491     BN_free(d);
1492     BN_free(e);
1493     BN_free(f);
1494     return ret;
1495 }
1496
1497 int test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx)
1498 {
1499     BIGNUM *a, *b[2], *c, *d, *e, *f;
1500     int i, j, ret = 0;
1501     int p0[] = { 163, 7, 6, 3, 0, -1 };
1502     int p1[] = { 193, 15, 0, -1 };
1503
1504     a = BN_new();
1505     b[0] = BN_new();
1506     b[1] = BN_new();
1507     c = BN_new();
1508     d = BN_new();
1509     e = BN_new();
1510     f = BN_new();
1511
1512     BN_GF2m_arr2poly(p0, b[0]);
1513     BN_GF2m_arr2poly(p1, b[1]);
1514
1515     for (i = 0; i < num0; i++) {
1516         BN_bntest_rand(a, 512, 0, 0);
1517         BN_bntest_rand(c, 512, 0, 0);
1518         BN_bntest_rand(d, 512, 0, 0);
1519         for (j = 0; j < 2; j++) {
1520             BN_GF2m_mod_exp(e, a, c, b[j], ctx);
1521             BN_GF2m_mod_exp(f, a, d, b[j], ctx);
1522             BN_GF2m_mod_mul(e, e, f, b[j], ctx);
1523             BN_add(f, c, d);
1524             BN_GF2m_mod_exp(f, a, f, b[j], ctx);
1525             BN_GF2m_add(f, e, f);
1526             /* Test that a^(c+d)=a^c*a^d. */
1527             if (!BN_is_zero(f)) {
1528                 fprintf(stderr,
1529                         "GF(2^m) modular exponentiation test failed!\n");
1530                 goto err;
1531             }
1532         }
1533     }
1534     ret = 1;
1535  err:
1536     BN_free(a);
1537     BN_free(b[0]);
1538     BN_free(b[1]);
1539     BN_free(c);
1540     BN_free(d);
1541     BN_free(e);
1542     BN_free(f);
1543     return ret;
1544 }
1545
1546 int test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx)
1547 {
1548     BIGNUM *a, *b[2], *c, *d, *e, *f;
1549     int i, j, ret = 0;
1550     int p0[] = { 163, 7, 6, 3, 0, -1 };
1551     int p1[] = { 193, 15, 0, -1 };
1552
1553     a = BN_new();
1554     b[0] = BN_new();
1555     b[1] = BN_new();
1556     c = BN_new();
1557     d = BN_new();
1558     e = BN_new();
1559     f = BN_new();
1560
1561     BN_GF2m_arr2poly(p0, b[0]);
1562     BN_GF2m_arr2poly(p1, b[1]);
1563
1564     for (i = 0; i < num0; i++) {
1565         BN_bntest_rand(a, 512, 0, 0);
1566         for (j = 0; j < 2; j++) {
1567             BN_GF2m_mod(c, a, b[j]);
1568             BN_GF2m_mod_sqrt(d, a, b[j], ctx);
1569             BN_GF2m_mod_sqr(e, d, b[j], ctx);
1570             BN_GF2m_add(f, c, e);
1571             /* Test that d^2 = a, where d = sqrt(a). */
1572             if (!BN_is_zero(f)) {
1573                 fprintf(stderr, "GF(2^m) modular square root test failed!\n");
1574                 goto err;
1575             }
1576         }
1577     }
1578     ret = 1;
1579  err:
1580     BN_free(a);
1581     BN_free(b[0]);
1582     BN_free(b[1]);
1583     BN_free(c);
1584     BN_free(d);
1585     BN_free(e);
1586     BN_free(f);
1587     return ret;
1588 }
1589
1590 int test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx)
1591 {
1592     BIGNUM *a, *b[2], *c, *d, *e;
1593     int i, j, s = 0, t, ret = 0;
1594     int p0[] = { 163, 7, 6, 3, 0, -1 };
1595     int p1[] = { 193, 15, 0, -1 };
1596
1597     a = BN_new();
1598     b[0] = BN_new();
1599     b[1] = BN_new();
1600     c = BN_new();
1601     d = BN_new();
1602     e = BN_new();
1603
1604     BN_GF2m_arr2poly(p0, b[0]);
1605     BN_GF2m_arr2poly(p1, b[1]);
1606
1607     for (i = 0; i < num0; i++) {
1608         BN_bntest_rand(a, 512, 0, 0);
1609         for (j = 0; j < 2; j++) {
1610             t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
1611             if (t) {
1612                 s++;
1613                 BN_GF2m_mod_sqr(d, c, b[j], ctx);
1614                 BN_GF2m_add(d, c, d);
1615                 BN_GF2m_mod(e, a, b[j]);
1616                 BN_GF2m_add(e, e, d);
1617                 /*
1618                  * Test that solution of quadratic c satisfies c^2 + c = a.
1619                  */
1620                 if (!BN_is_zero(e)) {
1621                     fprintf(stderr,
1622                             "GF(2^m) modular solve quadratic test failed!\n");
1623                     goto err;
1624                 }
1625
1626             }
1627         }
1628     }
1629     if (s == 0) {
1630         fprintf(stderr,
1631                 "All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n",
1632                 num0);
1633         fprintf(stderr,
1634                 "this is very unlikely and probably indicates an error.\n");
1635         goto err;
1636     }
1637     ret = 1;
1638  err:
1639     BN_free(a);
1640     BN_free(b[0]);
1641     BN_free(b[1]);
1642     BN_free(c);
1643     BN_free(d);
1644     BN_free(e);
1645     return ret;
1646 }
1647 #endif
1648 static int genprime_cb(int p, int n, BN_GENCB *arg)
1649 {
1650     char c = '*';
1651
1652     if (p == 0)
1653         c = '.';
1654     if (p == 1)
1655         c = '+';
1656     if (p == 2)
1657         c = '*';
1658     if (p == 3)
1659         c = '\n';
1660     putc(c, stderr);
1661     fflush(stderr);
1662     return 1;
1663 }
1664
1665 int test_kron(BIO *bp, BN_CTX *ctx)
1666 {
1667     BN_GENCB cb;
1668     BIGNUM *a, *b, *r, *t;
1669     int i;
1670     int legendre, kronecker;
1671     int ret = 0;
1672
1673     a = BN_new();
1674     b = BN_new();
1675     r = BN_new();
1676     t = BN_new();
1677     if (a == NULL || b == NULL || r == NULL || t == NULL)
1678         goto err;
1679
1680     BN_GENCB_set(&cb, genprime_cb, NULL);
1681
1682     /*
1683      * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In
1684      * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is
1685      * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we
1686      * generate a random prime b and compare these values for a number of
1687      * random a's.  (That is, we run the Solovay-Strassen primality test to
1688      * confirm that b is prime, except that we don't want to test whether b
1689      * is prime but whether BN_kronecker works.)
1690      */
1691
1692     if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb))
1693         goto err;
1694     b->neg = rand_neg();
1695     putc('\n', stderr);
1696
1697     for (i = 0; i < num0; i++) {
1698         if (!BN_bntest_rand(a, 512, 0, 0))
1699             goto err;
1700         a->neg = rand_neg();
1701
1702         /* t := (|b|-1)/2  (note that b is odd) */
1703         if (!BN_copy(t, b))
1704             goto err;
1705         t->neg = 0;
1706         if (!BN_sub_word(t, 1))
1707             goto err;
1708         if (!BN_rshift1(t, t))
1709             goto err;
1710         /* r := a^t mod b */
1711         b->neg = 0;
1712
1713         if (!BN_mod_exp_recp(r, a, t, b, ctx))
1714             goto err;
1715         b->neg = 1;
1716
1717         if (BN_is_word(r, 1))
1718             legendre = 1;
1719         else if (BN_is_zero(r))
1720             legendre = 0;
1721         else {
1722             if (!BN_add_word(r, 1))
1723                 goto err;
1724             if (0 != BN_ucmp(r, b)) {
1725                 fprintf(stderr, "Legendre symbol computation failed\n");
1726                 goto err;
1727             }
1728             legendre = -1;
1729         }
1730
1731         kronecker = BN_kronecker(a, b, ctx);
1732         if (kronecker < -1)
1733             goto err;
1734         /* we actually need BN_kronecker(a, |b|) */
1735         if (a->neg && b->neg)
1736             kronecker = -kronecker;
1737
1738         if (legendre != kronecker) {
1739             fprintf(stderr, "legendre != kronecker; a = ");
1740             BN_print_fp(stderr, a);
1741             fprintf(stderr, ", b = ");
1742             BN_print_fp(stderr, b);
1743             fprintf(stderr, "\n");
1744             goto err;
1745         }
1746
1747         putc('.', stderr);
1748         fflush(stderr);
1749     }
1750
1751     putc('\n', stderr);
1752     fflush(stderr);
1753     ret = 1;
1754  err:
1755     BN_free(a);
1756     BN_free(b);
1757     BN_free(r);
1758     BN_free(t);
1759     return ret;
1760 }
1761
1762 int test_sqrt(BIO *bp, BN_CTX *ctx)
1763 {
1764     BN_GENCB cb;
1765     BIGNUM *a, *p, *r;
1766     int i, j;
1767     int ret = 0;
1768
1769     a = BN_new();
1770     p = BN_new();
1771     r = BN_new();
1772     if (a == NULL || p == NULL || r == NULL)
1773         goto err;
1774
1775     BN_GENCB_set(&cb, genprime_cb, NULL);
1776
1777     for (i = 0; i < 16; i++) {
1778         if (i < 8) {
1779             unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
1780
1781             if (!BN_set_word(p, primes[i]))
1782                 goto err;
1783         } else {
1784             if (!BN_set_word(a, 32))
1785                 goto err;
1786             if (!BN_set_word(r, 2 * i + 1))
1787                 goto err;
1788
1789             if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb))
1790                 goto err;
1791             putc('\n', stderr);
1792         }
1793         p->neg = rand_neg();
1794
1795         for (j = 0; j < num2; j++) {
1796             /*
1797              * construct 'a' such that it is a square modulo p, but in
1798              * general not a proper square and not reduced modulo p
1799              */
1800             if (!BN_bntest_rand(r, 256, 0, 3))
1801                 goto err;
1802             if (!BN_nnmod(r, r, p, ctx))
1803                 goto err;
1804             if (!BN_mod_sqr(r, r, p, ctx))
1805                 goto err;
1806             if (!BN_bntest_rand(a, 256, 0, 3))
1807                 goto err;
1808             if (!BN_nnmod(a, a, p, ctx))
1809                 goto err;
1810             if (!BN_mod_sqr(a, a, p, ctx))
1811                 goto err;
1812             if (!BN_mul(a, a, r, ctx))
1813                 goto err;
1814             if (rand_neg())
1815                 if (!BN_sub(a, a, p))
1816                     goto err;
1817
1818             if (!BN_mod_sqrt(r, a, p, ctx))
1819                 goto err;
1820             if (!BN_mod_sqr(r, r, p, ctx))
1821                 goto err;
1822
1823             if (!BN_nnmod(a, a, p, ctx))
1824                 goto err;
1825
1826             if (BN_cmp(a, r) != 0) {
1827                 fprintf(stderr, "BN_mod_sqrt failed: a = ");
1828                 BN_print_fp(stderr, a);
1829                 fprintf(stderr, ", r = ");
1830                 BN_print_fp(stderr, r);
1831                 fprintf(stderr, ", p = ");
1832                 BN_print_fp(stderr, p);
1833                 fprintf(stderr, "\n");
1834                 goto err;
1835             }
1836
1837             putc('.', stderr);
1838             fflush(stderr);
1839         }
1840
1841         putc('\n', stderr);
1842         fflush(stderr);
1843     }
1844     ret = 1;
1845  err:
1846     BN_free(a);
1847     BN_free(p);
1848     BN_free(r);
1849     return ret;
1850 }
1851
1852 int test_small_prime(BIO *bp, BN_CTX *ctx)
1853 {
1854     static const int bits = 10;
1855     int ret = 0;
1856     BIGNUM *r;
1857
1858     r = BN_new();
1859     if (!BN_generate_prime_ex(r, bits, 0, NULL, NULL, NULL))
1860         goto err;
1861     if (BN_num_bits(r) != bits) {
1862         BIO_printf(bp, "Expected %d bit prime, got %d bit number\n", bits,
1863                    BN_num_bits(r));
1864         goto err;
1865     }
1866
1867     ret = 1;
1868
1869  err:
1870     BN_clear_free(r);
1871     return ret;
1872 }
1873
1874 int test_bn2dec(BIO *bp)
1875 {
1876     static const char *bn2dec_tests[] = {
1877         "0",
1878         "1",
1879         "-1",
1880         "100",
1881         "-100",
1882         "123456789012345678901234567890",
1883         "-123456789012345678901234567890",
1884         "123456789012345678901234567890123456789012345678901234567890",
1885         "-123456789012345678901234567890123456789012345678901234567890",
1886     };
1887     int ret = 0;
1888     size_t i;
1889     BIGNUM *bn = NULL;
1890     char *dec = NULL;
1891
1892     for (i = 0; i < OSSL_NELEM(bn2dec_tests); i++) {
1893         if (!BN_dec2bn(&bn, bn2dec_tests[i]))
1894             goto err;
1895
1896         dec = BN_bn2dec(bn);
1897         if (dec == NULL) {
1898             fprintf(stderr, "BN_bn2dec failed on %s.\n", bn2dec_tests[i]);
1899             goto err;
1900         }
1901
1902         if (strcmp(dec, bn2dec_tests[i]) != 0) {
1903             fprintf(stderr, "BN_bn2dec gave %s, wanted %s.\n", dec,
1904                     bn2dec_tests[i]);
1905             goto err;
1906         }
1907
1908         OPENSSL_free(dec);
1909         dec = NULL;
1910     }
1911
1912     ret = 1;
1913
1914 err:
1915     BN_free(bn);
1916     OPENSSL_free(dec);
1917     return ret;
1918 }
1919
1920 int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_)
1921 {
1922     BIGNUM *a, *b, *c, *d;
1923     int i;
1924
1925     b = BN_new();
1926     c = BN_new();
1927     d = BN_new();
1928     BN_one(c);
1929
1930     if (a_)
1931         a = a_;
1932     else {
1933         a = BN_new();
1934         BN_bntest_rand(a, 200, 0, 0);
1935         a->neg = rand_neg();
1936     }
1937     for (i = 0; i < num0; i++) {
1938         BN_lshift(b, a, i + 1);
1939         BN_add(c, c, c);
1940         if (bp != NULL) {
1941             if (!results) {
1942                 BN_print(bp, a);
1943                 BIO_puts(bp, " * ");
1944                 BN_print(bp, c);
1945                 BIO_puts(bp, " - ");
1946             }
1947             BN_print(bp, b);
1948             BIO_puts(bp, "\n");
1949         }
1950         BN_mul(d, a, c, ctx);
1951         BN_sub(d, d, b);
1952         if (!BN_is_zero(d)) {
1953             fprintf(stderr, "Left shift test failed!\n");
1954             fprintf(stderr, "a=");
1955             BN_print_fp(stderr, a);
1956             fprintf(stderr, "\nb=");
1957             BN_print_fp(stderr, b);
1958             fprintf(stderr, "\nc=");
1959             BN_print_fp(stderr, c);
1960             fprintf(stderr, "\nd=");
1961             BN_print_fp(stderr, d);
1962             fprintf(stderr, "\n");
1963             return 0;
1964         }
1965     }
1966     BN_free(a);
1967     BN_free(b);
1968     BN_free(c);
1969     BN_free(d);
1970     return (1);
1971 }
1972
1973 int test_lshift1(BIO *bp)
1974 {
1975     BIGNUM *a, *b, *c;
1976     int i;
1977
1978     a = BN_new();
1979     b = BN_new();
1980     c = BN_new();
1981
1982     BN_bntest_rand(a, 200, 0, 0);
1983     a->neg = rand_neg();
1984     for (i = 0; i < num0; i++) {
1985         BN_lshift1(b, a);
1986         if (bp != NULL) {
1987             if (!results) {
1988                 BN_print(bp, a);
1989                 BIO_puts(bp, " * 2");
1990                 BIO_puts(bp, " - ");
1991             }
1992             BN_print(bp, b);
1993             BIO_puts(bp, "\n");
1994         }
1995         BN_add(c, a, a);
1996         BN_sub(a, b, c);
1997         if (!BN_is_zero(a)) {
1998             fprintf(stderr, "Left shift one test failed!\n");
1999             return 0;
2000         }
2001
2002         BN_copy(a, b);
2003     }
2004     BN_free(a);
2005     BN_free(b);
2006     BN_free(c);
2007     return (1);
2008 }
2009
2010 int test_rshift(BIO *bp, BN_CTX *ctx)
2011 {
2012     BIGNUM *a, *b, *c, *d, *e;
2013     int i;
2014
2015     a = BN_new();
2016     b = BN_new();
2017     c = BN_new();
2018     d = BN_new();
2019     e = BN_new();
2020     BN_one(c);
2021
2022     BN_bntest_rand(a, 200, 0, 0);
2023     a->neg = rand_neg();
2024     for (i = 0; i < num0; i++) {
2025         BN_rshift(b, a, i + 1);
2026         BN_add(c, c, c);
2027         if (bp != NULL) {
2028             if (!results) {
2029                 BN_print(bp, a);
2030                 BIO_puts(bp, " / ");
2031                 BN_print(bp, c);
2032                 BIO_puts(bp, " - ");
2033             }
2034             BN_print(bp, b);
2035             BIO_puts(bp, "\n");
2036         }
2037         BN_div(d, e, a, c, ctx);
2038         BN_sub(d, d, b);
2039         if (!BN_is_zero(d)) {
2040             fprintf(stderr, "Right shift test failed!\n");
2041             return 0;
2042         }
2043     }
2044     BN_free(a);
2045     BN_free(b);
2046     BN_free(c);
2047     BN_free(d);
2048     BN_free(e);
2049     return (1);
2050 }
2051
2052 int test_rshift1(BIO *bp)
2053 {
2054     BIGNUM *a, *b, *c;
2055     int i;
2056
2057     a = BN_new();
2058     b = BN_new();
2059     c = BN_new();
2060
2061     BN_bntest_rand(a, 200, 0, 0);
2062     a->neg = rand_neg();
2063     for (i = 0; i < num0; i++) {
2064         BN_rshift1(b, a);
2065         if (bp != NULL) {
2066             if (!results) {
2067                 BN_print(bp, a);
2068                 BIO_puts(bp, " / 2");
2069                 BIO_puts(bp, " - ");
2070             }
2071             BN_print(bp, b);
2072             BIO_puts(bp, "\n");
2073         }
2074         BN_sub(c, a, b);
2075         BN_sub(c, c, b);
2076         if (!BN_is_zero(c) && !BN_abs_is_word(c, 1)) {
2077             fprintf(stderr, "Right shift one test failed!\n");
2078             return 0;
2079         }
2080         BN_copy(a, b);
2081     }
2082     BN_free(a);
2083     BN_free(b);
2084     BN_free(c);
2085     return (1);
2086 }
2087
2088 int rand_neg(void)
2089 {
2090     static unsigned int neg = 0;
2091     static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 };
2092
2093     return (sign[(neg++) % 8]);
2094 }