bn_lib.c revision 306196
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 70const char BN_version[] = "Big Number" OPENSSL_VERSION_PTEXT; 71 72/* This stuff appears to be completely unused, so is deprecated */ 73#ifndef OPENSSL_NO_DEPRECATED 74/*- 75 * For a 32 bit machine 76 * 2 - 4 == 128 77 * 3 - 8 == 256 78 * 4 - 16 == 512 79 * 5 - 32 == 1024 80 * 6 - 64 == 2048 81 * 7 - 128 == 4096 82 * 8 - 256 == 8192 83 */ 84static int bn_limit_bits = 0; 85static int bn_limit_num = 8; /* (1<<bn_limit_bits) */ 86static int bn_limit_bits_low = 0; 87static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */ 88static int bn_limit_bits_high = 0; 89static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */ 90static int bn_limit_bits_mont = 0; 91static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */ 92 93void BN_set_params(int mult, int high, int low, int mont) 94{ 95 if (mult >= 0) { 96 if (mult > (int)(sizeof(int) * 8) - 1) 97 mult = sizeof(int) * 8 - 1; 98 bn_limit_bits = mult; 99 bn_limit_num = 1 << mult; 100 } 101 if (high >= 0) { 102 if (high > (int)(sizeof(int) * 8) - 1) 103 high = sizeof(int) * 8 - 1; 104 bn_limit_bits_high = high; 105 bn_limit_num_high = 1 << high; 106 } 107 if (low >= 0) { 108 if (low > (int)(sizeof(int) * 8) - 1) 109 low = sizeof(int) * 8 - 1; 110 bn_limit_bits_low = low; 111 bn_limit_num_low = 1 << low; 112 } 113 if (mont >= 0) { 114 if (mont > (int)(sizeof(int) * 8) - 1) 115 mont = sizeof(int) * 8 - 1; 116 bn_limit_bits_mont = mont; 117 bn_limit_num_mont = 1 << mont; 118 } 119} 120 121int BN_get_params(int which) 122{ 123 if (which == 0) 124 return (bn_limit_bits); 125 else if (which == 1) 126 return (bn_limit_bits_high); 127 else if (which == 2) 128 return (bn_limit_bits_low); 129 else if (which == 3) 130 return (bn_limit_bits_mont); 131 else 132 return (0); 133} 134#endif 135 136const BIGNUM *BN_value_one(void) 137{ 138 static const BN_ULONG data_one = 1L; 139 static const BIGNUM const_one = 140 { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA }; 141 142 return (&const_one); 143} 144 145int BN_num_bits_word(BN_ULONG l) 146{ 147 static const unsigned char bits[256] = { 148 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 149 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 150 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 151 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 152 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 153 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 154 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 155 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 156 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 157 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 158 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 159 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 160 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 161 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 162 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 163 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 164 }; 165 166#if defined(SIXTY_FOUR_BIT_LONG) 167 if (l & 0xffffffff00000000L) { 168 if (l & 0xffff000000000000L) { 169 if (l & 0xff00000000000000L) { 170 return (bits[(int)(l >> 56)] + 56); 171 } else 172 return (bits[(int)(l >> 48)] + 48); 173 } else { 174 if (l & 0x0000ff0000000000L) { 175 return (bits[(int)(l >> 40)] + 40); 176 } else 177 return (bits[(int)(l >> 32)] + 32); 178 } 179 } else 180#else 181# ifdef SIXTY_FOUR_BIT 182 if (l & 0xffffffff00000000LL) { 183 if (l & 0xffff000000000000LL) { 184 if (l & 0xff00000000000000LL) { 185 return (bits[(int)(l >> 56)] + 56); 186 } else 187 return (bits[(int)(l >> 48)] + 48); 188 } else { 189 if (l & 0x0000ff0000000000LL) { 190 return (bits[(int)(l >> 40)] + 40); 191 } else 192 return (bits[(int)(l >> 32)] + 32); 193 } 194 } else 195# endif 196#endif 197 { 198#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) 199 if (l & 0xffff0000L) { 200 if (l & 0xff000000L) 201 return (bits[(int)(l >> 24L)] + 24); 202 else 203 return (bits[(int)(l >> 16L)] + 16); 204 } else 205#endif 206 { 207#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) 208 if (l & 0xff00L) 209 return (bits[(int)(l >> 8)] + 8); 210 else 211#endif 212 return (bits[(int)(l)]); 213 } 214 } 215} 216 217int BN_num_bits(const BIGNUM *a) 218{ 219 int i = a->top - 1; 220 bn_check_top(a); 221 222 if (BN_is_zero(a)) 223 return 0; 224 return ((i * BN_BITS2) + BN_num_bits_word(a->d[i])); 225} 226 227void BN_clear_free(BIGNUM *a) 228{ 229 int i; 230 231 if (a == NULL) 232 return; 233 bn_check_top(a); 234 if (a->d != NULL) { 235 OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0])); 236 if (!(BN_get_flags(a, BN_FLG_STATIC_DATA))) 237 OPENSSL_free(a->d); 238 } 239 i = BN_get_flags(a, BN_FLG_MALLOCED); 240 OPENSSL_cleanse(a, sizeof(BIGNUM)); 241 if (i) 242 OPENSSL_free(a); 243} 244 245void BN_free(BIGNUM *a) 246{ 247 if (a == NULL) 248 return; 249 bn_check_top(a); 250 if ((a->d != NULL) && !(BN_get_flags(a, BN_FLG_STATIC_DATA))) 251 OPENSSL_free(a->d); 252 if (a->flags & BN_FLG_MALLOCED) 253 OPENSSL_free(a); 254 else { 255#ifndef OPENSSL_NO_DEPRECATED 256 a->flags |= BN_FLG_FREE; 257#endif 258 a->d = NULL; 259 } 260} 261 262void BN_init(BIGNUM *a) 263{ 264 memset(a, 0, sizeof(BIGNUM)); 265 bn_check_top(a); 266} 267 268BIGNUM *BN_new(void) 269{ 270 BIGNUM *ret; 271 272 if ((ret = (BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL) { 273 BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE); 274 return (NULL); 275 } 276 ret->flags = BN_FLG_MALLOCED; 277 ret->top = 0; 278 ret->neg = 0; 279 ret->dmax = 0; 280 ret->d = NULL; 281 bn_check_top(ret); 282 return (ret); 283} 284 285/* This is used both by bn_expand2() and bn_dup_expand() */ 286/* The caller MUST check that words > b->dmax before calling this */ 287static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) 288{ 289 BN_ULONG *A, *a = NULL; 290 const BN_ULONG *B; 291 int i; 292 293 bn_check_top(b); 294 295 if (words > (INT_MAX / (4 * BN_BITS2))) { 296 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG); 297 return NULL; 298 } 299 if (BN_get_flags(b, BN_FLG_STATIC_DATA)) { 300 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 301 return (NULL); 302 } 303 a = A = (BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG) * words); 304 if (A == NULL) { 305 BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE); 306 return (NULL); 307 } 308#ifdef PURIFY 309 /* 310 * Valgrind complains in BN_consttime_swap because we process the whole 311 * array even if it's not initialised yet. This doesn't matter in that 312 * function - what's important is constant time operation (we're not 313 * actually going to use the data) 314 */ 315 memset(a, 0, sizeof(BN_ULONG) * words); 316#endif 317 318#if 1 319 B = b->d; 320 /* Check if the previous number needs to be copied */ 321 if (B != NULL) { 322 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { 323 /* 324 * The fact that the loop is unrolled 325 * 4-wise is a tribute to Intel. It's 326 * the one that doesn't have enough 327 * registers to accomodate more data. 328 * I'd unroll it 8-wise otherwise:-) 329 * 330 * <appro@fy.chalmers.se> 331 */ 332 BN_ULONG a0, a1, a2, a3; 333 a0 = B[0]; 334 a1 = B[1]; 335 a2 = B[2]; 336 a3 = B[3]; 337 A[0] = a0; 338 A[1] = a1; 339 A[2] = a2; 340 A[3] = a3; 341 } 342 /* 343 * workaround for ultrix cc: without 'case 0', the optimizer does 344 * the switch table by doing a=top&3; a--; goto jump_table[a]; 345 * which fails for top== 0 346 */ 347 switch (b->top & 3) { 348 case 3: 349 A[2] = B[2]; 350 case 2: 351 A[1] = B[1]; 352 case 1: 353 A[0] = B[0]; 354 case 0: 355 ; 356 } 357 } 358#else 359 memset(A, 0, sizeof(BN_ULONG) * words); 360 memcpy(A, b->d, sizeof(b->d[0]) * b->top); 361#endif 362 363 return (a); 364} 365 366/* 367 * This is an internal function that can be used instead of bn_expand2() when 368 * there is a need to copy BIGNUMs instead of only expanding the data part, 369 * while still expanding them. Especially useful when needing to expand 370 * BIGNUMs that are declared 'const' and should therefore not be changed. The 371 * reason to use this instead of a BN_dup() followed by a bn_expand2() is 372 * memory allocation overhead. A BN_dup() followed by a bn_expand2() will 373 * allocate new memory for the BIGNUM data twice, and free it once, while 374 * bn_dup_expand() makes sure allocation is made only once. 375 */ 376 377#ifndef OPENSSL_NO_DEPRECATED 378BIGNUM *bn_dup_expand(const BIGNUM *b, int words) 379{ 380 BIGNUM *r = NULL; 381 382 bn_check_top(b); 383 384 /* 385 * This function does not work if words <= b->dmax && top < words because 386 * BN_dup() does not preserve 'dmax'! (But bn_dup_expand() is not used 387 * anywhere yet.) 388 */ 389 390 if (words > b->dmax) { 391 BN_ULONG *a = bn_expand_internal(b, words); 392 393 if (a) { 394 r = BN_new(); 395 if (r) { 396 r->top = b->top; 397 r->dmax = words; 398 r->neg = b->neg; 399 r->d = a; 400 } else { 401 /* r == NULL, BN_new failure */ 402 OPENSSL_free(a); 403 } 404 } 405 /* 406 * If a == NULL, there was an error in allocation in 407 * bn_expand_internal(), and NULL should be returned 408 */ 409 } else { 410 r = BN_dup(b); 411 } 412 413 bn_check_top(r); 414 return r; 415} 416#endif 417 418/* 419 * This is an internal function that should not be used in applications. It 420 * ensures that 'b' has enough room for a 'words' word number and initialises 421 * any unused part of b->d with leading zeros. It is mostly used by the 422 * various BIGNUM routines. If there is an error, NULL is returned. If not, 423 * 'b' is returned. 424 */ 425 426BIGNUM *bn_expand2(BIGNUM *b, int words) 427{ 428 bn_check_top(b); 429 430 if (words > b->dmax) { 431 BN_ULONG *a = bn_expand_internal(b, words); 432 if (!a) 433 return NULL; 434 if (b->d) 435 OPENSSL_free(b->d); 436 b->d = a; 437 b->dmax = words; 438 } 439 440/* None of this should be necessary because of what b->top means! */ 441#if 0 442 /* 443 * NB: bn_wexpand() calls this only if the BIGNUM really has to grow 444 */ 445 if (b->top < b->dmax) { 446 int i; 447 BN_ULONG *A = &(b->d[b->top]); 448 for (i = (b->dmax - b->top) >> 3; i > 0; i--, A += 8) { 449 A[0] = 0; 450 A[1] = 0; 451 A[2] = 0; 452 A[3] = 0; 453 A[4] = 0; 454 A[5] = 0; 455 A[6] = 0; 456 A[7] = 0; 457 } 458 for (i = (b->dmax - b->top) & 7; i > 0; i--, A++) 459 A[0] = 0; 460 assert(A == &(b->d[b->dmax])); 461 } 462#endif 463 bn_check_top(b); 464 return b; 465} 466 467BIGNUM *BN_dup(const BIGNUM *a) 468{ 469 BIGNUM *t; 470 471 if (a == NULL) 472 return NULL; 473 bn_check_top(a); 474 475 t = BN_new(); 476 if (t == NULL) 477 return NULL; 478 if (!BN_copy(t, a)) { 479 BN_free(t); 480 return NULL; 481 } 482 bn_check_top(t); 483 return t; 484} 485 486BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) 487{ 488 int i; 489 BN_ULONG *A; 490 const BN_ULONG *B; 491 492 bn_check_top(b); 493 494 if (a == b) 495 return (a); 496 if (bn_wexpand(a, b->top) == NULL) 497 return (NULL); 498 499#if 1 500 A = a->d; 501 B = b->d; 502 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { 503 BN_ULONG a0, a1, a2, a3; 504 a0 = B[0]; 505 a1 = B[1]; 506 a2 = B[2]; 507 a3 = B[3]; 508 A[0] = a0; 509 A[1] = a1; 510 A[2] = a2; 511 A[3] = a3; 512 } 513 /* ultrix cc workaround, see comments in bn_expand_internal */ 514 switch (b->top & 3) { 515 case 3: 516 A[2] = B[2]; 517 case 2: 518 A[1] = B[1]; 519 case 1: 520 A[0] = B[0]; 521 case 0:; 522 } 523#else 524 memcpy(a->d, b->d, sizeof(b->d[0]) * b->top); 525#endif 526 527 a->top = b->top; 528 a->neg = b->neg; 529 bn_check_top(a); 530 return (a); 531} 532 533void BN_swap(BIGNUM *a, BIGNUM *b) 534{ 535 int flags_old_a, flags_old_b; 536 BN_ULONG *tmp_d; 537 int tmp_top, tmp_dmax, tmp_neg; 538 539 bn_check_top(a); 540 bn_check_top(b); 541 542 flags_old_a = a->flags; 543 flags_old_b = b->flags; 544 545 tmp_d = a->d; 546 tmp_top = a->top; 547 tmp_dmax = a->dmax; 548 tmp_neg = a->neg; 549 550 a->d = b->d; 551 a->top = b->top; 552 a->dmax = b->dmax; 553 a->neg = b->neg; 554 555 b->d = tmp_d; 556 b->top = tmp_top; 557 b->dmax = tmp_dmax; 558 b->neg = tmp_neg; 559 560 a->flags = 561 (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA); 562 b->flags = 563 (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA); 564 bn_check_top(a); 565 bn_check_top(b); 566} 567 568void BN_clear(BIGNUM *a) 569{ 570 bn_check_top(a); 571 if (a->d != NULL) 572 OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0])); 573 a->top = 0; 574 a->neg = 0; 575} 576 577BN_ULONG BN_get_word(const BIGNUM *a) 578{ 579 if (a->top > 1) 580 return BN_MASK2; 581 else if (a->top == 1) 582 return a->d[0]; 583 /* a->top == 0 */ 584 return 0; 585} 586 587int BN_set_word(BIGNUM *a, BN_ULONG w) 588{ 589 bn_check_top(a); 590 if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL) 591 return (0); 592 a->neg = 0; 593 a->d[0] = w; 594 a->top = (w ? 1 : 0); 595 bn_check_top(a); 596 return (1); 597} 598 599BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) 600{ 601 unsigned int i, m; 602 unsigned int n; 603 BN_ULONG l; 604 BIGNUM *bn = NULL; 605 606 if (ret == NULL) 607 ret = bn = BN_new(); 608 if (ret == NULL) 609 return (NULL); 610 bn_check_top(ret); 611 l = 0; 612 n = len; 613 if (n == 0) { 614 ret->top = 0; 615 return (ret); 616 } 617 i = ((n - 1) / BN_BYTES) + 1; 618 m = ((n - 1) % (BN_BYTES)); 619 if (bn_wexpand(ret, (int)i) == NULL) { 620 if (bn) 621 BN_free(bn); 622 return NULL; 623 } 624 ret->top = i; 625 ret->neg = 0; 626 while (n--) { 627 l = (l << 8L) | *(s++); 628 if (m-- == 0) { 629 ret->d[--i] = l; 630 l = 0; 631 m = BN_BYTES - 1; 632 } 633 } 634 /* 635 * need to call this due to clear byte at top if avoiding having the top 636 * bit set (-ve number) 637 */ 638 bn_correct_top(ret); 639 return (ret); 640} 641 642/* ignore negative */ 643int BN_bn2bin(const BIGNUM *a, unsigned char *to) 644{ 645 int n, i; 646 BN_ULONG l; 647 648 bn_check_top(a); 649 n = i = BN_num_bytes(a); 650 while (i--) { 651 l = a->d[i / BN_BYTES]; 652 *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff; 653 } 654 return (n); 655} 656 657int BN_ucmp(const BIGNUM *a, const BIGNUM *b) 658{ 659 int i; 660 BN_ULONG t1, t2, *ap, *bp; 661 662 bn_check_top(a); 663 bn_check_top(b); 664 665 i = a->top - b->top; 666 if (i != 0) 667 return (i); 668 ap = a->d; 669 bp = b->d; 670 for (i = a->top - 1; i >= 0; i--) { 671 t1 = ap[i]; 672 t2 = bp[i]; 673 if (t1 != t2) 674 return ((t1 > t2) ? 1 : -1); 675 } 676 return (0); 677} 678 679int BN_cmp(const BIGNUM *a, const BIGNUM *b) 680{ 681 int i; 682 int gt, lt; 683 BN_ULONG t1, t2; 684 685 if ((a == NULL) || (b == NULL)) { 686 if (a != NULL) 687 return (-1); 688 else if (b != NULL) 689 return (1); 690 else 691 return (0); 692 } 693 694 bn_check_top(a); 695 bn_check_top(b); 696 697 if (a->neg != b->neg) { 698 if (a->neg) 699 return (-1); 700 else 701 return (1); 702 } 703 if (a->neg == 0) { 704 gt = 1; 705 lt = -1; 706 } else { 707 gt = -1; 708 lt = 1; 709 } 710 711 if (a->top > b->top) 712 return (gt); 713 if (a->top < b->top) 714 return (lt); 715 for (i = a->top - 1; i >= 0; i--) { 716 t1 = a->d[i]; 717 t2 = b->d[i]; 718 if (t1 > t2) 719 return (gt); 720 if (t1 < t2) 721 return (lt); 722 } 723 return (0); 724} 725 726int BN_set_bit(BIGNUM *a, int n) 727{ 728 int i, j, k; 729 730 if (n < 0) 731 return 0; 732 733 i = n / BN_BITS2; 734 j = n % BN_BITS2; 735 if (a->top <= i) { 736 if (bn_wexpand(a, i + 1) == NULL) 737 return (0); 738 for (k = a->top; k < i + 1; k++) 739 a->d[k] = 0; 740 a->top = i + 1; 741 } 742 743 a->d[i] |= (((BN_ULONG)1) << j); 744 bn_check_top(a); 745 return (1); 746} 747 748int BN_clear_bit(BIGNUM *a, int n) 749{ 750 int i, j; 751 752 bn_check_top(a); 753 if (n < 0) 754 return 0; 755 756 i = n / BN_BITS2; 757 j = n % BN_BITS2; 758 if (a->top <= i) 759 return (0); 760 761 a->d[i] &= (~(((BN_ULONG)1) << j)); 762 bn_correct_top(a); 763 return (1); 764} 765 766int BN_is_bit_set(const BIGNUM *a, int n) 767{ 768 int i, j; 769 770 bn_check_top(a); 771 if (n < 0) 772 return 0; 773 i = n / BN_BITS2; 774 j = n % BN_BITS2; 775 if (a->top <= i) 776 return 0; 777 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); 778} 779 780int BN_mask_bits(BIGNUM *a, int n) 781{ 782 int b, w; 783 784 bn_check_top(a); 785 if (n < 0) 786 return 0; 787 788 w = n / BN_BITS2; 789 b = n % BN_BITS2; 790 if (w >= a->top) 791 return 0; 792 if (b == 0) 793 a->top = w; 794 else { 795 a->top = w + 1; 796 a->d[w] &= ~(BN_MASK2 << b); 797 } 798 bn_correct_top(a); 799 return (1); 800} 801 802void BN_set_negative(BIGNUM *a, int b) 803{ 804 if (b && !BN_is_zero(a)) 805 a->neg = 1; 806 else 807 a->neg = 0; 808} 809 810int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) 811{ 812 int i; 813 BN_ULONG aa, bb; 814 815 aa = a[n - 1]; 816 bb = b[n - 1]; 817 if (aa != bb) 818 return ((aa > bb) ? 1 : -1); 819 for (i = n - 2; i >= 0; i--) { 820 aa = a[i]; 821 bb = b[i]; 822 if (aa != bb) 823 return ((aa > bb) ? 1 : -1); 824 } 825 return (0); 826} 827 828/* 829 * Here follows a specialised variants of bn_cmp_words(). It has the 830 * property of performing the operation on arrays of different sizes. The 831 * sizes of those arrays is expressed through cl, which is the common length 832 * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the 833 * two lengths, calculated as len(a)-len(b). All lengths are the number of 834 * BN_ULONGs... 835 */ 836 837int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) 838{ 839 int n, i; 840 n = cl - 1; 841 842 if (dl < 0) { 843 for (i = dl; i < 0; i++) { 844 if (b[n - i] != 0) 845 return -1; /* a < b */ 846 } 847 } 848 if (dl > 0) { 849 for (i = dl; i > 0; i--) { 850 if (a[n + i] != 0) 851 return 1; /* a > b */ 852 } 853 } 854 return bn_cmp_words(a, b, cl); 855} 856 857/* 858 * Constant-time conditional swap of a and b. 859 * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set. 860 * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b, 861 * and that no more than nwords are used by either a or b. 862 * a and b cannot be the same number 863 */ 864void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) 865{ 866 BN_ULONG t; 867 int i; 868 869 bn_wcheck_size(a, nwords); 870 bn_wcheck_size(b, nwords); 871 872 assert(a != b); 873 assert((condition & (condition - 1)) == 0); 874 assert(sizeof(BN_ULONG) >= sizeof(int)); 875 876 condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1; 877 878 t = (a->top ^ b->top) & condition; 879 a->top ^= t; 880 b->top ^= t; 881 882#define BN_CONSTTIME_SWAP(ind) \ 883 do { \ 884 t = (a->d[ind] ^ b->d[ind]) & condition; \ 885 a->d[ind] ^= t; \ 886 b->d[ind] ^= t; \ 887 } while (0) 888 889 switch (nwords) { 890 default: 891 for (i = 10; i < nwords; i++) 892 BN_CONSTTIME_SWAP(i); 893 /* Fallthrough */ 894 case 10: 895 BN_CONSTTIME_SWAP(9); /* Fallthrough */ 896 case 9: 897 BN_CONSTTIME_SWAP(8); /* Fallthrough */ 898 case 8: 899 BN_CONSTTIME_SWAP(7); /* Fallthrough */ 900 case 7: 901 BN_CONSTTIME_SWAP(6); /* Fallthrough */ 902 case 6: 903 BN_CONSTTIME_SWAP(5); /* Fallthrough */ 904 case 5: 905 BN_CONSTTIME_SWAP(4); /* Fallthrough */ 906 case 4: 907 BN_CONSTTIME_SWAP(3); /* Fallthrough */ 908 case 3: 909 BN_CONSTTIME_SWAP(2); /* Fallthrough */ 910 case 2: 911 BN_CONSTTIME_SWAP(1); /* Fallthrough */ 912 case 1: 913 BN_CONSTTIME_SWAP(0); 914 } 915#undef BN_CONSTTIME_SWAP 916} 917