![[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.1.2 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.
7: * Zero-based indexing added, names changed from IPES to IDEA.
8: * CFB functions added. Random number routines added.
9: *
1.1.1.3 ! root 10: * Optimized for speed 21 Oct 92 by Colin Plumb.
! 11: * Very minor speedup on 23 Feb 93 by Colin Plumb.
! 12: * idearand() given a separate expanded key on 25 Feb 93, Colin Plumb.
1.1.1.2 root 13: *
14: * There are two adjustments that can be made to this code to
15: * speed it up. Defaults may be used for PCs. Only the -DIDEA32
16: * pays off significantly if selectively set or not set.
17: * Experiment to see what works better for you.
18: *
19: * Multiplication: default is inline, -DAVOID_JUMPS uses a
20: * different version that does not do any conditional
21: * jumps (a few percent worse on a SPARC), while
22: * -DSMALL_CACHE takes it out of line to stay
23: * within a small on-chip code cache.
24: * Variables: normally, 16-bit variables are used, but some
25: * machines (notably RISCs) do not have 16-bit registers,
26: * so they do a great deal of masking. -DIDEA32 uses "int"
27: * register variables and masks explicitly only where
28: * necessary. On a SPARC, for example, this boosts
29: * performace by 30%.
30: *
31: * The IDEA(tm) block cipher is covered by a patent held by ETH and a
32: * Swiss company called Ascom-Tech AG. The Swiss patent number is
33: * PCT/CH91/00117. International patents are pending. IDEA(tm) is a
34: * trademark of Ascom-Tech AG. There is no license fee required for
35: * noncommercial use. Commercial users may obtain licensing details
36: * from Dieter Profos, Ascom Tech AG, Solothurn Lab, Postfach 151, 4502
37: * Solothurn, 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 these papers:
46: * 1) Xuejia Lai, "Detailed Description and a Software Implementation of
47: * the IPES Cipher", Institute for Signal and Information
48: * Processing, ETH-Zentrum, Zurich, Switzerland, 1991
49: * 2) Xuejia Lai, James L. Massey, Sean Murphy, "Markov Ciphers and
50: * Differential Cryptanalysis", Advances in Cryptology- EUROCRYPT'91
51: *
52: * This code assumes that each pair of 8-bit bytes comprising a 16-bit
53: * word in the key and in the cipher block are externally represented
54: * with the Most Significant Byte (MSB) first, regardless of the
55: * internal native byte order of the target CPU.
56: */
57:
58: #include "idea.h"
59:
60: #ifdef TEST
61: #include <stdio.h>
62: #include <time.h>
63: #endif
64:
65: #define ROUNDS 8 /* Don't change this value, should be 8 */
66: #define KEYLEN (6*ROUNDS+4) /* length of key schedule */
67:
68: typedef word16 IDEAkey[KEYLEN];
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: #define CONST __const__
82: #else
83: #define CONST
84: #endif
85:
1.1.1.3 ! root 86: static void en_key_idea(word16 *userkey, word16 *Z);
1.1.1.2 root 87: static void de_key_idea(IDEAkey Z, IDEAkey DK);
88: static void cipher_idea(word16 in[4], word16 out[4], CONST IDEAkey Z);
89:
90: /*
91: * Multiplication, modulo (2**16)+1
92: * Note that this code is structured like this on the assumption that
93: * untaken branches are cheaper than taken branches, and the compiler
94: * doesn't schedule branches.
95: */
96: #ifdef SMALL_CACHE
97: CONST static uint16 mul(register uint16 a, register uint16 b)
98: {
99: register word32 p;
100:
101: if (a)
102: { if (b)
103: { p = (word32)a * b;
104: b = low16(p);
105: a = p>>16;
106: return b - a + (b < a);
107: }
108: else
109: { return 1-a;
110: }
111: }
112: else
113: { return 1-b;
114: }
115: } /* mul */
116: #endif /* SMALL_CACHE */
117:
118: /*
119: * Compute multiplicative inverse of x, modulo (2**16)+1,
120: * using Euclid's GCD algorithm. It is unrolled twice to
121: * avoid swapping the meaning of the registers each iteration,
122: * and some subtracts of t have been changed to adds.
123: */
124: CONST static uint16 inv(uint16 x)
125: {
126: uint16 t0, t1;
127: uint16 q, y;
128:
129: if (x <= 1)
130: return x; /* 0 and 1 are self-inverse */
1.1.1.3 ! root 131: t1 = 0x10001L / x; /* Since x >= 2, this fits into 16 bits */
! 132: y = 0x10001L % x;
1.1.1.2 root 133: if (y == 1)
134: return low16(1-t1);
135: t0 = 1;
136: do
137: { q = x / y;
138: x = x % y;
139: t0 += q * t1;
140: if (x == 1)
141: return t0;
142: q = y / x;
143: y = y % x;
144: t1 += q * t0;
145: } while (y != 1);
146: return low16(1-t1);
147: } /* inv */
148:
149: /* Compute IDEA encryption subkeys Z */
150: static void en_key_idea(word16 *userkey, word16 *Z)
151: {
152: int i,j;
153:
154: /*
155: * shifts
156: */
157: for (j=0; j<8; j++)
158: Z[j] = *userkey++;
159:
160: for (i=0; j<KEYLEN; j++)
161: { i++;
162: Z[i+7] = Z[i & 7] << 9 | Z[i+1 & 7] >> 7;
163: Z += i & 8;
164: i &= 7;
165: }
166: } /* en_key_idea */
167:
168: /* Compute IDEA decryption subkeys DK from encryption subkeys Z */
169: /* Note: these buffers *may* overlap! */
170: static void de_key_idea(IDEAkey Z, IDEAkey DK)
171: {
172: int j;
173: uint16 t1, t2, t3;
174: IDEAkey T;
175: word16 *p = T + KEYLEN;
176:
177: t1 = inv(*Z++);
178: t2 = -*Z++;
179: t3 = -*Z++;
180: *--p = inv(*Z++);
181: *--p = t3;
182: *--p = t2;
183: *--p = t1;
184:
185: for (j = 1; j < ROUNDS; j++)
186: {
187: t1 = *Z++;
188: *--p = *Z++;
189: *--p = t1;
190:
191: t1 = inv(*Z++);
192: t2 = -*Z++;
193: t3 = -*Z++;
194: *--p = inv(*Z++);
195: *--p = t2;
196: *--p = t3;
197: *--p = t1;
198: }
199: t1 = *Z++;
200: *--p = *Z++;
201: *--p = t1;
202:
203: t1 = inv(*Z++);
204: t2 = -*Z++;
205: t3 = -*Z++;
206: *--p = inv(*Z++);
207: *--p = t3;
208: *--p = t2;
209: *--p = t1;
210: /* Copy and destroy temp copy */
211: for (j = 0, p = T; j < KEYLEN; j++)
212: {
213: *DK++ = *p;
214: *p++ = 0;
215: }
216: } /* de_key_idea */
217:
218: /*
219: * MUL(x,y) computes x = x*y, modulo 0x10001. Requires two temps,
220: * t16 and t32. x must me a side-effect-free lvalue. y may be
221: * anything, but unlike x, must be strictly 16 bits even if low16()
222: * is #defined.
223: * All of these are equivalent - see which is faster on your machine
224: */
225: #ifdef SMALL_CACHE
226: #define MUL(x,y) (x = mul(low16(x),y))
227: #else
228: #ifdef AVOID_JUMPS
229: #define MUL(x,y) (x = low16(x-1), t16 = low16((y)-1), \
230: t32 = (word32)x*t16+x+t16+1, x = low16(t32), \
231: t16 = t32>>16, x = x-t16+(x<t16) )
232: #else
233: #define MUL(x,y) ((t16 = (y)) ? (x=low16(x)) ? \
234: t32 = (word32)x*t16, x = low16(t32), t16 = t32>>16, \
235: x = x-t16+(x<t16) : \
236: (x = 1-t16) : (x = 1-x))
237: #endif
238: #endif
239:
240: /* IDEA encryption/decryption algorithm */
241: /* Note that in and out can be the same buffer */
242: static void cipher_idea(word16 in[4], word16 out[4], register CONST IDEAkey Z)
243: {
1.1.1.3 ! root 244: register uint16 x1, x2, x3, x4, s2, s3;
! 245: #ifndef SMALL_CACHE
1.1.1.2 root 246: register uint16 t16;
247: register word32 t32;
1.1.1.3 ! root 248: #endif
1.1.1.2 root 249:
250: int r = ROUNDS;
251:
252: x1 = *in++; x2 = *in++;
253: x3 = *in++; x4 = *in;
254: do
255: {
256: MUL(x1,*Z++);
257: x2 += *Z++;
258: x3 += *Z++;
259: MUL(x4, *Z++);
260:
1.1.1.3 ! root 261: s3 = x3;
! 262: x3 ^= x1;
! 263: MUL(x3, *Z++);
! 264: s2 = x2;
! 265: x2 ^= x4;
! 266: x2 += x3;
! 267: MUL(x2, *Z++);
! 268: x3 += x2;
! 269:
! 270: x1 ^= x2;
! 271: x4 ^= x3;
! 272:
! 273: x2 ^= s3;
! 274: x3 ^= s2;
1.1.1.2 root 275: } while (--r);
276: MUL(x1, *Z++);
277: *out++ = x1;
278: *out++ = x3 + *Z++;
279: *out++ = x2 + *Z++;
280: MUL(x4, *Z);
281: *out = x4;
282: } /* cipher_idea */
283:
284: /*-------------------------------------------------------------*/
285:
286: #ifdef TEST
287: /*
288: * This is the number of Kbytes of test data to encrypt.
289: * It defaults to 1 MByte.
290: */
291: #ifndef KBYTES
292: #define KBYTES 1024
293: #endif
294:
295: void main(void)
296: { /* Test driver for IDEA cipher */
297: int i, j, k;
298: IDEAkey Z, DK;
299: word16 XX[4], TT[4], YY[4];
300: word16 userkey[8];
301: clock_t start, end;
302: long l;
303:
304: /* Make a sample user key for testing... */
305: for(i=0; i<8; i++)
306: userkey[i] = i+1;
307:
308: /* Compute encryption subkeys from user key... */
309: en_key_idea(userkey,Z);
310: printf("\nEncryption key subblocks: ");
311: for(j=0; j<ROUNDS+1; j++)
312: {
313: printf("\nround %d: ", j+1);
314: if (j==ROUNDS)
315: for(i=0; i<4; i++)
316: printf(" %6u", Z[j*6+i]);
317: else
318: for(i=0; i<6; i++)
319: printf(" %6u", Z[j*6+i]);
320: }
321:
322: /* Compute decryption subkeys from encryption subkeys... */
323: de_key_idea(Z,DK);
324: printf("\nDecryption key subblocks: ");
325: for(j=0; j<ROUNDS+1; j++)
326: {
327: printf("\nround %d: ", j+1);
328: if (j==ROUNDS)
329: for(i=0; i<4; i++)
330: printf(" %6u", DK[j*6+i]);
331: else
332: for(i=0; i<6; i++)
333: printf(" %6u", DK[j*6+i]);
334: }
335:
336: /* Make a sample plaintext pattern for testing... */
337: for (k=0; k<4; k++)
338: XX[k] = k;
339:
340: printf("\n Encrypting %d KBytes (%ld blocks)...", KBYTES, KBYTES*64l);
341: fflush(stdout);
342: start = clock();
343: cipher_idea(XX,YY,Z); /* encrypt plaintext XX, making YY */
344: for (l = 1; l < 64*KBYTES; l++)
345: cipher_idea(YY,YY,Z); /* repeated encryption */
346: cipher_idea(YY,TT,DK); /* decrypt ciphertext YY, making TT */
347: for (l = 1; l < 64*KBYTES; l++)
348: cipher_idea(TT,TT,DK); /* repeated decryption */
349: end = clock() - start;
350: l = end * 1000. / CLOCKS_PER_SEC + 1;
351: i = l/1000;
352: j = l%1000;
353: l = KBYTES * 1024. * CLOCKS_PER_SEC / end;
354: printf("%d.%03d seconds = %ld bytes per second\n", i, j, l);
355:
356: printf("\nX %6u %6u %6u %6u \n",
357: XX[0], XX[1], XX[2], XX[3]);
358: printf("Y %6u %6u %6u %6u \n",
359: YY[0], YY[1], YY[2], YY[3]);
360: printf("T %6u %6u %6u %6u \n",
361: TT[0], TT[1], TT[2], TT[3]);
362:
363: /* Now decrypted TT should be same as original XX */
364: for (k=0; k<4; k++)
365: if (TT[k] != XX[k])
366: {
367: printf("\n\07Error! Noninvertable encryption.\n");
368: exit(-1); /* error exit */
369: }
370: printf("\nNormal exit.\n");
371: exit(0); /* normal exit */
372: } /* main */
373:
374:
375: #endif /* TEST */
376:
377:
378: /*************************************************************************/
379:
380:
381: /*
382: * xorbuf - change buffer via xor with random mask block
383: * Used for Cipher Feedback (CFB) or Cipher Block Chaining
384: * (CBC) modes of encryption.
385: * Can be applied for any block encryption algorithm,
386: * with any block size, such as the DES or the IDEA cipher.
387: */
388: static void xorbuf(register byteptr buf, register byteptr mask,
389: register int count)
390: /* count must be > 0 */
391: {
392: if (count)
393: do
394: *buf++ ^= *mask++;
395: while (--count);
396: } /* xorbuf */
397:
398:
399: /*
400: * cfbshift - shift bytes into IV for CFB input
401: * Used only for Cipher Feedback (CFB) mode of encryption.
402: * Can be applied for any block encryption algorithm with any
403: * block size, such as the DES or the IDEA cipher.
404: */
405: static void cfbshift(register byteptr iv, register byteptr buf,
406: register int count, int blocksize)
407: /* iv is the initialization vector.
408: * buf is the buffer pointer.
409: * count is the number of bytes to shift in...must be > 0.
410: * blocksize is 8 bytes for DES or IDEA ciphers.
411: */
412: {
413: int retained;
414: if (count)
415: {
416: retained = blocksize-count; /* number bytes in iv to retain */
417: /* left-shift retained bytes of IV over by count bytes to make room */
418: while (retained--)
419: {
420: *iv = *(iv+count);
421: iv++;
422: }
423: /* now copy count bytes from buf to shifted tail of IV */
424: do *iv++ = *buf++;
425: while (--count);
426: }
427: } /* cfbshift */
428:
429:
430:
431: /* Key schedules for IDEA encryption and decryption */
1.1.1.3 ! root 432: static IDEAkey Z;
1.1.1.2 root 433: static word16 *iv_idea; /* pointer to IV for CFB or CBC */
434: static boolean cfb_dc_idea; /* TRUE iff CFB decrypting */
435:
436:
437: /* initkey_idea initializes IDEA for ECB mode operations */
1.1.1.3 ! root 438: static void initkey_idea(byte key[16], boolean decryp)
1.1.1.2 root 439: {
440: word16 userkey[8]; /* IDEA key is 16 bytes long */
441: int i;
442: /* Assume each pair of bytes comprising a word is ordered MSB-first. */
443: for (i=0; i<8; i++)
444: {
445: userkey[i] = (key[0]<<8) + key[1];
446: key++; key++;
447: }
448: en_key_idea(userkey,Z);
449: if (decryp)
450: {
451: de_key_idea(Z,Z); /* compute inverse key schedule DK */
452: }
453: for (i=0; i<8; i++) /* Erase dangerous traces */
454: userkey[i] = 0;
455: } /* initkey_idea */
456:
457:
458: /* Run a 64-bit block thru IDEA in ECB (Electronic Code Book) mode,
459: using the currently selected key schedule.
460: */
1.1.1.3 ! root 461: static void idea_ecb(word16 *inbuf, word16 *outbuf)
1.1.1.2 root 462: {
463: /* Assume each pair of bytes comprising a word is ordered MSB-first. */
464: #ifndef HIGHFIRST /* If this is a least-significant-byte-first CPU */
465: word16 x;
466:
467: /* Invert the byte order for each 16-bit word for internal use. */
468: x = inbuf[0]; outbuf[0] = x >> 8 | x << 8;
469: x = inbuf[1]; outbuf[1] = x >> 8 | x << 8;
470: x = inbuf[2]; outbuf[2] = x >> 8 | x << 8;
471: x = inbuf[3]; outbuf[3] = x >> 8 | x << 8;
472: cipher_idea(outbuf, outbuf, Z);
473: x = outbuf[0]; outbuf[0] = x >> 8 | x << 8;
474: x = outbuf[1]; outbuf[1] = x >> 8 | x << 8;
475: x = outbuf[2]; outbuf[2] = x >> 8 | x << 8;
476: x = outbuf[3]; outbuf[3] = x >> 8 | x << 8;
477: #else /* HIGHFIRST */
478: /* Byte order for internal and external representations is the same. */
479: cipher_idea(inbuf, outbuf, Z);
480: #endif /* HIGHFIRST */
481: } /* idea_ecb */
482:
483:
484: /*
485: * initcfb - Initializes the IDEA key schedule tables via key,
486: * and initializes the Cipher Feedback mode IV.
487: * References context variables cfb_dc_idea and iv_idea.
488: */
489: void initcfb_idea(word16 iv0[4], byte key[16], boolean decryp)
490: /* iv0 is copied to global iv_idea, buffer will be destroyed by ideacfb.
491: key is pointer to key buffer.
492: decryp is TRUE if decrypting, FALSE if encrypting.
493: */
494: {
495: iv_idea = iv0;
496: cfb_dc_idea = decryp;
497: initkey_idea(key,FALSE);
498: } /* initcfb_idea */
499:
500:
501: /*
502: * ideacfb - encipher a buffer with IDEA enciphering algorithm,
503: * using Cipher Feedback (CFB) mode.
504: *
505: * Assumes initcfb_idea has already been called.
506: * References context variables cfb_dc_idea and iv_idea.
507: */
508: void ideacfb(byteptr buf, int count)
509: /* buf is input, output buffer, may be more than 1 block.
510: * count is byte count of buffer. May be > IDEABLOCKSIZE.
511: */
512: {
513: int chunksize; /* smaller of count, IDEABLOCKSIZE */
514: word16 temp[IDEABLOCKSIZE/2];
515:
516: while ((chunksize = min(count,IDEABLOCKSIZE)) > 0)
517: {
518: idea_ecb(iv_idea,temp); /* encrypt iv_idea, making temp. */
519:
520: if (cfb_dc_idea) /* buf is ciphertext */
521: /* shift in ciphertext to IV... */
522: cfbshift((byte *)iv_idea,buf,chunksize,IDEABLOCKSIZE);
523:
524: /* convert buf via xor */
525: xorbuf(buf,(byte *)temp,chunksize); /* buf now has enciphered output */
526:
527: if (!cfb_dc_idea) /* buf was plaintext, is now ciphertext */
528: /* shift in ciphertext to IV... */
529: cfbshift((byte *)iv_idea,buf,chunksize,IDEABLOCKSIZE);
530:
531: count -= chunksize;
532: buf += chunksize;
533: }
534: } /* ideacfb */
535:
536:
537: /*
538: close_idea function erases all the key schedule information when
539: we are all done with a set of operations for a particular IDEA key
540: context. This is to prevent any sensitive data from being left
541: around in memory.
542: */
543: void close_idea(void) /* erase current key schedule tables */
544: {
545: short i;
546: for (i = 0; i < KEYLEN; i++)
547: Z[i] = 0;
548: } /* close_idea() */
549:
550: /********************************************************************/
551:
552: /*
553: * These buffers are used by init_idearand, idearand, and close_idearand.
554: */
555: static word16 dtbuf_idea[4] = {0}; /* buffer for enciphered timestamp */
556: static word16 randseed_idea[4] = {0}; /* seed for IDEA random # generator */
557: static word16 randbuf_idea[4] = {0}; /* buffer for IDEA random # generator */
558: static byte randbuf_idea_counter = 0; /* # of random bytes left in randbuf_idea */
1.1.1.3 ! root 559: static IDEAkey randkey_idea; /* Expanded key for IDEA random # generator */
1.1.1.2 root 560:
561: /*
562: * init_idearand - initialize idearand, IDEA random number generator.
563: * Used for generating cryptographically strong random numbers.
564: * Much of the design comes from Appendix C of ANSI X9.17.
565: * key is pointer to IDEA key buffer.
566: * seed is pointer to random number seed buffer.
567: * tstamp is a 32-bit timestamp
568: */
569: void init_idearand(byte key[16], byte seed[8], word32 tstamp)
570: {
571: int i;
1.1.1.3 ! root 572:
! 573: en_key_idea((word16 *)key, randkey_idea);
1.1.1.2 root 574:
575: for (i=0; i<4; i++) /* capture timestamp material */
576: { dtbuf_idea[i] = tstamp; /* get bottom word */
577: tstamp = tstamp >> 16; /* drop bottom word */
578: /* tstamp has only 4 bytes-- last 4 bytes will always be 0 */
579: }
580: /* Start with enciphered timestamp: */
1.1.1.3 ! root 581: cipher_idea(dtbuf_idea, dtbuf_idea, randkey_idea);
1.1.1.2 root 582:
583: /* initialize seed material */
584: for (i=0; i<8; i++)
585: ((byte *)randseed_idea)[i] = seed[i];
586:
587: randbuf_idea_counter = 0; /* # of random bytes left in randbuf_idea */
588:
589: } /* init_idearand */
590:
591:
592: /*
593: * idearand - IDEA pseudo-random number generator
594: * Used for generating cryptographically strong random numbers.
595: * Much of the design comes from Appendix C of ANSI X9.17.
596: */
597: byte idearand(void)
598: {
599: int i;
600: if (randbuf_idea_counter==0) /* if random buffer is spent...*/
601: { /* Combine enciphered timestamp with seed material: */
602: for (i=0; i<4; i++)
603: randseed_idea[i] ^= dtbuf_idea[i];
1.1.1.3 ! root 604: cipher_idea(randseed_idea,randbuf_idea,randkey_idea); /* fill new block */
1.1.1.2 root 605:
606: /* Compute new seed vector: */
607: for (i=0; i<4; i++)
608: randseed_idea[i] = randbuf_idea[i] ^ dtbuf_idea[i];
1.1.1.3 ! root 609: cipher_idea(randseed_idea,randseed_idea,randkey_idea); /* fill new seed */
1.1.1.2 root 610:
611: randbuf_idea_counter = 8; /* reset counter for full buffer */
612: }
613: /* Take a byte from randbuf_idea: */
614: return(((byte *)randbuf_idea)[--randbuf_idea_counter]);
615: } /* idearand */
616:
617:
618: void close_idearand(void)
619: { /* Erase random IDEA buffers and wipe out IDEA key info */
620: int i;
621: for (i=0; i<4; i++)
622: { randbuf_idea[i] = 0;
623: randseed_idea[i] = 0;
624: dtbuf_idea[i] = 0;
625: }
1.1.1.3 ! root 626: for (i = 0; i<KEYLEN; i++)
! 627: randkey_idea[i] = 0;
1.1.1.2 root 628: } /* close_idearand */
629:
630: /* end of idea.c */
631:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.