home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / crypl200.zip / KEYMGMT / PGP_IDEA.C < prev    next >
Text File  |  1996-09-22  |  13KB  |  418 lines
  1. /* This code was scanned from the book "PGP - Source Code and Internals",
  2.    Phil Zimmermann, MIT Press 1995, ISBN 0-262-24039-4, p.369-382 using
  3.    OmniPage Pro v6 and then cleaned up (removed page numbers, fixed a few
  4.    mis-recognised characters, etc) with an editor.  It was not exported
  5.    from the US in electronic form */
  6.  
  7. /*
  8.  *    idea.c - C source code for IDEA block cipher.
  9.  *      IDEA (International Data Encryption Algorithm), formerly known as 
  10.  *      IPES (Improved Proposed Encryption Standard).
  11.  *      Algorithm developed by Xuejia Lai and James L. Massey, of ETH Zurich.
  12.  *      This implementation modified and derived from original C code 
  13.  *      developed by Xuejia Lai.
  14.  *      Zero-based indexing added, names changed from IPES to IDEA.
  15.  *      CFB functions added.  Random number routines added.
  16.  *
  17.  *      Extensively optimized and restructured by Colin Plumb.
  18.  *
  19.  *      There are two adjustments that can be made to this code to
  20.  *      speed it up.  Defaults may be used for PCs.  Only the -DIDEA32
  21.  *      pays off significantly if selectively set or not set.
  22.  *      Experiment to see what works best for your machine.
  23.  *
  24.  *      Multiplication: default is inline, -DAVOID_JUMPS uses a
  25.  *              different version that does not do any conditional
  26.  *              jumps (a few percent worse on a SPARC), while
  27.  *              -DSMALL_CACHE takes it out of line to stay
  28.  *              within a small on-chip code cache.
  29.  *      Variables: normally, 16-bit variables are used, but some
  30.  *              machines (notably RISCs) do not have 16-bit registers,
  31.  *              so they do a great deal of masking.  -DIDEA32 uses "int"
  32.  *              register variables and masks explicitly only where
  33.  *              necessary.  On a SPARC, for example, this boosts
  34.  *              performace by 30%.
  35.  *
  36.  *      The IDEA(tm) block cipher is covered by patents held by ETH and a
  37.  *      Swiss company called Ascom-Tech AG.  The Swiss patent number is
  38.  *      PCT/CH91/00117, the European patent number is EP 0 482 154 B1, and
  39.  *      the U.S. patent number is US005214703.  IDEA(tm) is a trademark of
  40.  *      Ascom-Tech AG.  There is no license fee required for noncommercial
  41.  *      use.  Commercial users may obtain licensing details from Dieter
  42.  *      Profos, Ascom Tech AG, Solothurn Lab, Postfach 151, 4502 Solothurn,
  43.  *      Switzerland, Tel +41 65 242885, Fax +41 65 235761.
  44.  *
  45.  *      The IDEA block cipher uses a 64-bit block size, and a 128-bit key 
  46.  *      size.  It breaks the 64-bit cipher block into four 16-bit words
  47.  *      because all of the primitive inner operations are done with 16-bit 
  48.  *      arithmetic.  It likewise breaks the 128-bit cipher key into eight 
  49.  *      16-bit words.
  50.  *
  51.  *      For further information on the IDEA cipher, see the book:
  52.  *        Xuejia Lai, "On the Design and Security of Block Ciphers",
  53.  *        ETH Series on Information Processing (ed. J.L. Massey) Vol 1,
  54.  *        Hartung-Gorre Verlag, Konstanz, Switzerland, 1992.  ISBN
  55.  *        3-89191-573-X.
  56.  *
  57.  *      This code runs on arrays of bytes by taking pairs in big-endian
  58.  *      order to make the 16-bit words that IDEA uses internally.  This
  59.  *      produces the same result regardless of the byte order of the
  60.  *      native CPU.
  61.  */
  62.  
  63. #include <string.h>
  64. #if defined( INC_ALL ) || defined( INC_CHILD )
  65.   #include "pgp_idea.h"
  66. #else
  67.   #include "keymgmt/pgp_idea.h"
  68. #endif /* Compiler-specific includes */
  69.  
  70. #ifdef IDEA32            /* Use >16-bit temporaries */
  71. #define low16(x) ((x) & 0xFFFF)
  72. typedef unsigned int uint16;    /* at LEAST 16 bits, maybe more */
  73. #else
  74. #define low16(x) (x)        /* this is only ever applied to uint16's */
  75. typedef word16 uint16;
  76. #endif
  77.  
  78. #ifdef _GNUC_
  79. /* __const__ simply means there are no side effects for this function,
  80.  * which is useful info for the gcc optimizer
  81.  */
  82. #define CONST __const__
  83. #else
  84. #define CONST
  85. #endif
  86.  
  87. /*
  88.  * Multiplication, modulo (2**16)+1
  89.  * Note that this code is structured on the assumption that
  90.  * untaken branches are cheaper than taken branches, and the
  91.  * compiler doesn't schedule branches.
  92.  */
  93. #ifdef SMALL_CACHE
  94. CONST static uint16
  95.  mul(register uint16 a, register uint16 b)
  96. {
  97.     register word32 p;
  98.  
  99.     p = (word32) a *b;
  100.     if (p) {
  101.     b = low16(p);
  102.     a = p >> 16;
  103.     return (b - a) + (b < a);
  104.     } else if (a) {
  105.     return 1 - a;
  106.     } else {
  107.     return 1 - b;
  108.     }
  109. }                /* mul */
  110. #endif                /* SMALL_CACHE */
  111.  
  112. /*
  113.  * Compute the multiplicative inverse of x, modulo 65537, using Euclid's
  114.  * algorithm. It is unrolled twice to avoid swapping the registers each
  115.  * iteration, and some subtracts of t have been changed to adds.
  116.  */
  117. CONST static uint16
  118.  mulInv(uint16 x)
  119. {
  120.     uint16 t0, t1;
  121.     uint16 q, y;
  122.  
  123.     if (x <= 1)
  124.     return x;        /* 0 and 1 are self-inverse */
  125.     t1 = 0x10001L / x;        /* Since x >= 2, this fits into 16 bits */
  126.     y = 0x10001L % x;
  127.     if (y == 1)
  128.     return low16(1 - t1);
  129.     t0 = 1;
  130.     do {
  131.     q = x / y;
  132.     x = x % y;
  133.     t0 += q * t1;
  134.     if (x == 1)
  135.         return t0;
  136.     q = y / x;
  137.     y = y % x;
  138.     t1 += q * t0;
  139.     } while (y != 1);
  140.     return low16(1 - t1);
  141. }                /* mukInv */
  142.  
  143. /*
  144.  * Expand a 128-bit user key to a working encryption key EK
  145.  */
  146. static void ideaExpandKey(byte const *userkey, word16 * EK)
  147. {
  148.     int i, j;
  149.  
  150.     for (j = 0; j < 8; j++) {
  151.     EK[j] = (userkey[0] << 8) + userkey[1];
  152.     userkey += 2;
  153.     }
  154.     for (i = 0; j < IDEAKEYLEN; j++) {
  155.     i++;
  156.     EK[i + 7] = (EK[i & 7] << 9) | (EK[i + 1 & 7] >> 7);
  157.     EK += i & 8;
  158.     i &= 7;
  159.     }
  160. }                /* ideaExpandKey */
  161.  
  162. /*
  163.  * MUL(x,y) computes x = x*y, modulo 0x10001.  Requires two temps,
  164.  * t16 and t32.  x is modified, and must be a side-effect-free lvalue.
  165.  * y may be anything, but unlike x, must be strictly less than 65536 
  166.  * even if low16() is #defined.
  167.  * All of these are equivalent - see which is faster on your machine
  168.  */
  169. #ifdef SMALL_CACHE
  170. #define MUL(x,y) (x = mul(low16(x),y))
  171. #else                /* !SMALL_CACHE */
  172. #ifdef AVOID_JUMPS
  173. #define MUL(x,y) (x = low16(x-1), t16 = low16((y)-1), \
  174.         t32 = (word32)x*t16 + x + t16, x = low16(t32), \
  175.         t16 = t32>>16, x = (x-t16) + (x<t16) + 1)
  176. #else                /* !AVOID_JUMPS (default) */
  177. #define MUL(x,y) \
  178.     ((t16 = (y)) ? \
  179.         (x=low16(x)) ? \
  180.             t32 = (word32)x*t16, \
  181.             x = low16(t32), \
  182.             t16 = t32>>16, \
  183.             x = (x-t16)+(x<t16) \
  184.         : \
  185.             (x = 1-t16) \
  186.     : \
  187.         (x = 1-x))
  188. #endif
  189. #endif
  190.  
  191. /*      IDEA encryption/decryption algorithm */
  192. /* Note that in and out can be the same buffer */
  193. static void ideaCipher(byte const inbuf[8], byte outbuf[8],
  194.                word16 const *key)
  195. {
  196.     register uint16 x1, x2, x3, x4, s2, s3;
  197.     word16 *in, *out;
  198. #ifndef SMALL_CACHE
  199.     register uint16 t16;    /* Temporaries needed by MUL macro */
  200.     register word32 t32;
  201. #endif
  202.     int r = IDEAROUNDS;
  203.  
  204.     in = (word16 *) inbuf;
  205.     x1 = *in++;
  206.     x2 = *in++;
  207.     x3 = *in++;
  208.     x4 = *in;
  209. #ifndef HIGHFIRST
  210.     x1 = (x1 >> 8) | (x1 << 8);
  211.     x2 = (x2 >> 8) | (x2 << 8);
  212.     x3 = (x3 >> 8) | (x3 << 8);
  213.     x4 = (x4 >> 8) | (x4 << 8);
  214. #endif
  215.     do {
  216.     MUL(x1, *key++);
  217.     x2 += *key++;
  218.     x3 += *key++;
  219.     MUL(x4, *key++);
  220.  
  221.     s3 = x3;
  222.     x3 ^= x1;
  223.     MUL(x3, *key++);
  224.     s2 = x2;
  225.     x2 ^= x4;
  226.     x2 += x3;
  227.     MUL(x2, *key++);
  228.     x3 += x2;
  229.  
  230.     x1 ^= x2;
  231.     x4 ^= x3;
  232.  
  233.     x2 ^= s3;
  234.     x3 ^= s2;
  235.     } while (--r);
  236.     MUL(x1, *key++);
  237.     x3 += *key++;
  238.     x2 += *key++;
  239.     MUL(x4, *key);
  240.  
  241.     out = (word16 *) outbuf;
  242. #ifdef HIGHFIRST
  243.     *out++ = x1;
  244.     *out++ = x3;
  245.     *out++ = x2;
  246.     *out = x4;
  247. #else                /* !HIGHFIRST */
  248.     x1 = low16(x1);
  249.     x2 = low16(x2);
  250.     x3 = low16(x3);
  251.     x4 = low16(x4);
  252.     *out++ = (x1 >> 8) | (x1 << 8);
  253.     *out++ = (x3 >> 8) | (x3 << 8);
  254.     *out++ = (x2 >> 8) | (x2 << 8);
  255.     *out = (x4 >> 8) | (x4 << 8);
  256. #endif
  257. }                /* ideaCipher */
  258.  
  259. /*************************************************************************/
  260.  
  261. void ideaCfbReinit(struct IdeaCfbContext *context, byte const *iv)
  262. {
  263.     if (iv)
  264.     memcpy(context->iv, iv, 8);
  265.     else
  266.     memset(context->iv, 0, 8);
  267.     context->bufleft = 0;
  268. }
  269.  
  270. void ideaCfbInit(struct IdeaCfbContext *context, byte const key[16])
  271. {
  272.     ideaExpandKey(key, context->key);
  273.     ideaCfbReinit(context, 0);
  274. }
  275.  
  276. void ideaCfbDestroy(struct IdeaCfbContext *context)
  277. {
  278.     memset(context, 0, sizeof(context));
  279. }
  280.  
  281. /*
  282.  * Okay, explanation time:
  283.  * Phil invented a unique way of doing CFB that's sensitive to semantic
  284.  * boundaries within the data being encrypted.  One way to phrase
  285.  * CFB en/decryption is to say that you XOR the current 8 bytes with
  286.  * IDEA(previous 8 bytes of ciphertext).  Normally, you repeat this
  287.  * at 8-byte intervals, but Phil decided to resync things on the
  288.  * boundaries between elements in the stream being encrypted.
  289.  *
  290.  * That is, the last 4 bytes of a 12-byte field are en/decrypted using
  291.  * the first 4 bytes of IDEA(previous 8 bytes of ciphertext), but then
  292.  * the last 4 bytes of that IDEA computation are thrown away, and the
  293.  * first 8 bytes of the next field are en/decrypted using
  294.  * IDEA(last 8 bytes of ciphertext).  This is equivalent to using a
  295.  * shorter feedback length (if you're familiar with the general CFB
  296.  * technique) briefly, and doesn't weaken the cipher any (using shorter
  297.  * CFB lengths makes it stronger, actually), it just makes it a bit unusual.
  298.  *
  299.  * Anyway, to accomodate this behaviour, every time we do an IDEA
  300.  * encrpytion of 8 bytes of ciphertext to get 8 bytes of XOR mask,
  301.  * we remember the ciphertext.  Then if we have to resync things
  302.  * after having processed, say, 2 bytes, we refill the iv buffer
  303.  * with the last 6 bytes of the old ciphertext followed by the
  304.  * 2 bytes of new ciphertext stored in the front of the iv buffer.
  305.  */
  306. void ideaCfbSync(struct IdeaCfbContext *context)
  307. {
  308.     int bufleft = context->bufleft;
  309.  
  310.     if (bufleft) {
  311.     memmove(context->iv + bufleft, context->iv, 8 - bufleft);
  312.     memcpy(context->iv, context->oldcipher + 8 - bufleft, bufleft);
  313.     context->bufleft = 0;
  314.     }
  315. }
  316.  
  317. /*
  318.  * Encrypt a buffer of data, using IDEA in CFB mode.
  319.  * There are more compact ways of writing this, but this is
  320.  * written for speed.
  321.  */
  322. void ideaCfbEncrypt(struct IdeaCfbContext *context, byte const *src,
  323.             byte * dest, int count)
  324. {
  325.     int bufleft = context->bufleft;
  326.     byte *bufptr = context->iv + 8 - bufleft;
  327.  
  328.     /* If there are no more bytes to encrypt that there are bytes
  329.      * in the buffer, XOR them in and return.
  330.      */
  331.     if (count <= bufleft) {
  332.     context->bufleft = bufleft - count;
  333.     while (count--) {
  334.         *dest++ = *bufptr++ ^= *src++;
  335.     }
  336.     return;
  337.     }
  338.     count -= bufleft;
  339.     /* Encrypt the first bufleft (0 to 7) bytes of the input by XOR
  340.      * with the last bufleft bytes in the iv buffer.
  341.      */
  342.     while (bufleft--) {
  343.     *dest++ = (*bufptr++ ^= *src++);
  344.     }
  345.     /* Encrypt middle blocks of the input by cranking the cipher,
  346.      * XORing 8-byte blocks, and repeating until the count
  347.      * is 8 or less.
  348.      */
  349.     while (count > 8) {
  350.     bufptr = context->iv;
  351.     memcpy(context->oldcipher, bufptr, 8);
  352.     ideaCipher(bufptr, bufptr, context->key);
  353.     bufleft = 8;
  354.     count -= 8;
  355.     do {
  356.         *dest++ = (*bufptr++ ^= *src++);
  357.     } while (--bufleft);
  358.     }
  359.     /* Do the last 1 to 8 bytes */
  360.     bufptr = context->iv;
  361.     memcpy(context->oldcipher, bufptr, 8);
  362.     ideaCipher(bufptr, bufptr, context->key);
  363.     context->bufleft = 8 - count;
  364.     do {
  365.     *dest++ = (*bufptr++ ^= *src++);
  366.     } while (--count);
  367. }
  368.  
  369.  
  370. /*
  371.  * Decrypt a buffer of data, using IDEA in CFB mode.
  372.  * There are more compact ways of writing this, but this is
  373.  * written for speed.
  374.  */
  375. void ideaCfbDecrypt(struct IdeaCfbContext *context, byte const *src,
  376.             byte * dest, int count)
  377. {
  378.     int bufleft = context->bufleft;
  379.     static byte *bufptr;
  380.     byte t;
  381.  
  382.     bufptr = context->iv + (8 - bufleft);
  383.     if (count <= bufleft) {
  384.     context->bufleft = bufleft - count;
  385.     while (count--) {
  386.         t = *bufptr;
  387.         *dest++ = t ^ (*bufptr++ = *src++);
  388.     }
  389.     return;
  390.     }
  391.     count -= bufleft;
  392.     while (bufleft--) {
  393.     t = *bufptr;
  394.     *dest++ = t ^ (*bufptr++ = *src++);
  395.     }
  396.     while (count > 8) {
  397.     bufptr = context->iv;
  398.     memcpy(context->oldcipher, bufptr, 8);
  399.     ideaCipher(bufptr, bufptr, context->key);
  400.     bufleft = 8;
  401.     count -= 8;
  402.     do {
  403.         t = *bufptr;
  404.         *dest++ = t ^ (*bufptr++ = *src++);
  405.     } while (--bufleft);
  406.     }
  407.     bufptr = context->iv;
  408.     memcpy(context->oldcipher, bufptr, 8);
  409.     ideaCipher(bufptr, bufptr, context->key);
  410.     context->bufleft = 8 - count;
  411.     do {
  412.     t = *bufptr;
  413.     *dest++ = t ^ (*bufptr++ = *src++);
  414.     } while (--count);
  415. }
  416.  
  417. /* end of idea.c */
  418.