Cryptography
 Computer Science Computer Catlog Cryptography Catlog

 Caesar Cipher Digital Signature Public key cryptography Symmetric vs. public-key Key Management Stream Ciphers Self-Synchronizing Ciphers Feedback Shift Registers Modes of Operation Multiple Encryption Transposition Ciphers Substitution Ciphers Poly-alpha Substitutions Poly-alpha Cipher Machine Cryptanalysis Ciphers Data Encryption Standard DES Algorithm IDEA Algorithm RC5 Algorithm RSA Encryption Rabin Encryption ElGamal Encryption MD4 & MD5 Secure Hash Algorithm Kerberos Authentication Diffie-Hellman protocols Key Management Life Cycle

## 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 , 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: a b; addition mod 2n: (a+b) AND 0xFFFF, denoted
a b; and (modified) multiplication mod 2n+1, with 0 Z2n associated with 2n Z2n+1:
a b.   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 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 Ki K-1i = 1;) and (216)-1 = 216 is then defined to give K-1i = 0.

Definition of : In IDEA, a b 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 for is 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. 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. 