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 28 typedef struct filetest_st { 29 const char *name; 30 int (*func)(STANZA *s); 31 } FILETEST; 32 33 typedef struct mpitest_st { 34 const char *base10; 35 const char *mpi; 36 size_t mpi_len; 37 } MPITEST; 38 39 static const int NUM0 = 100; /* number of tests */ 40 static const int NUM1 = 50; /* additional tests for some functions */ 41 static BN_CTX *ctx; 42 43 /* 44 * Polynomial coefficients used in GFM tests. 45 */ 46 #ifndef OPENSSL_NO_EC2M 47 static int p0[] = { 163, 7, 6, 3, 0, -1 }; 48 static 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 */ 54 static 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 */ 68 static 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 */ 80 static int parseBN(BIGNUM **out, const char *in) 81 { 82 *out = NULL; 83 return BN_hex2bn(out, in); 84 } 85 86 static int parsedecBN(BIGNUM **out, const char *in) 87 { 88 *out = NULL; 89 return BN_dec2bn(out, in); 90 } 91 92 static 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 109 static 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 126 static 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 */ 139 static 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 147 static 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 220 static 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 257 static 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 303 static 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 312 static 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 326 static 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 349 static 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 372 static 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 409 static 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 429 static 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 */ 453 static 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 716 static 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 750 static 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 790 static 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 843 static 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 882 static 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 /* Test that a non-sensical, too small value causes a failure */ 895 if (!TEST_true(BN_one(b[0]))) 896 goto err; 897 if (!TEST_true(BN_bntest_rand(a, 512, 0, 0))) 898 goto err; 899 if (!TEST_false(BN_GF2m_mod_inv(c, a, b[0], ctx))) 900 goto err; 901 902 if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0])) 903 && TEST_true(BN_GF2m_arr2poly(p1, b[1])))) 904 goto err; 905 906 for (i = 0; i < NUM0; i++) { 907 if (!TEST_true(BN_bntest_rand(a, 512, 0, 0))) 908 goto err; 909 for (j = 0; j < 2; j++) { 910 if (!(TEST_true(BN_GF2m_mod_inv(c, a, b[j], ctx)) 911 && TEST_true(BN_GF2m_mod_mul(d, a, c, b[j], ctx)) 912 /* Test that ((1/a)*a) = 1. */ 913 && TEST_BN_eq_one(d))) 914 goto err; 915 } 916 } 917 st = 1; 918 err: 919 BN_free(a); 920 BN_free(b[0]); 921 BN_free(b[1]); 922 BN_free(c); 923 BN_free(d); 924 return st; 925 } 926 927 static int test_gf2m_moddiv(void) 928 { 929 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL; 930 BIGNUM *e = NULL, *f = NULL; 931 int i, j, st = 0; 932 933 if (!TEST_ptr(a = BN_new()) 934 || !TEST_ptr(b[0] = BN_new()) 935 || !TEST_ptr(b[1] = BN_new()) 936 || !TEST_ptr(c = BN_new()) 937 || !TEST_ptr(d = BN_new()) 938 || !TEST_ptr(e = BN_new()) 939 || !TEST_ptr(f = BN_new())) 940 goto err; 941 942 if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0])) 943 && TEST_true(BN_GF2m_arr2poly(p1, b[1])))) 944 goto err; 945 946 for (i = 0; i < NUM0; i++) { 947 if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0)) 948 && TEST_true(BN_bntest_rand(c, 512, 0, 0)))) 949 goto err; 950 for (j = 0; j < 2; j++) { 951 if (!(TEST_true(BN_GF2m_mod_div(d, a, c, b[j], ctx)) 952 && TEST_true(BN_GF2m_mod_mul(e, d, c, b[j], ctx)) 953 && TEST_true(BN_GF2m_mod_div(f, a, e, b[j], ctx)) 954 /* Test that ((a/c)*c)/a = 1. */ 955 && TEST_BN_eq_one(f))) 956 goto err; 957 } 958 } 959 st = 1; 960 err: 961 BN_free(a); 962 BN_free(b[0]); 963 BN_free(b[1]); 964 BN_free(c); 965 BN_free(d); 966 BN_free(e); 967 BN_free(f); 968 return st; 969 } 970 971 static int test_gf2m_modexp(void) 972 { 973 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL; 974 BIGNUM *e = NULL, *f = NULL; 975 int i, j, st = 0; 976 977 if (!TEST_ptr(a = BN_new()) 978 || !TEST_ptr(b[0] = BN_new()) 979 || !TEST_ptr(b[1] = BN_new()) 980 || !TEST_ptr(c = BN_new()) 981 || !TEST_ptr(d = BN_new()) 982 || !TEST_ptr(e = BN_new()) 983 || !TEST_ptr(f = BN_new())) 984 goto err; 985 986 if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0])) 987 && TEST_true(BN_GF2m_arr2poly(p1, b[1])))) 988 goto err; 989 990 for (i = 0; i < NUM0; i++) { 991 if (!(TEST_true(BN_bntest_rand(a, 512, 0, 0)) 992 && TEST_true(BN_bntest_rand(c, 512, 0, 0)) 993 && TEST_true(BN_bntest_rand(d, 512, 0, 0)))) 994 goto err; 995 for (j = 0; j < 2; j++) { 996 if (!(TEST_true(BN_GF2m_mod_exp(e, a, c, b[j], ctx)) 997 && TEST_true(BN_GF2m_mod_exp(f, a, d, b[j], ctx)) 998 && TEST_true(BN_GF2m_mod_mul(e, e, f, b[j], ctx)) 999 && TEST_true(BN_add(f, c, d)) 1000 && TEST_true(BN_GF2m_mod_exp(f, a, f, b[j], ctx)) 1001 && TEST_true(BN_GF2m_add(f, e, f)) 1002 /* Test that a^(c+d)=a^c*a^d. */ 1003 && TEST_BN_eq_zero(f))) 1004 goto err; 1005 } 1006 } 1007 st = 1; 1008 err: 1009 BN_free(a); 1010 BN_free(b[0]); 1011 BN_free(b[1]); 1012 BN_free(c); 1013 BN_free(d); 1014 BN_free(e); 1015 BN_free(f); 1016 return st; 1017 } 1018 1019 static int test_gf2m_modsqrt(void) 1020 { 1021 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL; 1022 BIGNUM *e = NULL, *f = NULL; 1023 int i, j, st = 0; 1024 1025 if (!TEST_ptr(a = BN_new()) 1026 || !TEST_ptr(b[0] = BN_new()) 1027 || !TEST_ptr(b[1] = BN_new()) 1028 || !TEST_ptr(c = BN_new()) 1029 || !TEST_ptr(d = BN_new()) 1030 || !TEST_ptr(e = BN_new()) 1031 || !TEST_ptr(f = BN_new())) 1032 goto err; 1033 1034 if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0])) 1035 && TEST_true(BN_GF2m_arr2poly(p1, b[1])))) 1036 goto err; 1037 1038 for (i = 0; i < NUM0; i++) { 1039 if (!TEST_true(BN_bntest_rand(a, 512, 0, 0))) 1040 goto err; 1041 1042 for (j = 0; j < 2; j++) { 1043 if (!(TEST_true(BN_GF2m_mod(c, a, b[j])) 1044 && TEST_true(BN_GF2m_mod_sqrt(d, a, b[j], ctx)) 1045 && TEST_true(BN_GF2m_mod_sqr(e, d, b[j], ctx)) 1046 && TEST_true(BN_GF2m_add(f, c, e)) 1047 /* Test that d^2 = a, where d = sqrt(a). */ 1048 && TEST_BN_eq_zero(f))) 1049 goto err; 1050 } 1051 } 1052 st = 1; 1053 err: 1054 BN_free(a); 1055 BN_free(b[0]); 1056 BN_free(b[1]); 1057 BN_free(c); 1058 BN_free(d); 1059 BN_free(e); 1060 BN_free(f); 1061 return st; 1062 } 1063 1064 static int test_gf2m_modsolvequad(void) 1065 { 1066 BIGNUM *a = NULL, *b[2] = {NULL,NULL}, *c = NULL, *d = NULL; 1067 BIGNUM *e = NULL; 1068 int i, j, s = 0, t, st = 0; 1069 1070 if (!TEST_ptr(a = BN_new()) 1071 || !TEST_ptr(b[0] = BN_new()) 1072 || !TEST_ptr(b[1] = BN_new()) 1073 || !TEST_ptr(c = BN_new()) 1074 || !TEST_ptr(d = BN_new()) 1075 || !TEST_ptr(e = BN_new())) 1076 goto err; 1077 1078 if (!(TEST_true(BN_GF2m_arr2poly(p0, b[0])) 1079 && TEST_true(BN_GF2m_arr2poly(p1, b[1])))) 1080 goto err; 1081 1082 for (i = 0; i < NUM0; i++) { 1083 if (!TEST_true(BN_bntest_rand(a, 512, 0, 0))) 1084 goto err; 1085 for (j = 0; j < 2; j++) { 1086 t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx); 1087 if (t) { 1088 s++; 1089 if (!(TEST_true(BN_GF2m_mod_sqr(d, c, b[j], ctx)) 1090 && TEST_true(BN_GF2m_add(d, c, d)) 1091 && TEST_true(BN_GF2m_mod(e, a, b[j])) 1092 && TEST_true(BN_GF2m_add(e, e, d)) 1093 /* 1094 * Test that solution of quadratic c 1095 * satisfies c^2 + c = a. 1096 */ 1097 && TEST_BN_eq_zero(e))) 1098 goto err; 1099 } 1100 } 1101 } 1102 if (!TEST_int_ge(s, 0)) { 1103 TEST_info("%d tests found no roots; probably an error", NUM0); 1104 goto err; 1105 } 1106 st = 1; 1107 err: 1108 BN_free(a); 1109 BN_free(b[0]); 1110 BN_free(b[1]); 1111 BN_free(c); 1112 BN_free(d); 1113 BN_free(e); 1114 return st; 1115 } 1116 #endif 1117 1118 static int test_kronecker(void) 1119 { 1120 BIGNUM *a = NULL, *b = NULL, *r = NULL, *t = NULL; 1121 int i, legendre, kronecker, st = 0; 1122 1123 if (!TEST_ptr(a = BN_new()) 1124 || !TEST_ptr(b = BN_new()) 1125 || !TEST_ptr(r = BN_new()) 1126 || !TEST_ptr(t = BN_new())) 1127 goto err; 1128 1129 /* 1130 * We test BN_kronecker(a, b, ctx) just for b odd (Jacobi symbol). In 1131 * this case we know that if b is prime, then BN_kronecker(a, b, ctx) is 1132 * congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol). So we 1133 * generate a random prime b and compare these values for a number of 1134 * random a's. (That is, we run the Solovay-Strassen primality test to 1135 * confirm that b is prime, except that we don't want to test whether b 1136 * is prime but whether BN_kronecker works.) 1137 */ 1138 1139 if (!TEST_true(BN_generate_prime_ex(b, 512, 0, NULL, NULL, NULL))) 1140 goto err; 1141 BN_set_negative(b, rand_neg()); 1142 1143 for (i = 0; i < NUM0; i++) { 1144 if (!TEST_true(BN_bntest_rand(a, 512, 0, 0))) 1145 goto err; 1146 BN_set_negative(a, rand_neg()); 1147 1148 /* t := (|b|-1)/2 (note that b is odd) */ 1149 if (!TEST_true(BN_copy(t, b))) 1150 goto err; 1151 BN_set_negative(t, 0); 1152 if (!TEST_true(BN_sub_word(t, 1))) 1153 goto err; 1154 if (!TEST_true(BN_rshift1(t, t))) 1155 goto err; 1156 /* r := a^t mod b */ 1157 BN_set_negative(b, 0); 1158 1159 if (!TEST_true(BN_mod_exp_recp(r, a, t, b, ctx))) 1160 goto err; 1161 BN_set_negative(b, 1); 1162 1163 if (BN_is_word(r, 1)) 1164 legendre = 1; 1165 else if (BN_is_zero(r)) 1166 legendre = 0; 1167 else { 1168 if (!TEST_true(BN_add_word(r, 1))) 1169 goto err; 1170 if (!TEST_int_eq(BN_ucmp(r, b), 0)) { 1171 TEST_info("Legendre symbol computation failed"); 1172 goto err; 1173 } 1174 legendre = -1; 1175 } 1176 1177 if (!TEST_int_ge(kronecker = BN_kronecker(a, b, ctx), -1)) 1178 goto err; 1179 /* we actually need BN_kronecker(a, |b|) */ 1180 if (BN_is_negative(a) && BN_is_negative(b)) 1181 kronecker = -kronecker; 1182 1183 if (!TEST_int_eq(legendre, kronecker)) 1184 goto err; 1185 } 1186 1187 st = 1; 1188 err: 1189 BN_free(a); 1190 BN_free(b); 1191 BN_free(r); 1192 BN_free(t); 1193 return st; 1194 } 1195 1196 static int file_sum(STANZA *s) 1197 { 1198 BIGNUM *a = NULL, *b = NULL, *sum = NULL, *ret = NULL; 1199 BN_ULONG b_word; 1200 int st = 0; 1201 1202 if (!TEST_ptr(a = getBN(s, "A")) 1203 || !TEST_ptr(b = getBN(s, "B")) 1204 || !TEST_ptr(sum = getBN(s, "Sum")) 1205 || !TEST_ptr(ret = BN_new())) 1206 goto err; 1207 1208 if (!TEST_true(BN_add(ret, a, b)) 1209 || !equalBN("A + B", sum, ret) 1210 || !TEST_true(BN_sub(ret, sum, a)) 1211 || !equalBN("Sum - A", b, ret) 1212 || !TEST_true(BN_sub(ret, sum, b)) 1213 || !equalBN("Sum - B", a, ret)) 1214 goto err; 1215 1216 /* 1217 * Test that the functions work when |r| and |a| point to the same BIGNUM, 1218 * or when |r| and |b| point to the same BIGNUM. 1219 * There is no test for all of |r|, |a|, and |b| pointint to the same BIGNUM. 1220 */ 1221 if (!TEST_true(BN_copy(ret, a)) 1222 || !TEST_true(BN_add(ret, ret, b)) 1223 || !equalBN("A + B (r is a)", sum, ret) 1224 || !TEST_true(BN_copy(ret, b)) 1225 || !TEST_true(BN_add(ret, a, ret)) 1226 || !equalBN("A + B (r is b)", sum, ret) 1227 || !TEST_true(BN_copy(ret, sum)) 1228 || !TEST_true(BN_sub(ret, ret, a)) 1229 || !equalBN("Sum - A (r is a)", b, ret) 1230 || !TEST_true(BN_copy(ret, a)) 1231 || !TEST_true(BN_sub(ret, sum, ret)) 1232 || !equalBN("Sum - A (r is b)", b, ret) 1233 || !TEST_true(BN_copy(ret, sum)) 1234 || !TEST_true(BN_sub(ret, ret, b)) 1235 || !equalBN("Sum - B (r is a)", a, ret) 1236 || !TEST_true(BN_copy(ret, b)) 1237 || !TEST_true(BN_sub(ret, sum, ret)) 1238 || !equalBN("Sum - B (r is b)", a, ret)) 1239 goto err; 1240 1241 /* 1242 * Test BN_uadd() and BN_usub() with the prerequisites they are 1243 * documented as having. Note that these functions are frequently used 1244 * when the prerequisites don't hold. In those cases, they are supposed 1245 * to work as if the prerequisite hold, but we don't test that yet. 1246 */ 1247 if (!BN_is_negative(a) && !BN_is_negative(b) && BN_cmp(a, b) >= 0) { 1248 if (!TEST_true(BN_uadd(ret, a, b)) 1249 || !equalBN("A +u B", sum, ret) 1250 || !TEST_true(BN_usub(ret, sum, a)) 1251 || !equalBN("Sum -u A", b, ret) 1252 || !TEST_true(BN_usub(ret, sum, b)) 1253 || !equalBN("Sum -u B", a, ret)) 1254 goto err; 1255 /* 1256 * Test that the functions work when |r| and |a| point to the same 1257 * BIGNUM, or when |r| and |b| point to the same BIGNUM. 1258 * There is no test for all of |r|, |a|, and |b| pointint to the same 1259 * BIGNUM. 1260 */ 1261 if (!TEST_true(BN_copy(ret, a)) 1262 || !TEST_true(BN_uadd(ret, ret, b)) 1263 || !equalBN("A +u B (r is a)", sum, ret) 1264 || !TEST_true(BN_copy(ret, b)) 1265 || !TEST_true(BN_uadd(ret, a, ret)) 1266 || !equalBN("A +u B (r is b)", sum, ret) 1267 || !TEST_true(BN_copy(ret, sum)) 1268 || !TEST_true(BN_usub(ret, ret, a)) 1269 || !equalBN("Sum -u A (r is a)", b, ret) 1270 || !TEST_true(BN_copy(ret, a)) 1271 || !TEST_true(BN_usub(ret, sum, ret)) 1272 || !equalBN("Sum -u A (r is b)", b, ret) 1273 || !TEST_true(BN_copy(ret, sum)) 1274 || !TEST_true(BN_usub(ret, ret, b)) 1275 || !equalBN("Sum -u B (r is a)", a, ret) 1276 || !TEST_true(BN_copy(ret, b)) 1277 || !TEST_true(BN_usub(ret, sum, ret)) 1278 || !equalBN("Sum -u B (r is b)", a, ret)) 1279 goto err; 1280 } 1281 1282 /* 1283 * Test with BN_add_word() and BN_sub_word() if |b| is small enough. 1284 */ 1285 b_word = BN_get_word(b); 1286 if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) { 1287 if (!TEST_true(BN_copy(ret, a)) 1288 || !TEST_true(BN_add_word(ret, b_word)) 1289 || !equalBN("A + B (word)", sum, ret) 1290 || !TEST_true(BN_copy(ret, sum)) 1291 || !TEST_true(BN_sub_word(ret, b_word)) 1292 || !equalBN("Sum - B (word)", a, ret)) 1293 goto err; 1294 } 1295 st = 1; 1296 1297 err: 1298 BN_free(a); 1299 BN_free(b); 1300 BN_free(sum); 1301 BN_free(ret); 1302 return st; 1303 } 1304 1305 static int file_lshift1(STANZA *s) 1306 { 1307 BIGNUM *a = NULL, *lshift1 = NULL, *zero = NULL, *ret = NULL; 1308 BIGNUM *two = NULL, *remainder = NULL; 1309 int st = 0; 1310 1311 if (!TEST_ptr(a = getBN(s, "A")) 1312 || !TEST_ptr(lshift1 = getBN(s, "LShift1")) 1313 || !TEST_ptr(zero = BN_new()) 1314 || !TEST_ptr(ret = BN_new()) 1315 || !TEST_ptr(two = BN_new()) 1316 || !TEST_ptr(remainder = BN_new())) 1317 goto err; 1318 1319 BN_zero(zero); 1320 1321 if (!TEST_true(BN_set_word(two, 2)) 1322 || !TEST_true(BN_add(ret, a, a)) 1323 || !equalBN("A + A", lshift1, ret) 1324 || !TEST_true(BN_mul(ret, a, two, ctx)) 1325 || !equalBN("A * 2", lshift1, ret) 1326 || !TEST_true(BN_div(ret, remainder, lshift1, two, ctx)) 1327 || !equalBN("LShift1 / 2", a, ret) 1328 || !equalBN("LShift1 % 2", zero, remainder) 1329 || !TEST_true(BN_lshift1(ret, a)) 1330 || !equalBN("A << 1", lshift1, ret) 1331 || !TEST_true(BN_rshift1(ret, lshift1)) 1332 || !equalBN("LShift >> 1", a, ret) 1333 || !TEST_true(BN_rshift1(ret, lshift1)) 1334 || !equalBN("LShift >> 1", a, ret)) 1335 goto err; 1336 1337 /* Set the LSB to 1 and test rshift1 again. */ 1338 if (!TEST_true(BN_set_bit(lshift1, 0)) 1339 || !TEST_true(BN_div(ret, NULL /* rem */ , lshift1, two, ctx)) 1340 || !equalBN("(LShift1 | 1) / 2", a, ret) 1341 || !TEST_true(BN_rshift1(ret, lshift1)) 1342 || !equalBN("(LShift | 1) >> 1", a, ret)) 1343 goto err; 1344 1345 st = 1; 1346 err: 1347 BN_free(a); 1348 BN_free(lshift1); 1349 BN_free(zero); 1350 BN_free(ret); 1351 BN_free(two); 1352 BN_free(remainder); 1353 1354 return st; 1355 } 1356 1357 static int file_lshift(STANZA *s) 1358 { 1359 BIGNUM *a = NULL, *lshift = NULL, *ret = NULL; 1360 int n = 0, st = 0; 1361 1362 if (!TEST_ptr(a = getBN(s, "A")) 1363 || !TEST_ptr(lshift = getBN(s, "LShift")) 1364 || !TEST_ptr(ret = BN_new()) 1365 || !getint(s, &n, "N")) 1366 goto err; 1367 1368 if (!TEST_true(BN_lshift(ret, a, n)) 1369 || !equalBN("A << N", lshift, ret) 1370 || !TEST_true(BN_rshift(ret, lshift, n)) 1371 || !equalBN("A >> N", a, ret)) 1372 goto err; 1373 1374 st = 1; 1375 err: 1376 BN_free(a); 1377 BN_free(lshift); 1378 BN_free(ret); 1379 return st; 1380 } 1381 1382 static int file_rshift(STANZA *s) 1383 { 1384 BIGNUM *a = NULL, *rshift = NULL, *ret = NULL; 1385 int n = 0, st = 0; 1386 1387 if (!TEST_ptr(a = getBN(s, "A")) 1388 || !TEST_ptr(rshift = getBN(s, "RShift")) 1389 || !TEST_ptr(ret = BN_new()) 1390 || !getint(s, &n, "N")) 1391 goto err; 1392 1393 if (!TEST_true(BN_rshift(ret, a, n)) 1394 || !equalBN("A >> N", rshift, ret)) 1395 goto err; 1396 1397 /* If N == 1, try with rshift1 as well */ 1398 if (n == 1) { 1399 if (!TEST_true(BN_rshift1(ret, a)) 1400 || !equalBN("A >> 1 (rshift1)", rshift, ret)) 1401 goto err; 1402 } 1403 st = 1; 1404 1405 err: 1406 BN_free(a); 1407 BN_free(rshift); 1408 BN_free(ret); 1409 return st; 1410 } 1411 1412 static int file_square(STANZA *s) 1413 { 1414 BIGNUM *a = NULL, *square = NULL, *zero = NULL, *ret = NULL; 1415 BIGNUM *remainder = NULL, *tmp = NULL; 1416 int st = 0; 1417 1418 if (!TEST_ptr(a = getBN(s, "A")) 1419 || !TEST_ptr(square = getBN(s, "Square")) 1420 || !TEST_ptr(zero = BN_new()) 1421 || !TEST_ptr(ret = BN_new()) 1422 || !TEST_ptr(remainder = BN_new())) 1423 goto err; 1424 1425 BN_zero(zero); 1426 if (!TEST_true(BN_sqr(ret, a, ctx)) 1427 || !equalBN("A^2", square, ret) 1428 || !TEST_true(BN_mul(ret, a, a, ctx)) 1429 || !equalBN("A * A", square, ret) 1430 || !TEST_true(BN_div(ret, remainder, square, a, ctx)) 1431 || !equalBN("Square / A", a, ret) 1432 || !equalBN("Square % A", zero, remainder)) 1433 goto err; 1434 1435 #if HAVE_BN_SQRT 1436 BN_set_negative(a, 0); 1437 if (!TEST_true(BN_sqrt(ret, square, ctx)) 1438 || !equalBN("sqrt(Square)", a, ret)) 1439 goto err; 1440 1441 /* BN_sqrt should fail on non-squares and negative numbers. */ 1442 if (!TEST_BN_eq_zero(square)) { 1443 if (!TEST_ptr(tmp = BN_new()) 1444 || !TEST_true(BN_copy(tmp, square))) 1445 goto err; 1446 BN_set_negative(tmp, 1); 1447 1448 if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx), 0)) 1449 goto err; 1450 ERR_clear_error(); 1451 1452 BN_set_negative(tmp, 0); 1453 if (BN_add(tmp, tmp, BN_value_one())) 1454 goto err; 1455 if (!TEST_int_eq(BN_sqrt(ret, tmp, ctx))) 1456 goto err; 1457 ERR_clear_error(); 1458 } 1459 #endif 1460 1461 st = 1; 1462 err: 1463 BN_free(a); 1464 BN_free(square); 1465 BN_free(zero); 1466 BN_free(ret); 1467 BN_free(remainder); 1468 BN_free(tmp); 1469 return st; 1470 } 1471 1472 static int file_product(STANZA *s) 1473 { 1474 BIGNUM *a = NULL, *b = NULL, *product = NULL, *ret = NULL; 1475 BIGNUM *remainder = NULL, *zero = NULL; 1476 int st = 0; 1477 1478 if (!TEST_ptr(a = getBN(s, "A")) 1479 || !TEST_ptr(b = getBN(s, "B")) 1480 || !TEST_ptr(product = getBN(s, "Product")) 1481 || !TEST_ptr(ret = BN_new()) 1482 || !TEST_ptr(remainder = BN_new()) 1483 || !TEST_ptr(zero = BN_new())) 1484 goto err; 1485 1486 BN_zero(zero); 1487 1488 if (!TEST_true(BN_mul(ret, a, b, ctx)) 1489 || !equalBN("A * B", product, ret) 1490 || !TEST_true(BN_div(ret, remainder, product, a, ctx)) 1491 || !equalBN("Product / A", b, ret) 1492 || !equalBN("Product % A", zero, remainder) 1493 || !TEST_true(BN_div(ret, remainder, product, b, ctx)) 1494 || !equalBN("Product / B", a, ret) 1495 || !equalBN("Product % B", zero, remainder)) 1496 goto err; 1497 1498 st = 1; 1499 err: 1500 BN_free(a); 1501 BN_free(b); 1502 BN_free(product); 1503 BN_free(ret); 1504 BN_free(remainder); 1505 BN_free(zero); 1506 return st; 1507 } 1508 1509 static int file_quotient(STANZA *s) 1510 { 1511 BIGNUM *a = NULL, *b = NULL, *quotient = NULL, *remainder = NULL; 1512 BIGNUM *ret = NULL, *ret2 = NULL, *nnmod = NULL; 1513 BN_ULONG b_word, ret_word; 1514 int st = 0; 1515 1516 if (!TEST_ptr(a = getBN(s, "A")) 1517 || !TEST_ptr(b = getBN(s, "B")) 1518 || !TEST_ptr(quotient = getBN(s, "Quotient")) 1519 || !TEST_ptr(remainder = getBN(s, "Remainder")) 1520 || !TEST_ptr(ret = BN_new()) 1521 || !TEST_ptr(ret2 = BN_new()) 1522 || !TEST_ptr(nnmod = BN_new())) 1523 goto err; 1524 1525 if (!TEST_true(BN_div(ret, ret2, a, b, ctx)) 1526 || !equalBN("A / B", quotient, ret) 1527 || !equalBN("A % B", remainder, ret2) 1528 || !TEST_true(BN_mul(ret, quotient, b, ctx)) 1529 || !TEST_true(BN_add(ret, ret, remainder)) 1530 || !equalBN("Quotient * B + Remainder", a, ret)) 1531 goto err; 1532 1533 /* 1534 * Test with BN_mod_word() and BN_div_word() if the divisor is 1535 * small enough. 1536 */ 1537 b_word = BN_get_word(b); 1538 if (!BN_is_negative(b) && b_word != (BN_ULONG)-1) { 1539 BN_ULONG remainder_word = BN_get_word(remainder); 1540 1541 assert(remainder_word != (BN_ULONG)-1); 1542 if (!TEST_ptr(BN_copy(ret, a))) 1543 goto err; 1544 ret_word = BN_div_word(ret, b_word); 1545 if (ret_word != remainder_word) { 1546 #ifdef BN_DEC_FMT1 1547 TEST_error( 1548 "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1, 1549 ret_word, remainder_word); 1550 #else 1551 TEST_error("Got A %% B (word) mismatch"); 1552 #endif 1553 goto err; 1554 } 1555 if (!equalBN ("A / B (word)", quotient, ret)) 1556 goto err; 1557 1558 ret_word = BN_mod_word(a, b_word); 1559 if (ret_word != remainder_word) { 1560 #ifdef BN_DEC_FMT1 1561 TEST_error( 1562 "Got A %% B (word) = " BN_DEC_FMT1 ", wanted " BN_DEC_FMT1 "", 1563 ret_word, remainder_word); 1564 #else 1565 TEST_error("Got A %% B (word) mismatch"); 1566 #endif 1567 goto err; 1568 } 1569 } 1570 1571 /* Test BN_nnmod. */ 1572 if (!BN_is_negative(b)) { 1573 if (!TEST_true(BN_copy(nnmod, remainder)) 1574 || (BN_is_negative(nnmod) 1575 && !TEST_true(BN_add(nnmod, nnmod, b))) 1576 || !TEST_true(BN_nnmod(ret, a, b, ctx)) 1577 || !equalBN("A % B (non-negative)", nnmod, ret)) 1578 goto err; 1579 } 1580 1581 st = 1; 1582 err: 1583 BN_free(a); 1584 BN_free(b); 1585 BN_free(quotient); 1586 BN_free(remainder); 1587 BN_free(ret); 1588 BN_free(ret2); 1589 BN_free(nnmod); 1590 return st; 1591 } 1592 1593 static int file_modmul(STANZA *s) 1594 { 1595 BIGNUM *a = NULL, *b = NULL, *m = NULL, *mod_mul = NULL, *ret = NULL; 1596 int st = 0; 1597 1598 if (!TEST_ptr(a = getBN(s, "A")) 1599 || !TEST_ptr(b = getBN(s, "B")) 1600 || !TEST_ptr(m = getBN(s, "M")) 1601 || !TEST_ptr(mod_mul = getBN(s, "ModMul")) 1602 || !TEST_ptr(ret = BN_new())) 1603 goto err; 1604 1605 if (!TEST_true(BN_mod_mul(ret, a, b, m, ctx)) 1606 || !equalBN("A * B (mod M)", mod_mul, ret)) 1607 goto err; 1608 1609 if (BN_is_odd(m)) { 1610 /* Reduce |a| and |b| and test the Montgomery version. */ 1611 BN_MONT_CTX *mont = BN_MONT_CTX_new(); 1612 BIGNUM *a_tmp = BN_new(); 1613 BIGNUM *b_tmp = BN_new(); 1614 1615 if (mont == NULL || a_tmp == NULL || b_tmp == NULL 1616 || !TEST_true(BN_MONT_CTX_set(mont, m, ctx)) 1617 || !TEST_true(BN_nnmod(a_tmp, a, m, ctx)) 1618 || !TEST_true(BN_nnmod(b_tmp, b, m, ctx)) 1619 || !TEST_true(BN_to_montgomery(a_tmp, a_tmp, mont, ctx)) 1620 || !TEST_true(BN_to_montgomery(b_tmp, b_tmp, mont, ctx)) 1621 || !TEST_true(BN_mod_mul_montgomery(ret, a_tmp, b_tmp, 1622 mont, ctx)) 1623 || !TEST_true(BN_from_montgomery(ret, ret, mont, ctx)) 1624 || !equalBN("A * B (mod M) (mont)", mod_mul, ret)) 1625 st = 0; 1626 else 1627 st = 1; 1628 BN_MONT_CTX_free(mont); 1629 BN_free(a_tmp); 1630 BN_free(b_tmp); 1631 if (st == 0) 1632 goto err; 1633 } 1634 1635 st = 1; 1636 err: 1637 BN_free(a); 1638 BN_free(b); 1639 BN_free(m); 1640 BN_free(mod_mul); 1641 BN_free(ret); 1642 return st; 1643 } 1644 1645 static int file_modexp(STANZA *s) 1646 { 1647 BIGNUM *a = NULL, *e = NULL, *m = NULL, *mod_exp = NULL, *ret = NULL; 1648 BIGNUM *b = NULL, *c = NULL, *d = NULL; 1649 int st = 0; 1650 1651 if (!TEST_ptr(a = getBN(s, "A")) 1652 || !TEST_ptr(e = getBN(s, "E")) 1653 || !TEST_ptr(m = getBN(s, "M")) 1654 || !TEST_ptr(mod_exp = getBN(s, "ModExp")) 1655 || !TEST_ptr(ret = BN_new()) 1656 || !TEST_ptr(d = BN_new())) 1657 goto err; 1658 1659 if (!TEST_true(BN_mod_exp(ret, a, e, m, ctx)) 1660 || !equalBN("A ^ E (mod M)", mod_exp, ret)) 1661 goto err; 1662 1663 if (BN_is_odd(m)) { 1664 if (!TEST_true(BN_mod_exp_mont(ret, a, e, m, ctx, NULL)) 1665 || !equalBN("A ^ E (mod M) (mont)", mod_exp, ret) 1666 || !TEST_true(BN_mod_exp_mont_consttime(ret, a, e, m, 1667 ctx, NULL)) 1668 || !equalBN("A ^ E (mod M) (mont const", mod_exp, ret)) 1669 goto err; 1670 } 1671 1672 /* Regression test for carry propagation bug in sqr8x_reduction */ 1673 BN_hex2bn(&a, "050505050505"); 1674 BN_hex2bn(&b, "02"); 1675 BN_hex2bn(&c, 1676 "4141414141414141414141274141414141414141414141414141414141414141" 1677 "4141414141414141414141414141414141414141414141414141414141414141" 1678 "4141414141414141414141800000000000000000000000000000000000000000" 1679 "0000000000000000000000000000000000000000000000000000000000000000" 1680 "0000000000000000000000000000000000000000000000000000000000000000" 1681 "0000000000000000000000000000000000000000000000000000000001"); 1682 if (!TEST_true(BN_mod_exp(d, a, b, c, ctx)) 1683 || !TEST_true(BN_mul(e, a, a, ctx)) 1684 || !TEST_BN_eq(d, e)) 1685 goto err; 1686 1687 st = 1; 1688 err: 1689 BN_free(a); 1690 BN_free(b); 1691 BN_free(c); 1692 BN_free(d); 1693 BN_free(e); 1694 BN_free(m); 1695 BN_free(mod_exp); 1696 BN_free(ret); 1697 return st; 1698 } 1699 1700 static int file_exp(STANZA *s) 1701 { 1702 BIGNUM *a = NULL, *e = NULL, *exp = NULL, *ret = NULL; 1703 int st = 0; 1704 1705 if (!TEST_ptr(a = getBN(s, "A")) 1706 || !TEST_ptr(e = getBN(s, "E")) 1707 || !TEST_ptr(exp = getBN(s, "Exp")) 1708 || !TEST_ptr(ret = BN_new())) 1709 goto err; 1710 1711 if (!TEST_true(BN_exp(ret, a, e, ctx)) 1712 || !equalBN("A ^ E", exp, ret)) 1713 goto err; 1714 1715 st = 1; 1716 err: 1717 BN_free(a); 1718 BN_free(e); 1719 BN_free(exp); 1720 BN_free(ret); 1721 return st; 1722 } 1723 1724 static int file_modsqrt(STANZA *s) 1725 { 1726 BIGNUM *a = NULL, *p = NULL, *mod_sqrt = NULL, *ret = NULL, *ret2 = NULL; 1727 int st = 0; 1728 1729 if (!TEST_ptr(a = getBN(s, "A")) 1730 || !TEST_ptr(p = getBN(s, "P")) 1731 || !TEST_ptr(mod_sqrt = getBN(s, "ModSqrt")) 1732 || !TEST_ptr(ret = BN_new()) 1733 || !TEST_ptr(ret2 = BN_new())) 1734 goto err; 1735 1736 if (BN_is_negative(mod_sqrt)) { 1737 /* A negative testcase */ 1738 if (!TEST_ptr_null(BN_mod_sqrt(ret, a, p, ctx))) 1739 goto err; 1740 1741 st = 1; 1742 goto err; 1743 } 1744 1745 /* There are two possible answers. */ 1746 if (!TEST_ptr(BN_mod_sqrt(ret, a, p, ctx)) 1747 || !TEST_true(BN_sub(ret2, p, ret))) 1748 goto err; 1749 1750 /* The first condition should NOT be a test. */ 1751 if (BN_cmp(ret2, mod_sqrt) != 0 1752 && !equalBN("sqrt(A) (mod P)", mod_sqrt, ret)) 1753 goto err; 1754 1755 st = 1; 1756 err: 1757 BN_free(a); 1758 BN_free(p); 1759 BN_free(mod_sqrt); 1760 BN_free(ret); 1761 BN_free(ret2); 1762 return st; 1763 } 1764 1765 static int file_gcd(STANZA *s) 1766 { 1767 BIGNUM *a = NULL, *b = NULL, *gcd = NULL, *ret = NULL; 1768 int st = 0; 1769 1770 if (!TEST_ptr(a = getBN(s, "A")) 1771 || !TEST_ptr(b = getBN(s, "B")) 1772 || !TEST_ptr(gcd = getBN(s, "GCD")) 1773 || !TEST_ptr(ret = BN_new())) 1774 goto err; 1775 1776 if (!TEST_true(BN_gcd(ret, a, b, ctx)) 1777 || !equalBN("gcd(A,B)", gcd, ret)) 1778 goto err; 1779 1780 st = 1; 1781 err: 1782 BN_free(a); 1783 BN_free(b); 1784 BN_free(gcd); 1785 BN_free(ret); 1786 return st; 1787 } 1788 1789 static int test_bn2padded(void) 1790 { 1791 uint8_t zeros[256], out[256], reference[128]; 1792 size_t bytes; 1793 BIGNUM *n; 1794 int st = 0; 1795 1796 /* Test edge case at 0. */ 1797 if (!TEST_ptr((n = BN_new()))) 1798 goto err; 1799 if (!TEST_int_eq(BN_bn2binpad(n, NULL, 0), 0)) 1800 goto err; 1801 memset(out, -1, sizeof(out)); 1802 if (!TEST_int_eq(BN_bn2binpad(n, out, sizeof(out)), sizeof(out))) 1803 goto err; 1804 memset(zeros, 0, sizeof(zeros)); 1805 if (!TEST_mem_eq(zeros, sizeof(zeros), out, sizeof(out))) 1806 goto err; 1807 1808 /* Test a random numbers at various byte lengths. */ 1809 for (bytes = 128 - 7; bytes <= 128; bytes++) { 1810 # define TOP_BIT_ON 0 1811 # define BOTTOM_BIT_NOTOUCH 0 1812 if (!TEST_true(BN_rand(n, bytes * 8, TOP_BIT_ON, BOTTOM_BIT_NOTOUCH))) 1813 goto err; 1814 if (!TEST_int_eq(BN_num_bytes(n), bytes) 1815 || !TEST_int_eq(BN_bn2bin(n, reference), bytes)) 1816 goto err; 1817 /* Empty buffer should fail. */ 1818 if (!TEST_int_eq(BN_bn2binpad(n, NULL, 0), -1)) 1819 goto err; 1820 /* One byte short should fail. */ 1821 if (!TEST_int_eq(BN_bn2binpad(n, out, bytes - 1), -1)) 1822 goto err; 1823 /* Exactly right size should encode. */ 1824 if (!TEST_int_eq(BN_bn2binpad(n, out, bytes), bytes) 1825 || !TEST_mem_eq(out, bytes, reference, bytes)) 1826 goto err; 1827 /* Pad up one byte extra. */ 1828 if (!TEST_int_eq(BN_bn2binpad(n, out, bytes + 1), bytes + 1) 1829 || !TEST_mem_eq(out + 1, bytes, reference, bytes) 1830 || !TEST_mem_eq(out, 1, zeros, 1)) 1831 goto err; 1832 /* Pad up to 256. */ 1833 if (!TEST_int_eq(BN_bn2binpad(n, out, sizeof(out)), sizeof(out)) 1834 || !TEST_mem_eq(out + sizeof(out) - bytes, bytes, 1835 reference, bytes) 1836 || !TEST_mem_eq(out, sizeof(out) - bytes, 1837 zeros, sizeof(out) - bytes)) 1838 goto err; 1839 } 1840 1841 st = 1; 1842 err: 1843 BN_free(n); 1844 return st; 1845 } 1846 1847 static int test_dec2bn(void) 1848 { 1849 BIGNUM *bn = NULL; 1850 int st = 0; 1851 1852 if (!TEST_int_eq(parsedecBN(&bn, "0"), 1) 1853 || !TEST_BN_eq_word(bn, 0) 1854 || !TEST_BN_eq_zero(bn) 1855 || !TEST_BN_le_zero(bn) 1856 || !TEST_BN_ge_zero(bn) 1857 || !TEST_BN_even(bn)) 1858 goto err; 1859 BN_free(bn); 1860 bn = NULL; 1861 1862 if (!TEST_int_eq(parsedecBN(&bn, "256"), 3) 1863 || !TEST_BN_eq_word(bn, 256) 1864 || !TEST_BN_ge_zero(bn) 1865 || !TEST_BN_gt_zero(bn) 1866 || !TEST_BN_ne_zero(bn) 1867 || !TEST_BN_even(bn)) 1868 goto err; 1869 BN_free(bn); 1870 bn = NULL; 1871 1872 if (!TEST_int_eq(parsedecBN(&bn, "-42"), 3) 1873 || !TEST_BN_abs_eq_word(bn, 42) 1874 || !TEST_BN_lt_zero(bn) 1875 || !TEST_BN_le_zero(bn) 1876 || !TEST_BN_ne_zero(bn) 1877 || !TEST_BN_even(bn)) 1878 goto err; 1879 BN_free(bn); 1880 bn = NULL; 1881 1882 if (!TEST_int_eq(parsedecBN(&bn, "1"), 1) 1883 || !TEST_BN_eq_word(bn, 1) 1884 || !TEST_BN_ne_zero(bn) 1885 || !TEST_BN_gt_zero(bn) 1886 || !TEST_BN_ge_zero(bn) 1887 || !TEST_BN_eq_one(bn) 1888 || !TEST_BN_odd(bn)) 1889 goto err; 1890 BN_free(bn); 1891 bn = NULL; 1892 1893 if (!TEST_int_eq(parsedecBN(&bn, "-0"), 2) 1894 || !TEST_BN_eq_zero(bn) 1895 || !TEST_BN_ge_zero(bn) 1896 || !TEST_BN_le_zero(bn) 1897 || !TEST_BN_even(bn)) 1898 goto err; 1899 BN_free(bn); 1900 bn = NULL; 1901 1902 if (!TEST_int_eq(parsedecBN(&bn, "42trailing garbage is ignored"), 2) 1903 || !TEST_BN_abs_eq_word(bn, 42) 1904 || !TEST_BN_ge_zero(bn) 1905 || !TEST_BN_gt_zero(bn) 1906 || !TEST_BN_ne_zero(bn) 1907 || !TEST_BN_even(bn)) 1908 goto err; 1909 1910 st = 1; 1911 err: 1912 BN_free(bn); 1913 return st; 1914 } 1915 1916 static int test_hex2bn(void) 1917 { 1918 BIGNUM *bn = NULL; 1919 int st = 0; 1920 1921 if (!TEST_int_eq(parseBN(&bn, "0"), 1) 1922 || !TEST_BN_eq_zero(bn) 1923 || !TEST_BN_ge_zero(bn) 1924 || !TEST_BN_even(bn)) 1925 goto err; 1926 BN_free(bn); 1927 bn = NULL; 1928 1929 if (!TEST_int_eq(parseBN(&bn, "256"), 3) 1930 || !TEST_BN_eq_word(bn, 0x256) 1931 || !TEST_BN_ge_zero(bn) 1932 || !TEST_BN_gt_zero(bn) 1933 || !TEST_BN_ne_zero(bn) 1934 || !TEST_BN_even(bn)) 1935 goto err; 1936 BN_free(bn); 1937 bn = NULL; 1938 1939 if (!TEST_int_eq(parseBN(&bn, "-42"), 3) 1940 || !TEST_BN_abs_eq_word(bn, 0x42) 1941 || !TEST_BN_lt_zero(bn) 1942 || !TEST_BN_le_zero(bn) 1943 || !TEST_BN_ne_zero(bn) 1944 || !TEST_BN_even(bn)) 1945 goto err; 1946 BN_free(bn); 1947 bn = NULL; 1948 1949 if (!TEST_int_eq(parseBN(&bn, "cb"), 2) 1950 || !TEST_BN_eq_word(bn, 0xCB) 1951 || !TEST_BN_ge_zero(bn) 1952 || !TEST_BN_gt_zero(bn) 1953 || !TEST_BN_ne_zero(bn) 1954 || !TEST_BN_odd(bn)) 1955 goto err; 1956 BN_free(bn); 1957 bn = NULL; 1958 1959 if (!TEST_int_eq(parseBN(&bn, "-0"), 2) 1960 || !TEST_BN_eq_zero(bn) 1961 || !TEST_BN_ge_zero(bn) 1962 || !TEST_BN_le_zero(bn) 1963 || !TEST_BN_even(bn)) 1964 goto err; 1965 BN_free(bn); 1966 bn = NULL; 1967 1968 if (!TEST_int_eq(parseBN(&bn, "abctrailing garbage is ignored"), 3) 1969 || !TEST_BN_eq_word(bn, 0xabc) 1970 || !TEST_BN_ge_zero(bn) 1971 || !TEST_BN_gt_zero(bn) 1972 || !TEST_BN_ne_zero(bn) 1973 || !TEST_BN_even(bn)) 1974 goto err; 1975 st = 1; 1976 1977 err: 1978 BN_free(bn); 1979 return st; 1980 } 1981 1982 static int test_asc2bn(void) 1983 { 1984 BIGNUM *bn = NULL; 1985 int st = 0; 1986 1987 if (!TEST_ptr(bn = BN_new())) 1988 goto err; 1989 1990 if (!TEST_true(BN_asc2bn(&bn, "0")) 1991 || !TEST_BN_eq_zero(bn) 1992 || !TEST_BN_ge_zero(bn)) 1993 goto err; 1994 1995 if (!TEST_true(BN_asc2bn(&bn, "256")) 1996 || !TEST_BN_eq_word(bn, 256) 1997 || !TEST_BN_ge_zero(bn)) 1998 goto err; 1999 2000 if (!TEST_true(BN_asc2bn(&bn, "-42")) 2001 || !TEST_BN_abs_eq_word(bn, 42) 2002 || !TEST_BN_lt_zero(bn)) 2003 goto err; 2004 2005 if (!TEST_true(BN_asc2bn(&bn, "0x1234")) 2006 || !TEST_BN_eq_word(bn, 0x1234) 2007 || !TEST_BN_ge_zero(bn)) 2008 goto err; 2009 2010 if (!TEST_true(BN_asc2bn(&bn, "0X1234")) 2011 || !TEST_BN_eq_word(bn, 0x1234) 2012 || !TEST_BN_ge_zero(bn)) 2013 goto err; 2014 2015 if (!TEST_true(BN_asc2bn(&bn, "-0xabcd")) 2016 || !TEST_BN_abs_eq_word(bn, 0xabcd) 2017 || !TEST_BN_lt_zero(bn)) 2018 goto err; 2019 2020 if (!TEST_true(BN_asc2bn(&bn, "-0")) 2021 || !TEST_BN_eq_zero(bn) 2022 || !TEST_BN_ge_zero(bn)) 2023 goto err; 2024 2025 if (!TEST_true(BN_asc2bn(&bn, "123trailing garbage is ignored")) 2026 || !TEST_BN_eq_word(bn, 123) 2027 || !TEST_BN_ge_zero(bn)) 2028 goto err; 2029 2030 st = 1; 2031 err: 2032 BN_free(bn); 2033 return st; 2034 } 2035 2036 static const MPITEST kMPITests[] = { 2037 {"0", "\x00\x00\x00\x00", 4}, 2038 {"1", "\x00\x00\x00\x01\x01", 5}, 2039 {"-1", "\x00\x00\x00\x01\x81", 5}, 2040 {"128", "\x00\x00\x00\x02\x00\x80", 6}, 2041 {"256", "\x00\x00\x00\x02\x01\x00", 6}, 2042 {"-256", "\x00\x00\x00\x02\x81\x00", 6}, 2043 }; 2044 2045 static int test_mpi(int i) 2046 { 2047 uint8_t scratch[8]; 2048 const MPITEST *test = &kMPITests[i]; 2049 size_t mpi_len, mpi_len2; 2050 BIGNUM *bn = NULL; 2051 BIGNUM *bn2 = NULL; 2052 int st = 0; 2053 2054 if (!TEST_ptr(bn = BN_new()) 2055 || !TEST_true(BN_asc2bn(&bn, test->base10))) 2056 goto err; 2057 mpi_len = BN_bn2mpi(bn, NULL); 2058 if (!TEST_size_t_le(mpi_len, sizeof(scratch))) 2059 goto err; 2060 2061 if (!TEST_size_t_eq(mpi_len2 = BN_bn2mpi(bn, scratch), mpi_len) 2062 || !TEST_mem_eq(test->mpi, test->mpi_len, scratch, mpi_len)) 2063 goto err; 2064 2065 if (!TEST_ptr(bn2 = BN_mpi2bn(scratch, mpi_len, NULL))) 2066 goto err; 2067 2068 if (!TEST_BN_eq(bn, bn2)) { 2069 BN_free(bn2); 2070 goto err; 2071 } 2072 BN_free(bn2); 2073 2074 st = 1; 2075 err: 2076 BN_free(bn); 2077 return st; 2078 } 2079 2080 static int test_rand(void) 2081 { 2082 BIGNUM *bn = NULL; 2083 int st = 0; 2084 2085 if (!TEST_ptr(bn = BN_new())) 2086 return 0; 2087 2088 /* Test BN_rand for degenerate cases with |top| and |bottom| parameters. */ 2089 if (!TEST_false(BN_rand(bn, 0, 0 /* top */ , 0 /* bottom */ )) 2090 || !TEST_false(BN_rand(bn, 0, 1 /* top */ , 1 /* bottom */ )) 2091 || !TEST_true(BN_rand(bn, 1, 0 /* top */ , 0 /* bottom */ )) 2092 || !TEST_BN_eq_one(bn) 2093 || !TEST_false(BN_rand(bn, 1, 1 /* top */ , 0 /* bottom */ )) 2094 || !TEST_true(BN_rand(bn, 1, -1 /* top */ , 1 /* bottom */ )) 2095 || !TEST_BN_eq_one(bn) 2096 || !TEST_true(BN_rand(bn, 2, 1 /* top */ , 0 /* bottom */ )) 2097 || !TEST_BN_eq_word(bn, 3)) 2098 goto err; 2099 2100 st = 1; 2101 err: 2102 BN_free(bn); 2103 return st; 2104 } 2105 2106 /* 2107 * Run some statistical tests to provide a degree confidence that the 2108 * BN_rand_range() function works as expected. The test cases and 2109 * critical values are generated by the bn_rand_range script. 2110 * 2111 * Each individual test is a Chi^2 goodness of fit for a specified number 2112 * of samples and range. The samples are assumed to be independent and 2113 * that they are from a discrete uniform distribution. 2114 * 2115 * Some of these individual tests are expected to fail, the success/failure 2116 * of each is an independent Bernoulli trial. The number of such successes 2117 * will form a binomial distribution. The count of the successes is compared 2118 * against a precomputed critical value to determine the overall outcome. 2119 */ 2120 struct rand_range_case { 2121 unsigned int range; 2122 unsigned int iterations; 2123 double critical; 2124 }; 2125 2126 #include "bn_rand_range.h" 2127 2128 static int test_rand_range_single(size_t n) 2129 { 2130 const unsigned int range = rand_range_cases[n].range; 2131 const unsigned int iterations = rand_range_cases[n].iterations; 2132 const double critical = rand_range_cases[n].critical; 2133 const double expected = iterations / (double)range; 2134 double sum = 0; 2135 BIGNUM *rng = NULL, *val = NULL; 2136 size_t *counts; 2137 unsigned int i, v; 2138 int res = 0; 2139 2140 if (!TEST_ptr(counts = OPENSSL_zalloc(sizeof(*counts) * range)) 2141 || !TEST_ptr(rng = BN_new()) 2142 || !TEST_ptr(val = BN_new()) 2143 || !TEST_true(BN_set_word(rng, range))) 2144 goto err; 2145 for (i = 0; i < iterations; i++) { 2146 if (!TEST_true(BN_rand_range(val, rng)) 2147 || !TEST_uint_lt(v = (unsigned int)BN_get_word(val), range)) 2148 goto err; 2149 counts[v]++; 2150 } 2151 2152 for (i = 0; i < range; i++) { 2153 const double delta = counts[i] - expected; 2154 sum += delta * delta; 2155 } 2156 sum /= expected; 2157 2158 if (sum > critical) { 2159 TEST_info("Chi^2 test negative %.4f > %4.f", sum, critical); 2160 TEST_note("test case %zu range %u iterations %u", n + 1, range, 2161 iterations); 2162 goto err; 2163 } 2164 2165 res = 1; 2166 err: 2167 BN_free(rng); 2168 BN_free(val); 2169 OPENSSL_free(counts); 2170 return res; 2171 } 2172 2173 static int test_rand_range(void) 2174 { 2175 int n_success = 0; 2176 size_t i; 2177 2178 for (i = 0; i < OSSL_NELEM(rand_range_cases); i++) 2179 n_success += test_rand_range_single(i); 2180 if (TEST_int_ge(n_success, binomial_critical)) 2181 return 1; 2182 TEST_note("This test is expected to fail by chance 0.01%% of the time."); 2183 return 0; 2184 } 2185 2186 static int test_negzero(void) 2187 { 2188 BIGNUM *a = NULL, *b = NULL, *c = NULL, *d = NULL; 2189 BIGNUM *numerator = NULL, *denominator = NULL; 2190 int consttime, st = 0; 2191 2192 if (!TEST_ptr(a = BN_new()) 2193 || !TEST_ptr(b = BN_new()) 2194 || !TEST_ptr(c = BN_new()) 2195 || !TEST_ptr(d = BN_new())) 2196 goto err; 2197 2198 /* Test that BN_mul never gives negative zero. */ 2199 if (!TEST_true(BN_set_word(a, 1))) 2200 goto err; 2201 BN_set_negative(a, 1); 2202 BN_zero(b); 2203 if (!TEST_true(BN_mul(c, a, b, ctx))) 2204 goto err; 2205 if (!TEST_BN_eq_zero(c) 2206 || !TEST_BN_ge_zero(c)) 2207 goto err; 2208 2209 for (consttime = 0; consttime < 2; consttime++) { 2210 if (!TEST_ptr(numerator = BN_new()) 2211 || !TEST_ptr(denominator = BN_new())) 2212 goto err; 2213 if (consttime) { 2214 BN_set_flags(numerator, BN_FLG_CONSTTIME); 2215 BN_set_flags(denominator, BN_FLG_CONSTTIME); 2216 } 2217 /* Test that BN_div never gives negative zero in the quotient. */ 2218 if (!TEST_true(BN_set_word(numerator, 1)) 2219 || !TEST_true(BN_set_word(denominator, 2))) 2220 goto err; 2221 BN_set_negative(numerator, 1); 2222 if (!TEST_true(BN_div(a, b, numerator, denominator, ctx)) 2223 || !TEST_BN_eq_zero(a) 2224 || !TEST_BN_ge_zero(a)) 2225 goto err; 2226 2227 /* Test that BN_div never gives negative zero in the remainder. */ 2228 if (!TEST_true(BN_set_word(denominator, 1)) 2229 || !TEST_true(BN_div(a, b, numerator, denominator, ctx)) 2230 || !TEST_BN_eq_zero(b) 2231 || !TEST_BN_ge_zero(b)) 2232 goto err; 2233 BN_free(numerator); 2234 BN_free(denominator); 2235 numerator = denominator = NULL; 2236 } 2237 2238 /* Test that BN_set_negative will not produce a negative zero. */ 2239 BN_zero(a); 2240 BN_set_negative(a, 1); 2241 if (BN_is_negative(a)) 2242 goto err; 2243 st = 1; 2244 2245 err: 2246 BN_free(a); 2247 BN_free(b); 2248 BN_free(c); 2249 BN_free(d); 2250 BN_free(numerator); 2251 BN_free(denominator); 2252 return st; 2253 } 2254 2255 static int test_badmod(void) 2256 { 2257 BIGNUM *a = NULL, *b = NULL, *zero = NULL; 2258 BN_MONT_CTX *mont = NULL; 2259 int st = 0; 2260 2261 if (!TEST_ptr(a = BN_new()) 2262 || !TEST_ptr(b = BN_new()) 2263 || !TEST_ptr(zero = BN_new()) 2264 || !TEST_ptr(mont = BN_MONT_CTX_new())) 2265 goto err; 2266 BN_zero(zero); 2267 2268 if (!TEST_false(BN_div(a, b, BN_value_one(), zero, ctx))) 2269 goto err; 2270 ERR_clear_error(); 2271 2272 if (!TEST_false(BN_mod_mul(a, BN_value_one(), BN_value_one(), zero, ctx))) 2273 goto err; 2274 ERR_clear_error(); 2275 2276 if (!TEST_false(BN_mod_exp(a, BN_value_one(), BN_value_one(), zero, ctx))) 2277 goto err; 2278 ERR_clear_error(); 2279 2280 if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(), 2281 zero, ctx, NULL))) 2282 goto err; 2283 ERR_clear_error(); 2284 2285 if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(), 2286 zero, ctx, NULL))) 2287 goto err; 2288 ERR_clear_error(); 2289 2290 if (!TEST_false(BN_MONT_CTX_set(mont, zero, ctx))) 2291 goto err; 2292 ERR_clear_error(); 2293 2294 /* Some operations also may not be used with an even modulus. */ 2295 if (!TEST_true(BN_set_word(b, 16))) 2296 goto err; 2297 2298 if (!TEST_false(BN_MONT_CTX_set(mont, b, ctx))) 2299 goto err; 2300 ERR_clear_error(); 2301 2302 if (!TEST_false(BN_mod_exp_mont(a, BN_value_one(), BN_value_one(), 2303 b, ctx, NULL))) 2304 goto err; 2305 ERR_clear_error(); 2306 2307 if (!TEST_false(BN_mod_exp_mont_consttime(a, BN_value_one(), BN_value_one(), 2308 b, ctx, NULL))) 2309 goto err; 2310 ERR_clear_error(); 2311 2312 st = 1; 2313 err: 2314 BN_free(a); 2315 BN_free(b); 2316 BN_free(zero); 2317 BN_MONT_CTX_free(mont); 2318 return st; 2319 } 2320 2321 static int test_expmodzero(void) 2322 { 2323 BIGNUM *a = NULL, *r = NULL, *zero = NULL; 2324 int st = 0; 2325 2326 if (!TEST_ptr(zero = BN_new()) 2327 || !TEST_ptr(a = BN_new()) 2328 || !TEST_ptr(r = BN_new())) 2329 goto err; 2330 BN_zero(zero); 2331 2332 if (!TEST_true(BN_mod_exp(r, a, zero, BN_value_one(), NULL)) 2333 || !TEST_BN_eq_zero(r) 2334 || !TEST_true(BN_mod_exp_mont(r, a, zero, BN_value_one(), 2335 NULL, NULL)) 2336 || !TEST_BN_eq_zero(r) 2337 || !TEST_true(BN_mod_exp_mont_consttime(r, a, zero, 2338 BN_value_one(), 2339 NULL, NULL)) 2340 || !TEST_BN_eq_zero(r) 2341 || !TEST_true(BN_mod_exp_mont_word(r, 42, zero, 2342 BN_value_one(), NULL, NULL)) 2343 || !TEST_BN_eq_zero(r)) 2344 goto err; 2345 2346 st = 1; 2347 err: 2348 BN_free(zero); 2349 BN_free(a); 2350 BN_free(r); 2351 return st; 2352 } 2353 2354 static int test_expmodone(void) 2355 { 2356 int ret = 0, i; 2357 BIGNUM *r = BN_new(); 2358 BIGNUM *a = BN_new(); 2359 BIGNUM *p = BN_new(); 2360 BIGNUM *m = BN_new(); 2361 2362 if (!TEST_ptr(r) 2363 || !TEST_ptr(a) 2364 || !TEST_ptr(p) 2365 || !TEST_ptr(p) 2366 || !TEST_ptr(m) 2367 || !TEST_true(BN_set_word(a, 1)) 2368 || !TEST_true(BN_set_word(p, 0)) 2369 || !TEST_true(BN_set_word(m, 1))) 2370 goto err; 2371 2372 /* Calculate r = 1 ^ 0 mod 1, and check the result is always 0 */ 2373 for (i = 0; i < 2; i++) { 2374 if (!TEST_true(BN_mod_exp(r, a, p, m, NULL)) 2375 || !TEST_BN_eq_zero(r) 2376 || !TEST_true(BN_mod_exp_mont(r, a, p, m, NULL, NULL)) 2377 || !TEST_BN_eq_zero(r) 2378 || !TEST_true(BN_mod_exp_mont_consttime(r, a, p, m, NULL, NULL)) 2379 || !TEST_BN_eq_zero(r) 2380 || !TEST_true(BN_mod_exp_mont_word(r, 1, p, m, NULL, NULL)) 2381 || !TEST_BN_eq_zero(r) 2382 || !TEST_true(BN_mod_exp_simple(r, a, p, m, NULL)) 2383 || !TEST_BN_eq_zero(r) 2384 || !TEST_true(BN_mod_exp_recp(r, a, p, m, NULL)) 2385 || !TEST_BN_eq_zero(r)) 2386 goto err; 2387 /* Repeat for r = 1 ^ 0 mod -1 */ 2388 if (i == 0) 2389 BN_set_negative(m, 1); 2390 } 2391 2392 ret = 1; 2393 err: 2394 BN_free(r); 2395 BN_free(a); 2396 BN_free(p); 2397 BN_free(m); 2398 return ret; 2399 } 2400 2401 static int test_smallprime(int kBits) 2402 { 2403 BIGNUM *r; 2404 int st = 0; 2405 2406 if (!TEST_ptr(r = BN_new())) 2407 goto err; 2408 2409 if (kBits <= 1) { 2410 if (!TEST_false(BN_generate_prime_ex(r, kBits, 0, 2411 NULL, NULL, NULL))) 2412 goto err; 2413 } else { 2414 if (!TEST_true(BN_generate_prime_ex(r, kBits, 0, 2415 NULL, NULL, NULL)) 2416 || !TEST_int_eq(BN_num_bits(r), kBits)) 2417 goto err; 2418 } 2419 2420 st = 1; 2421 err: 2422 BN_free(r); 2423 return st; 2424 } 2425 2426 static int test_smallsafeprime(int kBits) 2427 { 2428 BIGNUM *r; 2429 int st = 0; 2430 2431 if (!TEST_ptr(r = BN_new())) 2432 goto err; 2433 2434 if (kBits <= 5 && kBits != 3) { 2435 if (!TEST_false(BN_generate_prime_ex(r, kBits, 1, 2436 NULL, NULL, NULL))) 2437 goto err; 2438 } else { 2439 if (!TEST_true(BN_generate_prime_ex(r, kBits, 1, 2440 NULL, NULL, NULL)) 2441 || !TEST_int_eq(BN_num_bits(r), kBits)) 2442 goto err; 2443 } 2444 2445 st = 1; 2446 err: 2447 BN_free(r); 2448 return st; 2449 } 2450 2451 static int primes[] = { 2, 3, 5, 7, 17863 }; 2452 2453 static int test_is_prime(int i) 2454 { 2455 int ret = 0; 2456 BIGNUM *r = NULL; 2457 int trial; 2458 2459 if (!TEST_ptr(r = BN_new())) 2460 goto err; 2461 2462 for (trial = 0; trial <= 1; ++trial) { 2463 if (!TEST_true(BN_set_word(r, primes[i])) 2464 || !TEST_int_eq(BN_check_prime(r, ctx, NULL), 2465 1)) 2466 goto err; 2467 } 2468 2469 ret = 1; 2470 err: 2471 BN_free(r); 2472 return ret; 2473 } 2474 2475 static int not_primes[] = { -1, 0, 1, 4 }; 2476 2477 static int test_not_prime(int i) 2478 { 2479 int ret = 0; 2480 BIGNUM *r = NULL; 2481 int trial; 2482 2483 if (!TEST_ptr(r = BN_new())) 2484 goto err; 2485 2486 for (trial = 0; trial <= 1; ++trial) { 2487 if (!TEST_true(BN_set_word(r, not_primes[i])) 2488 || !TEST_false(BN_check_prime(r, ctx, NULL))) 2489 goto err; 2490 } 2491 2492 ret = 1; 2493 err: 2494 BN_free(r); 2495 return ret; 2496 } 2497 2498 static int test_ctx_set_ct_flag(BN_CTX *c) 2499 { 2500 int st = 0; 2501 size_t i; 2502 BIGNUM *b[15]; 2503 2504 BN_CTX_start(c); 2505 for (i = 0; i < OSSL_NELEM(b); i++) { 2506 if (!TEST_ptr(b[i] = BN_CTX_get(c))) 2507 goto err; 2508 if (i % 2 == 1) 2509 BN_set_flags(b[i], BN_FLG_CONSTTIME); 2510 } 2511 2512 st = 1; 2513 err: 2514 BN_CTX_end(c); 2515 return st; 2516 } 2517 2518 static int test_ctx_check_ct_flag(BN_CTX *c) 2519 { 2520 int st = 0; 2521 size_t i; 2522 BIGNUM *b[30]; 2523 2524 BN_CTX_start(c); 2525 for (i = 0; i < OSSL_NELEM(b); i++) { 2526 if (!TEST_ptr(b[i] = BN_CTX_get(c))) 2527 goto err; 2528 if (!TEST_false(BN_get_flags(b[i], BN_FLG_CONSTTIME))) 2529 goto err; 2530 } 2531 2532 st = 1; 2533 err: 2534 BN_CTX_end(c); 2535 return st; 2536 } 2537 2538 static int test_ctx_consttime_flag(void) 2539 { 2540 /*- 2541 * The constant-time flag should not "leak" among BN_CTX frames: 2542 * 2543 * - test_ctx_set_ct_flag() starts a frame in the given BN_CTX and 2544 * sets the BN_FLG_CONSTTIME flag on some of the BIGNUMs obtained 2545 * from the frame before ending it. 2546 * - test_ctx_check_ct_flag() then starts a new frame and gets a 2547 * number of BIGNUMs from it. In absence of leaks, none of the 2548 * BIGNUMs in the new frame should have BN_FLG_CONSTTIME set. 2549 * 2550 * In actual BN_CTX usage inside libcrypto the leak could happen at 2551 * any depth level in the BN_CTX stack, with varying results 2552 * depending on the patterns of sibling trees of nested function 2553 * calls sharing the same BN_CTX object, and the effect of 2554 * unintended BN_FLG_CONSTTIME on the called BN_* functions. 2555 * 2556 * This simple unit test abstracts away this complexity and verifies 2557 * that the leak does not happen between two sibling functions 2558 * sharing the same BN_CTX object at the same level of nesting. 2559 * 2560 */ 2561 BN_CTX *nctx = NULL; 2562 BN_CTX *sctx = NULL; 2563 size_t i = 0; 2564 int st = 0; 2565 2566 if (!TEST_ptr(nctx = BN_CTX_new()) 2567 || !TEST_ptr(sctx = BN_CTX_secure_new())) 2568 goto err; 2569 2570 for (i = 0; i < 2; i++) { 2571 BN_CTX *c = i == 0 ? nctx : sctx; 2572 if (!TEST_true(test_ctx_set_ct_flag(c)) 2573 || !TEST_true(test_ctx_check_ct_flag(c))) 2574 goto err; 2575 } 2576 2577 st = 1; 2578 err: 2579 BN_CTX_free(nctx); 2580 BN_CTX_free(sctx); 2581 return st; 2582 } 2583 2584 static int test_gcd_prime(void) 2585 { 2586 BIGNUM *a = NULL, *b = NULL, *gcd = NULL; 2587 int i, st = 0; 2588 2589 if (!TEST_ptr(a = BN_new()) 2590 || !TEST_ptr(b = BN_new()) 2591 || !TEST_ptr(gcd = BN_new())) 2592 goto err; 2593 2594 if (!TEST_true(BN_generate_prime_ex(a, 1024, 0, NULL, NULL, NULL))) 2595 goto err; 2596 for (i = 0; i < NUM0; i++) { 2597 if (!TEST_true(BN_generate_prime_ex(b, 1024, 0, 2598 NULL, NULL, NULL)) 2599 || !TEST_true(BN_gcd(gcd, a, b, ctx)) 2600 || !TEST_true(BN_is_one(gcd))) 2601 goto err; 2602 } 2603 2604 st = 1; 2605 err: 2606 BN_free(a); 2607 BN_free(b); 2608 BN_free(gcd); 2609 return st; 2610 } 2611 2612 typedef struct mod_exp_test_st 2613 { 2614 const char *base; 2615 const char *exp; 2616 const char *mod; 2617 const char *res; 2618 } MOD_EXP_TEST; 2619 2620 static const MOD_EXP_TEST ModExpTests[] = { 2621 /* original test vectors for rsaz_512_sqr bug, by OSS-Fuzz */ 2622 { 2623 "1166180238001879113042182292626169621106255558914000595999312084" 2624 "4627946820899490684928760491249738643524880720584249698100907201" 2625 "002086675047927600340800371", 2626 "8000000000000000000000000000000000000000000000000000000000000000" 2627 "0000000000000000000000000000000000000000000000000000000000000000" 2628 "00000000", 2629 "1340780792684523720980737645613191762604395855615117867483316354" 2630 "3294276330515137663421134775482798690129946803802212663956180562" 2631 "088664022929883876655300863", 2632 "8243904058268085430037326628480645845409758077568738532059032482" 2633 "8294114415890603594730158120426756266457928475330450251339773498" 2634 "26758407619521544102068438" 2635 }, 2636 { 2637 "4974270041410803822078866696159586946995877618987010219312844726" 2638 "0284386121835740784990869050050504348861513337232530490826340663" 2639 "197278031692737429054", 2640 "4974270041410803822078866696159586946995877428188754995041148539" 2641 "1663243362592271353668158565195557417149981094324650322556843202" 2642 "946445882670777892608", 2643 "1340780716511420227215592830971452482815377482627251725537099028" 2644 "4429769497230131760206012644403029349547320953206103351725462999" 2645 "947509743623340557059752191", 2646 "5296244594780707015616522701706118082963369547253192207884519362" 2647 "1767869984947542695665420219028522815539559194793619684334900442" 2648 "49304558011362360473525933" 2649 }, 2650 /* test vectors for rsaz_512_srq bug, with rcx/rbx=1 */ 2651 { /* between first and second iteration */ 2652 "5148719036160389201525610950887605325980251964889646556085286545" 2653 "3931548809178823413169359635978762036512397113080988070677858033" 2654 "36463909753993540214027190", 2655 "6703903964971298549787012499102923063739682910296196688861780721" 2656 "8608820150367734884009371490834517138450159290932430254268769414" 2657 "05973284973216824503042158", 2658 "6703903964971298549787012499102923063739682910296196688861780721" 2659 "8608820150367734884009371490834517138450159290932430254268769414" 2660 "05973284973216824503042159", 2661 "1" 2662 }, 2663 { /* between second and third iteration */ 2664 "8908340854353752577419678771330460827942371434853054158622636544" 2665 "8151360109722890949471912566649465436296659601091730745087014189" 2666 "2672764191218875181826063", 2667 "6703903964971298549787012499102923063739682910296196688861780721" 2668 "8608820150367734884009371490834517138450159290932430254268769414" 2669 "05973284973216824503042158", 2670 "6703903964971298549787012499102923063739682910296196688861780721" 2671 "8608820150367734884009371490834517138450159290932430254268769414" 2672 "05973284973216824503042159", 2673 "1" 2674 }, 2675 { /* between third and fourth iteration */ 2676 "3427446396505596330634350984901719674479522569002785244080234738" 2677 "4288743635435746136297299366444548736533053717416735379073185344" 2678 "26985272974404612945608761", 2679 "6703903964971298549787012499102923063739682910296196688861780721" 2680 "8608820150367734884009371490834517138450159290932430254268769414" 2681 "05973284973216824503042158", 2682 "6703903964971298549787012499102923063739682910296196688861780721" 2683 "8608820150367734884009371490834517138450159290932430254268769414" 2684 "05973284973216824503042159", 2685 "1" 2686 }, 2687 { /* between fourth and fifth iteration */ 2688 "3472743044917564564078857826111874560045331237315597383869652985" 2689 "6919870028890895988478351133601517365908445058405433832718206902" 2690 "4088133164805266956353542", 2691 "6703903964971298549787012499102923063739682910296196688861780721" 2692 "8608820150367734884009371490834517138450159290932430254268769414" 2693 "05973284973216824503042158", 2694 "6703903964971298549787012499102923063739682910296196688861780721" 2695 "8608820150367734884009371490834517138450159290932430254268769414" 2696 "05973284973216824503042159", 2697 "1" 2698 }, 2699 { /* between fifth and sixth iteration */ 2700 "3608632990153469264412378349742339216742409743898601587274768025" 2701 "0110772032985643555192767717344946174122842255204082586753499651" 2702 "14483434992887431333675068", 2703 "6703903964971298549787012499102923063739682910296196688861780721" 2704 "8608820150367734884009371490834517138450159290932430254268769414" 2705 "05973284973216824503042158", 2706 "6703903964971298549787012499102923063739682910296196688861780721" 2707 "8608820150367734884009371490834517138450159290932430254268769414" 2708 "05973284973216824503042159", 2709 "1" 2710 }, 2711 { /* between sixth and seventh iteration */ 2712 "8455374370234070242910508226941981520235709767260723212165264877" 2713 "8689064388017521524568434328264431772644802567028663962962025746" 2714 "9283458217850119569539086", 2715 "6703903964971298549787012499102923063739682910296196688861780721" 2716 "8608820150367734884009371490834517138450159290932430254268769414" 2717 "05973284973216824503042158", 2718 "6703903964971298549787012499102923063739682910296196688861780721" 2719 "8608820150367734884009371490834517138450159290932430254268769414" 2720 "05973284973216824503042159", 2721 "1" 2722 }, 2723 { /* between seventh and eighth iteration */ 2724 "5155371529688532178421209781159131443543419764974688878527112131" 2725 "7446518205609427412336183157918981038066636807317733319323257603" 2726 "04416292040754017461076359", 2727 "1005585594745694782468051874865438459560952436544429503329267108" 2728 "2791323022555160232601405723625177570767523893639864538140315412" 2729 "108959927459825236754563832", 2730 "1005585594745694782468051874865438459560952436544429503329267108" 2731 "2791323022555160232601405723625177570767523893639864538140315412" 2732 "108959927459825236754563833", 2733 "1" 2734 }, 2735 /* test vectors for rsaz_512_srq bug, with rcx/rbx=2 */ 2736 { /* between first and second iteration */ 2737 "3155666506033786929967309937640790361084670559125912405342594979" 2738 "4345142818528956285490897841406338022378565972533508820577760065" 2739 "58494345853302083699912572", 2740 "6703903964971298549787012499102923063739682910296196688861780721" 2741 "8608820150367734884009371490834517138450159290932430254268769414" 2742 "05973284973216824503042158", 2743 "6703903964971298549787012499102923063739682910296196688861780721" 2744 "8608820150367734884009371490834517138450159290932430254268769414" 2745 "05973284973216824503042159", 2746 "1" 2747 }, 2748 { /* between second and third iteration */ 2749 "3789819583801342198190405714582958759005991915505282362397087750" 2750 "4213544724644823098843135685133927198668818185338794377239590049" 2751 "41019388529192775771488319", 2752 "6703903964971298549787012499102923063739682910296196688861780721" 2753 "8608820150367734884009371490834517138450159290932430254268769414" 2754 "05973284973216824503042158", 2755 "6703903964971298549787012499102923063739682910296196688861780721" 2756 "8608820150367734884009371490834517138450159290932430254268769414" 2757 "05973284973216824503042159", 2758 "1" 2759 }, 2760 { /* between third and forth iteration */ 2761 "4695752552040706867080542538786056470322165281761525158189220280" 2762 "4025547447667484759200742764246905647644662050122968912279199065" 2763 "48065034299166336940507214", 2764 "6703903964971298549787012499102923063739682910296196688861780721" 2765 "8608820150367734884009371490834517138450159290932430254268769414" 2766 "05973284973216824503042158", 2767 "6703903964971298549787012499102923063739682910296196688861780721" 2768 "8608820150367734884009371490834517138450159290932430254268769414" 2769 "05973284973216824503042159", 2770 "1" 2771 }, 2772 { /* between forth and fifth iteration */ 2773 "2159140240970485794188159431017382878636879856244045329971239574" 2774 "8919691133560661162828034323196457386059819832804593989740268964" 2775 "74502911811812651475927076", 2776 "6703903964971298549787012499102923063739682910296196688861780721" 2777 "8608820150367734884009371490834517138450159290932430254268769414" 2778 "05973284973216824503042158", 2779 "6703903964971298549787012499102923063739682910296196688861780721" 2780 "8608820150367734884009371490834517138450159290932430254268769414" 2781 "05973284973216824503042159", 2782 "1" 2783 }, 2784 { /* between fifth and sixth iteration */ 2785 "5239312332984325668414624633307915097111691815000872662334695514" 2786 "5436533521392362443557163429336808208137221322444780490437871903" 2787 "99972784701334569424519255", 2788 "6703903964971298549787012499102923063739682910296196688861780721" 2789 "8608820150367734884009371490834517138450159290932430254268769414" 2790 "05973284973216824503042158", 2791 "6703903964971298549787012499102923063739682910296196688861780721" 2792 "8608820150367734884009371490834517138450159290932430254268769414" 2793 "05973284973216824503042159", 2794 "1" 2795 }, 2796 { /* between sixth and seventh iteration */ 2797 "1977953647322612860406858017869125467496941904523063466791308891" 2798 "1172796739058531929470539758361774569875505293428856181093904091" 2799 "33788264851714311303725089", 2800 "6703903964971298549787012499102923063739682910296196688861780721" 2801 "8608820150367734884009371490834517138450159290932430254268769414" 2802 "05973284973216824503042158", 2803 "6703903964971298549787012499102923063739682910296196688861780721" 2804 "8608820150367734884009371490834517138450159290932430254268769414" 2805 "05973284973216824503042159", 2806 "1" 2807 }, 2808 { /* between seventh and eighth iteration */ 2809 "6456987954117763835533395796948878140715006860263624787492985786" 2810 "8514630216966738305923915688821526449499763719943997120302368211" 2811 "04813318117996225041943964", 2812 "1340780792994259709957402499820584612747936582059239337772356144" 2813 "3721764030073546976801874298166903427690031858186486050853753882" 2814 "811946551499689575296532556", 2815 "1340780792994259709957402499820584612747936582059239337772356144" 2816 "3721764030073546976801874298166903427690031858186486050853753882" 2817 "811946551499689575296532557", 2818 "1" 2819 } 2820 }; 2821 2822 static int test_mod_exp(int i) 2823 { 2824 const MOD_EXP_TEST *test = &ModExpTests[i]; 2825 int res = 0; 2826 BIGNUM* result = NULL; 2827 BIGNUM *base = NULL, *exponent = NULL, *modulo = NULL; 2828 char *s = NULL; 2829 2830 if (!TEST_ptr(result = BN_new()) 2831 || !TEST_true(BN_dec2bn(&base, test->base)) 2832 || !TEST_true(BN_dec2bn(&exponent, test->exp)) 2833 || !TEST_true(BN_dec2bn(&modulo, test->mod))) 2834 goto err; 2835 2836 if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1)) 2837 goto err; 2838 2839 if (!TEST_ptr(s = BN_bn2dec(result))) 2840 goto err; 2841 2842 if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res))) 2843 goto err; 2844 2845 res = 1; 2846 2847 err: 2848 OPENSSL_free(s); 2849 BN_free(result); 2850 BN_free(base); 2851 BN_free(exponent); 2852 BN_free(modulo); 2853 return res; 2854 } 2855 2856 static int test_mod_exp_consttime(int i) 2857 { 2858 const MOD_EXP_TEST *test = &ModExpTests[i]; 2859 int res = 0; 2860 BIGNUM* result = NULL; 2861 BIGNUM *base = NULL, *exponent = NULL, *modulo = NULL; 2862 char *s = NULL; 2863 2864 if (!TEST_ptr(result = BN_new()) 2865 || !TEST_true(BN_dec2bn(&base, test->base)) 2866 || !TEST_true(BN_dec2bn(&exponent, test->exp)) 2867 || !TEST_true(BN_dec2bn(&modulo, test->mod))) 2868 goto err; 2869 2870 BN_set_flags(base, BN_FLG_CONSTTIME); 2871 BN_set_flags(exponent, BN_FLG_CONSTTIME); 2872 BN_set_flags(modulo, BN_FLG_CONSTTIME); 2873 2874 if (!TEST_int_eq(BN_mod_exp(result, base, exponent, modulo, ctx), 1)) 2875 goto err; 2876 2877 if (!TEST_ptr(s = BN_bn2dec(result))) 2878 goto err; 2879 2880 if (!TEST_mem_eq(s, strlen(s), test->res, strlen(test->res))) 2881 goto err; 2882 2883 res = 1; 2884 2885 err: 2886 OPENSSL_free(s); 2887 BN_free(result); 2888 BN_free(base); 2889 BN_free(exponent); 2890 BN_free(modulo); 2891 return res; 2892 } 2893 2894 /* 2895 * Regression test to ensure BN_mod_exp2_mont fails safely if argument m is 2896 * zero. 2897 */ 2898 static int test_mod_exp2_mont(void) 2899 { 2900 int res = 0; 2901 BIGNUM *exp_result = NULL; 2902 BIGNUM *exp_a1 = NULL, *exp_p1 = NULL, *exp_a2 = NULL, *exp_p2 = NULL, 2903 *exp_m = NULL; 2904 2905 if (!TEST_ptr(exp_result = BN_new()) 2906 || !TEST_ptr(exp_a1 = BN_new()) 2907 || !TEST_ptr(exp_p1 = BN_new()) 2908 || !TEST_ptr(exp_a2 = BN_new()) 2909 || !TEST_ptr(exp_p2 = BN_new()) 2910 || !TEST_ptr(exp_m = BN_new())) 2911 goto err; 2912 2913 if (!TEST_true(BN_one(exp_a1)) 2914 || !TEST_true(BN_one(exp_p1)) 2915 || !TEST_true(BN_one(exp_a2)) 2916 || !TEST_true(BN_one(exp_p2))) 2917 goto err; 2918 2919 BN_zero(exp_m); 2920 2921 /* input of 0 is even, so must fail */ 2922 if (!TEST_int_eq(BN_mod_exp2_mont(exp_result, exp_a1, exp_p1, exp_a2, 2923 exp_p2, exp_m, ctx, NULL), 0)) 2924 goto err; 2925 2926 res = 1; 2927 2928 err: 2929 BN_free(exp_result); 2930 BN_free(exp_a1); 2931 BN_free(exp_p1); 2932 BN_free(exp_a2); 2933 BN_free(exp_p2); 2934 BN_free(exp_m); 2935 return res; 2936 } 2937 2938 static int test_mod_inverse(void) 2939 { 2940 int res = 0; 2941 char *str = NULL; 2942 BIGNUM *a = NULL; 2943 BIGNUM *b = NULL; 2944 BIGNUM *r = NULL; 2945 2946 if (!TEST_true(BN_dec2bn(&a, "5193817943"))) 2947 goto err; 2948 if (!TEST_true(BN_dec2bn(&b, "3259122431"))) 2949 goto err; 2950 if (!TEST_ptr(r = BN_new())) 2951 goto err; 2952 if (!TEST_ptr_eq(BN_mod_inverse(r, a, b, ctx), r)) 2953 goto err; 2954 if (!TEST_ptr_ne(str = BN_bn2dec(r), NULL)) 2955 goto err; 2956 if (!TEST_int_eq(strcmp(str, "2609653924"), 0)) 2957 goto err; 2958 2959 /* Note that this aliases the result with the modulus. */ 2960 if (!TEST_ptr_null(BN_mod_inverse(b, a, b, ctx))) 2961 goto err; 2962 2963 res = 1; 2964 2965 err: 2966 BN_free(a); 2967 BN_free(b); 2968 BN_free(r); 2969 OPENSSL_free(str); 2970 return res; 2971 } 2972 2973 static int test_mod_exp_alias(int idx) 2974 { 2975 int res = 0; 2976 char *str = NULL; 2977 BIGNUM *a = NULL; 2978 BIGNUM *b = NULL; 2979 BIGNUM *c = NULL; 2980 BIGNUM *r = NULL; 2981 2982 if (!TEST_true(BN_dec2bn(&a, "15"))) 2983 goto err; 2984 if (!TEST_true(BN_dec2bn(&b, "10"))) 2985 goto err; 2986 if (!TEST_true(BN_dec2bn(&c, "39"))) 2987 goto err; 2988 if (!TEST_ptr(r = BN_new())) 2989 goto err; 2990 2991 if (!TEST_int_eq((idx == 0 ? BN_mod_exp_simple 2992 : BN_mod_exp_recp)(r, a, b, c, ctx), 1)) 2993 goto err; 2994 if (!TEST_ptr_ne(str = BN_bn2dec(r), NULL)) 2995 goto err; 2996 if (!TEST_str_eq(str, "36")) 2997 goto err; 2998 2999 OPENSSL_free(str); 3000 str = NULL; 3001 3002 BN_copy(r, b); 3003 3004 /* Aliasing with exponent must work. */ 3005 if (!TEST_int_eq((idx == 0 ? BN_mod_exp_simple 3006 : BN_mod_exp_recp)(r, a, r, c, ctx), 1)) 3007 goto err; 3008 if (!TEST_ptr_ne(str = BN_bn2dec(r), NULL)) 3009 goto err; 3010 if (!TEST_str_eq(str, "36")) 3011 goto err; 3012 3013 OPENSSL_free(str); 3014 str = NULL; 3015 3016 /* Aliasing with modulus should return failure for the simple call. */ 3017 if (idx == 0) { 3018 if (!TEST_int_eq(BN_mod_exp_simple(c, a, b, c, ctx), 0)) 3019 goto err; 3020 } else { 3021 if (!TEST_int_eq(BN_mod_exp_recp(c, a, b, c, ctx), 1)) 3022 goto err; 3023 if (!TEST_ptr_ne(str = BN_bn2dec(c), NULL)) 3024 goto err; 3025 if (!TEST_str_eq(str, "36")) 3026 goto err; 3027 } 3028 3029 res = 1; 3030 3031 err: 3032 BN_free(a); 3033 BN_free(b); 3034 BN_free(c); 3035 BN_free(r); 3036 OPENSSL_free(str); 3037 return res; 3038 } 3039 3040 static int file_test_run(STANZA *s) 3041 { 3042 static const FILETEST filetests[] = { 3043 {"Sum", file_sum}, 3044 {"LShift1", file_lshift1}, 3045 {"LShift", file_lshift}, 3046 {"RShift", file_rshift}, 3047 {"Square", file_square}, 3048 {"Product", file_product}, 3049 {"Quotient", file_quotient}, 3050 {"ModMul", file_modmul}, 3051 {"ModExp", file_modexp}, 3052 {"Exp", file_exp}, 3053 {"ModSqrt", file_modsqrt}, 3054 {"GCD", file_gcd}, 3055 }; 3056 int numtests = OSSL_NELEM(filetests); 3057 const FILETEST *tp = filetests; 3058 3059 for ( ; --numtests >= 0; tp++) { 3060 if (findattr(s, tp->name) != NULL) { 3061 if (!tp->func(s)) { 3062 TEST_info("%s:%d: Failed %s test", 3063 s->test_file, s->start, tp->name); 3064 return 0; 3065 } 3066 return 1; 3067 } 3068 } 3069 TEST_info("%s:%d: Unknown test", s->test_file, s->start); 3070 return 0; 3071 } 3072 3073 static int run_file_tests(int i) 3074 { 3075 STANZA *s = NULL; 3076 char *testfile = test_get_argument(i); 3077 int c; 3078 3079 if (!TEST_ptr(s = OPENSSL_zalloc(sizeof(*s)))) 3080 return 0; 3081 if (!test_start_file(s, testfile)) { 3082 OPENSSL_free(s); 3083 return 0; 3084 } 3085 3086 /* Read test file. */ 3087 while (!BIO_eof(s->fp) && test_readstanza(s)) { 3088 if (s->numpairs == 0) 3089 continue; 3090 if (!file_test_run(s)) 3091 s->errors++; 3092 s->numtests++; 3093 test_clearstanza(s); 3094 } 3095 test_end_file(s); 3096 c = s->errors; 3097 OPENSSL_free(s); 3098 3099 return c == 0; 3100 } 3101 3102 typedef enum OPTION_choice { 3103 OPT_ERR = -1, 3104 OPT_EOF = 0, 3105 OPT_STOCHASTIC_TESTS, 3106 OPT_TEST_ENUM 3107 } OPTION_CHOICE; 3108 3109 const OPTIONS *test_get_options(void) 3110 { 3111 static const OPTIONS test_options[] = { 3112 OPT_TEST_OPTIONS_WITH_EXTRA_USAGE("[file...]\n"), 3113 { "stochastic", OPT_STOCHASTIC_TESTS, '-', "Run stochastic tests" }, 3114 { OPT_HELP_STR, 1, '-', 3115 "file\tFile to run tests on. Normal tests are not run\n" }, 3116 { NULL } 3117 }; 3118 return test_options; 3119 } 3120 3121 int setup_tests(void) 3122 { 3123 OPTION_CHOICE o; 3124 int n, stochastic = 0; 3125 3126 while ((o = opt_next()) != OPT_EOF) { 3127 switch (o) { 3128 case OPT_STOCHASTIC_TESTS: 3129 stochastic = 1; 3130 break; 3131 case OPT_TEST_CASES: 3132 break; 3133 default: 3134 case OPT_ERR: 3135 return 0; 3136 } 3137 } 3138 n = test_get_argument_count(); 3139 3140 if (!TEST_ptr(ctx = BN_CTX_new())) 3141 return 0; 3142 3143 if (n == 0) { 3144 ADD_TEST(test_sub); 3145 ADD_TEST(test_div_recip); 3146 ADD_ALL_TESTS(test_signed_mod_replace_ab, OSSL_NELEM(signed_mod_tests)); 3147 ADD_ALL_TESTS(test_signed_mod_replace_ba, OSSL_NELEM(signed_mod_tests)); 3148 ADD_TEST(test_mod); 3149 ADD_TEST(test_mod_inverse); 3150 ADD_ALL_TESTS(test_mod_exp_alias, 2); 3151 ADD_TEST(test_modexp_mont5); 3152 ADD_TEST(test_kronecker); 3153 ADD_TEST(test_rand); 3154 ADD_TEST(test_bn2padded); 3155 ADD_TEST(test_dec2bn); 3156 ADD_TEST(test_hex2bn); 3157 ADD_TEST(test_asc2bn); 3158 ADD_ALL_TESTS(test_mpi, (int)OSSL_NELEM(kMPITests)); 3159 ADD_TEST(test_negzero); 3160 ADD_TEST(test_badmod); 3161 ADD_TEST(test_expmodzero); 3162 ADD_TEST(test_expmodone); 3163 ADD_ALL_TESTS(test_smallprime, 16); 3164 ADD_ALL_TESTS(test_smallsafeprime, 16); 3165 ADD_TEST(test_swap); 3166 ADD_TEST(test_ctx_consttime_flag); 3167 #ifndef OPENSSL_NO_EC2M 3168 ADD_TEST(test_gf2m_add); 3169 ADD_TEST(test_gf2m_mod); 3170 ADD_TEST(test_gf2m_mul); 3171 ADD_TEST(test_gf2m_sqr); 3172 ADD_TEST(test_gf2m_modinv); 3173 ADD_TEST(test_gf2m_moddiv); 3174 ADD_TEST(test_gf2m_modexp); 3175 ADD_TEST(test_gf2m_modsqrt); 3176 ADD_TEST(test_gf2m_modsolvequad); 3177 #endif 3178 ADD_ALL_TESTS(test_is_prime, (int)OSSL_NELEM(primes)); 3179 ADD_ALL_TESTS(test_not_prime, (int)OSSL_NELEM(not_primes)); 3180 ADD_TEST(test_gcd_prime); 3181 ADD_ALL_TESTS(test_mod_exp, (int)OSSL_NELEM(ModExpTests)); 3182 ADD_ALL_TESTS(test_mod_exp_consttime, (int)OSSL_NELEM(ModExpTests)); 3183 ADD_TEST(test_mod_exp2_mont); 3184 if (stochastic) 3185 ADD_TEST(test_rand_range); 3186 } else { 3187 ADD_ALL_TESTS(run_file_tests, n); 3188 } 3189 return 1; 3190 } 3191 3192 void cleanup_tests(void) 3193 { 3194 BN_CTX_free(ctx); 3195 } 3196