by Neal R. Wagner
Copyright © 2001 by Neal R. Wagner. All rights reserved.
NOTE: This site is obsolete. See book draft (in PDF):
In a simple cipher, one might exclusive-or the key with the plaintext. Such a step is easily reversed by another exclusive-or of the same key with the ciphertext. In the case of the AES, there are a number of rounds, each needing its own key, so the actual key is ``stretched out'' and transformed to give portions of key for each round. This is the key expansion that is the topic of this section.
The key expansion routine, as part of the overall AES algorithm, takes an input key (denoted key below) of 4*Nk bytes, or Nk 32-bit words. Nk has value either 4, 6, or 8. The output is an expanded key (denoted w below) of 4*Nb*(Nr+1) bytes, where Nb is always 4 and Nr is the number of rounds in the algorithm, with Nr equal 10 in case Nk is 4, Nr equal 12 in case Nk is 6, and Nr equal 14 in case Nk is 8.
The key expansion routine below states most of the actions in terms of words or 4-byte units, since the AES specification itself emphasizes words, but my implementation uses bytes exclusively.
Constants: int Nb = 4; // but it might change someday Inputs: int Nk = 4, 6, or 8; // the number of words in the key array key of 4*Nk bytes or Nk words // input key Output:array w of Nb*(Nr+1) words or 4*Nb*(Nr+1) bytes // expanded key Algorithm:
Discussion of items in the above pseudo-code in order:
|Expanded Key Sizes in Words|
| Key Length
| Number of Rounds
| Exp. Key Size
|Powers of x = 0x02|
Notice that in the algorithm for key expansion, the first reference to Rcon is Rcon[i/Nk], where i has value Nk, so that the smallest index to Rcon is 0, and this uses x0.
The function KeyExpansion() merely supplies a much expanded (and transformed) key for use by the AddRoundKey() function in the main AES algorithm (see Section 1). This does a byte-wise exclusive-or of 4*Nb = 16 bytes at a time of the key with the 4*Nb = 16 bytes of the state. Successive segments of 4*Nb = 16 bytes of the expanded key are exclusive-ored in before the rounds of the algorithm, during each round, and at the end of the rounds. In the end, there are Nr rounds, but Nr+1 exclusive-ors of parts of the expanded key. Since none of the expanded key is used more than once, this means that algorithm needs 4*Nb*(Nr+1) = 16*(Nr+1) bytes of expanded key, and this is just the amount provided by the KeyExpansion() function.