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 BN_MONT_CTX *mont; 1046 1047 a = BN_new(); 1048 p = BN_new(); 1049 m = BN_new(); 1050 d = BN_new(); 1051 e = BN_new(); 1052 mont = BN_MONT_CTX_new(); 1053 1054 BN_bntest_rand(m, 1024, 0, 1); /* must be odd for montgomery */ 1055 /* Zero exponent */ 1056 BN_bntest_rand(a, 1024, 0, 0); 1057 BN_zero(p); 1058 if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)) 1059 return 0; 1060 if (!BN_is_one(d)) { 1061 fprintf(stderr, "Modular exponentiation test failed!\n"); 1062 return 0; 1063 } 1064 /* Zero input */ 1065 BN_bntest_rand(p, 1024, 0, 0); 1066 BN_zero(a); 1067 if (!BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)) 1068 return 0; 1069 if (!BN_is_zero(d)) { 1070 fprintf(stderr, "Modular exponentiation test failed!\n"); 1071 return 0; 1072 } 1073 /* 1074 * Craft an input whose Montgomery representation is 1, i.e., shorter 1075 * than the modulus m, in order to test the const time precomputation 1076 * scattering/gathering. 1077 */ 1078 BN_one(a); 1079 BN_MONT_CTX_set(mont, m, ctx); 1080 if (!BN_from_montgomery(e, a, mont, ctx)) 1081 return 0; 1082 if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL)) 1083 return 0; 1084 if (!BN_mod_exp_simple(a, e, p, m, ctx)) 1085 return 0; 1086 if (BN_cmp(a, d) != 0) { 1087 fprintf(stderr, "Modular exponentiation test failed!\n"); 1088 return 0; 1089 } 1090 /* Finally, some regular test vectors. */ 1091 BN_bntest_rand(e, 1024, 0, 0); 1092 if (!BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL)) 1093 return 0; 1094 if (!BN_mod_exp_simple(a, e, p, m, ctx)) 1095 return 0; 1096 if (BN_cmp(a, d) != 0) { 1097 fprintf(stderr, "Modular exponentiation test failed!\n"); 1098 return 0; 1099 } 1100 BN_MONT_CTX_free(mont); 1101 BN_free(a); 1102 BN_free(p); 1103 BN_free(m); 1104 BN_free(d); 1105 BN_free(e); 1106 return (1); 1107} 1108 1109int test_exp(BIO *bp, BN_CTX *ctx) 1110{ 1111 BIGNUM *a, *b, *d, *e, *one; 1112 int i; 1113 1114 a = BN_new(); 1115 b = BN_new(); 1116 d = BN_new(); 1117 e = BN_new(); 1118 one = BN_new(); 1119 BN_one(one); 1120 1121 for (i = 0; i < num2; i++) { 1122 BN_bntest_rand(a, 20 + i * 5, 0, 0); 1123 BN_bntest_rand(b, 2 + i, 0, 0); 1124 1125 if (BN_exp(d, a, b, ctx) <= 0) 1126 return (0); 1127 1128 if (bp != NULL) { 1129 if (!results) { 1130 BN_print(bp, a); 1131 BIO_puts(bp, " ^ "); 1132 BN_print(bp, b); 1133 BIO_puts(bp, " - "); 1134 } 1135 BN_print(bp, d); 1136 BIO_puts(bp, "\n"); 1137 } 1138 BN_one(e); 1139 for (; !BN_is_zero(b); BN_sub(b, b, one)) 1140 BN_mul(e, e, a, ctx); 1141 BN_sub(e, e, d); 1142 if (!BN_is_zero(e)) { 1143 fprintf(stderr, "Exponentiation test failed!\n"); 1144 return 0; 1145 } 1146 } 1147 BN_free(a); 1148 BN_free(b); 1149 BN_free(d); 1150 BN_free(e); 1151 BN_free(one); 1152 return (1); 1153} 1154 1155#ifndef OPENSSL_NO_EC2M 1156int test_gf2m_add(BIO *bp) 1157{ 1158 BIGNUM a, b, c; 1159 int i, ret = 0; 1160 1161 BN_init(&a); 1162 BN_init(&b); 1163 BN_init(&c); 1164 1165 for (i = 0; i < num0; i++) { 1166 BN_rand(&a, 512, 0, 0); 1167 BN_copy(&b, BN_value_one()); 1168 a.neg = rand_neg(); 1169 b.neg = rand_neg(); 1170 BN_GF2m_add(&c, &a, &b); 1171# if 0 /* make test uses ouput in bc but bc can't 1172 * handle GF(2^m) arithmetic */ 1173 if (bp != NULL) { 1174 if (!results) { 1175 BN_print(bp, &a); 1176 BIO_puts(bp, " ^ "); 1177 BN_print(bp, &b); 1178 BIO_puts(bp, " = "); 1179 } 1180 BN_print(bp, &c); 1181 BIO_puts(bp, "\n"); 1182 } 1183# endif 1184 /* Test that two added values have the correct parity. */ 1185 if ((BN_is_odd(&a) && BN_is_odd(&c)) 1186 || (!BN_is_odd(&a) && !BN_is_odd(&c))) { 1187 fprintf(stderr, "GF(2^m) addition test (a) failed!\n"); 1188 goto err; 1189 } 1190 BN_GF2m_add(&c, &c, &c); 1191 /* Test that c + c = 0. */ 1192 if (!BN_is_zero(&c)) { 1193 fprintf(stderr, "GF(2^m) addition test (b) failed!\n"); 1194 goto err; 1195 } 1196 } 1197 ret = 1; 1198 err: 1199 BN_free(&a); 1200 BN_free(&b); 1201 BN_free(&c); 1202 return ret; 1203} 1204 1205int test_gf2m_mod(BIO *bp) 1206{ 1207 BIGNUM *a, *b[2], *c, *d, *e; 1208 int i, j, ret = 0; 1209 int p0[] = { 163, 7, 6, 3, 0, -1 }; 1210 int p1[] = { 193, 15, 0, -1 }; 1211 1212 a = BN_new(); 1213 b[0] = BN_new(); 1214 b[1] = BN_new(); 1215 c = BN_new(); 1216 d = BN_new(); 1217 e = BN_new(); 1218 1219 BN_GF2m_arr2poly(p0, b[0]); 1220 BN_GF2m_arr2poly(p1, b[1]); 1221 1222 for (i = 0; i < num0; i++) { 1223 BN_bntest_rand(a, 1024, 0, 0); 1224 for (j = 0; j < 2; j++) { 1225 BN_GF2m_mod(c, a, b[j]); 1226# if 0 /* make test uses ouput in bc but bc can't 1227 * handle GF(2^m) arithmetic */ 1228 if (bp != NULL) { 1229 if (!results) { 1230 BN_print(bp, a); 1231 BIO_puts(bp, " % "); 1232 BN_print(bp, b[j]); 1233 BIO_puts(bp, " - "); 1234 BN_print(bp, c); 1235 BIO_puts(bp, "\n"); 1236 } 1237 } 1238# endif 1239 BN_GF2m_add(d, a, c); 1240 BN_GF2m_mod(e, d, b[j]); 1241 /* Test that a + (a mod p) mod p == 0. */ 1242 if (!BN_is_zero(e)) { 1243 fprintf(stderr, "GF(2^m) modulo test failed!\n"); 1244 goto err; 1245 } 1246 } 1247 } 1248 ret = 1; 1249 err: 1250 BN_free(a); 1251 BN_free(b[0]); 1252 BN_free(b[1]); 1253 BN_free(c); 1254 BN_free(d); 1255 BN_free(e); 1256 return ret; 1257} 1258 1259int test_gf2m_mod_mul(BIO *bp, BN_CTX *ctx) 1260{ 1261 BIGNUM *a, *b[2], *c, *d, *e, *f, *g, *h; 1262 int i, j, ret = 0; 1263 int p0[] = { 163, 7, 6, 3, 0, -1 }; 1264 int p1[] = { 193, 15, 0, -1 }; 1265 1266 a = BN_new(); 1267 b[0] = BN_new(); 1268 b[1] = BN_new(); 1269 c = BN_new(); 1270 d = BN_new(); 1271 e = BN_new(); 1272 f = BN_new(); 1273 g = BN_new(); 1274 h = BN_new(); 1275 1276 BN_GF2m_arr2poly(p0, b[0]); 1277 BN_GF2m_arr2poly(p1, b[1]); 1278 1279 for (i = 0; i < num0; i++) { 1280 BN_bntest_rand(a, 1024, 0, 0); 1281 BN_bntest_rand(c, 1024, 0, 0); 1282 BN_bntest_rand(d, 1024, 0, 0); 1283 for (j = 0; j < 2; j++) { 1284 BN_GF2m_mod_mul(e, a, c, b[j], ctx); 1285# if 0 /* make test uses ouput in bc but bc can't 1286 * handle GF(2^m) arithmetic */ 1287 if (bp != NULL) { 1288 if (!results) { 1289 BN_print(bp, a); 1290 BIO_puts(bp, " * "); 1291 BN_print(bp, c); 1292 BIO_puts(bp, " % "); 1293 BN_print(bp, b[j]); 1294 BIO_puts(bp, " - "); 1295 BN_print(bp, e); 1296 BIO_puts(bp, "\n"); 1297 } 1298 } 1299# endif 1300 BN_GF2m_add(f, a, d); 1301 BN_GF2m_mod_mul(g, f, c, b[j], ctx); 1302 BN_GF2m_mod_mul(h, d, c, b[j], ctx); 1303 BN_GF2m_add(f, e, g); 1304 BN_GF2m_add(f, f, h); 1305 /* Test that (a+d)*c = a*c + d*c. */ 1306 if (!BN_is_zero(f)) { 1307 fprintf(stderr, 1308 "GF(2^m) modular multiplication test failed!\n"); 1309 goto err; 1310 } 1311 } 1312 } 1313 ret = 1; 1314 err: 1315 BN_free(a); 1316 BN_free(b[0]); 1317 BN_free(b[1]); 1318 BN_free(c); 1319 BN_free(d); 1320 BN_free(e); 1321 BN_free(f); 1322 BN_free(g); 1323 BN_free(h); 1324 return ret; 1325} 1326 1327int test_gf2m_mod_sqr(BIO *bp, BN_CTX *ctx) 1328{ 1329 BIGNUM *a, *b[2], *c, *d; 1330 int i, j, ret = 0; 1331 int p0[] = { 163, 7, 6, 3, 0, -1 }; 1332 int p1[] = { 193, 15, 0, -1 }; 1333 1334 a = BN_new(); 1335 b[0] = BN_new(); 1336 b[1] = BN_new(); 1337 c = BN_new(); 1338 d = BN_new(); 1339 1340 BN_GF2m_arr2poly(p0, b[0]); 1341 BN_GF2m_arr2poly(p1, b[1]); 1342 1343 for (i = 0; i < num0; i++) { 1344 BN_bntest_rand(a, 1024, 0, 0); 1345 for (j = 0; j < 2; j++) { 1346 BN_GF2m_mod_sqr(c, a, b[j], ctx); 1347 BN_copy(d, a); 1348 BN_GF2m_mod_mul(d, a, d, b[j], ctx); 1349# if 0 /* make test uses ouput in bc but bc can't 1350 * handle GF(2^m) arithmetic */ 1351 if (bp != NULL) { 1352 if (!results) { 1353 BN_print(bp, a); 1354 BIO_puts(bp, " ^ 2 % "); 1355 BN_print(bp, b[j]); 1356 BIO_puts(bp, " = "); 1357 BN_print(bp, c); 1358 BIO_puts(bp, "; a * a = "); 1359 BN_print(bp, d); 1360 BIO_puts(bp, "\n"); 1361 } 1362 } 1363# endif 1364 BN_GF2m_add(d, c, d); 1365 /* Test that a*a = a^2. */ 1366 if (!BN_is_zero(d)) { 1367 fprintf(stderr, "GF(2^m) modular squaring test failed!\n"); 1368 goto err; 1369 } 1370 } 1371 } 1372 ret = 1; 1373 err: 1374 BN_free(a); 1375 BN_free(b[0]); 1376 BN_free(b[1]); 1377 BN_free(c); 1378 BN_free(d); 1379 return ret; 1380} 1381 1382int test_gf2m_mod_inv(BIO *bp, BN_CTX *ctx) 1383{ 1384 BIGNUM *a, *b[2], *c, *d; 1385 int i, j, ret = 0; 1386 int p0[] = { 163, 7, 6, 3, 0, -1 }; 1387 int p1[] = { 193, 15, 0, -1 }; 1388 1389 a = BN_new(); 1390 b[0] = BN_new(); 1391 b[1] = BN_new(); 1392 c = BN_new(); 1393 d = BN_new(); 1394 1395 BN_GF2m_arr2poly(p0, b[0]); 1396 BN_GF2m_arr2poly(p1, b[1]); 1397 1398 for (i = 0; i < num0; i++) { 1399 BN_bntest_rand(a, 512, 0, 0); 1400 for (j = 0; j < 2; j++) { 1401 BN_GF2m_mod_inv(c, a, b[j], ctx); 1402 BN_GF2m_mod_mul(d, a, c, b[j], ctx); 1403# if 0 /* make test uses ouput in bc but bc can't 1404 * handle GF(2^m) arithmetic */ 1405 if (bp != NULL) { 1406 if (!results) { 1407 BN_print(bp, a); 1408 BIO_puts(bp, " * "); 1409 BN_print(bp, c); 1410 BIO_puts(bp, " - 1 % "); 1411 BN_print(bp, b[j]); 1412 BIO_puts(bp, "\n"); 1413 } 1414 } 1415# endif 1416 /* Test that ((1/a)*a) = 1. */ 1417 if (!BN_is_one(d)) { 1418 fprintf(stderr, "GF(2^m) modular inversion test failed!\n"); 1419 goto err; 1420 } 1421 } 1422 } 1423 ret = 1; 1424 err: 1425 BN_free(a); 1426 BN_free(b[0]); 1427 BN_free(b[1]); 1428 BN_free(c); 1429 BN_free(d); 1430 return ret; 1431} 1432 1433int test_gf2m_mod_div(BIO *bp, BN_CTX *ctx) 1434{ 1435 BIGNUM *a, *b[2], *c, *d, *e, *f; 1436 int i, j, ret = 0; 1437 int p0[] = { 163, 7, 6, 3, 0, -1 }; 1438 int p1[] = { 193, 15, 0, -1 }; 1439 1440 a = BN_new(); 1441 b[0] = BN_new(); 1442 b[1] = BN_new(); 1443 c = BN_new(); 1444 d = BN_new(); 1445 e = BN_new(); 1446 f = 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 BN_bntest_rand(c, 512, 0, 0); 1454 for (j = 0; j < 2; j++) { 1455 BN_GF2m_mod_div(d, a, c, b[j], ctx); 1456 BN_GF2m_mod_mul(e, d, c, b[j], ctx); 1457 BN_GF2m_mod_div(f, a, e, b[j], ctx); 1458# if 0 /* make test uses ouput in bc but bc can't 1459 * handle GF(2^m) arithmetic */ 1460 if (bp != NULL) { 1461 if (!results) { 1462 BN_print(bp, a); 1463 BIO_puts(bp, " = "); 1464 BN_print(bp, c); 1465 BIO_puts(bp, " * "); 1466 BN_print(bp, d); 1467 BIO_puts(bp, " % "); 1468 BN_print(bp, b[j]); 1469 BIO_puts(bp, "\n"); 1470 } 1471 } 1472# endif 1473 /* Test that ((a/c)*c)/a = 1. */ 1474 if (!BN_is_one(f)) { 1475 fprintf(stderr, "GF(2^m) modular division test failed!\n"); 1476 goto err; 1477 } 1478 } 1479 } 1480 ret = 1; 1481 err: 1482 BN_free(a); 1483 BN_free(b[0]); 1484 BN_free(b[1]); 1485 BN_free(c); 1486 BN_free(d); 1487 BN_free(e); 1488 BN_free(f); 1489 return ret; 1490} 1491 1492int test_gf2m_mod_exp(BIO *bp, BN_CTX *ctx) 1493{ 1494 BIGNUM *a, *b[2], *c, *d, *e, *f; 1495 int i, j, ret = 0; 1496 int p0[] = { 163, 7, 6, 3, 0, -1 }; 1497 int p1[] = { 193, 15, 0, -1 }; 1498 1499 a = BN_new(); 1500 b[0] = BN_new(); 1501 b[1] = BN_new(); 1502 c = BN_new(); 1503 d = BN_new(); 1504 e = BN_new(); 1505 f = BN_new(); 1506 1507 BN_GF2m_arr2poly(p0, b[0]); 1508 BN_GF2m_arr2poly(p1, b[1]); 1509 1510 for (i = 0; i < num0; i++) { 1511 BN_bntest_rand(a, 512, 0, 0); 1512 BN_bntest_rand(c, 512, 0, 0); 1513 BN_bntest_rand(d, 512, 0, 0); 1514 for (j = 0; j < 2; j++) { 1515 BN_GF2m_mod_exp(e, a, c, b[j], ctx); 1516 BN_GF2m_mod_exp(f, a, d, b[j], ctx); 1517 BN_GF2m_mod_mul(e, e, f, b[j], ctx); 1518 BN_add(f, c, d); 1519 BN_GF2m_mod_exp(f, a, f, b[j], ctx); 1520# if 0 /* make test uses ouput in bc but bc can't 1521 * handle GF(2^m) arithmetic */ 1522 if (bp != NULL) { 1523 if (!results) { 1524 BN_print(bp, a); 1525 BIO_puts(bp, " ^ ("); 1526 BN_print(bp, c); 1527 BIO_puts(bp, " + "); 1528 BN_print(bp, d); 1529 BIO_puts(bp, ") = "); 1530 BN_print(bp, e); 1531 BIO_puts(bp, "; - "); 1532 BN_print(bp, f); 1533 BIO_puts(bp, " % "); 1534 BN_print(bp, b[j]); 1535 BIO_puts(bp, "\n"); 1536 } 1537 } 1538# endif 1539 BN_GF2m_add(f, e, f); 1540 /* Test that a^(c+d)=a^c*a^d. */ 1541 if (!BN_is_zero(f)) { 1542 fprintf(stderr, 1543 "GF(2^m) modular exponentiation test failed!\n"); 1544 goto err; 1545 } 1546 } 1547 } 1548 ret = 1; 1549 err: 1550 BN_free(a); 1551 BN_free(b[0]); 1552 BN_free(b[1]); 1553 BN_free(c); 1554 BN_free(d); 1555 BN_free(e); 1556 BN_free(f); 1557 return ret; 1558} 1559 1560int test_gf2m_mod_sqrt(BIO *bp, BN_CTX *ctx) 1561{ 1562 BIGNUM *a, *b[2], *c, *d, *e, *f; 1563 int i, j, ret = 0; 1564 int p0[] = { 163, 7, 6, 3, 0, -1 }; 1565 int p1[] = { 193, 15, 0, -1 }; 1566 1567 a = BN_new(); 1568 b[0] = BN_new(); 1569 b[1] = BN_new(); 1570 c = BN_new(); 1571 d = BN_new(); 1572 e = BN_new(); 1573 f = BN_new(); 1574 1575 BN_GF2m_arr2poly(p0, b[0]); 1576 BN_GF2m_arr2poly(p1, b[1]); 1577 1578 for (i = 0; i < num0; i++) { 1579 BN_bntest_rand(a, 512, 0, 0); 1580 for (j = 0; j < 2; j++) { 1581 BN_GF2m_mod(c, a, b[j]); 1582 BN_GF2m_mod_sqrt(d, a, b[j], ctx); 1583 BN_GF2m_mod_sqr(e, d, b[j], ctx); 1584# if 0 /* make test uses ouput in bc but bc can't 1585 * handle GF(2^m) arithmetic */ 1586 if (bp != NULL) { 1587 if (!results) { 1588 BN_print(bp, d); 1589 BIO_puts(bp, " ^ 2 - "); 1590 BN_print(bp, a); 1591 BIO_puts(bp, "\n"); 1592 } 1593 } 1594# endif 1595 BN_GF2m_add(f, c, e); 1596 /* Test that d^2 = a, where d = sqrt(a). */ 1597 if (!BN_is_zero(f)) { 1598 fprintf(stderr, "GF(2^m) modular square root test failed!\n"); 1599 goto err; 1600 } 1601 } 1602 } 1603 ret = 1; 1604 err: 1605 BN_free(a); 1606 BN_free(b[0]); 1607 BN_free(b[1]); 1608 BN_free(c); 1609 BN_free(d); 1610 BN_free(e); 1611 BN_free(f); 1612 return ret; 1613} 1614 1615int test_gf2m_mod_solve_quad(BIO *bp, BN_CTX *ctx) 1616{ 1617 BIGNUM *a, *b[2], *c, *d, *e; 1618 int i, j, s = 0, t, ret = 0; 1619 int p0[] = { 163, 7, 6, 3, 0, -1 }; 1620 int p1[] = { 193, 15, 0, -1 }; 1621 1622 a = BN_new(); 1623 b[0] = BN_new(); 1624 b[1] = BN_new(); 1625 c = BN_new(); 1626 d = BN_new(); 1627 e = BN_new(); 1628 1629 BN_GF2m_arr2poly(p0, b[0]); 1630 BN_GF2m_arr2poly(p1, b[1]); 1631 1632 for (i = 0; i < num0; i++) { 1633 BN_bntest_rand(a, 512, 0, 0); 1634 for (j = 0; j < 2; j++) { 1635 t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx); 1636 if (t) { 1637 s++; 1638 BN_GF2m_mod_sqr(d, c, b[j], ctx); 1639 BN_GF2m_add(d, c, d); 1640 BN_GF2m_mod(e, a, b[j]); 1641# if 0 /* make test uses ouput in bc but bc can't 1642 * handle GF(2^m) arithmetic */ 1643 if (bp != NULL) { 1644 if (!results) { 1645 BN_print(bp, c); 1646 BIO_puts(bp, " is root of z^2 + z = "); 1647 BN_print(bp, a); 1648 BIO_puts(bp, " % "); 1649 BN_print(bp, b[j]); 1650 BIO_puts(bp, "\n"); 1651 } 1652 } 1653# endif 1654 BN_GF2m_add(e, e, d); 1655 /* 1656 * Test that solution of quadratic c satisfies c^2 + c = a. 1657 */ 1658 if (!BN_is_zero(e)) { 1659 fprintf(stderr, 1660 "GF(2^m) modular solve quadratic test failed!\n"); 1661 goto err; 1662 } 1663 1664 } else { 1665# if 0 /* make test uses ouput in bc but bc can't 1666 * handle GF(2^m) arithmetic */ 1667 if (bp != NULL) { 1668 if (!results) { 1669 BIO_puts(bp, "There are no roots of z^2 + z = "); 1670 BN_print(bp, a); 1671 BIO_puts(bp, " % "); 1672 BN_print(bp, b[j]); 1673 BIO_puts(bp, "\n"); 1674 } 1675 } 1676# endif 1677 } 1678 } 1679 } 1680 if (s == 0) { 1681 fprintf(stderr, 1682 "All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n", 1683 num0); 1684 fprintf(stderr, 1685 "this is very unlikely and probably indicates an error.\n"); 1686 goto err; 1687 } 1688 ret = 1; 1689 err: 1690 BN_free(a); 1691 BN_free(b[0]); 1692 BN_free(b[1]); 1693 BN_free(c); 1694 BN_free(d); 1695 BN_free(e); 1696 return ret; 1697} 1698#endif 1699static int genprime_cb(int p, int n, BN_GENCB *arg) 1700{ 1701 char c = '*'; 1702 1703 if (p == 0) 1704 c = '.'; 1705 if (p == 1) 1706 c = '+'; 1707 if (p == 2) 1708 c = '*'; 1709 if (p == 3) 1710 c = '\n'; 1711 putc(c, stderr); 1712 fflush(stderr); 1713 return 1; 1714} 1715 1716int test_kron(BIO *bp, BN_CTX *ctx) 1717{ 1718 BN_GENCB cb; 1719 BIGNUM *a, *b, *r, *t; 1720 int i; 1721 int legendre, kronecker; 1722 int ret = 0; 1723 1724 a = BN_new(); 1725 b = BN_new(); 1726 r = BN_new(); 1727 t = BN_new(); 1728 if (a == NULL || b == NULL || r == NULL || t == NULL) 1729 goto err; 1730 1731 BN_GENCB_set(&cb, genprime_cb, NULL); 1732 1733 /* 1734 * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In 1735 * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is 1736 * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we 1737 * generate a random prime b and compare these values for a number of 1738 * random a's. (That is, we run the Solovay-Strassen primality test to 1739 * confirm that b is prime, except that we don't want to test whether b 1740 * is prime but whether BN_kronecker works.) 1741 */ 1742 1743 if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb)) 1744 goto err; 1745 b->neg = rand_neg(); 1746 putc('\n', stderr); 1747 1748 for (i = 0; i < num0; i++) { 1749 if (!BN_bntest_rand(a, 512, 0, 0)) 1750 goto err; 1751 a->neg = rand_neg(); 1752 1753 /* t := (|b|-1)/2 (note that b is odd) */ 1754 if (!BN_copy(t, b)) 1755 goto err; 1756 t->neg = 0; 1757 if (!BN_sub_word(t, 1)) 1758 goto err; 1759 if (!BN_rshift1(t, t)) 1760 goto err; 1761 /* r := a^t mod b */ 1762 b->neg = 0; 1763 1764 if (!BN_mod_exp_recp(r, a, t, b, ctx)) 1765 goto err; 1766 b->neg = 1; 1767 1768 if (BN_is_word(r, 1)) 1769 legendre = 1; 1770 else if (BN_is_zero(r)) 1771 legendre = 0; 1772 else { 1773 if (!BN_add_word(r, 1)) 1774 goto err; 1775 if (0 != BN_ucmp(r, b)) { 1776 fprintf(stderr, "Legendre symbol computation failed\n"); 1777 goto err; 1778 } 1779 legendre = -1; 1780 } 1781 1782 kronecker = BN_kronecker(a, b, ctx); 1783 if (kronecker < -1) 1784 goto err; 1785 /* we actually need BN_kronecker(a, |b|) */ 1786 if (a->neg && b->neg) 1787 kronecker = -kronecker; 1788 1789 if (legendre != kronecker) { 1790 fprintf(stderr, "legendre != kronecker; a = "); 1791 BN_print_fp(stderr, a); 1792 fprintf(stderr, ", b = "); 1793 BN_print_fp(stderr, b); 1794 fprintf(stderr, "\n"); 1795 goto err; 1796 } 1797 1798 putc('.', stderr); 1799 fflush(stderr); 1800 } 1801 1802 putc('\n', stderr); 1803 fflush(stderr); 1804 ret = 1; 1805 err: 1806 if (a != NULL) 1807 BN_free(a); 1808 if (b != NULL) 1809 BN_free(b); 1810 if (r != NULL) 1811 BN_free(r); 1812 if (t != NULL) 1813 BN_free(t); 1814 return ret; 1815} 1816 1817int test_sqrt(BIO *bp, BN_CTX *ctx) 1818{ 1819 BN_GENCB cb; 1820 BIGNUM *a, *p, *r; 1821 int i, j; 1822 int ret = 0; 1823 1824 a = BN_new(); 1825 p = BN_new(); 1826 r = BN_new(); 1827 if (a == NULL || p == NULL || r == NULL) 1828 goto err; 1829 1830 BN_GENCB_set(&cb, genprime_cb, NULL); 1831 1832 for (i = 0; i < 16; i++) { 1833 if (i < 8) { 1834 unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 }; 1835 1836 if (!BN_set_word(p, primes[i])) 1837 goto err; 1838 } else { 1839 if (!BN_set_word(a, 32)) 1840 goto err; 1841 if (!BN_set_word(r, 2 * i + 1)) 1842 goto err; 1843 1844 if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb)) 1845 goto err; 1846 putc('\n', stderr); 1847 } 1848 p->neg = rand_neg(); 1849 1850 for (j = 0; j < num2; j++) { 1851 /* 1852 * construct 'a' such that it is a square modulo p, but in 1853 * general not a proper square and not reduced modulo p 1854 */ 1855 if (!BN_bntest_rand(r, 256, 0, 3)) 1856 goto err; 1857 if (!BN_nnmod(r, r, p, ctx)) 1858 goto err; 1859 if (!BN_mod_sqr(r, r, p, ctx)) 1860 goto err; 1861 if (!BN_bntest_rand(a, 256, 0, 3)) 1862 goto err; 1863 if (!BN_nnmod(a, a, p, ctx)) 1864 goto err; 1865 if (!BN_mod_sqr(a, a, p, ctx)) 1866 goto err; 1867 if (!BN_mul(a, a, r, ctx)) 1868 goto err; 1869 if (rand_neg()) 1870 if (!BN_sub(a, a, p)) 1871 goto err; 1872 1873 if (!BN_mod_sqrt(r, a, p, ctx)) 1874 goto err; 1875 if (!BN_mod_sqr(r, r, p, ctx)) 1876 goto err; 1877 1878 if (!BN_nnmod(a, a, p, ctx)) 1879 goto err; 1880 1881 if (BN_cmp(a, r) != 0) { 1882 fprintf(stderr, "BN_mod_sqrt failed: a = "); 1883 BN_print_fp(stderr, a); 1884 fprintf(stderr, ", r = "); 1885 BN_print_fp(stderr, r); 1886 fprintf(stderr, ", p = "); 1887 BN_print_fp(stderr, p); 1888 fprintf(stderr, "\n"); 1889 goto err; 1890 } 1891 1892 putc('.', stderr); 1893 fflush(stderr); 1894 } 1895 1896 putc('\n', stderr); 1897 fflush(stderr); 1898 } 1899 ret = 1; 1900 err: 1901 if (a != NULL) 1902 BN_free(a); 1903 if (p != NULL) 1904 BN_free(p); 1905 if (r != NULL) 1906 BN_free(r); 1907 return ret; 1908} 1909 1910int test_lshift(BIO *bp, BN_CTX *ctx, BIGNUM *a_) 1911{ 1912 BIGNUM *a, *b, *c, *d; 1913 int i; 1914 1915 b = BN_new(); 1916 c = BN_new(); 1917 d = BN_new(); 1918 BN_one(c); 1919 1920 if (a_) 1921 a = a_; 1922 else { 1923 a = BN_new(); 1924 BN_bntest_rand(a, 200, 0, 0); 1925 a->neg = rand_neg(); 1926 } 1927 for (i = 0; i < num0; i++) { 1928 BN_lshift(b, a, i + 1); 1929 BN_add(c, c, c); 1930 if (bp != NULL) { 1931 if (!results) { 1932 BN_print(bp, a); 1933 BIO_puts(bp, " * "); 1934 BN_print(bp, c); 1935 BIO_puts(bp, " - "); 1936 } 1937 BN_print(bp, b); 1938 BIO_puts(bp, "\n"); 1939 } 1940 BN_mul(d, a, c, ctx); 1941 BN_sub(d, d, b); 1942 if (!BN_is_zero(d)) { 1943 fprintf(stderr, "Left shift test failed!\n"); 1944 fprintf(stderr, "a="); 1945 BN_print_fp(stderr, a); 1946 fprintf(stderr, "\nb="); 1947 BN_print_fp(stderr, b); 1948 fprintf(stderr, "\nc="); 1949 BN_print_fp(stderr, c); 1950 fprintf(stderr, "\nd="); 1951 BN_print_fp(stderr, d); 1952 fprintf(stderr, "\n"); 1953 return 0; 1954 } 1955 } 1956 BN_free(a); 1957 BN_free(b); 1958 BN_free(c); 1959 BN_free(d); 1960 return (1); 1961} 1962 1963int test_lshift1(BIO *bp) 1964{ 1965 BIGNUM *a, *b, *c; 1966 int i; 1967 1968 a = BN_new(); 1969 b = BN_new(); 1970 c = BN_new(); 1971 1972 BN_bntest_rand(a, 200, 0, 0); 1973 a->neg = rand_neg(); 1974 for (i = 0; i < num0; i++) { 1975 BN_lshift1(b, a); 1976 if (bp != NULL) { 1977 if (!results) { 1978 BN_print(bp, a); 1979 BIO_puts(bp, " * 2"); 1980 BIO_puts(bp, " - "); 1981 } 1982 BN_print(bp, b); 1983 BIO_puts(bp, "\n"); 1984 } 1985 BN_add(c, a, a); 1986 BN_sub(a, b, c); 1987 if (!BN_is_zero(a)) { 1988 fprintf(stderr, "Left shift one test failed!\n"); 1989 return 0; 1990 } 1991 1992 BN_copy(a, b); 1993 } 1994 BN_free(a); 1995 BN_free(b); 1996 BN_free(c); 1997 return (1); 1998} 1999 2000int test_rshift(BIO *bp, BN_CTX *ctx) 2001{ 2002 BIGNUM *a, *b, *c, *d, *e; 2003 int i; 2004 2005 a = BN_new(); 2006 b = BN_new(); 2007 c = BN_new(); 2008 d = BN_new(); 2009 e = BN_new(); 2010 BN_one(c); 2011 2012 BN_bntest_rand(a, 200, 0, 0); 2013 a->neg = rand_neg(); 2014 for (i = 0; i < num0; i++) { 2015 BN_rshift(b, a, i + 1); 2016 BN_add(c, c, c); 2017 if (bp != NULL) { 2018 if (!results) { 2019 BN_print(bp, a); 2020 BIO_puts(bp, " / "); 2021 BN_print(bp, c); 2022 BIO_puts(bp, " - "); 2023 } 2024 BN_print(bp, b); 2025 BIO_puts(bp, "\n"); 2026 } 2027 BN_div(d, e, a, c, ctx); 2028 BN_sub(d, d, b); 2029 if (!BN_is_zero(d)) { 2030 fprintf(stderr, "Right shift test failed!\n"); 2031 return 0; 2032 } 2033 } 2034 BN_free(a); 2035 BN_free(b); 2036 BN_free(c); 2037 BN_free(d); 2038 BN_free(e); 2039 return (1); 2040} 2041 2042int test_rshift1(BIO *bp) 2043{ 2044 BIGNUM *a, *b, *c; 2045 int i; 2046 2047 a = BN_new(); 2048 b = BN_new(); 2049 c = BN_new(); 2050 2051 BN_bntest_rand(a, 200, 0, 0); 2052 a->neg = rand_neg(); 2053 for (i = 0; i < num0; i++) { 2054 BN_rshift1(b, a); 2055 if (bp != NULL) { 2056 if (!results) { 2057 BN_print(bp, a); 2058 BIO_puts(bp, " / 2"); 2059 BIO_puts(bp, " - "); 2060 } 2061 BN_print(bp, b); 2062 BIO_puts(bp, "\n"); 2063 } 2064 BN_sub(c, a, b); 2065 BN_sub(c, c, b); 2066 if (!BN_is_zero(c) && !BN_abs_is_word(c, 1)) { 2067 fprintf(stderr, "Right shift one test failed!\n"); 2068 return 0; 2069 } 2070 BN_copy(a, b); 2071 } 2072 BN_free(a); 2073 BN_free(b); 2074 BN_free(c); 2075 return (1); 2076} 2077 2078int rand_neg(void) 2079{ 2080 static unsigned int neg = 0; 2081 static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 }; 2082 2083 return (sign[(neg++) % 8]); 2084} 2085