![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to mpilib.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [PGP] / pgp / src|
Return to mpilib.h CVS log | Up to [PGP] / pgp / src |
1.1.1.9 ! root 1: /* C include file for MPI multiprecision integer math routines. ! 2: ! 3: Boulder Software Engineering ! 4: 3021 Eleventh Street ! 5: Boulder, CO 80304 ! 6: (303) 541-0140 ! 7: ! 8: (c) Copyright 1986-92 by Philip Zimmermann. All rights reserved. ! 9: The author assumes no liability for damages resulting from the use ! 10: of this software, even if the damage results from defects in this ! 11: software. No warranty is expressed or implied. ! 12: ! 13: These routines implement all of the multiprecision arithmetic necessary ! 14: for Rivest-Shamir-Adleman (RSA) public key cryptography, as well as ! 15: other number-theoretic algorithms such as ElGamal, Diffie-Hellman, ! 16: or Rabin. ! 17: ! 18: Although originally developed in Microsoft C for the IBM PC, this code ! 19: contains few machine dependencies. It assumes 2's complement ! 20: arithmetic. It can be adapted to 8-bit, 16-bit, or 32-bit machines, ! 21: lowbyte-highbyte order or highbyte-lowbyte order. This version ! 22: has been converted to ANSI C. ! 23: ! 24: Modified 8 Apr 92 - HAJK - Implement new VAX/VMS primitive support. ! 25: Modified 29 Nov 92 - Thad Smith ! 26: */ ! 27: ! 28: #include <string.h> ! 29: #include "usuals.h" /* typedefs for byte, word16, boolean, etc. */ ! 30: #include "platform.h" /* customization for different environments */ ! 31: ! 32: /* Platform customization: ! 33: * A version which runs on almost any computer can be implemented by ! 34: * defining PORTABLE and MPORTABLE, preferably as a command line ! 35: * parameter. Faster versions can be generated by specifying specific ! 36: * parameters, such as size of unit and MULTUNIT, and by supplying some ! 37: * of the critical in assembly. See the file platform.h for more ! 38: * details on customization. ! 39: * ! 40: * The symbol HIGHFIRST, designating that integers and longs are stored ! 41: * with the most significant bit in the lowest address, should be defined ! 42: * on the command line for compiling all files, since it is used by files ! 43: * other than the mpilib routines. ! 44: */ ! 45: ! 46: #ifndef ALIGN ! 47: #define ALIGN ! 48: #endif ! 49: ! 50: #ifndef PEASANT /* if not Russian peasant modulo multiply algorithm */ ! 51: #ifndef MERRITT /* if not Merritt's modmult */ ! 52: #ifndef UPTON /* if not Upton's modmult */ ! 53: #ifndef SMITH ! 54: #define SMITH /* default: use Smith's modmult algorithm */ ! 55: #endif ! 56: #endif ! 57: #endif ! 58: #endif ! 59: ! 60: #ifdef SMITH ! 61: #define UPTON_OR_SMITH /* enable common code */ ! 62: #endif ! 63: #ifdef UPTON ! 64: #define UPTON_OR_SMITH /* enable common code */ ! 65: #endif ! 66: ! 67: #ifndef UNIT32 ! 68: #ifndef UNIT8 ! 69: #define UNIT16 /* default--use 16-bit units */ ! 70: #endif ! 71: #endif ! 72: ! 73: /*** CAUTION: If your machine has an unusual word size that is not a ! 74: power of 2 (8, 16, 32, or 64) bits wide, then the macros here that ! 75: use the symbol "LOG_UNITSIZE" must be changed. ! 76: ***/ ! 77: ! 78: #ifdef UNIT8 ! 79: typedef unsigned char unit; ! 80: typedef signed char signedunit; ! 81: #define UNITSIZE 8 /* number of bits in a unit */ ! 82: #define LOG_UNITSIZE 3 ! 83: #define uppermostbit ((unit) 0x80) ! 84: #define BYTES_PER_UNIT 1 /* number of bytes in a unit */ ! 85: #define units2bits(n) ((n) << 3) /* fast multiply by UNITSIZE */ ! 86: #define units2bytes(n) (n) ! 87: #define bits2units(n) (((n)+7) >> 3) ! 88: #define bytes2units(n) (n) ! 89: #endif ! 90: ! 91: #ifdef UNIT16 ! 92: typedef word16 unit; ! 93: typedef short signedunit; ! 94: #define UNITSIZE 16 /* number of bits in a unit */ ! 95: #define LOG_UNITSIZE 4 ! 96: #define uppermostbit ((unit) 0x8000) ! 97: #define BYTES_PER_UNIT 2 /* number of bytes in a unit */ ! 98: #define units2bits(n) ((n) << 4) /* fast multiply by UNITSIZE */ ! 99: #define units2bytes(n) ((n) << 1) ! 100: #define bits2units(n) (((n)+15) >> 4) ! 101: #define bytes2units(n) (((n)+1) >> 1) ! 102: #endif ! 103: ! 104: #ifdef UNIT32 ! 105: typedef word32 unit; ! 106: typedef long signedunit; ! 107: #define UNITSIZE 32 /* number of bits in a unit */ ! 108: #define LOG_UNITSIZE 5 ! 109: #define uppermostbit ((unit) 0x80000000L) ! 110: #define BYTES_PER_UNIT 4 /* number of bytes in a unit */ ! 111: #define units2bits(n) ((n) << 5) /* fast multiply by UNITSIZE */ ! 112: #define units2bytes(n) ((n) << 2) ! 113: #define bits2units(n) (((n)+31) >> 5) ! 114: #define bytes2units(n) (((n)+3) >> 2) ! 115: #endif ! 116: ! 117: #define power_of_2(b) ((unit) 1 << (b)) /* computes power-of-2 bit masks */ ! 118: #define bits2bytes(n) (((n)+7) >> 3) ! 119: /* Some C compilers (like the ADSP2101) will not always collapse constant ! 120: expressions at compile time if the expressions contain shift ! 121: operators. */ ! 122: /* #define uppermostbit power_of_2(UNITSIZE-1) */ ! 123: /* #define UNITSIZE units2bits(1) */ /* number of bits in a unit */ ! 124: /* #define bytes2units(n) bits2units((n)<<3) */ ! 125: /* #define BYTES_PER_UNIT (UNITSIZE >> 3) */ ! 126: /* LOG_UNITSIZE is the log base 2 of UNITSIZE, ie: 4 for 16-bit units */ ! 127: /* #define units2bits(n) ((n) << LOG_UNITSIZE) */ /* fast multiply by ! 128: UNITSIZE */ ! 129: /* #define units2bytes(n) ((n) << (LOG_UNITSIZE-3)) */ ! 130: /* #define bits2units(n) (((n)+(UNITSIZE-1)) >> LOG_UNITSIZE) */ ! 131: /* #define bytes2units(n) (((n)+(BYTES_PER_UNIT-1)) >> (LOG_UNITSIZE-3)) */ ! 132: ! 133: typedef unit *unitptr; ! 134: ! 135: ! 136: /*--------------------- Byte ordering stuff -------------------*/ ! 137: #ifdef HIGHFIRST ! 138: ! 139: /* these definitions assume MSB comes first */ ! 140: #define tohigher(n) (-(n)) /* offset towards higher unit */ ! 141: #define pre_higherunit(r) (--(r)) ! 142: #define pre_lowerunit(r) (++(r)) ! 143: #define post_higherunit(r) ((r)--) ! 144: #define post_lowerunit(r) ((r)++) ! 145: #define bit_index(n) (global_precision-bits2units((n)+1)) ! 146: #define lsbptr(r,prec) ((r)+(prec)-1) ! 147: #define make_lsbptr(r,prec) (r) = lsbptr(r,prec) ! 148: #define unmake_lsbptr(r,prec) (r) = ((r)-(prec)+1) ! 149: #define msbptr(r,prec) (r) ! 150: #define make_msbptr(r,prec) /* (r) = msbptr(r,prec) */ ! 151: ! 152: /* The macro rescale(r,current_precision,new_precision) rescales ! 153: a multiprecision integer by adjusting r and its precision to new values. ! 154: It can be used to reverse the effects of the normalize ! 155: routine given above. See the comments in normalize concerning ! 156: Intel vs. Motorola LSB/MSB conventions. ! 157: WARNING: You can only safely call rescale on registers that ! 158: you have previously normalized with the above normalize routine, ! 159: or are known to be big enough for the new precision. You may ! 160: specify a new precision that is smaller than the current precision. ! 161: You must be careful not to specify a new_precision value that is ! 162: too big, or which adjusts the r pointer out of range. ! 163: */ ! 164: #define rescale(r,currentp,newp) r -= ((newp) - (currentp)) ! 165: ! 166: /* The macro normalize(r,precision) "normalizes" a multiprecision integer ! 167: by adjusting r and precision to new values. For Motorola-style processors ! 168: (MSB-first), r is a pointer to the MSB of the register, and must ! 169: be adjusted to point to the first nonzero unit. For Intel/VAX-style ! 170: (LSB-first) processors, r is a pointer to the LSB of the register, ! 171: and must be left unchanged. The precision counter is always adjusted, ! 172: regardless of processor type. In the case of precision = 0, ! 173: r becomes undefined. ! 174: */ ! 175: #define normalize(r,prec) \ ! 176: { prec = significance(r); r += (global_precision-(prec)); } ! 177: ! 178: #else /* LOWFIRST byte order */ ! 179: ! 180: /* these definitions assume LSB comes first */ ! 181: #define tohigher(n) (n) /* offset towards higher unit */ ! 182: #define pre_higherunit(r) (++(r)) ! 183: #define pre_lowerunit(r) (--(r)) ! 184: #define post_higherunit(r) ((r)++) ! 185: #define post_lowerunit(r) ((r)--) ! 186: #define bit_index(n) (bits2units((n)+1)-1) ! 187: #define lsbptr(r,prec) (r) ! 188: #define make_lsbptr(r,prec) /* (r) = lsbptr(r,prec) */ ! 189: #define unmake_lsbptr(r,prec) /* (r) = (r) */ ! 190: #define msbptr(r,prec) ((r)+(prec)-1) ! 191: #define make_msbptr(r,prec) (r) = msbptr(r,prec) ! 192: ! 193: #define rescale(r,currentp,newp) /* nil statement */ ! 194: #define normalize(r,prec) prec = significance(r) ! 195: ! 196: #endif /* LOWFIRST byte order */ ! 197: /*------------------ End byte ordering stuff -------------------*/ ! 198: ! 199: /* Note that the address calculations require that lsbptr, msbptr, ! 200: make_lsbptr, make_msbptr, mp_tstbit, mp_setbit, mp_clrbit, ! 201: and bitptr all have unitptr arguments, not byte pointer arguments. ! 202: */ ! 203: #define bitptr(r,n) &((r)[bit_index(n)]) ! 204: #define bitmsk(n) power_of_2((n) & (UNITSIZE-1)) ! 205: /* bitmsk() assumes UNITSIZE is a power of 2 */ ! 206: #define mp_tstbit(r,n) (*bitptr(r,n) & bitmsk(n)) ! 207: #define mp_setbit(r,n) (*bitptr(r,n) |= bitmsk(n)) ! 208: #define mp_clrbit(r,n) (*bitptr(r,n) &= ~bitmsk(n)) ! 209: #define msunit(r) (*msbptr(r,global_precision)) ! 210: #define lsunit(r) (*lsbptr(r,global_precision)) ! 211: /* #define mp_tstminus(r) ((msunit(r) & uppermostbit)!=0) */ ! 212: #define mp_tstminus(r) ((signedunit) msunit(r) < 0) ! 213: ! 214: ! 215: /* set working precision to specified number of bits. */ ! 216: #ifdef mp_setp ! 217: void mp_setp(short nbits); ! 218: #define set_precision(prec) mp_setp(units2bits(global_precision=(prec))) ! 219: #else ! 220: #define set_precision(prec) (global_precision = (prec)) ! 221: #endif ! 222: ! 223: /* We'll pull in the assembler code here if asked to. */ ! 224: #ifdef WIN32 ! 225: #ifdef USE_WIN32_ASSEMBLER ! 226: #include "mpw32asm.h" ! 227: #endif /* USE_WIN32_ASSEMBLER */ ! 228: #endif /* WIN32 */ ! 229: ! 230: #ifdef PEASANT ! 231: ! 232: /* Define C names for Russian peasant modmult primitives. */ ! 233: #define stage_modulus stage_peasant_modulus ! 234: #define mp_modmult peasant_modmult ! 235: #define modmult_burn peasant_burn ! 236: #define SLOP_BITS PEASANT_SLOP_BITS ! 237: ! 238: #else /* not PEASANT */ ! 239: #ifdef MERRITT ! 240: /* Define C names for Merritt's modmult primitives. */ ! 241: #define stage_modulus stage_merritt_modulus ! 242: #define mp_modmult merritt_modmult ! 243: #define modmult_burn merritt_burn ! 244: #define SLOP_BITS MERRITT_SLOP_BITS ! 245: ! 246: #else /* not PEASANT, MERRITT */ ! 247: #ifdef UPTON ! 248: /* Define C names for Upton's modmult primitives. */ ! 249: #define stage_modulus stage_upton_modulus ! 250: #define mp_modmult upton_modmult ! 251: #define modmult_burn upton_burn ! 252: #define SLOP_BITS UPTON_SLOP_BITS ! 253: ! 254: #else /* not PEASANT, MERRITT, UPTON */ ! 255: #ifdef SMITH ! 256: /* Define C names for Smith's modmult primitives. */ ! 257: #define stage_modulus stage_smith_modulus ! 258: #define mp_modmult smith_modmult ! 259: #define modmult_burn smith_burn ! 260: #define SLOP_BITS SMITH_SLOP_BITS ! 261: ! 262: #endif /* SMITH */ ! 263: #endif /* UPTON */ ! 264: #endif /* MERRITT */ ! 265: #endif /* PEASANT */ ! 266: ! 267: ! 268: #define mp_shift_left(r1) mp_rotate_left(r1,(boolean)0) ! 269: /* multiprecision shift left 1 bit */ ! 270: ! 271: #if !defined(mp_add) ! 272: #define mp_add(r1,r2) mp_addc(r1,r2,(boolean)0) ! 273: /* multiprecision add with no carry */ ! 274: #endif ! 275: ! 276: #define mp_sub(r1,r2) mp_subb(r1,r2,(boolean)0) ! 277: /* multiprecision subtract with no borrow */ ! 278: ! 279: #define mp_abs(r) (mp_tstminus(r) ? (mp_neg(r),TRUE) : FALSE) ! 280: ! 281: #define msub(r,m) if (mp_compare(r,m) >= 0) mp_sub(r,m) ! 282: /* Prevents r from getting bigger than modulus m */ ! 283: ! 284: #define testeq(r,i) \ ! 285: ( (lsunit(r)==(i)) && (significance(r)<=1) ) ! 286: ! 287: #define testne(r,i) \ ! 288: ( (lsunit(r)!=(i)) || (significance(r)>1) ) ! 289: ! 290: #define testge(r,i) \ ! 291: ( (lsunit(r)>=(i)) || (significance(r)>1) ) ! 292: ! 293: #define testle(r,i) \ ! 294: ( (lsunit(r)<=(i)) && (significance(r)<=1) ) ! 295: ! 296: #define mp_square(r1,r2) mp_mult(r1,r2,r2) ! 297: /* Square r2, returning product in r1 */ ! 298: ! 299: #define mp_modsquare(r1,r2) mp_modmult(r1,r2,r2) ! 300: /* Square r2, returning modulo'ed product in r1 */ ! 301: ! 302: #define countbytes(r) ((countbits(r)+7)>>3) ! 303: ! 304: /* SLOP_BITS is how many "carry bits" to allow for intermediate ! 305: calculation results to exceed the size of the modulus. ! 306: It is used by modexp to give some overflow elbow room for ! 307: modmult to use to perform modulo operations with the modulus. ! 308: The number of slop bits required is determined by the modmult ! 309: algorithm. The Russian peasant modmult algorithm only requires ! 310: 1 slop bit, for example. Note that if we use an external assembly ! 311: modmult routine, SLOP_BITS may be meaningless or may be defined in a ! 312: non-constant manner. ! 313: */ ! 314: #define PEASANT_SLOP_BITS 1 ! 315: #define MERRITT_SLOP_BITS UNITSIZE ! 316: #define UPTON_SLOP_BITS (UNITSIZE/2) ! 317: #ifdef mp_smul /* old version requires MS word = 0 */ ! 318: #define SMITH_SLOP_BITS UNITSIZE ! 319: #else /* mp_smula or C version of mp_smul */ ! 320: #define SMITH_SLOP_BITS 0 ! 321: #endif /* mp_smul */ ! 322: ! 323: #define MIN_KEY_BITS 384 ! 324: #define MAX_KEY_BITS 2048 ! 325: ! 326: /* MAX_BIT_PRECISION is upper limit that assembly primitives can handle. ! 327: It must be less than 32704 bits, or 4088 bytes. It should be an ! 328: integer multiple of UNITSIZE*2. ! 329: */ ! 330: #define MAX_BIT_PRECISION (MAX_KEY_BITS+(2*UNITSIZE)) ! 331: #define MAX_BYTE_PRECISION (MAX_BIT_PRECISION/8) ! 332: #define MAX_UNIT_PRECISION (MAX_BIT_PRECISION/UNITSIZE) ! 333: ! 334: ! 335: /* global_precision is the unit precision last set by set_precision */ ! 336: #if defined(WIN32) ! 337: /* For Win32 we want this to be 32-bit, for compatibility with the assembler code */ ! 338: extern unsigned int global_precision; ! 339: #else ! 340: extern short global_precision; ! 341: #endif ! 342: ! 343: ! 344: /* The "bit sniffer" macros all begin sniffing at the MSB. ! 345: They are used internally by all the various multiply, divide, ! 346: modulo, exponentiation, and square root functions. ! 347: */ ! 348: #define sniff_bit(bptr,bitmask) (*(bptr) & bitmask) ! 349: ! 350: #define init_bitsniffer(bptr,bitmask,prec,bits) \ ! 351: { normalize(bptr,prec); \ ! 352: if (!prec) \ ! 353: return(0); \ ! 354: bits = units2bits(prec); \ ! 355: make_msbptr(bptr,prec); bitmask = uppermostbit; \ ! 356: while (!sniff_bit(bptr,bitmask)) \ ! 357: { bitmask >>= 1; bits--; \ ! 358: } \ ! 359: } ! 360: ! 361: #define bump_bitsniffer(bptr,bitmask) \ ! 362: { if (!(bitmask >>= 1)) \ ! 363: { bitmask = uppermostbit; \ ! 364: post_lowerunit(bptr); \ ! 365: } \ ! 366: } ! 367: ! 368: /* bump_2bitsniffers is used internally by mp_udiv. */ ! 369: #define bump_2bitsniffers(bptr,bptr2,bitmask) \ ! 370: { if (!(bitmask >>= 1)) \ ! 371: { bitmask = uppermostbit; \ ! 372: post_lowerunit(bptr); \ ! 373: post_lowerunit(bptr2); \ ! 374: } \ ! 375: } ! 376: ! 377: /* stuff_bit is used internally by mp_udiv and mp_sqrt. */ ! 378: #define stuff_bit(bptr,bitmask) *(bptr) |= bitmask ! 379: ! 380: ! 381: boolean mp_addc ! 382: (register unitptr r1,register unitptr r2,register boolean carry); ! 383: /* multiprecision add with carry r2 to r1, result in r1 */ ! 384: ! 385: boolean mp_subb ! 386: (register unitptr r1,register unitptr r2,register boolean borrow); ! 387: /* multiprecision subtract with borrow, r2 from r1, result in r1 */ ! 388: ! 389: boolean mp_rotate_left(register unitptr r1,register boolean carry); ! 390: /* multiprecision rotate left 1 bit with carry, result in r1. */ ! 391: ! 392: void mp_shift_right_bits(register unitptr r1,register short bits); ! 393: /* multiprecision shift right bits, result in r1. */ ! 394: ! 395: short mp_compare(register unitptr r1,register unitptr r2); ! 396: /* Compares registers *r1, *r2, and returns -1, 0, or 1 */ ! 397: ! 398: boolean mp_inc(register unitptr r); ! 399: /* Increment multiprecision integer r. */ ! 400: ! 401: boolean mp_dec(register unitptr r); ! 402: /* Decrement multiprecision integer r. */ ! 403: ! 404: void mp_neg(register unitptr r); ! 405: /* Compute 2's complement, the arithmetic negative, of r */ ! 406: ! 407: #ifndef mp_move ! 408: #define mp_move(d,s) memcpy((void*)(d), (void*)(s), \ ! 409: units2bytes(global_precision)) ! 410: #endif ! 411: #ifndef unitfill0 ! 412: #define unitfill0(r,ct) memset((void*)(r), 0, units2bytes(ct)) ! 413: #endif ! 414: ! 415: #ifndef mp_burn ! 416: #define mp_burn(r) mp_init(r,0) /* for burning the evidence */ ! 417: #define mp_init0(r) mp_init(r,0) ! 418: #endif ! 419: ! 420: #define empty_array(r) unitfill0(r, sizeof(r)/sizeof(r[0])/sizeof(unit)) ! 421: ! 422: void mp_init(register unitptr r, word16 value); ! 423: /* Init multiprecision register r with short value. */ ! 424: ! 425: short significance(register unitptr r); ! 426: /* Returns number of significant units in r */ ! 427: ! 428: int mp_udiv(register unitptr remainder,register unitptr quotient, ! 429: register unitptr dividend,register unitptr divisor); ! 430: /* Unsigned divide, treats both operands as positive. */ ! 431: ! 432: int mp_recip(register unitptr quotient,register unitptr divisor); ! 433: /* Compute reciprocal as 1/divisor. Used by faster modmult. */ ! 434: ! 435: int mp_div(register unitptr remainder,register unitptr quotient, ! 436: register unitptr dividend,register unitptr divisor); ! 437: /* Signed divide, either or both operands may be negative. */ ! 438: ! 439: word16 mp_shortdiv(register unitptr quotient, ! 440: register unitptr dividend,register word16 divisor); ! 441: /* Returns short remainder of unsigned divide. */ ! 442: ! 443: int mp_mod(register unitptr remainder, ! 444: register unitptr dividend,register unitptr divisor); ! 445: /* Unsigned divide, treats both operands as positive. */ ! 446: ! 447: word16 mp_shortmod(register unitptr dividend,register word16 divisor); ! 448: /* Just returns short remainder of unsigned divide. */ ! 449: ! 450: int mp_mult(register unitptr prod, ! 451: register unitptr multiplicand,register unitptr multiplier); ! 452: /* Computes multiprecision prod = multiplicand * multiplier */ ! 453: ! 454: int countbits(unitptr r); ! 455: /* Returns number of significant bits in r. */ ! 456: ! 457: int stage_peasant_modulus(unitptr n); ! 458: int stage_merritt_modulus(unitptr n); ! 459: int stage_upton_modulus(unitptr n); ! 460: int stage_smith_modulus(unitptr n); ! 461: /* Must pass modulus to stage_modulus before calling modmult. */ ! 462: ! 463: int peasant_modmult(register unitptr prod, ! 464: unitptr multiplicand,register unitptr multiplier); ! 465: int merritt_modmult(register unitptr prod, ! 466: unitptr multiplicand,register unitptr multiplier); ! 467: int upton_modmult(register unitptr prod, ! 468: unitptr multiplicand,register unitptr multiplier); ! 469: int smith_modmult(register unitptr prod, ! 470: unitptr multiplicand,register unitptr multiplier); ! 471: /* Performs combined multiply/modulo operation, with global modulus */ ! 472: ! 473: ! 474: ! 475: int mp_modexp(register unitptr expout,register unitptr expin, ! 476: register unitptr exponent,register unitptr modulus); ! 477: /* Combined exponentiation/modulo algorithm. */ ! 478: ! 479: int mp_modexp_crt(unitptr expout, unitptr expin, ! 480: unitptr p, unitptr q, unitptr ep, unitptr eq, unitptr u); ! 481: /* exponentiation and modulo using Chinese Remainder Theorem */ ! 482: ! 483: /****************** end of MPI library ****************************/
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.