1 /* $OpenBSD: bn_test.c,v 1.21 2025/01/22 10:12:28 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_set_negative(a, rand_neg()); 593 BN_set_negative(b, rand_neg()); 594 BN_RECP_CTX_free(recp); 595 CHECK_GOTO(recp = BN_RECP_CTX_create(b)); 596 CHECK_GOTO(BN_div_reciprocal(d, c, a, recp, ctx)); 597 if (bp != NULL) { 598 if (!results) { 599 CHECK_GOTO(BN_print(bp, a)); 600 BIO_puts(bp, " / "); 601 CHECK_GOTO(BN_print(bp, b)); 602 BIO_puts(bp, " - "); 603 } 604 CHECK_GOTO(BN_print(bp, d)); 605 BIO_puts(bp, "\n"); 606 607 if (!results) { 608 CHECK_GOTO(BN_print(bp, a)); 609 BIO_puts(bp, " % "); 610 CHECK_GOTO(BN_print(bp, b)); 611 BIO_puts(bp, " - "); 612 } 613 CHECK_GOTO(BN_print(bp, c)); 614 BIO_puts(bp, "\n"); 615 } 616 CHECK_GOTO(BN_mul(e, d, b, ctx)); 617 CHECK_GOTO(BN_add(d, e, c)); 618 CHECK_GOTO(BN_sub(d, d, a)); 619 if (!BN_is_zero(d)) { 620 fprintf(stderr, "Reciprocal division test failed!\n"); 621 fprintf(stderr, "a="); 622 CHECK_GOTO(BN_print_fp(stderr, a)); 623 fprintf(stderr, "\nb="); 624 CHECK_GOTO(BN_print_fp(stderr, b)); 625 fprintf(stderr, "\n"); 626 goto err; 627 } 628 } 629 630 ret = 1; 631 err: 632 BN_CTX_end(ctx); 633 BN_RECP_CTX_free(recp); 634 635 return ret; 636 } 637 638 int 639 test_mul(BIO *bp, BN_CTX *ctx) 640 { 641 BIGNUM *a, *b, *c, *d, *e; 642 int i; 643 int ret = 0; 644 645 BN_CTX_start(ctx); 646 647 if ((a = BN_CTX_get(ctx)) == NULL) 648 goto err; 649 if ((b = BN_CTX_get(ctx)) == NULL) 650 goto err; 651 if ((c = BN_CTX_get(ctx)) == NULL) 652 goto err; 653 if ((d = BN_CTX_get(ctx)) == NULL) 654 goto err; 655 if ((e = BN_CTX_get(ctx)) == NULL) 656 goto err; 657 658 for (i = 0; i < num0 + num1; i++) { 659 if (i <= num1) { 660 CHECK_GOTO(BN_bntest_rand(a, 100, 0, 0)); 661 CHECK_GOTO(BN_bntest_rand(b, 100, 0, 0)); 662 } else 663 CHECK_GOTO(BN_bntest_rand(b, i - num1, 0, 0)); 664 BN_set_negative(a, rand_neg()); 665 BN_set_negative(b, rand_neg()); 666 CHECK_GOTO(BN_mul(c, a, b, ctx)); 667 if (bp != NULL) { 668 if (!results) { 669 CHECK_GOTO(BN_print(bp, a)); 670 BIO_puts(bp, " * "); 671 CHECK_GOTO(BN_print(bp, b)); 672 BIO_puts(bp, " - "); 673 } 674 CHECK_GOTO(BN_print(bp, c)); 675 BIO_puts(bp, "\n"); 676 } 677 CHECK_GOTO(BN_div(d, e, c, a, ctx)); 678 CHECK_GOTO(BN_sub(d, d, b)); 679 if (!BN_is_zero(d) || !BN_is_zero(e)) { 680 fprintf(stderr, "Multiplication test failed!\n"); 681 goto err; 682 } 683 } 684 685 ret = 1; 686 err: 687 BN_CTX_end(ctx); 688 689 return ret; 690 } 691 692 int 693 test_sqr(BIO *bp, BN_CTX *ctx) 694 { 695 BIGNUM *a, *c, *d, *e; 696 int i; 697 int ret = 0; 698 699 BN_CTX_start(ctx); 700 701 if ((a = BN_CTX_get(ctx)) == NULL) 702 goto err; 703 if ((c = BN_CTX_get(ctx)) == NULL) 704 goto err; 705 if ((d = BN_CTX_get(ctx)) == NULL) 706 goto err; 707 if ((e = BN_CTX_get(ctx)) == NULL) 708 goto err; 709 710 for (i = 0; i < num0; i++) { 711 CHECK_GOTO(BN_bntest_rand(a, 40 + i * 10, 0, 0)); 712 BN_set_negative(a, rand_neg()); 713 CHECK_GOTO(BN_sqr(c, a, ctx)); 714 if (bp != NULL) { 715 if (!results) { 716 CHECK_GOTO(BN_print(bp, a)); 717 BIO_puts(bp, " * "); 718 CHECK_GOTO(BN_print(bp, a)); 719 BIO_puts(bp, " - "); 720 } 721 CHECK_GOTO(BN_print(bp, c)); 722 BIO_puts(bp, "\n"); 723 } 724 CHECK_GOTO(BN_div(d, e, c, a, ctx)); 725 CHECK_GOTO(BN_sub(d, d, a)); 726 if (!BN_is_zero(d) || !BN_is_zero(e)) { 727 fprintf(stderr, "Square test failed!\n"); 728 goto err; 729 } 730 } 731 732 /* Regression test for a BN_sqr overflow bug. */ 733 if (!BN_hex2bn(&a, "80000000000000008000000000000001" 734 "FFFFFFFFFFFFFFFE0000000000000000")) { 735 fprintf(stderr, "BN_hex2bn failed\n"); 736 goto err; 737 } 738 CHECK_GOTO(BN_sqr(c, a, ctx)); 739 if (bp != NULL) { 740 if (!results) { 741 CHECK_GOTO(BN_print(bp, a)); 742 BIO_puts(bp, " * "); 743 CHECK_GOTO(BN_print(bp, a)); 744 BIO_puts(bp, " - "); 745 } 746 CHECK_GOTO(BN_print(bp, c)); 747 BIO_puts(bp, "\n"); 748 } 749 CHECK_GOTO(BN_mul(d, a, a, ctx)); 750 if (BN_cmp(c, d)) { 751 fprintf(stderr, 752 "Square test failed: BN_sqr and BN_mul produce " 753 "different results!\n"); 754 goto err; 755 } 756 757 /* Regression test for a BN_sqr overflow bug. */ 758 if (!BN_hex2bn(&a, "80000000000000000000000080000001" 759 "FFFFFFFE000000000000000000000000")) { 760 fprintf(stderr, "BN_hex2bn failed\n"); 761 goto err; 762 } 763 CHECK_GOTO(BN_sqr(c, a, ctx)); 764 if (bp != NULL) { 765 if (!results) { 766 CHECK_GOTO(BN_print(bp, a)); 767 BIO_puts(bp, " * "); 768 CHECK_GOTO(BN_print(bp, a)); 769 BIO_puts(bp, " - "); 770 } 771 CHECK_GOTO(BN_print(bp, c)); 772 BIO_puts(bp, "\n"); 773 } 774 CHECK_GOTO(BN_mul(d, a, a, ctx)); 775 if (BN_cmp(c, d)) { 776 fprintf(stderr, "Square test failed: BN_sqr and BN_mul produce " 777 "different results!\n"); 778 goto err; 779 } 780 781 ret = 1; 782 err: 783 BN_CTX_end(ctx); 784 785 return ret; 786 } 787 788 int 789 test_mont(BIO *bp, BN_CTX *ctx) 790 { 791 BN_MONT_CTX *mont = NULL; 792 BIGNUM *a, *b, *c, *d, *A, *B, *n; 793 int i; 794 int ret = 0; 795 796 BN_CTX_start(ctx); 797 798 if ((a = BN_CTX_get(ctx)) == NULL) 799 goto err; 800 if ((b = BN_CTX_get(ctx)) == NULL) 801 goto err; 802 if ((c = BN_CTX_get(ctx)) == NULL) 803 goto err; 804 if ((d = BN_CTX_get(ctx)) == NULL) 805 goto err; 806 if ((A = BN_CTX_get(ctx)) == NULL) 807 goto err; 808 if ((B = BN_CTX_get(ctx)) == NULL) 809 goto err; 810 if ((n = BN_CTX_get(ctx)) == NULL) 811 goto err; 812 813 if ((mont = BN_MONT_CTX_new()) == NULL) 814 goto err; 815 816 BN_zero(n); 817 if (BN_MONT_CTX_set(mont, n, ctx)) { 818 fprintf(stderr, "BN_MONT_CTX_set succeeded for zero modulus!\n"); 819 goto err; 820 } 821 ERR_clear_error(); 822 823 CHECK_GOTO(BN_set_word(n, 16)); 824 if (BN_MONT_CTX_set(mont, n, ctx)) { 825 fprintf(stderr, "BN_MONT_CTX_set succeeded for even modulus!\n"); 826 goto err; 827 } 828 ERR_clear_error(); 829 830 CHECK_GOTO(BN_bntest_rand(a, 100, 0, 0)); 831 CHECK_GOTO(BN_bntest_rand(b, 100, 0, 0)); 832 for (i = 0; i < num2; i++) { 833 int bits = (200 * (i + 1)) / num2; 834 835 if (bits == 0) 836 continue; 837 CHECK_GOTO(BN_bntest_rand(n, bits, 0, 1)); 838 CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx)); 839 840 CHECK_GOTO(BN_nnmod(a, a, n, ctx)); 841 CHECK_GOTO(BN_nnmod(b, b, n, ctx)); 842 843 CHECK_GOTO(BN_to_montgomery(A, a, mont, ctx)); 844 CHECK_GOTO(BN_to_montgomery(B, b, mont, ctx)); 845 846 CHECK_GOTO(BN_mod_mul_montgomery(c, A, B, mont, ctx)); 847 CHECK_GOTO(BN_from_montgomery(A, c, mont, ctx)); 848 if (bp != NULL) { 849 if (!results) { 850 CHECK_GOTO(BN_print(bp, a)); 851 BIO_puts(bp, " * "); 852 CHECK_GOTO(BN_print(bp, b)); 853 BIO_puts(bp, " % "); 854 /* n == &mont->N */ 855 CHECK_GOTO(BN_print(bp, n)); 856 BIO_puts(bp, " - "); 857 } 858 CHECK_GOTO(BN_print(bp, A)); 859 BIO_puts(bp, "\n"); 860 } 861 CHECK_GOTO(BN_mod_mul(d, a, b, n, ctx)); 862 CHECK_GOTO(BN_sub(d, d, A)); 863 if (!BN_is_zero(d)) { 864 fprintf(stderr, "Montgomery multiplication test failed!\n"); 865 goto err; 866 } 867 } 868 869 ret = 1; 870 err: 871 BN_CTX_end(ctx); 872 BN_MONT_CTX_free(mont); 873 874 return ret; 875 } 876 877 int 878 test_mod(BIO *bp, BN_CTX *ctx) 879 { 880 BIGNUM *a, *b, *c, *d, *e; 881 int i; 882 int ret = 0; 883 884 BN_CTX_start(ctx); 885 886 if ((a = BN_CTX_get(ctx)) == NULL) 887 goto err; 888 if ((b = BN_CTX_get(ctx)) == NULL) 889 goto err; 890 if ((c = BN_CTX_get(ctx)) == NULL) 891 goto err; 892 if ((d = BN_CTX_get(ctx)) == NULL) 893 goto err; 894 if ((e = BN_CTX_get(ctx)) == NULL) 895 goto err; 896 897 CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0)); 898 for (i = 0; i < num0; i++) { 899 CHECK_GOTO(BN_bntest_rand(b, 450 + i * 10, 0, 0)); 900 BN_set_negative(a, rand_neg()); 901 BN_set_negative(b, rand_neg()); 902 CHECK_GOTO(BN_mod(c, a, b, ctx)); 903 if (bp != NULL) { 904 if (!results) { 905 CHECK_GOTO(BN_print(bp, a)); 906 BIO_puts(bp, " % "); 907 CHECK_GOTO(BN_print(bp, b)); 908 BIO_puts(bp, " - "); 909 } 910 CHECK_GOTO(BN_print(bp, c)); 911 BIO_puts(bp, "\n"); 912 } 913 CHECK_GOTO(BN_div(d, e, a, b, ctx)); 914 CHECK_GOTO(BN_sub(e, e, c)); 915 if (!BN_is_zero(e)) { 916 fprintf(stderr, "Modulo test failed!\n"); 917 goto err; 918 } 919 } 920 921 ret = 1; 922 err: 923 BN_CTX_end(ctx); 924 925 return ret; 926 } 927 928 int 929 test_mod_mul(BIO *bp, BN_CTX *ctx) 930 { 931 BIGNUM *a, *b, *c, *d, *e; 932 int i, j; 933 int ret = 0; 934 935 BN_CTX_start(ctx); 936 937 if ((a = BN_CTX_get(ctx)) == NULL) 938 goto err; 939 if ((b = BN_CTX_get(ctx)) == NULL) 940 goto err; 941 if ((c = BN_CTX_get(ctx)) == NULL) 942 goto err; 943 if ((d = BN_CTX_get(ctx)) == NULL) 944 goto err; 945 if ((e = BN_CTX_get(ctx)) == NULL) 946 goto err; 947 948 CHECK_GOTO(BN_one(a)); 949 CHECK_GOTO(BN_one(b)); 950 BN_zero(c); 951 if (BN_mod_mul(e, a, b, c, ctx)) { 952 fprintf(stderr, "BN_mod_mul with zero modulus succeeded!\n"); 953 goto err; 954 } 955 ERR_clear_error(); 956 957 for (j = 0; j < 3; j++) { 958 CHECK_GOTO(BN_bntest_rand(c, 1024, 0, 0)); 959 for (i = 0; i < num0; i++) { 960 CHECK_GOTO(BN_bntest_rand(a, 475 + i * 10, 0, 0)); 961 CHECK_GOTO(BN_bntest_rand(b, 425 + i * 11, 0, 0)); 962 BN_set_negative(a, rand_neg()); 963 BN_set_negative(b, rand_neg()); 964 if (!BN_mod_mul(e, a, b, c, ctx)) { 965 unsigned long l; 966 967 while ((l = ERR_get_error())) 968 fprintf(stderr, "ERROR:%s\n", 969 ERR_error_string(l, NULL)); 970 exit(1); 971 } 972 if (bp != NULL) { 973 if (!results) { 974 CHECK_GOTO(BN_print(bp, a)); 975 BIO_puts(bp, " * "); 976 CHECK_GOTO(BN_print(bp, b)); 977 BIO_puts(bp, " % "); 978 CHECK_GOTO(BN_print(bp, c)); 979 if ((BN_is_negative(a) ^ BN_is_negative(b)) && 980 !BN_is_zero(e)) { 981 /* If (a*b) % c is negative, c must be added 982 * in order to obtain the normalized remainder 983 * (new with OpenSSL 0.9.7, previous versions of 984 * BN_mod_mul could generate negative results) 985 */ 986 BIO_puts(bp, " + "); 987 CHECK_GOTO(BN_print(bp, c)); 988 } 989 BIO_puts(bp, " - "); 990 } 991 CHECK_GOTO(BN_print(bp, e)); 992 BIO_puts(bp, "\n"); 993 } 994 CHECK_GOTO(BN_mul(d, a, b, ctx)); 995 CHECK_GOTO(BN_sub(d, d, e)); 996 CHECK_GOTO(BN_div(a, b, d, c, ctx)); 997 if (!BN_is_zero(b)) { 998 fprintf(stderr, "Modulo multiply test failed!\n"); 999 ERR_print_errors_fp(stderr); 1000 goto err; 1001 } 1002 } 1003 } 1004 1005 ret = 1; 1006 err: 1007 BN_CTX_end(ctx); 1008 1009 return ret; 1010 } 1011 1012 int 1013 test_mod_exp(BIO *bp, BN_CTX *ctx) 1014 { 1015 BIGNUM *a, *b, *c, *d, *e; 1016 int i; 1017 int ret = 0; 1018 1019 BN_CTX_start(ctx); 1020 1021 if ((a = BN_CTX_get(ctx)) == NULL) 1022 goto err; 1023 if ((b = BN_CTX_get(ctx)) == NULL) 1024 goto err; 1025 if ((c = BN_CTX_get(ctx)) == NULL) 1026 goto err; 1027 if ((d = BN_CTX_get(ctx)) == NULL) 1028 goto err; 1029 if ((e = BN_CTX_get(ctx)) == NULL) 1030 goto err; 1031 1032 CHECK_GOTO(BN_one(a)); 1033 CHECK_GOTO(BN_one(b)); 1034 BN_zero(c); 1035 if (BN_mod_exp(d, a, b, c, ctx)) { 1036 fprintf(stderr, "BN_mod_exp with zero modulus succeeded!\n"); 1037 goto err; 1038 } 1039 ERR_clear_error(); 1040 if (BN_mod_exp_ct(d, a, b, c, ctx)) { 1041 fprintf(stderr, "BN_mod_exp_ct with zero modulus succeeded!\n"); 1042 goto err; 1043 } 1044 ERR_clear_error(); 1045 if (BN_mod_exp_nonct(d, a, b, c, ctx)) { 1046 fprintf(stderr, "BN_mod_exp_nonct with zero modulus succeeded!\n"); 1047 goto err; 1048 } 1049 ERR_clear_error(); 1050 1051 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */ 1052 for (i = 0; i < num2; i++) { 1053 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0)); 1054 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0)); 1055 1056 if (!BN_mod_exp(d, a, b, c, ctx)) 1057 goto err; 1058 1059 if (bp != NULL) { 1060 if (!results) { 1061 CHECK_GOTO(BN_print(bp, a)); 1062 BIO_puts(bp, " ^ "); 1063 CHECK_GOTO(BN_print(bp, b)); 1064 BIO_puts(bp, " % "); 1065 CHECK_GOTO(BN_print(bp, c)); 1066 BIO_puts(bp, " - "); 1067 } 1068 CHECK_GOTO(BN_print(bp, d)); 1069 BIO_puts(bp, "\n"); 1070 } 1071 CHECK_GOTO(BN_exp(e, a, b, ctx)); 1072 CHECK_GOTO(BN_sub(e, e, d)); 1073 CHECK_GOTO(BN_div(a, b, e, c, ctx)); 1074 if (!BN_is_zero(b)) { 1075 fprintf(stderr, "Modulo exponentiation test failed!\n"); 1076 goto err; 1077 } 1078 } 1079 1080 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */ 1081 for (i = 0; i < num2; i++) { 1082 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0)); 1083 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0)); 1084 1085 if (!BN_mod_exp_ct(d, a, b, c, ctx)) 1086 goto err; 1087 1088 if (bp != NULL) { 1089 if (!results) { 1090 CHECK_GOTO(BN_print(bp, a)); 1091 BIO_puts(bp, " ^ "); 1092 CHECK_GOTO(BN_print(bp, b)); 1093 BIO_puts(bp, " % "); 1094 CHECK_GOTO(BN_print(bp, c)); 1095 BIO_puts(bp, " - "); 1096 } 1097 CHECK_GOTO(BN_print(bp, d)); 1098 BIO_puts(bp, "\n"); 1099 } 1100 CHECK_GOTO(BN_exp(e, a, b, ctx)); 1101 CHECK_GOTO(BN_sub(e, e, d)); 1102 CHECK_GOTO(BN_div(a, b, e, c, ctx)); 1103 if (!BN_is_zero(b)) { 1104 fprintf(stderr, "Modulo exponentiation test failed!\n"); 1105 goto err; 1106 } 1107 } 1108 1109 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */ 1110 for (i = 0; i < num2; i++) { 1111 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0)); 1112 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0)); 1113 1114 if (!BN_mod_exp_nonct(d, a, b, c, ctx)) 1115 goto err; 1116 1117 if (bp != NULL) { 1118 if (!results) { 1119 CHECK_GOTO(BN_print(bp, a)); 1120 BIO_puts(bp, " ^ "); 1121 CHECK_GOTO(BN_print(bp, b)); 1122 BIO_puts(bp, " % "); 1123 CHECK_GOTO(BN_print(bp, c)); 1124 BIO_puts(bp, " - "); 1125 } 1126 CHECK_GOTO(BN_print(bp, d)); 1127 BIO_puts(bp, "\n"); 1128 } 1129 CHECK_GOTO(BN_exp(e, a, b, ctx)); 1130 CHECK_GOTO(BN_sub(e, e, d)); 1131 CHECK_GOTO(BN_div(a, b, e, c, ctx)); 1132 if (!BN_is_zero(b)) { 1133 fprintf(stderr, "Modulo exponentiation test failed!\n"); 1134 goto err; 1135 } 1136 } 1137 1138 ret = 1; 1139 err: 1140 BN_CTX_end(ctx); 1141 1142 return ret; 1143 } 1144 1145 int 1146 test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx) 1147 { 1148 BIGNUM *a, *b, *c, *d, *e; 1149 int i; 1150 int ret = 0; 1151 1152 BN_CTX_start(ctx); 1153 1154 if ((a = BN_CTX_get(ctx)) == NULL) 1155 goto err; 1156 if ((b = BN_CTX_get(ctx)) == NULL) 1157 goto err; 1158 if ((c = BN_CTX_get(ctx)) == NULL) 1159 goto err; 1160 if ((d = BN_CTX_get(ctx)) == NULL) 1161 goto err; 1162 if ((e = BN_CTX_get(ctx)) == NULL) 1163 goto err; 1164 1165 CHECK_GOTO(BN_one(a)); 1166 CHECK_GOTO(BN_one(b)); 1167 BN_zero(c); 1168 if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) { 1169 fprintf(stderr, "BN_mod_exp_mont_consttime with zero modulus " 1170 "succeeded\n"); 1171 goto err; 1172 } 1173 ERR_clear_error(); 1174 1175 CHECK_GOTO(BN_set_word(c, 16)); 1176 if (BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) { 1177 fprintf(stderr, "BN_mod_exp_mont_consttime with even modulus " 1178 "succeeded\n"); 1179 goto err; 1180 } 1181 ERR_clear_error(); 1182 1183 CHECK_GOTO(BN_bntest_rand(c, 30, 0, 1)); /* must be odd for montgomery */ 1184 for (i = 0; i < num2; i++) { 1185 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0)); 1186 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0)); 1187 1188 if (!BN_mod_exp_mont_consttime(d, a, b, c, ctx, NULL)) 1189 goto err; 1190 1191 if (bp != NULL) { 1192 if (!results) { 1193 CHECK_GOTO(BN_print(bp, a)); 1194 BIO_puts(bp, " ^ "); 1195 CHECK_GOTO(BN_print(bp, b)); 1196 BIO_puts(bp, " % "); 1197 CHECK_GOTO(BN_print(bp, c)); 1198 BIO_puts(bp, " - "); 1199 } 1200 CHECK_GOTO(BN_print(bp, d)); 1201 BIO_puts(bp, "\n"); 1202 } 1203 CHECK_GOTO(BN_exp(e, a, b, ctx)); 1204 CHECK_GOTO(BN_sub(e, e, d)); 1205 CHECK_GOTO(BN_div(a, b, e, c, ctx)); 1206 if (!BN_is_zero(b)) { 1207 fprintf(stderr, "Modulo exponentiation test failed!\n"); 1208 goto err; 1209 } 1210 } 1211 1212 ret = 1; 1213 err: 1214 BN_CTX_end(ctx); 1215 1216 return ret; 1217 } 1218 1219 /* 1220 * Test constant-time modular exponentiation with 1024-bit inputs, which on 1221 * x86_64 cause a different code branch to be taken. 1222 */ 1223 int 1224 test_mod_exp_mont5(BIO *bp, BN_CTX *ctx) 1225 { 1226 BIGNUM *a, *p, *m, *d, *e; 1227 BIGNUM *b, *n, *c; 1228 BN_MONT_CTX *mont = NULL; 1229 int len; 1230 int ret = 0; 1231 1232 BN_CTX_start(ctx); 1233 1234 if ((a = BN_CTX_get(ctx)) == NULL) 1235 goto err; 1236 if ((p = BN_CTX_get(ctx)) == NULL) 1237 goto err; 1238 if ((m = BN_CTX_get(ctx)) == NULL) 1239 goto err; 1240 if ((d = BN_CTX_get(ctx)) == NULL) 1241 goto err; 1242 if ((e = BN_CTX_get(ctx)) == NULL) 1243 goto err; 1244 if ((b = BN_CTX_get(ctx)) == NULL) 1245 goto err; 1246 if ((n = BN_CTX_get(ctx)) == NULL) 1247 goto err; 1248 if ((c = BN_CTX_get(ctx)) == NULL) 1249 goto err; 1250 1251 CHECK_GOTO(mont = BN_MONT_CTX_new()); 1252 1253 CHECK_GOTO(BN_bntest_rand(m, 1024, 0, 1)); /* must be odd for montgomery */ 1254 /* Zero exponent */ 1255 CHECK_GOTO(BN_bntest_rand(a, 1024, 0, 0)); 1256 BN_zero(p); 1257 if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)) 1258 goto err; 1259 if (!BN_is_one(d)) { 1260 fprintf(stderr, "Modular exponentiation test failed!\n"); 1261 goto err; 1262 } 1263 /* Regression test for carry bug in mulx4x_mont */ 1264 len = BN_hex2bn(&a, 1265 "7878787878787878787878787878787878787878787878787878787878787878" 1266 "7878787878787878787878787878787878787878787878787878787878787878" 1267 "7878787878787878787878787878787878787878787878787878787878787878" 1268 "7878787878787878787878787878787878787878787878787878787878787878"); 1269 CHECK_GOTO(len); 1270 len = BN_hex2bn(&b, 1271 "095D72C08C097BA488C5E439C655A192EAFB6380073D8C2664668EDDB4060744" 1272 "E16E57FB4EDB9AE10A0CEFCDC28A894F689A128379DB279D48A2E20849D68593" 1273 "9B7803BCF46CEBF5C533FB0DD35B080593DE5472E3FE5DB951B8BFF9B4CB8F03" 1274 "9CC638A5EE8CDD703719F8000E6A9F63BEED5F2FCD52FF293EA05A251BB4AB81"); 1275 CHECK_GOTO(len); 1276 len = BN_hex2bn(&n, 1277 "D78AF684E71DB0C39CFF4E64FB9DB567132CB9C50CC98009FEB820B26F2DED9B" 1278 "91B9B5E2B83AE0AE4EB4E0523CA726BFBE969B89FD754F674CE99118C3F2D1C5" 1279 "D81FDC7C54E02B60262B241D53C040E99E45826ECA37A804668E690E1AFC1CA4" 1280 "2C9A15D84D4954425F0B7642FC0BD9D7B24E2618D2DCC9B729D944BADACFDDAF"); 1281 CHECK_GOTO(len); 1282 CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx)); 1283 CHECK_GOTO(BN_mod_mul_montgomery(c, a, b, mont, ctx)); 1284 CHECK_GOTO(BN_mod_mul_montgomery(d, b, a, mont, ctx)); 1285 if (BN_cmp(c, d)) { 1286 fprintf(stderr, "Montgomery multiplication test failed:" 1287 " a*b != b*a.\n"); 1288 goto err; 1289 } 1290 /* Regression test for carry bug in sqr[x]8x_mont */ 1291 len = BN_hex2bn(&n, 1292 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 1293 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 1294 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 1295 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 1296 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 1297 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 1298 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 1299 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF00" 1300 "0000000000000000000000000000000000000000000000000000000000000000" 1301 "0000000000000000000000000000000000000000000000000000000000000000" 1302 "0000000000000000000000000000000000000000000000000000000000000000" 1303 "0000000000000000000000000000000000000000000000000000000000000000" 1304 "0000000000000000000000000000000000000000000000000000000000000000" 1305 "0000000000000000000000000000000000000000000000000000000000000000" 1306 "0000000000000000000000000000000000000000000000000000000000000000" 1307 "00000000000000000000000000000000000000000000000000FFFFFFFFFFFFFF"); 1308 CHECK_GOTO(len); 1309 len = BN_hex2bn(&a, 1310 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 1311 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 1312 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 1313 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 1314 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 1315 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 1316 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 1317 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF0000000000" 1318 "0000000000000000000000000000000000000000000000000000000000000000" 1319 "0000000000000000000000000000000000000000000000000000000000000000" 1320 "0000000000000000000000000000000000000000000000000000000000000000" 1321 "0000000000000000000000000000000000000000000000000000000000000000" 1322 "0000000000000000000000000000000000000000000000000000000000000000" 1323 "0000000000000000000000000000000000000000000000000000000000000000" 1324 "0000000000000000000000000000000000000000000000000000000000000000" 1325 "000000000000000000000000000000000000000000FFFFFFFFFFFFFF00000000"); 1326 CHECK_GOTO(len); 1327 CHECK_GOTO(bn_copy(b, a)); 1328 CHECK_GOTO(BN_MONT_CTX_set(mont, n, ctx)); 1329 CHECK_GOTO(BN_mod_mul_montgomery(c, a, a, mont, ctx)); 1330 CHECK_GOTO(BN_mod_mul_montgomery(d, a, b, mont, ctx)); 1331 if (BN_cmp(c, d)) { 1332 fprintf(stderr, "Montgomery multiplication test failed:" 1333 " a**2 != a*a.\n"); 1334 goto err; 1335 } 1336 /* Zero input */ 1337 CHECK_GOTO(BN_bntest_rand(p, 1024, 0, 0)); 1338 BN_zero(a); 1339 if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)) 1340 goto err; 1341 if (!BN_is_zero(d)) { 1342 fprintf(stderr, "Modular exponentiation test failed!\n"); 1343 goto err; 1344 } 1345 /* 1346 * Craft an input whose Montgomery representation is 1, i.e., shorter 1347 * than the modulus m, in order to test the const time precomputation 1348 * scattering/gathering. 1349 */ 1350 CHECK_GOTO(BN_one(a)); 1351 CHECK_GOTO(BN_MONT_CTX_set(mont, m, ctx)); 1352 if (!BN_from_montgomery(e, a, mont, ctx)) 1353 goto err; 1354 if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL)) 1355 goto err; 1356 if (!BN_mod_exp_simple(a, e, p, m, ctx)) 1357 goto err; 1358 if (BN_cmp(a, d) != 0) { 1359 fprintf(stderr, "Modular exponentiation test failed!\n"); 1360 goto err; 1361 } 1362 /* Finally, some regular test vectors. */ 1363 CHECK_GOTO(BN_bntest_rand(e, 1024, 0, 0)); 1364 if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL)) 1365 goto err; 1366 if (!BN_mod_exp_simple(a, e, p, m, ctx)) 1367 goto err; 1368 if (BN_cmp(a, d) != 0) { 1369 fprintf(stderr, "Modular exponentiation test failed!\n"); 1370 goto err; 1371 } 1372 1373 ret = 1; 1374 err: 1375 BN_CTX_end(ctx); 1376 BN_MONT_CTX_free(mont); 1377 1378 return ret; 1379 } 1380 1381 int 1382 test_exp(BIO *bp, BN_CTX *ctx) 1383 { 1384 BIGNUM *a, *b, *d, *e; 1385 int i; 1386 int ret = 0; 1387 1388 BN_CTX_start(ctx); 1389 1390 if ((a = BN_CTX_get(ctx)) == NULL) 1391 goto err; 1392 if ((b = BN_CTX_get(ctx)) == NULL) 1393 goto err; 1394 if ((d = BN_CTX_get(ctx)) == NULL) 1395 goto err; 1396 if ((e = BN_CTX_get(ctx)) == NULL) 1397 goto err; 1398 1399 for (i = 0; i < num2; i++) { 1400 CHECK_GOTO(BN_bntest_rand(a, 20 + i * 5, 0, 0)); 1401 CHECK_GOTO(BN_bntest_rand(b, 2 + i, 0, 0)); 1402 1403 if (BN_exp(d, a, b, ctx) <= 0) 1404 goto err; 1405 1406 if (bp != NULL) { 1407 if (!results) { 1408 CHECK_GOTO(BN_print(bp, a)); 1409 BIO_puts(bp, " ^ "); 1410 CHECK_GOTO(BN_print(bp, b)); 1411 BIO_puts(bp, " - "); 1412 } 1413 CHECK_GOTO(BN_print(bp, d)); 1414 BIO_puts(bp, "\n"); 1415 } 1416 CHECK_GOTO(BN_one(e)); 1417 for (; !BN_is_zero(b); BN_sub_word(b, 1)) 1418 CHECK_GOTO(BN_mul(e, e, a, ctx)); 1419 CHECK_GOTO(BN_sub(e, e, d)); 1420 if (!BN_is_zero(e)) { 1421 fprintf(stderr, "Exponentiation test failed!\n"); 1422 goto err; 1423 } 1424 } 1425 1426 ret = 1; 1427 err: 1428 BN_CTX_end(ctx); 1429 1430 return ret; 1431 } 1432 1433 static int 1434 genprime_cb(int p, int n, BN_GENCB *arg) 1435 { 1436 char c = '*'; 1437 1438 if (p == 0) 1439 c = '.'; 1440 if (p == 1) 1441 c = '+'; 1442 if (p == 2) 1443 c = '*'; 1444 if (p == 3) 1445 c = '\n'; 1446 putc(c, stderr); 1447 return 1; 1448 } 1449 1450 int 1451 test_kron(BIO *bp, BN_CTX *ctx) 1452 { 1453 BIGNUM *a, *b, *r, *t; 1454 BN_GENCB *cb = NULL; 1455 int i; 1456 int legendre, kronecker; 1457 int ret = 0; 1458 1459 BN_CTX_start(ctx); 1460 1461 if ((a = BN_CTX_get(ctx)) == NULL) 1462 goto err; 1463 if ((b = BN_CTX_get(ctx)) == NULL) 1464 goto err; 1465 if ((r = BN_CTX_get(ctx)) == NULL) 1466 goto err; 1467 if ((t = BN_CTX_get(ctx)) == NULL) 1468 goto err; 1469 1470 if ((cb = BN_GENCB_new()) == NULL) 1471 goto err; 1472 1473 BN_GENCB_set(cb, genprime_cb, NULL); 1474 1475 /* 1476 * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In 1477 * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is 1478 * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we 1479 * generate a random prime b and compare these values for a number of 1480 * random a's. (That is, we run the Solovay-Strassen primality test to 1481 * confirm that b is prime, except that we don't want to test whether b 1482 * is prime but whether BN_kronecker works.) 1483 */ 1484 1485 if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, cb)) 1486 goto err; 1487 BN_set_negative(b, rand_neg()); 1488 putc('\n', stderr); 1489 1490 for (i = 0; i < num0; i++) { 1491 if (!BN_bntest_rand(a, 512, 0, 0)) 1492 goto err; 1493 BN_set_negative(a, rand_neg()); 1494 1495 /* t := (|b|-1)/2 (note that b is odd) */ 1496 if (!bn_copy(t, b)) 1497 goto err; 1498 BN_set_negative(t, 0); 1499 if (!BN_sub_word(t, 1)) 1500 goto err; 1501 if (!BN_rshift1(t, t)) 1502 goto err; 1503 /* r := a^t mod b */ 1504 BN_set_negative(b, 0); 1505 1506 if (!BN_mod_exp_recp(r, a, t, b, ctx)) 1507 goto err; 1508 BN_set_negative(b, 1); 1509 1510 if (BN_is_word(r, 1)) 1511 legendre = 1; 1512 else if (BN_is_zero(r)) 1513 legendre = 0; 1514 else { 1515 if (!BN_add_word(r, 1)) 1516 goto err; 1517 if (0 != BN_ucmp(r, b)) { 1518 fprintf(stderr, "Legendre symbol computation failed\n"); 1519 goto err; 1520 } 1521 legendre = -1; 1522 } 1523 1524 kronecker = BN_kronecker(a, b, ctx); 1525 if (kronecker < -1) 1526 goto err; 1527 /* we actually need BN_kronecker(a, |b|) */ 1528 if (BN_is_negative(a) && BN_is_negative(b)) 1529 kronecker = -kronecker; 1530 1531 if (legendre != kronecker) { 1532 fprintf(stderr, "legendre != kronecker; a = "); 1533 CHECK_GOTO(BN_print_fp(stderr, a)); 1534 fprintf(stderr, ", b = "); 1535 CHECK_GOTO(BN_print_fp(stderr, b)); 1536 fprintf(stderr, "\n"); 1537 goto err; 1538 } 1539 1540 putc('.', stderr); 1541 } 1542 1543 putc('\n', stderr); 1544 1545 ret = 1; 1546 err: 1547 BN_GENCB_free(cb); 1548 BN_CTX_end(ctx); 1549 1550 return ret; 1551 } 1552 1553 int 1554 test_sqrt(BIO *bp, BN_CTX *ctx) 1555 { 1556 BIGNUM *a, *p, *r; 1557 BN_GENCB *cb = NULL; 1558 int i, j; 1559 int ret = 0; 1560 1561 BN_CTX_start(ctx); 1562 1563 if ((a = BN_CTX_get(ctx)) == NULL) 1564 goto err; 1565 if ((p = BN_CTX_get(ctx)) == NULL) 1566 goto err; 1567 if ((r = BN_CTX_get(ctx)) == NULL) 1568 goto err; 1569 1570 if ((cb = BN_GENCB_new()) == NULL) 1571 goto err; 1572 1573 BN_GENCB_set(cb, genprime_cb, NULL); 1574 1575 for (i = 0; i < 16; i++) { 1576 if (i < 8) { 1577 unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 }; 1578 1579 if (!BN_set_word(p, primes[i])) 1580 goto err; 1581 } else { 1582 if (!BN_set_word(a, 32)) 1583 goto err; 1584 if (!BN_set_word(r, 2 * i + 1)) 1585 goto err; 1586 1587 if (!BN_generate_prime_ex(p, 256, 0, a, r, cb)) 1588 goto err; 1589 putc('\n', stderr); 1590 } 1591 BN_set_negative(p, rand_neg()); 1592 1593 for (j = 0; j < num2; j++) { 1594 /* 1595 * construct 'a' such that it is a square modulo p, but in 1596 * general not a proper square and not reduced modulo p 1597 */ 1598 if (!BN_bntest_rand(r, 256, 0, 3)) 1599 goto err; 1600 if (!BN_nnmod(r, r, p, ctx)) 1601 goto err; 1602 if (!BN_mod_sqr(r, r, p, ctx)) 1603 goto err; 1604 if (!BN_bntest_rand(a, 256, 0, 3)) 1605 goto err; 1606 if (!BN_nnmod(a, a, p, ctx)) 1607 goto err; 1608 if (!BN_mod_sqr(a, a, p, ctx)) 1609 goto err; 1610 if (!BN_mul(a, a, r, ctx)) 1611 goto err; 1612 if (rand_neg()) 1613 if (!BN_sub(a, a, p)) 1614 goto err; 1615 1616 if (!BN_mod_sqrt(r, a, p, ctx)) 1617 goto err; 1618 if (!BN_mod_sqr(r, r, p, ctx)) 1619 goto err; 1620 1621 if (!BN_nnmod(a, a, p, ctx)) 1622 goto err; 1623 1624 if (BN_cmp(a, r) != 0) { 1625 fprintf(stderr, "BN_mod_sqrt failed: a = "); 1626 CHECK_GOTO(BN_print_fp(stderr, a)); 1627 fprintf(stderr, ", r = "); 1628 CHECK_GOTO(BN_print_fp(stderr, r)); 1629 fprintf(stderr, ", p = "); 1630 CHECK_GOTO(BN_print_fp(stderr, p)); 1631 fprintf(stderr, "\n"); 1632 goto err; 1633 } 1634 1635 putc('.', stderr); 1636 } 1637 1638 putc('\n', stderr); 1639 } 1640 1641 ret = 1; 1642 err: 1643 BN_GENCB_free(cb); 1644 BN_CTX_end(ctx); 1645 1646 return ret; 1647 } 1648 1649 int 1650 test_lshift(BIO *bp, BN_CTX *ctx, int use_lst) 1651 { 1652 BIGNUM *a, *b, *c, *d; 1653 int i; 1654 int ret = 0; 1655 1656 BN_CTX_start(ctx); 1657 1658 if ((a = BN_CTX_get(ctx)) == NULL) 1659 goto err; 1660 if ((b = BN_CTX_get(ctx)) == NULL) 1661 goto err; 1662 if ((c = BN_CTX_get(ctx)) == NULL) 1663 goto err; 1664 if ((d = BN_CTX_get(ctx)) == NULL) 1665 goto err; 1666 CHECK_GOTO(BN_one(c)); 1667 1668 if (use_lst) { 1669 if (!BN_hex2bn(&a, "C64F43042AEACA6E5836805BE8C99B04" 1670 "5D4836C2FD16C964F0")) 1671 goto err; 1672 } else { 1673 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0)); 1674 BN_set_negative(a, rand_neg()); 1675 } 1676 for (i = 0; i < num0; i++) { 1677 CHECK_GOTO(BN_lshift(b, a, i + 1)); 1678 CHECK_GOTO(BN_add(c, c, c)); 1679 if (bp != NULL) { 1680 if (!results) { 1681 CHECK_GOTO(BN_print(bp, a)); 1682 BIO_puts(bp, " * "); 1683 CHECK_GOTO(BN_print(bp, c)); 1684 BIO_puts(bp, " - "); 1685 } 1686 CHECK_GOTO(BN_print(bp, b)); 1687 BIO_puts(bp, "\n"); 1688 } 1689 CHECK_GOTO(BN_mul(d, a, c, ctx)); 1690 CHECK_GOTO(BN_sub(d, d, b)); 1691 if (!BN_is_zero(d)) { 1692 fprintf(stderr, "Left shift test failed!\n"); 1693 fprintf(stderr, "a="); 1694 CHECK_GOTO(BN_print_fp(stderr, a)); 1695 fprintf(stderr, "\nb="); 1696 CHECK_GOTO(BN_print_fp(stderr, b)); 1697 fprintf(stderr, "\nc="); 1698 CHECK_GOTO(BN_print_fp(stderr, c)); 1699 fprintf(stderr, "\nd="); 1700 CHECK_GOTO(BN_print_fp(stderr, d)); 1701 fprintf(stderr, "\n"); 1702 goto err; 1703 } 1704 } 1705 1706 ret = 1; 1707 err: 1708 BN_CTX_end(ctx); 1709 1710 return ret; 1711 } 1712 1713 int 1714 test_lshift1(BIO *bp, BN_CTX *ctx) 1715 { 1716 BIGNUM *a, *b, *c; 1717 int i; 1718 int ret = 0; 1719 1720 BN_CTX_start(ctx); 1721 1722 if ((a = BN_CTX_get(ctx)) == NULL) 1723 goto err; 1724 if ((b = BN_CTX_get(ctx)) == NULL) 1725 goto err; 1726 if ((c = BN_CTX_get(ctx)) == NULL) 1727 goto err; 1728 1729 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0)); 1730 BN_set_negative(a, rand_neg()); 1731 for (i = 0; i < num0; i++) { 1732 CHECK_GOTO(BN_lshift1(b, a)); 1733 if (bp != NULL) { 1734 if (!results) { 1735 CHECK_GOTO(BN_print(bp, a)); 1736 BIO_puts(bp, " * 2"); 1737 BIO_puts(bp, " - "); 1738 } 1739 CHECK_GOTO(BN_print(bp, b)); 1740 BIO_puts(bp, "\n"); 1741 } 1742 CHECK_GOTO(BN_add(c, a, a)); 1743 CHECK_GOTO(BN_sub(a, b, c)); 1744 if (!BN_is_zero(a)) { 1745 fprintf(stderr, "Left shift one test failed!\n"); 1746 goto err; 1747 } 1748 1749 CHECK_GOTO(bn_copy(a, b)); 1750 } 1751 1752 ret = 1; 1753 err: 1754 BN_CTX_end(ctx); 1755 1756 return ret; 1757 } 1758 1759 int 1760 test_rshift(BIO *bp, BN_CTX *ctx) 1761 { 1762 BIGNUM *a, *b, *c, *d, *e; 1763 int i; 1764 int ret = 0; 1765 1766 BN_CTX_start(ctx); 1767 1768 if ((a = BN_CTX_get(ctx)) == NULL) 1769 goto err; 1770 if ((b = BN_CTX_get(ctx)) == NULL) 1771 goto err; 1772 if ((c = BN_CTX_get(ctx)) == NULL) 1773 goto err; 1774 if ((d = BN_CTX_get(ctx)) == NULL) 1775 goto err; 1776 if ((e = BN_CTX_get(ctx)) == NULL) 1777 goto err; 1778 CHECK_GOTO(BN_one(c)); 1779 1780 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0)); 1781 BN_set_negative(a, rand_neg()); 1782 for (i = 0; i < num0; i++) { 1783 CHECK_GOTO(BN_rshift(b, a, i + 1)); 1784 CHECK_GOTO(BN_add(c, c, c)); 1785 if (bp != NULL) { 1786 if (!results) { 1787 CHECK_GOTO(BN_print(bp, a)); 1788 BIO_puts(bp, " / "); 1789 CHECK_GOTO(BN_print(bp, c)); 1790 BIO_puts(bp, " - "); 1791 } 1792 CHECK_GOTO(BN_print(bp, b)); 1793 BIO_puts(bp, "\n"); 1794 } 1795 CHECK_GOTO(BN_div(d, e, a, c, ctx)); 1796 CHECK_GOTO(BN_sub(d, d, b)); 1797 if (!BN_is_zero(d)) { 1798 fprintf(stderr, "Right shift test failed!\n"); 1799 goto err; 1800 } 1801 } 1802 1803 ret = 1; 1804 err: 1805 BN_CTX_end(ctx); 1806 1807 return ret; 1808 } 1809 1810 int 1811 test_rshift1(BIO *bp, BN_CTX *ctx) 1812 { 1813 BIGNUM *a, *b, *c; 1814 int i; 1815 int ret = 0; 1816 1817 BN_CTX_start(ctx); 1818 1819 if ((a = BN_CTX_get(ctx)) == NULL) 1820 goto err; 1821 if ((b = BN_CTX_get(ctx)) == NULL) 1822 goto err; 1823 if ((c = BN_CTX_get(ctx)) == NULL) 1824 goto err; 1825 1826 CHECK_GOTO(BN_bntest_rand(a, 200, 0, 0)); 1827 BN_set_negative(a, rand_neg()); 1828 for (i = 0; i < num0; i++) { 1829 CHECK_GOTO(BN_rshift1(b, a)); 1830 if (bp != NULL) { 1831 if (!results) { 1832 CHECK_GOTO(BN_print(bp, a)); 1833 BIO_puts(bp, " / 2"); 1834 BIO_puts(bp, " - "); 1835 } 1836 CHECK_GOTO(BN_print(bp, b)); 1837 BIO_puts(bp, "\n"); 1838 } 1839 CHECK_GOTO(BN_sub(c, a, b)); 1840 CHECK_GOTO(BN_sub(c, c, b)); 1841 if (!BN_is_zero(c) && !BN_abs_is_word(c, 1)) { 1842 fprintf(stderr, "Right shift one test failed!\n"); 1843 goto err; 1844 } 1845 CHECK_GOTO(bn_copy(a, b)); 1846 } 1847 1848 ret = 1; 1849 err: 1850 BN_CTX_end(ctx); 1851 1852 return ret; 1853 } 1854 1855 int 1856 rand_neg(void) 1857 { 1858 static unsigned int neg = 0; 1859 static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 }; 1860 1861 return sign[neg++ % 8]; 1862 } 1863 1864 int 1865 test_mod_exp_sizes(BIO *bp, BN_CTX *ctx) 1866 { 1867 BN_MONT_CTX *mont_ctx = NULL; 1868 BIGNUM *p, *x, *y, *r, *r2; 1869 int size; 1870 int ret = 0; 1871 1872 BN_CTX_start(ctx); 1873 CHECK_GOTO(p = BN_CTX_get(ctx)); 1874 CHECK_GOTO(x = BN_CTX_get(ctx)); 1875 CHECK_GOTO(y = BN_CTX_get(ctx)); 1876 CHECK_GOTO(r = BN_CTX_get(ctx)); 1877 CHECK_GOTO(r2 = BN_CTX_get(ctx)); 1878 mont_ctx = BN_MONT_CTX_new(); 1879 1880 if (r2 == NULL || mont_ctx == NULL) 1881 goto err; 1882 1883 if (!BN_generate_prime_ex(p, 32, 0, NULL, NULL, NULL) || 1884 !BN_MONT_CTX_set(mont_ctx, p, ctx)) 1885 goto err; 1886 1887 for (size = 32; size < 1024; size += 8) { 1888 if (!BN_rand(x, size, -1, 0) || 1889 !BN_rand(y, size, -1, 0) || 1890 !BN_mod_exp_mont_consttime(r, x, y, p, ctx, mont_ctx) || 1891 !BN_mod_exp(r2, x, y, p, ctx)) 1892 goto err; 1893 1894 if (BN_cmp(r, r2) != 0) { 1895 char *r_str = NULL; 1896 char *r2_str = NULL; 1897 CHECK_GOTO(r_str = BN_bn2hex(r)); 1898 CHECK_GOTO(r2_str = BN_bn2hex(r2)); 1899 1900 printf("Incorrect answer at size %d: %s vs %s\n", 1901 size, r_str, r2_str); 1902 free(r_str); 1903 free(r2_str); 1904 goto err; 1905 } 1906 } 1907 1908 ret = 1; 1909 err: 1910 BN_CTX_end(ctx); 1911 BN_MONT_CTX_free(mont_ctx); 1912 1913 return ret; 1914 } 1915