/* $Id$ * * The basic IDEA transformation * * Please be aware that IDEA IS PATENT ENCUMBERED; see the note below. * ------------------------- * * This implementation is taken from pgp, see note below. * * Only primitive operations are done here, chaining modes etc * are implemented in a higher level program. * ********************************************************************** * * 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. * * Extensively optimized and restructured by Colin Plumb. * *********************************************************************** * * Some changes including endianness cleanup done by Niels Möller. * */ /* IDEA is patent encumbered; the following information was copied from the idea.c extension for the GNU Privacy Guard. The IDEA algorithm is patented by Ascom Systec Ltd. of CH-5506 Maegenwil, Switzerland, who allow it to be used on a royalty-free basis for certain non-profit applications. Commercial users must obtain a license from the company in order to use IDEA. IDEA may be used on a royalty-free basis under the following conditions: Free use for private purposes: The free use of software containing the algorithm is strictly limited to non revenue generating data transfer between private individuals, ie not serving commercial purposes. Requests by freeware developers to obtain a royalty-free license to spread an application program containing the algorithm for non-commercial purposes must be directed to Ascom. Special offer for shareware developers: There is a special waiver for shareware developers. Such waiver eliminates the upfront fees as well as royalties for the first US$10,000 gross sales of a product containing the algorithm if and only if: 1. The product is being sold for a minimum of US$10 and a maximum of US$50. 2. The source code for the shareware is available to the public. Special conditions for research projects: The use of the algorithm in research projects is free provided that it serves the purpose of such project and within the project duration. Any use of the algorithm after the termination of a project including activities resulting from a project and for purposes not directly related to the project requires a license. Ascom Tech requires the following notice to be included for freeware products: This software product contains the IDEA algorithm as described and claimed in US patent 5,214,703, EPO patent 0482154 (covering Austria, France, Germany, Italy, the Netherlands, Spain, Sweden, Switzerland, and the UK), and Japanese patent application 508119/1991, "Device for the conversion of a digital block and use of same" (hereinafter referred to as "the algorithm"). Any use of the algorithm for commercial purposes is thus subject to a license from Ascom Systec Ltd. of CH-5506 Maegenwil (Switzerland), being the patentee and sole owner of all rights, including the trademark IDEA. Commercial purposes shall mean any revenue generating purpose including but not limited to: i) Using the algorithm for company internal purposes (subject to a site license). ii) Incorporating the algorithm into any software and distributing such software and/or providing services relating thereto to others (subject to a product license). iii) Using a product containing the algorithm not covered by an IDEA license (subject to an end user license). All such end user license agreements are available exclusively from Ascom Systec Ltd and may be requested via the WWW at http://www.ascom.ch/systec or by email to idea@ascom.ch. Use other than for commercial purposes is strictly limited to non-revenue generating data transfer between private individuals. The use by government agencies, non-profit organizations, etc is considered as use for commercial purposes but may be subject to special conditions. Any misuse will be prosecuted. */ #include "crypto_types.h" #include #include /*-------------------------------------------------------------*/ #define low16(x) ((x) & 0xffff) /* * Multiplication, modulo (2**16)+1 * Note that this code is structured 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(UINT16 a, UINT16 b) { register UINT32 p; p = (UINT32)a * b; if (p) { b = low16(p); a = p>>16; return (b - a) + (b < a); } else if (a) { return 1-b; } else { return 1-a; } } /* mul */ #endif /* SMALL_CACHE */ /* * Compute the multiplicative inverse of x, modulo 65537, using Euclid's * algorithm. It is unrolled twice to avoid swapping the registers each * iteration, and some subtracts of t have been changed to adds. */ static const 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 */ /* * Expand a 128-bit user key to a working encryption key ctx */ void idea_expand(UINT16 *ctx, const UINT8 *userkey) { int i,j; for (j=0; j<8; j++) { ctx[j] = (userkey[0]<<8) + userkey[1]; userkey += 2; } for (i=0; j < IDEA_KEYLEN; j++) { i++; ctx[i+7] = ctx[i & 7] << 9 | ctx[(i+1) & 7] >> 7; ctx += i & 8; i &= 7; } } /* idea_expand */ /* * Compute IDEA decryption key DK from an expanded IDEA encryption key EK * Note that the input and output may be the same. Thus, the key is * inverted into an internal buffer, and then copied to the output. */ void idea_invert(UINT16 *d, const UINT16 *e) { int i; UINT16 t1, t2, t3; UINT16 temp[IDEA_KEYLEN]; UINT16 *p = temp + IDEA_KEYLEN; t1 = inv(*e++); t2 = -*e++; t3 = -*e++; *--p = inv(*e++); *--p = t3; *--p = t2; *--p = t1; for (i = 0; i < IDEA_ROUNDS-1; i++) { t1 = *e++; *--p = *e++; *--p = t1; t1 = inv(*e++); t2 = -*e++; t3 = -*e++; *--p = inv(*e++); *--p = t2; *--p = t3; *--p = t1; } t1 = *e++; *--p = *e++; *--p = t1; t1 = inv(*e++); t2 = -*e++; t3 = -*e++; *--p = inv(*e++); *--p = t3; *--p = t2; *--p = t1; /* Copy and destroy temp copy */ memcpy(d, temp, sizeof(temp)); memset(temp, 0, sizeof(temp)); } /* idea_invert */ /* * MUL(x,y) computes x = x*y, modulo 0x10001. Requires two temps, * t16 and t32. x is modified, and 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 /* !SMALL_CACHE */ #ifdef AVOID_JUMPS #define MUL(x,y) (x = low16(x-1), t16 = low16((y)-1), \ t32 = (UINT32)x*t16 + x + t16 + 1, x = low16(t32), \ t16 = t32>>16, x = (x-t16) + (x>16, \ x = (x-t16)+(x> 8; *(p)++ = (src) & 0xff; \ } while(0) /* IDEA encryption/decryption algorithm */ /* Note that in and out can be the same buffer */ void idea_crypt(const UINT16 *key, UINT8 *dest, const UINT8 *src) { register UINT16 x1, x2, x3, x4, s2, s3; /* Setup */ char2word(x1, src); char2word(x2, src); char2word(x3, src); char2word(x4, src); /* Encrypt */ { #ifndef SMALL_CACHE register UINT16 t16; /* Temporaries needed by MUL macro */ register UINT32 t32; #endif int r = IDEA_ROUNDS; do { MUL(x1,*key++); x2 += *key++; x3 += *key++; MUL(x4, *key++); s3 = x3; x3 ^= x1; MUL(x3, *key++); s2 = x2; x2 ^= x4; x2 += x3; MUL(x2, *key++); x3 += x2; x1 ^= x2; x4 ^= x3; x2 ^= s3; x3 ^= s2; } while (--r); MUL(x1, *key++); x3 += *key++; x2 += *key++; MUL(x4, *key); } word2char(x1, dest); word2char(x3, dest); word2char(x2, dest); word2char(x4, dest); } /* idea_crypt */ /*-------------------------------------------------------------*/