test/bntest.c

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