International Data Encryption Algorithm

The International Data Encryption Algorithm or IDEA is a European standard block cipher. Block size is 64 bits, key size 128 bits. No S-boxes 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 16-bit words as both input and output. Two are just bitwise XOR and addition modulo 2¹⁶. The third is basically multiplication, modulo 2¹⁶+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 Lai-Massey construction.

IDEA multiplication

To 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 2-bit numbers (0,1,2,3). We map them to (4,1,2,3) and then multiply them modulo 5; all multiplications use the non-zero part of the table. Results are in (1,2,3,4), which we map back to (1,2,3,0) so we get 2-bit output.

C code for IDEA multiplication of 2-bit numbers (range 0-3) 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 16-bit quantities. This works correctly because MOD is then the prime 2¹⁶+1. On a 32-bit processor, you need to add a bit of extra code to avoid having MAX*MAX overflow a 32-bit 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 ) ;
   }  
}

Overheads

The 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 32-bit or larger CPU. In most environments it will be more expensive than S-box 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.