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