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