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).

IDEA computation path

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:[1] 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).

  • [1] Thus the operands of © are from a set of cardinality 216 (Ц^+i) as are those of ф and BB.
 
Source
< Prev   CONTENTS   Source   Next >