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