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 Kj^{9} 1 < г < 4 to produce the final ciphertext Y = (Yi. Y_{2}. Y_{2}, Ki). All subkeys are derived from K.
A dominant design concept in IDEA is mixing operations from three different algebraic groups of 2^{n} 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 2^{n}+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... mo_{4}; 128-bit key К = k_{4}... k_{42}8-
OUTPUT: 64-bit ciphertext block У = (Yi, Y_{2}, Y_{3}, Y_{4}). (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 .. .m_{32}, m_{33} ... m_{48}, m_{49} .. .m_{64}), where Xj. is a 16-bit data store.
- 3. For round r from 1 to 8 do:
- 4. (output transformation) Д <- XiQK[^{9} Y_{4} <- X_{4}qK^{{9)} ,Y_{2} <- X_{3} EB K^{(9} Y_{3} <- Х_{2}ШК^
- 7.102 Algorithm IDEA key schedule (encryption)
INPUT: 128-bit key К = k_{x}... k_{x2}&.
OUTPUT: 52 16-bit key sub-blocks A'f^{r l} for 8 rounds r and the output transformation.
- 1. Order the subkeys k[^{1}} ... К^{{}6^{1}],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 I^{r)} in Algorithm 7.101. In Table 7.11, —K_{x} denotes the additive mverse (mod 2^{1G}) of К,: the mteger и = (2^{16} - K_{x}) AND OxFFFF, 0 < и < 2^{16} — 1. K~^{l} denotes the multiplicative inverse (mod 2^{16} + 1) of Ki, also in {0,1,... , 2^{1G} - 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 = 2^{16} + 1 and b = Ki, the ged is always 1 (except for Ki = 0, addressed separately) and thus K, ^{1} = y, or 2^{16} + 1 + у if у < 0. When K_{x} = 0, this input is mapped to 2^{1G} (since the inverse is defined by K,®K~^{1} = 1; see Note 7.104) and (2^{16})^{-1} = 2^{1C} is then defined to give K~^{1} = 0.
- 7.104 Note (definition of®) I11 IDEA, a®b corresponds to a (modified) multiplication, modulo 2^{1G}+1, of unsigned 16-bit integers a and b, where 0 € Z_{2}io is associated with 2^{16} e , as follows:^{[1]} if a = 0 or b = 0, replace it by 2^{16} (which is = — 1 mod 2^{16} + 1) prior to modular multiplication; and if the result is 2^{16}, 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 2^{1G} + 1), for c a 32-bit unsigned integer: if (a = 0) r a- (0x100 01 - b) (since 2^{16}b = -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 2^{n} +1) Multiplication mod 2^{16} +1 may be efficiently implemented as follows, for 0 < a, b < 2^{16} (cf. §14.3.4). Let c = ab = со ■ 2^{32} + ch ■ 2^{16} + cl, where c_{0} € {0,1} and 0 < cl, ch < 2^{1G}. To compute с' = c mod (2^{1C} + 1), first obtain cl and ch by standard multiplication. For a = b = 2^{1C}, note that со = 1, cl = сц = 0, and c = (-1)(-1) = 1, since 2^{1C} = -1 mod (2^{16} + 1); otherwise, со = 0. Consequently, c^{1} = cl - ch + cq if cl > ch, while c' = cl - ch + (2^{1G} + 1) if cl < ch (smce then —2^{1G}
L-c_{H} < 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, |
x_{2} |
x_{3} |
x_{4} |
||||
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, X_{2}, X_{3}, X_{4}).
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 |
K^{7}^ |
KV |
KT |
6 |
X, |
x_{2} |
X_{3} |
x_{4} |
||
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, X_{2}, Хз, X_{4}).
- [1] Thus the operands of © are from a set of cardinality 216 (Ц^+i) as are those of ф and BB.