1 /* 2 * Copyright 1995-2023 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 10 #include <assert.h> 11 #include <limits.h> 12 #include "internal/cryptlib.h" 13 #include "bn_local.h" 14 #include <openssl/opensslconf.h> 15 #include "internal/constant_time.h" 16 17 /* This stuff appears to be completely unused, so is deprecated */ 18 #if OPENSSL_API_COMPAT < 0x00908000L 19 /*- 20 * For a 32 bit machine 21 * 2 - 4 == 128 22 * 3 - 8 == 256 23 * 4 - 16 == 512 24 * 5 - 32 == 1024 25 * 6 - 64 == 2048 26 * 7 - 128 == 4096 27 * 8 - 256 == 8192 28 */ 29 static int bn_limit_bits = 0; 30 static int bn_limit_num = 8; /* (1<<bn_limit_bits) */ 31 static int bn_limit_bits_low = 0; 32 static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */ 33 static int bn_limit_bits_high = 0; 34 static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */ 35 static int bn_limit_bits_mont = 0; 36 static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */ 37 38 void BN_set_params(int mult, int high, int low, int mont) 39 { 40 if (mult >= 0) { 41 if (mult > (int)(sizeof(int) * 8) - 1) 42 mult = sizeof(int) * 8 - 1; 43 bn_limit_bits = mult; 44 bn_limit_num = 1 << mult; 45 } 46 if (high >= 0) { 47 if (high > (int)(sizeof(int) * 8) - 1) 48 high = sizeof(int) * 8 - 1; 49 bn_limit_bits_high = high; 50 bn_limit_num_high = 1 << high; 51 } 52 if (low >= 0) { 53 if (low > (int)(sizeof(int) * 8) - 1) 54 low = sizeof(int) * 8 - 1; 55 bn_limit_bits_low = low; 56 bn_limit_num_low = 1 << low; 57 } 58 if (mont >= 0) { 59 if (mont > (int)(sizeof(int) * 8) - 1) 60 mont = sizeof(int) * 8 - 1; 61 bn_limit_bits_mont = mont; 62 bn_limit_num_mont = 1 << mont; 63 } 64 } 65 66 int BN_get_params(int which) 67 { 68 if (which == 0) 69 return bn_limit_bits; 70 else if (which == 1) 71 return bn_limit_bits_high; 72 else if (which == 2) 73 return bn_limit_bits_low; 74 else if (which == 3) 75 return bn_limit_bits_mont; 76 else 77 return 0; 78 } 79 #endif 80 81 const BIGNUM *BN_value_one(void) 82 { 83 static const BN_ULONG data_one = 1L; 84 static const BIGNUM const_one = 85 { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA }; 86 87 return &const_one; 88 } 89 90 /* 91 * Old Visual Studio ARM compiler miscompiles BN_num_bits_word() 92 * https://mta.openssl.org/pipermail/openssl-users/2018-August/008465.html 93 */ 94 #if defined(_MSC_VER) && defined(_ARM_) && defined(_WIN32_WCE) \ 95 && _MSC_VER>=1400 && _MSC_VER<1501 96 # define MS_BROKEN_BN_num_bits_word 97 # pragma optimize("", off) 98 #endif 99 int BN_num_bits_word(BN_ULONG l) 100 { 101 BN_ULONG x, mask; 102 int bits = (l != 0); 103 104 #if BN_BITS2 > 32 105 x = l >> 32; 106 mask = (0 - x) & BN_MASK2; 107 mask = (0 - (mask >> (BN_BITS2 - 1))); 108 bits += 32 & mask; 109 l ^= (x ^ l) & mask; 110 #endif 111 112 x = l >> 16; 113 mask = (0 - x) & BN_MASK2; 114 mask = (0 - (mask >> (BN_BITS2 - 1))); 115 bits += 16 & mask; 116 l ^= (x ^ l) & mask; 117 118 x = l >> 8; 119 mask = (0 - x) & BN_MASK2; 120 mask = (0 - (mask >> (BN_BITS2 - 1))); 121 bits += 8 & mask; 122 l ^= (x ^ l) & mask; 123 124 x = l >> 4; 125 mask = (0 - x) & BN_MASK2; 126 mask = (0 - (mask >> (BN_BITS2 - 1))); 127 bits += 4 & mask; 128 l ^= (x ^ l) & mask; 129 130 x = l >> 2; 131 mask = (0 - x) & BN_MASK2; 132 mask = (0 - (mask >> (BN_BITS2 - 1))); 133 bits += 2 & mask; 134 l ^= (x ^ l) & mask; 135 136 x = l >> 1; 137 mask = (0 - x) & BN_MASK2; 138 mask = (0 - (mask >> (BN_BITS2 - 1))); 139 bits += 1 & mask; 140 141 return bits; 142 } 143 #ifdef MS_BROKEN_BN_num_bits_word 144 # pragma optimize("", on) 145 #endif 146 147 /* 148 * This function still leaks `a->dmax`: it's caller's responsibility to 149 * expand the input `a` in advance to a public length. 150 */ 151 static ossl_inline 152 int bn_num_bits_consttime(const BIGNUM *a) 153 { 154 int j, ret; 155 unsigned int mask, past_i; 156 int i = a->top - 1; 157 bn_check_top(a); 158 159 for (j = 0, past_i = 0, ret = 0; j < a->dmax; j++) { 160 mask = constant_time_eq_int(i, j); /* 0xff..ff if i==j, 0x0 otherwise */ 161 162 ret += BN_BITS2 & (~mask & ~past_i); 163 ret += BN_num_bits_word(a->d[j]) & mask; 164 165 past_i |= mask; /* past_i will become 0xff..ff after i==j */ 166 } 167 168 /* 169 * if BN_is_zero(a) => i is -1 and ret contains garbage, so we mask the 170 * final result. 171 */ 172 mask = ~(constant_time_eq_int(i, ((int)-1))); 173 174 return ret & mask; 175 } 176 177 int BN_num_bits(const BIGNUM *a) 178 { 179 int i = a->top - 1; 180 bn_check_top(a); 181 182 if (a->flags & BN_FLG_CONSTTIME) { 183 /* 184 * We assume that BIGNUMs flagged as CONSTTIME have also been expanded 185 * so that a->dmax is not leaking secret information. 186 * 187 * In other words, it's the caller's responsibility to ensure `a` has 188 * been preallocated in advance to a public length if we hit this 189 * branch. 190 * 191 */ 192 return bn_num_bits_consttime(a); 193 } 194 195 if (BN_is_zero(a)) 196 return 0; 197 198 return ((i * BN_BITS2) + BN_num_bits_word(a->d[i])); 199 } 200 201 static void bn_free_d(BIGNUM *a, int clear) 202 { 203 if (BN_get_flags(a, BN_FLG_SECURE)) 204 OPENSSL_secure_clear_free(a->d, a->dmax * sizeof(a->d[0])); 205 else if (clear != 0) 206 OPENSSL_clear_free(a->d, a->dmax * sizeof(a->d[0])); 207 else 208 OPENSSL_free(a->d); 209 } 210 211 212 void BN_clear_free(BIGNUM *a) 213 { 214 if (a == NULL) 215 return; 216 if (a->d != NULL && !BN_get_flags(a, BN_FLG_STATIC_DATA)) 217 bn_free_d(a, 1); 218 if (BN_get_flags(a, BN_FLG_MALLOCED)) { 219 OPENSSL_cleanse(a, sizeof(*a)); 220 OPENSSL_free(a); 221 } 222 } 223 224 void BN_free(BIGNUM *a) 225 { 226 if (a == NULL) 227 return; 228 if (!BN_get_flags(a, BN_FLG_STATIC_DATA)) 229 bn_free_d(a, 0); 230 if (a->flags & BN_FLG_MALLOCED) 231 OPENSSL_free(a); 232 } 233 234 void bn_init(BIGNUM *a) 235 { 236 static BIGNUM nilbn; 237 238 *a = nilbn; 239 bn_check_top(a); 240 } 241 242 BIGNUM *BN_new(void) 243 { 244 BIGNUM *ret; 245 246 if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) { 247 BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE); 248 return NULL; 249 } 250 ret->flags = BN_FLG_MALLOCED; 251 bn_check_top(ret); 252 return ret; 253 } 254 255 BIGNUM *BN_secure_new(void) 256 { 257 BIGNUM *ret = BN_new(); 258 if (ret != NULL) 259 ret->flags |= BN_FLG_SECURE; 260 return ret; 261 } 262 263 /* This is used by bn_expand2() */ 264 /* The caller MUST check that words > b->dmax before calling this */ 265 static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) 266 { 267 BN_ULONG *a = NULL; 268 269 if (words > (INT_MAX / (4 * BN_BITS2))) { 270 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG); 271 return NULL; 272 } 273 if (BN_get_flags(b, BN_FLG_STATIC_DATA)) { 274 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 275 return NULL; 276 } 277 if (BN_get_flags(b, BN_FLG_SECURE)) 278 a = OPENSSL_secure_zalloc(words * sizeof(*a)); 279 else 280 a = OPENSSL_zalloc(words * sizeof(*a)); 281 if (a == NULL) { 282 BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE); 283 return NULL; 284 } 285 286 assert(b->top <= words); 287 if (b->top > 0) 288 memcpy(a, b->d, sizeof(*a) * b->top); 289 290 return a; 291 } 292 293 /* 294 * This is an internal function that should not be used in applications. It 295 * ensures that 'b' has enough room for a 'words' word number and initialises 296 * any unused part of b->d with leading zeros. It is mostly used by the 297 * various BIGNUM routines. If there is an error, NULL is returned. If not, 298 * 'b' is returned. 299 */ 300 301 BIGNUM *bn_expand2(BIGNUM *b, int words) 302 { 303 if (words > b->dmax) { 304 BN_ULONG *a = bn_expand_internal(b, words); 305 if (!a) 306 return NULL; 307 if (b->d != NULL) 308 bn_free_d(b, 1); 309 b->d = a; 310 b->dmax = words; 311 } 312 313 return b; 314 } 315 316 BIGNUM *BN_dup(const BIGNUM *a) 317 { 318 BIGNUM *t; 319 320 if (a == NULL) 321 return NULL; 322 bn_check_top(a); 323 324 t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new(); 325 if (t == NULL) 326 return NULL; 327 if (!BN_copy(t, a)) { 328 BN_free(t); 329 return NULL; 330 } 331 bn_check_top(t); 332 return t; 333 } 334 335 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) 336 { 337 int bn_words; 338 339 bn_check_top(b); 340 341 bn_words = BN_get_flags(b, BN_FLG_CONSTTIME) ? b->dmax : b->top; 342 343 if (a == b) 344 return a; 345 if (bn_wexpand(a, bn_words) == NULL) 346 return NULL; 347 348 if (b->top > 0) 349 memcpy(a->d, b->d, sizeof(b->d[0]) * bn_words); 350 351 a->neg = b->neg; 352 a->top = b->top; 353 a->flags |= b->flags & BN_FLG_FIXED_TOP; 354 bn_check_top(a); 355 return a; 356 } 357 358 #define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \ 359 | BN_FLG_CONSTTIME \ 360 | BN_FLG_SECURE \ 361 | BN_FLG_FIXED_TOP)) 362 #define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED)) 363 364 void BN_swap(BIGNUM *a, BIGNUM *b) 365 { 366 int flags_old_a, flags_old_b; 367 BN_ULONG *tmp_d; 368 int tmp_top, tmp_dmax, tmp_neg; 369 370 bn_check_top(a); 371 bn_check_top(b); 372 373 flags_old_a = a->flags; 374 flags_old_b = b->flags; 375 376 tmp_d = a->d; 377 tmp_top = a->top; 378 tmp_dmax = a->dmax; 379 tmp_neg = a->neg; 380 381 a->d = b->d; 382 a->top = b->top; 383 a->dmax = b->dmax; 384 a->neg = b->neg; 385 386 b->d = tmp_d; 387 b->top = tmp_top; 388 b->dmax = tmp_dmax; 389 b->neg = tmp_neg; 390 391 a->flags = FLAGS_STRUCT(flags_old_a) | FLAGS_DATA(flags_old_b); 392 b->flags = FLAGS_STRUCT(flags_old_b) | FLAGS_DATA(flags_old_a); 393 bn_check_top(a); 394 bn_check_top(b); 395 } 396 397 void BN_clear(BIGNUM *a) 398 { 399 if (a == NULL) 400 return; 401 bn_check_top(a); 402 if (a->d != NULL) 403 OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax); 404 a->neg = 0; 405 a->top = 0; 406 a->flags &= ~BN_FLG_FIXED_TOP; 407 } 408 409 BN_ULONG BN_get_word(const BIGNUM *a) 410 { 411 if (a->top > 1) 412 return BN_MASK2; 413 else if (a->top == 1) 414 return a->d[0]; 415 /* a->top == 0 */ 416 return 0; 417 } 418 419 int BN_set_word(BIGNUM *a, BN_ULONG w) 420 { 421 bn_check_top(a); 422 if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL) 423 return 0; 424 a->neg = 0; 425 a->d[0] = w; 426 a->top = (w ? 1 : 0); 427 a->flags &= ~BN_FLG_FIXED_TOP; 428 bn_check_top(a); 429 return 1; 430 } 431 432 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) 433 { 434 unsigned int i, m; 435 unsigned int n; 436 BN_ULONG l; 437 BIGNUM *bn = NULL; 438 439 if (ret == NULL) 440 ret = bn = BN_new(); 441 if (ret == NULL) 442 return NULL; 443 bn_check_top(ret); 444 /* Skip leading zero's. */ 445 for ( ; len > 0 && *s == 0; s++, len--) 446 continue; 447 n = len; 448 if (n == 0) { 449 ret->top = 0; 450 return ret; 451 } 452 i = ((n - 1) / BN_BYTES) + 1; 453 m = ((n - 1) % (BN_BYTES)); 454 if (bn_wexpand(ret, (int)i) == NULL) { 455 BN_free(bn); 456 return NULL; 457 } 458 ret->top = i; 459 ret->neg = 0; 460 l = 0; 461 while (n--) { 462 l = (l << 8L) | *(s++); 463 if (m-- == 0) { 464 ret->d[--i] = l; 465 l = 0; 466 m = BN_BYTES - 1; 467 } 468 } 469 /* 470 * need to call this due to clear byte at top if avoiding having the top 471 * bit set (-ve number) 472 */ 473 bn_correct_top(ret); 474 return ret; 475 } 476 477 typedef enum {big, little} endianess_t; 478 479 /* ignore negative */ 480 static 481 int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen, endianess_t endianess) 482 { 483 int n; 484 size_t i, lasti, j, atop, mask; 485 BN_ULONG l; 486 487 /* 488 * In case |a| is fixed-top, BN_num_bytes can return bogus length, 489 * but it's assumed that fixed-top inputs ought to be "nominated" 490 * even for padded output, so it works out... 491 */ 492 n = BN_num_bytes(a); 493 if (tolen == -1) { 494 tolen = n; 495 } else if (tolen < n) { /* uncommon/unlike case */ 496 BIGNUM temp = *a; 497 498 bn_correct_top(&temp); 499 n = BN_num_bytes(&temp); 500 if (tolen < n) 501 return -1; 502 } 503 504 /* Swipe through whole available data and don't give away padded zero. */ 505 atop = a->dmax * BN_BYTES; 506 if (atop == 0) { 507 OPENSSL_cleanse(to, tolen); 508 return tolen; 509 } 510 511 lasti = atop - 1; 512 atop = a->top * BN_BYTES; 513 if (endianess == big) 514 to += tolen; /* start from the end of the buffer */ 515 for (i = 0, j = 0; j < (size_t)tolen; j++) { 516 unsigned char val; 517 l = a->d[i / BN_BYTES]; 518 mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1)); 519 val = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask); 520 if (endianess == big) 521 *--to = val; 522 else 523 *to++ = val; 524 i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */ 525 } 526 527 return tolen; 528 } 529 530 int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) 531 { 532 if (tolen < 0) 533 return -1; 534 return bn2binpad(a, to, tolen, big); 535 } 536 537 int BN_bn2bin(const BIGNUM *a, unsigned char *to) 538 { 539 return bn2binpad(a, to, -1, big); 540 } 541 542 BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret) 543 { 544 unsigned int i, m; 545 unsigned int n; 546 BN_ULONG l; 547 BIGNUM *bn = NULL; 548 549 if (ret == NULL) 550 ret = bn = BN_new(); 551 if (ret == NULL) 552 return NULL; 553 bn_check_top(ret); 554 s += len; 555 /* Skip trailing zeroes. */ 556 for ( ; len > 0 && s[-1] == 0; s--, len--) 557 continue; 558 n = len; 559 if (n == 0) { 560 ret->top = 0; 561 return ret; 562 } 563 i = ((n - 1) / BN_BYTES) + 1; 564 m = ((n - 1) % (BN_BYTES)); 565 if (bn_wexpand(ret, (int)i) == NULL) { 566 BN_free(bn); 567 return NULL; 568 } 569 ret->top = i; 570 ret->neg = 0; 571 l = 0; 572 while (n--) { 573 s--; 574 l = (l << 8L) | *s; 575 if (m-- == 0) { 576 ret->d[--i] = l; 577 l = 0; 578 m = BN_BYTES - 1; 579 } 580 } 581 /* 582 * need to call this due to clear byte at top if avoiding having the top 583 * bit set (-ve number) 584 */ 585 bn_correct_top(ret); 586 return ret; 587 } 588 589 int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen) 590 { 591 if (tolen < 0) 592 return -1; 593 return bn2binpad(a, to, tolen, little); 594 } 595 596 int BN_ucmp(const BIGNUM *a, const BIGNUM *b) 597 { 598 int i; 599 BN_ULONG t1, t2, *ap, *bp; 600 601 bn_check_top(a); 602 bn_check_top(b); 603 604 i = a->top - b->top; 605 if (i != 0) 606 return i; 607 ap = a->d; 608 bp = b->d; 609 for (i = a->top - 1; i >= 0; i--) { 610 t1 = ap[i]; 611 t2 = bp[i]; 612 if (t1 != t2) 613 return ((t1 > t2) ? 1 : -1); 614 } 615 return 0; 616 } 617 618 int BN_cmp(const BIGNUM *a, const BIGNUM *b) 619 { 620 int i; 621 int gt, lt; 622 BN_ULONG t1, t2; 623 624 if ((a == NULL) || (b == NULL)) { 625 if (a != NULL) 626 return -1; 627 else if (b != NULL) 628 return 1; 629 else 630 return 0; 631 } 632 633 bn_check_top(a); 634 bn_check_top(b); 635 636 if (a->neg != b->neg) { 637 if (a->neg) 638 return -1; 639 else 640 return 1; 641 } 642 if (a->neg == 0) { 643 gt = 1; 644 lt = -1; 645 } else { 646 gt = -1; 647 lt = 1; 648 } 649 650 if (a->top > b->top) 651 return gt; 652 if (a->top < b->top) 653 return lt; 654 for (i = a->top - 1; i >= 0; i--) { 655 t1 = a->d[i]; 656 t2 = b->d[i]; 657 if (t1 > t2) 658 return gt; 659 if (t1 < t2) 660 return lt; 661 } 662 return 0; 663 } 664 665 int BN_set_bit(BIGNUM *a, int n) 666 { 667 int i, j, k; 668 669 if (n < 0) 670 return 0; 671 672 i = n / BN_BITS2; 673 j = n % BN_BITS2; 674 if (a->top <= i) { 675 if (bn_wexpand(a, i + 1) == NULL) 676 return 0; 677 for (k = a->top; k < i + 1; k++) 678 a->d[k] = 0; 679 a->top = i + 1; 680 a->flags &= ~BN_FLG_FIXED_TOP; 681 } 682 683 a->d[i] |= (((BN_ULONG)1) << j); 684 bn_check_top(a); 685 return 1; 686 } 687 688 int BN_clear_bit(BIGNUM *a, int n) 689 { 690 int i, j; 691 692 bn_check_top(a); 693 if (n < 0) 694 return 0; 695 696 i = n / BN_BITS2; 697 j = n % BN_BITS2; 698 if (a->top <= i) 699 return 0; 700 701 a->d[i] &= (~(((BN_ULONG)1) << j)); 702 bn_correct_top(a); 703 return 1; 704 } 705 706 int BN_is_bit_set(const BIGNUM *a, int n) 707 { 708 int i, j; 709 710 bn_check_top(a); 711 if (n < 0) 712 return 0; 713 i = n / BN_BITS2; 714 j = n % BN_BITS2; 715 if (a->top <= i) 716 return 0; 717 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); 718 } 719 720 int BN_mask_bits(BIGNUM *a, int n) 721 { 722 int b, w; 723 724 bn_check_top(a); 725 if (n < 0) 726 return 0; 727 728 w = n / BN_BITS2; 729 b = n % BN_BITS2; 730 if (w >= a->top) 731 return 0; 732 if (b == 0) 733 a->top = w; 734 else { 735 a->top = w + 1; 736 a->d[w] &= ~(BN_MASK2 << b); 737 } 738 bn_correct_top(a); 739 return 1; 740 } 741 742 void BN_set_negative(BIGNUM *a, int b) 743 { 744 if (b && !BN_is_zero(a)) 745 a->neg = 1; 746 else 747 a->neg = 0; 748 } 749 750 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) 751 { 752 int i; 753 BN_ULONG aa, bb; 754 755 if (n == 0) 756 return 0; 757 758 aa = a[n - 1]; 759 bb = b[n - 1]; 760 if (aa != bb) 761 return ((aa > bb) ? 1 : -1); 762 for (i = n - 2; i >= 0; i--) { 763 aa = a[i]; 764 bb = b[i]; 765 if (aa != bb) 766 return ((aa > bb) ? 1 : -1); 767 } 768 return 0; 769 } 770 771 /* 772 * Here follows a specialised variants of bn_cmp_words(). It has the 773 * capability of performing the operation on arrays of different sizes. The 774 * sizes of those arrays is expressed through cl, which is the common length 775 * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the 776 * two lengths, calculated as len(a)-len(b). All lengths are the number of 777 * BN_ULONGs... 778 */ 779 780 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) 781 { 782 int n, i; 783 n = cl - 1; 784 785 if (dl < 0) { 786 for (i = dl; i < 0; i++) { 787 if (b[n - i] != 0) 788 return -1; /* a < b */ 789 } 790 } 791 if (dl > 0) { 792 for (i = dl; i > 0; i--) { 793 if (a[n + i] != 0) 794 return 1; /* a > b */ 795 } 796 } 797 return bn_cmp_words(a, b, cl); 798 } 799 800 /*- 801 * Constant-time conditional swap of a and b. 802 * a and b are swapped if condition is not 0. 803 * nwords is the number of words to swap. 804 * Assumes that at least nwords are allocated in both a and b. 805 * Assumes that no more than nwords are used by either a or b. 806 */ 807 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) 808 { 809 BN_ULONG t; 810 int i; 811 812 if (a == b) 813 return; 814 815 bn_wcheck_size(a, nwords); 816 bn_wcheck_size(b, nwords); 817 818 condition = ((~condition & ((condition - 1))) >> (BN_BITS2 - 1)) - 1; 819 820 t = (a->top ^ b->top) & condition; 821 a->top ^= t; 822 b->top ^= t; 823 824 t = (a->neg ^ b->neg) & condition; 825 a->neg ^= t; 826 b->neg ^= t; 827 828 /*- 829 * BN_FLG_STATIC_DATA: indicates that data may not be written to. Intention 830 * is actually to treat it as it's read-only data, and some (if not most) 831 * of it does reside in read-only segment. In other words observation of 832 * BN_FLG_STATIC_DATA in BN_consttime_swap should be treated as fatal 833 * condition. It would either cause SEGV or effectively cause data 834 * corruption. 835 * 836 * BN_FLG_MALLOCED: refers to BN structure itself, and hence must be 837 * preserved. 838 * 839 * BN_FLG_SECURE: must be preserved, because it determines how x->d was 840 * allocated and hence how to free it. 841 * 842 * BN_FLG_CONSTTIME: sufficient to mask and swap 843 * 844 * BN_FLG_FIXED_TOP: indicates that we haven't called bn_correct_top() on 845 * the data, so the d array may be padded with additional 0 values (i.e. 846 * top could be greater than the minimal value that it could be). We should 847 * be swapping it 848 */ 849 850 #define BN_CONSTTIME_SWAP_FLAGS (BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP) 851 852 t = ((a->flags ^ b->flags) & BN_CONSTTIME_SWAP_FLAGS) & condition; 853 a->flags ^= t; 854 b->flags ^= t; 855 856 /* conditionally swap the data */ 857 for (i = 0; i < nwords; i++) { 858 t = (a->d[i] ^ b->d[i]) & condition; 859 a->d[i] ^= t; 860 b->d[i] ^= t; 861 } 862 } 863 864 #undef BN_CONSTTIME_SWAP_FLAGS 865 866 /* Bits of security, see SP800-57 */ 867 868 int BN_security_bits(int L, int N) 869 { 870 int secbits, bits; 871 if (L >= 15360) 872 secbits = 256; 873 else if (L >= 7680) 874 secbits = 192; 875 else if (L >= 3072) 876 secbits = 128; 877 else if (L >= 2048) 878 secbits = 112; 879 else if (L >= 1024) 880 secbits = 80; 881 else 882 return 0; 883 if (N == -1) 884 return secbits; 885 bits = N / 2; 886 if (bits < 80) 887 return 0; 888 return bits >= secbits ? secbits : bits; 889 } 890 891 void BN_zero_ex(BIGNUM *a) 892 { 893 a->neg = 0; 894 a->top = 0; 895 a->flags &= ~BN_FLG_FIXED_TOP; 896 } 897 898 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w) 899 { 900 return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0)); 901 } 902 903 int BN_is_zero(const BIGNUM *a) 904 { 905 return a->top == 0; 906 } 907 908 int BN_is_one(const BIGNUM *a) 909 { 910 return BN_abs_is_word(a, 1) && !a->neg; 911 } 912 913 int BN_is_word(const BIGNUM *a, const BN_ULONG w) 914 { 915 return BN_abs_is_word(a, w) && (!w || !a->neg); 916 } 917 918 int BN_is_odd(const BIGNUM *a) 919 { 920 return (a->top > 0) && (a->d[0] & 1); 921 } 922 923 int BN_is_negative(const BIGNUM *a) 924 { 925 return (a->neg != 0); 926 } 927 928 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont, 929 BN_CTX *ctx) 930 { 931 return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx); 932 } 933 934 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags) 935 { 936 dest->d = b->d; 937 dest->top = b->top; 938 dest->dmax = b->dmax; 939 dest->neg = b->neg; 940 dest->flags = ((dest->flags & BN_FLG_MALLOCED) 941 | (b->flags & ~BN_FLG_MALLOCED) 942 | BN_FLG_STATIC_DATA | flags); 943 } 944 945 BN_GENCB *BN_GENCB_new(void) 946 { 947 BN_GENCB *ret; 948 949 if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) { 950 BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE); 951 return NULL; 952 } 953 954 return ret; 955 } 956 957 void BN_GENCB_free(BN_GENCB *cb) 958 { 959 if (cb == NULL) 960 return; 961 OPENSSL_free(cb); 962 } 963 964 void BN_set_flags(BIGNUM *b, int n) 965 { 966 b->flags |= n; 967 } 968 969 int BN_get_flags(const BIGNUM *b, int n) 970 { 971 return b->flags & n; 972 } 973 974 /* Populate a BN_GENCB structure with an "old"-style callback */ 975 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *), 976 void *cb_arg) 977 { 978 BN_GENCB *tmp_gencb = gencb; 979 tmp_gencb->ver = 1; 980 tmp_gencb->arg = cb_arg; 981 tmp_gencb->cb.cb_1 = callback; 982 } 983 984 /* Populate a BN_GENCB structure with a "new"-style callback */ 985 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *), 986 void *cb_arg) 987 { 988 BN_GENCB *tmp_gencb = gencb; 989 tmp_gencb->ver = 2; 990 tmp_gencb->arg = cb_arg; 991 tmp_gencb->cb.cb_2 = callback; 992 } 993 994 void *BN_GENCB_get_arg(BN_GENCB *cb) 995 { 996 return cb->arg; 997 } 998 999 BIGNUM *bn_wexpand(BIGNUM *a, int words) 1000 { 1001 return (words <= a->dmax) ? a : bn_expand2(a, words); 1002 } 1003 1004 void bn_correct_top_consttime(BIGNUM *a) 1005 { 1006 int j, atop; 1007 BN_ULONG limb; 1008 unsigned int mask; 1009 1010 for (j = 0, atop = 0; j < a->dmax; j++) { 1011 limb = a->d[j]; 1012 limb |= 0 - limb; 1013 limb >>= BN_BITS2 - 1; 1014 limb = 0 - limb; 1015 mask = (unsigned int)limb; 1016 mask &= constant_time_msb(j - a->top); 1017 atop = constant_time_select_int(mask, j + 1, atop); 1018 } 1019 1020 mask = constant_time_eq_int(atop, 0); 1021 a->top = atop; 1022 a->neg = constant_time_select_int(mask, 0, a->neg); 1023 a->flags &= ~BN_FLG_FIXED_TOP; 1024 } 1025 1026 void bn_correct_top(BIGNUM *a) 1027 { 1028 BN_ULONG *ftl; 1029 int tmp_top = a->top; 1030 1031 if (tmp_top > 0) { 1032 for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) { 1033 ftl--; 1034 if (*ftl != 0) 1035 break; 1036 } 1037 a->top = tmp_top; 1038 } 1039 if (a->top == 0) 1040 a->neg = 0; 1041 a->flags &= ~BN_FLG_FIXED_TOP; 1042 bn_pollute(a); 1043 } 1044