NOTE: This site is obsolete. See book draft (in PDF):

The Laws of Cryptography with Java Code.

---

Overview of Key Expansion.

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: void KeyExpansion(byte[] key, word[] w, int Nw) { int Nr = Nk + 6; w = new byte[4*Nb*(Nr+1)]; int temp; int i = 0; while ( i < Nk) { w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3]); i++; } i = Nk; while(i < Nb*(Nr+1)) { temp = w[i-1]; if (i % Nk == 0) temp = SubWord(RotWord(temp)) ^ Rcon[i/Nk]; else if (Nk > 6 && (i%Nk) == 4) temp = SubWord(temp); w[i] = w[i-Nk] ^ temp; i++; } }

Discussion of items in the above pseudo-code in order:

• The constant Nb = 4: This was mentioned earlier. Nb is the number of words in an AES block, and right now it is always 4.
• The key, key: the input key consists of Nk words, or 4*Nk bytes.
• The expanded key, w: This consists of Nb*(Nk+1) words, or 4*Nb*(Nk+1) bytes. The range of sizes are in the table below:

  Expanded Key Sizes in Words
  Key Length  (Nk words)	Number of Rounds  (Nr)	Exp. Key Size  (Nb(Nr+1) words)
  4	10	44
  6	12	52
  8	14	60

• RotWord(): This does the following simple cyclic permutation of a word: change [a₀,a₁,a₂,a₃] to [a₁,a₂,a₃,a₀].

• Rcon[i]: This is defined as the word: [x^i-1,0,0,0]. The following table contains values of powers of x:

  Powers of x = 0x02
  i		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
  xi		01	02	04	08	10	20	40	80	1b	36	6c	d8	ab	4d	9a

  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 x⁰.

• SubWord(): This just applies the S-box value used in SubBytes to each of the 4 bytes in the argument.

---

Use of Key Expansion in the AES Algorithm.

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.