 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 (see Figure 7.11). Round r uses six 16-bit subkeys A',(r), 1 < г < 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 Kj9 1 < г < 4 to produce the final ciphertext Y = (Yi. Y2. Y2, Ki). 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: афЬ addition mod 2": (a + b) AND OxFFFF, denoted affl b and (modified) multiplication mod 2n+l, with 0 e Z2» associated with 2” € Z2->+i: aQ>b (see Note 7.104). Figure 7.11: IDEA computation path.

7.101 Algorithm IDEA encryption

INPUT: 64-bit plaintext M = mi... mo4; 128-bit key К = k4... k428-

OUTPUT: 64-bit ciphertext block У = (Yi, Y2, Y3, Y4). (For decryption, see Note 7.103.)

• 1. (key schedule) Compute 16-bit subkeys К[г... , A',;’ * for rounds 1 < r < 8, and k[9 ... , A'|9) for the output transformation, using Algorithm 7.102.
• 2. (11Д2Д3Д4) (mi .. .mia, mi7 .. .m32, m33 ... m48, m49 .. .m64), where Xj. is a 16-bit data store.
• 3. For round r from 1 to 8 do: • 4. (output transformation) Д <- XiQK[9 Y4 <- X4qK{9) ,Y2 <- X3 EB K(9 Y3 <- Х2ШК^
• 7.102 Algorithm IDEA key schedule (encryption)

INPUT: 128-bit key К = kx... kx2&.

OUTPUT: 52 16-bit key sub-blocks A'fr l for 8 rounds r and the output transformation.

• 1. Order the subkeys k[1} ... К{61],1<[2)... K(2),... , hf]... K^8),k[9) ... I<{9).
• 2. Partition К into eight 16-bit blocks; assign these directly to the first 8 subkeys.
• 3. Do the following until all 52 subkeys are assigned: cyclic shift К left 25 bits; partition the result into 8 blocks; assign these blocks to the next 8 subkeys.

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

• 7.103 Note (IDEA decryption) Decryption is achieved using Algorithm 7.101 with the cipher- text Y provided as input M, and the same encryption key K, but the following change to the key schedule. First use К to derive all encryption subkeys A^r); from these compute the decryption subkeys K'[r'1 per Table 7.11; then use К'г] in place of Ir) in Algorithm 7.101. In Table 7.11, —Kx denotes the additive mverse (mod 21G) of К,: the mteger и = (216 - Kx) AND OxFFFF, 0 < и < 216 — 1. K~l denotes the multiplicative inverse (mod 216 + 1) of Ki, also in {0,1,... , 21G - 1}, derivable by the Extended Euclidean algorithm (Algorithm 2.107), which on inputs a > b > 0 returns integers x and у such that ax + by = gcd(a, b). Using a = 216 + 1 and b = Ki, the ged is always 1 (except for Ki = 0, addressed separately) and thus K, 1 = y, or 216 + 1 + у if у < 0. When Kx = 0, this input is mapped to 21G (since the inverse is defined by K,®K~1 = 1; see Note 7.104) and (216)-1 = 21C is then defined to give K~1 = 0.
• 7.104 Note (definition of®) I11 IDEA, a®b corresponds to a (modified) multiplication, modulo 21G+1, of unsigned 16-bit integers a and b, where 0 € Z2io is associated with 216 e , 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 (cf. Note 7.105, for ordinary
 round г             Table 7.11: IDEA decryption subkeys K'r* derived from encryption subkeys кг

multiplication mod 21G + 1), for c a 32-bit unsigned integer: if (a = 0) r a- (0x100 01 - b) (since 216b = -b), elseif (b = 0) r <- (0x10001 - a) (by similar reasoning), else {c <— ab; r <— ((c AND OxFFFF) - (c >> 16)); if (r < 0) r (0x10001 + r)}, with return value (r AND OxFFFF) in all 3 cases.

• 7.105 Note (implementing ab mod 2n +1) Multiplication mod 216 +1 may be efficiently implemented as follows, for 0 < a, b < 216 (cf. §14.3.4). Let c = ab = со ■ 232 + ch ■ 216 + cl, where c0 € {0,1} and 0 < cl, ch < 21G. To compute с' = c mod (21C + 1), first obtain cl and ch by standard multiplication. For a = b = 21C, note that со = 1, cl = сц = 0, and c = (-1)(-1) = 1, since 21C = -1 mod (216 + 1); otherwise, со = 0. Consequently, c1 = cl - ch + cq if cl > ch, while c' = cl - ch + (21G + 1) if cl < ch (smce then —21G L-cH < 0).
• 7.106 Example (IDEA test vectors) Sample data for IDEA encryption of 64-bit plaintext M using 128-bitkey К is given in Table 7.12. All entries are 16-bit values displayed in hexadecimal. Table 7.13 details the corresponding decryption of the resulting 64-bit ciphertext C under the same key К.
 128-bit key К = (1,2,3,4,5,6,7,8) 64-bit plaintext M = (0,1,2,3) Г КГ тЛг) X, x2 x3 x4 1 0001 0002 0003 0004 0005 0006 OOfO OOf 5 010a 0105 2 0007 0008 0400 0600 0800 OaOO 222f 21b5 f 45e e959 3 OCOO OeOO 1000 0200 0010 0014 Of 86 3 9be 8ee8 1173 4 0018 001C 0020 0004 0008 000C 57df ac58 c65b ba4d 5 2800 3000 3800 4000 0800 1000 8e8l ba9c f 77f 3a4a 6 1800 2000 0070 0080 0010 0020 6942 9409 e2lb lc64 7 0030 0040 0050 0060 0000 2000 99d0 C7f 6 5331 620e 8 4000 6000 8000 aOOO C000 eOOl 0a24 0098 ec6b 4925 9 0080 00C0 0100 0140 - — llfb ed2b 0198 6de5

Table 7.12: IDEA encryption sample: round subkeys and ciphertext (Xi, X2, X3, X4).

7.107 Note (security■ of IDEA) For the full 8-round IDEA, other than attacks on weak keys (see page 279), 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.

 К = (1>2,3,4,5,6,7,8) C = (Ilfb,ed2b,0198,6de5) r K7^ KV KT 6 X, x2 X3 x4 1 fed f f40 ffOO 659a C000 eOOl d98d d33l 27f 6 82b8 2 fffd 8000 aOOO cccc 0000 2000 bc4d e26b 9449 a576 3 a556 ffbO f fcO 52ab 0010 0020 0aa4 f 7ef da9c 24e3 4 554b f f 90 eOOO feOl 0800 1000 ca46 f e5b dc58 ll6d 5 332d C800 dOOO fffd 0008 000c 748f 8f 08 3 9da 45CC 6 4aab f feO f fe4 cOOl 0010 0014 3266 045e 2fb5 b02e 7 aa96 fOOO f 200 f f 81 0800 OaOO 0690 050a OOf d ldf a 8 4925 fcOO f f f 8 552b 0005 0006 0000 0005 0003 000c 9 0001 fffe fffd C001 - - 0000 0001 0002 0003

Table 7.13: IDEA decryption sample: round subkeys and variables (Xi, X2, Хз, X4).

•  Thus the operands of © are from a set of cardinality 216 (Ц^+i) as are those of ф and BB.