International Data Encryption Algorithm
This article may be deleted soon.  

The International Data Encryption Algorithm or IDEA ^{[1]} is a European standard block cipher. Block size is 64 bits, key size 128 bits. No Sboxes are used. The design was the PhD thesis of Xuejia Lai, supervised by James Massey, at ETH Zurich. IDEA achieves nonlinearity by mixing operations from three different algebraic systems. All operations have 16bit words as both input and output. Two are just bitwise XOR and addition modulo 2^{16}. The third is basically multiplication, modulo 2^{16}+1, but modified so that the "x*0 yields zero for all x" case does not weaken the cipher. IDEA introduced a new class of block cipher design, the LaiMassey construction. IDEA multiplicationTo see how the IDEA multiplication works, consider the multiplication table modulo 5: 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 If we take out the zeros, we get this table: 1 2 3 4 1 1 2 3 4 2 2 4 1 3 3 3 1 4 2 4 4 3 2 1 Here all output values occur equally often and every column and every row is a permutation of the set (1,2,3,4). These properties are provably true for any multiplication modulo a prime modulus. The operation is invertible as long as the modulus is prime. Our inputs are 2bit numbers (0,1,2,3). We map them to (4,1,2,3) and then multiply them modulo 5; all multiplications use the nonzero part of the table. Results are in (1,2,3,4), which we map back to (1,2,3,0) so we get 2bit output. C code for IDEA multiplication of 2bit numbers (range 03) would be: #define NBITS 2 #define MAX (1<<NBITS) #define MOD (MAX+1) unsigned idea_multiply(unsigned x, unsigned y) { unsigned z ; // make sure inputs are in range x %= MAX ; y %= MAX ; // adjust the range // avoid multiplying by zero if( x == 0 ) x = MAX ; if( y == 0 ) y = MAX ; // calculate the result // see table above z = (x*y) % MOD ; // adjust it // avoid returning MAX if( z == MAX ) z = 0 ; return( z ) ; } Change NBITS to 16 and you have real IDEA multiplication, operating on 16bit quantities. This works correctly because MOD is then the prime 2^{16}+1. On a 32bit processor, you need to add a bit of extra code to avoid having MAX*MAX overflow a 32bit register, but that is the only special case. Actually, we can take advantage of the fact that MAX is 1 modulo MOD to handle that special case and avoid the multiplication in some other cases. The code then looks something like this: unsigned idea_multiply(unsigned x, unsigned y) { unsigned z ; // make sure inputs are in range x %= MAX ; y %= MAX ; if(( x == 0 ) && ( y == 0 )) return(1) ; else if( x == 0 ) return(MOD  y) ; else if( y == 0 ) return(MOD  x) else { // calculate the result z = (x*y) % MOD ; // avoid returning MAX if( z == MAX ) z = 0 ; return( z ) ; } } OverheadsThe IDEA multiplication operation is highly nonlinear and has good avalanche properties; every output bit depends on all the inputs. It is not nearly as cheap as addition or XOR, but it is reasonably fast on a modern 32bit or larger CPU. In most environments it will be more expensive than Sbox lookups but in some, such as an embedded processor with limited cache, it may be cheaper. In any case, IDEA uses only 8 rounds so it can afford a moderately expensive operation in the round function. References
