![[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.1.6 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 dependencies. 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 - Implement new VAX/VMS primitive support.
25: Modified 29 Nov 92 - Thad Smith
26: */
27:
28: #include <string.h>
29: #include "usuals.h" /* typedefs for byte, word16, boolean, etc. */
30: #include "platform.h" /* customization for different environments */
31:
32: /* Platform customization:
33: * A version which runs on almost any computer can be implemented by
34: * defining PORTABLE and MPORTABLE, preferably as a command line
35: * parameter. Faster versions can be generated by specifying specific
36: * parameters, such as size of unit and MULTUNIT, and by supplying some
37: * of the critical in assembly. See the file platform.h for more
38: * details on customization.
39: *
40: * The symbol HIGHFIRST, designating that integers and longs are stored
41: * with the most significant bit in the lowest address, should be defined
42: * on the command line for compiling all files, since it is used by files
43: * other than the mpilib routines.
44: */
45:
46: #ifndef ALIGN
47: #define ALIGN
48: #endif
49:
50: #ifndef PEASANT /* if not Russian peasant modulo multiply algorithm */
51: #ifndef MERRITT /* if not Merritt's modmult */
52: #ifndef UPTON /* if not Upton's modmult */
53: #ifndef SMITH
54: #define SMITH /* default: use Smith's modmult algorithm */
55: #endif
56: #endif
57: #endif
58: #endif
59:
60: #ifdef SMITH
61: #define UPTON_OR_SMITH /* enable common code */
62: #endif
63: #ifdef UPTON
64: #define UPTON_OR_SMITH /* enable common code */
65: #endif
66:
67: #ifndef UNIT32
68: #ifndef UNIT8
69: #define UNIT16 /* default--use 16-bit units */
70: #endif
71: #endif
72:
73: /*** CAUTION: If your machine has an unusual word size that is not a
74: power of 2 (8, 16, 32, or 64) bits wide, then the macros here that
75: use the symbol "LOG_UNITSIZE" must be changed.
76: ***/
77:
78: #ifdef UNIT8
79: typedef unsigned char unit;
80: typedef signed char signedunit;
81: #define UNITSIZE 8 /* number of bits in a unit */
82: #define LOG_UNITSIZE 3
83: #define uppermostbit ((unit) 0x80)
84: #define BYTES_PER_UNIT 1 /* number of bytes in a unit */
85: #define units2bits(n) ((n) << 3) /* fast multiply by UNITSIZE */
86: #define units2bytes(n) (n)
87: #define bits2units(n) (((n)+7) >> 3)
88: #define bytes2units(n) (n)
89: #endif
90:
91: #ifdef UNIT16
92: typedef word16 unit;
93: typedef short signedunit;
94: #define UNITSIZE 16 /* number of bits in a unit */
95: #define LOG_UNITSIZE 4
96: #define uppermostbit ((unit) 0x8000)
97: #define BYTES_PER_UNIT 2 /* number of bytes in a unit */
98: #define units2bits(n) ((n) << 4) /* fast multiply by UNITSIZE */
99: #define units2bytes(n) ((n) << 1)
100: #define bits2units(n) (((n)+15) >> 4)
101: #define bytes2units(n) (((n)+1) >> 1)
102: #endif
103:
104: #ifdef UNIT32
105: typedef word32 unit;
106: typedef long signedunit;
107: #define UNITSIZE 32 /* number of bits in a unit */
108: #define LOG_UNITSIZE 5
109: #define uppermostbit ((unit) 0x80000000L)
110: #define BYTES_PER_UNIT 4 /* number of bytes in a unit */
111: #define units2bits(n) ((n) << 5) /* fast multiply by UNITSIZE */
112: #define units2bytes(n) ((n) << 2)
113: #define bits2units(n) (((n)+31) >> 5)
114: #define bytes2units(n) (((n)+3) >> 2)
115: #endif
116:
117: #define power_of_2(b) ((unit) 1 << (b)) /* computes power-of-2 bit masks */
118: #define bits2bytes(n) (((n)+7) >> 3)
119: /* Some C compilers (like the ADSP2101) will not always collapse constant
1.1.1.7 ! root 120: expressions at compile time if the expressions contain shift
! 121: operators. */
1.1.1.6 root 122: /* #define uppermostbit power_of_2(UNITSIZE-1) */
123: /* #define UNITSIZE units2bits(1) */ /* number of bits in a unit */
124: /* #define bytes2units(n) bits2units((n)<<3) */
125: /* #define BYTES_PER_UNIT (UNITSIZE >> 3) */
126: /* LOG_UNITSIZE is the log base 2 of UNITSIZE, ie: 4 for 16-bit units */
1.1.1.7 ! root 127: /* #define units2bits(n) ((n) << LOG_UNITSIZE) */ /* fast multiply by
! 128: UNITSIZE */
1.1.1.6 root 129: /* #define units2bytes(n) ((n) << (LOG_UNITSIZE-3)) */
130: /* #define bits2units(n) (((n)+(UNITSIZE-1)) >> LOG_UNITSIZE) */
131: /* #define bytes2units(n) (((n)+(BYTES_PER_UNIT-1)) >> (LOG_UNITSIZE-3)) */
132:
133: typedef unit *unitptr;
134:
135:
136: /*--------------------- Byte ordering stuff -------------------*/
137: #ifdef HIGHFIRST
138:
139: /* these definitions assume MSB comes first */
140: #define tohigher(n) (-(n)) /* offset towards higher unit */
141: #define pre_higherunit(r) (--(r))
142: #define pre_lowerunit(r) (++(r))
143: #define post_higherunit(r) ((r)--)
144: #define post_lowerunit(r) ((r)++)
145: #define bit_index(n) (global_precision-bits2units((n)+1))
146: #define lsbptr(r,prec) ((r)+(prec)-1)
147: #define make_lsbptr(r,prec) (r) = lsbptr(r,prec)
148: #define unmake_lsbptr(r,prec) (r) = ((r)-(prec)+1)
149: #define msbptr(r,prec) (r)
150: #define make_msbptr(r,prec) /* (r) = msbptr(r,prec) */
151:
152: /* The macro rescale(r,current_precision,new_precision) rescales
153: a multiprecision integer by adjusting r and its precision to new values.
154: It can be used to reverse the effects of the normalize
155: routine given above. See the comments in normalize concerning
156: Intel vs. Motorola LSB/MSB conventions.
157: WARNING: You can only safely call rescale on registers that
158: you have previously normalized with the above normalize routine,
159: or are known to be big enough for the new precision. You may
160: specify a new precision that is smaller than the current precision.
161: You must be careful not to specify a new_precision value that is
162: too big, or which adjusts the r pointer out of range.
163: */
164: #define rescale(r,currentp,newp) r -= ((newp) - (currentp))
165:
166: /* The macro normalize(r,precision) "normalizes" a multiprecision integer
167: by adjusting r and precision to new values. For Motorola-style processors
168: (MSB-first), r is a pointer to the MSB of the register, and must
169: be adjusted to point to the first nonzero unit. For Intel/VAX-style
170: (LSB-first) processors, r is a pointer to the LSB of the register,
171: and must be left unchanged. The precision counter is always adjusted,
172: regardless of processor type. In the case of precision = 0,
173: r becomes undefined.
174: */
175: #define normalize(r,prec) \
176: { prec = significance(r); r += (global_precision-(prec)); }
177:
178: #else /* LOWFIRST byte order */
179:
180: /* these definitions assume LSB comes first */
181: #define tohigher(n) (n) /* offset towards higher unit */
182: #define pre_higherunit(r) (++(r))
183: #define pre_lowerunit(r) (--(r))
184: #define post_higherunit(r) ((r)++)
185: #define post_lowerunit(r) ((r)--)
186: #define bit_index(n) (bits2units((n)+1)-1)
187: #define lsbptr(r,prec) (r)
188: #define make_lsbptr(r,prec) /* (r) = lsbptr(r,prec) */
189: #define unmake_lsbptr(r,prec) /* (r) = (r) */
190: #define msbptr(r,prec) ((r)+(prec)-1)
191: #define make_msbptr(r,prec) (r) = msbptr(r,prec)
192:
193: #define rescale(r,currentp,newp) /* nil statement */
194: #define normalize(r,prec) prec = significance(r)
195:
196: #endif /* LOWFIRST byte order */
197: /*------------------ End byte ordering stuff -------------------*/
198:
199: /* Note that the address calculations require that lsbptr, msbptr,
200: make_lsbptr, make_msbptr, mp_tstbit, mp_setbit, mp_clrbit,
1.1.1.7 ! root 201: and bitptr all have unitptr arguments, not byte pointer arguments.
! 202: */
1.1.1.6 root 203: #define bitptr(r,n) &((r)[bit_index(n)])
204: #define bitmsk(n) power_of_2((n) & (UNITSIZE-1))
205: /* bitmsk() assumes UNITSIZE is a power of 2 */
206: #define mp_tstbit(r,n) (*bitptr(r,n) & bitmsk(n))
207: #define mp_setbit(r,n) (*bitptr(r,n) |= bitmsk(n))
208: #define mp_clrbit(r,n) (*bitptr(r,n) &= ~bitmsk(n))
209: #define msunit(r) (*msbptr(r,global_precision))
210: #define lsunit(r) (*lsbptr(r,global_precision))
211: /* #define mp_tstminus(r) ((msunit(r) & uppermostbit)!=0) */
212: #define mp_tstminus(r) ((signedunit) msunit(r) < 0)
213:
214:
215: /* set working precision to specified number of bits. */
216: #ifdef mp_setp
217: void mp_setp(short nbits);
218: #define set_precision(prec) mp_setp(units2bits(global_precision=(prec)))
219: #else
220: #define set_precision(prec) (global_precision = (prec))
221: #endif
222:
223:
224: #ifdef PEASANT
225:
226: /* Define C names for Russian peasant modmult primitives. */
227: #define stage_modulus stage_peasant_modulus
228: #define mp_modmult peasant_modmult
229: #define modmult_burn peasant_burn
230: #define SLOP_BITS PEASANT_SLOP_BITS
231:
232: #else /* not PEASANT */
233: #ifdef MERRITT
234: /* Define C names for Merritt's modmult primitives. */
235: #define stage_modulus stage_merritt_modulus
236: #define mp_modmult merritt_modmult
237: #define modmult_burn merritt_burn
238: #define SLOP_BITS MERRITT_SLOP_BITS
239:
240: #else /* not PEASANT, MERRITT */
241: #ifdef UPTON
242: /* Define C names for Upton's modmult primitives. */
243: #define stage_modulus stage_upton_modulus
244: #define mp_modmult upton_modmult
245: #define modmult_burn upton_burn
246: #define SLOP_BITS UPTON_SLOP_BITS
247:
248: #else /* not PEASANT, MERRITT, UPTON */
249: #ifdef SMITH
250: /* Define C names for Smith's modmult primitives. */
251: #define stage_modulus stage_smith_modulus
252: #define mp_modmult smith_modmult
253: #define modmult_burn smith_burn
254: #define SLOP_BITS SMITH_SLOP_BITS
255:
256: #endif /* SMITH */
257: #endif /* UPTON */
258: #endif /* MERRITT */
259: #endif /* PEASANT */
260:
261:
262: #define mp_shift_left(r1) mp_rotate_left(r1,(boolean)0)
263: /* multiprecision shift left 1 bit */
264:
265: #define mp_add(r1,r2) mp_addc(r1,r2,(boolean)0)
266: /* multiprecision add with no carry */
267:
268: #define mp_sub(r1,r2) mp_subb(r1,r2,(boolean)0)
269: /* multiprecision subtract with no borrow */
270:
271: #define mp_abs(r) (mp_tstminus(r) ? (mp_neg(r),TRUE) : FALSE)
272:
273: #define msub(r,m) if (mp_compare(r,m) >= 0) mp_sub(r,m)
274: /* Prevents r from getting bigger than modulus m */
275:
276: #define testeq(r,i) \
277: ( (lsunit(r)==(i)) && (significance(r)<=1) )
278:
279: #define testne(r,i) \
280: ( (lsunit(r)!=(i)) || (significance(r)>1) )
281:
282: #define testge(r,i) \
283: ( (lsunit(r)>=(i)) || (significance(r)>1) )
284:
285: #define testle(r,i) \
286: ( (lsunit(r)<=(i)) && (significance(r)<=1) )
287:
288: #define mp_square(r1,r2) mp_mult(r1,r2,r2)
289: /* Square r2, returning product in r1 */
290:
291: #define mp_modsquare(r1,r2) mp_modmult(r1,r2,r2)
292: /* Square r2, returning modulo'ed product in r1 */
293:
294: #define countbytes(r) ((countbits(r)+7)>>3)
295:
296: /* SLOP_BITS is how many "carry bits" to allow for intermediate
297: calculation results to exceed the size of the modulus.
298: It is used by modexp to give some overflow elbow room for
299: modmult to use to perform modulo operations with the modulus.
300: The number of slop bits required is determined by the modmult
301: algorithm. The Russian peasant modmult algorithm only requires
302: 1 slop bit, for example. Note that if we use an external assembly
303: modmult routine, SLOP_BITS may be meaningless or may be defined in a
304: non-constant manner.
305: */
306: #define PEASANT_SLOP_BITS 1
307: #define MERRITT_SLOP_BITS UNITSIZE
308: #define UPTON_SLOP_BITS (UNITSIZE/2)
309: #ifdef mp_smul /* old version requires MS word = 0 */
310: #define SMITH_SLOP_BITS UNITSIZE
311: #else /* mp_smula or C version of mp_smul */
312: #define SMITH_SLOP_BITS 0
313: #endif /* mp_smul */
314:
315: /* MAX_BIT_PRECISION is upper limit that assembly primitives can handle.
316: It must be less than 32704 bits, or 4088 bytes. It should be an
317: integer multiple of UNITSIZE*2.
318: */
319: #if (SLOP_BITS > 0)
320: #define MAX_BIT_PRECISION (1280+(2*UNITSIZE))
321: #else
322: #define MAX_BIT_PRECISION 1280
323: #endif
324: #define MAX_BYTE_PRECISION (MAX_BIT_PRECISION/8)
325: #define MAX_UNIT_PRECISION (MAX_BIT_PRECISION/UNITSIZE)
326:
327:
328: /* global_precision is the unit precision last set by set_precision */
329: extern short global_precision;
330:
331:
332: /* The "bit sniffer" macros all begin sniffing at the MSB.
333: They are used internally by all the various multiply, divide,
334: modulo, exponentiation, and square root functions.
335: */
336: #define sniff_bit(bptr,bitmask) (*(bptr) & bitmask)
337:
338: #define init_bitsniffer(bptr,bitmask,prec,bits) \
339: { normalize(bptr,prec); \
340: if (!prec) \
341: return(0); \
342: bits = units2bits(prec); \
343: make_msbptr(bptr,prec); bitmask = uppermostbit; \
344: while (!sniff_bit(bptr,bitmask)) \
345: { bitmask >>= 1; bits--; \
346: } \
347: }
348:
349: #define bump_bitsniffer(bptr,bitmask) \
350: { if (!(bitmask >>= 1)) \
351: { bitmask = uppermostbit; \
352: post_lowerunit(bptr); \
353: } \
354: }
355:
356: /* bump_2bitsniffers is used internally by mp_udiv. */
357: #define bump_2bitsniffers(bptr,bptr2,bitmask) \
358: { if (!(bitmask >>= 1)) \
359: { bitmask = uppermostbit; \
360: post_lowerunit(bptr); \
361: post_lowerunit(bptr2); \
362: } \
363: }
364:
365: /* stuff_bit is used internally by mp_udiv and mp_sqrt. */
366: #define stuff_bit(bptr,bitmask) *(bptr) |= bitmask
367:
368:
369: boolean mp_addc
370: (register unitptr r1,register unitptr r2,register boolean carry);
371: /* multiprecision add with carry r2 to r1, result in r1 */
372:
373: boolean mp_subb
374: (register unitptr r1,register unitptr r2,register boolean borrow);
375: /* multiprecision subtract with borrow, r2 from r1, result in r1 */
376:
377: boolean mp_rotate_left(register unitptr r1,register boolean carry);
378: /* multiprecision rotate left 1 bit with carry, result in r1. */
379:
380: void mp_shift_right_bits(register unitptr r1,register short bits);
381: /* multiprecision shift right bits, result in r1. */
382:
383: short mp_compare(register unitptr r1,register unitptr r2);
384: /* Compares registers *r1, *r2, and returns -1, 0, or 1 */
385:
386: boolean mp_inc(register unitptr r);
387: /* Increment multiprecision integer r. */
388:
389: boolean mp_dec(register unitptr r);
390: /* Decrement multiprecision integer r. */
391:
392: void mp_neg(register unitptr r);
393: /* Compute 2's complement, the arithmetic negative, of r */
394:
395: #ifndef mp_move
396: #define mp_move(d,s) memcpy((void*)(d), (void*)(s), \
397: units2bytes(global_precision))
398: #endif
399: #ifndef unitfill0
400: #define unitfill0(r,ct) memset((void*)(r), 0, units2bytes(ct))
401: #endif
402:
403: #ifndef mp_burn
404: #define mp_burn(r) mp_init(r,0) /* for burning the evidence */
405: #define mp_init0(r) mp_init(r,0)
406: #endif
407:
408: #define empty_array(r) unitfill0(r, sizeof(r)/sizeof(r[0])/sizeof(unit))
409:
410: void mp_init(register unitptr r, word16 value);
411: /* Init multiprecision register r with short value. */
412:
413: short significance(register unitptr r);
414: /* Returns number of significant units in r */
415:
416: int mp_udiv(register unitptr remainder,register unitptr quotient,
417: register unitptr dividend,register unitptr divisor);
418: /* Unsigned divide, treats both operands as positive. */
419:
420: int mp_recip(register unitptr quotient,register unitptr divisor);
421: /* Compute reciprocal as 1/divisor. Used by faster modmult. */
422:
423: int mp_div(register unitptr remainder,register unitptr quotient,
424: register unitptr dividend,register unitptr divisor);
425: /* Signed divide, either or both operands may be negative. */
426:
427: word16 mp_shortdiv(register unitptr quotient,
428: register unitptr dividend,register word16 divisor);
429: /* Returns short remainder of unsigned divide. */
430:
431: int mp_mod(register unitptr remainder,
432: register unitptr dividend,register unitptr divisor);
433: /* Unsigned divide, treats both operands as positive. */
434:
435: word16 mp_shortmod(register unitptr dividend,register word16 divisor);
436: /* Just returns short remainder of unsigned divide. */
437:
438: int mp_mult(register unitptr prod,
439: register unitptr multiplicand,register unitptr multiplier);
440: /* Computes multiprecision prod = multiplicand * multiplier */
441:
442: int countbits(unitptr r);
443: /* Returns number of significant bits in r. */
444:
445: int stage_peasant_modulus(unitptr n);
446: int stage_merritt_modulus(unitptr n);
447: int stage_upton_modulus(unitptr n);
448: int stage_smith_modulus(unitptr n);
449: /* Must pass modulus to stage_modulus before calling modmult. */
450:
451: int peasant_modmult(register unitptr prod,
452: unitptr multiplicand,register unitptr multiplier);
453: int merritt_modmult(register unitptr prod,
454: unitptr multiplicand,register unitptr multiplier);
455: int upton_modmult(register unitptr prod,
456: unitptr multiplicand,register unitptr multiplier);
457: int smith_modmult(register unitptr prod,
458: unitptr multiplicand,register unitptr multiplier);
459: /* Performs combined multiply/modulo operation, with global modulus */
460:
461:
462:
463: int mp_modexp(register unitptr expout,register unitptr expin,
464: register unitptr exponent,register unitptr modulus);
465: /* Combined exponentiation/modulo algorithm. */
466:
467: int mp_modexp_crt(unitptr expout, unitptr expin,
468: unitptr p, unitptr q, unitptr ep, unitptr eq, unitptr u);
469: /* exponentiation and modulo using Chinese Remainder Theorem */
470:
471: /****************** end of MPI library ****************************/
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.