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