home *** CD-ROM | disk | FTP | other *** search
/ Hacker Chronicles 2 / HACKER2.BIN / 1235.RSALIB.H < prev    next >
Text File  |  1991-05-25  |  16KB  |  423 lines
  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.  
  423.