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