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