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