![[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 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.