Return to mpilib.h CVS log

Up to [PGP] / pgp / src

Annotation of pgp/src/mpilib.h, revision 1.1

1.1     ! 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 dependancies.  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
        !            25:        Implement new VAX/VMS primitive support.
        !            26: */
        !            27: 
        !            28: #include "usuals.h"  /* typedefs for byte, word16, boolean, etc. */
        !            29: 
        !            30: 
        !            31: /* #define PORTABLE    */ /* determines if we use C primitives */
        !            32: /* #define UNIT8       */ /* use 8-bit units */
        !            33: /* #define UNIT16      */ /* use 16-bit units */
        !            34: /* #define UNIT32      */ /* use 32-bit units */
        !            35: /* #define HIGHFIRST   */ /* determines if Motorola or Intel internal format */
        !            36: 
        !            37: #ifdef VMS                     /* VAX/VMS */
        !            38: #ifndef PORTABLE
        !            39: #define UNIT32          /* use 32-bit units */
        !            40: #endif /* not PORTABLE */
        !            41: #endif /* VMS */
        !            42: 
        !            43: #ifndef PEASANT /* if not Russian peasant modulo multiply algorithm */
        !            44: #ifndef MERRITT /* if not Merritt's modmult */
        !            45: #define UPTON  /* default: use Upton's modmult algorithm */
        !            46: #endif
        !            47: #endif
        !            48: 
        !            49: #ifndef UNIT32
        !            50: #ifndef UNIT8
        !            51: #define UNIT16                 /* default--use 16-bit units */
        !            52: #endif
        !            53: #endif
        !            54: 
        !            55: /***   CAUTION:  If your machine has an unusual word size that is not a
        !            56:        power of 2 (8, 16, 32, or 64) bits wide, then the macros here that 
        !            57:        use the symbol "LOG_UNITSIZE" must be changed.
        !            58: ***/
        !            59: 
        !            60: #ifdef UNIT8
        !            61: typedef unsigned char unit;
        !            62: typedef signed char signedunit;
        !            63: #define UNITSIZE 8 /* number of bits in a unit */
        !            64: #define uppermostbit ((unit) 0x80)
        !            65: #define BYTES_PER_UNIT 1 /* number of bytes in a unit */
        !            66: #define units2bits(n) ((n) << 3) /* fast multiply by UNITSIZE */
        !            67: #define units2bytes(n) (n)
        !            68: #define bits2units(n) (((n)+7) >> 3)
        !            69: #define bytes2units(n) (n)
        !            70: #endif
        !            71: 
        !            72: #ifdef UNIT16
        !            73: typedef word16 unit;
        !            74: typedef short signedunit;
        !            75: #define UNITSIZE 16 /* number of bits in a unit */
        !            76: #define uppermostbit ((unit) 0x8000)
        !            77: #define BYTES_PER_UNIT 2 /* number of bytes in a unit */
        !            78: #define units2bits(n) ((n) << 4) /* fast multiply by UNITSIZE */
        !            79: #define units2bytes(n) ((n) << 1)
        !            80: #define bits2units(n) (((n)+15) >> 4)
        !            81: #define bytes2units(n) (((n)+1) >> 1)
        !            82: #endif
        !            83: 
        !            84: #ifdef UNIT32
        !            85: typedef word32 unit;
        !            86: typedef long signedunit;
        !            87: #define UNITSIZE 32 /* number of bits in a unit */
        !            88: #define uppermostbit ((unit) 0x80000000L)
        !            89: #define BYTES_PER_UNIT 4 /* number of bytes in a unit */
        !            90: #define units2bits(n) ((n) << 5) /* fast multiply by UNITSIZE */
        !            91: #define units2bytes(n) ((n) << 2)
        !            92: #define bits2units(n) (((n)+31) >> 5)
        !            93: #define bytes2units(n) (((n)+3) >> 2)
        !            94: #undef PORTABLE                        /* can't use our C versions if 32 bits. */
        !            95: #endif
        !            96: 
        !            97: #define power_of_2(b) ((unit) 1 << (b)) /* computes power-of-2 bit masks */
        !            98: #define bits2bytes(n) (((n)+7) >> 3)
        !            99: /*     Some C compilers (like the ADSP2101) will not always collapse constant 
        !           100:        expressions at compile time if the expressions contain shift operators. */
        !           101: /* #define uppermostbit power_of_2(UNITSIZE-1) */
        !           102: /* #define UNITSIZE units2bits(1) */ /* number of bits in a unit */
        !           103: /* #define bytes2units(n) bits2units((n)<<3) */
        !           104: /* #define BYTES_PER_UNIT (UNITSIZE >> 3) */
        !           105: /* LOG_UNITSIZE is the log base 2 of UNITSIZE, ie: 4 for 16-bit units */
        !           106: /* #define units2bits(n) ((n) << LOG_UNITSIZE) */ /* fast multiply by UNITSIZE */
        !           107: /* #define units2bytes(n) ((n) << (LOG_UNITSIZE-3)) */
        !           108: /* #define bits2units(n) (((n)+(UNITSIZE-1)) >> LOG_UNITSIZE) */
        !           109: /* #define bytes2units(n) (((n)+(BYTES_PER_UNIT-1)) >> (LOG_UNITSIZE-3)) */
        !           110: 
        !           111: typedef unit *unitptr;
        !           112: 
        !           113: 
        !           114: /*--------------------- Byte ordering stuff -------------------*/
        !           115: #ifdef HIGHFIRST
        !           116: 
        !           117: /* these definitions assume MSB comes first */
        !           118: #define pre_higherunit(r)      (--(r))
        !           119: #define pre_lowerunit(r)       (++(r))
        !           120: #define post_higherunit(r)     ((r)--)
        !           121: #define post_lowerunit(r)      ((r)++)
        !           122: #define bit_index(n)           (global_precision-bits2units((n)+1))
        !           123: #define lsbptr(r,prec)         ((r)+(prec)-1)
        !           124: #define make_lsbptr(r,prec)    (r) = lsbptr(r,prec)  
        !           125: #define unmake_lsbptr(r,prec) (r) = ((r)-(prec)+1) 
        !           126: #define msbptr(r,prec)         (r)
        !           127: #define make_msbptr(r,prec)    /* (r) = msbptr(r,prec) */
        !           128: 
        !           129: #define rescale(r,currentp,newp) r -= ((newp) - (currentp))
        !           130: #define normalize(r,prec) \
        !           131:   { prec = significance(r); r += (global_precision-(prec)); }
        !           132: 
        !           133: #else  /* LOWFIRST byte order */
        !           134: 
        !           135: /* these definitions assume LSB comes first */
        !           136: #define pre_higherunit(r)      (++(r))
        !           137: #define pre_lowerunit(r)       (--(r))
        !           138: #define post_higherunit(r)     ((r)++)
        !           139: #define post_lowerunit(r)      ((r)--)
        !           140: #define bit_index(n)           (bits2units((n)+1)-1)
        !           141: #define lsbptr(r,prec)         (r)
        !           142: #define make_lsbptr(r,prec)    /* (r) = lsbptr(r,prec) */  
        !           143: #define unmake_lsbptr(r,prec) /* (r) = (r) */  
        !           144: #define msbptr(r,prec)         ((r)+(prec)-1)
        !           145: #define make_msbptr(r,prec)    (r) = msbptr(r,prec)
        !           146: 
        !           147: #define rescale(r,currentp,newp) /* nil statement */
        !           148: #define normalize(r,prec) prec = significance(r) 
        !           149: 
        !           150: #endif /* LOWFIRST byte order */
        !           151: /*------------------ End byte ordering stuff -------------------*/
        !           152: 
        !           153: /*     Note that the address calculations require that lsbptr, msbptr, 
        !           154:        make_lsbptr, make_msbptr, mp_tstbit, mp_setbit, mp_clrbit, 
        !           155:        and bitptr all have unitptr arguments, not byteptr arguments.  */
        !           156: #define bitptr(r,n) &((r)[bit_index(n)])
        !           157: #define bitmsk(n) power_of_2((n) & (UNITSIZE-1))
        !           158:        /* bitmsk() assumes UNITSIZE is a power of 2 */
        !           159: #define mp_tstbit(r,n) (*bitptr(r,n) &   bitmsk(n))
        !           160: #define mp_setbit(r,n) (*bitptr(r,n) |=  bitmsk(n))
        !           161: #define mp_clrbit(r,n) (*bitptr(r,n) &= ~bitmsk(n))
        !           162: #define msunit(r) (*msbptr(r,global_precision))
        !           163: #define lsunit(r) (*lsbptr(r,global_precision))
        !           164: /* #define mp_tstminus(r) ((msunit(r) & uppermostbit)!=0) */
        !           165: #define mp_tstminus(r) ((signedunit) msunit(r) < 0)
        !           166: 
        !           167: /*     MAX_BIT_PRECISION is upper limit that assembly primitives can handle.
        !           168:        It must be less than 32704 bits, or 4088 bytes.  It should be an
        !           169:        integer multiple of UNITSIZE*2.
        !           170: */
        !           171: #define MAX_BIT_PRECISION 1152
        !           172: #define MAX_BYTE_PRECISION (MAX_BIT_PRECISION/8)
        !           173: #define MAX_UNIT_PRECISION (MAX_BIT_PRECISION/UNITSIZE)
        !           174: 
        !           175: 
        !           176: /*************** multiprecision library primitives ****************/
        !           177: #ifdef PORTABLE        /* using slow portable C primitives */
        !           178: 
        !           179: #define set_precision(prec) (global_precision = (prec))
        !           180: 
        !           181: #else  /* not PORTABLE - not using portable C primitives */
        !           182: /*
        !           183:        The following primitives should be coded in assembly.
        !           184:        Functions P_ADDC, P_SUBB, and P_ROTL return a carry flag as their
        !           185:        functional return, and the result of the operation is placed in r1.
        !           186:        These assembly primitives are externally defined, unless PORTABLE 
        !           187:        is defined.
        !           188: */
        !           189: 
        !           190: #ifdef VMS
        !           191: /*
        !           192:        Define Assembler Prims With Lowercase Names To Prevent GCC hacking
        !           193:        them
        !           194: */
        !           195: #define P_SETP p_setp
        !           196: #define P_ADDC p_addc
        !           197: #define P_SUBB p_subb
        !           198: #define P_ROTL p_rotl
        !           199: 
        !           200: #endif /* VMS */
        !           201: 
        !           202: void P_SETP(short nbits);
        !           203:        /* sets working precision to specified number of bits. */
        !           204: 
        !           205: boolean P_ADDC(unitptr r1, unitptr r2, boolean carry);
        !           206:        /* multiprecision add with carry r2 to r1, result in r1 */
        !           207: 
        !           208: boolean P_SUBB(unitptr r1, unitptr r2, boolean borrow);
        !           209:        /* multiprecision subtract with borrow, r2 from r1, result in r1 */
        !           210: 
        !           211: boolean P_ROTL(unitptr r1, boolean carry);
        !           212:        /* multiprecision rotate left 1 bit with carry, result in r1. */
        !           213: 
        !           214: /* Define C primitive names as the equivalent calls to assembly primitives. */
        !           215: #define set_precision(prec)    P_SETP(units2bits(global_precision=(prec)))
        !           216: #define mp_addc                P_ADDC
        !           217: #define mp_subb                P_SUBB
        !           218: #define mp_rotate_left  P_ROTL
        !           219: 
        !           220: #ifdef VMS
        !           221: 
        !           222: short p_cmp(register unitptr r1,register unitptr r2);
        !           223:        /* Compares registers *r1, *r2, and returns -1, 0, or 1 */
        !           224: 
        !           225: #define mp_compare p_cmp
        !           226: 
        !           227: #endif /* VMS */
        !           228: 
        !           229: #endif /* not PORTABLE */
        !           230: /************** end of primitives that should be in assembly *************/
        !           231: 
        !           232: #ifdef PEASANT
        !           233: 
        !           234: /* Define C names for Russian peasant modmult primitives. */
        !           235: #define stage_modulus stage_peasant_modulus
        !           236: #define mp_modmult peasant_modmult
        !           237: #define modmult_burn peasant_burn
        !           238: 
        !           239: #endif /* PEASANT */
        !           240: 
        !           241: #ifdef MERRITT
        !           242: /* Define C names for Merritt's modmult primitives. */
        !           243: #define stage_modulus stage_merritt_modulus
        !           244: #define mp_modmult merritt_modmult
        !           245: #define modmult_burn merritt_burn
        !           246: 
        !           247: #endif /* MERRITT */
        !           248: 
        !           249: #ifdef UPTON
        !           250: /* Define C names for Upton's modmult primitives. */
        !           251: #define stage_modulus stage_upton_modulus
        !           252: #define mp_modmult upton_modmult
        !           253: #define modmult_burn upton_burn
        !           254: 
        !           255: #endif /* UPTON */
        !           256: 
        !           257: 
        !           258: #define mp_shift_left(r1) mp_rotate_left(r1,(boolean)0)
        !           259:        /* multiprecision shift left 1 bit */
        !           260: 
        !           261: #define mp_add(r1,r2) mp_addc(r1,r2,(boolean)0)
        !           262:        /* multiprecision add with no carry */
        !           263: 
        !           264: #define mp_sub(r1,r2) mp_subb(r1,r2,(boolean)0)
        !           265:        /* multiprecision subtract with no borrow */
        !           266: 
        !           267: #define mp_abs(r) (mp_tstminus(r) ? (mp_neg(r),TRUE) : FALSE)
        !           268: 
        !           269: #define msub(r,m) if (mp_compare(r,m) >= 0) mp_sub(r,m)
        !           270:        /* Prevents r from getting bigger than modulus m */
        !           271: 
        !           272: #define testeq(r,i)    \
        !           273:        ( (lsunit(r)==(i)) && (significance(r)<=1) )
        !           274: 
        !           275: #define testne(r,i)    \
        !           276:        ( (lsunit(r)!=(i)) || (significance(r)>1) )
        !           277: 
        !           278: #define testge(r,i)    \
        !           279:        ( (lsunit(r)>=(i)) || (significance(r)>1) )
        !           280: 
        !           281: #define testle(r,i)    \
        !           282:        ( (lsunit(r)<=(i)) && (significance(r)<=1) )
        !           283: 
        !           284: #define mp_square(r1,r2) mp_mult(r1,r2,r2)
        !           285:        /* Square r2, returning product in r1 */
        !           286: 
        !           287: #define mp_modsquare(r1,r2) mp_modmult(r1,r2,r2)
        !           288:        /* Square r2, returning modulo'ed product in r1 */
        !           289: 
        !           290: #define countbytes(r) ((countbits(r)+7)>>3)
        !           291: 
        !           292: /*     SLOP_BITS is how many "carry bits" to allow for intermediate 
        !           293:        calculation results to exceed the size of the modulus.
        !           294:        It is used by modexp to give some overflow elbow room for
        !           295:        modmult to use to perform modulo operations with the modulus. 
        !           296:        The number of slop bits required is determined by the modmult 
        !           297:        algorithm.  The Russian peasant modmult algorithm only requires 
        !           298:        1 slop bit, for example.  Note that if we use an external assembly
        !           299:        modmult routine, SLOP_BITS may be meaningless or may be defined in a
        !           300:        non-constant manner.
        !           301: */
        !           302: #ifdef MERRITT /* use Merritt's modmult algorithm */
        !           303: #define SLOP_BITS (UNITSIZE+1)
        !           304: #define MERRITT_KEY    /* cause keygen to generate unnormalized keys */
        !           305: #endif /* MERRITT */
        !           306: #ifdef PEASANT /* use Russian peasant modmult algorithm */
        !           307: #define SLOP_BITS 1
        !           308: #endif /* PEASANT */
        !           309: #ifdef UPTON   /* use Upton's modmult algorithm */
        !           310: /* Not clear what SLOP_BITS needs to be */
        !           311: #define SLOP_BITS UNITSIZE
        !           312: #endif /* UPTON */
        !           313: 
        !           314: /* global_precision is the unit precision last set by set_precision */
        !           315: extern short global_precision;
        !           316: 
        !           317: 
        !           318: 
        !           319: /*     The "bit sniffer" macros all begin sniffing at the MSB.
        !           320:        They are used internally by all the various multiply, divide, 
        !           321:        modulo, exponentiation, and square root functions.
        !           322: */
        !           323: #define sniff_bit(bptr,bitmask)        (*(bptr) & bitmask)
        !           324: 
        !           325: #define init_bitsniffer(bptr,bitmask,prec,bits) \
        !           326: { normalize(bptr,prec); \
        !           327:   if (!prec) \
        !           328:     return(0); \
        !           329:   bits = units2bits(prec); \
        !           330:   make_msbptr(bptr,prec); bitmask = uppermostbit; \
        !           331:   while (!sniff_bit(bptr,bitmask)) \
        !           332:   { bitmask >>= 1; bits--; \
        !           333:   } \
        !           334: }
        !           335: 
        !           336: #define bump_bitsniffer(bptr,bitmask) \
        !           337: { if (!(bitmask >>= 1)) \
        !           338:   { bitmask = uppermostbit; \
        !           339:        post_lowerunit(bptr); \
        !           340:   } \
        !           341: }
        !           342: 
        !           343: /* bump_2bitsniffers is used internally by mp_udiv. */
        !           344: #define bump_2bitsniffers(bptr,bptr2,bitmask) \
        !           345: { if (!(bitmask >>= 1)) \
        !           346:   { bitmask = uppermostbit; \
        !           347:     post_lowerunit(bptr); \
        !           348:     post_lowerunit(bptr2); \
        !           349:   } \
        !           350: }
        !           351: 
        !           352: /* stuff_bit is used internally by mp_udiv and mp_sqrt. */
        !           353: #define stuff_bit(bptr,bitmask)        *(bptr) |= bitmask
        !           354: 
        !           355: 
        !           356: 
        !           357: #ifdef PORTABLE        /* these slow C primitives should be recoded in assembly */
        !           358: 
        !           359: boolean mp_addc
        !           360:        (register unitptr r1,register unitptr r2,register boolean carry);
        !           361:        /* multiprecision add with carry r2 to r1, result in r1 */
        !           362: 
        !           363: boolean mp_subb
        !           364:        (register unitptr r1,register unitptr r2,register boolean borrow);
        !           365:        /* multiprecision subtract with borrow, r2 from r1, result in r1 */
        !           366: 
        !           367: boolean mp_rotate_left(register unitptr r1,register boolean carry);
        !           368:        /* multiprecision rotate left 1 bit with carry, result in r1. */
        !           369: 
        !           370: #endif /* PORTABLE */
        !           371: 
        !           372: void mp_shift_right_bits(register unitptr r1,register short bits);
        !           373:        /* multiprecision shift right bits, result in r1. */
        !           374: 
        !           375: short mp_compare(register unitptr r1,register unitptr r2);
        !           376:        /* Compares registers *r1, *r2, and returns -1, 0, or 1 */      
        !           377: 
        !           378: boolean mp_inc(register unitptr r);
        !           379:        /* Increment multiprecision integer r. */
        !           380: 
        !           381: boolean mp_dec(register unitptr r);
        !           382:        /* Decrement multiprecision integer r. */
        !           383: 
        !           384: void mp_neg(register unitptr r);
        !           385:        /* Compute 2's complement, the arithmetic negative, of r */
        !           386: 
        !           387: #ifdef VAXC
        !           388: /*
        !           389:  * A VAX is a CISC machine. Unfortunately C is at to low a level to use
        !           390:  * many of the instruction set enhancements so we define some macros
        !           391:  * here that implement fast moves and fast zero fills with single
        !           392:  * instructions.
        !           393:  */
        !           394: 
        !           395: #pragma builtins
        !           396: #define mp_move( dst, src)       _MOVC3( global_precision*4, (char *) src, (char *) dst)
        !           397: #define unitfill0( r, unitcount) _MOVC5( 0, (char *) 0, 0, unitcount*4, (char *) r)
        !           398: #define mp_burn(r) _MOVC5(0, (char *) 0, 0, global_precision*4, (char *) r)
        !           399: #define mp_init0(r) mp_burn(r) /* Just for documentation purposes */
        !           400: 
        !           401: #else /* VAXC */
        !           402: 
        !           403: void mp_move(register unitptr dst,register unitptr src);
        !           404: 
        !           405: void unitfill0(unitptr r,word16 unitcount);
        !           406: #define mp_burn(r) mp_init(r,0) /* for burning the evidence */
        !           407: #define mp_init0(r) mp_init(r,0)
        !           408: 
        !           409: #endif /* VAXC */
        !           410: 
        !           411: void mp_init(register unitptr r, word16 value);
        !           412:        /* Init multiprecision register r with short value. */
        !           413: 
        !           414: short significance(register unitptr r);
        !           415:        /* Returns number of significant units in r */
        !           416: 
        !           417: int mp_udiv(register unitptr remainder,register unitptr quotient,
        !           418:        register unitptr dividend,register unitptr divisor);
        !           419:        /* Unsigned divide, treats both operands as positive. */
        !           420: 
        !           421: int mp_recip(register unitptr quotient,register unitptr divisor);
        !           422:        /* Compute reciprocal as 1/divisor.  Used by faster modmult. */
        !           423: 
        !           424: int mp_div(register unitptr remainder,register unitptr quotient,
        !           425:        register unitptr dividend,register unitptr divisor);
        !           426:        /* Signed divide, either or both operands may be negative. */
        !           427: 
        !           428: word16 mp_shortdiv(register unitptr quotient,
        !           429:        register unitptr dividend,register word16 divisor);
        !           430:        /* Returns short remainder of unsigned divide. */
        !           431: 
        !           432: int mp_mod(register unitptr remainder,
        !           433:        register unitptr dividend,register unitptr divisor);
        !           434:        /* Unsigned divide, treats both operands as positive. */
        !           435: 
        !           436: word16 mp_shortmod(register unitptr dividend,register word16 divisor);
        !           437:        /* Just returns short remainder of unsigned divide. */
        !           438: 
        !           439: int mp_mult(register unitptr prod,
        !           440:        register unitptr multiplicand,register unitptr multiplier);
        !           441:        /* Computes multiprecision prod = multiplicand * multiplier */
        !           442: 
        !           443: int stage_modulus(unitptr n);
        !           444:        /* Must pass modulus to stage_modulus before calling modmult. */
        !           445: 
        !           446: int mp_modmult(register unitptr prod,
        !           447:        unitptr multiplicand,register unitptr multiplier);
        !           448:        /* Performs combined multiply/modulo operation, with global modulus */
        !           449: 
        !           450: int countbits(unitptr r);
        !           451:        /* Returns number of significant bits in r. */
        !           452: 
        !           453: int mp_modexp(register unitptr expout,register unitptr expin,
        !           454:        register unitptr exponent,register unitptr modulus);
        !           455:        /* Combined exponentiation/modulo algorithm. */
        !           456: 
        !           457: int rsa_decrypt(unitptr M, unitptr C,
        !           458:        unitptr d, unitptr p, unitptr q, unitptr u);
        !           459:        /* Uses Chinese Remainder Theorem shortcut for RSA decryption. */
        !           460: 
        !           461: /****************** end of MPI library ****************************/

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.