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