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