This is idea.c in view mode; [Download] [Up]
/* idea.c - C source code for IDEA block cipher.
* IDEA (International Data Encryption Algorithm), formerly known as
* IPES (Improved Proposed Encryption Standard).
* Algorithm developed by Xuejia Lai and James L. Massey, of ETH Zurich.
* This implementation modified and derived from original C code
* developed by Xuejia Lai.
* Zero-based indexing added, names changed from IPES to IDEA.
* CFB functions added. Random number routines added.
*
* Optimized for speed 21 Oct 92 by Colin Plumb.
* Very minor speedup on 23 Feb 93 by Colin Plumb.
* idearand() given a separate expanded key on 25 Feb 93, Colin Plumb.
*
* There are two adjustments that can be made to this code to
* speed it up. Defaults may be used for PCs. Only the -DIDEA32
* pays off significantly if selectively set or not set.
* Experiment to see what works better for you.
*
* Multiplication: default is inline, -DAVOID_JUMPS uses a
* different version that does not do any conditional
* jumps (a few percent worse on a SPARC), while
* -DSMALL_CACHE takes it out of line to stay
* within a small on-chip code cache.
* Variables: normally, 16-bit variables are used, but some
* machines (notably RISCs) do not have 16-bit registers,
* so they do a great deal of masking. -DIDEA32 uses "int"
* register variables and masks explicitly only where
* necessary. On a SPARC, for example, this boosts
* performace by 30%.
*
* The IDEA(tm) block cipher is covered by a patent held by ETH and a
* Swiss company called Ascom-Tech AG. The Swiss patent number is
* PCT/CH91/00117. International patents are pending. IDEA(tm) is a
* trademark of Ascom-Tech AG. There is no license fee required for
* noncommercial use. Commercial users may obtain licensing details
* from Dieter Profos, Ascom Tech AG, Solothurn Lab, Postfach 151, 4502
* Solothurn, Switzerland, Tel +41 65 242885, Fax +41 65 235761.
*
* The IDEA block cipher uses a 64-bit block size, and a 128-bit key
* size. It breaks the 64-bit cipher block into four 16-bit words
* because all of the primitive inner operations are done with 16-bit
* arithmetic. It likewise breaks the 128-bit cipher key into eight
* 16-bit words.
*
* For further information on the IDEA cipher, see these papers:
* 1) Xuejia Lai, "Detailed Description and a Software Implementation of
* the IPES Cipher", Institute for Signal and Information
* Processing, ETH-Zentrum, Zurich, Switzerland, 1991
* 2) Xuejia Lai, James L. Massey, Sean Murphy, "Markov Ciphers and
* Differential Cryptanalysis", Advances in Cryptology- EUROCRYPT'91
*
* This code assumes that each pair of 8-bit bytes comprising a 16-bit
* word in the key and in the cipher block are externally represented
* with the Most Significant Byte (MSB) first, regardless of the
* internal native byte order of the target CPU.
*/
#include "idea.h"
#ifdef TEST
#include <stdio.h>
#include <time.h>
#endif
#define ROUNDS 8 /* Don't change this value, should be 8 */
#define KEYLEN (6*ROUNDS+4) /* length of key schedule */
typedef word16 IDEAkey[KEYLEN];
#ifdef IDEA32 /* Use >16-bit temporaries */
#define low16(x) ((x) & 0xFFFF)
typedef unsigned int uint16; /* at LEAST 16 bits, maybe more */
#else
#define low16(x) (x) /* this is only ever applied to uint16's */
typedef word16 uint16;
#endif
#ifdef _GNUC_
/* __const__ simply means there are no side effects for this function,
* which is useful info for the gcc optimizer */
#define CONST __const__
#else
#define CONST
#endif
static void en_key_idea(word16 *userkey, word16 *Z);
static void de_key_idea(IDEAkey Z, IDEAkey DK);
static void cipher_idea(word16 in[4], word16 out[4], CONST IDEAkey Z);
/*
* Multiplication, modulo (2**16)+1
* Note that this code is structured like this on the assumption that
* untaken branches are cheaper than taken branches, and the compiler
* doesn't schedule branches.
*/
#ifdef SMALL_CACHE
CONST static uint16 mul(register uint16 a, register uint16 b)
{
register word32 p;
if (a)
{ if (b)
{ p = (word32)a * b;
b = low16(p);
a = p>>16;
return b - a + (b < a);
}
else
{ return 1-a;
}
}
else
{ return 1-b;
}
} /* mul */
#endif /* SMALL_CACHE */
/*
* Compute multiplicative inverse of x, modulo (2**16)+1,
* using Euclid's GCD algorithm. It is unrolled twice to
* avoid swapping the meaning of the registers each iteration,
* and some subtracts of t have been changed to adds.
*/
CONST static uint16 inv(uint16 x)
{
uint16 t0, t1;
uint16 q, y;
if (x <= 1)
return x; /* 0 and 1 are self-inverse */
t1 = 0x10001L / x; /* Since x >= 2, this fits into 16 bits */
y = 0x10001L % x;
if (y == 1)
return low16(1-t1);
t0 = 1;
do
{ q = x / y;
x = x % y;
t0 += q * t1;
if (x == 1)
return t0;
q = y / x;
y = y % x;
t1 += q * t0;
} while (y != 1);
return low16(1-t1);
} /* inv */
/* Compute IDEA encryption subkeys Z */
static void en_key_idea(word16 *userkey, word16 *Z)
{
int i,j;
/*
* shifts
*/
for (j=0; j<8; j++)
Z[j] = *userkey++;
for (i=0; j<KEYLEN; j++)
{ i++;
Z[i+7] = Z[i & 7] << 9 | Z[i+1 & 7] >> 7;
Z += i & 8;
i &= 7;
}
} /* en_key_idea */
/* Compute IDEA decryption subkeys DK from encryption subkeys Z */
/* Note: these buffers *may* overlap! */
static void de_key_idea(IDEAkey Z, IDEAkey DK)
{
int j;
uint16 t1, t2, t3;
IDEAkey T;
word16 *p = T + KEYLEN;
t1 = inv(*Z++);
t2 = -*Z++;
t3 = -*Z++;
*--p = inv(*Z++);
*--p = t3;
*--p = t2;
*--p = t1;
for (j = 1; j < ROUNDS; j++)
{
t1 = *Z++;
*--p = *Z++;
*--p = t1;
t1 = inv(*Z++);
t2 = -*Z++;
t3 = -*Z++;
*--p = inv(*Z++);
*--p = t2;
*--p = t3;
*--p = t1;
}
t1 = *Z++;
*--p = *Z++;
*--p = t1;
t1 = inv(*Z++);
t2 = -*Z++;
t3 = -*Z++;
*--p = inv(*Z++);
*--p = t3;
*--p = t2;
*--p = t1;
/* Copy and destroy temp copy */
for (j = 0, p = T; j < KEYLEN; j++)
{
*DK++ = *p;
*p++ = 0;
}
} /* de_key_idea */
/*
* MUL(x,y) computes x = x*y, modulo 0x10001. Requires two temps,
* t16 and t32. x must me a side-effect-free lvalue. y may be
* anything, but unlike x, must be strictly 16 bits even if low16()
* is #defined.
* All of these are equivalent - see which is faster on your machine
*/
#ifdef SMALL_CACHE
#define MUL(x,y) (x = mul(low16(x),y))
#else
#ifdef AVOID_JUMPS
#define MUL(x,y) (x = low16(x-1), t16 = low16((y)-1), \
t32 = (word32)x*t16+x+t16+1, x = low16(t32), \
t16 = t32>>16, x = x-t16+(x<t16) )
#else
#define MUL(x,y) ((t16 = (y)) ? (x=low16(x)) ? \
t32 = (word32)x*t16, x = low16(t32), t16 = t32>>16, \
x = x-t16+(x<t16) : \
(x = 1-t16) : (x = 1-x))
#endif
#endif
/* IDEA encryption/decryption algorithm */
/* Note that in and out can be the same buffer */
static void cipher_idea(word16 in[4], word16 out[4], register CONST IDEAkey Z)
{
register uint16 x1, x2, x3, x4, s2, s3;
#ifndef SMALL_CACHE
register uint16 t16;
register word32 t32;
#endif
int r = ROUNDS;
x1 = *in++; x2 = *in++;
x3 = *in++; x4 = *in;
do
{
MUL(x1,*Z++);
x2 += *Z++;
x3 += *Z++;
MUL(x4, *Z++);
s3 = x3;
x3 ^= x1;
MUL(x3, *Z++);
s2 = x2;
x2 ^= x4;
x2 += x3;
MUL(x2, *Z++);
x3 += x2;
x1 ^= x2;
x4 ^= x3;
x2 ^= s3;
x3 ^= s2;
} while (--r);
MUL(x1, *Z++);
*out++ = x1;
*out++ = x3 + *Z++;
*out++ = x2 + *Z++;
MUL(x4, *Z);
*out = x4;
} /* cipher_idea */
/*-------------------------------------------------------------*/
#ifdef TEST
/*
* This is the number of Kbytes of test data to encrypt.
* It defaults to 1 MByte.
*/
#ifndef KBYTES
#define KBYTES 1024
#endif
void main(void)
{ /* Test driver for IDEA cipher */
int i, j, k;
IDEAkey Z, DK;
word16 XX[4], TT[4], YY[4];
word16 userkey[8];
clock_t start, end;
long l;
/* Make a sample user key for testing... */
for(i=0; i<8; i++)
userkey[i] = i+1;
/* Compute encryption subkeys from user key... */
en_key_idea(userkey,Z);
printf("\nEncryption key subblocks: ");
for(j=0; j<ROUNDS+1; j++)
{
printf("\nround %d: ", j+1);
if (j==ROUNDS)
for(i=0; i<4; i++)
printf(" %6u", Z[j*6+i]);
else
for(i=0; i<6; i++)
printf(" %6u", Z[j*6+i]);
}
/* Compute decryption subkeys from encryption subkeys... */
de_key_idea(Z,DK);
printf("\nDecryption key subblocks: ");
for(j=0; j<ROUNDS+1; j++)
{
printf("\nround %d: ", j+1);
if (j==ROUNDS)
for(i=0; i<4; i++)
printf(" %6u", DK[j*6+i]);
else
for(i=0; i<6; i++)
printf(" %6u", DK[j*6+i]);
}
/* Make a sample plaintext pattern for testing... */
for (k=0; k<4; k++)
XX[k] = k;
printf("\n Encrypting %d KBytes (%ld blocks)...", KBYTES, KBYTES*64l);
fflush(stdout);
start = clock();
cipher_idea(XX,YY,Z); /* encrypt plaintext XX, making YY */
for (l = 1; l < 64*KBYTES; l++)
cipher_idea(YY,YY,Z); /* repeated encryption */
cipher_idea(YY,TT,DK); /* decrypt ciphertext YY, making TT */
for (l = 1; l < 64*KBYTES; l++)
cipher_idea(TT,TT,DK); /* repeated decryption */
end = clock() - start;
l = end * 1000. / CLOCKS_PER_SEC + 1;
i = l/1000;
j = l%1000;
l = KBYTES * 1024. * CLOCKS_PER_SEC / end;
printf("%d.%03d seconds = %ld bytes per second\n", i, j, l);
printf("\nX %6u %6u %6u %6u \n",
XX[0], XX[1], XX[2], XX[3]);
printf("Y %6u %6u %6u %6u \n",
YY[0], YY[1], YY[2], YY[3]);
printf("T %6u %6u %6u %6u \n",
TT[0], TT[1], TT[2], TT[3]);
/* Now decrypted TT should be same as original XX */
for (k=0; k<4; k++)
if (TT[k] != XX[k])
{
printf("\n\07Error! Noninvertable encryption.\n");
exit(-1); /* error exit */
}
printf("\nNormal exit.\n");
exit(0); /* normal exit */
} /* main */
#endif /* TEST */
/*************************************************************************/
/*
* xorbuf - change buffer via xor with random mask block
* Used for Cipher Feedback (CFB) or Cipher Block Chaining
* (CBC) modes of encryption.
* Can be applied for any block encryption algorithm,
* with any block size, such as the DES or the IDEA cipher.
*/
static void xorbuf(register byteptr buf, register byteptr mask,
register int count)
/* count must be > 0 */
{
if (count)
do
*buf++ ^= *mask++;
while (--count);
} /* xorbuf */
/*
* cfbshift - shift bytes into IV for CFB input
* Used only for Cipher Feedback (CFB) mode of encryption.
* Can be applied for any block encryption algorithm with any
* block size, such as the DES or the IDEA cipher.
*/
static void cfbshift(register byteptr iv, register byteptr buf,
register int count, int blocksize)
/* iv is the initialization vector.
* buf is the buffer pointer.
* count is the number of bytes to shift in...must be > 0.
* blocksize is 8 bytes for DES or IDEA ciphers.
*/
{
int retained;
if (count)
{
retained = blocksize-count; /* number bytes in iv to retain */
/* left-shift retained bytes of IV over by count bytes to make room */
while (retained--)
{
*iv = *(iv+count);
iv++;
}
/* now copy count bytes from buf to shifted tail of IV */
do *iv++ = *buf++;
while (--count);
}
} /* cfbshift */
/* Key schedules for IDEA encryption and decryption */
static IDEAkey Z;
static word16 *iv_idea; /* pointer to IV for CFB or CBC */
static boolean cfb_dc_idea; /* TRUE iff CFB decrypting */
/* initkey_idea initializes IDEA for ECB mode operations */
static void initkey_idea(byte key[16], boolean decryp)
{
word16 userkey[8]; /* IDEA key is 16 bytes long */
int i;
/* Assume each pair of bytes comprising a word is ordered MSB-first. */
for (i=0; i<8; i++)
{
userkey[i] = (key[0]<<8) + key[1];
key++; key++;
}
en_key_idea(userkey,Z);
if (decryp)
{
de_key_idea(Z,Z); /* compute inverse key schedule DK */
}
for (i=0; i<8; i++) /* Erase dangerous traces */
userkey[i] = 0;
} /* initkey_idea */
/* Run a 64-bit block thru IDEA in ECB (Electronic Code Book) mode,
using the currently selected key schedule.
*/
static void idea_ecb(word16 *inbuf, word16 *outbuf)
{
/* Assume each pair of bytes comprising a word is ordered MSB-first. */
#ifndef HIGHFIRST /* If this is a least-significant-byte-first CPU */
word16 x;
/* Invert the byte order for each 16-bit word for internal use. */
x = inbuf[0]; outbuf[0] = x >> 8 | x << 8;
x = inbuf[1]; outbuf[1] = x >> 8 | x << 8;
x = inbuf[2]; outbuf[2] = x >> 8 | x << 8;
x = inbuf[3]; outbuf[3] = x >> 8 | x << 8;
cipher_idea(outbuf, outbuf, Z);
x = outbuf[0]; outbuf[0] = x >> 8 | x << 8;
x = outbuf[1]; outbuf[1] = x >> 8 | x << 8;
x = outbuf[2]; outbuf[2] = x >> 8 | x << 8;
x = outbuf[3]; outbuf[3] = x >> 8 | x << 8;
#else /* HIGHFIRST */
/* Byte order for internal and external representations is the same. */
cipher_idea(inbuf, outbuf, Z);
#endif /* HIGHFIRST */
} /* idea_ecb */
/*
* initcfb - Initializes the IDEA key schedule tables via key,
* and initializes the Cipher Feedback mode IV.
* References context variables cfb_dc_idea and iv_idea.
*/
void initcfb_idea(word16 iv0[4], byte key[16], boolean decryp)
/* iv0 is copied to global iv_idea, buffer will be destroyed by ideacfb.
key is pointer to key buffer.
decryp is TRUE if decrypting, FALSE if encrypting.
*/
{
iv_idea = iv0;
cfb_dc_idea = decryp;
initkey_idea(key,FALSE);
} /* initcfb_idea */
/*
* ideacfb - encipher a buffer with IDEA enciphering algorithm,
* using Cipher Feedback (CFB) mode.
*
* Assumes initcfb_idea has already been called.
* References context variables cfb_dc_idea and iv_idea.
*/
void ideacfb(byteptr buf, int count)
/* buf is input, output buffer, may be more than 1 block.
* count is byte count of buffer. May be > IDEABLOCKSIZE.
*/
{
int chunksize; /* smaller of count, IDEABLOCKSIZE */
word16 temp[IDEABLOCKSIZE/2];
while ((chunksize = min(count,IDEABLOCKSIZE)) > 0)
{
idea_ecb(iv_idea,temp); /* encrypt iv_idea, making temp. */
if (cfb_dc_idea) /* buf is ciphertext */
/* shift in ciphertext to IV... */
cfbshift((byte *)iv_idea,buf,chunksize,IDEABLOCKSIZE);
/* convert buf via xor */
xorbuf(buf,(byte *)temp,chunksize); /* buf now has enciphered output */
if (!cfb_dc_idea) /* buf was plaintext, is now ciphertext */
/* shift in ciphertext to IV... */
cfbshift((byte *)iv_idea,buf,chunksize,IDEABLOCKSIZE);
count -= chunksize;
buf += chunksize;
}
} /* ideacfb */
/*
close_idea function erases all the key schedule information when
we are all done with a set of operations for a particular IDEA key
context. This is to prevent any sensitive data from being left
around in memory.
*/
void close_idea(void) /* erase current key schedule tables */
{
short i;
for (i = 0; i < KEYLEN; i++)
Z[i] = 0;
} /* close_idea() */
/********************************************************************/
/*
* These buffers are used by init_idearand, idearand, and close_idearand.
*/
static word16 dtbuf_idea[4] = {0}; /* buffer for enciphered timestamp */
static word16 randseed_idea[4] = {0}; /* seed for IDEA random # generator */
static word16 randbuf_idea[4] = {0}; /* buffer for IDEA random # generator */
static byte randbuf_idea_counter = 0; /* # of random bytes left in randbuf_idea */
static IDEAkey randkey_idea; /* Expanded key for IDEA random # generator */
/*
* init_idearand - initialize idearand, IDEA random number generator.
* Used for generating cryptographically strong random numbers.
* Much of the design comes from Appendix C of ANSI X9.17.
* key is pointer to IDEA key buffer.
* seed is pointer to random number seed buffer.
* tstamp is a 32-bit timestamp
*/
void init_idearand(byte key[16], byte seed[8], word32 tstamp)
{
int i;
en_key_idea((word16 *)key, randkey_idea);
for (i=0; i<4; i++) /* capture timestamp material */
{ dtbuf_idea[i] = tstamp; /* get bottom word */
tstamp = tstamp >> 16; /* drop bottom word */
/* tstamp has only 4 bytes-- last 4 bytes will always be 0 */
}
/* Start with enciphered timestamp: */
cipher_idea(dtbuf_idea, dtbuf_idea, randkey_idea);
/* initialize seed material */
for (i=0; i<8; i++)
((byte *)randseed_idea)[i] = seed[i];
randbuf_idea_counter = 0; /* # of random bytes left in randbuf_idea */
} /* init_idearand */
/*
* idearand - IDEA pseudo-random number generator
* Used for generating cryptographically strong random numbers.
* Much of the design comes from Appendix C of ANSI X9.17.
*/
byte idearand(void)
{
int i;
if (randbuf_idea_counter==0) /* if random buffer is spent...*/
{ /* Combine enciphered timestamp with seed material: */
for (i=0; i<4; i++)
randseed_idea[i] ^= dtbuf_idea[i];
cipher_idea(randseed_idea,randbuf_idea,randkey_idea); /* fill new block */
/* Compute new seed vector: */
for (i=0; i<4; i++)
randseed_idea[i] = randbuf_idea[i] ^ dtbuf_idea[i];
cipher_idea(randseed_idea,randseed_idea,randkey_idea); /* fill new seed */
randbuf_idea_counter = 8; /* reset counter for full buffer */
}
/* Take a byte from randbuf_idea: */
return(((byte *)randbuf_idea)[--randbuf_idea_counter]);
} /* idearand */
void close_idearand(void)
{ /* Erase random IDEA buffers and wipe out IDEA key info */
int i;
for (i=0; i<4; i++)
{ randbuf_idea[i] = 0;
randseed_idea[i] = 0;
dtbuf_idea[i] = 0;
}
for (i = 0; i<KEYLEN; i++)
randkey_idea[i] = 0;
} /* close_idearand */
/* end of idea.c */
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.