![[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 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 */
35: #define NULL (void *)0
36: #endif
37:
38: #include "mpilib.h"
39: #include "mpiio.h"
40: #include "pgp.h"
41:
42:
43: /*----------------- Following procedures relate to I/O ------------------*/
44:
45: int string_length(char *s)
46: /* Returns string length, just like strlen() from <string.h> */
47: { int i;
48: i = 0;
49: if (s != NULL)
50: while (*s++) i++;
51: return (i);
52: } /* string_length */
53:
54:
55: #ifdef DEBUG
56: static int ctox(int c)
57: /* Returns integer 0-15 if c is an ASCII hex digit, -1 otherwise. */
58: { if ((c >= '0') && (c <= '9'))
59: return(c - '0');
60: if ((c >= 'a') && (c <= 'f'))
61: return((c - 'a') + 10);
62: if ((c >= 'A') && (c <= 'F'))
63: return((c - 'A') + 10);
64: return(-1); /* error -- not a hex digit */
65: } /* ctox */
66:
67:
68: int str2reg(unitptr reg,string digitstr)
69: /* Converts a possibly-signed digit string into a large binary number.
70: Returns assumed radix, derived from suffix 'h','o',b','.' */
71: { unit temp[MAX_UNIT_PRECISION],base[MAX_UNIT_PRECISION];
72: int c,i;
73: boolean minus = FALSE;
74: short radix; /* base 2-16 */
75:
76: mp_init(reg,0);
77:
78: i = string_length(digitstr);
79: if (i==0) return(10); /* empty string, assume radix 10 */
80: c = digitstr[i-1]; /* get last char in string */
81:
82: switch (c) /* classify radix select suffix character */
83: {
84: case '.': radix = 10;
85: break;
86: case 'H':
87: case 'h': radix = 16;
88: break;
89: case 'O':
90: case 'o': radix = 8;
91: break;
92: case 'B':
93: case 'b': radix = 2; /* caution! 'b' is a hex digit! */
94: break;
95: default: radix = 10;
96: }
97:
98: mp_init(base,radix);
99: if ((minus = (*digitstr == '-')) != 0) digitstr++;
100: while ((c = *digitstr++) != 0)
101: { if (c==',') continue; /* allow commas in number */
102: c = ctox(c);
103: if ((c < 0) || (c >= radix))
104: break; /* scan terminated by any non-digit */
105: mp_mult(temp,reg,base);
106: mp_move(reg,temp);
107: mp_init(temp,c);
108: mp_add(reg,temp);
109: }
110: if (minus) mp_neg(reg);
111: return(radix);
112: } /* str2reg */
113:
114: #endif /* DEBUG */
115:
116: /* These I/O functions, such as putstr, puthexbyte, and puthexw16,
117: are provided here to avoid the need to link in printf from the
118: C I/O library. This is handy in an embedded application.
119: For embedded applications, use a customized putchar function,
120: separately compiled.
121: */
122:
123: void putstr(string s)
124: /* Put out null-terminated ASCII string via putchar. */
125: { while (*s) putchar(*s++);
126: } /* putstr */
127:
128: void puthexbyte(byte b)
129: /* Put out byte in ASCII hex via putchar. */
130: { static char *nibs = "0123456789ABCDEF";
131: putchar(nibs[b >> 4]);
132: putchar(nibs[b & 0x0F]);
133: } /* puthexbyte */
134:
135: void puthexw16(word16 w)
136: /* Put out 16-bit word in hex, high byte first. */
137: { puthexbyte((byte)(w >> 8));
138: puthexbyte((byte)(w & 0xFF));
139: } /* puthexw16 */
140:
141: #ifdef UNIT32
142: static void puthexw32(word32 lw)
143: /* Puts out 32-bit word in hex, high byte first. */
144: { puthexw16((word16)(lw>>16));
145: puthexw16((word16)(lw & 0xFFFFL));
146: } /* puthexw32 */
147: #endif /* UNIT32 */
148:
149:
150: #ifdef UNIT8
151: #define puthexunit(u) puthexbyte(u)
152: #endif
153: #ifdef UNIT16
154: #define puthexunit(u) puthexw16(u)
155: #endif
156: #ifdef UNIT32
157: #define puthexunit(u) puthexw32(u)
158: #endif
159:
160: #ifdef DEBUG
161: int display_in_base(string s,unitptr n,short radix)
162: /* Display n in any base, such as base 10. Returns number of digits. */
163: /* s is string to label the displayed register.
164: n is multiprecision integer.
165: radix is base, 2-16.
166: */
167: {
168: char buf[MAX_BIT_PRECISION + (MAX_BIT_PRECISION/8) + 2];
169: unit r[MAX_UNIT_PRECISION],quotient[MAX_UNIT_PRECISION];
170: word16 remainder;
171: char *bp = buf;
172: char minus = FALSE;
173: int places = 0;
174: int commaplaces; /* put commas this many digits apart */
175: int i;
176:
177: /* If string s is just an ESC char, don't print it.
178: It's just to inhibit the \n at the end of the number.
179: */
180: if ((s[0] != '\033') || (s[1] != '\0'))
181: putstr(s);
182:
183: if ( (radix < 2) || (radix > 16) )
184: { putstr("****\n"); /* radix out of range -- show error */
185: return(-1);
186: }
187: commaplaces = (radix==10 ? 3 : (radix==16 ? 4 :
188: (radix==2 ? 8 : (radix==8 ? 8 : 1))));
189: mp_move(r,n);
190: if ((radix == 10) && mp_tstminus(r))
191: { minus = TRUE;
192: mp_neg(r); /* make r positive */
193: }
194:
195: *bp = '\0';
196: do /* build backwards number string */
197: { if (++places>1)
198: if ((places % commaplaces)==1)
199: *++bp = ','; /* 000,000,000,000 */
200: remainder = mp_shortdiv(quotient,r,radix);
201: *++bp = "0123456789ABCDEF" [remainder]; /* Isn't C wonderful? */
202: mp_move(r,quotient);
203: } while (testne(r,0));
204: if (minus)
205: *++bp = '-';
206:
207: if (commaplaces!=1)
208: while ((++places % commaplaces) != 1)
209: *++bp = ' '; /* pad to line up commas */
210:
211: i = string_length(s);
212: while (*bp)
213: { putchar(*bp);
214: ++i;
215: if ((*bp == ',') || commaplaces==1)
216: if (i > (72-commaplaces))
217: { putchar('\n');
218: i=string_length(s);
219: while (i--) putchar(' ');
220: i = string_length(s);
221: }
222: bp--;
223: }
224: switch (radix)
225: { /* show suffix character to designate radix */
226: case 10: /* decimal */
227: putchar('.');
228: break;
229: case 16: /* hex */
230: putchar('h');
231: break;
232: case 8: /* octal */
233: putchar('o');
234: break;
235: case 2: /* binary */
236: putchar('b');
237: break;
238: default: /* nonstandard radix */
239: /* printf("(%d)",radix); */ ;
240: }
241:
242: if ((s[0] == '\033') && (s[1] == '\0'))
243: putchar(' '); /* supress newline */
244: else putchar('\n');
245:
246: fill0((byteptr)buf,sizeof(buf)); /* burn the evidence on the stack...*/
247: /* Note that local stack arrays r and quotient are now 0 */
248: return(places);
249: } /* display_in_base */
250:
251: #endif /* DEBUG */
252:
253: void mp_display(string s,unitptr r)
254: /* Display register r in hex, with prefix string s. */
255: { short precision;
256: int i,j;
257: putstr(s);
258: normalize(r,precision); /* strip off leading zeros */
259: if (precision == 0)
260: { putstr(" 0\n");
261: return;
262: }
263: make_msbptr(r,precision);
264: i=0;
265: while (precision--)
266: { if (!(i++ % (16/BYTES_PER_UNIT)))
267: { if (i>1)
268: { putchar('\n');
269: j=string_length(s);
270: while (j--) putchar(' ');
271: }
272: }
273: puthexunit(*r);
274: putchar(' ');
275: post_lowerunit(r);
276: }
277: putchar('\n');
278: } /* mp_display */
279:
280:
281: word16 checksum(register byteptr buf, register word16 count)
282: /* Returns checksum of buffer. */
283: { word16 cs;
284: cs = 0;
285: while (count--) cs += *buf++;
286: return(cs);
287: } /* checksum */
288:
289:
290: void cbc_xor(register unitptr dst, register unitptr src, word16 bytecount)
291: /* Performs the XOR necessary for RSA Cipher Block Chaining.
292: The dst buffer ought to have 1 less byte of significance than
293: the src buffer. Only the least significant part of the src
294: buffer is used. bytecount is the size of a plaintext block.
295: */
296: { short nunits; /* units of precision */
297: nunits = bytes2units(bytecount)-1;
298: make_lsbptr(dst,global_precision);
299: while (nunits--)
300: { *dst ^= *post_higherunit(src);
301: post_higherunit(dst);
302: bytecount -= units2bytes(1);
303: }
304: /* on the last unit, don't xor the excess top byte... */
305: *dst ^= (*src & (power_of_2(bytecount<<3)-1));
306: } /* cbc_xor */
307:
308:
309: void hiloswap(byteptr r1,short numbytes)
310: /* Reverses the order of bytes in an array of bytes. */
311: { byteptr r2;
312: byte b;
313: r2 = &(r1[numbytes-1]);
314: while (r1 < r2)
315: { b = *r1; *r1++ = *r2; *r2-- = b;
316: }
317: } /* hiloswap */
318:
319:
320: #define byteglue(lo,hi) ((((word16) hi) << 8) + (word16) lo)
321:
322: /**** The following functions must be changed if the external byteorder
323: changes for integers in PGP packet data.
324: ****/
325:
326:
327: word16 fetch_word16(byte *buf)
328: /* Fetches a 16-bit word from where byte pointer is pointing.
329: buf points to external-format byteorder array.
330: */
331: { word16 w0,w1;
332: #ifdef XLOWFIRST
333: w0 = *buf++;
334: w1 = *buf++;
335: #else
336: w1 = *buf++;
337: w0 = *buf++;
338: #endif
339: return(w0 + (w1<<8));
340: } /* fetch_word16 */
341:
342:
343: byte *put_word16(word16 w, byte *buf)
344: /* Puts a 16-bit word to where byte pointer is pointing, and
345: returns updated byte pointer.
346: buf points to external-format byteorder array.
347: */
348: {
349: #ifdef XLOWFIRST
350: buf[0] = w & 0xff;
351: w = w>>8;
352: buf[1] = w & 0xff;
353: #else
354: buf[1] = w & 0xff;
355: w = w>>8;
356: buf[0] = w & 0xff;
357: #endif
358: return(buf+2);
359: } /* put_word16 */
360:
361:
362: word32 fetch_word32(byte *buf)
363: /* Fetches a 32-bit word from where byte pointer is pointing.
364: buf points to external-format byteorder array.
365: */
366: { word32 w0,w1,w2,w3;
367: #ifdef XLOWFIRST
368: w0 = *buf++;
369: w1 = *buf++;
370: w2 = *buf++;
371: w3 = *buf++;
372: #else
373: w3 = *buf++;
374: w2 = *buf++;
375: w1 = *buf++;
376: w0 = *buf++;
377: #endif
378: return(w0 + (w1<<8) + (w2<<16) + (w3<<24));
379: } /* fetch_word32 */
380:
381:
382: byte *put_word32(word32 w, byte *buf)
383: /* Puts a 32-bit word to where byte pointer is pointing, and
384: returns updated byte pointer.
385: buf points to external-format byteorder array.
386: */
387: {
388: #ifdef XLOWFIRST
389: buf[0] = w & 0xff;
390: w = w>>8;
391: buf[1] = w & 0xff;
392: w = w>>8;
393: buf[2] = w & 0xff;
394: w = w>>8;
395: buf[3] = w & 0xff;
396: #else
397: buf[3] = w & 0xff;
398: w = w>>8;
399: buf[2] = w & 0xff;
400: w = w>>8;
401: buf[1] = w & 0xff;
402: w = w>>8;
403: buf[0] = w & 0xff;
404: #endif
405: return(buf+4);
406: } /* put_word32 */
407:
408:
409: /*** End of functions that must be changed if the external byteorder
410: changes for integer fields in PGP packets.
411: ***/
412:
413:
414:
415:
416: short mpi2reg(register unitptr r,register byteptr buf)
417: /* Converts a multiprecision integer from the externally-represented
418: form of a byte array with a 16-bit bitcount in a leading length
419: word to the internally-used representation as a unit array.
420: Converts to INTERNAL byte order.
421: The same buffer address may be used for both r and buf.
422: Returns number of units in result, or returns -1 on error.
423: */
424: { byte buf2[MAX_BYTE_PRECISION];
425: word16 bitcount, bytecount, unitcount, zero_bytes, i;
426:
427: /* First, extract 16-bit bitcount prefix from first 2 bytes... */
428: bitcount = fetch_word16(buf);
429: buf += 2;
430:
431: /* Convert bitcount to bytecount and unitcount... */
432: bytecount = bits2bytes(bitcount);
433: unitcount = bytes2units(bytecount);
434: if (unitcount > global_precision)
435: { /* precision overflow during conversion. */
436: return(-1); /* precision overflow -- error return */
437: }
438: zero_bytes = units2bytes(global_precision) - bytecount;
439: #ifdef XLOWFIRST
440: fill0(buf2+bytecount,zero_bytes); /* fill trailing zero bytes */
441: i = 0; /* assumes LSB first */
442: #else
443: fill0(buf2,zero_bytes); /* fill leading zero bytes */
444: i = zero_bytes; /* assumes MSB first */
445: #endif
446: while (bytecount--) buf2[i++] = *buf++;
447:
448: mp_convert_order(buf2); /* convert to INTERNAL byte order */
449: mp_move(r,(unitptr)buf2);
450: mp_burn((unitptr)buf2); /* burn the evidence on the stack */
451: return(unitcount); /* returns unitcount of reg */
452: } /* mpi2reg */
453:
454:
455: short reg2mpi(register byteptr buf,register unitptr r)
456: /* Converts the multiprecision integer r from the internal form of
457: a unit array to the normalized externally-represented form of a
458: byte array with a leading 16-bit bitcount word in buf[0] and buf[1].
459: This bitcount length prefix is exact count, not rounded up.
460: Converts to EXTERNAL byte order.
461: The same buffer address may be used for both r and buf.
462: Returns the number of bytes of the result, not counting length prefix.
463: */
464: { byte buf1[MAX_BYTE_PRECISION];
465: byteptr buf2;
466: short bytecount,bc;
467: word16 bitcount;
468: bitcount = countbits(r);
469: bytecount = bits2bytes(bitcount);
470: bc = bytecount; /* save bytecount for return */
471: buf2 = buf1;
472: mp_move((unitptr)buf2,r);
473: mp_convert_order(buf2); /* convert to EXTERNAL byteorder */
474: #ifndef XLOWFIRST
475: buf2 += units2bytes(global_precision) - bytecount;
476: #endif
477: buf = put_word16(bitcount, buf); /* store bitcount in external byteorder */
478:
479: while (bytecount--) *buf++ = *buf2++;
480:
481: mp_burn((unitptr)buf1); /* burn the evidence on the stack */
482: return(bc); /* returns bytecount of mpi, not counting prefix */
483: } /* reg2mpi */
484:
485:
486: #ifdef DEBUG
487:
488: void dumpbuf(string s, byteptr buf, int bytecount)
489: /* Dump buffer in hex, with string label prefix. */
490: { putstr(s);
491: while (bytecount--)
492: { puthexbyte(*buf++);
493: putchar(' ');
494: if ((bytecount & 0x0f)==0)
495: putchar('\n');
496: }
497: } /* dumpbuf */
498:
499: void dump_unit_array(string s, unitptr r)
500: /* Dump unit array r as a C array initializer, with string label prefix.
501: Array is dumped in native unit order.
502: */
503: { int unitcount;
504: unitcount = global_precision;
505: putstr(s);
506: putstr("\n{ ");
507: while (unitcount--)
508: { putstr("0x");
509: puthexunit(*r++);
510: putchar(',');
511: if (unitcount && ((unitcount & 0x07)==0))
512: putstr("\n ");
513: }
514: putstr(" 0};\n");
515: } /* dump_unit_array */
516:
517: #endif /* ifdef DEBUG */
518:
519:
520: /*
521: ** short preblock(outreg, inbuf, bytecount, modulus, randompad)
522: **
523: ** A plaintext message must be converted into an integer less than
524: ** the modulus n. We do this by making it 1 byte shorter than the
525: ** normalized modulus n. Short blocks are left justified and padded.
526: **
527: ** The padding used depends on whether randompad is NULL. First a
528: ** 0 byte is added beyond the data; then either 0xff's or values
529: ** from randompad are added. Last is a byte which tells whether
530: ** we are preblocking a message digest or a conventional key; we
531: ** assume that random padding is only used for conventional keys.
532: **
533: */
534: short preblock(unitptr outreg, byteptr inbuf, short bytecount,
535: unitptr modulus, byteptr randompad)
536: /* Converts plaintext block into form suitable for RSA encryption.
537: Converts to INTERNAL byte order.
538: Returns # of bytes remaining to process. Note that the same buffer
539: address may be used for both outreg and inbuf.
540: randompad is a pointer to a buffer of random pad bytes to use for
541: padding material, or NULL iff we want to use constant padding.
542: */
543: { byte out[MAX_BYTE_PRECISION];
544: short byte_precision,leading_zeros,remaining,blocksize,padsize;
545: short excess_pads; /* number of trailing zeros in long pads */
546: int i;
547:
548: byte_precision = units2bytes(global_precision);
549: leading_zeros = byte_precision - countbytes(modulus) + 1;
550: blocksize = byte_precision - leading_zeros;
551: /* note that blocksize includes data plus pad bytes, if any */
552:
553: remaining = bytecount - blocksize;
554: if (remaining>=0)
555: bytecount = blocksize;
556: padsize = blocksize - bytecount; /* bytes of padding */
557: i = 0;
558:
559: #ifndef XLOWFIRST
560: while (leading_zeros--) /* assumes MSB first */
561: out[i++] = 0;
562: #endif
563: while (bytecount--) /* copy user data */
564: out[i++] = *inbuf++;
565:
566: out [i++] = 0; /* Always start with a 0 for padding */
567:
568: /* Pad with either 0xff or values from randompad */
569: #ifdef XLOWFIRST
570: while (i < blocksize - 1)
571: #else
572: while (i < byte_precision - 1)
573: #endif
574: out[i++] = randompad ? *randompad++ : 0xff;
575:
576: /* End with type byte, which we deduce from randompad */
577: out[i++] = randompad ? CK_ENCRYPTED_BYTE : MD_ENCRYPTED_BYTE;
578:
579: /* End of padding logic */
580:
581: #ifdef XLOWFIRST
582: while (leading_zeros--) /* assumes LSB first */
583: out[i++] = 0;
584: #endif
585: mp_move(outreg,(unitptr)out);
586: mp_burn((unitptr)out); /* burn the evidence on the stack */
587: mp_convert_order((byte *)outreg); /* convert outreg to INTERNAL byte order */
588: return(remaining); /* less than 0 if there was padding */
589: } /* preblock */
590:
591:
592: short postunblock(byteptr outbuf, unitptr inreg, unitptr modulus)
593: /* Converts a just-decrypted RSA block back into unblocked plaintext form.
594: Converts to EXTERNAL byte order.
595: See the notes on preblocking in the preblock routine above.
596: Note that outbuf must be at least as large as inreg.
597: The same buffer address may be used for both outbuf and inreg.
598: Returns positive bytecount of plaintext, or negative error status.
599: */
600: { short i,byte_precision,leading_zeros,bytecount,blocksize;
601: boolean constpad;
602:
603: byte_precision = units2bytes(global_precision);
604: leading_zeros = byte_precision - countbytes(modulus) + 1;
605: blocksize = byte_precision - leading_zeros;
606: /* note that blocksize includes data plus pad bytes, if any */
607:
608: mp_move((unitptr)outbuf,inreg);
609: mp_convert_order(outbuf); /* convert to EXTERNAL byte order */
610:
611: /* Check high byte, make sure it's legal, figure out padding type */
612: #ifdef XLOWFIRST
613: i = blocksize - 1;
614: #else
615: i = byte_precision - 1;
616: #endif
617: if (outbuf[i] == MD_ENCRYPTED_BYTE)
618: constpad = 1;
619: else if (outbuf[i] == CK_ENCRYPTED_BYTE)
620: constpad = 0;
621: else
622: return(-1);
623:
624: /* Scan down for the 0 byte that ends padding */
625: while (--i > 0 && outbuf[i])
626: if (constpad && outbuf[i] != 0xff)
627: return(-1);
628:
629: #ifdef XLOWFIRST
630: bytecount = i;
631: #else
632: bytecount = i - leading_zeros;
633: if (leading_zeros)
634: for (i = 0; i < bytecount; ++i)
635: outbuf[i] = outbuf[i+leading_zeros];
636: #endif
637:
638: /* Zero out high part of buffer to make it look nice */
639: while (i < byte_precision)
640: outbuf[i++] = 0;
641:
642: return(bytecount); /* normal return */
643: } /* postunblock */
644:
645: /************ end of muliprecision integer I/O library *****************/
646:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.