Return to rsalib.h CVS log

Up to [PGP] / pgp / src

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

1.1     ! root        1: /*     C include file for RSA library math routines
        !             2: 
        !             3:        Boulder Software Engineering
        !             4:        3021 Eleventh Street
        !             5:        Boulder, CO 80304
        !             6:        (303) 444-4541
        !             7: 
        !             8:        (c) Copyright 1986 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 RSA public key cryptography.
        !            15: 
        !            16:        Although originally developed in Microsoft C for the IBM PC, this code 
        !            17:        contains few machine dependancies.  It assumes 2's complement 
        !            18:        arithmetic.  It can be adapted to 8-bit, 16-bit, or 32-bit machines, 
        !            19:        lowbyte-highbyte order or highbyte-lowbyte order.  This version
        !            20:        has been converted to ANSI C.
        !            21: */
        !            22: 
        !            23: /* Elaborate protection mechanisms to assure no redefinitions of types...*/
        !            24: #ifndef BOOLSTUFF
        !            25: #define BOOLSTUFF
        !            26: #ifndef TRUE
        !            27: #define FALSE 0
        !            28: #define TRUE (!FALSE)
        !            29: #endif /* if TRUE not already defined */
        !            30: typedef unsigned char boolean; /* values are TRUE or FALSE */
        !            31: #endif /* if BOOLSTUFF not already defined */
        !            32: #ifndef BYTESTUFF
        !            33: #define BYTESTUFF
        !            34: typedef unsigned char byte;    /* values are 0-255 */
        !            35: typedef byte *byteptr; /* pointer to byte */
        !            36: typedef char *string;  /* pointer to ASCII character string */
        !            37: #endif /* if BYTESTUFF not already defined */
        !            38: #ifndef WORDSTUFF
        !            39: #define WORDSTUFF
        !            40: typedef unsigned short word16; /* values are 0-65536 */
        !            41: typedef unsigned long word32;  /* values are 0-4294967296 */
        !            42: #endif /* if WORDSTUFF not already defined */
        !            43: #ifndef min    /* if min macro not already defined */
        !            44: #define min(a,b) ( (a)<(b) ? (a) : (b) )
        !            45: #define max(a,b) ( (a)>(b) ? (a) : (b) )
        !            46: #endif /* if min macro not already defined */
        !            47: 
        !            48: 
        !            49: /* #define PORTABLE    */ /* determines if we use C primitives */
        !            50: /* #define STEWART */ /* determines if we use Stewart's modmult */
        !            51: /* #define ASM_MODMULT */ /* determines if we use assembly modmult */
        !            52: /* #define UNIT8       */ /* use 8-bit units */
        !            53: /* #define UNIT16      */ /* use 16-bit units */
        !            54: /* #define UNIT32      */ /* use 32-bit units */
        !            55: /* #define HIGHFIRST   */ /* determines if Motorola or Intel internal format */
        !            56: 
        !            57: 
        !            58: #ifndef STEWART        /* if not Stewart's modmult algorithm */
        !            59: #ifndef ASM_MODMULT    /* if not assembly modmult algorithm */
        !            60: #ifndef PEASANT /* if not Russian peasant modulo multiply algorithm */
        !            61: #define MERRITT        /* default: use Merritt's modmult algorithm */
        !            62: #endif
        !            63: #endif
        !            64: #endif
        !            65: 
        !            66: #ifndef UNIT32
        !            67: #ifndef UNIT8
        !            68: #define UNIT16                 /* default--use 16-bit units */
        !            69: #endif
        !            70: #endif
        !            71: 
        !            72: /***   CAUTION:  If your machine has an unusual word size that is not a
        !            73:        power of 2 (8, 16, 32, or 64) bits wide, then the macros here that 
        !            74:        use the symbol "LOG_UNITSIZE" must be changed.
        !            75: ***/
        !            76: 
        !            77: #ifdef UNIT8
        !            78: typedef unsigned char unit;
        !            79: typedef signed char signedunit;
        !            80: #define UNITSIZE 8 /* number of bits in a unit */
        !            81: #define uppermostbit ((unit) 0x80)
        !            82: #define BYTES_PER_UNIT 1 /* number of bytes in a unit */
        !            83: #define units2bits(n) ((n) << 3) /* fast multiply by UNITSIZE */
        !            84: #define units2bytes(n) (n)
        !            85: #define bits2units(n) (((n)+7) >> 3)
        !            86: #define bytes2units(n) (n)
        !            87: #endif
        !            88: 
        !            89: #ifdef UNIT16
        !            90: typedef word16 unit;
        !            91: typedef short signedunit;
        !            92: #define UNITSIZE 16 /* number of bits in a unit */
        !            93: #define uppermostbit ((unit) 0x8000)
        !            94: #define BYTES_PER_UNIT 2 /* number of bytes in a unit */
        !            95: #define units2bits(n) ((n) << 4) /* fast multiply by UNITSIZE */
        !            96: #define units2bytes(n) ((n) << 1)
        !            97: #define bits2units(n) (((n)+15) >> 4)
        !            98: #define bytes2units(n) (((n)+1) >> 1)
        !            99: #endif
        !           100: 
        !           101: #ifdef UNIT32
        !           102: typedef word32 unit;
        !           103: typedef long signedunit;
        !           104: #define UNITSIZE 32 /* number of bits in a unit */
        !           105: #define uppermostbit ((unit) 0x80000000)
        !           106: #define BYTES_PER_UNIT 4 /* number of bytes in a unit */
        !           107: #define units2bits(n) ((n) << 5) /* fast multiply by UNITSIZE */
        !           108: #define units2bytes(n) ((n) << 2)
        !           109: #define bits2units(n) (((n)+31) >> 5)
        !           110: #define bytes2units(n) (((n)+3) >> 2)
        !           111: #undef PORTABLE                        /* can't use our C versions if 32 bits. */
        !           112: #endif
        !           113: 
        !           114: #define power_of_2(b) ((unit) 1 << (b)) /* computes power-of-2 bit masks */
        !           115: #define bits2bytes(n) (((n)+7) >> 3)
        !           116: /*     Some C compilers (like the ADSP2101) will not always collapse constant 
        !           117:        expressions at compile time if the expressions contain shift operators. */
        !           118: /* #define uppermostbit power_of_2(UNITSIZE-1) */
        !           119: /* #define UNITSIZE units2bits(1) */ /* number of bits in a unit */
        !           120: /* #define bytes2units(n) bits2units((n)<<3) */
        !           121: /* #define BYTES_PER_UNIT (UNITSIZE >> 3) */
        !           122: /* LOG_UNITSIZE is the log base 2 of UNITSIZE, ie: 4 for 16-bit units */
        !           123: /* #define units2bits(n) ((n) << LOG_UNITSIZE) */ /* fast multiply by UNITSIZE */
        !           124: /* #define units2bytes(n) ((n) << (LOG_UNITSIZE-3)) */
        !           125: /* #define bits2units(n) (((n)+(UNITSIZE-1)) >> LOG_UNITSIZE) */
        !           126: /* #define bytes2units(n) (((n)+(BYTES_PER_UNIT-1)) >> (LOG_UNITSIZE-3)) */
        !           127: 
        !           128: typedef unit *unitptr;
        !           129: 
        !           130: 
        !           131: /*--------------------- Byte ordering stuff -------------------*/
        !           132: #ifdef HIGHFIRST
        !           133: 
        !           134: /* these definitions assume MSB comes first */
        !           135: #define pre_higherunit(r)      (--(r))
        !           136: #define pre_lowerunit(r)       (++(r))
        !           137: #define post_higherunit(r)     ((r)--)
        !           138: #define post_lowerunit(r)      ((r)++)
        !           139: #define bit_index(n)           (global_precision-bits2units((n)+1))
        !           140: #define lsbptr(r,prec)         ((r)+(prec)-1)
        !           141: #define make_lsbptr(r,prec)    (r) = lsbptr(r,prec)  
        !           142: #define unmake_lsbptr(r,prec) (r) = ((r)-(prec)+1) 
        !           143: #define msbptr(r,prec)         (r)
        !           144: #define make_msbptr(r,prec)    /* (r) = msbptr(r,prec) */
        !           145: 
        !           146: #define rescale(r,currentp,newp) r -= ((newp) - (currentp))
        !           147: #define normalize(r,prec) \
        !           148:   { prec = significance(r); r += (global_precision-(prec)); }
        !           149: 
        !           150: #else  /* LOWFIRST byte order */
        !           151: 
        !           152: /* these definitions assume LSB comes first */
        !           153: #define pre_higherunit(r)      (++(r))
        !           154: #define pre_lowerunit(r)       (--(r))
        !           155: #define post_higherunit(r)     ((r)++)
        !           156: #define post_lowerunit(r)      ((r)--)
        !           157: #define bit_index(n)           (bits2units((n)+1)-1)
        !           158: #define lsbptr(r,prec)         (r)
        !           159: #define make_lsbptr(r,prec)    /* (r) = lsbptr(r,prec) */  
        !           160: #define unmake_lsbptr(r,prec) /* (r) = (r) */  
        !           161: #define msbptr(r,prec)         ((r)+(prec)-1)
        !           162: #define make_msbptr(r,prec)    (r) = msbptr(r,prec)
        !           163: 
        !           164: #define rescale(r,currentp,newp) /* nil statement */
        !           165: #define normalize(r,prec) prec = significance(r) 
        !           166: 
        !           167: #endif /* LOWFIRST byte order */
        !           168: /*------------------ End byte ordering stuff -------------------*/
        !           169: 
        !           170: /*     Note that the address calculations require that lsbptr, msbptr, 
        !           171:        make_lsbptr, make_msbptr, mp_tstbit, mp_setbit, mp_clrbit, 
        !           172:        and bitptr all have unitptr arguments, not byteptr arguments.  */
        !           173: #define bitptr(r,n) &((r)[bit_index(n)])
        !           174: #define mp_tstbit(r,n) (*bitptr(r,n) &   power_of_2((n) & (UNITSIZE-1)))
        !           175: #define mp_setbit(r,n) (*bitptr(r,n) |=  power_of_2((n) & (UNITSIZE-1)))
        !           176: #define mp_clrbit(r,n) (*bitptr(r,n) &= ~power_of_2((n) & (UNITSIZE-1)))
        !           177: #define msunit(r) (*msbptr(r,global_precision))
        !           178: #define lsunit(r) (*lsbptr(r,global_precision))
        !           179: /* #define mp_tstminus(r) ((msunit(r) & uppermostbit)!=0) */
        !           180: #define mp_tstminus(r) ((signedunit) msunit(r) < 0)
        !           181: 
        !           182: /*     MAX_BIT_PRECISION is upper limit that assembly primitives can handle.
        !           183:        It must be less than 32704 bits, or 4088 bytes.  It should be an
        !           184:        integer multiple of UNITSIZE*2.
        !           185: */
        !           186: #define MAX_BIT_PRECISION 1024 /* limit for current 8086 primitives */
        !           187: /* #define MAX_BIT_PRECISION 544 /* 544 is limit for ADSP2101 primitives */
        !           188: #define MAX_BYTE_PRECISION (MAX_BIT_PRECISION/8)
        !           189: #define MAX_UNIT_PRECISION (MAX_BIT_PRECISION/UNITSIZE)
        !           190: 
        !           191: 
        !           192: /*************** multiprecision library primitives ****************/
        !           193: #ifdef PORTABLE        /* using slow portable C primitives */
        !           194: 
        !           195: #define set_precision(prec) (global_precision = (prec))
        !           196: 
        !           197: #else  /* not PORTABLE - not using portable C primitives */
        !           198: /*
        !           199:        The following primitives should be coded in assembly.
        !           200:        Functions P_ADDC, P_SUBB, and P_ROTL return a carry flag as their
        !           201:        functional return, and the result of the operation is placed in r1.
        !           202:        These assembly primitives are externally defined, unless PORTABLE 
        !           203:        is defined.
        !           204: */
        !           205: 
        !           206: void P_SETP(short nbits);
        !           207:        /* sets working precision to specified number of bits. */
        !           208: 
        !           209: boolean P_ADDC(unitptr r1, unitptr r2, boolean carry);
        !           210:        /* multiprecision add with carry r2 to r1, result in r1 */
        !           211: 
        !           212: boolean P_SUBB(unitptr r1, unitptr r2, boolean borrow);
        !           213:        /* multiprecision subtract with borrow, r2 from r1, result in r1 */
        !           214: 
        !           215: boolean P_ROTL(unitptr r1, boolean carry);
        !           216:        /* multiprecision rotate left 1 bit with carry, result in r1. */
        !           217: 
        !           218: /* Define C primitive names as the equivalent calls to assembly primitives. */
        !           219: #define set_precision(prec)    P_SETP(units2bits(global_precision=(prec)))
        !           220: #define mp_addc                P_ADDC
        !           221: #define mp_subb                P_SUBB
        !           222: #define mp_rotate_left  P_ROTL
        !           223: 
        !           224: #endif /* not PORTABLE */
        !           225: /************** end of primitives that should be in assembly *************/
        !           226: 
        !           227: #ifdef ASM_MODMULT     /* use assembly primitive modmult */
        !           228: 
        !           229: /*     The following modmult-related primitives can be coded in assembly.
        !           230:        These assembly primitives are externally defined, 
        !           231:        if ASM_MODMULT is defined.
        !           232: */
        !           233: 
        !           234: /* Define C names for assembly modmult primitives. */
        !           235: #define stage_modulus P_STAGEMOD
        !           236: #define mp_modmult P_MMULT
        !           237: #define modmult_burn P_MMBURN
        !           238: 
        !           239: #endif /* ASM_MODMULT */
        !           240: 
        !           241: #ifdef PEASANT
        !           242: 
        !           243: /* Define C names for Russian peasant modmult primitives. */
        !           244: #define stage_modulus stage_peasant_modulus
        !           245: #define mp_modmult peasant_modmult
        !           246: #define modmult_burn peasant_burn
        !           247: 
        !           248: #endif /* PEASANT */
        !           249: 
        !           250: #ifdef MERRITT
        !           251: /* Define C names for Merritt's modmult primitives. */
        !           252: #define stage_modulus stage_merritt_modulus
        !           253: #define mp_modmult merritt_modmult
        !           254: #define modmult_burn merritt_burn
        !           255: 
        !           256: #endif /* MERRITT */
        !           257: 
        !           258: #ifdef STEWART
        !           259: /* Define C names for Stewart's modmult primitives. */
        !           260: #define stage_modulus stage_stewart_modulus
        !           261: #define mp_modmult P_MMULT
        !           262: #define modmult_burn stewart_burn
        !           263: 
        !           264: #endif /* STEWART */
        !           265: 
        !           266: 
        !           267: #define mp_shift_left(r1) mp_rotate_left(r1,(boolean)0)
        !           268:        /* multiprecision shift left 1 bit */
        !           269: 
        !           270: #define mp_shift_right(r1) mp_rotate_right(r1,(boolean)0)
        !           271:        /* multiprecision shift right 1 bit */
        !           272: 
        !           273: #define mp_add(r1,r2) mp_addc(r1,r2,(boolean)0)
        !           274:        /* multiprecision add with no carry */
        !           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 mp_burn(r) mp_init(r,0)        /* for burning the evidence */
        !           285: 
        !           286: #define testeq(r,i)    \
        !           287:        ( (lsunit(r)==(i)) && (significance(r)<=1) )
        !           288: 
        !           289: #define testne(r,i)    \
        !           290:        ( (lsunit(r)!=(i)) || (significance(r)>1) )
        !           291: 
        !           292: #define mp_square(r1,r2) mp_mult(r1,r2,r2)
        !           293:        /* Square r2, returning product in r1 */
        !           294: 
        !           295: #define mp_modsquare(r1,r2) mp_modmult(r1,r2,r2)
        !           296:        /* Square r2, returning modulo'ed product in r1 */
        !           297: 
        !           298: #define countbytes(r) ((countbits(r)+7)>>3)
        !           299: 
        !           300: /*     SLOP_BITS is how many "carry bits" to allow for intermediate 
        !           301:        calculation results to exceed the size of the modulus.
        !           302:        It is used by modexp to give some overflow elbow room for
        !           303:        modmult to use to perform modulo operations with the modulus. 
        !           304:        The number of slop bits required is determined by the modmult 
        !           305:        algorithm.  The Russian peasant modmult algorithm only requires 
        !           306:        1 slop bit, for example.  Note that if ASM_MODMULT is
        !           307:        defined, SLOP_BITS may be meaningless or may be defined in a
        !           308:        non-constant manner.
        !           309: */
        !           310: #ifdef MERRITT /* use Merritt's modmult algorithm */
        !           311: #define SLOP_BITS (UNITSIZE+1)
        !           312: #define MERRITT_KEY    /* cause keygen to generate unnormalized keys */
        !           313: #endif /* MERRITT */
        !           314: #ifdef PEASANT /* use Russian peasant modmult algorithm */
        !           315: #define SLOP_BITS 1
        !           316: #endif /* PEASANT */
        !           317: #ifdef ASM_MODMULT     /* use external assembly modmult algorithm */
        !           318: /* SLOP_BITS is likely either 1, UNITSIZE+1, non-constant or meaningless. */
        !           319: #define SLOP_BITS 0
        !           320: #endif /* ASM_MODMULT */
        !           321: #ifdef STEWART /* use Stewart's modmult modmult algorithm */
        !           322: #define SLOP_BITS 0
        !           323: #define STEWART_KEY    /* cause keygen to generate normalized keys */
        !           324: #endif /* STEWART */
        !           325: 
        !           326: 
        !           327: #ifndef RSALIB /* not compiling RSALIB */
        !           328: /* global_precision is the unit precision last set by set_precision */
        !           329: extern short global_precision;
        !           330: #endif /* not compiling RSALIB */
        !           331: 
        !           332: 
        !           333: #ifndef RSALIB /* not compiling RSALIB */
        !           334:        /*      Bug in DSP2101 C compiler -- no function protypes 
        !           335:                allowed when compiling those same functions. */
        !           336: 
        !           337: #ifdef PORTABLE        /* these slow C primitives should be recoded in assembly */
        !           338: 
        !           339: boolean mp_addc
        !           340:        (register unitptr r1,register unitptr r2,register boolean carry);
        !           341:        /* multiprecision add with carry r2 to r1, result in r1 */
        !           342: 
        !           343: boolean mp_subb
        !           344:        (register unitptr r1,register unitptr r2,register boolean borrow);
        !           345:        /* multiprecision subtract with borrow, r2 from r1, result in r1 */
        !           346: 
        !           347: boolean mp_rotate_left(register unitptr r1,register boolean carry);
        !           348:        /* multiprecision rotate left 1 bit with carry, result in r1. */
        !           349: 
        !           350: #endif /* PORTABLE */
        !           351: 
        !           352: boolean mp_rotate_right(register unitptr r1,register boolean carry);
        !           353:        /* multiprecision rotate right 1 bit with carry, r1. */
        !           354: 
        !           355: short mp_compare(register unitptr r1,register unitptr r2);
        !           356:        /* Compares registers *r1, *r2, and returns -1, 0, or 1 */      
        !           357: 
        !           358: boolean mp_inc(register unitptr r);
        !           359:        /* Increment multiprecision integer r. */
        !           360: 
        !           361: boolean mp_dec(register unitptr r);
        !           362:        /* Decrement multiprecision integer r. */
        !           363: 
        !           364: void mp_neg(register unitptr r);
        !           365:        /* Compute 2's complement, the arithmetic negative, of r */
        !           366: 
        !           367: void mp_move(register unitptr dst,register unitptr src);
        !           368: 
        !           369: void mp_init(register unitptr r, word16 value);
        !           370:        /* Init multiprecision register r with short value. */
        !           371: 
        !           372: short significance(register unitptr r);
        !           373:        /* Returns number of significant units in r */
        !           374: 
        !           375: int mp_udiv(register unitptr remainder,register unitptr quotient,
        !           376:        register unitptr dividend,register unitptr divisor);
        !           377:        /* Unsigned divide, treats both operands as positive. */
        !           378: 
        !           379: int mp_div(register unitptr remainder,register unitptr quotient,
        !           380:        register unitptr dividend,register unitptr divisor);
        !           381:        /* Signed divide, either or both operands may be negative. */
        !           382: 
        !           383: word16 mp_shortdiv(register unitptr quotient,
        !           384:        register unitptr dividend,register word16 divisor);
        !           385:        /* Returns short remainder of unsigned divide. */
        !           386: 
        !           387: int mp_mod(register unitptr remainder,
        !           388:        register unitptr dividend,register unitptr divisor);
        !           389:        /* Unsigned divide, treats both operands as positive. */
        !           390: 
        !           391: word16 mp_shortmod(register unitptr dividend,register word16 divisor);
        !           392:        /* Just returns short remainder of unsigned divide. */
        !           393: 
        !           394: int mp_mult(register unitptr prod,
        !           395:        register unitptr multiplicand,register unitptr multiplier);
        !           396:        /* Computes multiprecision prod = multiplicand * multiplier */
        !           397: 
        !           398: void stage_modulus(unitptr n);
        !           399:        /* Must pass modulus to stage_modulus before calling modmult. */
        !           400: 
        !           401: int mp_modmult(register unitptr prod,
        !           402:        unitptr multiplicand,register unitptr multiplier);
        !           403:        /* Performs combined multiply/modulo operation, with global modulus */
        !           404: 
        !           405: int countbits(unitptr r);
        !           406:        /* Returns number of significant bits in r. */
        !           407: 
        !           408: int mp_modexp(register unitptr expout,register unitptr expin,
        !           409:        register unitptr exponent,register unitptr modulus);
        !           410:        /* Combined exponentiation/modulo algorithm. */
        !           411: 
        !           412: int rsa_decrypt(unitptr M, unitptr C,
        !           413:        unitptr d, unitptr p, unitptr q, unitptr u);
        !           414:        /* Uses Chinese Remainder Theorem shortcut for RSA decryption. */
        !           415: 
        !           416: int mp_sqrt(unitptr quotient,unitptr dividend); 
        !           417:        /* Quotient is returned as the square root of dividend. */
        !           418: 
        !           419: #endif /* not compiling RSALIB */
        !           420: 
        !           421: /****************** end of RSA library ****************************/
        !           422: 

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