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