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 <stdio.h> 66#include <stdlib.h> 67#include <string.h> 68#include "bn_lcl.h" 69 70const char *BN_version="Big Number"; 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 90int BN_num_bits_word(BN_ULONG l) 91 { 92 static const char bits[256]={ 93 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4, 94 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 95 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 96 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 97 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 98 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 99 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 100 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 101 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 102 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 103 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 104 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 105 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 106 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 107 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 108 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 109 }; 110 111#if defined(SIXTY_FOUR_BIT_LONG) 112 if (l & 0xffffffff00000000L) 113 { 114 if (l & 0xffff000000000000L) 115 { 116 if (l & 0xff00000000000000L) 117 { 118 return(bits[(int)(l>>56)]+56); 119 } 120 else return(bits[(int)(l>>48)]+48); 121 } 122 else 123 { 124 if (l & 0x0000ff0000000000L) 125 { 126 return(bits[(int)(l>>40)]+40); 127 } 128 else return(bits[(int)(l>>32)]+32); 129 } 130 } 131 else 132#else 133#ifdef SIXTY_FOUR_BIT 134 if (l & 0xffffffff00000000LL) 135 { 136 if (l & 0xffff000000000000LL) 137 { 138 if (l & 0xff00000000000000LL) 139 { 140 return(bits[(int)(l>>56)]+56); 141 } 142 else return(bits[(int)(l>>48)]+48); 143 } 144 else 145 { 146 if (l & 0x0000ff0000000000LL) 147 { 148 return(bits[(int)(l>>40)]+40); 149 } 150 else return(bits[(int)(l>>32)]+32); 151 } 152 } 153 else 154#endif 155#endif 156 { 157#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) 158 if (l & 0xffff0000L) 159 { 160 if (l & 0xff000000L) 161 return(bits[(int)(l>>24L)]+24); 162 else return(bits[(int)(l>>16L)]+16); 163 } 164 else 165#endif 166 { 167#if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) 168 if (l & 0xff00L) 169 return(bits[(int)(l>>8)]+8); 170 else 171#endif 172 return(bits[(int)(l )] ); 173 } 174 } 175 } 176 177int BN_num_bits(const BIGNUM *a) 178 { 179 BN_ULONG l; 180 int i; 181 182 bn_check_top(a); 183 184 if (a->top == 0) return(0); 185 l=a->d[a->top-1]; 186 assert(l != 0); 187 i=(a->top-1)*BN_BITS2; 188 return(i+BN_num_bits_word(l)); 189 } 190 191void BN_clear_free(BIGNUM *a) 192 { 193 int i; 194 195 if (a == NULL) return; 196 if (a->d != NULL) 197 { 198 memset(a->d,0,a->dmax*sizeof(a->d[0])); 199 if (!(BN_get_flags(a,BN_FLG_STATIC_DATA))) 200 free(a->d); 201 } 202 i=BN_get_flags(a,BN_FLG_MALLOCED); 203 memset(a,0,sizeof(BIGNUM)); 204 if (i) 205 free(a); 206 } 207 208void BN_free(BIGNUM *a) 209 { 210 if (a == NULL) return; 211 if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA))) 212 free(a->d); 213 a->flags|=BN_FLG_FREE; /* REMOVE? */ 214 if (a->flags & BN_FLG_MALLOCED) 215 free(a); 216 } 217 218void BN_init(BIGNUM *a) 219 { 220 memset(a,0,sizeof(BIGNUM)); 221 } 222 223BIGNUM *BN_new(void) 224 { 225 BIGNUM *ret; 226 227 if ((ret=(BIGNUM *)malloc(sizeof(BIGNUM))) == NULL) 228 { 229 return(NULL); 230 } 231 ret->flags=BN_FLG_MALLOCED; 232 ret->top=0; 233 ret->neg=0; 234 ret->dmax=0; 235 ret->d=NULL; 236 return(ret); 237 } 238 239/* This is an internal function that should not be used in applications. 240 * It ensures that 'b' has enough room for a 'words' word number number. 241 * It is mostly used by the various BIGNUM routines. If there is an error, 242 * NULL is returned. If not, 'b' is returned. */ 243 244BIGNUM *bn_expand2(BIGNUM *b, int words) 245 { 246 BN_ULONG *A,*a; 247 const BN_ULONG *B; 248 int i; 249 250 bn_check_top(b); 251 252 if (words > b->dmax) 253 { 254 bn_check_top(b); 255 if (BN_get_flags(b,BN_FLG_STATIC_DATA)) 256 { 257 return(NULL); 258 } 259 a=A=(BN_ULONG *)malloc(sizeof(BN_ULONG)*(words+1)); 260 if (A == NULL) 261 { 262 return(NULL); 263 } 264#if 1 265 B=b->d; 266 /* Check if the previous number needs to be copied */ 267 if (B != NULL) 268 { 269#if 0 270 /* This lot is an unrolled loop to copy b->top 271 * BN_ULONGs from B to A 272 */ 273/* 274 * I have nothing against unrolling but it's usually done for 275 * several reasons, namely: 276 * - minimize percentage of decision making code, i.e. branches; 277 * - avoid cache trashing; 278 * - make it possible to schedule loads earlier; 279 * Now let's examine the code below. The cornerstone of C is 280 * "programmer is always right" and that's what we love it for:-) 281 * For this very reason C compilers have to be paranoid when it 282 * comes to data aliasing and assume the worst. Yeah, but what 283 * does it mean in real life? This means that loop body below will 284 * be compiled to sequence of loads immediately followed by stores 285 * as compiler assumes the worst, something in A==B+1 style. As a 286 * result CPU pipeline is going to starve for incoming data. Secondly 287 * if A and B happen to share same cache line such code is going to 288 * cause severe cache trashing. Both factors have severe impact on 289 * performance of modern CPUs and this is the reason why this 290 * particular piece of code is #ifdefed away and replaced by more 291 * "friendly" version found in #else section below. This comment 292 * also applies to BN_copy function. 293 * 294 * <appro@fy.chalmers.se> 295 */ 296 for (i=b->top&(~7); i>0; i-=8) 297 { 298 A[0]=B[0]; A[1]=B[1]; A[2]=B[2]; A[3]=B[3]; 299 A[4]=B[4]; A[5]=B[5]; A[6]=B[6]; A[7]=B[7]; 300 A+=8; 301 B+=8; 302 } 303 switch (b->top&7) 304 { 305 case 7: 306 A[6]=B[6]; 307 case 6: 308 A[5]=B[5]; 309 case 5: 310 A[4]=B[4]; 311 case 4: 312 A[3]=B[3]; 313 case 3: 314 A[2]=B[2]; 315 case 2: 316 A[1]=B[1]; 317 case 1: 318 A[0]=B[0]; 319 case 0: 320 /* I need the 'case 0' entry for utrix cc. 321 * If the optimizer is turned on, it does the 322 * switch table by doing 323 * a=top&7 324 * a--; 325 * goto jump_table[a]; 326 * If top is 0, this makes us jump to 0xffffffc 327 * which is rather bad :-(. 328 * eric 23-Apr-1998 329 */ 330 ; 331 } 332#else 333 for (i=b->top>>2; i>0; i--,A+=4,B+=4) 334 { 335 /* 336 * The fact that the loop is unrolled 337 * 4-wise is a tribute to Intel. It's 338 * the one that doesn't have enough 339 * registers to accomodate more data. 340 * I'd unroll it 8-wise otherwise:-) 341 * 342 * <appro@fy.chalmers.se> 343 */ 344 BN_ULONG a0,a1,a2,a3; 345 a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3]; 346 A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3; 347 } 348 switch (b->top&3) 349 { 350 case 3: A[2]=B[2]; 351 case 2: A[1]=B[1]; 352 case 1: A[0]=B[0]; 353 case 0: ; /* ultrix cc workaround, see above */ 354 } 355#endif 356 free(b->d); 357 } 358 359 b->d=a; 360 b->dmax=words; 361 362 /* Now need to zero any data between b->top and b->max */ 363 364 A= &(b->d[b->top]); 365 for (i=(b->dmax - b->top)>>3; i>0; i--,A+=8) 366 { 367 A[0]=0; A[1]=0; A[2]=0; A[3]=0; 368 A[4]=0; A[5]=0; A[6]=0; A[7]=0; 369 } 370 for (i=(b->dmax - b->top)&7; i>0; i--,A++) 371 A[0]=0; 372#else 373 memset(A,0,sizeof(BN_ULONG)*(words+1)); 374 memcpy(A,b->d,sizeof(b->d[0])*b->top); 375 b->d=a; 376 b->max=words; 377#endif 378 379/* memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG)); */ 380/* { int i; for (i=b->max; i<words+1; i++) p[i]=i;} */ 381 382 } 383 return(b); 384 } 385 386BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) 387 { 388 int i; 389 BN_ULONG *A; 390 const BN_ULONG *B; 391 392 bn_check_top(b); 393 394 if (a == b) return(a); 395 if (bn_wexpand(a,b->top) == NULL) return(NULL); 396 397#if 1 398 A=a->d; 399 B=b->d; 400 for (i=b->top>>2; i>0; i--,A+=4,B+=4) 401 { 402 BN_ULONG a0,a1,a2,a3; 403 a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3]; 404 A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3; 405 } 406 switch (b->top&3) 407 { 408 case 3: A[2]=B[2]; 409 case 2: A[1]=B[1]; 410 case 1: A[0]=B[0]; 411 case 0: ; /* ultrix cc workaround, see comments in bn_expand2 */ 412 } 413#else 414 memcpy(a->d,b->d,sizeof(b->d[0])*b->top); 415#endif 416 417/* memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/ 418 a->top=b->top; 419 if ((a->top == 0) && (a->d != NULL)) 420 a->d[0]=0; 421 a->neg=b->neg; 422 return(a); 423 } 424 425int BN_set_word(BIGNUM *a, BN_ULONG w) 426 { 427 int i,n; 428 if (bn_expand(a,sizeof(BN_ULONG)*8) == NULL) return(0); 429 430 n=sizeof(BN_ULONG)/BN_BYTES; 431 a->neg=0; 432 a->top=0; 433 a->d[0]=(BN_ULONG)w&BN_MASK2; 434 if (a->d[0] != 0) a->top=1; 435 for (i=1; i<n; i++) 436 { 437 /* the following is done instead of 438 * w>>=BN_BITS2 so compilers don't complain 439 * on builds where sizeof(long) == BN_TYPES */ 440#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */ 441 w>>=BN_BITS4; 442 w>>=BN_BITS4; 443#else 444 w=0; 445#endif 446 a->d[i]=(BN_ULONG)w&BN_MASK2; 447 if (a->d[i] != 0) a->top=i+1; 448 } 449 return(1); 450 } 451 452/* ignore negative */ 453BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) 454 { 455 unsigned int i,m; 456 unsigned int n; 457 BN_ULONG l; 458 459 if (ret == NULL) ret=BN_new(); 460 if (ret == NULL) return(NULL); 461 l=0; 462 n=len; 463 if (n == 0) 464 { 465 ret->top=0; 466 return(ret); 467 } 468 if (bn_expand(ret,(int)(n+2)*8) == NULL) 469 return(NULL); 470 i=((n-1)/BN_BYTES)+1; 471 m=((n-1)%(BN_BYTES)); 472 ret->top=i; 473 while (n-- > 0) 474 { 475 l=(l<<8L)| *(s++); 476 if (m-- == 0) 477 { 478 ret->d[--i]=l; 479 l=0; 480 m=BN_BYTES-1; 481 } 482 } 483 /* need to call this due to clear byte at top if avoiding 484 * having the top bit set (-ve number) */ 485 bn_fix_top(ret); 486 return(ret); 487 } 488 489/* ignore negative */ 490int BN_bn2bin(const BIGNUM *a, unsigned char *to) 491 { 492 int n,i; 493 BN_ULONG l; 494 495 n=i=BN_num_bytes(a); 496 while (i-- > 0) 497 { 498 l=a->d[i/BN_BYTES]; 499 *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff; 500 } 501 return(n); 502 } 503 504int BN_ucmp(const BIGNUM *a, const BIGNUM *b) 505 { 506 int i; 507 BN_ULONG t1,t2,*ap,*bp; 508 509 bn_check_top(a); 510 bn_check_top(b); 511 512 i=a->top-b->top; 513 if (i != 0) return(i); 514 ap=a->d; 515 bp=b->d; 516 for (i=a->top-1; i>=0; i--) 517 { 518 t1= ap[i]; 519 t2= bp[i]; 520 if (t1 != t2) 521 return(t1 > t2?1:-1); 522 } 523 return(0); 524 } 525 526int BN_cmp(const BIGNUM *a, const BIGNUM *b) 527 { 528 int i; 529 int gt,lt; 530 BN_ULONG t1,t2; 531 532 if ((a == NULL) || (b == NULL)) 533 { 534 if (a != NULL) 535 return(-1); 536 else if (b != NULL) 537 return(1); 538 else 539 return(0); 540 } 541 542 bn_check_top(a); 543 bn_check_top(b); 544 545 if (a->neg != b->neg) 546 { 547 if (a->neg) 548 return(-1); 549 else return(1); 550 } 551 if (a->neg == 0) 552 { gt=1; lt= -1; } 553 else { gt= -1; lt=1; } 554 555 if (a->top > b->top) return(gt); 556 if (a->top < b->top) return(lt); 557 for (i=a->top-1; i>=0; i--) 558 { 559 t1=a->d[i]; 560 t2=b->d[i]; 561 if (t1 > t2) return(gt); 562 if (t1 < t2) return(lt); 563 } 564 return(0); 565 } 566 567int BN_is_bit_set(const BIGNUM *a, int n) 568 { 569 int i,j; 570 571 if (n < 0) return(0); 572 i=n/BN_BITS2; 573 j=n%BN_BITS2; 574 if (a->top <= i) return(0); 575 return((a->d[i]&(((BN_ULONG)1)<<j))?1:0); 576 } 577