![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to rsalib.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [PGP] / pgp / src|
Return to rsalib.h CVS log | Up to [PGP] / pgp / src |
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.