Cryptography
Computer Science
Computer Catlog
Cryptography - TOC

IDEA


    The cipher named IDEA (International Data Encryption Algorithm) encrypts 64-bit plaintext to 64-bit ciphertext blocks, using a 128-bit input key K. Based in part on a novel generalization of the Feistel structure, it consists of 8 computationally identical rounds followed by an output transformation. Round r uses six 16-bit subkeys K(r)i ,
1  i  6, to transform a 64-bit input X into an output of four 16-bit blocks, which are input to the next round. The round 8 output enters the output transformation, employing four additional subkeys K(9)i , 1  i  4 to produce the final ciphertext Y = (Y1; Y2; Y3; Y4). All subkeys are derived from K.


    A dominant design concept in IDEA is mixing operations from three different algebraic groups of 2n elements. The corresponding group operations on sub-blocks a and b of bitlength n = 16 are bitwise XOR: ab; addition mod 2n: (a+b) AND 0xFFFF, denoted
ab; and (modified) multiplication mod 2n+1, with 0 Z2n associated with 2n Z2n+1:
ab.
IDEA Computation Path

IDEA Algorithm

IDEA Key Schedule

    The key schedule of Algorithm may be converted into a table which lists, for each of the 52 keys blocks, which 16 (consecutive) bits of the input key K form it.


    IDEA decryption: Decryption is achieved using Algorithm with the ciphertext Y provided as input M, and the same encryption key K, but the following change to the key schedule. First use K to derive all encryption subkeys K(r) i ; from these compute the decryption subkeys K'(r) i per Table; then use K'(r)i in place of K(r)i in Algorithm . In Table, -Ki denotes the additive inverse (mod 216) of Ki: the integer u = (216 +Ki) AND 0xFFFF, 0  u  216 -1. K-1 i denotes the multiplicative inverse (mod 216 +1) of Ki, also in {0,1,…,216-1}, derivable by the Extended Euclidean algorithm, which on inputs
a  b  0 returns integers x and y such that ax + by = gcd(a; b). Using a = 216 + 1 and b = Ki, the gcd is always 1 (except for Ki = 0, addressed separately) and thus K-1i = y, or 216 +1+y if y < 0. When Ki = 0, this input is mapped to 216 (since the inverse is defined by KiK-1i = 1;) and (216)-1 = 216 is then defined to give K-1i = 0.

    Definition of : In IDEA, ab corresponds to a (modified) multiplication, modulo 216+1, of unsigned 16-bit integers a and b, where 0 Z216 is associated with 216 Z* 216+1 as follows: if a = 0 or b = 0, replace it by 216 (which is=-1 mod 216 + 1) prior to modular multiplication; and if the result is 216, replace this by 0. Thus, maps two 16- bit inputs to a 16-bit output. Pseudo-code foris as follows (for ordinary multiplication mod 216 + 1), for c a 32-bit unsigned integer: if (a = 0) r (0x10001 - b) (since 216b =-b), elseif (b = 0) r (0x10001 - a) (by similar reasoning), else {c ab; r ((c AND 0xFFFF) - (c >>16)); if (r < 0) r (0x10001 +r)}, with return value (r AND 0xFFFF) in all 3 cases.
IDEA Decryption Subkeys

    Implementing ab mod 2n+1: Multiplication mod 216+1may be efficiently implemented as follows, for 0  a,b  216. Let c = ab = c0 - 232 +cH - 216 +cL, where c0{0; 1} and 0  cL; cH < 216. To compute c' = c mod (216 + 1), first obtain cL and cH by standard multiplication. For a = b = 216, note that c0 = 1, cL = cH = 0, and c' = (-1)(-1) = 1, since 216 =-1 mod (216+1); otherwise, c0 = 0. Consequently, c' = cL - cH + c0 if cL  cH, while c' = cL - cH + (216 + 1) if cL < cH (since then - 216 < cL - cH < 0).

    Security of IDEA: For the full 8-round IDEA, other than attacks on weak keys, no published attack is better than exhaustive search on the 128-bit key space. The security of IDEA currently appears bounded only by the weaknesses arising from the relatively small (compared to its keylength) blocklength of 64 bits.
IDEA Decryption Sample


Google