home *** CD-ROM | disk | FTP | other *** search
/ Hacker / Hacker.iso / HACKER / CRACK / PGPCRACK / IDEA.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-04-27  |  16.4 KB  |  593 lines
  1. /*
  2.  *    idea.c - C source code for IDEA block cipher.
  3.  *      IDEA (International Data Encryption Algorithm), formerly known as 
  4.  *      IPES (Improved Proposed Encryption Standard).
  5.  *      Algorithm developed by Xuejia Lai and James L. Massey, of ETH Zurich.
  6.  *      This implementation modified and derived from original C code 
  7.  *      developed by Xuejia Lai.  
  8.  *      Zero-based indexing added, names changed from IPES to IDEA.
  9.  *      CFB functions added.  Random number routines added.
  10.  *
  11.  *      Extensively optimized and restructured by Colin Plumb.
  12.  *
  13.  *      There are two adjustments that can be made to this code to
  14.  *      speed it up.  Defaults may be used for PCs.  Only the -DIDEA32
  15.  *      pays off significantly if selectively set or not set.
  16.  *      Experiment to see what works best for your machine.
  17.  *
  18.  *      Multiplication: default is inline, -DAVOID_JUMPS uses a
  19.  *              different version that does not do any conditional
  20.  *              jumps (a few percent worse on a SPARC), while
  21.  *              -DSMALL_CACHE takes it out of line to stay
  22.  *              within a small on-chip code cache.
  23.  *      Variables: normally, 16-bit variables are used, but some
  24.  *              machines (notably RISCs) do not have 16-bit registers,
  25.  *              so they do a great deal of masking.  -DIDEA32 uses "int"
  26.  *              register variables and masks explicitly only where
  27.  *              necessary.  On a SPARC, for example, this boosts
  28.  *              performace by 30%.
  29.  *
  30.  *      The IDEA(tm) block cipher is covered by patents held by ETH and a
  31.  *      Swiss company called Ascom-Tech AG.  The Swiss patent number is
  32.  *      PCT/CH91/00117, the European patent number is EP 0 482 154 B1, and
  33.  *      the U.S. patent number is US005214703.  IDEA(tm) is a trademark of
  34.  *      Ascom-Tech AG.  There is no license fee required for noncommercial
  35.  *      use.  Commercial users may obtain licensing details from Dieter
  36.  *      Profos, Ascom Tech AG, Solothurn Lab, Postfach 151, 4502 Solothurn,
  37.  *      Switzerland, Tel +41 65 242885, Fax +41 65 235761.
  38.  *
  39.  *      The IDEA block cipher uses a 64-bit block size, and a 128-bit key 
  40.  *      size.  It breaks the 64-bit cipher block into four 16-bit words
  41.  *      because all of the primitive inner operations are done with 16-bit 
  42.  *      arithmetic.  It likewise breaks the 128-bit cipher key into eight 
  43.  *      16-bit words.
  44.  *
  45.  *      For further information on the IDEA cipher, see the book:
  46.  *        Xuejia Lai, "On the Design and Security of Block Ciphers",
  47.  *        ETH Series on Information Processing (ed. J.L. Massey) Vol 1,
  48.  *        Hartung-Gorre Verlag, Konstanz, Switzerland, 1992.  ISBN
  49.  *        3-89191-573-X.
  50.  *
  51.  *      This code runs on arrays of bytes by taking pairs in big-endian
  52.  *      order to make the 16-bit words that IDEA uses internally.  This
  53.  *      produces the same result regardless of the byte order of the
  54.  *      native CPU.
  55.  */
  56.  
  57. #include <string.h>
  58. #include "idea.h"
  59.  
  60. #ifdef MACTC5
  61. #include <string.h>
  62. #define IDEA32
  63. #define SMALL_CACHE
  64. #define USE68ASM
  65. void ideaCipher(byte const inbuf[8], byte outbuf[8],
  66.                word16 const *key);
  67. #endif
  68.  
  69. #ifdef IDEA32            /* Use >16-bit temporaries */
  70. #define low16(x) ((x) & 0xFFFF)
  71. typedef unsigned int uint16;    /* at LEAST 16 bits, maybe more */
  72. #else
  73. #define low16(x) (x)        /* this is only ever applied to uint16's */
  74. typedef word16 uint16;
  75. #endif
  76.  
  77. #ifdef _GNUC_
  78. /* __const__ simply means there are no side effects for this function,
  79.  * which is useful info for the gcc optimizer
  80.  */
  81. #define CONST __const__
  82. #else
  83. #define CONST
  84. #endif
  85.  
  86. /*
  87.  * Multiplication, modulo (2**16)+1
  88.  * Note that this code is structured on the assumption that
  89.  * untaken branches are cheaper than taken branches, and the
  90.  * compiler doesn't schedule branches.
  91.  */
  92. #ifdef SMALL_CACHE
  93. #ifdef MACTC5
  94.  
  95. CONST static uint16 
  96. mul(uint16 a, uint16 b) {
  97. asm {
  98.         move.w    a,d1
  99.         beq.s    @aeq0
  100.         move.w    b,d0
  101.         beq.s    @beq0
  102.         mulu.w    d0,d1    ; a = a * b
  103.         move.w    d1,d0    ; b = a
  104.         swap    d1        ; a = a >> 16
  105.         sub.w    d1,d0    ; b = b - a
  106.         bcc.s    @endit    ; b >= a?
  107.         addq.w    #1,d0    ; b < a : (b - a) + 1
  108.         bra.s    @endit
  109. @aeq0:    moveq    #1,d0
  110.         move.w    b,d1
  111.         sub.w    d1,d0    ; 1 - b
  112.         bra.s    @endit
  113. @beq0:    moveq    #1,d0
  114.         sub.w    d1,d0    ; 1 - a
  115.         }
  116. endit:    return;
  117. }
  118.  
  119. #else
  120.  
  121. CONST static uint16
  122.  mul(register uint16 a, register uint16 b)
  123. {
  124.     register word32 p;
  125.  
  126.     p = (word32) a *b;
  127.     if (p) {
  128.     b = low16(p);
  129.     a = p >> 16;
  130.     return (b - a) + (b < a);
  131.     } else if (a) {
  132.     return 1 - a;
  133.     } else {
  134.     return 1 - b;
  135.     }
  136. }                /* mul */
  137. #endif            /* MACTC5 */
  138. #endif            /* SMALL_CACHE */
  139.  
  140. /*
  141.  * Compute the multiplicative inverse of x, modulo 65537, using Euclid's
  142.  * algorithm. It is unrolled twice to avoid swapping the registers each
  143.  * iteration, and some subtracts of t have been changed to adds.
  144.  */
  145. CONST static uint16
  146.  mulInv(uint16 x)
  147. {
  148.     uint16 t0, t1;
  149.     uint16 q, y;
  150.  
  151.     if (x <= 1)
  152.     return x;        /* 0 and 1 are self-inverse */
  153.     t1 = 0x10001L / x;        /* Since x >= 2, this fits into 16 bits */
  154.     y = 0x10001L % x;
  155.     if (y == 1)
  156.     return low16(1 - t1);
  157.     t0 = 1;
  158.     do {
  159.     q = x / y;
  160.     x = x % y;
  161.     t0 += q * t1;
  162.     if (x == 1)
  163.         return t0;
  164.     q = y / x;
  165.     y = y % x;
  166.     t1 += q * t0;
  167.     } while (y != 1);
  168.     return low16(1 - t1);
  169. }                /* mukInv */
  170.  
  171. /*
  172.  * Expand a 128-bit user key to a working encryption key EK
  173.  */
  174. static void ideaExpandKey(byte const *userkey, word16 * EK)
  175. {
  176.     int i, j;
  177.  
  178.     for (j = 0; j < 8; j++) {
  179.     EK[j] = (userkey[0] << 8) + userkey[1];
  180.     userkey += 2;
  181.     }
  182.     for (i = 0; j < IDEAKEYLEN; j++) {
  183.     i++;
  184.     EK[i + 7] = EK[i & 7] << 9 | EK[i + 1 & 7] >> 7;
  185.     EK += i & 8;
  186.     i &= 7;
  187.     }
  188. }                /* ideaExpandKey */
  189.  
  190. /*
  191.  * Compute IDEA decryption key DK from an expanded IDEA encryption key EK
  192.  * Note that the input and output may be the same.  Thus, the key is
  193.  * inverted into an internal buffer, and then copied to the output.
  194.  */
  195. static void ideaInvertKey(word16 const *EK, word16 DK[IDEAKEYLEN])
  196. {
  197.     int i;
  198.     uint16 t1, t2, t3;
  199.     word16 temp[IDEAKEYLEN];
  200.     word16 *p = temp + IDEAKEYLEN;
  201.  
  202.     t1 = mulInv(*EK++);
  203.     t2 = -*EK++;
  204.     t3 = -*EK++;
  205.     *--p = mulInv(*EK++);
  206.     *--p = t3;
  207.     *--p = t2;
  208.     *--p = t1;
  209.  
  210.     for (i = 0; i < IDEAROUNDS - 1; i++) {
  211.     t1 = *EK++;
  212.     *--p = *EK++;
  213.     *--p = t1;
  214.  
  215.     t1 = mulInv(*EK++);
  216.     t2 = -*EK++;
  217.     t3 = -*EK++;
  218.     *--p = mulInv(*EK++);
  219.     *--p = t2;
  220.     *--p = t3;
  221.     *--p = t1;
  222.     }
  223.     t1 = *EK++;
  224.     *--p = *EK++;
  225.     *--p = t1;
  226.  
  227.     t1 = mulInv(*EK++);
  228.     t2 = -*EK++;
  229.     t3 = -*EK++;
  230.     *--p = mulInv(*EK++);
  231.     *--p = t3;
  232.     *--p = t2;
  233.     *--p = t1;
  234. /* Copy and destroy temp copy */
  235.     memcpy(DK, temp, sizeof(temp));
  236.     burn(temp);
  237. }                /* ideaInvertKey */
  238.  
  239. /*
  240.  * MUL(x,y) computes x = x*y, modulo 0x10001.  Requires two temps, 
  241.  * t16 and t32.  x is modified, and must be a side-effect-free lvalue.
  242.  * y may be anything, but unlike x, must be strictly less than 65536 
  243.  * even if low16() is #defined.
  244.  * All of these are equivalent - see which is faster on your machine
  245.  */
  246. #ifdef SMALL_CACHE
  247. #define MUL(x,y) (x = mul(low16(x),y))
  248. #else                /* !SMALL_CACHE */
  249. #ifdef AVOID_JUMPS
  250. #define MUL(x,y) (x = low16(x-1), t16 = low16((y)-1), \
  251.         t32 = (word32)x*t16 + x + t16, x = low16(t32), \
  252.         t16 = t32>>16, x = (x-t16) + (x<t16) + 1)
  253. #else                /* !AVOID_JUMPS (default) */
  254. #define MUL(x,y) \
  255.     ((t16 = (y)) ? \
  256.         (x=low16(x)) ? \
  257.             t32 = (word32)x*t16, \
  258.             x = low16(t32), \
  259.             t16 = t32>>16, \
  260.             x = (x-t16)+(x<t16) \
  261.         : \
  262.             (x = 1-t16) \
  263.     : \
  264.         (x = 1-x))
  265. #endif
  266. #endif
  267.  
  268. /*      IDEA encryption/decryption algorithm */
  269. /* Note that in and out can be the same buffer */
  270. #ifndef USE68ASM
  271. static void ideaCipher(byte const inbuf[8], byte outbuf[8],
  272.                word16 const *key)
  273. {
  274.     register uint16 x1, x2, x3, x4, s2, s3;
  275.     word16 *in, *out;
  276. #ifndef SMALL_CACHE
  277.     register uint16 t16;    /* Temporaries needed by MUL macro */
  278.     register word32 t32;
  279. #endif
  280.     int r = IDEAROUNDS;
  281.  
  282.     in = (word16 *) inbuf;
  283.     x1 = *in++;
  284.     x2 = *in++;
  285.     x3 = *in++;
  286.     x4 = *in;
  287. #ifndef HIGHFIRST
  288.     x1 = (x1 >> 8) | (x1 << 8);
  289.     x2 = (x2 >> 8) | (x2 << 8);
  290.     x3 = (x3 >> 8) | (x3 << 8);
  291.     x4 = (x4 >> 8) | (x4 << 8);
  292. #endif
  293.     do {
  294.     MUL(x1, *key++);
  295.     x2 += *key++;
  296.     x3 += *key++;
  297.     MUL(x4, *key++);
  298.  
  299.     s3 = x3;
  300.     x3 ^= x1;
  301.     MUL(x3, *key++);
  302.     s2 = x2;
  303.     x2 ^= x4;
  304.     x2 += x3;
  305.     MUL(x2, *key++);
  306.     x3 += x2;
  307.  
  308.     x1 ^= x2;
  309.     x4 ^= x3;
  310.  
  311.     x2 ^= s3;
  312.     x3 ^= s2;
  313.     } while (--r);
  314.     MUL(x1, *key++);
  315.     x3 += *key++;
  316.     x2 += *key++;
  317.     MUL(x4, *key);
  318.  
  319.     out = (word16 *) outbuf;
  320. #ifdef HIGHFIRST
  321.     *out++ = x1;
  322.     *out++ = x3;
  323.     *out++ = x2;
  324.     *out = x4;
  325. #else                /* !HIGHFIRST */
  326.     x1 = low16(x1);
  327.     x2 = low16(x2);
  328.     x3 = low16(x3);
  329.     x4 = low16(x4);
  330.     *out++ = (x1 >> 8) | (x1 << 8);
  331.     *out++ = (x3 >> 8) | (x3 << 8);
  332.     *out++ = (x2 >> 8) | (x2 << 8);
  333.     *out = (x4 >> 8) | (x4 << 8);
  334. #endif
  335. }                /* ideaCipher */
  336. #endif            /* USE68ASM */
  337.  
  338. /*-------------------------------------------------------------*/
  339.  
  340. #ifdef TEST
  341.  
  342. #include <stdio.h>
  343. #include <time.h>
  344. /*
  345.  * This is the number of Kbytes of test data to encrypt.
  346.  * It defaults to 1 MByte.
  347.  */
  348. #ifndef BLOCKS
  349. #ifndef KBYTES
  350. #define KBYTES 1024
  351. #endif
  352. #define BLOCKS (64*KBYTES)
  353. #endif
  354.  
  355. int main(void)
  356. {                /* Test driver for IDEA cipher */
  357.     int i, j, k;
  358.     byte userkey[16];
  359.     word16 EK[IDEAKEYLEN], DK[IDEAKEYLEN];
  360.     byte XX[8], YY[8], ZZ[8];
  361.     clock_t start, end;
  362.     long l;
  363.  
  364.     /* Make a sample user key for testing... */
  365.     for (i = 0; i < 16; i++)
  366.     userkey[i] = i + 1;
  367.  
  368.     /* Compute encryption subkeys from user key... */
  369.     ideaExpandKey(userkey, EK);
  370.     printf("\nEncryption key subblocks: ");
  371.     for (j = 0; j < IDEAROUNDS + 1; j++) {
  372.     printf("\nround %d:   ", j + 1);
  373.     if (j < IDEAROUNDS)
  374.         for (i = 0; i < 6; i++)
  375.         printf(" %6u", EK[j * 6 + i]);
  376.     else
  377.         for (i = 0; i < 4; i++)
  378.         printf(" %6u", EK[j * 6 + i]);
  379.     }
  380.  
  381.     /* Compute decryption subkeys from encryption subkeys... */
  382.     ideaInvertKey(EK, DK);
  383.     printf("\nDecryption key subblocks: ");
  384.     for (j = 0; j < IDEAROUNDS + 1; j++) {
  385.     printf("\nround %d:   ", j + 1);
  386.     if (j < IDEAROUNDS)
  387.         for (i = 0; i < 6; i++)
  388.         printf(" %6u", DK[j * 6 + i]);
  389.     else
  390.         for (i = 0; i < 4; i++)
  391.         printf(" %6u", DK[j * 6 + i]);
  392.     }
  393.  
  394.     /* Make a sample plaintext pattern for testing... */
  395.     for (k = 0; k < 8; k++)
  396.     XX[k] = k;
  397.  
  398.     printf("\n Encrypting %d bytes (%ld blocks)...", BLOCKS * 16, BLOCKS);
  399.     fflush(stdout);
  400.     start = clock();
  401.     memcpy(YY, XX, 8);
  402.     for (l = 0; l < BLOCKS; l++)
  403.     ideaCipher(YY, YY, EK);    /* repeated encryption */
  404.     memcpy(ZZ, YY, 8);
  405.     for (l = 0; l < BLOCKS; l++)
  406.     ideaCipher(ZZ, ZZ, DK);    /* repeated decryption */
  407.     end = clock() - start;
  408.     l = end / (CLOCKS_PER_SEC / 1000) + 1;
  409.     i = l / 1000;
  410.     j = l % 1000;
  411.     l = (16 * BLOCKS * (CLOCKS_PER_SEC / 1000)) / (end / 1000);
  412.     printf("%d.%03d seconds = %ld bytes per second\n", i, j, l);
  413.  
  414.     printf("\nX %3u  %3u  %3u  %3u  %3u  %3u  %3u %3u\n",
  415.        XX[0], XX[1], XX[2], XX[3], XX[4], XX[5], XX[6], XX[7]);
  416.     printf("\nY %3u  %3u  %3u  %3u  %3u  %3u  %3u %3u\n",
  417.        YY[0], YY[1], YY[2], YY[3], YY[4], YY[5], YY[6], YY[7]);
  418.     printf("\nZ %3u  %3u  %3u  %3u  %3u  %3u  %3u %3u\n",
  419.        ZZ[0], ZZ[1], ZZ[2], ZZ[3], ZZ[4], ZZ[5], ZZ[6], ZZ[7]);
  420.  
  421.     /* Now decrypted ZZ should be same as original XX */
  422.     for (k = 0; k < 8; k++)
  423.     if (XX[k] != ZZ[k]) {
  424.         printf("\n\07Error!  Noninvertable encryption.\n");
  425.         exit(-1);        /* error exit */
  426.     }
  427.     printf("\nNormal exit.\n");
  428.     return 0;            /* normal exit */
  429. }                /* main */
  430.  
  431. #endif                /* TEST */
  432.  
  433.  
  434. /*************************************************************************/
  435.  
  436. void ideaCfbReinit(struct IdeaCfbContext *context, byte const *iv)
  437. {
  438.     if (iv)
  439.     memcpy(context->iv, iv, 8);
  440.     else
  441.     fill0(context->iv, 8);
  442.     context->bufleft = 0;
  443. }
  444.  
  445. void ideaCfbInit(struct IdeaCfbContext *context, byte const key[16])
  446. {
  447.     ideaExpandKey(key, context->key);
  448.     ideaCfbReinit(context, 0);
  449. }
  450.  
  451. void ideaCfbDestroy(struct IdeaCfbContext *context)
  452. {
  453.     burn(*context);
  454. }
  455.  
  456. /*
  457.  * Okay, explanation time:
  458.  * Phil invented a unique way of doing CFB that's sensitive to semantic
  459.  * boundaries within the data being encrypted.  One way to phrase
  460.  * CFB en/decryption is to say that you XOR the current 8 bytes with
  461.  * IDEA(previous 8 bytes of ciphertext).  Normally, you repeat this
  462.  * at 8-byte intervals, but Phil decided to resync things on the
  463.  * boundaries between elements in the stream being encrypted.
  464.  *
  465.  * That is, the last 4 bytes of a 12-byte field are en/decrypted using
  466.  * the first 4 bytes of IDEA(previous 8 bytes of ciphertext), but then
  467.  * the last 4 bytes of that IDEA computation are thrown away, and the
  468.  * first 8 bytes of the next field are en/decrypted using
  469.  * IDEA(last 8 bytes of ciphertext).  This is equivalent to using a
  470.  * shorter feedback length (if you're familiar with the general CFB
  471.  * technique) briefly, and doesn't weaken the cipher any (using shorter
  472.  * CFB lengths makes it stronger, actually), it just makes it a bit unusual.
  473.  *
  474.  * Anyway, to accomodate this behaviour, every time we do an IDEA
  475.  * encrpytion of 8 bytes of ciphertext to get 8 bytes of XOR mask,
  476.  * we remember the ciphertext.  Then if we have to resync things
  477.  * after having processed, say, 2 bytes, we refill the iv buffer
  478.  * with the last 6 bytes of the old ciphertext followed by the
  479.  * 2 bytes of new ciphertext stored in the front of the iv buffer.
  480.  */
  481. void ideaCfbSync(struct IdeaCfbContext *context)
  482. {
  483.     int bufleft = context->bufleft;
  484.  
  485.     if (bufleft) {
  486.     memmove(context->iv + bufleft, context->iv, 8 - bufleft);
  487.     memcpy(context->iv, context->oldcipher + 8 - bufleft, bufleft);
  488.     context->bufleft = 0;
  489.     }
  490. }
  491.  
  492. /*
  493.  * Encrypt a buffer of data, using IDEA in CFB mode.
  494.  * There are more compact ways of writing this, but this is
  495.  * written for speed.
  496.  */
  497. void ideaCfbEncrypt(struct IdeaCfbContext *context, byte const *src,
  498.             byte * dest, int count)
  499. {
  500.     int bufleft = context->bufleft;
  501.     byte *bufptr = context->iv + 8 - bufleft;
  502.  
  503.     /* If there are no more bytes to encrypt that there are bytes
  504.      * in the buffer, XOR them in and return.
  505.      */
  506.     if (count <= bufleft) {
  507.     context->bufleft = bufleft - count;
  508.     while (count--) {
  509.         *dest++ = *bufptr++ ^= *src++;
  510.     }
  511.     return;
  512.     }
  513.     count -= bufleft;
  514.     /* Encrypt the first bufleft (0 to 7) bytes of the input by XOR
  515.      * with the last bufleft bytes in the iv buffer.
  516.      */
  517.     while (bufleft--) {
  518.     *dest++ = (*bufptr++ ^= *src++);
  519.     }
  520.     /* Encrypt middle blocks of the input by cranking the cipher,
  521.      * XORing 8-byte blocks, and repeating until the count
  522.      * is 8 or less.
  523.      */
  524.     while (count > 8) {
  525.     bufptr = context->iv;
  526.     memcpy(context->oldcipher, bufptr, 8);
  527.     ideaCipher(bufptr, bufptr, context->key);
  528.     bufleft = 8;
  529.     count -= 8;
  530.     do {
  531.         *dest++ = (*bufptr++ ^= *src++);
  532.     } while (--bufleft);
  533.     }
  534.     /* Do the last 1 to 8 bytes */
  535.     bufptr = context->iv;
  536.     memcpy(context->oldcipher, bufptr, 8);
  537.     ideaCipher(bufptr, bufptr, context->key);
  538.     context->bufleft = 8 - count;
  539.     do {
  540.     *dest++ = (*bufptr++ ^= *src++);
  541.     } while (--count);
  542. }
  543.  
  544.  
  545. /*
  546.  * Decrypt a buffer of data, using IDEA in CFB mode.
  547.  * There are more compact ways of writing this, but this is
  548.  * written for speed.
  549.  */
  550. void ideaCfbDecrypt(struct IdeaCfbContext *context, byte const *src,
  551.             byte * dest, int count)
  552. {
  553.     int bufleft = context->bufleft;
  554.     static byte *bufptr;
  555.     byte t;
  556.  
  557.     bufptr = context->iv + (8 - bufleft);
  558.     if (count <= bufleft) {
  559.     context->bufleft = bufleft - count;
  560.     while (count--) {
  561.         t = *bufptr;
  562.         *dest++ = t ^ (*bufptr++ = *src++);
  563.     }
  564.     return;
  565.     }
  566.     count -= bufleft;
  567.     while (bufleft--) {
  568.     t = *bufptr;
  569.     *dest++ = t ^ (*bufptr++ = *src++);
  570.     }
  571.     while (count > 8) {
  572.     bufptr = context->iv;
  573.     memcpy(context->oldcipher, bufptr, 8);
  574.     ideaCipher(bufptr, bufptr, context->key);
  575.     bufleft = 8;
  576.     count -= 8;
  577.     do {
  578.         t = *bufptr;
  579.         *dest++ = t ^ (*bufptr++ = *src++);
  580.     } while (--bufleft);
  581.     }
  582.     bufptr = context->iv;
  583.     memcpy(context->oldcipher, bufptr, 8);
  584.     ideaCipher(bufptr, bufptr, context->key);
  585.     context->bufleft = 8 - count;
  586.     do {
  587.     t = *bufptr;
  588.     *dest++ = t ^ (*bufptr++ = *src++);
  589.     } while (--count);
  590. }
  591.  
  592. /* end of idea.c */
  593.