International Data Encryption Algorithm

The International Data Encryption Algorithm or IDEA is a European standard block cipher. It is an iterated block cipher, but does not have a Feistel structure. Block size is 64 bits, key 128. No S-boxes are used.

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 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)
{
   // 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
        return( (x*y) % MOD ) ;
}

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.