crypto/openssl/crypto/bn/bntest.c

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