![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to mpiio.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [PGP] / pgp / src|
Return to mpiio.c CVS log | Up to [PGP] / pgp / src |
1.1.1.2 root 1: /* mpiio.c - C source code for multiprecision integer I/O routines.
2: Implemented Nov 86 by Philip Zimmermann
3: Last revised 13 Sep 91 by PRZ
4:
5: Boulder Software Engineering
6: 3021 Eleventh Street
7: Boulder, CO 80304
8: (303) 541-0140
9:
10: (c) Copyright 1986-92 by Philip Zimmermann. All rights reserved.
11: The author assumes no liability for damages resulting from the use
12: of this software, even if the damage results from defects in this
13: software. No warranty is expressed or implied.
14:
15: These routines are for multiprecision arithmetic I/O functions for
16: number-theoretic cryptographic algorithms such as ElGamal,
17: Diffie-Hellman, Rabin, or factoring studies for large composite
18: numbers, as well as Rivest-Shamir-Adleman (RSA) public key
19: cryptography.
20:
21: The external data representation for RSA messages and keys that
22: some of these library routines assume is outlined in a paper by
23: Philip Zimmermann, "A Proposed Standard Format for RSA Cryptosystems",
24: IEEE Computer, September 1986, Vol. 19 No. 9, pages 21-34.
25: Some revisions to this data format have occurred since the paper
26: was published.
27: */
28:
29: /* #define DEBUG */
30:
31:
32: #ifndef EMBEDDED /* not EMBEDDED - not compiling for embedded target */
33: #include <stdio.h> /* for printf, etc. */
34: #else /* EMBEDDED - compiling for embedded target */
1.1.1.4 ! root 35: #define NULL (VOID *)0
1.1.1.2 root 36: #endif
37:
38: #include "mpilib.h"
39: #include "mpiio.h"
40: #include "pgp.h"
41:
1.1.1.3 root 42: static void puthexbyte(byte b); /* Put out byte in ASCII hex via putchar. */
43: static
44: void puthexw16(word16 w); /* Put out 16-bit word in hex, high byte first. */
45: static
46: void putstr(string s); /* Put out null-terminated ASCII string via putchar. */
1.1.1.2 root 47:
48: /*----------------- Following procedures relate to I/O ------------------*/
49:
50: int string_length(char *s)
51: /* Returns string length, just like strlen() from <string.h> */
52: { int i;
53: i = 0;
54: if (s != NULL)
55: while (*s++) i++;
56: return (i);
57: } /* string_length */
58:
59:
60: #ifdef DEBUG
61: static int ctox(int c)
62: /* Returns integer 0-15 if c is an ASCII hex digit, -1 otherwise. */
63: { if ((c >= '0') && (c <= '9'))
64: return(c - '0');
65: if ((c >= 'a') && (c <= 'f'))
66: return((c - 'a') + 10);
67: if ((c >= 'A') && (c <= 'F'))
68: return((c - 'A') + 10);
69: return(-1); /* error -- not a hex digit */
70: } /* ctox */
71:
72:
73: int str2reg(unitptr reg,string digitstr)
74: /* Converts a possibly-signed digit string into a large binary number.
75: Returns assumed radix, derived from suffix 'h','o',b','.' */
76: { unit temp[MAX_UNIT_PRECISION],base[MAX_UNIT_PRECISION];
77: int c,i;
78: boolean minus = FALSE;
79: short radix; /* base 2-16 */
80:
81: mp_init(reg,0);
82:
83: i = string_length(digitstr);
84: if (i==0) return(10); /* empty string, assume radix 10 */
85: c = digitstr[i-1]; /* get last char in string */
86:
87: switch (c) /* classify radix select suffix character */
88: {
89: case '.': radix = 10;
90: break;
91: case 'H':
92: case 'h': radix = 16;
93: break;
94: case 'O':
95: case 'o': radix = 8;
96: break;
97: case 'B':
98: case 'b': radix = 2; /* caution! 'b' is a hex digit! */
99: break;
100: default: radix = 10;
101: }
102:
103: mp_init(base,radix);
104: if ((minus = (*digitstr == '-')) != 0) digitstr++;
105: while ((c = *digitstr++) != 0)
106: { if (c==',') continue; /* allow commas in number */
107: c = ctox(c);
108: if ((c < 0) || (c >= radix))
109: break; /* scan terminated by any non-digit */
110: mp_mult(temp,reg,base);
111: mp_move(reg,temp);
112: mp_init(temp,c);
113: mp_add(reg,temp);
114: }
115: if (minus) mp_neg(reg);
116: return(radix);
117: } /* str2reg */
118:
119: #endif /* DEBUG */
120:
121: /* These I/O functions, such as putstr, puthexbyte, and puthexw16,
122: are provided here to avoid the need to link in printf from the
123: C I/O library. This is handy in an embedded application.
124: For embedded applications, use a customized putchar function,
125: separately compiled.
126: */
127:
1.1.1.3 root 128: static void putstr(string s)
1.1.1.2 root 129: /* Put out null-terminated ASCII string via putchar. */
130: { while (*s) putchar(*s++);
131: } /* putstr */
132:
1.1.1.3 root 133: static void puthexbyte(byte b)
1.1.1.2 root 134: /* Put out byte in ASCII hex via putchar. */
135: { static char *nibs = "0123456789ABCDEF";
136: putchar(nibs[b >> 4]);
137: putchar(nibs[b & 0x0F]);
138: } /* puthexbyte */
139:
1.1.1.3 root 140: static void puthexw16(word16 w)
1.1.1.2 root 141: /* Put out 16-bit word in hex, high byte first. */
142: { puthexbyte((byte)(w >> 8));
143: puthexbyte((byte)(w & 0xFF));
144: } /* puthexw16 */
145:
146: #ifdef UNIT32
147: static void puthexw32(word32 lw)
148: /* Puts out 32-bit word in hex, high byte first. */
149: { puthexw16((word16)(lw>>16));
150: puthexw16((word16)(lw & 0xFFFFL));
151: } /* puthexw32 */
152: #endif /* UNIT32 */
153:
154:
155: #ifdef UNIT8
156: #define puthexunit(u) puthexbyte(u)
157: #endif
158: #ifdef UNIT16
159: #define puthexunit(u) puthexw16(u)
160: #endif
161: #ifdef UNIT32
162: #define puthexunit(u) puthexw32(u)
163: #endif
164:
165: #ifdef DEBUG
166: int display_in_base(string s,unitptr n,short radix)
167: /* Display n in any base, such as base 10. Returns number of digits. */
168: /* s is string to label the displayed register.
169: n is multiprecision integer.
170: radix is base, 2-16.
171: */
172: {
173: char buf[MAX_BIT_PRECISION + (MAX_BIT_PRECISION/8) + 2];
174: unit r[MAX_UNIT_PRECISION],quotient[MAX_UNIT_PRECISION];
175: word16 remainder;
176: char *bp = buf;
177: char minus = FALSE;
178: int places = 0;
179: int commaplaces; /* put commas this many digits apart */
180: int i;
181:
182: /* If string s is just an ESC char, don't print it.
183: It's just to inhibit the \n at the end of the number.
184: */
185: if ((s[0] != '\033') || (s[1] != '\0'))
186: putstr(s);
187:
188: if ( (radix < 2) || (radix > 16) )
189: { putstr("****\n"); /* radix out of range -- show error */
190: return(-1);
191: }
192: commaplaces = (radix==10 ? 3 : (radix==16 ? 4 :
193: (radix==2 ? 8 : (radix==8 ? 8 : 1))));
194: mp_move(r,n);
195: if ((radix == 10) && mp_tstminus(r))
196: { minus = TRUE;
197: mp_neg(r); /* make r positive */
198: }
199:
200: *bp = '\0';
201: do /* build backwards number string */
202: { if (++places>1)
203: if ((places % commaplaces)==1)
204: *++bp = ','; /* 000,000,000,000 */
205: remainder = mp_shortdiv(quotient,r,radix);
206: *++bp = "0123456789ABCDEF" [remainder]; /* Isn't C wonderful? */
207: mp_move(r,quotient);
208: } while (testne(r,0));
209: if (minus)
210: *++bp = '-';
211:
212: if (commaplaces!=1)
213: while ((++places % commaplaces) != 1)
214: *++bp = ' '; /* pad to line up commas */
215:
216: i = string_length(s);
217: while (*bp)
218: { putchar(*bp);
219: ++i;
220: if ((*bp == ',') || commaplaces==1)
221: if (i > (72-commaplaces))
222: { putchar('\n');
223: i=string_length(s);
224: while (i--) putchar(' ');
225: i = string_length(s);
226: }
227: bp--;
228: }
229: switch (radix)
230: { /* show suffix character to designate radix */
231: case 10: /* decimal */
232: putchar('.');
233: break;
234: case 16: /* hex */
235: putchar('h');
236: break;
237: case 8: /* octal */
238: putchar('o');
239: break;
240: case 2: /* binary */
241: putchar('b');
242: break;
243: default: /* nonstandard radix */
244: /* printf("(%d)",radix); */ ;
245: }
246:
247: if ((s[0] == '\033') && (s[1] == '\0'))
248: putchar(' '); /* supress newline */
249: else putchar('\n');
250:
251: fill0((byteptr)buf,sizeof(buf)); /* burn the evidence on the stack...*/
252: /* Note that local stack arrays r and quotient are now 0 */
253: return(places);
254: } /* display_in_base */
255:
256: #endif /* DEBUG */
257:
258: void mp_display(string s,unitptr r)
259: /* Display register r in hex, with prefix string s. */
260: { short precision;
261: int i,j;
262: putstr(s);
263: normalize(r,precision); /* strip off leading zeros */
264: if (precision == 0)
265: { putstr(" 0\n");
266: return;
267: }
268: make_msbptr(r,precision);
269: i=0;
270: while (precision--)
271: { if (!(i++ % (16/BYTES_PER_UNIT)))
272: { if (i>1)
273: { putchar('\n');
274: j=string_length(s);
275: while (j--) putchar(' ');
276: }
277: }
278: puthexunit(*r);
279: putchar(' ');
280: post_lowerunit(r);
281: }
282: putchar('\n');
283: } /* mp_display */
284:
285:
286: word16 checksum(register byteptr buf, register word16 count)
287: /* Returns checksum of buffer. */
288: { word16 cs;
289: cs = 0;
290: while (count--) cs += *buf++;
291: return(cs);
292: } /* checksum */
293:
294:
295: void cbc_xor(register unitptr dst, register unitptr src, word16 bytecount)
296: /* Performs the XOR necessary for RSA Cipher Block Chaining.
297: The dst buffer ought to have 1 less byte of significance than
298: the src buffer. Only the least significant part of the src
299: buffer is used. bytecount is the size of a plaintext block.
300: */
301: { short nunits; /* units of precision */
302: nunits = bytes2units(bytecount)-1;
303: make_lsbptr(dst,global_precision);
304: while (nunits--)
305: { *dst ^= *post_higherunit(src);
306: post_higherunit(dst);
307: bytecount -= units2bytes(1);
308: }
309: /* on the last unit, don't xor the excess top byte... */
310: *dst ^= (*src & (power_of_2(bytecount<<3)-1));
311: } /* cbc_xor */
312:
313:
314: void hiloswap(byteptr r1,short numbytes)
315: /* Reverses the order of bytes in an array of bytes. */
316: { byteptr r2;
317: byte b;
318: r2 = &(r1[numbytes-1]);
319: while (r1 < r2)
320: { b = *r1; *r1++ = *r2; *r2-- = b;
321: }
322: } /* hiloswap */
323:
324:
325: #define byteglue(lo,hi) ((((word16) hi) << 8) + (word16) lo)
326:
327: /**** The following functions must be changed if the external byteorder
328: changes for integers in PGP packet data.
329: ****/
330:
331:
332: word16 fetch_word16(byte *buf)
333: /* Fetches a 16-bit word from where byte pointer is pointing.
334: buf points to external-format byteorder array.
335: */
336: { word16 w0,w1;
1.1.1.3 root 337: /* Assume MSB external byte ordering */
1.1.1.2 root 338: w1 = *buf++;
339: w0 = *buf++;
340: return(w0 + (w1<<8));
341: } /* fetch_word16 */
342:
343:
344: byte *put_word16(word16 w, byte *buf)
345: /* Puts a 16-bit word to where byte pointer is pointing, and
346: returns updated byte pointer.
347: buf points to external-format byteorder array.
348: */
349: {
1.1.1.3 root 350: /* Assume MSB external byte ordering */
1.1.1.2 root 351: buf[1] = w & 0xff;
352: w = w>>8;
353: buf[0] = w & 0xff;
354: return(buf+2);
355: } /* put_word16 */
356:
357:
358: word32 fetch_word32(byte *buf)
359: /* Fetches a 32-bit word from where byte pointer is pointing.
360: buf points to external-format byteorder array.
361: */
362: { word32 w0,w1,w2,w3;
1.1.1.3 root 363: /* Assume MSB external byte ordering */
1.1.1.2 root 364: w3 = *buf++;
365: w2 = *buf++;
366: w1 = *buf++;
367: w0 = *buf++;
368: return(w0 + (w1<<8) + (w2<<16) + (w3<<24));
369: } /* fetch_word32 */
370:
371:
372: byte *put_word32(word32 w, byte *buf)
373: /* Puts a 32-bit word to where byte pointer is pointing, and
374: returns updated byte pointer.
375: buf points to external-format byteorder array.
376: */
377: {
1.1.1.3 root 378: /* Assume MSB external byte ordering */
1.1.1.2 root 379: buf[3] = w & 0xff;
380: w = w>>8;
381: buf[2] = w & 0xff;
382: w = w>>8;
383: buf[1] = w & 0xff;
384: w = w>>8;
385: buf[0] = w & 0xff;
386: return(buf+4);
387: } /* put_word32 */
388:
389:
390: /*** End of functions that must be changed if the external byteorder
391: changes for integer fields in PGP packets.
392: ***/
393:
394:
395:
396:
397: short mpi2reg(register unitptr r,register byteptr buf)
398: /* Converts a multiprecision integer from the externally-represented
399: form of a byte array with a 16-bit bitcount in a leading length
400: word to the internally-used representation as a unit array.
401: Converts to INTERNAL byte order.
402: The same buffer address may be used for both r and buf.
403: Returns number of units in result, or returns -1 on error.
404: */
405: { byte buf2[MAX_BYTE_PRECISION];
406: word16 bitcount, bytecount, unitcount, zero_bytes, i;
407:
408: /* First, extract 16-bit bitcount prefix from first 2 bytes... */
409: bitcount = fetch_word16(buf);
410: buf += 2;
411:
412: /* Convert bitcount to bytecount and unitcount... */
413: bytecount = bits2bytes(bitcount);
414: unitcount = bytes2units(bytecount);
415: if (unitcount > global_precision)
416: { /* precision overflow during conversion. */
417: return(-1); /* precision overflow -- error return */
418: }
419: zero_bytes = units2bytes(global_precision) - bytecount;
1.1.1.3 root 420: /* Assume MSB external byte ordering */
1.1.1.2 root 421: fill0(buf2,zero_bytes); /* fill leading zero bytes */
422: i = zero_bytes; /* assumes MSB first */
423: while (bytecount--) buf2[i++] = *buf++;
424:
425: mp_convert_order(buf2); /* convert to INTERNAL byte order */
426: mp_move(r,(unitptr)buf2);
427: mp_burn((unitptr)buf2); /* burn the evidence on the stack */
428: return(unitcount); /* returns unitcount of reg */
429: } /* mpi2reg */
430:
431:
432: short reg2mpi(register byteptr buf,register unitptr r)
433: /* Converts the multiprecision integer r from the internal form of
434: a unit array to the normalized externally-represented form of a
435: byte array with a leading 16-bit bitcount word in buf[0] and buf[1].
436: This bitcount length prefix is exact count, not rounded up.
437: Converts to EXTERNAL byte order.
438: The same buffer address may be used for both r and buf.
439: Returns the number of bytes of the result, not counting length prefix.
440: */
441: { byte buf1[MAX_BYTE_PRECISION];
442: byteptr buf2;
443: short bytecount,bc;
444: word16 bitcount;
445: bitcount = countbits(r);
446: #ifdef DEBUG
447: if (bitcount > MAX_BIT_PRECISION)
448: { fprintf(stderr, "reg2mpi: bitcount out of range (%d)\n", bitcount);
449: return 0;
450: }
451: #endif
452: bytecount = bits2bytes(bitcount);
453: bc = bytecount; /* save bytecount for return */
454: buf2 = buf1;
455: mp_move((unitptr)buf2,r);
456: mp_convert_order(buf2); /* convert to EXTERNAL byteorder */
1.1.1.3 root 457: /* Assume MSB external byte ordering */
1.1.1.2 root 458: buf2 += units2bytes(global_precision) - bytecount;
459: buf = put_word16(bitcount, buf); /* store bitcount in external byteorder */
460:
461: while (bytecount--) *buf++ = *buf2++;
462:
463: mp_burn((unitptr)buf1); /* burn the evidence on the stack */
464: return(bc); /* returns bytecount of mpi, not counting prefix */
465: } /* reg2mpi */
466:
467:
468: #ifdef DEBUG
469:
470: void dumpbuf(string s, byteptr buf, int bytecount)
471: /* Dump buffer in hex, with string label prefix. */
472: { putstr(s);
473: while (bytecount--)
474: { puthexbyte(*buf++);
475: putchar(' ');
476: if ((bytecount & 0x0f)==0)
477: putchar('\n');
478: }
479: } /* dumpbuf */
480:
481: void dump_unit_array(string s, unitptr r)
482: /* Dump unit array r as a C array initializer, with string label prefix.
483: Array is dumped in native unit order.
484: */
485: { int unitcount;
486: unitcount = global_precision;
487: putstr(s);
488: putstr("\n{ ");
489: while (unitcount--)
490: { putstr("0x");
491: puthexunit(*r++);
492: putchar(',');
493: if (unitcount && ((unitcount & 0x07)==0))
494: putstr("\n ");
495: }
496: putstr(" 0};\n");
497: } /* dump_unit_array */
498:
499: #endif /* ifdef DEBUG */
500:
1.1.1.3 root 501: /************ end of multiprecision integer I/O library *****************/
1.1.1.2 root 502:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.