bn_lib.c revision 352193
1/* crypto/bn/bn_lib.c */ 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3 * All rights reserved. 4 * 5 * This package is an SSL implementation written 6 * by Eric Young (eay@cryptsoft.com). 7 * The implementation was written so as to conform with Netscapes SSL. 8 * 9 * This library is free for commercial and non-commercial use as long as 10 * the following conditions are aheared to. The following conditions 11 * apply to all code found in this distribution, be it the RC4, RSA, 12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13 * included with this distribution is covered by the same copyright terms 14 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15 * 16 * Copyright remains Eric Young's, and as such any Copyright notices in 17 * the code are not to be removed. 18 * If this package is used in a product, Eric Young should be given attribution 19 * as the author of the parts of the library used. 20 * This can be in the form of a textual message at program startup or 21 * in documentation (online or textual) provided with the package. 22 * 23 * Redistribution and use in source and binary forms, with or without 24 * modification, are permitted provided that the following conditions 25 * are met: 26 * 1. Redistributions of source code must retain the copyright 27 * notice, this list of conditions and the following disclaimer. 28 * 2. Redistributions in binary form must reproduce the above copyright 29 * notice, this list of conditions and the following disclaimer in the 30 * documentation and/or other materials provided with the distribution. 31 * 3. All advertising materials mentioning features or use of this software 32 * must display the following acknowledgement: 33 * "This product includes cryptographic software written by 34 * Eric Young (eay@cryptsoft.com)" 35 * The word 'cryptographic' can be left out if the rouines from the library 36 * being used are not cryptographic related :-). 37 * 4. If you include any Windows specific code (or a derivative thereof) from 38 * the apps directory (application code) you must include an acknowledgement: 39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40 * 41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51 * SUCH DAMAGE. 52 * 53 * The licence and distribution terms for any publically available version or 54 * derivative of this code cannot be changed. i.e. this code cannot simply be 55 * copied and put under another distribution licence 56 * [including the GNU Public Licence.] 57 */ 58 59#ifndef BN_DEBUG 60# undef NDEBUG /* avoid conflicting definitions */ 61# define NDEBUG 62#endif 63 64#include <assert.h> 65#include <limits.h> 66#include <stdio.h> 67#include "cryptlib.h" 68#include "bn_lcl.h" 69#include "constant_time_locl.h" 70 71const char BN_version[] = "Big Number" OPENSSL_VERSION_PTEXT; 72 73/* This stuff appears to be completely unused, so is deprecated */ 74#ifndef OPENSSL_NO_DEPRECATED 75/*- 76 * For a 32 bit machine 77 * 2 - 4 == 128 78 * 3 - 8 == 256 79 * 4 - 16 == 512 80 * 5 - 32 == 1024 81 * 6 - 64 == 2048 82 * 7 - 128 == 4096 83 * 8 - 256 == 8192 84 */ 85static int bn_limit_bits = 0; 86static int bn_limit_num = 8; /* (1<<bn_limit_bits) */ 87static int bn_limit_bits_low = 0; 88static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */ 89static int bn_limit_bits_high = 0; 90static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */ 91static int bn_limit_bits_mont = 0; 92static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */ 93 94void BN_set_params(int mult, int high, int low, int mont) 95{ 96 if (mult >= 0) { 97 if (mult > (int)(sizeof(int) * 8) - 1) 98 mult = sizeof(int) * 8 - 1; 99 bn_limit_bits = mult; 100 bn_limit_num = 1 << mult; 101 } 102 if (high >= 0) { 103 if (high > (int)(sizeof(int) * 8) - 1) 104 high = sizeof(int) * 8 - 1; 105 bn_limit_bits_high = high; 106 bn_limit_num_high = 1 << high; 107 } 108 if (low >= 0) { 109 if (low > (int)(sizeof(int) * 8) - 1) 110 low = sizeof(int) * 8 - 1; 111 bn_limit_bits_low = low; 112 bn_limit_num_low = 1 << low; 113 } 114 if (mont >= 0) { 115 if (mont > (int)(sizeof(int) * 8) - 1) 116 mont = sizeof(int) * 8 - 1; 117 bn_limit_bits_mont = mont; 118 bn_limit_num_mont = 1 << mont; 119 } 120} 121 122int BN_get_params(int which) 123{ 124 if (which == 0) 125 return (bn_limit_bits); 126 else if (which == 1) 127 return (bn_limit_bits_high); 128 else if (which == 2) 129 return (bn_limit_bits_low); 130 else if (which == 3) 131 return (bn_limit_bits_mont); 132 else 133 return (0); 134} 135#endif 136 137const BIGNUM *BN_value_one(void) 138{ 139 static const BN_ULONG data_one = 1L; 140 static const BIGNUM const_one = 141 { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA }; 142 143 return (&const_one); 144} 145 146int BN_num_bits_word(BN_ULONG l) 147{ 148 BN_ULONG x, mask; 149 int bits = (l != 0); 150 151#if BN_BITS2 > 32 152 x = l >> 32; 153 mask = (0 - x) & BN_MASK2; 154 mask = (0 - (mask >> (BN_BITS2 - 1))); 155 bits += 32 & mask; 156 l ^= (x ^ l) & mask; 157#endif 158 159 x = l >> 16; 160 mask = (0 - x) & BN_MASK2; 161 mask = (0 - (mask >> (BN_BITS2 - 1))); 162 bits += 16 & mask; 163 l ^= (x ^ l) & mask; 164 165 x = l >> 8; 166 mask = (0 - x) & BN_MASK2; 167 mask = (0 - (mask >> (BN_BITS2 - 1))); 168 bits += 8 & mask; 169 l ^= (x ^ l) & mask; 170 171 x = l >> 4; 172 mask = (0 - x) & BN_MASK2; 173 mask = (0 - (mask >> (BN_BITS2 - 1))); 174 bits += 4 & mask; 175 l ^= (x ^ l) & mask; 176 177 x = l >> 2; 178 mask = (0 - x) & BN_MASK2; 179 mask = (0 - (mask >> (BN_BITS2 - 1))); 180 bits += 2 & mask; 181 l ^= (x ^ l) & mask; 182 183 x = l >> 1; 184 mask = (0 - x) & BN_MASK2; 185 mask = (0 - (mask >> (BN_BITS2 - 1))); 186 bits += 1 & mask; 187 188 return bits; 189} 190 191/* 192 * This function still leaks `a->dmax`: it's caller's responsibility to 193 * expand the input `a` in advance to a public length. 194 */ 195static inline 196int bn_num_bits_consttime(const BIGNUM *a) 197{ 198 int j, ret; 199 unsigned int mask, past_i; 200 int i = a->top - 1; 201 bn_check_top(a); 202 203 for (j = 0, past_i = 0, ret = 0; j < a->dmax; j++) { 204 mask = constant_time_eq_int(i, j); /* 0xff..ff if i==j, 0x0 otherwise */ 205 206 ret += BN_BITS2 & (~mask & ~past_i); 207 ret += BN_num_bits_word(a->d[j]) & mask; 208 209 past_i |= mask; /* past_i will become 0xff..ff after i==j */ 210 } 211 212 /* 213 * if BN_is_zero(a) => i is -1 and ret contains garbage, so we mask the 214 * final result. 215 */ 216 mask = ~(constant_time_eq_int(i, ((int)-1))); 217 218 return ret & mask; 219} 220 221int BN_num_bits(const BIGNUM *a) 222{ 223 int i = a->top - 1; 224 bn_check_top(a); 225 226 if (a->flags & BN_FLG_CONSTTIME) { 227 /* 228 * We assume that BIGNUMs flagged as CONSTTIME have also been expanded 229 * so that a->dmax is not leaking secret information. 230 * 231 * In other words, it's the caller's responsibility to ensure `a` has 232 * been preallocated in advance to a public length if we hit this 233 * branch. 234 * 235 */ 236 return bn_num_bits_consttime(a); 237 } 238 239 if (BN_is_zero(a)) 240 return 0; 241 242 return ((i * BN_BITS2) + BN_num_bits_word(a->d[i])); 243} 244 245void BN_clear_free(BIGNUM *a) 246{ 247 int i; 248 249 if (a == NULL) 250 return; 251 bn_check_top(a); 252 if (a->d != NULL) { 253 OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0])); 254 if (!(BN_get_flags(a, BN_FLG_STATIC_DATA))) 255 OPENSSL_free(a->d); 256 } 257 i = BN_get_flags(a, BN_FLG_MALLOCED); 258 OPENSSL_cleanse(a, sizeof(BIGNUM)); 259 if (i) 260 OPENSSL_free(a); 261} 262 263void BN_free(BIGNUM *a) 264{ 265 if (a == NULL) 266 return; 267 bn_check_top(a); 268 if ((a->d != NULL) && !(BN_get_flags(a, BN_FLG_STATIC_DATA))) 269 OPENSSL_free(a->d); 270 if (a->flags & BN_FLG_MALLOCED) 271 OPENSSL_free(a); 272 else { 273#ifndef OPENSSL_NO_DEPRECATED 274 a->flags |= BN_FLG_FREE; 275#endif 276 a->d = NULL; 277 } 278} 279 280void BN_init(BIGNUM *a) 281{ 282 memset(a, 0, sizeof(BIGNUM)); 283 bn_check_top(a); 284} 285 286BIGNUM *BN_new(void) 287{ 288 BIGNUM *ret; 289 290 if ((ret = (BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL) { 291 BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE); 292 return (NULL); 293 } 294 ret->flags = BN_FLG_MALLOCED; 295 ret->top = 0; 296 ret->neg = 0; 297 ret->dmax = 0; 298 ret->d = NULL; 299 bn_check_top(ret); 300 return (ret); 301} 302 303/* This is used both by bn_expand2() and bn_dup_expand() */ 304/* The caller MUST check that words > b->dmax before calling this */ 305static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) 306{ 307 BN_ULONG *A, *a = NULL; 308 const BN_ULONG *B; 309 int i; 310 311 if (words > (INT_MAX / (4 * BN_BITS2))) { 312 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG); 313 return NULL; 314 } 315 if (BN_get_flags(b, BN_FLG_STATIC_DATA)) { 316 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 317 return (NULL); 318 } 319 a = A = (BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG) * words); 320 if (A == NULL) { 321 BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE); 322 return (NULL); 323 } 324#ifdef PURIFY 325 /* 326 * Valgrind complains in BN_consttime_swap because we process the whole 327 * array even if it's not initialised yet. This doesn't matter in that 328 * function - what's important is constant time operation (we're not 329 * actually going to use the data) 330 */ 331 memset(a, 0, sizeof(BN_ULONG) * words); 332#endif 333 334#if 1 335 B = b->d; 336 /* Check if the previous number needs to be copied */ 337 if (B != NULL) { 338 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { 339 /* 340 * The fact that the loop is unrolled 341 * 4-wise is a tribute to Intel. It's 342 * the one that doesn't have enough 343 * registers to accomodate more data. 344 * I'd unroll it 8-wise otherwise:-) 345 * 346 * <appro@fy.chalmers.se> 347 */ 348 BN_ULONG a0, a1, a2, a3; 349 a0 = B[0]; 350 a1 = B[1]; 351 a2 = B[2]; 352 a3 = B[3]; 353 A[0] = a0; 354 A[1] = a1; 355 A[2] = a2; 356 A[3] = a3; 357 } 358 /* 359 * workaround for ultrix cc: without 'case 0', the optimizer does 360 * the switch table by doing a=top&3; a--; goto jump_table[a]; 361 * which fails for top== 0 362 */ 363 switch (b->top & 3) { 364 case 3: 365 A[2] = B[2]; 366 case 2: 367 A[1] = B[1]; 368 case 1: 369 A[0] = B[0]; 370 case 0: 371 ; 372 } 373 } 374#else 375 memset(A, 0, sizeof(BN_ULONG) * words); 376 memcpy(A, b->d, sizeof(b->d[0]) * b->top); 377#endif 378 379 return (a); 380} 381 382/* 383 * This is an internal function that can be used instead of bn_expand2() when 384 * there is a need to copy BIGNUMs instead of only expanding the data part, 385 * while still expanding them. Especially useful when needing to expand 386 * BIGNUMs that are declared 'const' and should therefore not be changed. The 387 * reason to use this instead of a BN_dup() followed by a bn_expand2() is 388 * memory allocation overhead. A BN_dup() followed by a bn_expand2() will 389 * allocate new memory for the BIGNUM data twice, and free it once, while 390 * bn_dup_expand() makes sure allocation is made only once. 391 */ 392 393#ifndef OPENSSL_NO_DEPRECATED 394BIGNUM *bn_dup_expand(const BIGNUM *b, int words) 395{ 396 BIGNUM *r = NULL; 397 398 bn_check_top(b); 399 400 /* 401 * This function does not work if words <= b->dmax && top < words because 402 * BN_dup() does not preserve 'dmax'! (But bn_dup_expand() is not used 403 * anywhere yet.) 404 */ 405 406 if (words > b->dmax) { 407 BN_ULONG *a = bn_expand_internal(b, words); 408 409 if (a) { 410 r = BN_new(); 411 if (r) { 412 r->top = b->top; 413 r->dmax = words; 414 r->neg = b->neg; 415 r->d = a; 416 } else { 417 /* r == NULL, BN_new failure */ 418 OPENSSL_free(a); 419 } 420 } 421 /* 422 * If a == NULL, there was an error in allocation in 423 * bn_expand_internal(), and NULL should be returned 424 */ 425 } else { 426 r = BN_dup(b); 427 } 428 429 bn_check_top(r); 430 return r; 431} 432#endif 433 434/* 435 * This is an internal function that should not be used in applications. It 436 * ensures that 'b' has enough room for a 'words' word number and initialises 437 * any unused part of b->d with leading zeros. It is mostly used by the 438 * various BIGNUM routines. If there is an error, NULL is returned. If not, 439 * 'b' is returned. 440 */ 441 442BIGNUM *bn_expand2(BIGNUM *b, int words) 443{ 444 if (words > b->dmax) { 445 BN_ULONG *a = bn_expand_internal(b, words); 446 if (!a) 447 return NULL; 448 if (b->d) 449 OPENSSL_free(b->d); 450 b->d = a; 451 b->dmax = words; 452 } 453 454/* None of this should be necessary because of what b->top means! */ 455#if 0 456 /* 457 * NB: bn_wexpand() calls this only if the BIGNUM really has to grow 458 */ 459 if (b->top < b->dmax) { 460 int i; 461 BN_ULONG *A = &(b->d[b->top]); 462 for (i = (b->dmax - b->top) >> 3; i > 0; i--, A += 8) { 463 A[0] = 0; 464 A[1] = 0; 465 A[2] = 0; 466 A[3] = 0; 467 A[4] = 0; 468 A[5] = 0; 469 A[6] = 0; 470 A[7] = 0; 471 } 472 for (i = (b->dmax - b->top) & 7; i > 0; i--, A++) 473 A[0] = 0; 474 assert(A == &(b->d[b->dmax])); 475 } 476#endif 477 return b; 478} 479 480BIGNUM *BN_dup(const BIGNUM *a) 481{ 482 BIGNUM *t; 483 484 if (a == NULL) 485 return NULL; 486 bn_check_top(a); 487 488 t = BN_new(); 489 if (t == NULL) 490 return NULL; 491 if (!BN_copy(t, a)) { 492 BN_free(t); 493 return NULL; 494 } 495 bn_check_top(t); 496 return t; 497} 498 499BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) 500{ 501 int i; 502 BN_ULONG *A; 503 const BN_ULONG *B; 504 505 bn_check_top(b); 506 507 if (a == b) 508 return (a); 509 if (bn_wexpand(a, b->top) == NULL) 510 return (NULL); 511 512#if 1 513 A = a->d; 514 B = b->d; 515 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { 516 BN_ULONG a0, a1, a2, a3; 517 a0 = B[0]; 518 a1 = B[1]; 519 a2 = B[2]; 520 a3 = B[3]; 521 A[0] = a0; 522 A[1] = a1; 523 A[2] = a2; 524 A[3] = a3; 525 } 526 /* ultrix cc workaround, see comments in bn_expand_internal */ 527 switch (b->top & 3) { 528 case 3: 529 A[2] = B[2]; 530 case 2: 531 A[1] = B[1]; 532 case 1: 533 A[0] = B[0]; 534 case 0:; 535 } 536#else 537 memcpy(a->d, b->d, sizeof(b->d[0]) * b->top); 538#endif 539 540 a->neg = b->neg; 541 a->top = b->top; 542 a->flags |= b->flags & BN_FLG_FIXED_TOP; 543 bn_check_top(a); 544 return (a); 545} 546 547#define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \ 548 | BN_FLG_CONSTTIME \ 549 | BN_FLG_FIXED_TOP)) 550#define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED)) 551 552void BN_swap(BIGNUM *a, BIGNUM *b) 553{ 554 int flags_old_a, flags_old_b; 555 BN_ULONG *tmp_d; 556 int tmp_top, tmp_dmax, tmp_neg; 557 558 bn_check_top(a); 559 bn_check_top(b); 560 561 flags_old_a = a->flags; 562 flags_old_b = b->flags; 563 564 tmp_d = a->d; 565 tmp_top = a->top; 566 tmp_dmax = a->dmax; 567 tmp_neg = a->neg; 568 569 a->d = b->d; 570 a->top = b->top; 571 a->dmax = b->dmax; 572 a->neg = b->neg; 573 574 b->d = tmp_d; 575 b->top = tmp_top; 576 b->dmax = tmp_dmax; 577 b->neg = tmp_neg; 578 579 a->flags = FLAGS_STRUCT(flags_old_a) | FLAGS_DATA(flags_old_b); 580 b->flags = FLAGS_STRUCT(flags_old_b) | FLAGS_DATA(flags_old_a); 581 bn_check_top(a); 582 bn_check_top(b); 583} 584 585void BN_clear(BIGNUM *a) 586{ 587 bn_check_top(a); 588 if (a->d != NULL) 589 OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0])); 590 a->top = 0; 591 a->neg = 0; 592 a->flags &= ~BN_FLG_FIXED_TOP; 593} 594 595BN_ULONG BN_get_word(const BIGNUM *a) 596{ 597 if (a->top > 1) 598 return BN_MASK2; 599 else if (a->top == 1) 600 return a->d[0]; 601 /* a->top == 0 */ 602 return 0; 603} 604 605int BN_set_word(BIGNUM *a, BN_ULONG w) 606{ 607 bn_check_top(a); 608 if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL) 609 return (0); 610 a->neg = 0; 611 a->d[0] = w; 612 a->top = (w ? 1 : 0); 613 a->flags &= ~BN_FLG_FIXED_TOP; 614 bn_check_top(a); 615 return (1); 616} 617 618BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) 619{ 620 unsigned int i, m; 621 unsigned int n; 622 BN_ULONG l; 623 BIGNUM *bn = NULL; 624 625 if (ret == NULL) 626 ret = bn = BN_new(); 627 if (ret == NULL) 628 return (NULL); 629 bn_check_top(ret); 630 l = 0; 631 n = len; 632 if (n == 0) { 633 ret->top = 0; 634 return (ret); 635 } 636 i = ((n - 1) / BN_BYTES) + 1; 637 m = ((n - 1) % (BN_BYTES)); 638 if (bn_wexpand(ret, (int)i) == NULL) { 639 if (bn) 640 BN_free(bn); 641 return NULL; 642 } 643 ret->top = i; 644 ret->neg = 0; 645 while (n--) { 646 l = (l << 8L) | *(s++); 647 if (m-- == 0) { 648 ret->d[--i] = l; 649 l = 0; 650 m = BN_BYTES - 1; 651 } 652 } 653 /* 654 * need to call this due to clear byte at top if avoiding having the top 655 * bit set (-ve number) 656 */ 657 bn_correct_top(ret); 658 return (ret); 659} 660 661typedef enum {big, little} endianess_t; 662 663/* ignore negative */ 664static 665int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen, endianess_t endianess) 666{ 667 int n; 668 size_t i, lasti, j, atop, mask; 669 BN_ULONG l; 670 671 /* 672 * In case |a| is fixed-top, BN_num_bytes can return bogus length, 673 * but it's assumed that fixed-top inputs ought to be "nominated" 674 * even for padded output, so it works out... 675 */ 676 n = BN_num_bytes(a); 677 if (tolen == -1) { 678 tolen = n; 679 } else if (tolen < n) { /* uncommon/unlike case */ 680 BIGNUM temp = *a; 681 682 bn_correct_top(&temp); 683 n = BN_num_bytes(&temp); 684 if (tolen < n) 685 return -1; 686 } 687 688 /* Swipe through whole available data and don't give away padded zero. */ 689 atop = a->dmax * BN_BYTES; 690 if (atop == 0) { 691 OPENSSL_cleanse(to, tolen); 692 return tolen; 693 } 694 695 lasti = atop - 1; 696 atop = a->top * BN_BYTES; 697 if (endianess == big) 698 to += tolen; /* start from the end of the buffer */ 699 for (i = 0, j = 0; j < (size_t)tolen; j++) { 700 unsigned char val; 701 l = a->d[i / BN_BYTES]; 702 mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1)); 703 val = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask); 704 if (endianess == big) 705 *--to = val; 706 else 707 *to++ = val; 708 i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */ 709 } 710 711 return tolen; 712} 713 714int bn_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) 715{ 716 if (tolen < 0) 717 return -1; 718 return bn2binpad(a, to, tolen, big); 719} 720 721int BN_bn2bin(const BIGNUM *a, unsigned char *to) 722{ 723 return bn2binpad(a, to, -1, big); 724} 725 726BIGNUM *bn_lebin2bn(const unsigned char *s, int len, BIGNUM *ret) 727{ 728 unsigned int i, m; 729 unsigned int n; 730 BN_ULONG l; 731 BIGNUM *bn = NULL; 732 733 if (ret == NULL) 734 ret = bn = BN_new(); 735 if (ret == NULL) 736 return NULL; 737 bn_check_top(ret); 738 s += len; 739 /* Skip trailing zeroes. */ 740 for ( ; len > 0 && s[-1] == 0; s--, len--) 741 continue; 742 n = len; 743 if (n == 0) { 744 ret->top = 0; 745 return ret; 746 } 747 i = ((n - 1) / BN_BYTES) + 1; 748 m = ((n - 1) % (BN_BYTES)); 749 if (bn_wexpand(ret, (int)i) == NULL) { 750 BN_free(bn); 751 return NULL; 752 } 753 ret->top = i; 754 ret->neg = 0; 755 l = 0; 756 while (n--) { 757 s--; 758 l = (l << 8L) | *s; 759 if (m-- == 0) { 760 ret->d[--i] = l; 761 l = 0; 762 m = BN_BYTES - 1; 763 } 764 } 765 /* 766 * need to call this due to clear byte at top if avoiding having the top 767 * bit set (-ve number) 768 */ 769 bn_correct_top(ret); 770 return ret; 771} 772 773int bn_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen) 774{ 775 if (tolen < 0) 776 return -1; 777 return bn2binpad(a, to, tolen, little); 778} 779 780int BN_ucmp(const BIGNUM *a, const BIGNUM *b) 781{ 782 int i; 783 BN_ULONG t1, t2, *ap, *bp; 784 785 bn_check_top(a); 786 bn_check_top(b); 787 788 i = a->top - b->top; 789 if (i != 0) 790 return (i); 791 ap = a->d; 792 bp = b->d; 793 for (i = a->top - 1; i >= 0; i--) { 794 t1 = ap[i]; 795 t2 = bp[i]; 796 if (t1 != t2) 797 return ((t1 > t2) ? 1 : -1); 798 } 799 return (0); 800} 801 802int BN_cmp(const BIGNUM *a, const BIGNUM *b) 803{ 804 int i; 805 int gt, lt; 806 BN_ULONG t1, t2; 807 808 if ((a == NULL) || (b == NULL)) { 809 if (a != NULL) 810 return (-1); 811 else if (b != NULL) 812 return (1); 813 else 814 return (0); 815 } 816 817 bn_check_top(a); 818 bn_check_top(b); 819 820 if (a->neg != b->neg) { 821 if (a->neg) 822 return (-1); 823 else 824 return (1); 825 } 826 if (a->neg == 0) { 827 gt = 1; 828 lt = -1; 829 } else { 830 gt = -1; 831 lt = 1; 832 } 833 834 if (a->top > b->top) 835 return (gt); 836 if (a->top < b->top) 837 return (lt); 838 for (i = a->top - 1; i >= 0; i--) { 839 t1 = a->d[i]; 840 t2 = b->d[i]; 841 if (t1 > t2) 842 return (gt); 843 if (t1 < t2) 844 return (lt); 845 } 846 return (0); 847} 848 849int BN_set_bit(BIGNUM *a, int n) 850{ 851 int i, j, k; 852 853 if (n < 0) 854 return 0; 855 856 i = n / BN_BITS2; 857 j = n % BN_BITS2; 858 if (a->top <= i) { 859 if (bn_wexpand(a, i + 1) == NULL) 860 return (0); 861 for (k = a->top; k < i + 1; k++) 862 a->d[k] = 0; 863 a->top = i + 1; 864 a->flags &= ~BN_FLG_FIXED_TOP; 865 } 866 867 a->d[i] |= (((BN_ULONG)1) << j); 868 bn_check_top(a); 869 return (1); 870} 871 872int BN_clear_bit(BIGNUM *a, int n) 873{ 874 int i, j; 875 876 bn_check_top(a); 877 if (n < 0) 878 return 0; 879 880 i = n / BN_BITS2; 881 j = n % BN_BITS2; 882 if (a->top <= i) 883 return (0); 884 885 a->d[i] &= (~(((BN_ULONG)1) << j)); 886 bn_correct_top(a); 887 return (1); 888} 889 890int BN_is_bit_set(const BIGNUM *a, int n) 891{ 892 int i, j; 893 894 bn_check_top(a); 895 if (n < 0) 896 return 0; 897 i = n / BN_BITS2; 898 j = n % BN_BITS2; 899 if (a->top <= i) 900 return 0; 901 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); 902} 903 904int BN_mask_bits(BIGNUM *a, int n) 905{ 906 int b, w; 907 908 bn_check_top(a); 909 if (n < 0) 910 return 0; 911 912 w = n / BN_BITS2; 913 b = n % BN_BITS2; 914 if (w >= a->top) 915 return 0; 916 if (b == 0) 917 a->top = w; 918 else { 919 a->top = w + 1; 920 a->d[w] &= ~(BN_MASK2 << b); 921 } 922 bn_correct_top(a); 923 return (1); 924} 925 926void BN_set_negative(BIGNUM *a, int b) 927{ 928 if (b && !BN_is_zero(a)) 929 a->neg = 1; 930 else 931 a->neg = 0; 932} 933 934int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) 935{ 936 int i; 937 BN_ULONG aa, bb; 938 939 if (n == 0) 940 return 0; 941 942 aa = a[n - 1]; 943 bb = b[n - 1]; 944 if (aa != bb) 945 return ((aa > bb) ? 1 : -1); 946 for (i = n - 2; i >= 0; i--) { 947 aa = a[i]; 948 bb = b[i]; 949 if (aa != bb) 950 return ((aa > bb) ? 1 : -1); 951 } 952 return (0); 953} 954 955/* 956 * Here follows a specialised variants of bn_cmp_words(). It has the 957 * property of performing the operation on arrays of different sizes. The 958 * sizes of those arrays is expressed through cl, which is the common length 959 * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the 960 * two lengths, calculated as len(a)-len(b). All lengths are the number of 961 * BN_ULONGs... 962 */ 963 964int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) 965{ 966 int n, i; 967 n = cl - 1; 968 969 if (dl < 0) { 970 for (i = dl; i < 0; i++) { 971 if (b[n - i] != 0) 972 return -1; /* a < b */ 973 } 974 } 975 if (dl > 0) { 976 for (i = dl; i > 0; i--) { 977 if (a[n + i] != 0) 978 return 1; /* a > b */ 979 } 980 } 981 return bn_cmp_words(a, b, cl); 982} 983 984/* 985 * Constant-time conditional swap of a and b. 986 * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set. 987 * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b, 988 * and that no more than nwords are used by either a or b. 989 * a and b cannot be the same number 990 */ 991void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) 992{ 993 BN_ULONG t; 994 int i; 995 996 bn_wcheck_size(a, nwords); 997 bn_wcheck_size(b, nwords); 998 999 assert(a != b); 1000 assert((condition & (condition - 1)) == 0); 1001 assert(sizeof(BN_ULONG) >= sizeof(int)); 1002 1003 condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1; 1004 1005 t = (a->top ^ b->top) & condition; 1006 a->top ^= t; 1007 b->top ^= t; 1008 1009 t = (a->neg ^ b->neg) & condition; 1010 a->neg ^= t; 1011 b->neg ^= t; 1012 1013 /*- 1014 * BN_FLG_STATIC_DATA: indicates that data may not be written to. Intention 1015 * is actually to treat it as it's read-only data, and some (if not most) 1016 * of it does reside in read-only segment. In other words observation of 1017 * BN_FLG_STATIC_DATA in BN_consttime_swap should be treated as fatal 1018 * condition. It would either cause SEGV or effectively cause data 1019 * corruption. 1020 * 1021 * BN_FLG_MALLOCED: refers to BN structure itself, and hence must be 1022 * preserved. 1023 * 1024 * BN_FLG_SECURE: must be preserved, because it determines how x->d was 1025 * allocated and hence how to free it. 1026 * 1027 * BN_FLG_CONSTTIME: sufficient to mask and swap 1028 * 1029 * BN_FLG_FIXED_TOP: indicates that we haven't called bn_correct_top() on 1030 * the data, so the d array may be padded with additional 0 values (i.e. 1031 * top could be greater than the minimal value that it could be). We should 1032 * be swapping it 1033 */ 1034 1035#define BN_CONSTTIME_SWAP_FLAGS (BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP) 1036 1037 t = ((a->flags ^ b->flags) & BN_CONSTTIME_SWAP_FLAGS) & condition; 1038 a->flags ^= t; 1039 b->flags ^= t; 1040 1041#define BN_CONSTTIME_SWAP(ind) \ 1042 do { \ 1043 t = (a->d[ind] ^ b->d[ind]) & condition; \ 1044 a->d[ind] ^= t; \ 1045 b->d[ind] ^= t; \ 1046 } while (0) 1047 1048 switch (nwords) { 1049 default: 1050 for (i = 10; i < nwords; i++) 1051 BN_CONSTTIME_SWAP(i); 1052 /* Fallthrough */ 1053 case 10: 1054 BN_CONSTTIME_SWAP(9); /* Fallthrough */ 1055 case 9: 1056 BN_CONSTTIME_SWAP(8); /* Fallthrough */ 1057 case 8: 1058 BN_CONSTTIME_SWAP(7); /* Fallthrough */ 1059 case 7: 1060 BN_CONSTTIME_SWAP(6); /* Fallthrough */ 1061 case 6: 1062 BN_CONSTTIME_SWAP(5); /* Fallthrough */ 1063 case 5: 1064 BN_CONSTTIME_SWAP(4); /* Fallthrough */ 1065 case 4: 1066 BN_CONSTTIME_SWAP(3); /* Fallthrough */ 1067 case 3: 1068 BN_CONSTTIME_SWAP(2); /* Fallthrough */ 1069 case 2: 1070 BN_CONSTTIME_SWAP(1); /* Fallthrough */ 1071 case 1: 1072 BN_CONSTTIME_SWAP(0); 1073 } 1074#undef BN_CONSTTIME_SWAP 1075} 1076