Cryptography Reference
In-Depth Information
4.2.2.6 KeyExpansion
As mentioned above,
KeyExpansion
takes as input anAES key and generates a so-
called “key schedule”, consisting of
Nr+1
round keys
K[i]
, each of which is a 4
4
byte array which can also be regarded as a one-dimensional array consisting of 4 four-
byte words (the columns of the two-dimensional array). Thus the key expansion can
be seen as a process that takes as input
Nk
four-byte words (the columns of the array in
which the AES key is initialized) and generates
4(Nr+1)-Nk
more words making
a total of
4(Nr+1)
words which are denoted by
w[0]
,
w[1]
, ...,
w[4Nr+3]
.The
first four of these words make up the array
K[0]
, the next four
K[1]
, and so on until
K[Nr]
, thus giving the round subkeys used by the
AddRoundKey
operation. The
key expansion algorithm uses two other functions. One of them is called
RotWord
and performs a cyclic left shift of the bytes in a word (or, rather, an “up shift”
when the word is written as a column). The other is
SubWord
and it simply applies
the S-box to the bytes in a word.
KeyExpansion
also uses the “round constant
word array”
Rcon
which consists of 14 four-byte words obtained by successive
multiplication by the byte
02
in
×
F
2
8
, starting with the word
[01,00,00,00]
(so
2
i
−
1
that
Rcon[i]
=
if the bytes are represented as integers in the 0..255
range and exponentiation is taken in
[
,
0
,
0
,
0
]
F
2
8
).
The key expansion algorithm can be given in pseudocode as follows. Note that,
after building the first
Nk
words of the expanded keywith theAES key, each following
word
w[i]
is obtained by Xor-ing the previous word
w[i-1]
with the word
Nk
positions before, except when the position is a multiple of
Nk
or when
Nk=8
,in
which cases some additional transformations are applied to
w[i-1]
prior to the
Xor operation.
Algorithm 4.2. KeyExpansion
.
Input
: An AES key k given as a one-dimensional byte array
[k[0]
,
k[1]
,
...
,
k[4Nk]]
.
Output
: An expanded key given as an array of
Nr+1
round keys.
for i from 0 to Nk-1 do
w[i] := [k[4i], k[4i+1], k[4i+2], k[4i+3]]
end do
;
for i from Nk to 4Nr+3 do
temp := w[i-1]
;
if i
mod
Nk
=
0
then
temp := SubWord(RotWord(temp))
⊕
Rcon[i/Nk]
else if Nk
>
6
and i
mod
Nk
=
4
temp := SubWord(temp)
end if
;
w[i]
:=
w[i-Nk]
⊕
temp
end do
;
for i from 0 to Nr do
K[i] := [w[4i], w[4i+1], w[4i+2], w[4i+3]]
end do
;
return [K[0], ..., K[Nr]]
.