![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to rsaio.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [PGP] / pgp / src|
Return to rsaio.c CVS log | Up to [PGP] / pgp / src |
1.1 root 1: /* C source code for RSA library I/O routines.
2: Implemented Nov 86 by Philip Zimmermann
3: Last revised 11 Apr 91 by PRZ
4:
5: Boulder Software Engineering
6: 3021 Eleventh Street
7: Boulder, CO 80304
8: (303) 444-4541
9:
10: (c) Copyright 1986 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: The external data representation for RSA messages and keys that
16: some of these library routines assume is outlined in a paper by
17: Philip Zimmermann, "A Proposed Standard Format for RSA Cryptosystems",
18: IEEE Computer, September 1986, Vol. 19 No. 9, pages 21-34.
19: Some revisions to this data format have occurred since the paper
20: was published.
21: */
22:
23: /* #define DEBUG */
24:
25:
26: #ifndef EMBEDDED /* not EMBEDDED - not compiling for embedded target */
27: #include <stdio.h> /* for printf, etc. */
28: #else /* EMBEDDED - compiling for embedded target */
29: #define NULL (void *)0
30: #endif
31:
32: #include "rsalib.h"
33: #define RSAIO
34: #include "rsaio.h"
35:
36:
37: /*----------------- Following procedures relate to I/O ------------------*/
38:
39: int string_length(char *s)
40: /* Returns string length, just like strlen() from <string.h> */
41: { int i;
42: i = 0;
43: while (*s++) i++;
44: return (i);
45: } /* string_length */
46:
47:
48: static int ctox(int c)
49: /* Returns integer 0-15 if c is an ASCII hex digit, -1 otherwise. */
50: { if ((c >= '0') && (c <= '9'))
51: return(c - '0');
52: if ((c >= 'a') && (c <= 'f'))
53: return((c - 'a') + 10);
54: if ((c >= 'A') && (c <= 'F'))
55: return((c - 'A') + 10);
56: return(-1); /* error -- not a hex digit */
57: } /* ctox */
58:
59:
60: int str2reg(unitptr reg,string digitstr)
61: /* Converts a possibly-signed digit string into a large binary number.
62: Returns assumed radix, derived from suffix 'h','o',b','.' */
63: { unit temp[MAX_UNIT_PRECISION],base[MAX_UNIT_PRECISION];
64: int c,i;
65: boolean minus = FALSE;
66: short radix; /* base 2-16 */
67:
68: mp_init(reg,0);
69:
70: i = string_length(digitstr);
71: if (i==0) return(10); /* empty string, assume radix 10 */
72: c = digitstr[i-1]; /* get last char in string */
73:
74: switch (c) /* classify radix select suffix character */
75: {
76: case '.': radix = 10;
77: break;
78: case 'H':
79: case 'h': radix = 16;
80: break;
81: case 'O':
82: case 'o': radix = 8;
83: break;
84: case 'B':
85: case 'b': radix = 2; /* caution! 'b' is a hex digit! */
86: break;
87: default: radix = 10;
88: }
89:
90: mp_init(base,radix);
91: if (minus = (*digitstr == '-')) digitstr++;
92: while (c = *digitstr++)
93: { if (c==',') continue; /* allow commas in number */
94: c = ctox(c);
95: if ((c < 0) || (c >= radix))
96: break; /* scan terminated by any non-digit */
97: mp_mult(temp,reg,base);
98: mp_move(reg,temp);
99: mp_init(temp,c);
100: mp_add(reg,temp);
101: }
102: if (minus) mp_neg(reg);
103: return(radix);
104: } /* str2reg */
105:
106:
107: /* These I/O functions, such as putstr, puthexbyte, and puthexw16,
108: are provided here to avoid the need to link in printf from the
109: C I/O library. This is handy in an embedded application.
110: */
111:
112: #ifdef EMBEDDED /* if compiling for embedded target */
113: int putchar(int c) /* standard C library function */
114: { /* stub -- replace with putchar suitable for embedded target. */
115: } /* putchar */
116: #endif /* if compiling for embedded target */
117:
118: void putstr(string s)
119: /* Put out null-terminated ASCII string via putchar. */
120: { while (*s) putchar(*s++);
121: } /* putstr */
122:
123: void puthexbyte(byte b)
124: /* Put out byte in ASCII hex via putchar. */
125: { static const char *nibs = "0123456789ABCDEF";
126: putchar(nibs[b >> 4]);
127: putchar(nibs[b & 0x0F]);
128: } /* puthexbyte */
129:
130: void puthexw16(word16 w)
131: /* Put out 16-bit word in hex, high byte first. */
132: { puthexbyte((byte)(w >> 8));
133: puthexbyte((byte)(w & 0xFF));
134: } /* puthexw16 */
135:
136: #ifdef UNIT32
137: static void puthexw32(word32 lw)
138: /* Puts out 32-bit word in hex, high byte first. */
139: { puthexw16((word16)(lw>>16));
140: puthexw16((word16)(lw & 0xFFFFL));
141: } /* puthexw32 */
142: #endif /* UNIT32 */
143:
144:
145: #ifdef UNIT8
146: #define puthexunit(u) puthexbyte(u)
147: #endif
148: #ifdef UNIT16
149: #define puthexunit(u) puthexw16(u)
150: #endif
151: #ifdef UNIT32
152: #define puthexunit(u) puthexw32(u)
153: #endif
154:
155:
156: void fill0(byteptr buf,word16 bytecount)
157: /* Zero-fill the byte buffer. */
158: { while (bytecount--) *buf++ = 0;
159: } /* fill0 */
160:
161:
162: int display_in_base(string s,unitptr n,short radix)
163: /* Display n in any base, such as base 10. Returns number of digits. */
164: /* s is string to label the displayed register.
165: n is multiprecision integer.
166: radix is base, 2-16.
167: */
168: {
169: char buf[MAX_BIT_PRECISION + (MAX_BIT_PRECISION/8) + 2];
170: unit r[MAX_UNIT_PRECISION],quotient[MAX_UNIT_PRECISION];
171: word16 remainder;
172: char *bp = buf;
173: char minus = FALSE;
174: int places = 0;
175: int commaplaces; /* put commas this many digits apart */
176: int i;
177:
178: /* If string s is just an ESC char, don't print it.
179: It's just to inhibit the \n at the end of the number.
180: */
181: if ((s[0] != '\033') || (s[1] != '\0'))
182: putstr(s);
183:
184: if ( (radix < 2) || (radix > 16) )
185: { putstr("****\n"); /* radix out of range -- show error */
186: return(-1);
187: }
188: commaplaces = (radix==10 ? 3 : (radix==16 ? 4 :
189: (radix==2 ? 8 : (radix==8 ? 8 : 1))));
190: mp_move(r,n);
191: if ((radix == 10) && mp_tstminus(r))
192: { minus = TRUE;
193: mp_neg(r); /* make r positive */
194: }
195:
196: *bp = '\0';
197: do /* build backwards number string */
198: { if (++places>1)
199: if ((places % commaplaces)==1)
200: *++bp = ','; /* 000,000,000,000 */
201: remainder = mp_shortdiv(quotient,r,radix);
202: *++bp = "0123456789ABCDEF" [remainder]; /* Isn't C wonderful? */
203: mp_move(r,quotient);
204: } while (testne(r,0));
205: if (minus)
206: *++bp = '-';
207:
208: if (commaplaces!=1)
209: while ((++places % commaplaces) != 1)
210: *++bp = ' '; /* pad to line up commas */
211:
212: i = string_length(s);
213: while (*bp)
214: { putchar(*bp);
215: ++i;
216: if ((*bp == ',') || commaplaces==1)
217: if (i > (72-commaplaces))
218: { putchar('\n');
219: i=string_length(s);
220: while (i--) putchar(' ');
221: i = string_length(s);
222: }
223: bp--;
224: }
225: switch (radix)
226: { /* show suffix character to designate radix */
227: case 10: /* decimal */
228: putchar('.');
229: break;
230: case 16: /* hex */
231: putchar('h');
232: break;
233: case 8: /* octal */
234: putchar('o');
235: break;
236: case 2: /* binary */
237: putchar('b');
238: break;
239: default: /* nonstandard radix */
240: /* printf("(%d)",radix); */ ;
241: }
242:
243: if ((s[0] == '\033') && (s[1] == '\0'))
244: putchar(' '); /* supress newline */
245: else putchar('\n');
246:
247: fill0(buf,sizeof(buf)); /* burn the evidence on the stack...*/
248: /* Note that local stack arrays r and quotient are now 0 */
249: return(places);
250: } /* display_in_base */
251:
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:
323: short mpi2reg(register unitptr r,register byteptr buf)
324: /* Converts a multiprecision integer from the externally-represented
325: form of a byte array with a 16-bit bitcount in a leading length
326: word to the internally-used representation as a unit array.
327: Converts to INTERNAL byte order.
328: The same buffer address may be used for both r and buf.
329: Returns number of units in result, or returns -1 on error.
330: */
331: { byte buf2[MAX_BYTE_PRECISION];
332: word16 bytecount, unitcount, zero_bytes, i;
333: word16 lowcount,highcount;
334:
335: /* First, extract 16-bit bitcount prefix from first 2 bytes... */
336: #ifdef XHIGHFIRST
337: highcount = *buf++;
338: lowcount = *buf++;
339: #else
340: lowcount = *buf++;
341: highcount = *buf++;
342: #endif
343: /* Convert bitcount to bytecount and unitcount... */
344: bytecount = bits2bytes(byteglue(lowcount,highcount));
345: unitcount = bytes2units(bytecount);
346: if (unitcount > global_precision)
347: { /* precision overflow during conversion. */
348: return(-1); /* precision overflow -- error return */
349: }
350: zero_bytes = units2bytes(global_precision) - bytecount;
351:
352: #ifdef XHIGHFIRST
353: fill0(buf2,zero_bytes); /* fill leading zero bytes */
354: i = zero_bytes;
355: #else
356: fill0(buf2+bytecount,zero_bytes); /* fill trailing zero bytes */
357: i = 0;
358: #endif
359: while (bytecount--) buf2[i++] = *buf++;
360:
361: convert_order(buf2); /* convert to INTERNAL byte order */
362: mp_move(r,(unitptr)buf2);
363: mp_burn((unitptr)buf2); /* burn the evidence on the stack */
364: return(unitcount); /* returns unitcount of reg */
365: } /* mpi2reg */
366:
367:
368: short reg2mpi(register byteptr buf,register unitptr r)
369: /* Converts the multiprecision integer r from the internal form of
370: a unit array to the normalized externally-represented form of a
371: byte array with a leading 16-bit bitcount word in buf[0] and buf[1].
372: This bitcount length prefix is exact count, not rounded up.
373: Converts to EXTERNAL byte order.
374: The same buffer address may be used for both r and buf.
375: Returns the number of bytes of the result, not counting length prefix.
376: */
377: { byte buf1[MAX_BYTE_PRECISION];
378: byteptr buf2;
379: short bytecount,bc;
380: word16 bitcount;
381: bitcount = countbits(r);
382: bytecount = bits2bytes(bitcount);
383: bc = bytecount; /* save bytecount for return */
384: buf2 = buf1;
385: mp_move((unitptr)buf2,r);
386: convert_order(buf2); /* convert to EXTERNAL byte order */
387: #ifdef XHIGHFIRST
388: /* Skip over leading zero bytes. */
389: buf2 += (units2bytes(global_precision) - bytecount);
390: *buf++ = bitcount >> 8; /* store bitcount with high byte first */
391: *buf++ = bitcount & 0xff;
392: #else
393: *buf++ = bitcount & 0xff; /* store bitcount with low byte first */
394: *buf++ = bitcount >> 8;
395: #endif /* not XHIGHFIRST */
396:
397: while (bytecount--) *buf++ = *buf2++;
398:
399: mp_burn((unitptr)buf1); /* burn the evidence on the stack */
400: return(bc); /* returns bytecount of mpi, not counting prefix */
401: } /* reg2mpi */
402:
403:
404: #ifdef DEBUG
405:
406: void dumpbuf(string s, byteptr buf, int bytecount)
407: /* Dump buffer in hex, with string label prefix. */
408: { putstr(s);
409: while (bytecount--)
410: { puthexbyte(*buf++);
411: putchar(' ');
412: if ((bytecount & 0x0f)==0)
413: putchar('\n');
414: }
415: } /* dumpbuf */
416:
417: void dump_unit_array(string s, unitptr r)
418: /* Dump unit array r as a C array initializer, with string label prefix.
419: Array is dumped in native unit order.
420: */
421: { int unitcount;
422: unitcount = significance(r);
423: putstr(s);
424: putstr("\n{ ");
425: while (unitcount--)
426: { putstr("0x");
427: puthexunit(*r++);
428: putchar(',');
429: if (unitcount && ((unitcount & 0x07)==0))
430: putstr("\n ");
431: }
432: putstr(" 0};\n");
433: } /* dump_unit_array */
434:
435: #endif /* ifdef DEBUG */
436:
437:
438: /*
439: ** short preblock(outreg, inbuf, bytecount, modulus, cksbit, randompad)
440: **
441: ** A plaintext message must be converted into an integer less than
442: ** the modulus n. We do this by making it 1 byte shorter than the
443: ** normalized modulus n. Short blocks are left justified and padded.
444: ** The last pad byte is a count of how many pad bytes were required,
445: ** including itself. Then the 16-bit checksum is appended.
446: **
447: ** When using very long keys, if there are more than 255 bytes
448: ** of padding, the extra pad bytes will all be 0. The first
449: ** nonzero pad byte from the end will contain the count of the
450: ** pad bytes preceding it, which should be 255 if there were more
451: ** than 255 total pad bytes.
452: **
453: ** For example, suppose the 5-byte string "hello" were the plaintext
454: ** that needed preblocking, and the modulus was 11 bytes long, and
455: ** nonrandom padding with a 16-bit checksum was applied. Here it is
456: ** after preblocking, assuming an LSB-first external format:
457: ** (LSB) (MSB)
458: ** 'h','e','l','l','o',1,2,3,low_checksum,high_checksum,0,<slop zeros>
459: **
460: ** But if XHIGHFIRST were defined, it would be blocked this way:
461: ** (MSB) (LSB)
462: ** <slop zeros>,0,'h','e','l','l','o',1,2,3,high_checksum,low_checksum
463: */
464: short preblock(unitptr outreg, byteptr inbuf, short bytecount,
465: unitptr modulus, boolean cksbit, byteptr randompad)
466: /* Converts plaintext block into form suitable for RSA encryption.
467: Converts to INTERNAL byte order.
468: Returns # of bytes remaining to process. Note that the same buffer
469: address may be used for both outreg and inbuf.
470: cksbit is TRUE iff checksum word should be appended to block.
471: randompad is a pointer to a buffer of random pad bytes to use for
472: padding material, or NULL iff we want to use constant padding.
473: */
474: { byte out[MAX_BYTE_PRECISION];
475: byte pad;
476: short i,byte_precision,leading_zeros,remaining,blocksize,padsize;
477: short excess_pads; /* number of trailing zeros in long pads */
478: short startbyte;
479: word16 chksum;
480:
481: byte_precision = units2bytes(global_precision);
482: leading_zeros = byte_precision - countbytes(modulus) + 1;
483: blocksize = byte_precision - leading_zeros - (2*cksbit);
484: /* note that blocksize includes data plus pad bytes, if any */
485:
486: remaining = bytecount - blocksize;
487: if (remaining>=0)
488: bytecount = blocksize;
489: padsize = blocksize - bytecount; /* bytes of padding */
490: pad = 0;
491: i = 0;
492:
493: #ifdef XHIGHFIRST
494: while (leading_zeros--)
495: out[i++] = 0;
496: #endif
497: startbyte = i;
498: while (bytecount--) /* copy user data */
499: out[i++] = *inbuf++;
500:
501: /* Handle pad lengths in excess of 255 bytes... */
502: excess_pads = 0;
503: if (padsize > 255)
504: excess_pads = padsize - 255; /* compute spillage */
505: padsize -= excess_pads; /* do not allow padsize > 255 */
506:
507: /* Perform either random padding or constant padding... */
508: if (randompad != NULL) /* random pad buffer provided? */
509: { while (padsize-- > 1)
510: { ++pad;
511: out[i++] = *randompad++; /* use random pad bytes */
512: }
513: padsize++; /* correct last padsize-- */
514: } /* end of random padding */
515:
516: while ( padsize-- > 0 )
517: out[i++] = ++pad;
518:
519: while (excess_pads--) /* only if more than 255 pad bytes */
520: out[i++] = 0; /* excess padding is zeros */
521:
522: /* End of padding logic */
523:
524: if (cksbit)
525: { chksum = checksum(out+startbyte,blocksize);
526: #ifdef XHIGHFIRST
527: out[i++] = chksum >> 8; /* store checksum with high byte first */
528: out[i++] = chksum & 0xff;
529: #else
530: out[i++] = chksum & 0xff; /* store checksum with low byte first */
531: out[i++] = chksum >> 8;
532: #endif /* not XHIGHFIRST */
533: }
534:
535: #ifndef XHIGHFIRST
536: while (leading_zeros--)
537: out[i++] = 0;
538: #endif
539: mp_move(outreg,(unitptr)out);
540: mp_burn((unitptr)out); /* burn the evidence on the stack */
541: convert_order(outreg); /* convert outreg to INTERNAL byte order */
542: return(remaining); /* less than 0 if there was padding */
543: } /* preblock */
544:
545:
546: short postunblock(byteptr outbuf, unitptr inreg,
547: unitptr modulus, boolean padded, boolean cksbit)
548: /* Converts a just-decrypted RSA block back into unblocked plaintext form.
549: Converts to EXTERNAL byte order.
550: See the notes on preblocking in the preblock routine above.
551: Note that outbuf must be at least as large as inreg.
552: The same buffer address may be used for both outbuf and inreg.
553: padded is TRUE iff block is expected to contain pad bytes.
554: cksbit is TRUE iff block is expected to contain checksum word.
555: Returns positive bytecount of plaintext, or negative error status.
556: */
557: { short i,byte_precision,leading_zeros,bytecount,blocksize;
558: word16 chksum,chksumlo,chksumhi;
559: word16 padsize;
560:
561: byte_precision = units2bytes(global_precision);
562: leading_zeros = byte_precision - countbytes(modulus) + 1;
563: blocksize = byte_precision - leading_zeros - (2*cksbit);
564: /* note that blocksize includes data plus pad bytes, if any */
565:
566: mp_move((unitptr)outbuf,inreg);
567: convert_order(outbuf); /* convert to EXTERNAL byte order */
568:
569: #ifndef XHIGHFIRST
570: #define STARTBYTE 0
571: #else
572: #define STARTBYTE leading_zeros
573: #endif
574: if (cksbit)
575: {
576: #ifdef XHIGHFIRST
577: chksumhi = outbuf[STARTBYTE+blocksize];
578: chksumlo = outbuf[STARTBYTE+blocksize+1];
579: #else
580: chksumlo = outbuf[STARTBYTE+blocksize];
581: chksumhi = outbuf[STARTBYTE+blocksize+1];
582: #endif
583: chksum = byteglue(chksumlo,chksumhi);
584:
585: if ( chksum != checksum(outbuf+STARTBYTE,blocksize) )
586: return(-1); /* return checksum error */
587: } /* checkum expected */
588:
589: padsize = 0;
590: if (padded)
591: { i = STARTBYTE+blocksize-1;
592: while (outbuf[i] == 0) /* clip off null excess pad bytes */
593: { padsize++; i--;
594: }
595: padsize += outbuf[i];
596: }
597:
598: if (padsize > blocksize)
599: { /* Error - pad count out of range. */
600: padsize = 0; /* bogus padding means no padding */
601: return(-2); /* pad count out of range -- error return */
602: }
603: bytecount = blocksize - padsize;
604:
605: #ifdef XHIGHFIRST
606: i = 0;
607: while (i++ < bytecount)
608: outbuf[i-1] = outbuf[STARTBYTE+i-1];
609: #endif
610: i = bytecount;
611: while (i < byte_precision)
612: outbuf[i++] = 0;
613: return(bytecount); /* normal return */
614: #undef STARTBYTE
615: } /* postunblock */
616:
617: /****************** end of RSA I/O library ************************/
618:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.