# International Data Encryption Algorithm  Main Article Discussion Related Articles  [?] Bibliography  [?] External Links  [?] Citable Version  [?] This editable Main Article is under development and subject to a disclaimer. [edit intro]

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 216. The third is basically multiplication, modulo 216+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 216+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 ) ;
}
}
```