|
|
1.1 ! root 1: /* idea.c - C source code for IDEA block cipher. ! 2: IDEA (International Data Encryption Algorithm), formerly known as ! 3: IPES (Improved Proposed Encryption Standard). ! 4: Algorithm developed by Xuejia Lai and James L. Massey, of ETH Zurich. ! 5: This implementation modified and derived from original C code ! 6: developed by Xuejia Lai. Last modified 8 July 92. ! 7: ! 8: Zero-based indexing added, names changed from IPES to IDEA. ! 9: CFB functions added. Random number routines added. ! 10: ! 11: The IDEA(tm) block cipher is covered by a patent held by ETH and a ! 12: Swiss company called Ascom-Tech AG. The Swiss patent number is ! 13: PCT/CH91/00117. International patents are pending. IDEA(tm) is a ! 14: trademark of Ascom-Tech AG. There is no license fee required for ! 15: noncommercial use. Commercial users may obtain licensing details ! 16: from Dieter Profos, Ascom Tech AG, Solothurn Lab, Postfach 151, 4502 ! 17: Solothurn, Switzerland, Tel +41 65 242885, Fax +41 65 235761. ! 18: ! 19: The IDEA block cipher uses a 64-bit block size, and a 128-bit key ! 20: size. It breaks the 64-bit cipher block into four 16-bit words ! 21: because all of the primitive inner operations are done with 16-bit ! 22: arithmetic. It likewise breaks the 128-bit cipher key into eight ! 23: 16-bit words. ! 24: ! 25: For further information on the IDEA cipher, see these papers: ! 26: 1) Xuejia Lai, "Detailed Description and a Software Implementation of ! 27: the IPES Cipher", Institute for Signal and Information ! 28: Processing, ETH-Zentrum, Zurich, Switzerland, 1991 ! 29: 2) Xuejia Lai, James L. Massey, Sean Murphy, "Markov Ciphers and ! 30: Differential Cryptanalysis", Advances in Cryptology- EUROCRYPT'91 ! 31: ! 32: This code assumes that each pair of 8-bit bytes comprising a 16-bit ! 33: word in the key and in the cipher block are externally represented ! 34: with the Most Significant Byte (MSB) first, regardless of the ! 35: internal native byte order of the target CPU. ! 36: ! 37: */ ! 38: #include <stdio.h> ! 39: #include "idea.h" ! 40: ! 41: /* #define lower16(x) ((word16)((x) & mask16)) */ /* unoptimized version */ ! 42: #define lower16(x) ((word16)(x)) /* optimized version */ ! 43: ! 44: #define maxim 0x10001 ! 45: #define fuyi 0x10000 /* Why did Lai pick a name like this? */ ! 46: #define mask16 ((word16) 0xffff) ! 47: #define ROUNDS 8 /* Don't change this value, should be 8 */ ! 48: ! 49: static void en_key_idea(word16 userkey[8], word16 Z[6][ROUNDS+1]); ! 50: static void de_key_idea(word16 Z[6][ROUNDS+1], word16 DK[6][ROUNDS+1]); ! 51: static void cipher_idea(word16 inblock[4], word16 outblock[4], ! 52: word16 Z[6][ROUNDS+1]); ! 53: ! 54: ! 55: /* Multiplication, modulo (2**16)+1 */ ! 56: static word16 mul(register word16 a, register word16 b) ! 57: { ! 58: register word32 q; ! 59: register long int p; ! 60: if (a==0) ! 61: p = maxim-b; ! 62: else ! 63: if (b==0) ! 64: p = maxim-a; ! 65: else ! 66: { q = (word32)a * (word32)b; ! 67: p = (q & mask16) - (q>>16); ! 68: if (p<=0) ! 69: p = p+maxim; ! 70: } ! 71: return (lower16(p)); ! 72: } /* mul */ ! 73: ! 74: ! 75: /* Compute multiplicative inverse of x, modulo (2**16)+1, ! 76: using Euclid's GCD algorithm. */ ! 77: static word16 inv(word16 x) ! 78: { ! 79: long n1,n2,q,r,b1,b2,t; ! 80: if (x == 0) ! 81: b2 = 0; ! 82: else ! 83: { n1 = maxim; ! 84: n2 = x; ! 85: b2 = 1; ! 86: b1 = 0; ! 87: do ! 88: { r = (n1 % n2); ! 89: q = (n1-r)/n2; ! 90: if (r == 0) ! 91: { if (b2 < 0) ! 92: b2 = maxim+b2; ! 93: } ! 94: else ! 95: { n1 = n2; ! 96: n2 = r; ! 97: t = b2; ! 98: b2 = b1 - q*b2; ! 99: b1 = t; ! 100: } ! 101: } while (r != 0); ! 102: } ! 103: #ifdef IDEA_DEBUG ! 104: if ( mul(x, (word16) b2) != 1) /* check answer */ ! 105: printf("\n\07Error! inv(%u) = %u ?\n", x, (word16) b2 ); ! 106: #endif ! 107: return ((word16) b2); ! 108: } /* inv */ ! 109: ! 110: ! 111: /* Compute IDEA encryption subkeys Z */ ! 112: static void en_key_idea(word16 userkey[8], word16 Z[6][ROUNDS+1]) ! 113: { ! 114: word16 S[54]; ! 115: int i,j,r; ! 116: /* shifts */ ! 117: for (i = 0; i<8; i++) ! 118: S[i] = userkey[i]; ! 119: for (i = 8; i<54; i++) ! 120: { if ((i+2)%8 == 0) /* for S[14],S[22],... */ ! 121: S[i] = lower16((S[i-7] << 9) ^ (S[i-14] >> 7)); ! 122: else ! 123: if ((i+1)%8 == 0) /* for S[15],S[23],... */ ! 124: S[i] = lower16((S[i-15] << 9) ^ (S[i-14] >> 7)); ! 125: else ! 126: S[i] = lower16((S[i-7] << 9) ^ (S[i-6] >> 7)); ! 127: } ! 128: /* get subkeys */ ! 129: for (r=0; r<ROUNDS+1; r++) ! 130: for (j=0; j<6; j++) ! 131: Z[j][r] = S[6*r + j]; ! 132: ! 133: /* clear sensitive key data from memory... */ ! 134: for (i=0; i<54; i++) S[i] = 0; ! 135: ! 136: } /* en_key_idea */ ! 137: ! 138: ! 139: /* Compute IDEA decryption subkeys DK from encryption subkeys Z */ ! 140: static void de_key_idea(word16 Z[6][ROUNDS+1], word16 DK[6][ROUNDS+1]) ! 141: { ! 142: int j; ! 143: for (j=0; j<ROUNDS+1; j++) ! 144: { DK[0][ROUNDS-j] = inv(Z[0][j]); ! 145: DK[3][ROUNDS-j] = inv(Z[3][j]); ! 146: if (j==0 || j==ROUNDS) ! 147: { DK[1][ROUNDS-j] = lower16(fuyi-Z[1][j]); ! 148: DK[2][ROUNDS-j] = lower16(fuyi-Z[2][j]); ! 149: } ! 150: else ! 151: { DK[1][ROUNDS-j] = lower16(fuyi-Z[2][j]); ! 152: DK[2][ROUNDS-j] = lower16(fuyi-Z[1][j]); ! 153: } ! 154: } ! 155: for (j=0; j<ROUNDS; j++) ! 156: { DK[4][ROUNDS-1-j] = Z[4][j]; ! 157: DK[5][ROUNDS-1-j] = Z[5][j]; ! 158: } ! 159: } /* de_key_idea */ ! 160: ! 161: ! 162: /* IDEA encryption/decryption algorithm */ ! 163: static void cipher_idea(word16 inblock[4], word16 outblock[4], ! 164: register word16 Z[6][ROUNDS+1]) ! 165: { /* Note that inblock and outblock can be the same buffer */ ! 166: int r; ! 167: register word16 x1, x2, x3, x4, kk, t1, t2, a; ! 168: x1=inblock[0]; ! 169: x2=inblock[1]; ! 170: x3=inblock[2]; ! 171: x4=inblock[3]; ! 172: for (r=0; r<ROUNDS; r++) ! 173: { x1 = mul(x1, Z[0][r]); ! 174: x4 = mul(x4, Z[3][r]); ! 175: x2 = lower16(x2 + Z[1][r]); ! 176: x3 = lower16(x3 + Z[2][r]); ! 177: kk = mul(Z[4][r], (x1^x3)); ! 178: t1 = mul(Z[5][r], lower16(kk + (x2^x4)) ); ! 179: t2 = lower16(kk + t1); ! 180: x1 = x1^t1; ! 181: x4 = x4^t2; ! 182: a = x2^t2; ! 183: x2 = x3^t1; ! 184: x3 = a; ! 185: } ! 186: outblock[0] = mul(x1, Z[0][ROUNDS]); ! 187: outblock[3] = mul(x4, Z[3][ROUNDS]); ! 188: outblock[1] = lower16(x3 + Z[1][ROUNDS]); ! 189: outblock[2] = lower16(x2 + Z[2][ROUNDS]); ! 190: } /* cipher_idea */ ! 191: ! 192: ! 193: /*-------------------------------------------------------------*/ ! 194: ! 195: #ifdef TEST ! 196: ! 197: void main(void) ! 198: { /* Test driver for IDEA cipher */ ! 199: int i, j, k; ! 200: word16 Z[6][ROUNDS+1], DK[6][ROUNDS+1], XX[4], TT[4], YY[4]; ! 201: word16 userkey[8]; ! 202: ! 203: /* Make a sample user key for testing... */ ! 204: for(i=0; i<8; i++) ! 205: userkey[i] = i+1; ! 206: ! 207: /* Compute encryption subkeys from user key... */ ! 208: en_key_idea(userkey,Z); ! 209: printf("\nEncryption key subblocks: "); ! 210: for(j=0; j<ROUNDS+1; j++) ! 211: { printf("\nround %d: ", j+1); ! 212: if (j==ROUNDS) ! 213: for(i=0; i<4; i++) ! 214: printf(" %6u", Z[i][j]); ! 215: else ! 216: for(i=0; i<6; i++) ! 217: printf(" %6u", Z[i][j]); ! 218: } ! 219: ! 220: /* Compute decryption subkeys from encryption subkeys... */ ! 221: de_key_idea(Z,DK); ! 222: printf("\nDecryption key subblocks: "); ! 223: for(j=0; j<ROUNDS+1; j++) ! 224: { printf("\nround %d: ", j+1); ! 225: if (j==ROUNDS) ! 226: for(i=0; i<4; i++) ! 227: printf(" %6u", DK[i][j]); ! 228: else ! 229: for(i=0; i<6; i++) ! 230: printf(" %6u", DK[i][j]); ! 231: } ! 232: ! 233: /* Make a sample plaintext pattern for testing... */ ! 234: for (k=0; k<4; k++) ! 235: XX[k] = k; ! 236: ! 237: cipher_idea(XX,YY,Z); /* encrypt plaintext XX, making YY */ ! 238: ! 239: cipher_idea(YY,TT,DK); /* decrypt ciphertext YY, making TT */ ! 240: ! 241: printf("\nX %6u %6u %6u %6u \n", ! 242: XX[0], XX[1], XX[2], XX[3]); ! 243: printf("Y %6u %6u %6u %6u \n", ! 244: YY[0], YY[1], YY[2], YY[3]); ! 245: printf("T %6u %6u %6u %6u \n", ! 246: TT[0], TT[1], TT[2], TT[3]); ! 247: ! 248: /* Now decrypted TT should be same as original XX */ ! 249: for (k=0; k<4; k++) ! 250: if (TT[k] != XX[k]) ! 251: { printf("\n\07Error! Noninvertable encryption.\n"); ! 252: exit(-1); /* error exit */ ! 253: } ! 254: printf("\nNormal exit.\n"); ! 255: exit(0); /* normal exit */ ! 256: } /* main */ ! 257: ! 258: ! 259: #endif /* TEST */ ! 260: ! 261: ! 262: /*************************************************************************/ ! 263: ! 264: ! 265: #define byteglue(lo,hi) ((((word16) hi) << 8) + (word16) lo) ! 266: ! 267: /* ! 268: ** xorbuf - change buffer via xor with random mask block ! 269: ** Used for Cipher Feedback (CFB) or Cipher Block Chaining ! 270: ** (CBC) modes of encryption. ! 271: ** Can be applied for any block encryption algorithm, ! 272: ** with any block size, such as the DES or the IDEA cipher. ! 273: */ ! 274: static void xorbuf(register byteptr buf, register byteptr mask, register int count) ! 275: /* count must be > 0 */ ! 276: { if (count) ! 277: do ! 278: *buf++ ^= *mask++; ! 279: while (--count); ! 280: } /* xorbuf */ ! 281: ! 282: ! 283: /* ! 284: ** cfbshift - shift bytes into IV for CFB input ! 285: ** Used only for Cipher Feedback (CFB) mode of encryption. ! 286: ** Can be applied for any block encryption algorithm with any ! 287: ** block size, such as the DES or the IDEA cipher. ! 288: */ ! 289: static void cfbshift(register byteptr iv, register byteptr buf, ! 290: register int count, int blocksize) ! 291: /* iv is the initialization vector. ! 292: buf is the buffer pointer. ! 293: count is the number of bytes to shift in...must be > 0. ! 294: blocksize is 8 bytes for DES or IDEA ciphers. ! 295: */ ! 296: { int retained; ! 297: if (count) ! 298: { retained = blocksize-count; /* number bytes in iv to retain */ ! 299: /* left-shift retained bytes of IV over by count bytes to make room */ ! 300: while (retained--) ! 301: { *iv = *(iv+count); ! 302: iv++; ! 303: } ! 304: /* now copy count bytes from buf to shifted tail of IV */ ! 305: do *iv++ = *buf++; ! 306: while (--count); ! 307: } ! 308: } /* cfbshift */ ! 309: ! 310: ! 311: ! 312: /* Key schedules for IDEA encryption and decryption */ ! 313: static word16 Z[6][ROUNDS+1], DK[6][ROUNDS+1]; ! 314: static word16 (*keyschedule)[ROUNDS+1]; /* pointer to key schedule Z or DK */ ! 315: static word16 *iv_idea; /* pointer to IV for CFB or CBC */ ! 316: static boolean cfb_dc_idea; /* TRUE iff CFB decrypting */ ! 317: ! 318: ! 319: /* initkey_idea initializes IDEA for ECB mode operations */ ! 320: void initkey_idea(byte key[16], boolean decryp) ! 321: { ! 322: word16 userkey[8]; /* IDEA key is 16 bytes long */ ! 323: int i; ! 324: /* Assume each pair of bytes comprising a word is ordered MSB-first. */ ! 325: for (i=0; i<8; i++) ! 326: { userkey[i] = byteglue(*(key+1),*key); ! 327: key++; key++; ! 328: } ! 329: en_key_idea(userkey,Z); ! 330: keyschedule = Z; ! 331: if (decryp) ! 332: { int r,j; ! 333: de_key_idea(Z,DK); /* compute inverse key schedule DK */ ! 334: keyschedule = DK; ! 335: /* Don't need Z anymore. Erase dangerous traces... */ ! 336: for (r=0; r<ROUNDS+1; r++) ! 337: for (j=0; j<6; j++) ! 338: Z[j][r] = 0; ! 339: } ! 340: for (i=0; i<8; i++) /* Erase dangerous traces */ ! 341: userkey[i] = 0; ! 342: } /* initkey_idea */ ! 343: ! 344: ! 345: /* Run a 64-bit block thru IDEA in ECB (Electronic Code Book) mode, ! 346: using the currently selected key schedule. ! 347: */ ! 348: void idea_ecb(word16 *inbuf, word16 *outbuf) ! 349: { ! 350: /* Assume each pair of bytes comprising a word is ordered MSB-first. */ ! 351: #ifndef HIGHFIRST /* If this is a least-significant-byte-first CPU */ ! 352: /* Invert the byte order for each 16-bit word for internal use. */ ! 353: union { ! 354: word16 w[4]; ! 355: byte b[8]; ! 356: } inbuf2, outbuf2; ! 357: register byte *p; ! 358: p = (byte *) inbuf; ! 359: inbuf2.b[1] = *p++; ! 360: inbuf2.b[0] = *p++; ! 361: inbuf2.b[3] = *p++; ! 362: inbuf2.b[2] = *p++; ! 363: inbuf2.b[5] = *p++; ! 364: inbuf2.b[4] = *p++; ! 365: inbuf2.b[7] = *p++; ! 366: inbuf2.b[6] = *p++; ! 367: cipher_idea(inbuf2.w,outbuf2.w,keyschedule); ! 368: /* Now invert the byte order for each 16-bit word for external use. */ ! 369: p = (byte *) outbuf; ! 370: *p++ = outbuf2.b[1]; ! 371: *p++ = outbuf2.b[0]; ! 372: *p++ = outbuf2.b[3]; ! 373: *p++ = outbuf2.b[2]; ! 374: *p++ = outbuf2.b[5]; ! 375: *p++ = outbuf2.b[4]; ! 376: *p++ = outbuf2.b[7]; ! 377: *p++ = outbuf2.b[6]; ! 378: #else /* HIGHFIRST */ ! 379: /* Byte order for internal and external representations is the same. */ ! 380: cipher_idea(inbuf,outbuf,keyschedule); ! 381: #endif /* HIGHFIRST */ ! 382: } /* idea_ecb */ ! 383: ! 384: ! 385: /* ! 386: ** initcfb - Initializes the IDEA key schedule tables via key, ! 387: ** and initializes the Cipher Feedback mode IV. ! 388: ** References context variables cfb_dc_idea and iv_idea. ! 389: */ ! 390: void initcfb_idea(word16 iv0[4], byte key[16], boolean decryp) ! 391: /* iv0 is copied to global iv_idea, buffer will be destroyed by ideacfb. ! 392: key is pointer to key buffer. ! 393: decryp is TRUE if decrypting, FALSE if encrypting. ! 394: */ ! 395: { iv_idea = iv0; ! 396: cfb_dc_idea = decryp; ! 397: initkey_idea(key,FALSE); ! 398: } /* initcfb_idea */ ! 399: ! 400: ! 401: /* ! 402: ** ideacfb - encipher a buffer with IDEA enciphering algorithm, ! 403: ** using Cipher Feedback (CFB) mode. ! 404: ** ! 405: ** Assumes initcfb_idea has already been called. ! 406: ** References context variables cfb_dc_idea and iv_idea. ! 407: */ ! 408: void ideacfb(byteptr buf, int count) ! 409: /* buf is input, output buffer, may be more than 1 block. ! 410: count is byte count of buffer. May be > IDEABLOCKSIZE. ! 411: */ ! 412: { int chunksize; /* smaller of count, IDEABLOCKSIZE */ ! 413: word16 temp[IDEABLOCKSIZE/2]; ! 414: ! 415: while ((chunksize = min(count,IDEABLOCKSIZE)) > 0) ! 416: { ! 417: idea_ecb(iv_idea,temp); /* encrypt iv_idea, making temp. */ ! 418: ! 419: if (cfb_dc_idea) /* buf is ciphertext */ ! 420: /* shift in ciphertext to IV... */ ! 421: cfbshift((byte *)iv_idea,buf,chunksize,IDEABLOCKSIZE); ! 422: ! 423: /* convert buf via xor */ ! 424: xorbuf(buf,(byte *)temp,chunksize); /* buf now has enciphered output */ ! 425: ! 426: if (!cfb_dc_idea) /* buf was plaintext, is now ciphertext */ ! 427: /* shift in ciphertext to IV... */ ! 428: cfbshift((byte *)iv_idea,buf,chunksize,IDEABLOCKSIZE); ! 429: ! 430: count -= chunksize; ! 431: buf += chunksize; ! 432: } ! 433: } /* ideacfb */ ! 434: ! 435: ! 436: /* ! 437: close_idea function erases all the key schedule information when ! 438: we are all done with a set of operations for a particular IDEA key ! 439: context. This is to prevent any sensitive data from being left ! 440: around in memory. ! 441: */ ! 442: void close_idea(void) /* erase current key schedule tables */ ! 443: { short r,j; ! 444: for (r=0; r<ROUNDS+1; r++) ! 445: for (j=0; j<6; j++) ! 446: keyschedule[j][r] = 0; ! 447: } /* close_idea() */ ! 448: ! 449: /********************************************************************/ ! 450: ! 451: /* ! 452: ** These buffers are used by init_idearand, idearand, and close_idearand. ! 453: */ ! 454: static word16 dtbuf_idea[4] = {0}; /* buffer for enciphered timestamp */ ! 455: static word16 randseed_idea[4] = {0}; /* seed for IDEA random # generator */ ! 456: static word16 randbuf_idea[4] = {0}; /* buffer for IDEA random # generator */ ! 457: static byte randbuf_idea_counter = 0; /* # of random bytes left in randbuf_idea */ ! 458: ! 459: /* ! 460: ** init_idearand - initialize idearand, IDEA random number generator. ! 461: ** Used for generating cryptographically strong random numbers. ! 462: ** Much of the design comes from Appendix C of ANSI X9.17. ! 463: ** key is pointer to IDEA key buffer. ! 464: ** seed is pointer to random number seed buffer. ! 465: ** tstamp is a 32-bit timestamp ! 466: */ ! 467: void init_idearand(byte key[16], byte seed[8], word32 tstamp) ! 468: { int i; ! 469: initkey_idea(key, FALSE); /* initialize IDEA */ ! 470: ! 471: for (i=0; i<4; i++) /* capture timestamp material */ ! 472: { dtbuf_idea[i] = tstamp; /* get bottom byte */ ! 473: tstamp = tstamp >> 16; /* drop bottom byte */ ! 474: /* tstamp has only 4 bytes-- last 4 bytes will always be 0 */ ! 475: } ! 476: /* Start with enciphered timestamp: */ ! 477: idea_ecb(dtbuf_idea,dtbuf_idea); ! 478: ! 479: /* initialize seed material */ ! 480: for (i=0; i<8; i++) ! 481: ((byte *)randseed_idea)[i] = seed[i]; ! 482: ! 483: randbuf_idea_counter = 0; /* # of random bytes left in randbuf_idea */ ! 484: ! 485: } /* init_idearand */ ! 486: ! 487: ! 488: /* ! 489: ** idearand - IDEA pseudo-random number generator ! 490: ** Used for generating cryptographically strong random numbers. ! 491: ** Much of the design comes from Appendix C of ANSI X9.17. ! 492: */ ! 493: byte idearand(void) ! 494: { int i; ! 495: if (randbuf_idea_counter==0) /* if random buffer is spent...*/ ! 496: { ! 497: /* Combine enciphered timestamp with seed material: */ ! 498: for (i=0; i<4; i++) ! 499: randseed_idea[i] ^= dtbuf_idea[i]; ! 500: idea_ecb(randseed_idea,randbuf_idea); /* fill new block */ ! 501: ! 502: /* Compute new seed vector: */ ! 503: for (i=0; i<4; i++) ! 504: randseed_idea[i] = randbuf_idea[i] ^ dtbuf_idea[i]; ! 505: idea_ecb(randseed_idea,randseed_idea); /* fill new seed */ ! 506: ! 507: randbuf_idea_counter = 8; /* reset counter for full buffer */ ! 508: } ! 509: /* Take a byte from randbuf_idea: */ ! 510: return(((byte *)randbuf_idea)[--randbuf_idea_counter]); ! 511: } /* idearand */ ! 512: ! 513: ! 514: void close_idearand(void) ! 515: { /* Erase random IDEA buffers and wipe out IDEA key info */ ! 516: int i; ! 517: for (i=0; i<4; i++) ! 518: { randbuf_idea[i] = 0; ! 519: randseed_idea[i] = 0; ! 520: dtbuf_idea[i] = 0; ! 521: } ! 522: close_idea(); /* erase current key schedule tables */ ! 523: } /* close_idearand */ ! 524: ! 525: /* end of idea.c */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.