home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Hacker Chronicles 2
/
HACKER2.BIN
/
1231.RSAIO.C
< prev
next >
Wrap
Text File
|
1991-05-25
|
18KB
|
619 lines
/* C source code for RSA library I/O routines.
Implemented Nov 86 by Philip Zimmermann
Last revised 11 Apr 91 by PRZ
Boulder Software Engineering
3021 Eleventh Street
Boulder, CO 80304
(303) 444-4541
(c) Copyright 1986 by Philip Zimmermann. All rights reserved.
The author assumes no liability for damages resulting from the use
of this software, even if the damage results from defects in this
software. No warranty is expressed or implied.
The external data representation for RSA messages and keys that
some of these library routines assume is outlined in a paper by
Philip Zimmermann, "A Proposed Standard Format for RSA Cryptosystems",
IEEE Computer, September 1986, Vol. 19 No. 9, pages 21-34.
Some revisions to this data format have occurred since the paper
was published.
*/
/* #define DEBUG */
#ifndef EMBEDDED /* not EMBEDDED - not compiling for embedded target */
#include <stdio.h> /* for printf, etc. */
#else /* EMBEDDED - compiling for embedded target */
#define NULL (void *)0
#endif
#include "rsalib.h"
#define RSAIO
#include "rsaio.h"
/*----------------- Following procedures relate to I/O ------------------*/
int string_length(char *s)
/* Returns string length, just like strlen() from <string.h> */
{ int i;
i = 0;
while (*s++) i++;
return (i);
} /* string_length */
static int ctox(int c)
/* Returns integer 0-15 if c is an ASCII hex digit, -1 otherwise. */
{ if ((c >= '0') && (c <= '9'))
return(c - '0');
if ((c >= 'a') && (c <= 'f'))
return((c - 'a') + 10);
if ((c >= 'A') && (c <= 'F'))
return((c - 'A') + 10);
return(-1); /* error -- not a hex digit */
} /* ctox */
int str2reg(unitptr reg,string digitstr)
/* Converts a possibly-signed digit string into a large binary number.
Returns assumed radix, derived from suffix 'h','o',b','.' */
{ unit temp[MAX_UNIT_PRECISION],base[MAX_UNIT_PRECISION];
int c,i;
boolean minus = FALSE;
short radix; /* base 2-16 */
mp_init(reg,0);
i = string_length(digitstr);
if (i==0) return(10); /* empty string, assume radix 10 */
c = digitstr[i-1]; /* get last char in string */
switch (c) /* classify radix select suffix character */
{
case '.': radix = 10;
break;
case 'H':
case 'h': radix = 16;
break;
case 'O':
case 'o': radix = 8;
break;
case 'B':
case 'b': radix = 2; /* caution! 'b' is a hex digit! */
break;
default: radix = 10;
}
mp_init(base,radix);
if (minus = (*digitstr == '-')) digitstr++;
while (c = *digitstr++)
{ if (c==',') continue; /* allow commas in number */
c = ctox(c);
if ((c < 0) || (c >= radix))
break; /* scan terminated by any non-digit */
mp_mult(temp,reg,base);
mp_move(reg,temp);
mp_init(temp,c);
mp_add(reg,temp);
}
if (minus) mp_neg(reg);
return(radix);
} /* str2reg */
/* These I/O functions, such as putstr, puthexbyte, and puthexw16,
are provided here to avoid the need to link in printf from the
C I/O library. This is handy in an embedded application.
*/
#ifdef EMBEDDED /* if compiling for embedded target */
int putchar(int c) /* standard C library function */
{ /* stub -- replace with putchar suitable for embedded target. */
} /* putchar */
#endif /* if compiling for embedded target */
void putstr(string s)
/* Put out null-terminated ASCII string via putchar. */
{ while (*s) putchar(*s++);
} /* putstr */
void puthexbyte(byte b)
/* Put out byte in ASCII hex via putchar. */
{ static const char *nibs = "0123456789ABCDEF";
putchar(nibs[b >> 4]);
putchar(nibs[b & 0x0F]);
} /* puthexbyte */
void puthexw16(word16 w)
/* Put out 16-bit word in hex, high byte first. */
{ puthexbyte((byte)(w >> 8));
puthexbyte((byte)(w & 0xFF));
} /* puthexw16 */
#ifdef UNIT32
static void puthexw32(word32 lw)
/* Puts out 32-bit word in hex, high byte first. */
{ puthexw16((word16)(lw>>16));
puthexw16((word16)(lw & 0xFFFFL));
} /* puthexw32 */
#endif /* UNIT32 */
#ifdef UNIT8
#define puthexunit(u) puthexbyte(u)
#endif
#ifdef UNIT16
#define puthexunit(u) puthexw16(u)
#endif
#ifdef UNIT32
#define puthexunit(u) puthexw32(u)
#endif
void fill0(byteptr buf,word16 bytecount)
/* Zero-fill the byte buffer. */
{ while (bytecount--) *buf++ = 0;
} /* fill0 */
int display_in_base(string s,unitptr n,short radix)
/* Display n in any base, such as base 10. Returns number of digits. */
/* s is string to label the displayed register.
n is multiprecision integer.
radix is base, 2-16.
*/
{
char buf[MAX_BIT_PRECISION + (MAX_BIT_PRECISION/8) + 2];
unit r[MAX_UNIT_PRECISION],quotient[MAX_UNIT_PRECISION];
word16 remainder;
char *bp = buf;
char minus = FALSE;
int places = 0;
int commaplaces; /* put commas this many digits apart */
int i;
/* If string s is just an ESC char, don't print it.
It's just to inhibit the \n at the end of the number.
*/
if ((s[0] != '\033') || (s[1] != '\0'))
putstr(s);
if ( (radix < 2) || (radix > 16) )
{ putstr("****\n"); /* radix out of range -- show error */
return(-1);
}
commaplaces = (radix==10 ? 3 : (radix==16 ? 4 :
(radix==2 ? 8 : (radix==8 ? 8 : 1))));
mp_move(r,n);
if ((radix == 10) && mp_tstminus(r))
{ minus = TRUE;
mp_neg(r); /* make r positive */
}
*bp = '\0';
do /* build backwards number string */
{ if (++places>1)
if ((places % commaplaces)==1)
*++bp = ','; /* 000,000,000,000 */
remainder = mp_shortdiv(quotient,r,radix);
*++bp = "0123456789ABCDEF" [remainder]; /* Isn't C wonderful? */
mp_move(r,quotient);
} while (testne(r,0));
if (minus)
*++bp = '-';
if (commaplaces!=1)
while ((++places % commaplaces) != 1)
*++bp = ' '; /* pad to line up commas */
i = string_length(s);
while (*bp)
{ putchar(*bp);
++i;
if ((*bp == ',') || commaplaces==1)
if (i > (72-commaplaces))
{ putchar('\n');
i=string_length(s);
while (i--) putchar(' ');
i = string_length(s);
}
bp--;
}
switch (radix)
{ /* show suffix character to designate radix */
case 10: /* decimal */
putchar('.');
break;
case 16: /* hex */
putchar('h');
break;
case 8: /* octal */
putchar('o');
break;
case 2: /* binary */
putchar('b');
break;
default: /* nonstandard radix */
/* printf("(%d)",radix); */ ;
}
if ((s[0] == '\033') && (s[1] == '\0'))
putchar(' '); /* supress newline */
else putchar('\n');
fill0(buf,sizeof(buf)); /* burn the evidence on the stack...*/
/* Note that local stack arrays r and quotient are now 0 */
return(places);
} /* display_in_base */
void mp_display(string s,unitptr r)
/* Display register r in hex, with prefix string s. */
{ short precision;
int i,j;
putstr(s);
normalize(r,precision); /* strip off leading zeros */
if (precision == 0)
{ putstr(" 0\n");
return;
}
make_msbptr(r,precision);
i=0;
while (precision--)
{ if (!(i++ % (16/BYTES_PER_UNIT)))
{ if (i>1)
{ putchar('\n');
j=string_length(s);
while (j--) putchar(' ');
}
}
puthexunit(*r);
putchar(' ');
post_lowerunit(r);
}
putchar('\n');
} /* mp_display */
word16 checksum(register byteptr buf, register word16 count)
/* Returns checksum of buffer. */
{ word16 cs;
cs = 0;
while (count--) cs += *buf++;
return(cs);
} /* checksum */
void cbc_xor(register unitptr dst, register unitptr src, word16 bytecount)
/* Performs the XOR necessary for RSA Cipher Block Chaining.
The dst buffer ought to have 1 less byte of significance than
the src buffer. Only the least significant part of the src
buffer is used. bytecount is the size of a plaintext block.
*/
{ short nunits; /* units of precision */
nunits = bytes2units(bytecount)-1;
make_lsbptr(dst,global_precision);
while (nunits--)
{ *dst ^= *post_higherunit(src);
post_higherunit(dst);
bytecount -= units2bytes(1);
}
/* on the last unit, don't xor the excess top byte... */
*dst ^= (*src & (power_of_2(bytecount<<3)-1));
} /* cbc_xor */
void hiloswap(byteptr r1,short numbytes)
/* Reverses the order of bytes in an array of bytes. */
{ byteptr r2;
byte b;
r2 = &(r1[numbytes-1]);
while (r1 < r2)
{ b = *r1; *r1++ = *r2; *r2-- = b;
}
} /* hiloswap */
#define byteglue(lo,hi) ((((word16) hi) << 8) + (word16) lo)
short mpi2reg(register unitptr r,register byteptr buf)
/* Converts a multiprecision integer from the externally-represented
form of a byte array with a 16-bit bitcount in a leading length
word to the internally-used representation as a unit array.
Converts to INTERNAL byte order.
The same buffer address may be used for both r and buf.
Returns number of units in result, or returns -1 on error.
*/
{ byte buf2[MAX_BYTE_PRECISION];
word16 bytecount, unitcount, zero_bytes, i;
word16 lowcount,highcount;
/* First, extract 16-bit bitcount prefix from first 2 bytes... */
#ifdef XHIGHFIRST
highcount = *buf++;
lowcount = *buf++;
#else
lowcount = *buf++;
highcount = *buf++;
#endif
/* Convert bitcount to bytecount and unitcount... */
bytecount = bits2bytes(byteglue(lowcount,highcount));
unitcount = bytes2units(bytecount);
if (unitcount > global_precision)
{ /* precision overflow during conversion. */
return(-1); /* precision overflow -- error return */
}
zero_bytes = units2bytes(global_precision) - bytecount;
#ifdef XHIGHFIRST
fill0(buf2,zero_bytes); /* fill leading zero bytes */
i = zero_bytes;
#else
fill0(buf2+bytecount,zero_bytes); /* fill trailing zero bytes */
i = 0;
#endif
while (bytecount--) buf2[i++] = *buf++;
convert_order(buf2); /* convert to INTERNAL byte order */
mp_move(r,(unitptr)buf2);
mp_burn((unitptr)buf2); /* burn the evidence on the stack */
return(unitcount); /* returns unitcount of reg */
} /* mpi2reg */
short reg2mpi(register byteptr buf,register unitptr r)
/* Converts the multiprecision integer r from the internal form of
a unit array to the normalized externally-represented form of a
byte array with a leading 16-bit bitcount word in buf[0] and buf[1].
This bitcount length prefix is exact count, not rounded up.
Converts to EXTERNAL byte order.
The same buffer address may be used for both r and buf.
Returns the number of bytes of the result, not counting length prefix.
*/
{ byte buf1[MAX_BYTE_PRECISION];
byteptr buf2;
short bytecount,bc;
word16 bitcount;
bitcount = countbits(r);
bytecount = bits2bytes(bitcount);
bc = bytecount; /* save bytecount for return */
buf2 = buf1;
mp_move((unitptr)buf2,r);
convert_order(buf2); /* convert to EXTERNAL byte order */
#ifdef XHIGHFIRST
/* Skip over leading zero bytes. */
buf2 += (units2bytes(global_precision) - bytecount);
*buf++ = bitcount >> 8; /* store bitcount with high byte first */
*buf++ = bitcount & 0xff;
#else
*buf++ = bitcount & 0xff; /* store bitcount with low byte first */
*buf++ = bitcount >> 8;
#endif /* not XHIGHFIRST */
while (bytecount--) *buf++ = *buf2++;
mp_burn((unitptr)buf1); /* burn the evidence on the stack */
return(bc); /* returns bytecount of mpi, not counting prefix */
} /* reg2mpi */
#ifdef DEBUG
void dumpbuf(string s, byteptr buf, int bytecount)
/* Dump buffer in hex, with string label prefix. */
{ putstr(s);
while (bytecount--)
{ puthexbyte(*buf++);
putchar(' ');
if ((bytecount & 0x0f)==0)
putchar('\n');
}
} /* dumpbuf */
void dump_unit_array(string s, unitptr r)
/* Dump unit array r as a C array initializer, with string label prefix.
Array is dumped in native unit order.
*/
{ int unitcount;
unitcount = significance(r);
putstr(s);
putstr("\n{ ");
while (unitcount--)
{ putstr("0x");
puthexunit(*r++);
putchar(',');
if (unitcount && ((unitcount & 0x07)==0))
putstr("\n ");
}
putstr(" 0};\n");
} /* dump_unit_array */
#endif /* ifdef DEBUG */
/*
** short preblock(outreg, inbuf, bytecount, modulus, cksbit, randompad)
**
** A plaintext message must be converted into an integer less than
** the modulus n. We do this by making it 1 byte shorter than the
** normalized modulus n. Short blocks are left justified and padded.
** The last pad byte is a count of how many pad bytes were required,
** including itself. Then the 16-bit checksum is appended.
**
** When using very long keys, if there are more than 255 bytes
** of padding, the extra pad bytes will all be 0. The first
** nonzero pad byte from the end will contain the count of the
** pad bytes preceding it, which should be 255 if there were more
** than 255 total pad bytes.
**
** For example, suppose the 5-byte string "hello" were the plaintext
** that needed preblocking, and the modulus was 11 bytes long, and
** nonrandom padding with a 16-bit checksum was applied. Here it is
** after preblocking, assuming an LSB-first external format:
** (LSB) (MSB)
** 'h','e','l','l','o',1,2,3,low_checksum,high_checksum,0,<slop zeros>
**
** But if XHIGHFIRST were defined, it would be blocked this way:
** (MSB) (LSB)
** <slop zeros>,0,'h','e','l','l','o',1,2,3,high_checksum,low_checksum
*/
short preblock(unitptr outreg, byteptr inbuf, short bytecount,
unitptr modulus, boolean cksbit, byteptr randompad)
/* Converts plaintext block into form suitable for RSA encryption.
Converts to INTERNAL byte order.
Returns # of bytes remaining to process. Note that the same buffer
address may be used for both outreg and inbuf.
cksbit is TRUE iff checksum word should be appended to block.
randompad is a pointer to a buffer of random pad bytes to use for
padding material, or NULL iff we want to use constant padding.
*/
{ byte out[MAX_BYTE_PRECISION];
byte pad;
short i,byte_precision,leading_zeros,remaining,blocksize,padsize;
short excess_pads; /* number of trailing zeros in long pads */
short startbyte;
word16 chksum;
byte_precision = units2bytes(global_precision);
leading_zeros = byte_precision - countbytes(modulus) + 1;
blocksize = byte_precision - leading_zeros - (2*cksbit);
/* note that blocksize includes data plus pad bytes, if any */
remaining = bytecount - blocksize;
if (remaining>=0)
bytecount = blocksize;
padsize = blocksize - bytecount; /* bytes of padding */
pad = 0;
i = 0;
#ifdef XHIGHFIRST
while (leading_zeros--)
out[i++] = 0;
#endif
startbyte = i;
while (bytecount--) /* copy user data */
out[i++] = *inbuf++;
/* Handle pad lengths in excess of 255 bytes... */
excess_pads = 0;
if (padsize > 255)
excess_pads = padsize - 255; /* compute spillage */
padsize -= excess_pads; /* do not allow padsize > 255 */
/* Perform either random padding or constant padding... */
if (randompad != NULL) /* random pad buffer provided? */
{ while (padsize-- > 1)
{ ++pad;
out[i++] = *randompad++; /* use random pad bytes */
}
padsize++; /* correct last padsize-- */
} /* end of random padding */
while ( padsize-- > 0 )
out[i++] = ++pad;
while (excess_pads--) /* only if more than 255 pad bytes */
out[i++] = 0; /* excess padding is zeros */
/* End of padding logic */
if (cksbit)
{ chksum = checksum(out+startbyte,blocksize);
#ifdef XHIGHFIRST
out[i++] = chksum >> 8; /* store checksum with high byte first */
out[i++] = chksum & 0xff;
#else
out[i++] = chksum & 0xff; /* store checksum with low byte first */
out[i++] = chksum >> 8;
#endif /* not XHIGHFIRST */
}
#ifndef XHIGHFIRST
while (leading_zeros--)
out[i++] = 0;
#endif
mp_move(outreg,(unitptr)out);
mp_burn((unitptr)out); /* burn the evidence on the stack */
convert_order(outreg); /* convert outreg to INTERNAL byte order */
return(remaining); /* less than 0 if there was padding */
} /* preblock */
short postunblock(byteptr outbuf, unitptr inreg,
unitptr modulus, boolean padded, boolean cksbit)
/* Converts a just-decrypted RSA block back into unblocked plaintext form.
Converts to EXTERNAL byte order.
See the notes on preblocking in the preblock routine above.
Note that outbuf must be at least as large as inreg.
The same buffer address may be used for both outbuf and inreg.
padded is TRUE iff block is expected to contain pad bytes.
cksbit is TRUE iff block is expected to contain checksum word.
Returns positive bytecount of plaintext, or negative error status.
*/
{ short i,byte_precision,leading_zeros,bytecount,blocksize;
word16 chksum,chksumlo,chksumhi;
word16 padsize;
byte_precision = units2bytes(global_precision);
leading_zeros = byte_precision - countbytes(modulus) + 1;
blocksize = byte_precision - leading_zeros - (2*cksbit);
/* note that blocksize includes data plus pad bytes, if any */
mp_move((unitptr)outbuf,inreg);
convert_order(outbuf); /* convert to EXTERNAL byte order */
#ifndef XHIGHFIRST
#define STARTBYTE 0
#else
#define STARTBYTE leading_zeros
#endif
if (cksbit)
{
#ifdef XHIGHFIRST
chksumhi = outbuf[STARTBYTE+blocksize];
chksumlo = outbuf[STARTBYTE+blocksize+1];
#else
chksumlo = outbuf[STARTBYTE+blocksize];
chksumhi = outbuf[STARTBYTE+blocksize+1];
#endif
chksum = byteglue(chksumlo,chksumhi);
if ( chksum != checksum(outbuf+STARTBYTE,blocksize) )
return(-1); /* return checksum error */
} /* checkum expected */
padsize = 0;
if (padded)
{ i = STARTBYTE+blocksize-1;
while (outbuf[i] == 0) /* clip off null excess pad bytes */
{ padsize++; i--;
}
padsize += outbuf[i];
}
if (padsize > blocksize)
{ /* Error - pad count out of range. */
padsize = 0; /* bogus padding means no padding */
return(-2); /* pad count out of range -- error return */
}
bytecount = blocksize - padsize;
#ifdef XHIGHFIRST
i = 0;
while (i++ < bytecount)
outbuf[i-1] = outbuf[STARTBYTE+i-1];
#endif
i = bytecount;
while (i < byte_precision)
outbuf[i++] = 0;
return(bytecount); /* normal return */
#undef STARTBYTE
} /* postunblock */
/****************** end of RSA I/O library ************************/