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