home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: Security / Security.zip / idea-v11.zip / idea.c < prev    next >
C/C++ Source or Header  |  1993-11-16  |  8KB  |  206 lines
  1. /******************************************************************************/
  2. /*                                                                            */
  3. /* I N T E R N A T I O N A L  D A T A  E N C R Y P T I O N  A L G O R I T H M */
  4. /*                                                                            */
  5. /******************************************************************************/
  6. /* Author:       Richard De Moliner (demoliner@isi.ee.ethz.ch)                */
  7. /*               Signal and Information Processing Laboratory                 */
  8. /*               Swiss Federal Institute of Technology                        */
  9. /*               CH-8092 Zuerich, Switzerland                                 */
  10. /* Created:      April 23, 1992                                               */
  11. /* Changes:      November 16, 1993 (support of ANSI-C and C++)                */
  12. /* System:       SUN SPARCstation, SUN acc ANSI-C-Compiler, SUN-OS 4.1.3      */
  13. /******************************************************************************/
  14. #include "idea.h"
  15.  
  16. #define mulMod        0x10001 /* 2**16 + 1                                    */
  17. #define ones           0xFFFF /* 2**16 - 1                                    */
  18.  
  19. /******************************************************************************/
  20. /* Multiplication in the multiplicative group, a = a * b                      */
  21. /* pre:  0 <= a <= 0xFFFF.                                                    */
  22. /*       0 <= b <= 0xFFFF.                                                    */
  23. /* post: 'a' and 'b' have been modified.                                      */
  24. /*       a = a * b; where '*' is multiplication in the multiplicative group.  */
  25. /* note: This implementation of '*' is not complete. To bee complete the      */
  26. /*       result has to bee masked (MUL(a, b); a &= ones;).                    */
  27.  
  28. #define Mul(a, b)                                                              \
  29.   if (a == 0) a = mulMod - b;                                                  \
  30.   else if (b == 0) a = mulMod - a;                                             \
  31.   else {                                                                       \
  32.     a *= b;                                                                    \
  33.     if ((a & ones) >= (b = a >> 16)) a -= b;                                   \
  34.     else a += mulMod - b;                                                      \
  35.   } /* Mul */
  36.  
  37. /******************************************************************************/
  38. /* Encryption and decryption algorithm IDEA. Depending on the value of 'key'  */
  39. /* 'Idea_Crypt' either encrypts or decrypts 'dataIn'. The result is stored    */
  40. /* in 'dataOut'.                                                              */
  41. /* pre:  'dataIn'  contains the plain/cipher-text block.                      */
  42. /*       'key'     contains the encryption/decryption key.                    */
  43. /* post: 'dataOut' contains the cipher/plain-text block.                      */
  44.  
  45. #ifdef ANSI_C
  46.   void Idea_Crypt (Idea_Data dataIn, Idea_Data dataOut, Idea_Key key)
  47. #else
  48.   Idea_Crypt (dataIn, dataOut, key)
  49.   Idea_Data dataIn;
  50.   Idea_Data dataOut;
  51.   Idea_Key key;
  52. #endif
  53.  
  54. { register u_int32 x0, x1, x2, x3, t0, t1, t2;
  55.   int round;
  56.  
  57.   x0 = (u_int32)*dataIn++; x1 = (u_int32)*dataIn++;
  58.   x2 = (u_int32)*dataIn++; x3 = (u_int32)*dataIn;
  59.   for (round = Idea_nofRound; round > 0; round--) {
  60.     t1 = (u_int32)*key++;
  61.     x1 += (u_int32)*key++;
  62.     x2 += (u_int32)*key++; x2 &= ones;
  63.     t2 = (u_int32)*key++;
  64.     Mul(x0, t1); x0 &= ones;
  65.     Mul(x3, t2);
  66.     t0 = (u_int32)*key++;
  67.     t1 = x0 ^ x2;
  68.     Mul(t0, t1); t0 &= ones;
  69.     t1 = (u_int32)*key++;
  70.     t2 = (x1 ^ x3) + t0 & ones;
  71.     Mul(t1, t2); t1 &= ones;
  72.     t0 += t1;
  73.     x0 ^= t1; x3 ^= t0; x3 &= ones;
  74.     t0 ^= x1; x1 = x2 ^ t1; x2 = t0;
  75.   }
  76.   t0 = (u_int32)*key++;
  77.   Mul(x0, t0);
  78.   *dataOut++ = (u_int16)(x0 & ones);
  79.   *dataOut++ = (u_int16)((u_int32)*key++ + x2 & ones);
  80.   *dataOut++ = (u_int16)((u_int32)*key++ + x1 & ones);
  81.   t0 = (u_int32)*key;
  82.   Mul(x3, t0);
  83.   *dataOut = (u_int16)(x3 & ones);
  84. } /* Idea_Crypt */
  85.  
  86. /******************************************************************************/
  87. /* Multiplicative Inverse by Extended Stein Greatest Common Divisor Algorithm.*/
  88. /* pre:  0 <= x <= 0xFFFF.                                                    */
  89. /* post: x * MulInv(x) == 1, where '*' is multiplication in the               */
  90. /*                           multiplicative group.                            */
  91.  
  92. #ifdef ANSI_C
  93.   static u_int16 MulInv (u_int16 x)
  94. #else
  95.   static u_int16 MulInv (x)
  96.   u_int16 x;
  97. #endif
  98.  
  99. { register int32 n1, n2, N, a1, a2, b1, b2;
  100.  
  101.   if (x <= 1) return x;
  102.   n1 = N = (int32)x; n2 = mulMod;
  103.   a1 = b2 = 1; a2 = b1 = 0;
  104.   do {
  105.     while ((n1 & 1) == 0) {
  106.       if (a1 & 1)
  107.         if (a1 < 0) { a1 += mulMod; b1 -= N; }
  108.         else { a1 -= mulMod; b1 += N; }
  109.       n1 >>= 1; a1 >>= 1; b1 >>= 1;
  110.     }
  111.     if (n1 < n2)
  112.       do {
  113.         n2 -= n1; a2 -= a1; b2 -= b1;
  114.         if (n2 == 0) return (u_int16)(a1 < 0 ? a1 + mulMod : a1);
  115.         while ((n2 & 1) == 0) {
  116.           if (a2 & 1)
  117.             if (a2 < 0) { a2 += mulMod; b2 -= N; }
  118.             else { a2 -= mulMod; b2 += N; }
  119.           n2 >>= 1; a2 >>= 1; b2 >>= 1;
  120.         }
  121.       } while (n1 <= n2);
  122.     n1 -= n2; a1 -= a2; b1 -= b2;
  123.   } while (n1);
  124.   return (u_int16)(a2 < 0 ? a2 + mulMod : a2);
  125. } /* MulInv */
  126.  
  127. /******************************************************************************/
  128. /* Additive Inverse.                                                          */
  129. /* pre:  0 <= x <= 0xFFFF.                                                    */
  130. /* post: x + AddInv(x) == 0, where '+' is addition in the additive group.     */
  131.  
  132. #define AddInv(x)  (-x & ones)
  133.  
  134. /******************************************************************************/
  135. /* Inverts a decryption/encrytion key to a encrytion/decryption key.          */
  136. /* pre:  'key'    contains the encryption/decryption key.                     */
  137. /* post: 'invKey' contains the decryption/encryption key.                     */
  138.  
  139. #ifdef ANSI_C
  140.   void Idea_InvertKey (Idea_Key key, Idea_Key invKey)
  141. #else
  142.   Idea_InvertKey (key, invKey)
  143.   Idea_Key key;
  144.   Idea_Key invKey;
  145. #endif
  146.  
  147. { register u_int16 t, *in, *out;
  148.   register int lo, hi, i;
  149.  
  150.   in = key; out = invKey;
  151.   lo = 0; hi = 6 * Idea_nofRound;
  152.   t = MulInv(in[lo]); out[lo++] = MulInv(in[hi]); out[hi++] = t;
  153.   t = AddInv(in[lo]); out[lo++] = AddInv(in[hi]); out[hi++] = t;
  154.   t = AddInv(in[lo]); out[lo++] = AddInv(in[hi]); out[hi++] = t;
  155.   t = MulInv(in[lo]); out[lo++] = MulInv(in[hi]); out[hi] = t;
  156.   for (i = (Idea_nofRound - 1) / 2 ; i != 0 ; i --) {
  157.     t = in[lo]; out[lo++] = in[hi -= 5]; out[hi ++] = t;
  158.     t = in[lo]; out[lo++] = in[hi]; out[hi] = t;
  159.     t = MulInv(in[lo]); out[lo++] = MulInv(in[hi -= 5]); out[hi++] = t;
  160.     t = AddInv(in[lo]); out[lo++] = AddInv(in[++hi]); out[hi--] = t;
  161.     t = AddInv(in[lo]); out[lo++] = AddInv(in[hi]); out[hi++] = t;
  162.     t = MulInv(in[lo]); out[lo++] = MulInv(in[++hi]); out[hi] = t;
  163.   }
  164. #if (Idea_nofRound % 2 == 0)
  165.   t = in[lo]; out[lo++] = in[hi -= 5]; out[hi++] = t;
  166.   t = in[lo]; out[lo++] = in[hi]; out[hi] = t;
  167.   out[lo] = MulInv(in[lo]); lo++;
  168.   t = AddInv(in[lo]); out[lo] = AddInv(in[lo + 1]); lo++; out[lo++] = t;
  169.   out[lo] = MulInv(in[lo]);
  170. #else
  171.   out[lo] = in[lo]; lo++;
  172.   out[lo] = in[lo];
  173. #endif
  174. } /* Idea_InvertKey */
  175.  
  176. /******************************************************************************/
  177. /* Expands a user key of 128 bits to a full encryption key                    */
  178. /* pre:  'userKey' contains the 128 bit user key                              */
  179. /* post: 'key'     contains the encryption key                                */
  180.  
  181. #ifdef ANSI_C
  182.   void Idea_ExpandUserKey (Idea_UserKey userKey, Idea_Key key)
  183. #else
  184.   Idea_ExpandUserKey (userKey, key)
  185.   Idea_UserKey userKey;
  186.   Idea_Key key;
  187. #endif
  188.  
  189. { register int i;
  190.  
  191. #if (Idea_keyLen <= Idea_userKeyLen)
  192.   for (i = 0; i < Idea_keyLen; i++) key[i] = userKey[i];
  193. #else
  194.   for (i = 0; i < Idea_userKeyLen; i++) key[i] = userKey[i];
  195.   for (i = Idea_userKeyLen; i < Idea_keyLen; i++)
  196.     if ((i & 7) < 6)
  197.       key[i] = (key[i - 7] & 127) << 9 | key[i - 6] >> 7;
  198.     else if ((i & 7) == 6)
  199.       key[i] = (key[i - 7] & 127) << 9 | key[i - 14] >> 7; 
  200.     else
  201.       key[i] = (key[i - 15] & 127) << 9 | key[i - 14] >> 7; 
  202. #endif
  203. } /* Idea_ExpandUserKey */
  204.  
  205. /******************************************************************************/
  206.