![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to idea.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [PGP] / pgp / src|
Return to idea.c CVS log | Up to [PGP] / pgp / src |
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.