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