International Data Encryption Algorithm: Difference between revisions
imported>Sandy Harris |
John Leach (talk | contribs) m (Text replacement - "{{subpages}}" to "{{PropDel}}<br><br>{{subpages}}") |
||
(4 intermediate revisions by one other user not shown) | |||
Line 1: | Line 1: | ||
{{subpages}} | {{PropDel}}<br><br>{{subpages}} | ||
The '''International Data Encryption Algorithm''' or '''IDEA''' | The '''International Data Encryption Algorithm''' or '''IDEA''' | ||
<ref name=idea>{{citation | <ref name=idea>{{citation | ||
Line 8: | Line 8: | ||
| date = 1992 | | date = 1992 | ||
}}</ref> | }}</ref> | ||
is a European standard [[block cipher]] | is a European standard [[block cipher]]. Block size is 64 bits, key size 128 bits. No [[Block cipher#S-boxes|S-boxes]] are used. The design was the PhD thesis of [[Xuejia Lai]], supervised by [[James Massey]], at [[ETH Zurich]]. | ||
IDEA achieves [[Block_cipher#Nonlinearity|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<sup>16</sup>. The third is basically multiplication, modulo 2<sup>16</sup>+1, but modified so that the "x*0 yields zero for all x" case does not weaken the cipher. | IDEA achieves [[Block_cipher#Nonlinearity|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<sup>16</sup>. The third is basically multiplication, modulo 2<sup>16</sup>+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 [[Block cipher#Lai-Massey scheme|Lai-Massey construction]]. | |||
== IDEA multiplication == | == IDEA multiplication == | ||
Line 73: | Line 75: | ||
unsigned idea_multiply(unsigned x, unsigned y) | unsigned idea_multiply(unsigned x, unsigned y) | ||
{ | { | ||
unsigned z ; | |||
// make sure inputs are in range | // make sure inputs are in range | ||
x %= MAX ; | x %= MAX ; | ||
Line 83: | Line 87: | ||
else if( y == 0 ) | else if( y == 0 ) | ||
return(MOD - x) | return(MOD - x) | ||
else | else { | ||
// calculate the result | |||
z = (x*y) % MOD ; | |||
// avoid returning MAX | |||
if( z == MAX ) | |||
z = 0 ; | |||
return( z ) ; | |||
} | |||
} | } | ||
Latest revision as of 05:49, 8 April 2024
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 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 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 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 ) ; } } 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 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. References
|