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