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