19.3 Calculating the Round Key

Encryption and decryption each require the generation of L_r round keys, called collectively the key schedule. This occurs through expansion of the secret user key by attaching recursively derived 4-byte words ki = (k_0,i, k_1,i, k_2,i, k_3,i) to the user key.

The first L_k words k₀,..., of the key schedule are formed from the secret user key itself. For L_k Î {4,6} the next 4-byte word k_i is determined by XOR-ing the preceding word k_i−1 with . If i ≡ 0 mod L_k, then a function (k, i) is applied before the XOR operation, which is composed of a cyclic left shift (left rotation) r(k) of k bytes, a substitution S(r(k)) from the Rijndael S-box (we shall return to this later), and an XOR with a constant c (⌊i/L_k⌋), so that altogether the function F is given by (k, i) := S(r(k)) ⊕ c (⌊i/L_k⌋).

The constants c(j) are defined by c(j) := (rc(j), 0, 0, 0), where rc(j) are recursively determined elements from : rc(1) := 1, rc(j) := rc(j − 1). · x = x^j−1. Expressed in numerical values, this is equivalent to rc(1) := '01', rc(j) := rc(j − 1) • '02'. From the standpoint of programming, rc(j) is computed by a (j − 1)-fold execution of the function xtime described above, beginning with the argument 1, or more rapidly by access to a table (Tables 19.6 and 19.7).

Table 19.6: rc(j) constants (hexadecimal)

'01'	'02'	'04'	'08'	'10'	'20'	'40'	'80'	'1B'	'36'
'6C'	'D8'	'AB'	'4D'	'9A'	'2F'	'5E'	'BC'	'63'	'C6'
'97'	'35'	'6A'	'D4'	'B3'	'7D'	'FA'	'EF'	'C5'	'91'

Table 19.7: rc(j) constants (binary)

00000001	00000010	00000100	00001000	00010000
00100000	01000000	10000000	00011011	00110110
01101100	11011000	10101011	01001101	10011010
00101111	01011110	10111100	01100011	11000110
10010111	00110101	01101010	11010100	10110011
01111101	11111010	11101111	11000101	10010001

For keys of length 256 bits (that is, L_k = 8) an additional S-box operation is inserted: If i ≡ 4 mod L_k, then before the XOR operation k_i−1 is replaced by S (k_i−1).

Thus a key schedule is built up of L_b · (L_r + 1) 4-byte words, including the secret user key. At each round i = 0,..., L_r −1 the next L_b 4-byte words through kL_b·(i+1) are taken as round keys from the key schedule. The round keys are conceptualized, in analogy to the structuring of the message blocks, as a two-dimensional structure of the form depicted in Table 19.8.

Table 19.8: Representation of the round keys

k0,0	k0,1	k0,2	k0,3	k0,4	...
k1,0	k1,1	k1,2	k1,3	k1,4	...
k2,0	k2,1	k2,2	k2,3	k2,4	...
k3,0	k3,1	k3,2	k3,3	k3,4	...

For key lengths of 128 bits key generation can be understood from an examination of Figure 19.2

There are no weak keys known, those whose use would weaken the procedure.