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