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