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