1 /* Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay (at) cryptsoft.com). 6 * The implementation was written so as to conform with Netscapes SSL. 7 * 8 * This library is free for commercial and non-commercial use as long as 9 * the following conditions are aheared to. The following conditions 10 * apply to all code found in this distribution, be it the RC4, RSA, 11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 12 * included with this distribution is covered by the same copyright terms 13 * except that the holder is Tim Hudson (tjh (at) cryptsoft.com). 14 * 15 * Copyright remains Eric Young's, and as such any Copyright notices in 16 * the code are not to be removed. 17 * If this package is used in a product, Eric Young should be given attribution 18 * as the author of the parts of the library used. 19 * This can be in the form of a textual message at program startup or 20 * in documentation (online or textual) provided with the package. 21 * 22 * Redistribution and use in source and binary forms, with or without 23 * modification, are permitted provided that the following conditions 24 * are met: 25 * 1. Redistributions of source code must retain the copyright 26 * notice, this list of conditions and the following disclaimer. 27 * 2. Redistributions in binary form must reproduce the above copyright 28 * notice, this list of conditions and the following disclaimer in the 29 * documentation and/or other materials provided with the distribution. 30 * 3. All advertising materials mentioning features or use of this software 31 * must display the following acknowledgement: 32 * "This product includes cryptographic software written by 33 * Eric Young (eay (at) cryptsoft.com)" 34 * The word 'cryptographic' can be left out if the rouines from the library 35 * being used are not cryptographic related :-). 36 * 4. If you include any Windows specific code (or a derivative thereof) from 37 * the apps directory (application code) you must include an acknowledgement: 38 * "This product includes software written by Tim Hudson (tjh (at) cryptsoft.com)" 39 * 40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50 * SUCH DAMAGE. 51 * 52 * The licence and distribution terms for any publically available version or 53 * derivative of this code cannot be changed. i.e. this code cannot simply be 54 * copied and put under another distribution licence 55 * [including the GNU Public Licence.] 56 */ 57 /* ==================================================================== 58 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 59 * 60 * Portions of the attached software ("Contribution") are developed by 61 * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. 62 * 63 * The Contribution is licensed pursuant to the Eric Young open source 64 * license provided above. 65 * 66 * The binary polynomial arithmetic software is originally written by 67 * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems 68 * Laboratories. */ 69 70 #include <stdio.h> 71 72 #include <openssl/bio.h> 73 #include <openssl/bn.h> 74 #include <openssl/crypto.h> 75 #include <openssl/err.h> 76 #include <openssl/mem.h> 77 78 #include "internal.h" 79 80 static const int num0 = 100; /* number of tests */ 81 static const int num1 = 50; /* additional tests for some functions */ 82 static const int num2 = 5; /* number of tests for slow functions */ 83 84 int test_add(BIO *bp); 85 int test_sub(BIO *bp); 86 int test_lshift1(BIO *bp); 87 int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_); 88 int test_rshift1(BIO *bp); 89 int test_rshift(BIO *bp, BN_CTX *ctx); 90 int test_sqr(BIO *bp, BN_CTX *ctx); 91 int test_mul(BIO *bp); 92 int test_div(BIO *bp, BN_CTX *ctx); 93 int rand_neg(void); 94 95 int test_div_word(BIO *bp); 96 int test_mont(BIO *bp, BN_CTX *ctx); 97 int test_mod(BIO *bp, BN_CTX *ctx); 98 int test_mod_mul(BIO *bp, BN_CTX *ctx); 99 int test_mod_exp(BIO *bp, BN_CTX *ctx); 100 int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx); 101 int test_exp(BIO *bp, BN_CTX *ctx); 102 int test_mod_sqrt(BIO *bp, BN_CTX *ctx); 103 static int test_exp_mod_zero(void); 104 int test_small_prime(BIO *bp,BN_CTX *ctx); 105 int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx); 106 int test_sqrt(BIO *bp, BN_CTX *ctx); 107 int test_bn2bin_padded(BIO *bp, BN_CTX *ctx); 108 #if 0 109 int test_gf2m_add(BIO *bp); 110 int test_gf2m_mod(BIO *bp); 111 int test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx); 112 int test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx); 113 int test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx); 114 int test_gf2m_mod_div(BIO *bp, BN_CTX *ctx); 115 int test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx); 116 int test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx); 117 int test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx); 118 #endif 119 static int results = 0; 120 121 static unsigned char lst[] = 122 "\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9" 123 "\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0"; 124 125 static void ERR_print_errors_fp(FILE *out) { 126 } 127 128 static void message(BIO *out, char *m) { 129 BIO_puts(out, "print \"test "); 130 BIO_puts(out, m); 131 BIO_puts(out, "\\n\"\n"); 132 } 133 134 int main(int argc, char *argv[]) { 135 BN_CTX *ctx; 136 BIO *out = NULL; 137 char *outfile = NULL; 138 139 CRYPTO_library_init(); 140 141 results = 0; 142 143 argc--; 144 argv++; 145 while (argc >= 1) { 146 if (strcmp(*argv, "-results") == 0) 147 results = 1; 148 else if (strcmp(*argv, "-out") == 0) { 149 if (--argc < 1) 150 break; 151 outfile = *(++argv); 152 } 153 argc--; 154 argv++; 155 } 156 157 158 ctx = BN_CTX_new(); 159 if (ctx == NULL) 160 return 1; 161 162 out = BIO_new(BIO_s_file()); 163 if (out == NULL) { 164 return 1; 165 } 166 167 if (outfile == NULL) { 168 BIO_set_fp(out, stdout, BIO_NOCLOSE); 169 } else { 170 if (!BIO_write_filename(out, outfile)) { 171 perror(outfile); 172 return 1; 173 } 174 } 175 176 if (!results) 177 BIO_puts(out, "obase=16\nibase=16\n"); 178 179 message(out, "BN_add"); 180 if (!test_add(out)) 181 goto err; 182 (void)BIO_flush(out); 183 184 message(out, "BN_sub"); 185 if (!test_sub(out)) 186 goto err; 187 (void)BIO_flush(out); 188 189 message(out, "BN_lshift1"); 190 if (!test_lshift1(out)) 191 goto err; 192 (void)BIO_flush(out); 193 194 message(out, "BN_lshift (fixed)"); 195 if (!test_lshift(out, ctx, BN_bin2bn(lst, sizeof(lst) - 1, NULL))) 196 goto err; 197 (void)BIO_flush(out); 198 199 message(out, "BN_lshift"); 200 if (!test_lshift(out, ctx, NULL)) 201 goto err; 202 (void)BIO_flush(out); 203 204 message(out, "BN_rshift1"); 205 if (!test_rshift1(out)) 206 goto err; 207 (void)BIO_flush(out); 208 209 message(out, "BN_rshift"); 210 if (!test_rshift(out, ctx)) 211 goto err; 212 (void)BIO_flush(out); 213 214 message(out, "BN_sqr"); 215 if (!test_sqr(out, ctx)) 216 goto err; 217 (void)BIO_flush(out); 218 219 message(out, "BN_mul"); 220 if (!test_mul(out)) 221 goto err; 222 (void)BIO_flush(out); 223 224 message(out, "BN_div"); 225 if (!test_div(out, ctx)) 226 goto err; 227 (void)BIO_flush(out); 228 229 message(out, "BN_div_word"); 230 if (!test_div_word(out)) 231 goto err; 232 (void)BIO_flush(out); 233 234 message(out, "BN_mod"); 235 if (!test_mod(out, ctx)) 236 goto err; 237 (void)BIO_flush(out); 238 239 message(out, "BN_mod_mul"); 240 if (!test_mod_mul(out, ctx)) 241 goto err; 242 (void)BIO_flush(out); 243 244 message(out, "BN_mont"); 245 if (!test_mont(out, ctx)) 246 goto err; 247 (void)BIO_flush(out); 248 249 message(out, "BN_mod_exp"); 250 if (!test_mod_exp(out, ctx)) 251 goto err; 252 (void)BIO_flush(out); 253 254 message(out, "BN_mod_exp_mont_consttime"); 255 if (!test_mod_exp_mont_consttime(out, ctx) || 256 !test_mod_exp_mont5(out, ctx)) { 257 goto err; 258 } 259 (void)BIO_flush(out); 260 261 message(out, "BN_exp"); 262 if (!test_exp(out, ctx) || 263 !test_exp_mod_zero()) { 264 goto err; 265 } 266 (void)BIO_flush(out); 267 268 message(out, "BN_mod_sqrt"); 269 if (!test_mod_sqrt(out, ctx)) 270 goto err; 271 (void)BIO_flush(out); 272 273 message(out, "Small prime generation"); 274 if (!test_small_prime(out, ctx)) 275 goto err; 276 (void)BIO_flush(out); 277 278 message(out, "BN_sqrt"); 279 if (!test_sqrt(out, ctx)) 280 goto err; 281 (void)BIO_flush(out); 282 283 message(out, "BN_bn2bin_padded"); 284 if (!test_bn2bin_padded(out, ctx)) 285 goto err; 286 (void)BIO_flush(out); 287 288 BN_CTX_free(ctx); 289 BIO_free(out); 290 291 printf("PASS\n"); 292 return 0; 293 294 err: 295 BIO_puts(out, "1\n"); /* make sure the Perl script fed by bc notices 296 * the failure, see test_bn in test/Makefile.ssl*/ 297 (void)BIO_flush(out); 298 299 return 1; 300 } 301 302 int test_add(BIO *bp) { 303 BIGNUM a, b, c; 304 int i; 305 306 BN_init(&a); 307 BN_init(&b); 308 BN_init(&c); 309 310 BN_rand(&a, 512, 0, 0); 311 for (i = 0; i < num0; i++) { 312 BN_rand(&b, 450 + i, 0, 0); 313 a.neg = rand_neg(); 314 b.neg = rand_neg(); 315 BN_add(&c, &a, &b); 316 if (bp != NULL) { 317 if (!results) { 318 BN_print(bp, &a); 319 BIO_puts(bp, " + "); 320 BN_print(bp, &b); 321 BIO_puts(bp, " - "); 322 } 323 BN_print(bp, &c); 324 BIO_puts(bp, "\n"); 325 } 326 a.neg = !a.neg; 327 b.neg = !b.neg; 328 BN_add(&c, &c, &b); 329 BN_add(&c, &c, &a); 330 if (!BN_is_zero(&c)) { 331 fprintf(stderr, "Add test failed!\n"); 332 return 0; 333 } 334 } 335 BN_free(&a); 336 BN_free(&b); 337 BN_free(&c); 338 return (1); 339 } 340 341 int test_sub(BIO *bp) { 342 BIGNUM a, b, c; 343 int i; 344 345 BN_init(&a); 346 BN_init(&b); 347 BN_init(&c); 348 349 for (i = 0; i < num0 + num1; i++) { 350 if (i < num1) { 351 BN_rand(&a, 512, 0, 0); 352 BN_copy(&b, &a); 353 if (BN_set_bit(&a, i) == 0) 354 return (0); 355 BN_add_word(&b, i); 356 } else { 357 BN_rand(&b, 400 + i - num1, 0, 0); 358 a.neg = rand_neg(); 359 b.neg = rand_neg(); 360 } 361 BN_sub(&c, &a, &b); 362 if (bp != NULL) { 363 if (!results) { 364 BN_print(bp, &a); 365 BIO_puts(bp, " - "); 366 BN_print(bp, &b); 367 BIO_puts(bp, " - "); 368 } 369 BN_print(bp, &c); 370 BIO_puts(bp, "\n"); 371 } 372 BN_add(&c, &c, &b); 373 BN_sub(&c, &c, &a); 374 if (!BN_is_zero(&c)) { 375 fprintf(stderr, "Subtract test failed!\n"); 376 return 0; 377 } 378 } 379 BN_free(&a); 380 BN_free(&b); 381 BN_free(&c); 382 return (1); 383 } 384 385 int test_div(BIO *bp, BN_CTX *ctx) { 386 BIGNUM a, b, c, d, e; 387 int i; 388 389 BN_init(&a); 390 BN_init(&b); 391 BN_init(&c); 392 BN_init(&d); 393 BN_init(&e); 394 395 for (i = 0; i < num0 + num1; i++) { 396 if (i < num1) { 397 BN_rand(&a, 400, 0, 0); 398 BN_copy(&b, &a); 399 BN_lshift(&a, &a, i); 400 BN_add_word(&a, i); 401 } else 402 BN_rand(&b, 50 + 3 * (i - num1), 0, 0); 403 a.neg = rand_neg(); 404 b.neg = rand_neg(); 405 BN_div(&d, &c, &a, &b, ctx); 406 if (bp != NULL) { 407 if (!results) { 408 BN_print(bp, &a); 409 BIO_puts(bp, " / "); 410 BN_print(bp, &b); 411 BIO_puts(bp, " - "); 412 } 413 BN_print(bp, &d); 414 BIO_puts(bp, "\n"); 415 416 if (!results) { 417 BN_print(bp, &a); 418 BIO_puts(bp, " % "); 419 BN_print(bp, &b); 420 BIO_puts(bp, " - "); 421 } 422 BN_print(bp, &c); 423 BIO_puts(bp, "\n"); 424 } 425 BN_mul(&e, &d, &b, ctx); 426 BN_add(&d, &e, &c); 427 BN_sub(&d, &d, &a); 428 if (!BN_is_zero(&d)) { 429 fprintf(stderr, "Division test failed!\n"); 430 return 0; 431 } 432 } 433 BN_free(&a); 434 BN_free(&b); 435 BN_free(&c); 436 BN_free(&d); 437 BN_free(&e); 438 return (1); 439 } 440 441 int test_lshift1(BIO *bp) { 442 BIGNUM *a, *b, *c; 443 int i; 444 445 a = BN_new(); 446 b = BN_new(); 447 c = BN_new(); 448 449 BN_rand(a, 200, 0, 0); /**/ 450 a->neg = rand_neg(); 451 for (i = 0; i < num0; i++) { 452 BN_lshift1(b, a); 453 if (bp != NULL) { 454 if (!results) { 455 BN_print(bp, a); 456 BIO_puts(bp, " * 2"); 457 BIO_puts(bp, " - "); 458 } 459 BN_print(bp, b); 460 BIO_puts(bp, "\n"); 461 } 462 BN_add(c, a, a); 463 BN_sub(a, b, c); 464 if (!BN_is_zero(a)) { 465 fprintf(stderr, "Left shift one test failed!\n"); 466 return 0; 467 } 468 469 BN_copy(a, b); 470 } 471 BN_free(a); 472 BN_free(b); 473 BN_free(c); 474 return (1); 475 } 476 477 int test_rshift(BIO *bp, BN_CTX *ctx) { 478 BIGNUM *a, *b, *c, *d, *e; 479 int i; 480 481 a = BN_new(); 482 b = BN_new(); 483 c = BN_new(); 484 d = BN_new(); 485 e = BN_new(); 486 BN_one(c); 487 488 BN_rand(a, 200, 0, 0); /**/ 489 a->neg = rand_neg(); 490 for (i = 0; i < num0; i++) { 491 BN_rshift(b, a, i + 1); 492 BN_add(c, c, c); 493 if (bp != NULL) { 494 if (!results) { 495 BN_print(bp, a); 496 BIO_puts(bp, " / "); 497 BN_print(bp, c); 498 BIO_puts(bp, " - "); 499 } 500 BN_print(bp, b); 501 BIO_puts(bp, "\n"); 502 } 503 BN_div(d, e, a, c, ctx); 504 BN_sub(d, d, b); 505 if (!BN_is_zero(d)) { 506 fprintf(stderr, "Right shift test failed!\n"); 507 return 0; 508 } 509 } 510 BN_free(a); 511 BN_free(b); 512 BN_free(c); 513 BN_free(d); 514 BN_free(e); 515 return (1); 516 } 517 518 int test_rshift1(BIO *bp) { 519 BIGNUM *a, *b, *c; 520 int i; 521 522 a = BN_new(); 523 b = BN_new(); 524 c = BN_new(); 525 526 BN_rand(a, 200, 0, 0); /**/ 527 a->neg = rand_neg(); 528 for (i = 0; i < num0; i++) { 529 BN_rshift1(b, a); 530 if (bp != NULL) { 531 if (!results) { 532 BN_print(bp, a); 533 BIO_puts(bp, " / 2"); 534 BIO_puts(bp, " - "); 535 } 536 BN_print(bp, b); 537 BIO_puts(bp, "\n"); 538 } 539 BN_sub(c, a, b); 540 BN_sub(c, c, b); 541 if (!BN_is_zero(c) && !BN_abs_is_word(c, 1)) { 542 fprintf(stderr, "Right shift one test failed!\n"); 543 return 0; 544 } 545 BN_copy(a, b); 546 } 547 BN_free(a); 548 BN_free(b); 549 BN_free(c); 550 return (1); 551 } 552 553 int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_) { 554 BIGNUM *a, *b, *c, *d; 555 int i; 556 557 b = BN_new(); 558 c = BN_new(); 559 d = BN_new(); 560 BN_one(c); 561 562 if (a_) 563 a = a_; 564 else { 565 a = BN_new(); 566 BN_rand(a, 200, 0, 0); /**/ 567 a->neg = rand_neg(); 568 } 569 for (i = 0; i < num0; i++) { 570 BN_lshift(b, a, i + 1); 571 BN_add(c, c, c); 572 if (bp != NULL) { 573 if (!results) { 574 BN_print(bp, a); 575 BIO_puts(bp, " * "); 576 BN_print(bp, c); 577 BIO_puts(bp, " - "); 578 } 579 BN_print(bp, b); 580 BIO_puts(bp, "\n"); 581 } 582 BN_mul(d, a, c, ctx); 583 BN_sub(d, d, b); 584 if (!BN_is_zero(d)) { 585 fprintf(stderr, "Left shift test failed!\n"); 586 fprintf(stderr, "a="); 587 BN_print_fp(stderr, a); 588 fprintf(stderr, "\nb="); 589 BN_print_fp(stderr, b); 590 fprintf(stderr, "\nc="); 591 BN_print_fp(stderr, c); 592 fprintf(stderr, "\nd="); 593 BN_print_fp(stderr, d); 594 fprintf(stderr, "\n"); 595 return 0; 596 } 597 } 598 BN_free(a); 599 BN_free(b); 600 BN_free(c); 601 BN_free(d); 602 return (1); 603 } 604 605 int test_mul(BIO *bp) { 606 BIGNUM a, b, c, d, e; 607 int i; 608 BN_CTX *ctx; 609 610 ctx = BN_CTX_new(); 611 if (ctx == NULL) 612 abort(); 613 614 BN_init(&a); 615 BN_init(&b); 616 BN_init(&c); 617 BN_init(&d); 618 BN_init(&e); 619 620 for (i = 0; i < num0 + num1; i++) { 621 if (i <= num1) { 622 BN_rand(&a, 100, 0, 0); 623 BN_rand(&b, 100, 0, 0); 624 } else 625 BN_rand(&b, i - num1, 0, 0); 626 a.neg = rand_neg(); 627 b.neg = rand_neg(); 628 BN_mul(&c, &a, &b, ctx); 629 if (bp != NULL) { 630 if (!results) { 631 BN_print(bp, &a); 632 BIO_puts(bp, " * "); 633 BN_print(bp, &b); 634 BIO_puts(bp, " - "); 635 } 636 BN_print(bp, &c); 637 BIO_puts(bp, "\n"); 638 } 639 BN_div(&d, &e, &c, &a, ctx); 640 BN_sub(&d, &d, &b); 641 if (!BN_is_zero(&d) || !BN_is_zero(&e)) { 642 fprintf(stderr, "Multiplication test failed!\n"); 643 return 0; 644 } 645 } 646 BN_free(&a); 647 BN_free(&b); 648 BN_free(&c); 649 BN_free(&d); 650 BN_free(&e); 651 BN_CTX_free(ctx); 652 return (1); 653 } 654 655 int test_sqr(BIO *bp, BN_CTX *ctx) { 656 BIGNUM a, c, d, e; 657 int i; 658 659 BN_init(&a); 660 BN_init(&c); 661 BN_init(&d); 662 BN_init(&e); 663 664 for (i = 0; i < num0; i++) { 665 BN_rand(&a, 40 + i * 10, 0, 0); 666 a.neg = rand_neg(); 667 BN_sqr(&c, &a, ctx); 668 if (bp != NULL) { 669 if (!results) { 670 BN_print(bp, &a); 671 BIO_puts(bp, " * "); 672 BN_print(bp, &a); 673 BIO_puts(bp, " - "); 674 } 675 BN_print(bp, &c); 676 BIO_puts(bp, "\n"); 677 } 678 BN_div(&d, &e, &c, &a, ctx); 679 BN_sub(&d, &d, &a); 680 if (!BN_is_zero(&d) || !BN_is_zero(&e)) { 681 fprintf(stderr, "Square test failed!\n"); 682 return 0; 683 } 684 } 685 BN_free(&a); 686 BN_free(&c); 687 BN_free(&d); 688 BN_free(&e); 689 return (1); 690 } 691 692 693 int rand_neg(void) { 694 static unsigned int neg = 0; 695 static int sign[8] = {0, 0, 0, 1, 1, 0, 1, 1}; 696 697 return (sign[(neg++) % 8]); 698 } 699 700 static void print_word(BIO *bp, BN_ULONG w) { 701 BIO_printf(bp, BN_HEX_FMT1, w); 702 } 703 704 int test_div_word(BIO *bp) { 705 BIGNUM a, b; 706 BN_ULONG r, s; 707 int i; 708 709 BN_init(&a); 710 BN_init(&b); 711 712 for (i = 0; i < num0; i++) { 713 do { 714 BN_rand(&a, 512, -1, 0); 715 BN_rand(&b, BN_BITS2, -1, 0); 716 s = b.d[0]; 717 } while (!s); 718 719 BN_copy(&b, &a); 720 r = BN_div_word(&b, s); 721 722 if (bp != NULL) { 723 if (!results) { 724 BN_print(bp, &a); 725 BIO_puts(bp, " / "); 726 print_word(bp, s); 727 BIO_puts(bp, " - "); 728 } 729 BN_print(bp, &b); 730 BIO_puts(bp, "\n"); 731 732 if (!results) { 733 BN_print(bp, &a); 734 BIO_puts(bp, " % "); 735 print_word(bp, s); 736 BIO_puts(bp, " - "); 737 } 738 print_word(bp, r); 739 BIO_puts(bp, "\n"); 740 } 741 BN_mul_word(&b, s); 742 BN_add_word(&b, r); 743 BN_sub(&b, &a, &b); 744 if (!BN_is_zero(&b)) { 745 fprintf(stderr, "Division (word) test failed!\n"); 746 return 0; 747 } 748 } 749 BN_free(&a); 750 BN_free(&b); 751 return (1); 752 } 753 754 int test_mont(BIO *bp, BN_CTX *ctx) { 755 BIGNUM a, b, c, d, A, B; 756 BIGNUM n; 757 int i; 758 BN_MONT_CTX *mont; 759 760 BN_init(&a); 761 BN_init(&b); 762 BN_init(&c); 763 BN_init(&d); 764 BN_init(&A); 765 BN_init(&B); 766 BN_init(&n); 767 768 mont = BN_MONT_CTX_new(); 769 if (mont == NULL) 770 return 0; 771 772 BN_rand(&a, 100, 0, 0); /**/ 773 BN_rand(&b, 100, 0, 0); /**/ 774 for (i = 0; i < num2; i++) { 775 int bits = (200 * (i + 1)) / num2; 776 777 if (bits == 0) 778 continue; 779 BN_rand(&n, bits, 0, 1); 780 BN_MONT_CTX_set(mont, &n, ctx); 781 782 BN_nnmod(&a, &a, &n, ctx); 783 BN_nnmod(&b, &b, &n, ctx); 784 785 BN_to_montgomery(&A, &a, mont, ctx); 786 BN_to_montgomery(&B, &b, mont, ctx); 787 788 BN_mod_mul_montgomery(&c, &A, &B, mont, ctx); /**/ 789 BN_from_montgomery(&A, &c, mont, ctx); /**/ 790 if (bp != NULL) { 791 if (!results) { 792 #ifdef undef 793 fprintf(stderr, "%d * %d %% %d\n", BN_num_bits(&a), BN_num_bits(&b), 794 BN_num_bits(mont->N)); 795 #endif 796 BN_print(bp, &a); 797 BIO_puts(bp, " * "); 798 BN_print(bp, &b); 799 BIO_puts(bp, " % "); 800 BN_print(bp, &(mont->N)); 801 BIO_puts(bp, " - "); 802 } 803 BN_print(bp, &A); 804 BIO_puts(bp, "\n"); 805 } 806 BN_mod_mul(&d, &a, &b, &n, ctx); 807 BN_sub(&d, &d, &A); 808 if (!BN_is_zero(&d)) { 809 fprintf(stderr, "Montgomery multiplication test failed!\n"); 810 return 0; 811 } 812 } 813 BN_MONT_CTX_free(mont); 814 BN_free(&a); 815 BN_free(&b); 816 BN_free(&c); 817 BN_free(&d); 818 BN_free(&A); 819 BN_free(&B); 820 BN_free(&n); 821 return (1); 822 } 823 824 int test_mod(BIO *bp, BN_CTX *ctx) { 825 BIGNUM *a, *b, *c, *d, *e; 826 int i; 827 828 a = BN_new(); 829 b = BN_new(); 830 c = BN_new(); 831 d = BN_new(); 832 e = BN_new(); 833 834 BN_rand(a, 1024, 0, 0); /**/ 835 for (i = 0; i < num0; i++) { 836 BN_rand(b, 450 + i * 10, 0, 0); /**/ 837 a->neg = rand_neg(); 838 b->neg = rand_neg(); 839 BN_mod(c, a, b, ctx); /**/ 840 if (bp != NULL) { 841 if (!results) { 842 BN_print(bp, a); 843 BIO_puts(bp, " % "); 844 BN_print(bp, b); 845 BIO_puts(bp, " - "); 846 } 847 BN_print(bp, c); 848 BIO_puts(bp, "\n"); 849 } 850 BN_div(d, e, a, b, ctx); 851 BN_sub(e, e, c); 852 if (!BN_is_zero(e)) { 853 fprintf(stderr, "Modulo test failed!\n"); 854 return 0; 855 } 856 } 857 BN_free(a); 858 BN_free(b); 859 BN_free(c); 860 BN_free(d); 861 BN_free(e); 862 return (1); 863 } 864 865 int test_mod_mul(BIO *bp, BN_CTX *ctx) { 866 BIGNUM *a, *b, *c, *d, *e; 867 int i, j; 868 869 a = BN_new(); 870 b = BN_new(); 871 c = BN_new(); 872 d = BN_new(); 873 e = BN_new(); 874 875 for (j = 0; j < 3; j++) { 876 BN_rand(c, 1024, 0, 0); /**/ 877 for (i = 0; i < num0; i++) { 878 BN_rand(a, 475 + i * 10, 0, 0); /**/ 879 BN_rand(b, 425 + i * 11, 0, 0); /**/ 880 a->neg = rand_neg(); 881 b->neg = rand_neg(); 882 if (!BN_mod_mul(e, a, b, c, ctx)) { 883 unsigned long l; 884 885 while ((l = ERR_get_error())) 886 fprintf(stderr, "ERROR:%s\n", ERR_error_string(l, NULL)); 887 abort(); 888 } 889 if (bp != NULL) { 890 if (!results) { 891 BN_print(bp, a); 892 BIO_puts(bp, " * "); 893 BN_print(bp, b); 894 BIO_puts(bp, " % "); 895 BN_print(bp, c); 896 if ((a->neg ^ b->neg) && !BN_is_zero(e)) { 897 /* If (a*b) % c is negative, c must be added 898 * in order to obtain the normalized remainder 899 * (new with OpenSSL 0.9.7, previous versions of 900 * BN_mod_mul could generate negative results) 901 */ 902 BIO_puts(bp, " + "); 903 BN_print(bp, c); 904 } 905 BIO_puts(bp, " - "); 906 } 907 BN_print(bp, e); 908 BIO_puts(bp, "\n"); 909 } 910 BN_mul(d, a, b, ctx); 911 BN_sub(d, d, e); 912 BN_div(a, b, d, c, ctx); 913 if (!BN_is_zero(b)) { 914 fprintf(stderr, "Modulo multiply test failed!\n"); 915 ERR_print_errors_fp(stderr); 916 return 0; 917 } 918 } 919 } 920 BN_free(a); 921 BN_free(b); 922 BN_free(c); 923 BN_free(d); 924 BN_free(e); 925 return (1); 926 } 927 928 int test_mod_exp(BIO *bp, BN_CTX *ctx) { 929 BIGNUM *a, *b, *c, *d, *e; 930 int i; 931 932 a = BN_new(); 933 b = BN_new(); 934 c = BN_new(); 935 d = BN_new(); 936 e = BN_new(); 937 938 BN_rand(c, 30, 0, 1); /* must be odd for montgomery */ 939 for (i = 0; i < num2; i++) { 940 BN_rand(a, 20 + i * 5, 0, 0); /**/ 941 BN_rand(b, 2 + i, 0, 0); /**/ 942 943 if (!BN_mod_exp(d, a, b, c, ctx)) 944 return (0); 945 946 if (bp != NULL) { 947 if (!results) { 948 BN_print(bp, a); 949 BIO_puts(bp, " ^ "); 950 BN_print(bp, b); 951 BIO_puts(bp, " % "); 952 BN_print(bp, c); 953 BIO_puts(bp, " - "); 954 } 955 BN_print(bp, d); 956 BIO_puts(bp, "\n"); 957 } 958 BN_exp(e, a, b, ctx); 959 BN_sub(e, e, d); 960 BN_div(a, b, e, c, ctx); 961 if (!BN_is_zero(b)) { 962 fprintf(stderr, "Modulo exponentiation test failed!\n"); 963 return 0; 964 } 965 } 966 BN_free(a); 967 BN_free(b); 968 BN_free(c); 969 BN_free(d); 970 BN_free(e); 971 return (1); 972 } 973 974 int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx) { 975 BIGNUM *a, *b, *c, *d, *e; 976 int i; 977 978 a = BN_new(); 979 b = BN_new(); 980 c = BN_new(); 981 d = BN_new(); 982 e = BN_new(); 983 984 BN_rand(c, 30, 0, 1); /* must be odd for montgomery */ 985 for (i = 0; i < num2; i++) { 986 BN_rand(a, 20 + i * 5, 0, 0); /**/ 987 BN_rand(b, 2 + i, 0, 0); /**/ 988 989 if (!BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) 990 return (00); 991 992 if (bp != NULL) { 993 if (!results) { 994 BN_print(bp, a); 995 BIO_puts(bp, " ^ "); 996 BN_print(bp, b); 997 BIO_puts(bp, " % "); 998 BN_print(bp, c); 999 BIO_puts(bp, " - "); 1000 } 1001 BN_print(bp, d); 1002 BIO_puts(bp, "\n"); 1003 } 1004 BN_exp(e, a, b, ctx); 1005 BN_sub(e, e, d); 1006 BN_div(a, b, e, c, ctx); 1007 if (!BN_is_zero(b)) { 1008 fprintf(stderr, "Modulo exponentiation test failed!\n"); 1009 return 0; 1010 } 1011 } 1012 BN_free(a); 1013 BN_free(b); 1014 BN_free(c); 1015 BN_free(d); 1016 BN_free(e); 1017 return (1); 1018 } 1019 1020 /* Test constant-time modular exponentiation with 1024-bit inputs, 1021 * which on x86_64 cause a different code branch to be taken. */ 1022 int test_mod_exp_mont5(BIO *bp, BN_CTX *ctx) { 1023 BIGNUM *a, *p, *m, *d, *e; 1024 1025 BN_MONT_CTX *mont; 1026 1027 a = BN_new(); 1028 p = BN_new(); 1029 m = BN_new(); 1030 d = BN_new(); 1031 e = BN_new(); 1032 1033 mont = BN_MONT_CTX_new(); 1034 1035 BN_rand(m, 1024, 0, 1); /* must be odd for montgomery */ 1036 /* Zero exponent */ 1037 BN_rand(a, 1024, 0, 0); 1038 BN_zero(p); 1039 if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)) 1040 return 0; 1041 if (!BN_is_one(d)) { 1042 fprintf(stderr, "Modular exponentiation test failed!\n"); 1043 return 0; 1044 } 1045 /* Zero input */ 1046 BN_rand(p, 1024, 0, 0); 1047 BN_zero(a); 1048 if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)) 1049 return 0; 1050 if (!BN_is_zero(d)) { 1051 fprintf(stderr, "Modular exponentiation test failed!\n"); 1052 return 0; 1053 } 1054 /* Craft an input whose Montgomery representation is 1, 1055 * i.e., shorter than the modulus m, in order to test 1056 * the const time precomputation scattering/gathering. 1057 */ 1058 BN_one(a); 1059 BN_MONT_CTX_set(mont, m, ctx); 1060 if (!BN_from_montgomery(e, a, mont, ctx) || 1061 !BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL) || 1062 !BN_mod_exp(a, e, p, m, ctx)) { 1063 return 0; 1064 } 1065 if (BN_cmp(a, d) != 0) { 1066 fprintf(stderr, "Modular exponentiation test failed!\n"); 1067 return 0; 1068 } 1069 /* Finally, some regular test vectors. */ 1070 BN_rand(e, 1024, 0, 0); 1071 if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL)) 1072 return 0; 1073 if (!BN_mod_exp(a, e, p, m, ctx)) 1074 return 0; 1075 if (BN_cmp(a, d) != 0) { 1076 fprintf(stderr, "Modular exponentiation test failed!\n"); 1077 return 0; 1078 } 1079 1080 BN_MONT_CTX_free(mont); 1081 BN_free(a); 1082 BN_free(p); 1083 BN_free(m); 1084 BN_free(d); 1085 BN_free(e); 1086 return (1); 1087 } 1088 1089 int test_exp(BIO *bp, BN_CTX *ctx) { 1090 BIGNUM *a, *b, *d, *e, *one; 1091 int i; 1092 1093 a = BN_new(); 1094 b = BN_new(); 1095 d = BN_new(); 1096 e = BN_new(); 1097 one = BN_new(); 1098 BN_one(one); 1099 1100 for (i = 0; i < num2; i++) { 1101 BN_rand(a, 20 + i * 5, 0, 0); /**/ 1102 BN_rand(b, 2 + i, 0, 0); /**/ 1103 1104 if (BN_exp(d, a, b, ctx) <= 0) 1105 return (0); 1106 1107 if (bp != NULL) { 1108 if (!results) { 1109 BN_print(bp, a); 1110 BIO_puts(bp, " ^ "); 1111 BN_print(bp, b); 1112 BIO_puts(bp, " - "); 1113 } 1114 BN_print(bp, d); 1115 BIO_puts(bp, "\n"); 1116 } 1117 BN_one(e); 1118 for (; !BN_is_zero(b); BN_sub(b, b, one)) 1119 BN_mul(e, e, a, ctx); 1120 BN_sub(e, e, d); 1121 if (!BN_is_zero(e)) { 1122 fprintf(stderr, "Exponentiation test failed!\n"); 1123 return 0; 1124 } 1125 } 1126 BN_free(a); 1127 BN_free(b); 1128 BN_free(d); 1129 BN_free(e); 1130 BN_free(one); 1131 return (1); 1132 } 1133 1134 /* test_exp_mod_zero tests that x**0 mod 1 == 0. */ 1135 static int test_exp_mod_zero(void) { 1136 BIGNUM a, p, m; 1137 BIGNUM r; 1138 BN_CTX *ctx = BN_CTX_new(); 1139 int ret = 0; 1140 1141 BN_init(&m); 1142 BN_one(&m); 1143 1144 BN_init(&a); 1145 BN_one(&a); 1146 1147 BN_init(&p); 1148 BN_zero(&p); 1149 1150 BN_init(&r); 1151 BN_mod_exp(&r, &a, &p, &m, ctx); 1152 BN_CTX_free(ctx); 1153 1154 if (BN_is_zero(&r)) { 1155 ret = 1; 1156 } else { 1157 printf("1**0 mod 1 = "); 1158 BN_print_fp(stdout, &r); 1159 printf(", should be 0\n"); 1160 } 1161 1162 BN_free(&r); 1163 BN_free(&a); 1164 BN_free(&p); 1165 BN_free(&m); 1166 1167 return ret; 1168 } 1169 1170 static int genprime_cb(int p, int n, BN_GENCB *arg) { 1171 char c = '*'; 1172 1173 if (p == 0) 1174 c = '.'; 1175 if (p == 1) 1176 c = '+'; 1177 if (p == 2) 1178 c = '*'; 1179 if (p == 3) 1180 c = '\n'; 1181 putc(c, stdout); 1182 fflush(stdout); 1183 return 1; 1184 } 1185 1186 int test_mod_sqrt(BIO *bp, BN_CTX *ctx) { 1187 BN_GENCB cb; 1188 BIGNUM *a, *p, *r; 1189 int i, j; 1190 int ret = 0; 1191 1192 a = BN_new(); 1193 p = BN_new(); 1194 r = BN_new(); 1195 if (a == NULL || p == NULL || r == NULL) 1196 goto err; 1197 1198 BN_GENCB_set(&cb, genprime_cb, NULL); 1199 1200 for (i = 0; i < 16; i++) { 1201 if (i < 8) { 1202 unsigned primes[8] = {2, 3, 5, 7, 11, 13, 17, 19}; 1203 1204 if (!BN_set_word(p, primes[i])) 1205 goto err; 1206 } else { 1207 if (!BN_set_word(a, 32)) 1208 goto err; 1209 if (!BN_set_word(r, 2 * i + 1)) 1210 goto err; 1211 1212 if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb)) 1213 goto err; 1214 putc('\n', stdout); 1215 } 1216 p->neg = rand_neg(); 1217 1218 for (j = 0; j < num2; j++) { 1219 /* construct 'a' such that it is a square modulo p, 1220 * but in general not a proper square and not reduced modulo p */ 1221 if (!BN_rand(r, 256, 0, 3)) 1222 goto err; 1223 if (!BN_nnmod(r, r, p, ctx)) 1224 goto err; 1225 if (!BN_mod_sqr(r, r, p, ctx)) 1226 goto err; 1227 if (!BN_rand(a, 256, 0, 3)) 1228 goto err; 1229 if (!BN_nnmod(a, a, p, ctx)) 1230 goto err; 1231 if (!BN_mod_sqr(a, a, p, ctx)) 1232 goto err; 1233 if (!BN_mul(a, a, r, ctx)) 1234 goto err; 1235 if (rand_neg()) 1236 if (!BN_sub(a, a, p)) 1237 goto err; 1238 1239 if (!BN_mod_sqrt(r, a, p, ctx)) 1240 goto err; 1241 if (!BN_mod_sqr(r, r, p, ctx)) 1242 goto err; 1243 1244 if (!BN_nnmod(a, a, p, ctx)) 1245 goto err; 1246 1247 if (BN_cmp(a, r) != 0) { 1248 fprintf(stderr, "BN_mod_sqrt failed: a = "); 1249 BN_print_fp(stderr, a); 1250 fprintf(stderr, ", r = "); 1251 BN_print_fp(stderr, r); 1252 fprintf(stderr, ", p = "); 1253 BN_print_fp(stderr, p); 1254 fprintf(stderr, "\n"); 1255 goto err; 1256 } 1257 1258 putc('.', stdout); 1259 fflush(stdout); 1260 } 1261 1262 putc('\n', stdout); 1263 fflush(stderr); 1264 } 1265 ret = 1; 1266 err: 1267 if (a != NULL) 1268 BN_free(a); 1269 if (p != NULL) 1270 BN_free(p); 1271 if (r != NULL) 1272 BN_free(r); 1273 return ret; 1274 } 1275 1276 int test_small_prime(BIO *bp, BN_CTX *ctx) { 1277 static const int bits = 10; 1278 int ret = 0; 1279 BIGNUM r; 1280 1281 BN_init(&r); 1282 if (!BN_generate_prime_ex(&r, bits, 0, NULL, NULL, NULL)) { 1283 goto err; 1284 } 1285 if (BN_num_bits(&r) != bits) { 1286 BIO_printf(bp, "Expected %d bit prime, got %d bit number\n", bits, 1287 BN_num_bits(&r)); 1288 goto err; 1289 } 1290 1291 ret = 1; 1292 1293 err: 1294 BN_free(&r); 1295 return ret; 1296 } 1297 1298 int test_sqrt(BIO *bp, BN_CTX *ctx) { 1299 BIGNUM *n = BN_new(), *nn = BN_new(), *sqrt = BN_new(); 1300 unsigned i; 1301 1302 /* Test some random squares. */ 1303 for (i = 0; i < 100; i++) { 1304 if (!BN_rand(n, 1024 /* bit length */, -1 /* no modification of top bits */, 1305 0 /* don't modify bottom bit */) || 1306 !BN_mul(nn, n, n, ctx) || 1307 !BN_sqrt(sqrt, nn, ctx)) { 1308 BIO_print_errors_fp(stderr); 1309 return 0; 1310 } 1311 if (BN_cmp(n, sqrt) != 0) { 1312 fprintf(stderr, "Bad result from BN_sqrt.\n"); 1313 return 0; 1314 } 1315 } 1316 1317 /* Test some non-squares */ 1318 for (i = 0; i < 100; i++) { 1319 if (!BN_rand(n, 1024 /* bit length */, -1 /* no modification of top bits */, 1320 0 /* don't modify bottom bit */) || 1321 !BN_mul(nn, n, n, ctx) || 1322 !BN_add(nn, nn, BN_value_one())) { 1323 BIO_print_errors_fp(stderr); 1324 return 0; 1325 } 1326 1327 if (BN_sqrt(sqrt, nn, ctx)) { 1328 char *nn_str = BN_bn2dec(nn); 1329 fprintf(stderr, "BIO_sqrt didn't fail on a non-square: %s\n", nn_str); 1330 OPENSSL_free(nn_str); 1331 } 1332 } 1333 1334 BN_free(n); 1335 BN_free(sqrt); 1336 BN_free(nn); 1337 1338 return 1; 1339 } 1340 1341 int test_bn2bin_padded(BIO *bp, BN_CTX *ctx) { 1342 BIGNUM *n = BN_new(); 1343 uint8_t zeros[256], out[256], reference[128]; 1344 size_t bytes; 1345 1346 memset(zeros, 0, sizeof(zeros)); 1347 1348 /* Test edge case at 0. */ 1349 if (!BN_bn2bin_padded(NULL, 0, n)) { 1350 fprintf(stderr, 1351 "BN_bn2bin_padded failed to encode 0 in an empty buffer.\n"); 1352 return 0; 1353 } 1354 memset(out, -1, sizeof(out)); 1355 if (!BN_bn2bin_padded(out, sizeof(out), n)) { 1356 fprintf(stderr, 1357 "BN_bn2bin_padded failed to encode 0 in a non-empty buffer.\n"); 1358 return 0; 1359 } 1360 if (memcmp(zeros, out, sizeof(out))) { 1361 fprintf(stderr, "BN_bn2bin_padded did not zero buffer.\n"); 1362 return 0; 1363 } 1364 1365 /* Test a random numbers at various byte lengths. */ 1366 for (bytes = 128 - 7; bytes <= 128; bytes++) { 1367 if (!BN_rand(n, bytes * 8, 0 /* make sure top bit is 1 */, 1368 0 /* don't modify bottom bit */)) { 1369 BIO_print_errors_fp(stderr); 1370 return 0; 1371 } 1372 if (BN_num_bytes(n) != bytes || BN_bn2bin(n, reference) != bytes) { 1373 fprintf(stderr, "Bad result from BN_rand; bytes.\n"); 1374 return 0; 1375 } 1376 /* Empty buffer should fail. */ 1377 if (BN_bn2bin_padded(NULL, 0, n)) { 1378 fprintf(stderr, 1379 "BN_bn2bin_padded incorrectly succeeded on empty buffer.\n"); 1380 return 0; 1381 } 1382 /* One byte short should fail. */ 1383 if (BN_bn2bin_padded(out, bytes - 1, n)) { 1384 fprintf(stderr, "BN_bn2bin_padded incorrectly succeeded on short.\n"); 1385 return 0; 1386 } 1387 /* Exactly right size should encode. */ 1388 if (!BN_bn2bin_padded(out, bytes, n) || 1389 memcmp(out, reference, bytes) != 0) { 1390 fprintf(stderr, "BN_bn2bin_padded gave a bad result.\n"); 1391 return 0; 1392 } 1393 /* Pad up one byte extra. */ 1394 if (!BN_bn2bin_padded(out, bytes + 1, n) || 1395 memcmp(out + 1, reference, bytes) || memcmp(out, zeros, 1)) { 1396 fprintf(stderr, "BN_bn2bin_padded gave a bad result.\n"); 1397 return 0; 1398 } 1399 /* Pad up to 256. */ 1400 if (!BN_bn2bin_padded(out, sizeof(out), n) || 1401 memcmp(out + sizeof(out) - bytes, reference, bytes) || 1402 memcmp(out, zeros, sizeof(out) - bytes)) { 1403 fprintf(stderr, "BN_bn2bin_padded gave a bad result.\n"); 1404 return 0; 1405 } 1406 } 1407 1408 BN_free(n); 1409 1410 return 1; 1411 } 1412