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