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