1/* 2 * Copyright 1995-2022 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the Apache License 2.0 (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9#include <assert.h> 10#include <errno.h> 11#include <stdio.h> 12#include <string.h> 13#include <ctype.h> 14 15#include <openssl/bn.h> 16#include <openssl/crypto.h> 17#include <openssl/err.h> 18#include <openssl/rand.h> 19#include "internal/nelem.h" 20#include "internal/numbers.h" 21#include "testutil.h" 22 23/* 24 * Things in boring, not in openssl. 25 */ 26#define HAVE_BN_SQRT 0 27 28typedef struct filetest_st { 29 const char *name; 30 int (*func)(STANZA *s); 31} FILETEST; 32 33typedef struct mpitest_st { 34 const char *base10; 35 const char *mpi; 36 size_t mpi_len; 37} MPITEST; 38 39static const int NUM0 = 100; /* number of tests */ 40static const int NUM1 = 50; /* additional tests for some functions */ 41static BN_CTX *ctx; 42 43/* 44 * Polynomial coefficients used in GFM tests. 45 */ 46#ifndef OPENSSL_NO_EC2M 47static int p0[] = { 163, 7, 6, 3, 0, -1 }; 48static int p1[] = { 193, 15, 0, -1 }; 49#endif 50 51/* 52 * Look for |key| in the stanza and return it or NULL if not found. 53 */ 54static const char *findattr(STANZA *s, const char *key) 55{ 56 int i = s->numpairs; 57 PAIR *pp = s->pairs; 58 59 for ( ; --i >= 0; pp++) 60 if (OPENSSL_strcasecmp(pp->key, key) == 0) 61 return pp->value; 62 return NULL; 63} 64 65/* 66 * Parse BIGNUM from sparse hex-strings, return |BN_hex2bn| result. 67 */ 68static int parse_bigBN(BIGNUM **out, const char *bn_strings[]) 69{ 70 char *bigstring = glue_strings(bn_strings, NULL); 71 int ret = BN_hex2bn(out, bigstring); 72 73 OPENSSL_free(bigstring); 74 return ret; 75} 76 77/* 78 * Parse BIGNUM, return number of bytes parsed. 79 */ 80static int parseBN(BIGNUM **out, const char *in) 81{ 82 *out = NULL; 83 return BN_hex2bn(out, in); 84} 85 86static int parsedecBN(BIGNUM **out, const char *in) 87{ 88 *out = NULL; 89 return BN_dec2bn(out, in); 90} 91 92static BIGNUM *getBN(STANZA *s, const char *attribute) 93{ 94 const char *hex; 95 BIGNUM *ret = NULL; 96 97 if ((hex = findattr(s, attribute)) == NULL) { 98 TEST_error("%s:%d: Can't find %s", s->test_file, s->start, attribute); 99 return NULL; 100 } 101 102 if (parseBN(&ret, hex) != (int)strlen(hex)) { 103 TEST_error("Could not decode '%s'", hex); 104 return NULL; 105 } 106 return ret; 107} 108 109static int getint(STANZA *s, int *out, const char *attribute) 110{ 111 BIGNUM *ret; 112 BN_ULONG word; 113 int st = 0; 114 115 if (!TEST_ptr(ret = getBN(s, attribute)) 116 || !TEST_ulong_le(word = BN_get_word(ret), INT_MAX)) 117 goto err; 118 119 *out = (int)word; 120 st = 1; 121 err: 122 BN_free(ret); 123 return st; 124} 125 126static int equalBN(const char *op, const BIGNUM *expected, const BIGNUM *actual) 127{ 128 if (BN_cmp(expected, actual) == 0) 129 return 1; 130 131 TEST_error("unexpected %s value", op); 132 TEST_BN_eq(expected, actual); 133 return 0; 134} 135 136/* 137 * Return a "random" flag for if a BN should be negated. 138 */ 139static int rand_neg(void) 140{ 141 static unsigned int neg = 0; 142 static int sign[8] = { 0, 0, 0, 1, 1, 0, 1, 1 }; 143 144 return sign[(neg++) % 8]; 145} 146 147static int test_swap(void) 148{ 149 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL; 150 int top, cond, st = 0; 151 152 if (!TEST_ptr(a = BN_new()) 153 || !TEST_ptr(b = BN_new()) 154 || !TEST_ptr(c = BN_new()) 155 || !TEST_ptr(d = BN_new())) 156 goto err; 157 158 if (!(TEST_true(BN_bntest_rand(a, 1024, 1, 0)) 159 && TEST_true(BN_bntest_rand(b, 1024, 1, 0)) 160 && TEST_ptr(BN_copy(c, a)) 161 && TEST_ptr(BN_copy(d, b)))) 162 goto err; 163 top = BN_num_bits(a) / BN_BITS2; 164 165 /* regular swap */ 166 BN_swap(a, b); 167 if (!equalBN("swap", a, d) 168 || !equalBN("swap", b, c)) 169 goto err; 170 171 /* conditional swap: true */ 172 cond = 1; 173 BN_consttime_swap(cond, a, b, top); 174 if (!equalBN("cswap true", a, c) 175 || !equalBN("cswap true", b, d)) 176 goto err; 177 178 /* conditional swap: false */ 179 cond = 0; 180 BN_consttime_swap(cond, a, b, top); 181 if (!equalBN("cswap false", a, c) 182 || !equalBN("cswap false", b, d)) 183 goto err; 184 185 /* same tests but checking flag swap */ 186 BN_set_flags(a, BN_FLG_CONSTTIME); 187 188 BN_swap(a, b); 189 if (!equalBN("swap, flags", a, d) 190 || !equalBN("swap, flags", b, c) 191 || !TEST_true(BN_get_flags(b, BN_FLG_CONSTTIME)) 192 || !TEST_false(BN_get_flags(a, BN_FLG_CONSTTIME))) 193 goto err; 194 195 cond = 1; 196 BN_consttime_swap(cond, a, b, top); 197 if (!equalBN("cswap true, flags", a, c) 198 || !equalBN("cswap true, flags", b, d) 199 || !TEST_true(BN_get_flags(a, BN_FLG_CONSTTIME)) 200 || !TEST_false(BN_get_flags(b, BN_FLG_CONSTTIME))) 201 goto err; 202 203 cond = 0; 204 BN_consttime_swap(cond, a, b, top); 205 if (!equalBN("cswap false, flags", a, c) 206 || !equalBN("cswap false, flags", b, d) 207 || !TEST_true(BN_get_flags(a, BN_FLG_CONSTTIME)) 208 || !TEST_false(BN_get_flags(b, BN_FLG_CONSTTIME))) 209 goto err; 210 211 st = 1; 212 err: 213 BN_free(a); 214 BN_free(b); 215 BN_free(c); 216 BN_free(d); 217 return st; 218} 219 220static int test_sub(void) 221{ 222 BIGNUM *a = NULL, *b = NULL, *c = NULL; 223 int i, st = 0; 224 225 if (!TEST_ptr(a = BN_new()) 226 || !TEST_ptr(b = BN_new()) 227 || !TEST_ptr(c = BN_new())) 228 goto err; 229 230 for (i = 0; i < NUM0 + NUM1; i++) { 231 if (i < NUM1) { 232 if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0))) 233 && TEST_ptr(BN_copy(b, a)) 234 && TEST_int_ne(BN_set_bit(a, i), 0) 235 && TEST_true(BN_add_word(b, i))) 236 goto err; 237 } else { 238 if (!TEST_true(BN_bntest_rand(b, 400 + i - NUM1, 0, 0))) 239 goto err; 240 BN_set_negative(a, rand_neg()); 241 BN_set_negative(b, rand_neg()); 242 } 243 if (!(TEST_true(BN_sub(c, a, b)) 244 && TEST_true(BN_add(c, c, b)) 245 && TEST_true(BN_sub(c, c, a)) 246 && TEST_BN_eq_zero(c))) 247 goto err; 248 } 249 st = 1; 250 err: 251 BN_free(a); 252 BN_free(b); 253 BN_free(c); 254 return st; 255} 256 257static int test_div_recip(void) 258{ 259 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL; 260 BN_RECP_CTX *recp = NULL; 261 int st = 0, i; 262 263 if (!TEST_ptr(a = BN_new()) 264 || !TEST_ptr(b = BN_new()) 265 || !TEST_ptr(c = BN_new()) 266 || !TEST_ptr(d = BN_new()) 267 || !TEST_ptr(e = BN_new()) 268 || !TEST_ptr(recp = BN_RECP_CTX_new())) 269 goto err; 270 271 for (i = 0; i < NUM0 + NUM1; i++) { 272 if (i < NUM1) { 273 if (!(TEST_true(BN_bntest_rand(a, 400, 0, 0)) 274 && TEST_ptr(BN_copy(b, a)) 275 && TEST_true(BN_lshift(a, a, i)) 276 && TEST_true(BN_add_word(a, i)))) 277 goto err; 278 } else { 279 if (!(TEST_true(BN_bntest_rand(b, 50 + 3 * (i - NUM1), 0, 0)))) 280 goto err; 281 } 282 BN_set_negative(a, rand_neg()); 283 BN_set_negative(b, rand_neg()); 284 if (!(TEST_true(BN_RECP_CTX_set(recp, b, ctx)) 285 && TEST_true(BN_div_recp(d, c, a, recp, ctx)) 286 && TEST_true(BN_mul(e, d, b, ctx)) 287 && TEST_true(BN_add(d, e, c)) 288 && TEST_true(BN_sub(d, d, a)) 289 && TEST_BN_eq_zero(d))) 290 goto err; 291 } 292 st = 1; 293 err: 294 BN_free(a); 295 BN_free(b); 296 BN_free(c); 297 BN_free(d); 298 BN_free(e); 299 BN_RECP_CTX_free(recp); 300 return st; 301} 302 303static struct { 304 int n, divisor, result, remainder; 305} signed_mod_tests[] = { 306 { 10, 3, 3, 1 }, 307 { -10, 3, -3, -1 }, 308 { 10, -3, -3, 1 }, 309 { -10, -3, 3, -1 }, 310}; 311 312static BIGNUM *set_signed_bn(int value) 313{ 314 BIGNUM *bn = BN_new(); 315 316 if (bn == NULL) 317 return NULL; 318 if (!BN_set_word(bn, value < 0 ? -value : value)) { 319 BN_free(bn); 320 return NULL; 321 } 322 BN_set_negative(bn, value < 0); 323 return bn; 324} 325 326static int test_signed_mod_replace_ab(int n) 327{ 328 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL; 329 int st = 0; 330 331 if (!TEST_ptr(a = set_signed_bn(signed_mod_tests[n].n)) 332 || !TEST_ptr(b = set_signed_bn(signed_mod_tests[n].divisor)) 333 || !TEST_ptr(c = set_signed_bn(signed_mod_tests[n].result)) 334 || !TEST_ptr(d = set_signed_bn(signed_mod_tests[n].remainder))) 335 goto err; 336 337 if (TEST_true(BN_div(a, b, a, b, ctx)) 338 && TEST_BN_eq(a, c) 339 && TEST_BN_eq(b, d)) 340 st = 1; 341 err: 342 BN_free(a); 343 BN_free(b); 344 BN_free(c); 345 BN_free(d); 346 return st; 347} 348 349static int test_signed_mod_replace_ba(int n) 350{ 351 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL; 352 int st = 0; 353 354 if (!TEST_ptr(a = set_signed_bn(signed_mod_tests[n].n)) 355 || !TEST_ptr(b = set_signed_bn(signed_mod_tests[n].divisor)) 356 || !TEST_ptr(c = set_signed_bn(signed_mod_tests[n].result)) 357 || !TEST_ptr(d = set_signed_bn(signed_mod_tests[n].remainder))) 358 goto err; 359 360 if (TEST_true(BN_div(b, a, a, b, ctx)) 361 && TEST_BN_eq(b, c) 362 && TEST_BN_eq(a, d)) 363 st = 1; 364 err: 365 BN_free(a); 366 BN_free(b); 367 BN_free(c); 368 BN_free(d); 369 return st; 370} 371 372static int test_mod(void) 373{ 374 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL; 375 int st = 0, i; 376 377 if (!TEST_ptr(a = BN_new()) 378 || !TEST_ptr(b = BN_new()) 379 || !TEST_ptr(c = BN_new()) 380 || !TEST_ptr(d = BN_new()) 381 || !TEST_ptr(e = BN_new())) 382 goto err; 383 384 if (!(TEST_true(BN_bntest_rand(a, 1024, 0, 0)))) 385 goto err; 386 for (i = 0; i < NUM0; i++) { 387 if (!(TEST_true(BN_bntest_rand(b, 450 + i * 10, 0, 0)))) 388 goto err; 389 BN_set_negative(a, rand_neg()); 390 BN_set_negative(b, rand_neg()); 391 if (!(TEST_true(BN_mod(c, a, b, ctx)) 392 && TEST_true(BN_div(d, e, a, b, ctx)) 393 && TEST_BN_eq(e, c) 394 && TEST_true(BN_mul(c, d, b, ctx)) 395 && TEST_true(BN_add(d, c, e)) 396 && TEST_BN_eq(d, a))) 397 goto err; 398 } 399 st = 1; 400 err: 401 BN_free(a); 402 BN_free(b); 403 BN_free(c); 404 BN_free(d); 405 BN_free(e); 406 return st; 407} 408 409static const char *bn1strings[] = { 410 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 411 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 412 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 413 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 414 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 415 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 416 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 417 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF00", 418 "0000000000000000000000000000000000000000000000000000000000000000", 419 "0000000000000000000000000000000000000000000000000000000000000000", 420 "0000000000000000000000000000000000000000000000000000000000000000", 421 "0000000000000000000000000000000000000000000000000000000000000000", 422 "0000000000000000000000000000000000000000000000000000000000000000", 423 "0000000000000000000000000000000000000000000000000000000000000000", 424 "0000000000000000000000000000000000000000000000000000000000000000", 425 "00000000000000000000000000000000000000000000000000FFFFFFFFFFFFFF", 426 NULL 427}; 428 429static const char *bn2strings[] = { 430 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 431 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 432 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 433 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 434 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 435 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 436 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 437 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000000000FFFFFFFF0000000000", 438 "0000000000000000000000000000000000000000000000000000000000000000", 439 "0000000000000000000000000000000000000000000000000000000000000000", 440 "0000000000000000000000000000000000000000000000000000000000000000", 441 "0000000000000000000000000000000000000000000000000000000000000000", 442 "0000000000000000000000000000000000000000000000000000000000000000", 443 "0000000000000000000000000000000000000000000000000000000000000000", 444 "0000000000000000000000000000000000000000000000000000000000000000", 445 "000000000000000000000000000000000000000000FFFFFFFFFFFFFF00000000", 446 NULL 447}; 448 449/* 450 * Test constant-time modular exponentiation with 1024-bit inputs, which on 451 * x86_64 cause a different code branch to be taken. 452 */ 453static int test_modexp_mont5(void) 454{ 455 BIGNUM *a = NULL, *p = NULL, *m = NULL, *d = NULL, *e = NULL; 456 BIGNUM *b = NULL, *n = NULL, *c = NULL; 457 BN_MONT_CTX *mont = NULL; 458 int st = 0; 459 460 if (!TEST_ptr(a = BN_new()) 461 || !TEST_ptr(p = BN_new()) 462 || !TEST_ptr(m = BN_new()) 463 || !TEST_ptr(d = BN_new()) 464 || !TEST_ptr(e = BN_new()) 465 || !TEST_ptr(b = BN_new()) 466 || !TEST_ptr(n = BN_new()) 467 || !TEST_ptr(c = BN_new()) 468 || !TEST_ptr(mont = BN_MONT_CTX_new())) 469 goto err; 470 471 /* must be odd for montgomery */ 472 if (!(TEST_true(BN_bntest_rand(m, 1024, 0, 1)) 473 /* Zero exponent */ 474 && TEST_true(BN_bntest_rand(a, 1024, 0, 0)))) 475 goto err; 476 BN_zero(p); 477 478 if (!TEST_true(BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL))) 479 goto err; 480 if (!TEST_BN_eq_one(d)) 481 goto err; 482 483 /* Regression test for carry bug in mulx4x_mont */ 484 if (!(TEST_true(BN_hex2bn(&a, 485 "7878787878787878787878787878787878787878787878787878787878787878" 486 "7878787878787878787878787878787878787878787878787878787878787878" 487 "7878787878787878787878787878787878787878787878787878787878787878" 488 "7878787878787878787878787878787878787878787878787878787878787878")) 489 && TEST_true(BN_hex2bn(&b, 490 "095D72C08C097BA488C5E439C655A192EAFB6380073D8C2664668EDDB4060744" 491 "E16E57FB4EDB9AE10A0CEFCDC28A894F689A128379DB279D48A2E20849D68593" 492 "9B7803BCF46CEBF5C533FB0DD35B080593DE5472E3FE5DB951B8BFF9B4CB8F03" 493 "9CC638A5EE8CDD703719F8000E6A9F63BEED5F2FCD52FF293EA05A251BB4AB81")) 494 && TEST_true(BN_hex2bn(&n, 495 "D78AF684E71DB0C39CFF4E64FB9DB567132CB9C50CC98009FEB820B26F2DED9B" 496 "91B9B5E2B83AE0AE4EB4E0523CA726BFBE969B89FD754F674CE99118C3F2D1C5" 497 "D81FDC7C54E02B60262B241D53C040E99E45826ECA37A804668E690E1AFC1CA4" 498 "2C9A15D84D4954425F0B7642FC0BD9D7B24E2618D2DCC9B729D944BADACFDDAF")))) 499 goto err; 500 501 if (!(TEST_true(BN_MONT_CTX_set(mont, n, ctx)) 502 && TEST_true(BN_mod_mul_montgomery(c, a, b, mont, ctx)) 503 && TEST_true(BN_mod_mul_montgomery(d, b, a, mont, ctx)) 504 && TEST_BN_eq(c, d))) 505 goto err; 506 507 /* Regression test for carry bug in sqr[x]8x_mont */ 508 if (!(TEST_true(parse_bigBN(&n, bn1strings)) 509 && TEST_true(parse_bigBN(&a, bn2strings)))) 510 goto err; 511 BN_free(b); 512 if (!(TEST_ptr(b = BN_dup(a)) 513 && TEST_true(BN_MONT_CTX_set(mont, n, ctx)) 514 && TEST_true(BN_mod_mul_montgomery(c, a, a, mont, ctx)) 515 && TEST_true(BN_mod_mul_montgomery(d, a, b, mont, ctx)) 516 && TEST_BN_eq(c, d))) 517 goto err; 518 519 /* Regression test for carry bug in bn_sqrx8x_internal */ 520 { 521 static const char *ahex[] = { 522 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 523 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 524 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 525 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 526 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8FFEADBCFC4DAE7FFF908E92820306B", 527 "9544D954000000006C0000000000000000000000000000000000000000000000", 528 "00000000000000000000FF030202FFFFF8FFEBDBCFC4DAE7FFF908E92820306B", 529 "9544D954000000006C000000FF0302030000000000FFFFFFFFFFFFFFFFFFFFFF", 530 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF01FC00FF02FFFFFFFF", 531 "00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00FCFD", 532 "FCFFFFFFFFFF000000000000000000FF0302030000000000FFFFFFFFFFFFFFFF", 533 "FF00FCFDFDFF030202FF00000000FFFFFFFFFFFFFFFFFF00FCFDFCFFFFFFFFFF", 534 NULL 535 }; 536 static const char *nhex[] = { 537 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 538 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 539 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 540 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 541 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8F8F8F8000000", 542 "00000010000000006C0000000000000000000000000000000000000000000000", 543 "00000000000000000000000000000000000000FFFFFFFFFFFFF8F8F8F8000000", 544 "00000010000000006C000000000000000000000000FFFFFFFFFFFFFFFFFFFFFF", 545 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 546 "00FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 547 "FFFFFFFFFFFF000000000000000000000000000000000000FFFFFFFFFFFFFFFF", 548 "FFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", 549 NULL 550 }; 551 552 if (!(TEST_true(parse_bigBN(&a, ahex)) 553 && TEST_true(parse_bigBN(&n, nhex)))) 554 goto err; 555 } 556 BN_free(b); 557 if (!(TEST_ptr(b = BN_dup(a)) 558 && TEST_true(BN_MONT_CTX_set(mont, n, ctx)))) 559 goto err; 560 561 if (!TEST_true(BN_mod_mul_montgomery(c, a, a, mont, ctx)) 562 || !TEST_true(BN_mod_mul_montgomery(d, a, b, mont, ctx)) 563 || !TEST_BN_eq(c, d)) 564 goto err; 565 566 /* Regression test for bug in BN_from_montgomery_word */ 567 if (!(TEST_true(BN_hex2bn(&a, 568 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 569 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 570 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF")) 571 && TEST_true(BN_hex2bn(&n, 572 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 573 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF")) 574 && TEST_true(BN_MONT_CTX_set(mont, n, ctx)) 575 && TEST_false(BN_mod_mul_montgomery(d, a, a, mont, ctx)))) 576 goto err; 577 578 /* Regression test for bug in rsaz_1024_mul_avx2 */ 579 if (!(TEST_true(BN_hex2bn(&a, 580 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 581 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 582 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 583 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF")) 584 && TEST_true(BN_hex2bn(&b, 585 "2020202020202020202020202020202020202020202020202020202020202020" 586 "2020202020202020202020202020202020202020202020202020202020202020" 587 "20202020202020FF202020202020202020202020202020202020202020202020" 588 "2020202020202020202020202020202020202020202020202020202020202020")) 589 && TEST_true(BN_hex2bn(&n, 590 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 591 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 592 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 593 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020FF")) 594 && TEST_true(BN_MONT_CTX_set(mont, n, ctx)) 595 && TEST_true(BN_mod_exp_mont_consttime(c, a, b, n, ctx, mont)) 596 && TEST_true(BN_mod_exp_mont(d, a, b, n, ctx, mont)) 597 && TEST_BN_eq(c, d))) 598 goto err; 599 600 /* 601 * rsaz_1024_mul_avx2 expects fully-reduced inputs. 602 * BN_mod_exp_mont_consttime should reduce the input first. 603 */ 604 if (!(TEST_true(BN_hex2bn(&a, 605 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 606 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 607 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 608 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF")) 609 && TEST_true(BN_hex2bn(&b, 610 "1FA53F26F8811C58BE0357897AA5E165693230BC9DF5F01DFA6A2D59229EC69D" 611 "9DE6A89C36E3B6957B22D6FAAD5A3C73AE587B710DBE92E83D3A9A3339A085CB" 612 "B58F508CA4F837924BB52CC1698B7FDC2FD74362456A595A5B58E38E38E38E38" 613 "E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E38E")) 614 && TEST_true(BN_hex2bn(&n, 615 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 616 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 617 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" 618 "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2020202020DF")) 619 && TEST_true(BN_MONT_CTX_set(mont, n, ctx)) 620 && TEST_true(BN_mod_exp_mont_consttime(c, a, b, n, ctx, mont)))) 621 goto err; 622 BN_zero(d); 623 if (!TEST_BN_eq(c, d)) 624 goto err; 625 626 /* 627 * Regression test for overflow bug in bn_sqr_comba4/8 for 628 * mips-linux-gnu and mipsel-linux-gnu 32bit targets. 629 */ 630 { 631 static const char *ehex[] = { 632 "95564994a96c45954227b845a1e99cb939d5a1da99ee91acc962396ae999a9ee", 633 "38603790448f2f7694c242a875f0cad0aae658eba085f312d2febbbd128dd2b5", 634 "8f7d1149f03724215d704344d0d62c587ae3c5939cba4b9b5f3dc5e8e911ef9a", 635 "5ce1a5a749a4989d0d8368f6e1f8cdf3a362a6c97fb02047ff152b480a4ad985", 636 "2d45efdf0770542992afca6a0590d52930434bba96017afbc9f99e112950a8b1", 637 "a359473ec376f329bdae6a19f503be6d4be7393c4e43468831234e27e3838680", 638 "b949390d2e416a3f9759e5349ab4c253f6f29f819a6fe4cbfd27ada34903300e", 639 "da021f62839f5878a36f1bc3085375b00fd5fa3e68d316c0fdace87a97558465", 640 NULL}; 641 static const char *phex[] = { 642 "f95dc0f980fbd22e90caa5a387cc4a369f3f830d50dd321c40db8c09a7e1a241", 643 "a536e096622d3280c0c1ba849c1f4a79bf490f60006d081e8cf69960189f0d31", 644 "2cd9e17073a3fba7881b21474a13b334116cb2f5dbf3189a6de3515d0840f053", 645 "c776d3982d391b6d04d642dda5cc6d1640174c09875addb70595658f89efb439", 646 "dc6fbd55f903aadd307982d3f659207f265e1ec6271b274521b7a5e28e8fd7a5", 647 "5df089292820477802a43cf5b6b94e999e8c9944ddebb0d0e95a60f88cb7e813", 648 "ba110d20e1024774107dd02949031864923b3cb8c3f7250d6d1287b0a40db6a4", 649 "7bd5a469518eb65aa207ddc47d8c6e5fc8e0c105be8fc1d4b57b2e27540471d5", 650 NULL}; 651 static const char *mhex[] = { 652 "fef15d5ce4625f1bccfbba49fc8439c72bf8202af039a2259678941b60bb4a8f", 653 "2987e965d58fd8cf86a856674d519763d0e1211cc9f8596971050d56d9b35db3", 654 "785866cfbca17cfdbed6060be3629d894f924a89fdc1efc624f80d41a22f1900", 655 "9503fcc3824ef62ccb9208430c26f2d8ceb2c63488ec4c07437aa4c96c43dd8b", 656 "9289ed00a712ff66ee195dc71f5e4ead02172b63c543d69baf495f5fd63ba7bc", 657 "c633bd309c016e37736da92129d0b053d4ab28d21ad7d8b6fab2a8bbdc8ee647", 658 "d2fbcf2cf426cf892e6f5639e0252993965dfb73ccd277407014ea784aaa280c", 659 "b7b03972bc8b0baa72360bdb44b82415b86b2f260f877791cd33ba8f2d65229b", 660 NULL}; 661 662 if (!TEST_true(parse_bigBN(&e, ehex)) 663 || !TEST_true(parse_bigBN(&p, phex)) 664 || !TEST_true(parse_bigBN(&m, mhex)) 665 || !TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL)) 666 || !TEST_true(BN_mod_exp_simple(a, e, p, m, ctx)) 667 || !TEST_BN_eq(a, d)) 668 goto err; 669 } 670 671 /* Zero input */ 672 if (!TEST_true(BN_bntest_rand(p, 1024, 0, 0))) 673 goto err; 674 BN_zero(a); 675 if (!TEST_true(BN_mod_exp_mont_consttime(d, a, p, m, ctx, NULL)) 676 || !TEST_BN_eq_zero(d)) 677 goto err; 678 679 /* 680 * Craft an input whose Montgomery representation is 1, i.e., shorter 681 * than the modulus m, in order to test the const time precomputation 682 * scattering/gathering. 683 */ 684 if (!(TEST_true(BN_one(a)) 685 && TEST_true(BN_MONT_CTX_set(mont, m, ctx)))) 686 goto err; 687 if (!TEST_true(BN_from_montgomery(e, a, mont, ctx)) 688 || !TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL)) 689 || !TEST_true(BN_mod_exp_simple(a, e, p, m, ctx)) 690 || !TEST_BN_eq(a, d)) 691 goto err; 692 693 /* Finally, some regular test vectors. */ 694 if (!(TEST_true(BN_bntest_rand(e, 1024, 0, 0)) 695 && TEST_true(BN_mod_exp_mont_consttime(d, e, p, m, ctx, NULL)) 696 && TEST_true(BN_mod_exp_simple(a, e, p, m, ctx)) 697 && TEST_BN_eq(a, d))) 698 goto err; 699 700 st = 1; 701 702 err: 703 BN_MONT_CTX_free(mont); 704 BN_free(a); 705 BN_free(p); 706 BN_free(m); 707 BN_free(d); 708 BN_free(e); 709 BN_free(b); 710 BN_free(n); 711 BN_free(c); 712 return st; 713} 714 715#ifndef OPENSSL_NO_EC2M 716static int test_gf2m_add(void) 717{ 718 BIGNUM *a = NULL, *b = NULL, *c = NULL; 719 int i, st = 0; 720 721 if (!TEST_ptr(a = BN_new()) 722 || !TEST_ptr(b = BN_new()) 723 || !TEST_ptr(c = BN_new())) 724 goto err; 725 726 for (i = 0; i < NUM0; i++) { 727 if (!(TEST_true(BN_rand(a, 512, 0, 0)) 728 && TEST_ptr(BN_copy(b, BN_value_one())))) 729 goto err; 730 BN_set_negative(a, rand_neg()); 731 BN_set_negative(b, rand_neg()); 732 if (!(TEST_true(BN_GF2m_add(c, a, b)) 733 /* Test that two added values have the correct parity. */ 734 && TEST_false((BN_is_odd(a) && BN_is_odd(c)) 735 || (!BN_is_odd(a) && !BN_is_odd(c))))) 736 goto err; 737 if (!(TEST_true(BN_GF2m_add(c, c, c)) 738 /* Test that c + c = 0. */ 739 && TEST_BN_eq_zero(c))) 740 goto err; 741 } 742 st = 1; 743 err: 744 BN_free(a); 745 BN_free(b); 746 BN_free(c); 747 return st; 748} 749 750static int test_gf2m_mod(void) 751{ 752 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL, *e = NULL; 753 int i, j, st = 0; 754 755 if (!TEST_ptr(a = BN_new()) 756 || !TEST_ptr(b[0] = BN_new()) 757 || !TEST_ptr(b[1] = BN_new()) 758 || !TEST_ptr(c = BN_new()) 759 || !TEST_ptr(d = BN_new()) 760 || !TEST_ptr(e = BN_new())) 761 goto err; 762 763 if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0])) 764 && TEST_true(BN_GF2m_arr2poly(p1, b[1])))) 765 goto err; 766 767 for (i = 0; i < NUM0; i++) { 768 if (!TEST_true(BN_bntest_rand(a, 1024, 0, 0))) 769 goto err; 770 for (j = 0; j < 2; j++) { 771 if (!(TEST_true(BN_GF2m_mod(c, a, b[j])) 772 && TEST_true(BN_GF2m_add(d, a, c)) 773 && TEST_true(BN_GF2m_mod(e, d, b[j])) 774 /* Test that a + (a mod p) mod p == 0. */ 775 && TEST_BN_eq_zero(e))) 776 goto err; 777 } 778 } 779 st = 1; 780 err: 781 BN_free(a); 782 BN_free(b[0]); 783 BN_free(b[1]); 784 BN_free(c); 785 BN_free(d); 786 BN_free(e); 787 return st; 788} 789 790static int test_gf2m_mul(void) 791{ 792 BIGNUM *a, *b[2] = {NULL, NULL}, *c = NULL, *d = NULL; 793 BIGNUM *e = NULL, *f = NULL, *g = NULL, *h = NULL; 794 int i, j, st = 0; 795 796 if (!TEST_ptr(a = BN_new()) 797 || !TEST_ptr(b[0] = BN_new()) 798 || !TEST_ptr(b[1] = BN_new()) 799 || !TEST_ptr(c = BN_new()) 800 || !TEST_ptr(d = BN_new()) 801 || !TEST_ptr(e = BN_new()) 802 || !TEST_ptr(f = BN_new()) 803 || !TEST_ptr(g = BN_new()) 804 || !TEST_ptr(h = BN_new())) 805 goto err; 806 807 if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0])) 808 && TEST_true(BN_GF2m_arr2poly(p1, b[1])))) 809 goto err; 810 811 for (i = 0; i < NUM0; i++) { 812 if (!(TEST_true(BN_bntest_rand(a, 1024, 0, 0)) 813 && TEST_true(BN_bntest_rand(c, 1024, 0, 0)) 814 && TEST_true(BN_bntest_rand(d, 1024, 0, 0)))) 815 goto err; 816 for (j = 0; j < 2; j++) { 817 if (!(TEST_true(BN_GF2m_mod_mul(e, a, c, b[j], ctx)) 818 && TEST_true(BN_GF2m_add(f, a, d)) 819 && TEST_true(BN_GF2m_mod_mul(g, f, c, b[j], ctx)) 820 && TEST_true(BN_GF2m_mod_mul(h, d, c, b[j], ctx)) 821 && TEST_true(BN_GF2m_add(f, e, g)) 822 && TEST_true(BN_GF2m_add(f, f, h)) 823 /* Test that (a+d)*c = a*c + d*c. */ 824 && TEST_BN_eq_zero(f))) 825 goto err; 826 } 827 } 828 st = 1; 829 830 err: 831 BN_free(a); 832 BN_free(b[0]); 833 BN_free(b[1]); 834 BN_free(c); 835 BN_free(d); 836 BN_free(e); 837 BN_free(f); 838 BN_free(g); 839 BN_free(h); 840 return st; 841} 842 843static int test_gf2m_sqr(void) 844{ 845 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL; 846 int i, j, st = 0; 847 848 if (!TEST_ptr(a = BN_new()) 849 || !TEST_ptr(b[0] = BN_new()) 850 || !TEST_ptr(b[1] = BN_new()) 851 || !TEST_ptr(c = BN_new()) 852 || !TEST_ptr(d = BN_new())) 853 goto err; 854 855 if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0])) 856 && TEST_true(BN_GF2m_arr2poly(p1, b[1])))) 857 goto err; 858 859 for (i = 0; i < NUM0; i++) { 860 if (!TEST_true(BN_bntest_rand(a, 1024, 0, 0))) 861 goto err; 862 for (j = 0; j < 2; j++) { 863 if (!(TEST_true(BN_GF2m_mod_sqr(c, a, b[j], ctx)) 864 && TEST_true(BN_copy(d, a)) 865 && TEST_true(BN_GF2m_mod_mul(d, a, d, b[j], ctx)) 866 && TEST_true(BN_GF2m_add(d, c, d)) 867 /* Test that a*a = a^2. */ 868 && TEST_BN_eq_zero(d))) 869 goto err; 870 } 871 } 872 st = 1; 873 err: 874 BN_free(a); 875 BN_free(b[0]); 876 BN_free(b[1]); 877 BN_free(c); 878 BN_free(d); 879 return st; 880} 881 882static int test_gf2m_modinv(void) 883{ 884 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL; 885 int i, j, st = 0; 886 887 if (!TEST_ptr(a = BN_new()) 888 || !TEST_ptr(b[0] = BN_new()) 889 || !TEST_ptr(b[1] = BN_new()) 890 || !TEST_ptr(c = BN_new()) 891 || !TEST_ptr(d = BN_new())) 892 goto err; 893 894 if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0])) 895 && TEST_true(BN_GF2m_arr2poly(p1, b[1])))) 896 goto err; 897 898 for (i = 0; i < NUM0; i++) { 899 if (!TEST_true(BN_bntest_rand(a, 512, 0, 0))) 900 goto err; 901 for (j = 0; j < 2; j++) { 902 if (!(TEST_true(BN_GF2m_mod_inv(c, a, b[j], ctx)) 903 && TEST_true(BN_GF2m_mod_mul(d, a, c, b[j], ctx)) 904 /* Test that ((1/a)*a) = 1. */ 905 && TEST_BN_eq_one(d))) 906 goto err; 907 } 908 } 909 st = 1; 910 err: 911 BN_free(a); 912 BN_free(b[0]); 913 BN_free(b[1]); 914 BN_free(c); 915 BN_free(d); 916 return st; 917} 918 919static int test_gf2m_moddiv(void) 920{ 921 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL; 922 BIGNUM *e = NULL, *f = NULL; 923 int i, j, st = 0; 924 925 if (!TEST_ptr(a = BN_new()) 926 || !TEST_ptr(b[0] = BN_new()) 927 || !TEST_ptr(b[1] = BN_new()) 928 || !TEST_ptr(c = BN_new()) 929 || !TEST_ptr(d = BN_new()) 930 || !TEST_ptr(e = BN_new()) 931 || !TEST_ptr(f = BN_new())) 932 goto err; 933 934 if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0])) 935 && TEST_true(BN_GF2m_arr2poly(p1, b[1])))) 936 goto err; 937 938 for (i = 0; i < NUM0; i++) { 939 if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0)) 940 && TEST_true(BN_bntest_rand(c, 512, 0, 0)))) 941 goto err; 942 for (j = 0; j < 2; j++) { 943 if (!(TEST_true(BN_GF2m_mod_div(d, a, c, b[j], ctx)) 944 && TEST_true(BN_GF2m_mod_mul(e, d, c, b[j], ctx)) 945 && TEST_true(BN_GF2m_mod_div(f, a, e, b[j], ctx)) 946 /* Test that ((a/c)*c)/a = 1. */ 947 && TEST_BN_eq_one(f))) 948 goto err; 949 } 950 } 951 st = 1; 952 err: 953 BN_free(a); 954 BN_free(b[0]); 955 BN_free(b[1]); 956 BN_free(c); 957 BN_free(d); 958 BN_free(e); 959 BN_free(f); 960 return st; 961} 962 963static int test_gf2m_modexp(void) 964{ 965 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL; 966 BIGNUM *e = NULL, *f = NULL; 967 int i, j, st = 0; 968 969 if (!TEST_ptr(a = BN_new()) 970 || !TEST_ptr(b[0] = BN_new()) 971 || !TEST_ptr(b[1] = BN_new()) 972 || !TEST_ptr(c = BN_new()) 973 || !TEST_ptr(d = BN_new()) 974 || !TEST_ptr(e = BN_new()) 975 || !TEST_ptr(f = BN_new())) 976 goto err; 977 978 if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0])) 979 && TEST_true(BN_GF2m_arr2poly(p1, b[1])))) 980 goto err; 981 982 for (i = 0; i < NUM0; i++) { 983 if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0)) 984 && TEST_true(BN_bntest_rand(c, 512, 0, 0)) 985 && TEST_true(BN_bntest_rand(d, 512, 0, 0)))) 986 goto err; 987 for (j = 0; j < 2; j++) { 988 if (!(TEST_true(BN_GF2m_mod_exp(e, a, c, b[j], ctx)) 989 && TEST_true(BN_GF2m_mod_exp(f, a, d, b[j], ctx)) 990 && TEST_true(BN_GF2m_mod_mul(e, e, f, b[j], ctx)) 991 && TEST_true(BN_add(f, c, d)) 992 && TEST_true(BN_GF2m_mod_exp(f, a, f, b[j], ctx)) 993 && TEST_true(BN_GF2m_add(f, e, f)) 994 /* Test that a^(c+d)=a^c*a^d. */ 995 && TEST_BN_eq_zero(f))) 996 goto err; 997 } 998 } 999 st = 1; 1000 err: 1001 BN_free(a); 1002 BN_free(b[0]); 1003 BN_free(b[1]); 1004 BN_free(c); 1005 BN_free(d); 1006 BN_free(e); 1007 BN_free(f); 1008 return st; 1009} 1010 1011static int test_gf2m_modsqrt(void) 1012{ 1013 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL; 1014 BIGNUM *e = NULL, *f = NULL; 1015 int i, j, st = 0; 1016 1017 if (!TEST_ptr(a = BN_new()) 1018 || !TEST_ptr(b[0] = BN_new()) 1019 || !TEST_ptr(b[1] = BN_new()) 1020 || !TEST_ptr(c = BN_new()) 1021 || !TEST_ptr(d = BN_new()) 1022 || !TEST_ptr(e = BN_new()) 1023 || !TEST_ptr(f = BN_new())) 1024 goto err; 1025 1026 if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0])) 1027 && TEST_true(BN_GF2m_arr2poly(p1, b[1])))) 1028 goto err; 1029 1030 for (i = 0; i < NUM0; i++) { 1031 if (!TEST_true(BN_bntest_rand(a, 512, 0, 0))) 1032 goto err; 1033 1034 for (j = 0; j < 2; j++) { 1035 if (!(TEST_true(BN_GF2m_mod(c, a, b[j])) 1036 && TEST_true(BN_GF2m_mod_sqrt(d, a, b[j], ctx)) 1037 && TEST_true(BN_GF2m_mod_sqr(e, d, b[j], ctx)) 1038 && TEST_true(BN_GF2m_add(f, c, e)) 1039 /* Test that d^2 = a, where d = sqrt(a). */ 1040 && TEST_BN_eq_zero(f))) 1041 goto err; 1042 } 1043 } 1044 st = 1; 1045 err: 1046 BN_free(a); 1047 BN_free(b[0]); 1048 BN_free(b[1]); 1049 BN_free(c); 1050 BN_free(d); 1051 BN_free(e); 1052 BN_free(f); 1053 return st; 1054} 1055 1056static int test_gf2m_modsolvequad(void) 1057{ 1058 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL; 1059 BIGNUM *e = NULL; 1060 int i, j, s = 0, t, st = 0; 1061 1062 if (!TEST_ptr(a = BN_new()) 1063 || !TEST_ptr(b[0] = BN_new()) 1064 || !TEST_ptr(b[1] = BN_new()) 1065 || !TEST_ptr(c = BN_new()) 1066 || !TEST_ptr(d = BN_new()) 1067 || !TEST_ptr(e = BN_new())) 1068 goto err; 1069 1070 if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0])) 1071 && TEST_true(BN_GF2m_arr2poly(p1, b[1])))) 1072 goto err; 1073 1074 for (i = 0; i < NUM0; i++) { 1075 if (!TEST_true(BN_bntest_rand(a, 512, 0, 0))) 1076 goto err; 1077 for (j = 0; j < 2; j++) { 1078 t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx); 1079 if (t) { 1080 s++; 1081 if (!(TEST_true(BN_GF2m_mod_sqr(d, c, b[j], ctx)) 1082 && TEST_true(BN_GF2m_add(d, c, d)) 1083 && TEST_true(BN_GF2m_mod(e, a, b[j])) 1084 && TEST_true(BN_GF2m_add(e, e, d)) 1085 /* 1086 * Test that solution of quadratic c 1087 * satisfies c^2 + c = a. 1088 */ 1089 && TEST_BN_eq_zero(e))) 1090 goto err; 1091 } 1092 } 1093 } 1094 if (!TEST_int_ge(s, 0)) { 1095 TEST_info("%d tests found no roots; probably an error", NUM0); 1096 goto err; 1097 } 1098 st = 1; 1099 err: 1100 BN_free(a); 1101 BN_free(b[0]); 1102 BN_free(b[1]); 1103 BN_free(c); 1104 BN_free(d); 1105 BN_free(e); 1106 return st; 1107} 1108#endif 1109 1110static int test_kronecker(void) 1111{ 1112 BIGNUM *a = NULL, *b = NULL, *r = NULL, *t = NULL; 1113 int i, legendre, kronecker, st = 0; 1114 1115 if (!TEST_ptr(a = BN_new()) 1116 || !TEST_ptr(b = BN_new()) 1117 || !TEST_ptr(r = BN_new()) 1118 || !TEST_ptr(t = BN_new())) 1119 goto err; 1120 1121 /* 1122 * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In 1123 * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is 1124 * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we 1125 * generate a random prime b and compare these values for a number of 1126 * random a's. (That is, we run the Solovay-Strassen primality test to 1127 * confirm that b is prime, except that we don't want to test whether b 1128 * is prime but whether BN_kronecker works.) 1129 */ 1130 1131 if (!TEST_true(BN_generate_prime_ex(b, 512, 0, NULL, NULL, NULL))) 1132 goto err; 1133 BN_set_negative(b, rand_neg()); 1134 1135 for (i = 0; i < NUM0; i++) { 1136 if (!TEST_true(BN_bntest_rand(a, 512, 0, 0))) 1137 goto err; 1138 BN_set_negative(a, rand_neg()); 1139 1140 /* t := (|b|-1)/2 (note that b is odd) */ 1141 if (!TEST_true(BN_copy(t, b))) 1142 goto err; 1143 BN_set_negative(t, 0); 1144 if (!TEST_true(BN_sub_word(t, 1))) 1145 goto err; 1146 if (!TEST_true(BN_rshift1(t, t))) 1147 goto err; 1148 /* r := a^t mod b */ 1149 BN_set_negative(b, 0); 1150 1151 if (!TEST_true(BN_mod_exp_recp(r, a, t, b, ctx))) 1152 goto err; 1153 BN_set_negative(b, 1); 1154 1155 if (BN_is_word(r, 1)) 1156 legendre = 1; 1157 else if (BN_is_zero(r)) 1158 legendre = 0; 1159 else { 1160 if (!TEST_true(BN_add_word(r, 1))) 1161 goto err; 1162 if (!TEST_int_eq(BN_ucmp(r, b), 0)) { 1163 TEST_info("Legendre symbol computation failed"); 1164 goto err; 1165 } 1166 legendre = -1; 1167 } 1168 1169 if (!TEST_int_ge(kronecker = BN_kronecker(a, b, ctx), -1)) 1170 goto err; 1171 /* we actually need BN_kronecker(a, |b|) */ 1172 if (BN_is_negative(a) && BN_is_negative(b)) 1173 kronecker = -kronecker; 1174 1175 if (!TEST_int_eq(legendre, kronecker)) 1176 goto err; 1177 } 1178 1179 st = 1; 1180 err: 1181 BN_free(a); 1182 BN_free(b); 1183 BN_free(r); 1184 BN_free(t); 1185 return st; 1186} 1187 1188static int file_sum(STANZA *s) 1189{ 1190 BIGNUM *a = NULL, *b = NULL, *sum = NULL, *ret = NULL; 1191 BN_ULONG b_word; 1192 int st = 0; 1193 1194 if (!TEST_ptr(a = getBN(s, "A")) 1195 || !TEST_ptr(b = getBN(s, "B")) 1196 || !TEST_ptr(sum = getBN(s, "Sum")) 1197 || !TEST_ptr(ret = BN_new())) 1198 goto err; 1199 1200 if (!TEST_true(BN_add(ret, a, b)) 1201 || !equalBN("A + B", sum, ret) 1202 || !TEST_true(BN_sub(ret, sum, a)) 1203 || !equalBN("Sum - A", b, ret) 1204 || !TEST_true(BN_sub(ret, sum, b)) 1205 || !equalBN("Sum - B", a, ret)) 1206 goto err; 1207 1208 /* 1209 * Test that the functions work when |r| and |a| point to the same BIGNUM, 1210 * or when |r| and |b| point to the same BIGNUM. 1211 * There is no test for all of |r|, |a|, and |b| pointint to the same BIGNUM. 1212 */ 1213 if (!TEST_true(BN_copy(ret, a)) 1214 || !TEST_true(BN_add(ret, ret, b)) 1215 || !equalBN("A + B (r is a)", sum, ret) 1216 || !TEST_true(BN_copy(ret, b)) 1217 || !TEST_true(BN_add(ret, a, ret)) 1218 || !equalBN("A + B (r is b)", sum, ret) 1219 || !TEST_true(BN_copy(ret, sum)) 1220 || !TEST_true(BN_sub(ret, ret, a)) 1221 || !equalBN("Sum - A (r is a)", b, ret) 1222 || !TEST_true(BN_copy(ret, a)) 1223 || !TEST_true(BN_sub(ret, sum, ret)) 1224 || !equalBN("Sum - A (r is b)", b, ret) 1225 || !TEST_true(BN_copy(ret, sum)) 1226 || !TEST_true(BN_sub(ret, ret, b)) 1227 || !equalBN("Sum - B (r is a)", a, ret) 1228 || !TEST_true(BN_copy(ret, b)) 1229 || !TEST_true(BN_sub(ret, sum, ret)) 1230 || !equalBN("Sum - B (r is b)", a, ret)) 1231 goto err; 1232 1233 /* 1234 * Test BN_uadd() and BN_usub() with the prerequisites they are 1235 * documented as having. Note that these functions are frequently used 1236 * when the prerequisites don't hold. In those cases, they are supposed 1237 * to work as if the prerequisite hold, but we don't test that yet. 1238 */ 1239 if (!BN_is_negative(a) && !BN_is_negative(b) && BN_cmp(a, b) >= 0) { 1240 if (!TEST_true(BN_uadd(ret, a, b)) 1241 || !equalBN("A +u B", sum, ret) 1242 || !TEST_true(BN_usub(ret, sum, a)) 1243 || !equalBN("Sum -u A", b, ret) 1244 || !TEST_true(BN_usub(ret, sum, b)) 1245 || !equalBN("Sum -u B", a, ret)) 1246 goto err; 1247 /* 1248 * Test that the functions work when |r| and |a| point to the same 1249 * BIGNUM, or when |r| and |b| point to the same BIGNUM. 1250 * There is no test for all of |r|, |a|, and |b| pointint to the same 1251 * BIGNUM. 1252 */ 1253 if (!TEST_true(BN_copy(ret, a)) 1254 || !TEST_true(BN_uadd(ret, ret, b)) 1255 || !equalBN("A +u B (r is a)", sum, ret) 1256 || !TEST_true(BN_copy(ret, b)) 1257 || !TEST_true(BN_uadd(ret, a, ret)) 1258 || !equalBN("A +u B (r is b)", sum, ret) 1259 || !TEST_true(BN_copy(ret, sum)) 1260 || !TEST_true(BN_usub(ret, ret, a)) 1261 || !equalBN("Sum -u A (r is a)", b, ret) 1262 || !TEST_true(BN_copy(ret, a)) 1263 || !TEST_true(BN_usub(ret, sum, ret)) 1264 || !equalBN("Sum -u A (r is b)", b, ret) 1265 || !TEST_true(BN_copy(ret, sum)) 1266 || !TEST_true(BN_usub(ret, ret, b)) 1267 || !equalBN("Sum -u B (r is a)", a, ret) 1268 || !TEST_true(BN_copy(ret, b)) 1269 || !TEST_true(BN_usub(ret, sum, ret)) 1270 || !equalBN("Sum -u B (r is b)", a, ret)) 1271 goto err; 1272 } 1273 1274 /* 1275 * Test with BN_add_word() and BN_sub_word() if |b| is small enough. 1276 */ 1277 b_word = BN_get_word(b); 1278 if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) { 1279 if (!TEST_true(BN_copy(ret, a)) 1280 || !TEST_true(BN_add_word(ret, b_word)) 1281 || !equalBN("A + B (word)", sum, ret) 1282 || !TEST_true(BN_copy(ret, sum)) 1283 || !TEST_true(BN_sub_word(ret, b_word)) 1284 || !equalBN("Sum - B (word)", a, ret)) 1285 goto err; 1286 } 1287 st = 1; 1288 1289 err: 1290 BN_free(a); 1291 BN_free(b); 1292 BN_free(sum); 1293 BN_free(ret); 1294 return st; 1295} 1296 1297static int file_lshift1(STANZA *s) 1298{ 1299 BIGNUM *a = NULL, *lshift1 = NULL, *zero = NULL, *ret = NULL; 1300 BIGNUM *two = NULL, *remainder = NULL; 1301 int st = 0; 1302 1303 if (!TEST_ptr(a = getBN(s, "A")) 1304 || !TEST_ptr(lshift1 = getBN(s, "LShift1")) 1305 || !TEST_ptr(zero = BN_new()) 1306 || !TEST_ptr(ret = BN_new()) 1307 || !TEST_ptr(two = BN_new()) 1308 || !TEST_ptr(remainder = BN_new())) 1309 goto err; 1310 1311 BN_zero(zero); 1312 1313 if (!TEST_true(BN_set_word(two, 2)) 1314 || !TEST_true(BN_add(ret, a, a)) 1315 || !equalBN("A + A", lshift1, ret) 1316 || !TEST_true(BN_mul(ret, a, two, ctx)) 1317 || !equalBN("A * 2", lshift1, ret) 1318 || !TEST_true(BN_div(ret, remainder, lshift1, two, ctx)) 1319 || !equalBN("LShift1 / 2", a, ret) 1320 || !equalBN("LShift1 % 2", zero, remainder) 1321 || !TEST_true(BN_lshift1(ret, a)) 1322 || !equalBN("A << 1", lshift1, ret) 1323 || !TEST_true(BN_rshift1(ret, lshift1)) 1324 || !equalBN("LShift >> 1", a, ret) 1325 || !TEST_true(BN_rshift1(ret, lshift1)) 1326 || !equalBN("LShift >> 1", a, ret)) 1327 goto err; 1328 1329 /* Set the LSB to 1 and test rshift1 again. */ 1330 if (!TEST_true(BN_set_bit(lshift1, 0)) 1331 || !TEST_true(BN_div(ret, NULL /* rem */ , lshift1, two, ctx)) 1332 || !equalBN("(LShift1 | 1) / 2", a, ret) 1333 || !TEST_true(BN_rshift1(ret, lshift1)) 1334 || !equalBN("(LShift | 1) >> 1", a, ret)) 1335 goto err; 1336 1337 st = 1; 1338 err: 1339 BN_free(a); 1340 BN_free(lshift1); 1341 BN_free(zero); 1342 BN_free(ret); 1343 BN_free(two); 1344 BN_free(remainder); 1345 1346 return st; 1347} 1348 1349static int file_lshift(STANZA *s) 1350{ 1351 BIGNUM *a = NULL, *lshift = NULL, *ret = NULL; 1352 int n = 0, st = 0; 1353 1354 if (!TEST_ptr(a = getBN(s, "A")) 1355 || !TEST_ptr(lshift = getBN(s, "LShift")) 1356 || !TEST_ptr(ret = BN_new()) 1357 || !getint(s, &n, "N")) 1358 goto err; 1359 1360 if (!TEST_true(BN_lshift(ret, a, n)) 1361 || !equalBN("A << N", lshift, ret) 1362 || !TEST_true(BN_rshift(ret, lshift, n)) 1363 || !equalBN("A >> N", a, ret)) 1364 goto err; 1365 1366 st = 1; 1367 err: 1368 BN_free(a); 1369 BN_free(lshift); 1370 BN_free(ret); 1371 return st; 1372} 1373 1374static int file_rshift(STANZA *s) 1375{ 1376 BIGNUM *a = NULL, *rshift = NULL, *ret = NULL; 1377 int n = 0, st = 0; 1378 1379 if (!TEST_ptr(a = getBN(s, "A")) 1380 || !TEST_ptr(rshift = getBN(s, "RShift")) 1381 || !TEST_ptr(ret = BN_new()) 1382 || !getint(s, &n, "N")) 1383 goto err; 1384 1385 if (!TEST_true(BN_rshift(ret, a, n)) 1386 || !equalBN("A >> N", rshift, ret)) 1387 goto err; 1388 1389 /* If N == 1, try with rshift1 as well */ 1390 if (n == 1) { 1391 if (!TEST_true(BN_rshift1(ret, a)) 1392 || !equalBN("A >> 1 (rshift1)", rshift, ret)) 1393 goto err; 1394 } 1395 st = 1; 1396 1397 err: 1398 BN_free(a); 1399 BN_free(rshift); 1400 BN_free(ret); 1401 return st; 1402} 1403 1404static int file_square(STANZA *s) 1405{ 1406 BIGNUM *a = NULL, *square = NULL, *zero = NULL, *ret = NULL; 1407 BIGNUM *remainder = NULL, *tmp = NULL; 1408 int st = 0; 1409 1410 if (!TEST_ptr(a = getBN(s, "A")) 1411 || !TEST_ptr(square = getBN(s, "Square")) 1412 || !TEST_ptr(zero = BN_new()) 1413 || !TEST_ptr(ret = BN_new()) 1414 || !TEST_ptr(remainder = BN_new())) 1415 goto err; 1416 1417 BN_zero(zero); 1418 if (!TEST_true(BN_sqr(ret, a, ctx)) 1419 || !equalBN("A^2", square, ret) 1420 || !TEST_true(BN_mul(ret, a, a, ctx)) 1421 || !equalBN("A * A", square, ret) 1422 || !TEST_true(BN_div(ret, remainder, square, a, ctx)) 1423 || !equalBN("Square / A", a, ret) 1424 || !equalBN("Square % A", zero, remainder)) 1425 goto err; 1426 1427#if HAVE_BN_SQRT 1428 BN_set_negative(a, 0); 1429 if (!TEST_true(BN_sqrt(ret, square, ctx)) 1430 || !equalBN("sqrt(Square)", a, ret)) 1431 goto err; 1432 1433 /* BN_sqrt should fail on non-squares and negative numbers. */ 1434 if (!TEST_BN_eq_zero(square)) { 1435 if (!TEST_ptr(tmp = BN_new()) 1436 || !TEST_true(BN_copy(tmp, square))) 1437 goto err; 1438 BN_set_negative(tmp, 1); 1439 1440 if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx), 0)) 1441 goto err; 1442 ERR_clear_error(); 1443 1444 BN_set_negative(tmp, 0); 1445 if (BN_add(tmp, tmp, BN_value_one())) 1446 goto err; 1447 if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx))) 1448 goto err; 1449 ERR_clear_error(); 1450 } 1451#endif 1452 1453 st = 1; 1454 err: 1455 BN_free(a); 1456 BN_free(square); 1457 BN_free(zero); 1458 BN_free(ret); 1459 BN_free(remainder); 1460 BN_free(tmp); 1461 return st; 1462} 1463 1464static int file_product(STANZA *s) 1465{ 1466 BIGNUM *a = NULL, *b = NULL, *product = NULL, *ret = NULL; 1467 BIGNUM *remainder = NULL, *zero = NULL; 1468 int st = 0; 1469 1470 if (!TEST_ptr(a = getBN(s, "A")) 1471 || !TEST_ptr(b = getBN(s, "B")) 1472 || !TEST_ptr(product = getBN(s, "Product")) 1473 || !TEST_ptr(ret = BN_new()) 1474 || !TEST_ptr(remainder = BN_new()) 1475 || !TEST_ptr(zero = BN_new())) 1476 goto err; 1477 1478 BN_zero(zero); 1479 1480 if (!TEST_true(BN_mul(ret, a, b, ctx)) 1481 || !equalBN("A * B", product, ret) 1482 || !TEST_true(BN_div(ret, remainder, product, a, ctx)) 1483 || !equalBN("Product / A", b, ret) 1484 || !equalBN("Product % A", zero, remainder) 1485 || !TEST_true(BN_div(ret, remainder, product, b, ctx)) 1486 || !equalBN("Product / B", a, ret) 1487 || !equalBN("Product % B", zero, remainder)) 1488 goto err; 1489 1490 st = 1; 1491 err: 1492 BN_free(a); 1493 BN_free(b); 1494 BN_free(product); 1495 BN_free(ret); 1496 BN_free(remainder); 1497 BN_free(zero); 1498 return st; 1499} 1500 1501static int file_quotient(STANZA *s) 1502{ 1503 BIGNUM *a = NULL, *b = NULL, *quotient = NULL, *remainder = NULL; 1504 BIGNUM *ret = NULL, *ret2 = NULL, *nnmod = NULL; 1505 BN_ULONG b_word, ret_word; 1506 int st = 0; 1507 1508 if (!TEST_ptr(a = getBN(s, "A")) 1509 || !TEST_ptr(b = getBN(s, "B")) 1510 || !TEST_ptr(quotient = getBN(s, "Quotient")) 1511 || !TEST_ptr(remainder = getBN(s, "Remainder")) 1512 || !TEST_ptr(ret = BN_new()) 1513 || !TEST_ptr(ret2 = BN_new()) 1514 || !TEST_ptr(nnmod = BN_new())) 1515 goto err; 1516 1517 if (!TEST_true(BN_div(ret, ret2, a, b, ctx)) 1518 || !equalBN("A / B", quotient, ret) 1519 || !equalBN("A % B", remainder, ret2) 1520 || !TEST_true(BN_mul(ret, quotient, b, ctx)) 1521 || !TEST_true(BN_add(ret, ret, remainder)) 1522 || !equalBN("Quotient * B + Remainder", a, ret)) 1523 goto err; 1524 1525 /* 1526 * Test with BN_mod_word() and BN_div_word() if the divisor is 1527 * small enough. 1528 */ 1529 b_word = BN_get_word(b); 1530 if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) { 1531 BN_ULONG remainder_word = BN_get_word(remainder); 1532 1533 assert(remainder_word != (BN_ULONG)-1); 1534 if (!TEST_ptr(BN_copy(ret, a))) 1535 goto err; 1536 ret_word = BN_div_word(ret, b_word); 1537 if (ret_word != remainder_word) { 1538#ifdef BN_DEC_FMT1 1539 TEST_error( 1540 "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1, 1541 ret_word, remainder_word); 1542#else 1543 TEST_error("Got A %% B (word) mismatch"); 1544#endif 1545 goto err; 1546 } 1547 if (!equalBN ("A / B (word)", quotient, ret)) 1548 goto err; 1549 1550 ret_word = BN_mod_word(a, b_word); 1551 if (ret_word != remainder_word) { 1552#ifdef BN_DEC_FMT1 1553 TEST_error( 1554 "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1 "", 1555 ret_word, remainder_word); 1556#else 1557 TEST_error("Got A %% B (word) mismatch"); 1558#endif 1559 goto err; 1560 } 1561 } 1562 1563 /* Test BN_nnmod. */ 1564 if (!BN_is_negative(b)) { 1565 if (!TEST_true(BN_copy(nnmod, remainder)) 1566 || (BN_is_negative(nnmod) 1567 && !TEST_true(BN_add(nnmod, nnmod, b))) 1568 || !TEST_true(BN_nnmod(ret, a, b, ctx)) 1569 || !equalBN("A % B (non-negative)", nnmod, ret)) 1570 goto err; 1571 } 1572 1573 st = 1; 1574 err: 1575 BN_free(a); 1576 BN_free(b); 1577 BN_free(quotient); 1578 BN_free(remainder); 1579 BN_free(ret); 1580 BN_free(ret2); 1581 BN_free(nnmod); 1582 return st; 1583} 1584 1585static int file_modmul(STANZA *s) 1586{ 1587 BIGNUM *a = NULL, *b = NULL, *m = NULL, *mod_mul = NULL, *ret = NULL; 1588 int st = 0; 1589 1590 if (!TEST_ptr(a = getBN(s, "A")) 1591 || !TEST_ptr(b = getBN(s, "B")) 1592 || !TEST_ptr(m = getBN(s, "M")) 1593 || !TEST_ptr(mod_mul = getBN(s, "ModMul")) 1594 || !TEST_ptr(ret = BN_new())) 1595 goto err; 1596 1597 if (!TEST_true(BN_mod_mul(ret, a, b, m, ctx)) 1598 || !equalBN("A * B (mod M)", mod_mul, ret)) 1599 goto err; 1600 1601 if (BN_is_odd(m)) { 1602 /* Reduce |a| and |b| and test the Montgomery version. */ 1603 BN_MONT_CTX *mont = BN_MONT_CTX_new(); 1604 BIGNUM *a_tmp = BN_new(); 1605 BIGNUM *b_tmp = BN_new(); 1606 1607 if (mont == NULL || a_tmp == NULL || b_tmp == NULL 1608 || !TEST_true(BN_MONT_CTX_set(mont, m, ctx)) 1609 || !TEST_true(BN_nnmod(a_tmp, a, m, ctx)) 1610 || !TEST_true(BN_nnmod(b_tmp, b, m, ctx)) 1611 || !TEST_true(BN_to_montgomery(a_tmp, a_tmp, mont, ctx)) 1612 || !TEST_true(BN_to_montgomery(b_tmp, b_tmp, mont, ctx)) 1613 || !TEST_true(BN_mod_mul_montgomery(ret, a_tmp, b_tmp, 1614 mont, ctx)) 1615 || !TEST_true(BN_from_montgomery(ret, ret, mont, ctx)) 1616 || !equalBN("A * B (mod M) (mont)", mod_mul, ret)) 1617 st = 0; 1618 else 1619 st = 1; 1620 BN_MONT_CTX_free(mont); 1621 BN_free(a_tmp); 1622 BN_free(b_tmp); 1623 if (st == 0) 1624 goto err; 1625 } 1626 1627 st = 1; 1628 err: 1629 BN_free(a); 1630 BN_free(b); 1631 BN_free(m); 1632 BN_free(mod_mul); 1633 BN_free(ret); 1634 return st; 1635} 1636 1637static int file_modexp(STANZA *s) 1638{ 1639 BIGNUM *a = NULL, *e = NULL, *m = NULL, *mod_exp = NULL, *ret = NULL; 1640 BIGNUM *b = NULL, *c = NULL, *d = NULL; 1641 int st = 0; 1642 1643 if (!TEST_ptr(a = getBN(s, "A")) 1644 || !TEST_ptr(e = getBN(s, "E")) 1645 || !TEST_ptr(m = getBN(s, "M")) 1646 || !TEST_ptr(mod_exp = getBN(s, "ModExp")) 1647 || !TEST_ptr(ret = BN_new()) 1648 || !TEST_ptr(d = BN_new())) 1649 goto err; 1650 1651 if (!TEST_true(BN_mod_exp(ret, a, e, m, ctx)) 1652 || !equalBN("A ^ E (mod M)", mod_exp, ret)) 1653 goto err; 1654 1655 if (BN_is_odd(m)) { 1656 if (!TEST_true(BN_mod_exp_mont(ret, a, e, m, ctx, NULL)) 1657 || !equalBN("A ^ E (mod M) (mont)", mod_exp, ret) 1658 || !TEST_true(BN_mod_exp_mont_consttime(ret, a, e, m, 1659 ctx, NULL)) 1660 || !equalBN("A ^ E (mod M) (mont const", mod_exp, ret)) 1661 goto err; 1662 } 1663 1664 /* Regression test for carry propagation bug in sqr8x_reduction */ 1665 BN_hex2bn(&a, "050505050505"); 1666 BN_hex2bn(&b, "02"); 1667 BN_hex2bn(&c, 1668 "4141414141414141414141274141414141414141414141414141414141414141" 1669 "4141414141414141414141414141414141414141414141414141414141414141" 1670 "4141414141414141414141800000000000000000000000000000000000000000" 1671 "0000000000000000000000000000000000000000000000000000000000000000" 1672 "0000000000000000000000000000000000000000000000000000000000000000" 1673 "0000000000000000000000000000000000000000000000000000000001"); 1674 if (!TEST_true(BN_mod_exp(d, a, b, c, ctx)) 1675 || !TEST_true(BN_mul(e, a, a, ctx)) 1676 || !TEST_BN_eq(d, e)) 1677 goto err; 1678 1679 st = 1; 1680 err: 1681 BN_free(a); 1682 BN_free(b); 1683 BN_free(c); 1684 BN_free(d); 1685 BN_free(e); 1686 BN_free(m); 1687 BN_free(mod_exp); 1688 BN_free(ret); 1689 return st; 1690} 1691 1692static int file_exp(STANZA *s) 1693{ 1694 BIGNUM *a = NULL, *e = NULL, *exp = NULL, *ret = NULL; 1695 int st = 0; 1696 1697 if (!TEST_ptr(a = getBN(s, "A")) 1698 || !TEST_ptr(e = getBN(s, "E")) 1699 || !TEST_ptr(exp = getBN(s, "Exp")) 1700 || !TEST_ptr(ret = BN_new())) 1701 goto err; 1702 1703 if (!TEST_true(BN_exp(ret, a, e, ctx)) 1704 || !equalBN("A ^ E", exp, ret)) 1705 goto err; 1706 1707 st = 1; 1708 err: 1709 BN_free(a); 1710 BN_free(e); 1711 BN_free(exp); 1712 BN_free(ret); 1713 return st; 1714} 1715 1716static int file_modsqrt(STANZA *s) 1717{ 1718 BIGNUM *a = NULL, *p = NULL, *mod_sqrt = NULL, *ret = NULL, *ret2 = NULL; 1719 int st = 0; 1720 1721 if (!TEST_ptr(a = getBN(s, "A")) 1722 || !TEST_ptr(p = getBN(s, "P")) 1723 || !TEST_ptr(mod_sqrt = getBN(s, "ModSqrt")) 1724 || !TEST_ptr(ret = BN_new()) 1725 || !TEST_ptr(ret2 = BN_new())) 1726 goto err; 1727 1728 if (BN_is_negative(mod_sqrt)) { 1729 /* A negative testcase */ 1730 if (!TEST_ptr_null(BN_mod_sqrt(ret, a, p, ctx))) 1731 goto err; 1732 1733 st = 1; 1734 goto err; 1735 } 1736 1737 /* There are two possible answers. */ 1738 if (!TEST_ptr(BN_mod_sqrt(ret, a, p, ctx)) 1739 || !TEST_true(BN_sub(ret2, p, ret))) 1740 goto err; 1741 1742 /* The first condition should NOT be a test. */ 1743 if (BN_cmp(ret2, mod_sqrt) != 0 1744 && !equalBN("sqrt(A) (mod P)", mod_sqrt, ret)) 1745 goto err; 1746 1747 st = 1; 1748 err: 1749 BN_free(a); 1750 BN_free(p); 1751 BN_free(mod_sqrt); 1752 BN_free(ret); 1753 BN_free(ret2); 1754 return st; 1755} 1756 1757static int file_gcd(STANZA *s) 1758{ 1759 BIGNUM *a = NULL, *b = NULL, *gcd = NULL, *ret = NULL; 1760 int st = 0; 1761 1762 if (!TEST_ptr(a = getBN(s, "A")) 1763 || !TEST_ptr(b = getBN(s, "B")) 1764 || !TEST_ptr(gcd = getBN(s, "GCD")) 1765 || !TEST_ptr(ret = BN_new())) 1766 goto err; 1767 1768 if (!TEST_true(BN_gcd(ret, a, b, ctx)) 1769 || !equalBN("gcd(A,B)", gcd, ret)) 1770 goto err; 1771 1772 st = 1; 1773 err: 1774 BN_free(a); 1775 BN_free(b); 1776 BN_free(gcd); 1777 BN_free(ret); 1778 return st; 1779} 1780 1781static int test_bn2padded(void) 1782{ 1783 uint8_t zeros[256], out[256], reference[128]; 1784 size_t bytes; 1785 BIGNUM *n; 1786 int st = 0; 1787 1788 /* Test edge case at 0. */ 1789 if (!TEST_ptr((n = BN_new()))) 1790 goto err; 1791 if (!TEST_int_eq(BN_bn2binpad(n, NULL, 0), 0)) 1792 goto err; 1793 memset(out, -1, sizeof(out)); 1794 if (!TEST_int_eq(BN_bn2binpad(n, out, sizeof(out)), sizeof(out))) 1795 goto err; 1796 memset(zeros, 0, sizeof(zeros)); 1797 if (!TEST_mem_eq(zeros, sizeof(zeros), out, sizeof(out))) 1798 goto err; 1799 1800 /* Test a random numbers at various byte lengths. */ 1801 for (bytes = 128 - 7; bytes <= 128; bytes++) { 1802# define TOP_BIT_ON 0 1803# define BOTTOM_BIT_NOTOUCH 0 1804 if (!TEST_true(BN_rand(n, bytes * 8, TOP_BIT_ON, BOTTOM_BIT_NOTOUCH))) 1805 goto err; 1806 if (!TEST_int_eq(BN_num_bytes(n), bytes) 1807 || !TEST_int_eq(BN_bn2bin(n, reference), bytes)) 1808 goto err; 1809 /* Empty buffer should fail. */ 1810 if (!TEST_int_eq(BN_bn2binpad(n, NULL, 0), -1)) 1811 goto err; 1812 /* One byte short should fail. */ 1813 if (!TEST_int_eq(BN_bn2binpad(n, out, bytes - 1), -1)) 1814 goto err; 1815 /* Exactly right size should encode. */ 1816 if (!TEST_int_eq(BN_bn2binpad(n, out, bytes), bytes) 1817 || !TEST_mem_eq(out, bytes, reference, bytes)) 1818 goto err; 1819 /* Pad up one byte extra. */ 1820 if (!TEST_int_eq(BN_bn2binpad(n, out, bytes + 1), bytes + 1) 1821 || !TEST_mem_eq(out + 1, bytes, reference, bytes) 1822 || !TEST_mem_eq(out, 1, zeros, 1)) 1823 goto err; 1824 /* Pad up to 256. */ 1825 if (!TEST_int_eq(BN_bn2binpad(n, out, sizeof(out)), sizeof(out)) 1826 || !TEST_mem_eq(out + sizeof(out) - bytes, bytes, 1827 reference, bytes) 1828 || !TEST_mem_eq(out, sizeof(out) - bytes, 1829 zeros, sizeof(out) - bytes)) 1830 goto err; 1831 } 1832 1833 st = 1; 1834 err: 1835 BN_free(n); 1836 return st; 1837} 1838 1839static int test_dec2bn(void) 1840{ 1841 BIGNUM *bn = NULL; 1842 int st = 0; 1843 1844 if (!TEST_int_eq(parsedecBN(&bn, "0"), 1) 1845 || !TEST_BN_eq_word(bn, 0) 1846 || !TEST_BN_eq_zero(bn) 1847 || !TEST_BN_le_zero(bn) 1848 || !TEST_BN_ge_zero(bn) 1849 || !TEST_BN_even(bn)) 1850 goto err; 1851 BN_free(bn); 1852 bn = NULL; 1853 1854 if (!TEST_int_eq(parsedecBN(&bn, "256"), 3) 1855 || !TEST_BN_eq_word(bn, 256) 1856 || !TEST_BN_ge_zero(bn) 1857 || !TEST_BN_gt_zero(bn) 1858 || !TEST_BN_ne_zero(bn) 1859 || !TEST_BN_even(bn)) 1860 goto err; 1861 BN_free(bn); 1862 bn = NULL; 1863 1864 if (!TEST_int_eq(parsedecBN(&bn, "-42"), 3) 1865 || !TEST_BN_abs_eq_word(bn, 42) 1866 || !TEST_BN_lt_zero(bn) 1867 || !TEST_BN_le_zero(bn) 1868 || !TEST_BN_ne_zero(bn) 1869 || !TEST_BN_even(bn)) 1870 goto err; 1871 BN_free(bn); 1872 bn = NULL; 1873 1874 if (!TEST_int_eq(parsedecBN(&bn, "1"), 1) 1875 || !TEST_BN_eq_word(bn, 1) 1876 || !TEST_BN_ne_zero(bn) 1877 || !TEST_BN_gt_zero(bn) 1878 || !TEST_BN_ge_zero(bn) 1879 || !TEST_BN_eq_one(bn) 1880 || !TEST_BN_odd(bn)) 1881 goto err; 1882 BN_free(bn); 1883 bn = NULL; 1884 1885 if (!TEST_int_eq(parsedecBN(&bn, "-0"), 2) 1886 || !TEST_BN_eq_zero(bn) 1887 || !TEST_BN_ge_zero(bn) 1888 || !TEST_BN_le_zero(bn) 1889 || !TEST_BN_even(bn)) 1890 goto err; 1891 BN_free(bn); 1892 bn = NULL; 1893 1894 if (!TEST_int_eq(parsedecBN(&bn, "42trailing garbage is ignored"), 2) 1895 || !TEST_BN_abs_eq_word(bn, 42) 1896 || !TEST_BN_ge_zero(bn) 1897 || !TEST_BN_gt_zero(bn) 1898 || !TEST_BN_ne_zero(bn) 1899 || !TEST_BN_even(bn)) 1900 goto err; 1901 1902 st = 1; 1903 err: 1904 BN_free(bn); 1905 return st; 1906} 1907 1908static int test_hex2bn(void) 1909{ 1910 BIGNUM *bn = NULL; 1911 int st = 0; 1912 1913 if (!TEST_int_eq(parseBN(&bn, "0"), 1) 1914 || !TEST_BN_eq_zero(bn) 1915 || !TEST_BN_ge_zero(bn) 1916 || !TEST_BN_even(bn)) 1917 goto err; 1918 BN_free(bn); 1919 bn = NULL; 1920 1921 if (!TEST_int_eq(parseBN(&bn, "256"), 3) 1922 || !TEST_BN_eq_word(bn, 0x256) 1923 || !TEST_BN_ge_zero(bn) 1924 || !TEST_BN_gt_zero(bn) 1925 || !TEST_BN_ne_zero(bn) 1926 || !TEST_BN_even(bn)) 1927 goto err; 1928 BN_free(bn); 1929 bn = NULL; 1930 1931 if (!TEST_int_eq(parseBN(&bn, "-42"), 3) 1932 || !TEST_BN_abs_eq_word(bn, 0x42) 1933 || !TEST_BN_lt_zero(bn) 1934 || !TEST_BN_le_zero(bn) 1935 || !TEST_BN_ne_zero(bn) 1936 || !TEST_BN_even(bn)) 1937 goto err; 1938 BN_free(bn); 1939 bn = NULL; 1940 1941 if (!TEST_int_eq(parseBN(&bn, "cb"), 2) 1942 || !TEST_BN_eq_word(bn, 0xCB) 1943 || !TEST_BN_ge_zero(bn) 1944 || !TEST_BN_gt_zero(bn) 1945 || !TEST_BN_ne_zero(bn) 1946 || !TEST_BN_odd(bn)) 1947 goto err; 1948 BN_free(bn); 1949 bn = NULL; 1950 1951 if (!TEST_int_eq(parseBN(&bn, "-0"), 2) 1952 || !TEST_BN_eq_zero(bn) 1953 || !TEST_BN_ge_zero(bn) 1954 || !TEST_BN_le_zero(bn) 1955 || !TEST_BN_even(bn)) 1956 goto err; 1957 BN_free(bn); 1958 bn = NULL; 1959 1960 if (!TEST_int_eq(parseBN(&bn, "abctrailing garbage is ignored"), 3) 1961 || !TEST_BN_eq_word(bn, 0xabc) 1962 || !TEST_BN_ge_zero(bn) 1963 || !TEST_BN_gt_zero(bn) 1964 || !TEST_BN_ne_zero(bn) 1965 || !TEST_BN_even(bn)) 1966 goto err; 1967 st = 1; 1968 1969 err: 1970 BN_free(bn); 1971 return st; 1972} 1973 1974static int test_asc2bn(void) 1975{ 1976 BIGNUM *bn = NULL; 1977 int st = 0; 1978 1979 if (!TEST_ptr(bn = BN_new())) 1980 goto err; 1981 1982 if (!TEST_true(BN_asc2bn(&bn, "0")) 1983 || !TEST_BN_eq_zero(bn) 1984 || !TEST_BN_ge_zero(bn)) 1985 goto err; 1986 1987 if (!TEST_true(BN_asc2bn(&bn, "256")) 1988 || !TEST_BN_eq_word(bn, 256) 1989 || !TEST_BN_ge_zero(bn)) 1990 goto err; 1991 1992 if (!TEST_true(BN_asc2bn(&bn, "-42")) 1993 || !TEST_BN_abs_eq_word(bn, 42) 1994 || !TEST_BN_lt_zero(bn)) 1995 goto err; 1996 1997 if (!TEST_true(BN_asc2bn(&bn, "0x1234")) 1998 || !TEST_BN_eq_word(bn, 0x1234) 1999 || !TEST_BN_ge_zero(bn)) 2000 goto err; 2001 2002 if (!TEST_true(BN_asc2bn(&bn, "0X1234")) 2003 || !TEST_BN_eq_word(bn, 0x1234) 2004 || !TEST_BN_ge_zero(bn)) 2005 goto err; 2006 2007 if (!TEST_true(BN_asc2bn(&bn, "-0xabcd")) 2008 || !TEST_BN_abs_eq_word(bn, 0xabcd) 2009 || !TEST_BN_lt_zero(bn)) 2010 goto err; 2011 2012 if (!TEST_true(BN_asc2bn(&bn, "-0")) 2013 || !TEST_BN_eq_zero(bn) 2014 || !TEST_BN_ge_zero(bn)) 2015 goto err; 2016 2017 if (!TEST_true(BN_asc2bn(&bn, "123trailing garbage is ignored")) 2018 || !TEST_BN_eq_word(bn, 123) 2019 || !TEST_BN_ge_zero(bn)) 2020 goto err; 2021 2022 st = 1; 2023 err: 2024 BN_free(bn); 2025 return st; 2026} 2027 2028static const MPITEST kMPITests[] = { 2029 {"0", "\x00\x00\x00\x00", 4}, 2030 {"1", "\x00\x00\x00\x01\x01", 5}, 2031 {"-1", "\x00\x00\x00\x01\x81", 5}, 2032 {"128", "\x00\x00\x00\x02\x00\x80", 6}, 2033 {"256", "\x00\x00\x00\x02\x01\x00", 6}, 2034 {"-256", "\x00\x00\x00\x02\x81\x00", 6}, 2035}; 2036 2037static int test_mpi(int i) 2038{ 2039 uint8_t scratch[8]; 2040 const MPITEST *test = &kMPITests[i]; 2041 size_t mpi_len, mpi_len2; 2042 BIGNUM *bn = NULL; 2043 BIGNUM *bn2 = NULL; 2044 int st = 0; 2045 2046 if (!TEST_ptr(bn = BN_new()) 2047 || !TEST_true(BN_asc2bn(&bn, test->base10))) 2048 goto err; 2049 mpi_len = BN_bn2mpi(bn, NULL); 2050 if (!TEST_size_t_le(mpi_len, sizeof(scratch))) 2051 goto err; 2052 2053 if (!TEST_size_t_eq(mpi_len2 = BN_bn2mpi(bn, scratch), mpi_len) 2054 || !TEST_mem_eq(test->mpi, test->mpi_len, scratch, mpi_len)) 2055 goto err; 2056 2057 if (!TEST_ptr(bn2 = BN_mpi2bn(scratch, mpi_len, NULL))) 2058 goto err; 2059 2060 if (!TEST_BN_eq(bn, bn2)) { 2061 BN_free(bn2); 2062 goto err; 2063 } 2064 BN_free(bn2); 2065 2066 st = 1; 2067 err: 2068 BN_free(bn); 2069 return st; 2070} 2071 2072static int test_rand(void) 2073{ 2074 BIGNUM *bn = NULL; 2075 int st = 0; 2076 2077 if (!TEST_ptr(bn = BN_new())) 2078 return 0; 2079 2080 /* Test BN_rand for degenerate cases with |top| and |bottom| parameters. */ 2081 if (!TEST_false(BN_rand(bn, 0, 0 /* top */ , 0 /* bottom */ )) 2082 || !TEST_false(BN_rand(bn, 0, 1 /* top */ , 1 /* bottom */ )) 2083 || !TEST_true(BN_rand(bn, 1, 0 /* top */ , 0 /* bottom */ )) 2084 || !TEST_BN_eq_one(bn) 2085 || !TEST_false(BN_rand(bn, 1, 1 /* top */ , 0 /* bottom */ )) 2086 || !TEST_true(BN_rand(bn, 1, -1 /* top */ , 1 /* bottom */ )) 2087 || !TEST_BN_eq_one(bn) 2088 || !TEST_true(BN_rand(bn, 2, 1 /* top */ , 0 /* bottom */ )) 2089 || !TEST_BN_eq_word(bn, 3)) 2090 goto err; 2091 2092 st = 1; 2093 err: 2094 BN_free(bn); 2095 return st; 2096} 2097 2098/* 2099 * Run some statistical tests to provide a degree confidence that the 2100 * BN_rand_range() function works as expected. The test cases and 2101 * critical values are generated by the bn_rand_range script. 2102 * 2103 * Each individual test is a Chi^2 goodness of fit for a specified number 2104 * of samples and range. The samples are assumed to be independent and 2105 * that they are from a discrete uniform distribution. 2106 * 2107 * Some of these individual tests are expected to fail, the success/failure 2108 * of each is an independent Bernoulli trial. The number of such successes 2109 * will form a binomial distribution. The count of the successes is compared 2110 * against a precomputed critical value to determine the overall outcome. 2111 */ 2112struct rand_range_case { 2113 unsigned int range; 2114 unsigned int iterations; 2115 double critical; 2116}; 2117 2118#include "bn_rand_range.h" 2119 2120static int test_rand_range_single(size_t n) 2121{ 2122 const unsigned int range = rand_range_cases[n].range; 2123 const unsigned int iterations = rand_range_cases[n].iterations; 2124 const double critical = rand_range_cases[n].critical; 2125 const double expected = iterations / (double)range; 2126 double sum = 0; 2127 BIGNUM *rng = NULL, *val = NULL; 2128 size_t *counts; 2129 unsigned int i, v; 2130 int res = 0; 2131 2132 if (!TEST_ptr(counts = OPENSSL_zalloc(sizeof(*counts) * range)) 2133 || !TEST_ptr(rng = BN_new()) 2134 || !TEST_ptr(val = BN_new()) 2135 || !TEST_true(BN_set_word(rng, range))) 2136 goto err; 2137 for (i = 0; i < iterations; i++) { 2138 if (!TEST_true(BN_rand_range(val, rng)) 2139 || !TEST_uint_lt(v = (unsigned int)BN_get_word(val), range)) 2140 goto err; 2141 counts[v]++; 2142 } 2143 2144 for (i = 0; i < range; i++) { 2145 const double delta = counts[i] - expected; 2146 sum += delta * delta; 2147 } 2148 sum /= expected; 2149 2150 if (sum > critical) { 2151 TEST_info("Chi^2 test negative %.4f > %4.f", sum, critical); 2152 TEST_note("test case %zu range %u iterations %u", n + 1, range, 2153 iterations); 2154 goto err; 2155 } 2156 2157 res = 1; 2158err: 2159 BN_free(rng); 2160 BN_free(val); 2161 OPENSSL_free(counts); 2162 return res; 2163} 2164 2165static int test_rand_range(void) 2166{ 2167 int n_success = 0; 2168 size_t i; 2169 2170 for (i = 0; i < OSSL_NELEM(rand_range_cases); i++) 2171 n_success += test_rand_range_single(i); 2172 if (TEST_int_ge(n_success, binomial_critical)) 2173 return 1; 2174 TEST_note("This test is expected to fail by chance 0.01%% of the time."); 2175 return 0; 2176} 2177 2178static int test_negzero(void) 2179{ 2180 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL; 2181 BIGNUM *numerator = NULL, *denominator = NULL; 2182 int consttime, st = 0; 2183 2184 if (!TEST_ptr(a = BN_new()) 2185 || !TEST_ptr(b = BN_new()) 2186 || !TEST_ptr(c = BN_new()) 2187 || !TEST_ptr(d = BN_new())) 2188 goto err; 2189 2190 /* Test that BN_mul never gives negative zero. */ 2191 if (!TEST_true(BN_set_word(a, 1))) 2192 goto err; 2193 BN_set_negative(a, 1); 2194 BN_zero(b); 2195 if (!TEST_true(BN_mul(c, a, b, ctx))) 2196 goto err; 2197 if (!TEST_BN_eq_zero(c) 2198 || !TEST_BN_ge_zero(c)) 2199 goto err; 2200 2201 for (consttime = 0; consttime < 2; consttime++) { 2202 if (!TEST_ptr(numerator = BN_new()) 2203 || !TEST_ptr(denominator = BN_new())) 2204 goto err; 2205 if (consttime) { 2206 BN_set_flags(numerator, BN_FLG_CONSTTIME); 2207 BN_set_flags(denominator, BN_FLG_CONSTTIME); 2208 } 2209 /* Test that BN_div never gives negative zero in the quotient. */ 2210 if (!TEST_true(BN_set_word(numerator, 1)) 2211 || !TEST_true(BN_set_word(denominator, 2))) 2212 goto err; 2213 BN_set_negative(numerator, 1); 2214 if (!TEST_true(BN_div(a, b, numerator, denominator, ctx)) 2215 || !TEST_BN_eq_zero(a) 2216 || !TEST_BN_ge_zero(a)) 2217 goto err; 2218 2219 /* Test that BN_div never gives negative zero in the remainder. */ 2220 if (!TEST_true(BN_set_word(denominator, 1)) 2221 || !TEST_true(BN_div(a, b, numerator, denominator, ctx)) 2222 || !TEST_BN_eq_zero(b) 2223 || !TEST_BN_ge_zero(b)) 2224 goto err; 2225 BN_free(numerator); 2226 BN_free(denominator); 2227 numerator = denominator = NULL; 2228 } 2229 2230 /* Test that BN_set_negative will not produce a negative zero. */ 2231 BN_zero(a); 2232 BN_set_negative(a, 1); 2233 if (BN_is_negative(a)) 2234 goto err; 2235 st = 1; 2236 2237 err: 2238 BN_free(a); 2239 BN_free(b); 2240 BN_free(c); 2241 BN_free(d); 2242 BN_free(numerator); 2243 BN_free(denominator); 2244 return st; 2245} 2246 2247static int test_badmod(void) 2248{ 2249 BIGNUM *a = NULL, *b = NULL, *zero = NULL; 2250 BN_MONT_CTX *mont = NULL; 2251 int st = 0; 2252 2253 if (!TEST_ptr(a = BN_new()) 2254 || !TEST_ptr(b = BN_new()) 2255 || !TEST_ptr(zero = BN_new()) 2256 || !TEST_ptr(mont = BN_MONT_CTX_new())) 2257 goto err; 2258 BN_zero(zero); 2259 2260 if (!TEST_false(BN_div(a, b, BN_value_one(), zero, ctx))) 2261 goto err; 2262 ERR_clear_error(); 2263 2264 if (!TEST_false(BN_mod_mul(a, BN_value_one(), BN_value_one(), zero, ctx))) 2265 goto err; 2266 ERR_clear_error(); 2267 2268 if (!TEST_false(BN_mod_exp(a, BN_value_one(), BN_value_one(), zero, ctx))) 2269 goto err; 2270 ERR_clear_error(); 2271 2272 if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(), 2273 zero, ctx, NULL))) 2274 goto err; 2275 ERR_clear_error(); 2276 2277 if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(), 2278 zero, ctx, NULL))) 2279 goto err; 2280 ERR_clear_error(); 2281 2282 if (!TEST_false(BN_MONT_CTX_set(mont, zero, ctx))) 2283 goto err; 2284 ERR_clear_error(); 2285 2286 /* Some operations also may not be used with an even modulus. */ 2287 if (!TEST_true(BN_set_word(b, 16))) 2288 goto err; 2289 2290 if (!TEST_false(BN_MONT_CTX_set(mont, b, ctx))) 2291 goto err; 2292 ERR_clear_error(); 2293 2294 if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(), 2295 b, ctx, NULL))) 2296 goto err; 2297 ERR_clear_error(); 2298 2299 if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(), 2300 b, ctx, NULL))) 2301 goto err; 2302 ERR_clear_error(); 2303 2304 st = 1; 2305 err: 2306 BN_free(a); 2307 BN_free(b); 2308 BN_free(zero); 2309 BN_MONT_CTX_free(mont); 2310 return st; 2311} 2312 2313static int test_expmodzero(void) 2314{ 2315 BIGNUM *a = NULL, *r = NULL, *zero = NULL; 2316 int st = 0; 2317 2318 if (!TEST_ptr(zero = BN_new()) 2319 || !TEST_ptr(a = BN_new()) 2320 || !TEST_ptr(r = BN_new())) 2321 goto err; 2322 BN_zero(zero); 2323 2324 if (!TEST_true(BN_mod_exp(r, a, zero, BN_value_one(), NULL)) 2325 || !TEST_BN_eq_zero(r) 2326 || !TEST_true(BN_mod_exp_mont(r, a, zero, BN_value_one(), 2327 NULL, NULL)) 2328 || !TEST_BN_eq_zero(r) 2329 || !TEST_true(BN_mod_exp_mont_consttime(r, a, zero, 2330 BN_value_one(), 2331 NULL, NULL)) 2332 || !TEST_BN_eq_zero(r) 2333 || !TEST_true(BN_mod_exp_mont_word(r, 42, zero, 2334 BN_value_one(), NULL, NULL)) 2335 || !TEST_BN_eq_zero(r)) 2336 goto err; 2337 2338 st = 1; 2339 err: 2340 BN_free(zero); 2341 BN_free(a); 2342 BN_free(r); 2343 return st; 2344} 2345 2346static int test_expmodone(void) 2347{ 2348 int ret = 0, i; 2349 BIGNUM *r = BN_new(); 2350 BIGNUM *a = BN_new(); 2351 BIGNUM *p = BN_new(); 2352 BIGNUM *m = BN_new(); 2353 2354 if (!TEST_ptr(r) 2355 || !TEST_ptr(a) 2356 || !TEST_ptr(p) 2357 || !TEST_ptr(p) 2358 || !TEST_ptr(m) 2359 || !TEST_true(BN_set_word(a, 1)) 2360 || !TEST_true(BN_set_word(p, 0)) 2361 || !TEST_true(BN_set_word(m, 1))) 2362 goto err; 2363 2364 /* Calculate r = 1 ^ 0 mod 1, and check the result is always 0 */ 2365 for (i = 0; i < 2; i++) { 2366 if (!TEST_true(BN_mod_exp(r, a, p, m, NULL)) 2367 || !TEST_BN_eq_zero(r) 2368 || !TEST_true(BN_mod_exp_mont(r, a, p, m, NULL, NULL)) 2369 || !TEST_BN_eq_zero(r) 2370 || !TEST_true(BN_mod_exp_mont_consttime(r, a, p, m, NULL, NULL)) 2371 || !TEST_BN_eq_zero(r) 2372 || !TEST_true(BN_mod_exp_mont_word(r, 1, p, m, NULL, NULL)) 2373 || !TEST_BN_eq_zero(r) 2374 || !TEST_true(BN_mod_exp_simple(r, a, p, m, NULL)) 2375 || !TEST_BN_eq_zero(r) 2376 || !TEST_true(BN_mod_exp_recp(r, a, p, m, NULL)) 2377 || !TEST_BN_eq_zero(r)) 2378 goto err; 2379 /* Repeat for r = 1 ^ 0 mod -1 */ 2380 if (i == 0) 2381 BN_set_negative(m, 1); 2382 } 2383 2384 ret = 1; 2385 err: 2386 BN_free(r); 2387 BN_free(a); 2388 BN_free(p); 2389 BN_free(m); 2390 return ret; 2391} 2392 2393static int test_smallprime(int kBits) 2394{ 2395 BIGNUM *r; 2396 int st = 0; 2397 2398 if (!TEST_ptr(r = BN_new())) 2399 goto err; 2400 2401 if (kBits <= 1) { 2402 if (!TEST_false(BN_generate_prime_ex(r, kBits, 0, 2403 NULL, NULL, NULL))) 2404 goto err; 2405 } else { 2406 if (!TEST_true(BN_generate_prime_ex(r, kBits, 0, 2407 NULL, NULL, NULL)) 2408 || !TEST_int_eq(BN_num_bits(r), kBits)) 2409 goto err; 2410 } 2411 2412 st = 1; 2413 err: 2414 BN_free(r); 2415 return st; 2416} 2417 2418static int test_smallsafeprime(int kBits) 2419{ 2420 BIGNUM *r; 2421 int st = 0; 2422 2423 if (!TEST_ptr(r = BN_new())) 2424 goto err; 2425 2426 if (kBits <= 5 && kBits != 3) { 2427 if (!TEST_false(BN_generate_prime_ex(r, kBits, 1, 2428 NULL, NULL, NULL))) 2429 goto err; 2430 } else { 2431 if (!TEST_true(BN_generate_prime_ex(r, kBits, 1, 2432 NULL, NULL, NULL)) 2433 || !TEST_int_eq(BN_num_bits(r), kBits)) 2434 goto err; 2435 } 2436 2437 st = 1; 2438 err: 2439 BN_free(r); 2440 return st; 2441} 2442 2443static int primes[] = { 2, 3, 5, 7, 17863 }; 2444 2445static int test_is_prime(int i) 2446{ 2447 int ret = 0; 2448 BIGNUM *r = NULL; 2449 int trial; 2450 2451 if (!TEST_ptr(r = BN_new())) 2452 goto err; 2453 2454 for (trial = 0; trial <= 1; ++trial) { 2455 if (!TEST_true(BN_set_word(r, primes[i])) 2456 || !TEST_int_eq(BN_check_prime(r, ctx, NULL), 2457 1)) 2458 goto err; 2459 } 2460 2461 ret = 1; 2462 err: 2463 BN_free(r); 2464 return ret; 2465} 2466 2467static int not_primes[] = { -1, 0, 1, 4 }; 2468 2469static int test_not_prime(int i) 2470{ 2471 int ret = 0; 2472 BIGNUM *r = NULL; 2473 int trial; 2474 2475 if (!TEST_ptr(r = BN_new())) 2476 goto err; 2477 2478 for (trial = 0; trial <= 1; ++trial) { 2479 if (!TEST_true(BN_set_word(r, not_primes[i])) 2480 || !TEST_false(BN_check_prime(r, ctx, NULL))) 2481 goto err; 2482 } 2483 2484 ret = 1; 2485 err: 2486 BN_free(r); 2487 return ret; 2488} 2489 2490static int test_ctx_set_ct_flag(BN_CTX *c) 2491{ 2492 int st = 0; 2493 size_t i; 2494 BIGNUM *b[15]; 2495 2496 BN_CTX_start(c); 2497 for (i = 0; i < OSSL_NELEM(b); i++) { 2498 if (!TEST_ptr(b[i] = BN_CTX_get(c))) 2499 goto err; 2500 if (i % 2 == 1) 2501 BN_set_flags(b[i], BN_FLG_CONSTTIME); 2502 } 2503 2504 st = 1; 2505 err: 2506 BN_CTX_end(c); 2507 return st; 2508} 2509 2510static int test_ctx_check_ct_flag(BN_CTX *c) 2511{ 2512 int st = 0; 2513 size_t i; 2514 BIGNUM *b[30]; 2515 2516 BN_CTX_start(c); 2517 for (i = 0; i < OSSL_NELEM(b); i++) { 2518 if (!TEST_ptr(b[i] = BN_CTX_get(c))) 2519 goto err; 2520 if (!TEST_false(BN_get_flags(b[i], BN_FLG_CONSTTIME))) 2521 goto err; 2522 } 2523 2524 st = 1; 2525 err: 2526 BN_CTX_end(c); 2527 return st; 2528} 2529 2530static int test_ctx_consttime_flag(void) 2531{ 2532 /*- 2533 * The constant-time flag should not "leak" among BN_CTX frames: 2534 * 2535 * - test_ctx_set_ct_flag() starts a frame in the given BN_CTX and 2536 * sets the BN_FLG_CONSTTIME flag on some of the BIGNUMs obtained 2537 * from the frame before ending it. 2538 * - test_ctx_check_ct_flag() then starts a new frame and gets a 2539 * number of BIGNUMs from it. In absence of leaks, none of the 2540 * BIGNUMs in the new frame should have BN_FLG_CONSTTIME set. 2541 * 2542 * In actual BN_CTX usage inside libcrypto the leak could happen at 2543 * any depth level in the BN_CTX stack, with varying results 2544 * depending on the patterns of sibling trees of nested function 2545 * calls sharing the same BN_CTX object, and the effect of 2546 * unintended BN_FLG_CONSTTIME on the called BN_* functions. 2547 * 2548 * This simple unit test abstracts away this complexity and verifies 2549 * that the leak does not happen between two sibling functions 2550 * sharing the same BN_CTX object at the same level of nesting. 2551 * 2552 */ 2553 BN_CTX *nctx = NULL; 2554 BN_CTX *sctx = NULL; 2555 size_t i = 0; 2556 int st = 0; 2557 2558 if (!TEST_ptr(nctx = BN_CTX_new()) 2559 || !TEST_ptr(sctx = BN_CTX_secure_new())) 2560 goto err; 2561 2562 for (i = 0; i < 2; i++) { 2563 BN_CTX *c = i == 0 ? nctx : sctx; 2564 if (!TEST_true(test_ctx_set_ct_flag(c)) 2565 || !TEST_true(test_ctx_check_ct_flag(c))) 2566 goto err; 2567 } 2568 2569 st = 1; 2570 err: 2571 BN_CTX_free(nctx); 2572 BN_CTX_free(sctx); 2573 return st; 2574} 2575 2576static int test_gcd_prime(void) 2577{ 2578 BIGNUM *a = NULL, *b = NULL, *gcd = NULL; 2579 int i, st = 0; 2580 2581 if (!TEST_ptr(a = BN_new()) 2582 || !TEST_ptr(b = BN_new()) 2583 || !TEST_ptr(gcd = BN_new())) 2584 goto err; 2585 2586 if (!TEST_true(BN_generate_prime_ex(a, 1024, 0, NULL, NULL, NULL))) 2587 goto err; 2588 for (i = 0; i < NUM0; i++) { 2589 if (!TEST_true(BN_generate_prime_ex(b, 1024, 0, 2590 NULL, NULL, NULL)) 2591 || !TEST_true(BN_gcd(gcd, a, b, ctx)) 2592 || !TEST_true(BN_is_one(gcd))) 2593 goto err; 2594 } 2595 2596 st = 1; 2597 err: 2598 BN_free(a); 2599 BN_free(b); 2600 BN_free(gcd); 2601 return st; 2602} 2603 2604typedef struct mod_exp_test_st 2605{ 2606 const char *base; 2607 const char *exp; 2608 const char *mod; 2609 const char *res; 2610} MOD_EXP_TEST; 2611 2612static const MOD_EXP_TEST ModExpTests[] = { 2613 /* original test vectors for rsaz_512_sqr bug, by OSS-Fuzz */ 2614 { 2615 "1166180238001879113042182292626169621106255558914000595999312084" 2616 "4627946820899490684928760491249738643524880720584249698100907201" 2617 "002086675047927600340800371", 2618 "8000000000000000000000000000000000000000000000000000000000000000" 2619 "0000000000000000000000000000000000000000000000000000000000000000" 2620 "00000000", 2621 "1340780792684523720980737645613191762604395855615117867483316354" 2622 "3294276330515137663421134775482798690129946803802212663956180562" 2623 "088664022929883876655300863", 2624 "8243904058268085430037326628480645845409758077568738532059032482" 2625 "8294114415890603594730158120426756266457928475330450251339773498" 2626 "26758407619521544102068438" 2627 }, 2628 { 2629 "4974270041410803822078866696159586946995877618987010219312844726" 2630 "0284386121835740784990869050050504348861513337232530490826340663" 2631 "197278031692737429054", 2632 "4974270041410803822078866696159586946995877428188754995041148539" 2633 "1663243362592271353668158565195557417149981094324650322556843202" 2634 "946445882670777892608", 2635 "1340780716511420227215592830971452482815377482627251725537099028" 2636 "4429769497230131760206012644403029349547320953206103351725462999" 2637 "947509743623340557059752191", 2638 "5296244594780707015616522701706118082963369547253192207884519362" 2639 "1767869984947542695665420219028522815539559194793619684334900442" 2640 "49304558011362360473525933" 2641 }, 2642 /* test vectors for rsaz_512_srq bug, with rcx/rbx=1 */ 2643 { /* between first and second iteration */ 2644 "5148719036160389201525610950887605325980251964889646556085286545" 2645 "3931548809178823413169359635978762036512397113080988070677858033" 2646 "36463909753993540214027190", 2647 "6703903964971298549787012499102923063739682910296196688861780721" 2648 "8608820150367734884009371490834517138450159290932430254268769414" 2649 "05973284973216824503042158", 2650 "6703903964971298549787012499102923063739682910296196688861780721" 2651 "8608820150367734884009371490834517138450159290932430254268769414" 2652 "05973284973216824503042159", 2653 "1" 2654 }, 2655 { /* between second and third iteration */ 2656 "8908340854353752577419678771330460827942371434853054158622636544" 2657 "8151360109722890949471912566649465436296659601091730745087014189" 2658 "2672764191218875181826063", 2659 "6703903964971298549787012499102923063739682910296196688861780721" 2660 "8608820150367734884009371490834517138450159290932430254268769414" 2661 "05973284973216824503042158", 2662 "6703903964971298549787012499102923063739682910296196688861780721" 2663 "8608820150367734884009371490834517138450159290932430254268769414" 2664 "05973284973216824503042159", 2665 "1" 2666 }, 2667 { /* between third and fourth iteration */ 2668 "3427446396505596330634350984901719674479522569002785244080234738" 2669 "4288743635435746136297299366444548736533053717416735379073185344" 2670 "26985272974404612945608761", 2671 "6703903964971298549787012499102923063739682910296196688861780721" 2672 "8608820150367734884009371490834517138450159290932430254268769414" 2673 "05973284973216824503042158", 2674 "6703903964971298549787012499102923063739682910296196688861780721" 2675 "8608820150367734884009371490834517138450159290932430254268769414" 2676 "05973284973216824503042159", 2677 "1" 2678 }, 2679 { /* between fourth and fifth iteration */ 2680 "3472743044917564564078857826111874560045331237315597383869652985" 2681 "6919870028890895988478351133601517365908445058405433832718206902" 2682 "4088133164805266956353542", 2683 "6703903964971298549787012499102923063739682910296196688861780721" 2684 "8608820150367734884009371490834517138450159290932430254268769414" 2685 "05973284973216824503042158", 2686 "6703903964971298549787012499102923063739682910296196688861780721" 2687 "8608820150367734884009371490834517138450159290932430254268769414" 2688 "05973284973216824503042159", 2689 "1" 2690 }, 2691 { /* between fifth and sixth iteration */ 2692 "3608632990153469264412378349742339216742409743898601587274768025" 2693 "0110772032985643555192767717344946174122842255204082586753499651" 2694 "14483434992887431333675068", 2695 "6703903964971298549787012499102923063739682910296196688861780721" 2696 "8608820150367734884009371490834517138450159290932430254268769414" 2697 "05973284973216824503042158", 2698 "6703903964971298549787012499102923063739682910296196688861780721" 2699 "8608820150367734884009371490834517138450159290932430254268769414" 2700 "05973284973216824503042159", 2701 "1" 2702 }, 2703 { /* between sixth and seventh iteration */ 2704 "8455374370234070242910508226941981520235709767260723212165264877" 2705 "8689064388017521524568434328264431772644802567028663962962025746" 2706 "9283458217850119569539086", 2707 "6703903964971298549787012499102923063739682910296196688861780721" 2708 "8608820150367734884009371490834517138450159290932430254268769414" 2709 "05973284973216824503042158", 2710 "6703903964971298549787012499102923063739682910296196688861780721" 2711 "8608820150367734884009371490834517138450159290932430254268769414" 2712 "05973284973216824503042159", 2713 "1" 2714 }, 2715 { /* between seventh and eighth iteration */ 2716 "5155371529688532178421209781159131443543419764974688878527112131" 2717 "7446518205609427412336183157918981038066636807317733319323257603" 2718 "04416292040754017461076359", 2719 "1005585594745694782468051874865438459560952436544429503329267108" 2720 "2791323022555160232601405723625177570767523893639864538140315412" 2721 "108959927459825236754563832", 2722 "1005585594745694782468051874865438459560952436544429503329267108" 2723 "2791323022555160232601405723625177570767523893639864538140315412" 2724 "108959927459825236754563833", 2725 "1" 2726 }, 2727 /* test vectors for rsaz_512_srq bug, with rcx/rbx=2 */ 2728 { /* between first and second iteration */ 2729 "3155666506033786929967309937640790361084670559125912405342594979" 2730 "4345142818528956285490897841406338022378565972533508820577760065" 2731 "58494345853302083699912572", 2732 "6703903964971298549787012499102923063739682910296196688861780721" 2733 "8608820150367734884009371490834517138450159290932430254268769414" 2734 "05973284973216824503042158", 2735 "6703903964971298549787012499102923063739682910296196688861780721" 2736 "8608820150367734884009371490834517138450159290932430254268769414" 2737 "05973284973216824503042159", 2738 "1" 2739 }, 2740 { /* between second and third iteration */ 2741 "3789819583801342198190405714582958759005991915505282362397087750" 2742 "4213544724644823098843135685133927198668818185338794377239590049" 2743 "41019388529192775771488319", 2744 "6703903964971298549787012499102923063739682910296196688861780721" 2745 "8608820150367734884009371490834517138450159290932430254268769414" 2746 "05973284973216824503042158", 2747 "6703903964971298549787012499102923063739682910296196688861780721" 2748 "8608820150367734884009371490834517138450159290932430254268769414" 2749 "05973284973216824503042159", 2750 "1" 2751 }, 2752 { /* between third and forth iteration */ 2753 "4695752552040706867080542538786056470322165281761525158189220280" 2754 "4025547447667484759200742764246905647644662050122968912279199065" 2755 "48065034299166336940507214", 2756 "6703903964971298549787012499102923063739682910296196688861780721" 2757 "8608820150367734884009371490834517138450159290932430254268769414" 2758 "05973284973216824503042158", 2759 "6703903964971298549787012499102923063739682910296196688861780721" 2760 "8608820150367734884009371490834517138450159290932430254268769414" 2761 "05973284973216824503042159", 2762 "1" 2763 }, 2764 { /* between forth and fifth iteration */ 2765 "2159140240970485794188159431017382878636879856244045329971239574" 2766 "8919691133560661162828034323196457386059819832804593989740268964" 2767 "74502911811812651475927076", 2768 "6703903964971298549787012499102923063739682910296196688861780721" 2769 "8608820150367734884009371490834517138450159290932430254268769414" 2770 "05973284973216824503042158", 2771 "6703903964971298549787012499102923063739682910296196688861780721" 2772 "8608820150367734884009371490834517138450159290932430254268769414" 2773 "05973284973216824503042159", 2774 "1" 2775 }, 2776 { /* between fifth and sixth iteration */ 2777 "5239312332984325668414624633307915097111691815000872662334695514" 2778 "5436533521392362443557163429336808208137221322444780490437871903" 2779 "99972784701334569424519255", 2780 "6703903964971298549787012499102923063739682910296196688861780721" 2781 "8608820150367734884009371490834517138450159290932430254268769414" 2782 "05973284973216824503042158", 2783 "6703903964971298549787012499102923063739682910296196688861780721" 2784 "8608820150367734884009371490834517138450159290932430254268769414" 2785 "05973284973216824503042159", 2786 "1" 2787 }, 2788 { /* between sixth and seventh iteration */ 2789 "1977953647322612860406858017869125467496941904523063466791308891" 2790 "1172796739058531929470539758361774569875505293428856181093904091" 2791 "33788264851714311303725089", 2792 "6703903964971298549787012499102923063739682910296196688861780721" 2793 "8608820150367734884009371490834517138450159290932430254268769414" 2794 "05973284973216824503042158", 2795 "6703903964971298549787012499102923063739682910296196688861780721" 2796 "8608820150367734884009371490834517138450159290932430254268769414" 2797 "05973284973216824503042159", 2798 "1" 2799 }, 2800 { /* between seventh and eighth iteration */ 2801 "6456987954117763835533395796948878140715006860263624787492985786" 2802 "8514630216966738305923915688821526449499763719943997120302368211" 2803 "04813318117996225041943964", 2804 "1340780792994259709957402499820584612747936582059239337772356144" 2805 "3721764030073546976801874298166903427690031858186486050853753882" 2806 "811946551499689575296532556", 2807 "1340780792994259709957402499820584612747936582059239337772356144" 2808 "3721764030073546976801874298166903427690031858186486050853753882" 2809 "811946551499689575296532557", 2810 "1" 2811 } 2812}; 2813 2814static int test_mod_exp(int i) 2815{ 2816 const MOD_EXP_TEST *test = &ModExpTests[i]; 2817 int res = 0; 2818 BIGNUM* result = NULL; 2819 BIGNUM *base = NULL, *exponent = NULL, *modulo = NULL; 2820 char *s = NULL; 2821 2822 if (!TEST_ptr(result = BN_new()) 2823 || !TEST_true(BN_dec2bn(&base, test->base)) 2824 || !TEST_true(BN_dec2bn(&exponent, test->exp)) 2825 || !TEST_true(BN_dec2bn(&modulo, test->mod))) 2826 goto err; 2827 2828 if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1)) 2829 goto err; 2830 2831 if (!TEST_ptr(s = BN_bn2dec(result))) 2832 goto err; 2833 2834 if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res))) 2835 goto err; 2836 2837 res = 1; 2838 2839 err: 2840 OPENSSL_free(s); 2841 BN_free(result); 2842 BN_free(base); 2843 BN_free(exponent); 2844 BN_free(modulo); 2845 return res; 2846} 2847 2848static int test_mod_exp_consttime(int i) 2849{ 2850 const MOD_EXP_TEST *test = &ModExpTests[i]; 2851 int res = 0; 2852 BIGNUM* result = NULL; 2853 BIGNUM *base = NULL, *exponent = NULL, *modulo = NULL; 2854 char *s = NULL; 2855 2856 if (!TEST_ptr(result = BN_new()) 2857 || !TEST_true(BN_dec2bn(&base, test->base)) 2858 || !TEST_true(BN_dec2bn(&exponent, test->exp)) 2859 || !TEST_true(BN_dec2bn(&modulo, test->mod))) 2860 goto err; 2861 2862 BN_set_flags(base, BN_FLG_CONSTTIME); 2863 BN_set_flags(exponent, BN_FLG_CONSTTIME); 2864 BN_set_flags(modulo, BN_FLG_CONSTTIME); 2865 2866 if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1)) 2867 goto err; 2868 2869 if (!TEST_ptr(s = BN_bn2dec(result))) 2870 goto err; 2871 2872 if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res))) 2873 goto err; 2874 2875 res = 1; 2876 2877 err: 2878 OPENSSL_free(s); 2879 BN_free(result); 2880 BN_free(base); 2881 BN_free(exponent); 2882 BN_free(modulo); 2883 return res; 2884} 2885 2886/* 2887 * Regression test to ensure BN_mod_exp2_mont fails safely if argument m is 2888 * zero. 2889 */ 2890static int test_mod_exp2_mont(void) 2891{ 2892 int res = 0; 2893 BIGNUM *exp_result = NULL; 2894 BIGNUM *exp_a1 = NULL, *exp_p1 = NULL, *exp_a2 = NULL, *exp_p2 = NULL, 2895 *exp_m = NULL; 2896 2897 if (!TEST_ptr(exp_result = BN_new()) 2898 || !TEST_ptr(exp_a1 = BN_new()) 2899 || !TEST_ptr(exp_p1 = BN_new()) 2900 || !TEST_ptr(exp_a2 = BN_new()) 2901 || !TEST_ptr(exp_p2 = BN_new()) 2902 || !TEST_ptr(exp_m = BN_new())) 2903 goto err; 2904 2905 if (!TEST_true(BN_one(exp_a1)) 2906 || !TEST_true(BN_one(exp_p1)) 2907 || !TEST_true(BN_one(exp_a2)) 2908 || !TEST_true(BN_one(exp_p2))) 2909 goto err; 2910 2911 BN_zero(exp_m); 2912 2913 /* input of 0 is even, so must fail */ 2914 if (!TEST_int_eq(BN_mod_exp2_mont(exp_result, exp_a1, exp_p1, exp_a2, 2915 exp_p2, exp_m, ctx, NULL), 0)) 2916 goto err; 2917 2918 res = 1; 2919 2920err: 2921 BN_free(exp_result); 2922 BN_free(exp_a1); 2923 BN_free(exp_p1); 2924 BN_free(exp_a2); 2925 BN_free(exp_p2); 2926 BN_free(exp_m); 2927 return res; 2928} 2929 2930static int file_test_run(STANZA *s) 2931{ 2932 static const FILETEST filetests[] = { 2933 {"Sum", file_sum}, 2934 {"LShift1", file_lshift1}, 2935 {"LShift", file_lshift}, 2936 {"RShift", file_rshift}, 2937 {"Square", file_square}, 2938 {"Product", file_product}, 2939 {"Quotient", file_quotient}, 2940 {"ModMul", file_modmul}, 2941 {"ModExp", file_modexp}, 2942 {"Exp", file_exp}, 2943 {"ModSqrt", file_modsqrt}, 2944 {"GCD", file_gcd}, 2945 }; 2946 int numtests = OSSL_NELEM(filetests); 2947 const FILETEST *tp = filetests; 2948 2949 for ( ; --numtests >= 0; tp++) { 2950 if (findattr(s, tp->name) != NULL) { 2951 if (!tp->func(s)) { 2952 TEST_info("%s:%d: Failed %s test", 2953 s->test_file, s->start, tp->name); 2954 return 0; 2955 } 2956 return 1; 2957 } 2958 } 2959 TEST_info("%s:%d: Unknown test", s->test_file, s->start); 2960 return 0; 2961} 2962 2963static int run_file_tests(int i) 2964{ 2965 STANZA *s = NULL; 2966 char *testfile = test_get_argument(i); 2967 int c; 2968 2969 if (!TEST_ptr(s = OPENSSL_zalloc(sizeof(*s)))) 2970 return 0; 2971 if (!test_start_file(s, testfile)) { 2972 OPENSSL_free(s); 2973 return 0; 2974 } 2975 2976 /* Read test file. */ 2977 while (!BIO_eof(s->fp) && test_readstanza(s)) { 2978 if (s->numpairs == 0) 2979 continue; 2980 if (!file_test_run(s)) 2981 s->errors++; 2982 s->numtests++; 2983 test_clearstanza(s); 2984 } 2985 test_end_file(s); 2986 c = s->errors; 2987 OPENSSL_free(s); 2988 2989 return c == 0; 2990} 2991 2992typedef enum OPTION_choice { 2993 OPT_ERR = -1, 2994 OPT_EOF = 0, 2995 OPT_STOCHASTIC_TESTS, 2996 OPT_TEST_ENUM 2997} OPTION_CHOICE; 2998 2999const OPTIONS *test_get_options(void) 3000{ 3001 static const OPTIONS test_options[] = { 3002 OPT_TEST_OPTIONS_WITH_EXTRA_USAGE("[file...]\n"), 3003 { "stochastic", OPT_STOCHASTIC_TESTS, '-', "Run stochastic tests" }, 3004 { OPT_HELP_STR, 1, '-', 3005 "file\tFile to run tests on. Normal tests are not run\n" }, 3006 { NULL } 3007 }; 3008 return test_options; 3009} 3010 3011int setup_tests(void) 3012{ 3013 OPTION_CHOICE o; 3014 int n, stochastic = 0; 3015 3016 while ((o = opt_next()) != OPT_EOF) { 3017 switch (o) { 3018 case OPT_STOCHASTIC_TESTS: 3019 stochastic = 1; 3020 break; 3021 case OPT_TEST_CASES: 3022 break; 3023 default: 3024 case OPT_ERR: 3025 return 0; 3026 } 3027 } 3028 n = test_get_argument_count(); 3029 3030 if (!TEST_ptr(ctx = BN_CTX_new())) 3031 return 0; 3032 3033 if (n == 0) { 3034 ADD_TEST(test_sub); 3035 ADD_TEST(test_div_recip); 3036 ADD_ALL_TESTS(test_signed_mod_replace_ab, OSSL_NELEM(signed_mod_tests)); 3037 ADD_ALL_TESTS(test_signed_mod_replace_ba, OSSL_NELEM(signed_mod_tests)); 3038 ADD_TEST(test_mod); 3039 ADD_TEST(test_modexp_mont5); 3040 ADD_TEST(test_kronecker); 3041 ADD_TEST(test_rand); 3042 ADD_TEST(test_bn2padded); 3043 ADD_TEST(test_dec2bn); 3044 ADD_TEST(test_hex2bn); 3045 ADD_TEST(test_asc2bn); 3046 ADD_ALL_TESTS(test_mpi, (int)OSSL_NELEM(kMPITests)); 3047 ADD_TEST(test_negzero); 3048 ADD_TEST(test_badmod); 3049 ADD_TEST(test_expmodzero); 3050 ADD_TEST(test_expmodone); 3051 ADD_ALL_TESTS(test_smallprime, 16); 3052 ADD_ALL_TESTS(test_smallsafeprime, 16); 3053 ADD_TEST(test_swap); 3054 ADD_TEST(test_ctx_consttime_flag); 3055#ifndef OPENSSL_NO_EC2M 3056 ADD_TEST(test_gf2m_add); 3057 ADD_TEST(test_gf2m_mod); 3058 ADD_TEST(test_gf2m_mul); 3059 ADD_TEST(test_gf2m_sqr); 3060 ADD_TEST(test_gf2m_modinv); 3061 ADD_TEST(test_gf2m_moddiv); 3062 ADD_TEST(test_gf2m_modexp); 3063 ADD_TEST(test_gf2m_modsqrt); 3064 ADD_TEST(test_gf2m_modsolvequad); 3065#endif 3066 ADD_ALL_TESTS(test_is_prime, (int)OSSL_NELEM(primes)); 3067 ADD_ALL_TESTS(test_not_prime, (int)OSSL_NELEM(not_primes)); 3068 ADD_TEST(test_gcd_prime); 3069 ADD_ALL_TESTS(test_mod_exp, (int)OSSL_NELEM(ModExpTests)); 3070 ADD_ALL_TESTS(test_mod_exp_consttime, (int)OSSL_NELEM(ModExpTests)); 3071 ADD_TEST(test_mod_exp2_mont); 3072 if (stochastic) 3073 ADD_TEST(test_rand_range); 3074 } else { 3075 ADD_ALL_TESTS(run_file_tests, n); 3076 } 3077 return 1; 3078} 3079 3080void cleanup_tests(void) 3081{ 3082 BN_CTX_free(ctx); 3083} 3084