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#include <stdio.h> 60#include <stdlib.h> 61#include <string.h> 62 63#include "e_os.h" 64 65#include <openssl/bio.h> 66#include <openssl/bn.h> 67#include <openssl/rand.h> 68#include <openssl/x509.h> 69#include <openssl/err.h> 70 71const int num0 = 100; /* number of tests */ 72const int num1 = 50; /* additional tests for some functions */ 73const int num2 = 5; /* number of tests for slow functions */ 74 75int test_add(BIO *bp); 76int test_sub(BIO *bp); 77int test_lshift1(BIO *bp); 78int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_); 79int test_rshift1(BIO *bp); 80int test_rshift(BIO *bp,BN_CTX *ctx); 81int test_div(BIO *bp,BN_CTX *ctx); 82int test_div_recp(BIO *bp,BN_CTX *ctx); 83int test_mul(BIO *bp); 84int test_sqr(BIO *bp,BN_CTX *ctx); 85int test_mont(BIO *bp,BN_CTX *ctx); 86int test_mod(BIO *bp,BN_CTX *ctx); 87int test_mod_mul(BIO *bp,BN_CTX *ctx); 88int test_mod_exp(BIO *bp,BN_CTX *ctx); 89int test_exp(BIO *bp,BN_CTX *ctx); 90int test_kron(BIO *bp,BN_CTX *ctx); 91int test_sqrt(BIO *bp,BN_CTX *ctx); 92int rand_neg(void); 93static int results=0; 94 95static unsigned char lst[]="\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9" 96"\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0"; 97 98static const char rnd_seed[] = "string to make the random number generator think it has entropy"; 99 100static void message(BIO *out, char *m) 101 { 102 fprintf(stderr, "test %s\n", m); 103 BIO_puts(out, "print \"test "); 104 BIO_puts(out, m); 105 BIO_puts(out, "\\n\"\n"); 106 } 107 108int main(int argc, char *argv[]) 109 { 110 BN_CTX *ctx; 111 BIO *out; 112 char *outfile=NULL; 113 114 results = 0; 115 116 RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_generate_prime may fail */ 117 118 argc--; 119 argv++; 120 while (argc >= 1) 121 { 122 if (strcmp(*argv,"-results") == 0) 123 results=1; 124 else if (strcmp(*argv,"-out") == 0) 125 { 126 if (--argc < 1) break; 127 outfile= *(++argv); 128 } 129 argc--; 130 argv++; 131 } 132 133 134 ctx=BN_CTX_new(); 135 if (ctx == NULL) EXIT(1); 136 137 out=BIO_new(BIO_s_file()); 138 if (out == NULL) EXIT(1); 139 if (outfile == NULL) 140 { 141 BIO_set_fp(out,stdout,BIO_NOCLOSE); 142 } 143 else 144 { 145 if (!BIO_write_filename(out,outfile)) 146 { 147 perror(outfile); 148 EXIT(1); 149 } 150 } 151 152 if (!results) 153 BIO_puts(out,"obase=16\nibase=16\n"); 154 155 message(out,"BN_add"); 156 if (!test_add(out)) goto err; 157 BIO_flush(out); 158 159 message(out,"BN_sub"); 160 if (!test_sub(out)) goto err; 161 BIO_flush(out); 162 163 message(out,"BN_lshift1"); 164 if (!test_lshift1(out)) goto err; 165 BIO_flush(out); 166 167 message(out,"BN_lshift (fixed)"); 168 if (!test_lshift(out,ctx,BN_bin2bn(lst,sizeof(lst)-1,NULL))) 169 goto err; 170 BIO_flush(out); 171 172 message(out,"BN_lshift"); 173 if (!test_lshift(out,ctx,NULL)) goto err; 174 BIO_flush(out); 175 176 message(out,"BN_rshift1"); 177 if (!test_rshift1(out)) goto err; 178 BIO_flush(out); 179 180 message(out,"BN_rshift"); 181 if (!test_rshift(out,ctx)) goto err; 182 BIO_flush(out); 183 184 message(out,"BN_sqr"); 185 if (!test_sqr(out,ctx)) goto err; 186 BIO_flush(out); 187 188 message(out,"BN_mul"); 189 if (!test_mul(out)) goto err; 190 BIO_flush(out); 191 192 message(out,"BN_div"); 193 if (!test_div(out,ctx)) goto err; 194 BIO_flush(out); 195 196 message(out,"BN_div_recp"); 197 if (!test_div_recp(out,ctx)) goto err; 198 BIO_flush(out); 199 200 message(out,"BN_mod"); 201 if (!test_mod(out,ctx)) goto err; 202 BIO_flush(out); 203 204 message(out,"BN_mod_mul"); 205 if (!test_mod_mul(out,ctx)) goto err; 206 BIO_flush(out); 207 208 message(out,"BN_mont"); 209 if (!test_mont(out,ctx)) goto err; 210 BIO_flush(out); 211 212 message(out,"BN_mod_exp"); 213 if (!test_mod_exp(out,ctx)) goto err; 214 BIO_flush(out); 215 216 message(out,"BN_exp"); 217 if (!test_exp(out,ctx)) goto err; 218 BIO_flush(out); 219 220 message(out,"BN_kronecker"); 221 if (!test_kron(out,ctx)) goto err; 222 BIO_flush(out); 223 224 message(out,"BN_mod_sqrt"); 225 if (!test_sqrt(out,ctx)) goto err; 226 BIO_flush(out); 227 228 BN_CTX_free(ctx); 229 BIO_free(out); 230 231/**/ 232 EXIT(0); 233err: 234 BIO_puts(out,"1\n"); /* make sure the Perl script fed by bc notices 235 * the failure, see test_bn in test/Makefile */ 236 BIO_flush(out); 237 ERR_load_crypto_strings(); 238 ERR_print_errors_fp(stderr); 239 EXIT(1); 240 return(1); 241 } 242 243int test_add(BIO *bp) 244 { 245 BIGNUM a,b,c; 246 int i; 247 248 BN_init(&a); 249 BN_init(&b); 250 BN_init(&c); 251 252 BN_bntest_rand(&a,512,0,0); 253 for (i=0; i<num0; i++) 254 { 255 BN_bntest_rand(&b,450+i,0,0); 256 a.neg=rand_neg(); 257 b.neg=rand_neg(); 258 BN_add(&c,&a,&b); 259 if (bp != NULL) 260 { 261 if (!results) 262 { 263 BN_print(bp,&a); 264 BIO_puts(bp," + "); 265 BN_print(bp,&b); 266 BIO_puts(bp," - "); 267 } 268 BN_print(bp,&c); 269 BIO_puts(bp,"\n"); 270 } 271 a.neg=!a.neg; 272 b.neg=!b.neg; 273 BN_add(&c,&c,&b); 274 BN_add(&c,&c,&a); 275 if(!BN_is_zero(&c)) 276 { 277 fprintf(stderr,"Add test failed!\n"); 278 return 0; 279 } 280 } 281 BN_free(&a); 282 BN_free(&b); 283 BN_free(&c); 284 return(1); 285 } 286 287int test_sub(BIO *bp) 288 { 289 BIGNUM a,b,c; 290 int i; 291 292 BN_init(&a); 293 BN_init(&b); 294 BN_init(&c); 295 296 for (i=0; i<num0+num1; i++) 297 { 298 if (i < num1) 299 { 300 BN_bntest_rand(&a,512,0,0); 301 BN_copy(&b,&a); 302 if (BN_set_bit(&a,i)==0) return(0); 303 BN_add_word(&b,i); 304 } 305 else 306 { 307 BN_bntest_rand(&b,400+i-num1,0,0); 308 a.neg=rand_neg(); 309 b.neg=rand_neg(); 310 } 311 BN_sub(&c,&a,&b); 312 if (bp != NULL) 313 { 314 if (!results) 315 { 316 BN_print(bp,&a); 317 BIO_puts(bp," - "); 318 BN_print(bp,&b); 319 BIO_puts(bp," - "); 320 } 321 BN_print(bp,&c); 322 BIO_puts(bp,"\n"); 323 } 324 BN_add(&c,&c,&b); 325 BN_sub(&c,&c,&a); 326 if(!BN_is_zero(&c)) 327 { 328 fprintf(stderr,"Subtract test failed!\n"); 329 return 0; 330 } 331 } 332 BN_free(&a); 333 BN_free(&b); 334 BN_free(&c); 335 return(1); 336 } 337 338int test_div(BIO *bp, BN_CTX *ctx) 339 { 340 BIGNUM a,b,c,d,e; 341 int i; 342 343 BN_init(&a); 344 BN_init(&b); 345 BN_init(&c); 346 BN_init(&d); 347 BN_init(&e); 348 349 for (i=0; i<num0+num1; i++) 350 { 351 if (i < num1) 352 { 353 BN_bntest_rand(&a,400,0,0); 354 BN_copy(&b,&a); 355 BN_lshift(&a,&a,i); 356 BN_add_word(&a,i); 357 } 358 else 359 BN_bntest_rand(&b,50+3*(i-num1),0,0); 360 a.neg=rand_neg(); 361 b.neg=rand_neg(); 362 BN_div(&d,&c,&a,&b,ctx); 363 if (bp != NULL) 364 { 365 if (!results) 366 { 367 BN_print(bp,&a); 368 BIO_puts(bp," / "); 369 BN_print(bp,&b); 370 BIO_puts(bp," - "); 371 } 372 BN_print(bp,&d); 373 BIO_puts(bp,"\n"); 374 375 if (!results) 376 { 377 BN_print(bp,&a); 378 BIO_puts(bp," % "); 379 BN_print(bp,&b); 380 BIO_puts(bp," - "); 381 } 382 BN_print(bp,&c); 383 BIO_puts(bp,"\n"); 384 } 385 BN_mul(&e,&d,&b,ctx); 386 BN_add(&d,&e,&c); 387 BN_sub(&d,&d,&a); 388 if(!BN_is_zero(&d)) 389 { 390 fprintf(stderr,"Division test failed!\n"); 391 return 0; 392 } 393 } 394 BN_free(&a); 395 BN_free(&b); 396 BN_free(&c); 397 BN_free(&d); 398 BN_free(&e); 399 return(1); 400 } 401 402int test_div_recp(BIO *bp, BN_CTX *ctx) 403 { 404 BIGNUM a,b,c,d,e; 405 BN_RECP_CTX recp; 406 int i; 407 408 BN_RECP_CTX_init(&recp); 409 BN_init(&a); 410 BN_init(&b); 411 BN_init(&c); 412 BN_init(&d); 413 BN_init(&e); 414 415 for (i=0; i<num0+num1; i++) 416 { 417 if (i < num1) 418 { 419 BN_bntest_rand(&a,400,0,0); 420 BN_copy(&b,&a); 421 BN_lshift(&a,&a,i); 422 BN_add_word(&a,i); 423 } 424 else 425 BN_bntest_rand(&b,50+3*(i-num1),0,0); 426 a.neg=rand_neg(); 427 b.neg=rand_neg(); 428 BN_RECP_CTX_set(&recp,&b,ctx); 429 BN_div_recp(&d,&c,&a,&recp,ctx); 430 if (bp != NULL) 431 { 432 if (!results) 433 { 434 BN_print(bp,&a); 435 BIO_puts(bp," / "); 436 BN_print(bp,&b); 437 BIO_puts(bp," - "); 438 } 439 BN_print(bp,&d); 440 BIO_puts(bp,"\n"); 441 442 if (!results) 443 { 444 BN_print(bp,&a); 445 BIO_puts(bp," % "); 446 BN_print(bp,&b); 447 BIO_puts(bp," - "); 448 } 449 BN_print(bp,&c); 450 BIO_puts(bp,"\n"); 451 } 452 BN_mul(&e,&d,&b,ctx); 453 BN_add(&d,&e,&c); 454 BN_sub(&d,&d,&a); 455 if(!BN_is_zero(&d)) 456 { 457 fprintf(stderr,"Reciprocal division test failed!\n"); 458 fprintf(stderr,"a="); 459 BN_print_fp(stderr,&a); 460 fprintf(stderr,"\nb="); 461 BN_print_fp(stderr,&b); 462 fprintf(stderr,"\n"); 463 return 0; 464 } 465 } 466 BN_free(&a); 467 BN_free(&b); 468 BN_free(&c); 469 BN_free(&d); 470 BN_free(&e); 471 BN_RECP_CTX_free(&recp); 472 return(1); 473 } 474 475int test_mul(BIO *bp) 476 { 477 BIGNUM a,b,c,d,e; 478 int i; 479 BN_CTX *ctx; 480 481 ctx = BN_CTX_new(); 482 if (ctx == NULL) EXIT(1); 483 484 BN_init(&a); 485 BN_init(&b); 486 BN_init(&c); 487 BN_init(&d); 488 BN_init(&e); 489 490 for (i=0; i<num0+num1; i++) 491 { 492 if (i <= num1) 493 { 494 BN_bntest_rand(&a,100,0,0); 495 BN_bntest_rand(&b,100,0,0); 496 } 497 else 498 BN_bntest_rand(&b,i-num1,0,0); 499 a.neg=rand_neg(); 500 b.neg=rand_neg(); 501 BN_mul(&c,&a,&b,ctx); 502 if (bp != NULL) 503 { 504 if (!results) 505 { 506 BN_print(bp,&a); 507 BIO_puts(bp," * "); 508 BN_print(bp,&b); 509 BIO_puts(bp," - "); 510 } 511 BN_print(bp,&c); 512 BIO_puts(bp,"\n"); 513 } 514 BN_div(&d,&e,&c,&a,ctx); 515 BN_sub(&d,&d,&b); 516 if(!BN_is_zero(&d) || !BN_is_zero(&e)) 517 { 518 fprintf(stderr,"Multiplication test failed!\n"); 519 return 0; 520 } 521 } 522 BN_free(&a); 523 BN_free(&b); 524 BN_free(&c); 525 BN_free(&d); 526 BN_free(&e); 527 BN_CTX_free(ctx); 528 return(1); 529 } 530 531int test_sqr(BIO *bp, BN_CTX *ctx) 532 { 533 BIGNUM a,c,d,e; 534 int i; 535 536 BN_init(&a); 537 BN_init(&c); 538 BN_init(&d); 539 BN_init(&e); 540 541 for (i=0; i<num0; i++) 542 { 543 BN_bntest_rand(&a,40+i*10,0,0); 544 a.neg=rand_neg(); 545 BN_sqr(&c,&a,ctx); 546 if (bp != NULL) 547 { 548 if (!results) 549 { 550 BN_print(bp,&a); 551 BIO_puts(bp," * "); 552 BN_print(bp,&a); 553 BIO_puts(bp," - "); 554 } 555 BN_print(bp,&c); 556 BIO_puts(bp,"\n"); 557 } 558 BN_div(&d,&e,&c,&a,ctx); 559 BN_sub(&d,&d,&a); 560 if(!BN_is_zero(&d) || !BN_is_zero(&e)) 561 { 562 fprintf(stderr,"Square test failed!\n"); 563 return 0; 564 } 565 } 566 BN_free(&a); 567 BN_free(&c); 568 BN_free(&d); 569 BN_free(&e); 570 return(1); 571 } 572 573int test_mont(BIO *bp, BN_CTX *ctx) 574 { 575 BIGNUM a,b,c,d,A,B; 576 BIGNUM n; 577 int i; 578 BN_MONT_CTX *mont; 579 580 BN_init(&a); 581 BN_init(&b); 582 BN_init(&c); 583 BN_init(&d); 584 BN_init(&A); 585 BN_init(&B); 586 BN_init(&n); 587 588 mont=BN_MONT_CTX_new(); 589 590 BN_bntest_rand(&a,100,0,0); /**/ 591 BN_bntest_rand(&b,100,0,0); /**/ 592 for (i=0; i<num2; i++) 593 { 594 int bits = (200*(i+1))/num2; 595 596 if (bits == 0) 597 continue; 598 BN_bntest_rand(&n,bits,0,1); 599 BN_MONT_CTX_set(mont,&n,ctx); 600 601 BN_nnmod(&a,&a,&n,ctx); 602 BN_nnmod(&b,&b,&n,ctx); 603 604 BN_to_montgomery(&A,&a,mont,ctx); 605 BN_to_montgomery(&B,&b,mont,ctx); 606 607 BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/ 608 BN_from_montgomery(&A,&c,mont,ctx);/**/ 609 if (bp != NULL) 610 { 611 if (!results) 612 { 613#ifdef undef 614fprintf(stderr,"%d * %d %% %d\n", 615BN_num_bits(&a), 616BN_num_bits(&b), 617BN_num_bits(mont->N)); 618#endif 619 BN_print(bp,&a); 620 BIO_puts(bp," * "); 621 BN_print(bp,&b); 622 BIO_puts(bp," % "); 623 BN_print(bp,&(mont->N)); 624 BIO_puts(bp," - "); 625 } 626 BN_print(bp,&A); 627 BIO_puts(bp,"\n"); 628 } 629 BN_mod_mul(&d,&a,&b,&n,ctx); 630 BN_sub(&d,&d,&A); 631 if(!BN_is_zero(&d)) 632 { 633 fprintf(stderr,"Montgomery multiplication test failed!\n"); 634 return 0; 635 } 636 } 637 BN_MONT_CTX_free(mont); 638 BN_free(&a); 639 BN_free(&b); 640 BN_free(&c); 641 BN_free(&d); 642 BN_free(&A); 643 BN_free(&B); 644 BN_free(&n); 645 return(1); 646 } 647 648int test_mod(BIO *bp, BN_CTX *ctx) 649 { 650 BIGNUM *a,*b,*c,*d,*e; 651 int i; 652 653 a=BN_new(); 654 b=BN_new(); 655 c=BN_new(); 656 d=BN_new(); 657 e=BN_new(); 658 659 BN_bntest_rand(a,1024,0,0); /**/ 660 for (i=0; i<num0; i++) 661 { 662 BN_bntest_rand(b,450+i*10,0,0); /**/ 663 a->neg=rand_neg(); 664 b->neg=rand_neg(); 665 BN_mod(c,a,b,ctx);/**/ 666 if (bp != NULL) 667 { 668 if (!results) 669 { 670 BN_print(bp,a); 671 BIO_puts(bp," % "); 672 BN_print(bp,b); 673 BIO_puts(bp," - "); 674 } 675 BN_print(bp,c); 676 BIO_puts(bp,"\n"); 677 } 678 BN_div(d,e,a,b,ctx); 679 BN_sub(e,e,c); 680 if(!BN_is_zero(e)) 681 { 682 fprintf(stderr,"Modulo test failed!\n"); 683 return 0; 684 } 685 } 686 BN_free(a); 687 BN_free(b); 688 BN_free(c); 689 BN_free(d); 690 BN_free(e); 691 return(1); 692 } 693 694int test_mod_mul(BIO *bp, BN_CTX *ctx) 695 { 696 BIGNUM *a,*b,*c,*d,*e; 697 int i,j; 698 699 a=BN_new(); 700 b=BN_new(); 701 c=BN_new(); 702 d=BN_new(); 703 e=BN_new(); 704 705 for (j=0; j<3; j++) { 706 BN_bntest_rand(c,1024,0,0); /**/ 707 for (i=0; i<num0; i++) 708 { 709 BN_bntest_rand(a,475+i*10,0,0); /**/ 710 BN_bntest_rand(b,425+i*11,0,0); /**/ 711 a->neg=rand_neg(); 712 b->neg=rand_neg(); 713 if (!BN_mod_mul(e,a,b,c,ctx)) 714 { 715 unsigned long l; 716 717 while ((l=ERR_get_error())) 718 fprintf(stderr,"ERROR:%s\n", 719 ERR_error_string(l,NULL)); 720 EXIT(1); 721 } 722 if (bp != NULL) 723 { 724 if (!results) 725 { 726 BN_print(bp,a); 727 BIO_puts(bp," * "); 728 BN_print(bp,b); 729 BIO_puts(bp," % "); 730 BN_print(bp,c); 731 if ((a->neg ^ b->neg) && !BN_is_zero(e)) 732 { 733 /* If (a*b) % c is negative, c must be added 734 * in order to obtain the normalized remainder 735 * (new with OpenSSL 0.9.7, previous versions of 736 * BN_mod_mul could generate negative results) 737 */ 738 BIO_puts(bp," + "); 739 BN_print(bp,c); 740 } 741 BIO_puts(bp," - "); 742 } 743 BN_print(bp,e); 744 BIO_puts(bp,"\n"); 745 } 746 BN_mul(d,a,b,ctx); 747 BN_sub(d,d,e); 748 BN_div(a,b,d,c,ctx); 749 if(!BN_is_zero(b)) 750 { 751 fprintf(stderr,"Modulo multiply test failed!\n"); 752 ERR_print_errors_fp(stderr); 753 return 0; 754 } 755 } 756 } 757 BN_free(a); 758 BN_free(b); 759 BN_free(c); 760 BN_free(d); 761 BN_free(e); 762 return(1); 763 } 764 765int test_mod_exp(BIO *bp, BN_CTX *ctx) 766 { 767 BIGNUM *a,*b,*c,*d,*e; 768 int i; 769 770 a=BN_new(); 771 b=BN_new(); 772 c=BN_new(); 773 d=BN_new(); 774 e=BN_new(); 775 776 BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */ 777 for (i=0; i<num2; i++) 778 { 779 BN_bntest_rand(a,20+i*5,0,0); /**/ 780 BN_bntest_rand(b,2+i,0,0); /**/ 781 782 if (!BN_mod_exp(d,a,b,c,ctx)) 783 return(00); 784 785 if (bp != NULL) 786 { 787 if (!results) 788 { 789 BN_print(bp,a); 790 BIO_puts(bp," ^ "); 791 BN_print(bp,b); 792 BIO_puts(bp," % "); 793 BN_print(bp,c); 794 BIO_puts(bp," - "); 795 } 796 BN_print(bp,d); 797 BIO_puts(bp,"\n"); 798 } 799 BN_exp(e,a,b,ctx); 800 BN_sub(e,e,d); 801 BN_div(a,b,e,c,ctx); 802 if(!BN_is_zero(b)) 803 { 804 fprintf(stderr,"Modulo exponentiation test failed!\n"); 805 return 0; 806 } 807 } 808 BN_free(a); 809 BN_free(b); 810 BN_free(c); 811 BN_free(d); 812 BN_free(e); 813 return(1); 814 } 815 816int test_exp(BIO *bp, BN_CTX *ctx) 817 { 818 BIGNUM *a,*b,*d,*e,*one; 819 int i; 820 821 a=BN_new(); 822 b=BN_new(); 823 d=BN_new(); 824 e=BN_new(); 825 one=BN_new(); 826 BN_one(one); 827 828 for (i=0; i<num2; i++) 829 { 830 BN_bntest_rand(a,20+i*5,0,0); /**/ 831 BN_bntest_rand(b,2+i,0,0); /**/ 832 833 if (!BN_exp(d,a,b,ctx)) 834 return(00); 835 836 if (bp != NULL) 837 { 838 if (!results) 839 { 840 BN_print(bp,a); 841 BIO_puts(bp," ^ "); 842 BN_print(bp,b); 843 BIO_puts(bp," - "); 844 } 845 BN_print(bp,d); 846 BIO_puts(bp,"\n"); 847 } 848 BN_one(e); 849 for( ; !BN_is_zero(b) ; BN_sub(b,b,one)) 850 BN_mul(e,e,a,ctx); 851 BN_sub(e,e,d); 852 if(!BN_is_zero(e)) 853 { 854 fprintf(stderr,"Exponentiation test failed!\n"); 855 return 0; 856 } 857 } 858 BN_free(a); 859 BN_free(b); 860 BN_free(d); 861 BN_free(e); 862 BN_free(one); 863 return(1); 864 } 865 866static void genprime_cb(int p, int n, void *arg) 867 { 868 char c='*'; 869 870 if (p == 0) c='.'; 871 if (p == 1) c='+'; 872 if (p == 2) c='*'; 873 if (p == 3) c='\n'; 874 putc(c, stderr); 875 fflush(stderr); 876 (void)n; 877 (void)arg; 878 } 879 880int test_kron(BIO *bp, BN_CTX *ctx) 881 { 882 BIGNUM *a,*b,*r,*t; 883 int i; 884 int legendre, kronecker; 885 int ret = 0; 886 887 a = BN_new(); 888 b = BN_new(); 889 r = BN_new(); 890 t = BN_new(); 891 if (a == NULL || b == NULL || r == NULL || t == NULL) goto err; 892 893 /* We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). 894 * In this case we know that if b is prime, then BN_kronecker(a, b, ctx) 895 * is congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). 896 * So we generate a random prime b and compare these values 897 * for a number of random a's. (That is, we run the Solovay-Strassen 898 * primality test to confirm that b is prime, except that we 899 * don't want to test whether b is prime but whether BN_kronecker 900 * works.) */ 901 902 if (!BN_generate_prime(b, 512, 0, NULL, NULL, genprime_cb, NULL)) goto err; 903 b->neg = rand_neg(); 904 putc('\n', stderr); 905 906 for (i = 0; i < num0; i++) 907 { 908 if (!BN_bntest_rand(a, 512, 0, 0)) goto err; 909 a->neg = rand_neg(); 910 911 /* t := (|b|-1)/2 (note that b is odd) */ 912 if (!BN_copy(t, b)) goto err; 913 t->neg = 0; 914 if (!BN_sub_word(t, 1)) goto err; 915 if (!BN_rshift1(t, t)) goto err; 916 /* r := a^t mod b */ 917 b->neg=0; 918 919 if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err; 920 b->neg=1; 921 922 if (BN_is_word(r, 1)) 923 legendre = 1; 924 else if (BN_is_zero(r)) 925 legendre = 0; 926 else 927 { 928 if (!BN_add_word(r, 1)) goto err; 929 if (0 != BN_ucmp(r, b)) 930 { 931 fprintf(stderr, "Legendre symbol computation failed\n"); 932 goto err; 933 } 934 legendre = -1; 935 } 936 937 kronecker = BN_kronecker(a, b, ctx); 938 if (kronecker < -1) goto err; 939 /* we actually need BN_kronecker(a, |b|) */ 940 if (a->neg && b->neg) 941 kronecker = -kronecker; 942 943 if (legendre != kronecker) 944 { 945 fprintf(stderr, "legendre != kronecker; a = "); 946 BN_print_fp(stderr, a); 947 fprintf(stderr, ", b = "); 948 BN_print_fp(stderr, b); 949 fprintf(stderr, "\n"); 950 goto err; 951 } 952 953 putc('.', stderr); 954 fflush(stderr); 955 } 956 957 putc('\n', stderr); 958 fflush(stderr); 959 ret = 1; 960 err: 961 if (a != NULL) BN_free(a); 962 if (b != NULL) BN_free(b); 963 if (r != NULL) BN_free(r); 964 if (t != NULL) BN_free(t); 965 return ret; 966 } 967 968int test_sqrt(BIO *bp, BN_CTX *ctx) 969 { 970 BIGNUM *a,*p,*r; 971 int i, j; 972 int ret = 0; 973 974 a = BN_new(); 975 p = BN_new(); 976 r = BN_new(); 977 if (a == NULL || p == NULL || r == NULL) goto err; 978 979 for (i = 0; i < 16; i++) 980 { 981 if (i < 8) 982 { 983 unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 }; 984 985 if (!BN_set_word(p, primes[i])) goto err; 986 } 987 else 988 { 989 if (!BN_set_word(a, 32)) goto err; 990 if (!BN_set_word(r, 2*i + 1)) goto err; 991 992 if (!BN_generate_prime(p, 256, 0, a, r, genprime_cb, NULL)) goto err; 993 putc('\n', stderr); 994 } 995 p->neg = rand_neg(); 996 997 for (j = 0; j < num2; j++) 998 { 999 /* construct 'a' such that it is a square modulo p, 1000 * but in general not a proper square and not reduced modulo p */ 1001 if (!BN_bntest_rand(r, 256, 0, 3)) goto err; 1002 if (!BN_nnmod(r, r, p, ctx)) goto err; 1003 if (!BN_mod_sqr(r, r, p, ctx)) goto err; 1004 if (!BN_bntest_rand(a, 256, 0, 3)) goto err; 1005 if (!BN_nnmod(a, a, p, ctx)) goto err; 1006 if (!BN_mod_sqr(a, a, p, ctx)) goto err; 1007 if (!BN_mul(a, a, r, ctx)) goto err; 1008 if (rand_neg()) 1009 if (!BN_sub(a, a, p)) goto err; 1010 1011 if (!BN_mod_sqrt(r, a, p, ctx)) goto err; 1012 if (!BN_mod_sqr(r, r, p, ctx)) goto err; 1013 1014 if (!BN_nnmod(a, a, p, ctx)) goto err; 1015 1016 if (BN_cmp(a, r) != 0) 1017 { 1018 fprintf(stderr, "BN_mod_sqrt failed: a = "); 1019 BN_print_fp(stderr, a); 1020 fprintf(stderr, ", r = "); 1021 BN_print_fp(stderr, r); 1022 fprintf(stderr, ", p = "); 1023 BN_print_fp(stderr, p); 1024 fprintf(stderr, "\n"); 1025 goto err; 1026 } 1027 1028 putc('.', stderr); 1029 fflush(stderr); 1030 } 1031 1032 putc('\n', stderr); 1033 fflush(stderr); 1034 } 1035 ret = 1; 1036 err: 1037 if (a != NULL) BN_free(a); 1038 if (p != NULL) BN_free(p); 1039 if (r != NULL) BN_free(r); 1040 return ret; 1041 } 1042 1043int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_) 1044 { 1045 BIGNUM *a,*b,*c,*d; 1046 int i; 1047 1048 b=BN_new(); 1049 c=BN_new(); 1050 d=BN_new(); 1051 BN_one(c); 1052 1053 if(a_) 1054 a=a_; 1055 else 1056 { 1057 a=BN_new(); 1058 BN_bntest_rand(a,200,0,0); /**/ 1059 a->neg=rand_neg(); 1060 } 1061 for (i=0; i<num0; i++) 1062 { 1063 BN_lshift(b,a,i+1); 1064 BN_add(c,c,c); 1065 if (bp != NULL) 1066 { 1067 if (!results) 1068 { 1069 BN_print(bp,a); 1070 BIO_puts(bp," * "); 1071 BN_print(bp,c); 1072 BIO_puts(bp," - "); 1073 } 1074 BN_print(bp,b); 1075 BIO_puts(bp,"\n"); 1076 } 1077 BN_mul(d,a,c,ctx); 1078 BN_sub(d,d,b); 1079 if(!BN_is_zero(d)) 1080 { 1081 fprintf(stderr,"Left shift test failed!\n"); 1082 fprintf(stderr,"a="); 1083 BN_print_fp(stderr,a); 1084 fprintf(stderr,"\nb="); 1085 BN_print_fp(stderr,b); 1086 fprintf(stderr,"\nc="); 1087 BN_print_fp(stderr,c); 1088 fprintf(stderr,"\nd="); 1089 BN_print_fp(stderr,d); 1090 fprintf(stderr,"\n"); 1091 return 0; 1092 } 1093 } 1094 BN_free(a); 1095 BN_free(b); 1096 BN_free(c); 1097 BN_free(d); 1098 return(1); 1099 } 1100 1101int test_lshift1(BIO *bp) 1102 { 1103 BIGNUM *a,*b,*c; 1104 int i; 1105 1106 a=BN_new(); 1107 b=BN_new(); 1108 c=BN_new(); 1109 1110 BN_bntest_rand(a,200,0,0); /**/ 1111 a->neg=rand_neg(); 1112 for (i=0; i<num0; i++) 1113 { 1114 BN_lshift1(b,a); 1115 if (bp != NULL) 1116 { 1117 if (!results) 1118 { 1119 BN_print(bp,a); 1120 BIO_puts(bp," * 2"); 1121 BIO_puts(bp," - "); 1122 } 1123 BN_print(bp,b); 1124 BIO_puts(bp,"\n"); 1125 } 1126 BN_add(c,a,a); 1127 BN_sub(a,b,c); 1128 if(!BN_is_zero(a)) 1129 { 1130 fprintf(stderr,"Left shift one test failed!\n"); 1131 return 0; 1132 } 1133 1134 BN_copy(a,b); 1135 } 1136 BN_free(a); 1137 BN_free(b); 1138 BN_free(c); 1139 return(1); 1140 } 1141 1142int test_rshift(BIO *bp,BN_CTX *ctx) 1143 { 1144 BIGNUM *a,*b,*c,*d,*e; 1145 int i; 1146 1147 a=BN_new(); 1148 b=BN_new(); 1149 c=BN_new(); 1150 d=BN_new(); 1151 e=BN_new(); 1152 BN_one(c); 1153 1154 BN_bntest_rand(a,200,0,0); /**/ 1155 a->neg=rand_neg(); 1156 for (i=0; i<num0; i++) 1157 { 1158 BN_rshift(b,a,i+1); 1159 BN_add(c,c,c); 1160 if (bp != NULL) 1161 { 1162 if (!results) 1163 { 1164 BN_print(bp,a); 1165 BIO_puts(bp," / "); 1166 BN_print(bp,c); 1167 BIO_puts(bp," - "); 1168 } 1169 BN_print(bp,b); 1170 BIO_puts(bp,"\n"); 1171 } 1172 BN_div(d,e,a,c,ctx); 1173 BN_sub(d,d,b); 1174 if(!BN_is_zero(d)) 1175 { 1176 fprintf(stderr,"Right shift test failed!\n"); 1177 return 0; 1178 } 1179 } 1180 BN_free(a); 1181 BN_free(b); 1182 BN_free(c); 1183 BN_free(d); 1184 BN_free(e); 1185 return(1); 1186 } 1187 1188int test_rshift1(BIO *bp) 1189 { 1190 BIGNUM *a,*b,*c; 1191 int i; 1192 1193 a=BN_new(); 1194 b=BN_new(); 1195 c=BN_new(); 1196 1197 BN_bntest_rand(a,200,0,0); /**/ 1198 a->neg=rand_neg(); 1199 for (i=0; i<num0; i++) 1200 { 1201 BN_rshift1(b,a); 1202 if (bp != NULL) 1203 { 1204 if (!results) 1205 { 1206 BN_print(bp,a); 1207 BIO_puts(bp," / 2"); 1208 BIO_puts(bp," - "); 1209 } 1210 BN_print(bp,b); 1211 BIO_puts(bp,"\n"); 1212 } 1213 BN_sub(c,a,b); 1214 BN_sub(c,c,b); 1215 if(!BN_is_zero(c) && !BN_abs_is_word(c, 1)) 1216 { 1217 fprintf(stderr,"Right shift one test failed!\n"); 1218 return 0; 1219 } 1220 BN_copy(a,b); 1221 } 1222 BN_free(a); 1223 BN_free(b); 1224 BN_free(c); 1225 return(1); 1226 } 1227 1228int rand_neg(void) 1229 { 1230 static unsigned int neg=0; 1231 static int sign[8]={0,0,0,1,1,0,1,1}; 1232 1233 return(sign[(neg++)%8]); 1234 } 1235