Key Expansion / Key Schedule

Each round use its own round key into the "Add Key" step that is derived from the original encryption key.

So, the Key Schedule will allow creating a different key for each encryption round, each of these sub-keys being 128 bits

The entire key length is then 128 times n+1 ( where n is the amount of round, depending of the original key size )

• $128 \cdot 11 = 1408$ bits for AES-128

• $128 \cdot 13 = 1664$ bits for AES-192

• $128 \cdot 15 = 1920$ bits for AES-256

To make the key expansion, the original key is divided into 32 bits blocks called words

Here is 4 words for AES-128, 6 for AES-192 and 8 for AES-256

The next words are calculated following these graph :

Figure 1. AES 128 Expansion key

Figure 2. AES 192 Expansion key

Figure 3. AES 256 Expansion key

Algorithm steps

The following explanation will be based on AES-128. Some little ajustement ( such as the amount of generated words ) have to be done to make it applicable to the others key size.

As explained before, AES-128 need a total key lenght of 1408 bits ( $11 \cdot 128$ ).

As each word has a size of 32 bits, ( $\frac{1408}{32} = 44$ )44 words are needed.

The first four words group

The first four words are provided by the original key.

• W0 = key[0:31]

• W1 = key[32:63]

• W2 = key[64:95]

• W3 = key[96:127]

Here, we have the four words of the key used for the round 0 ( before the 10 loops )

To serve as the round key for the $i^{th}$ round, $i$ must be a multiple of 4.

These will obviously serve as the round key for the $i/4^{th}$ round. For example :

• w4, w5, w6, w7 is the round key for round 1

• w8, w9, w10, w11 the round key for round 2,

• and so on.

The others words groups

Let’s say that we have the four words of the round key for the i th round:

$$w_i \; w_{i+1} \; w_{i+2} \; w_{i+3}$$

And we need to determine the words

$$w_{i+4} \; w_{i+5} \; w_{i+6} \; w_{i+7}$$

Using the Figure 1, we can write :

$$w_{i+5} = w_{i+4} \oplus w_{i+1} \\ w_{i+6} = w_{i+5} \oplus w_{i+2} \\ w_{i+7} = w_{i+6} \oplus w_{i+3} \\$$

Note that except for the first word in a new 4-word grouping, each word is an XOR of the previous word and the corresponding word in the previous 4-word grouping.

The first word of each groups

$w_{i+4}$ is the beginning of the 4-word group and is obtained by using :

$$w_{i+4} = w_i \oplus g(w_{i+3})$$

The first word of the new 4-word group is obtained by XOR’ing the first word of the last group ( $w_i$ ) with the result of a function g() applied to the last word of the previous 4-word group

The g() function

The function $g()$consists of the following 3 steps :

• Perform a one-byte left circular rotation on the argument 4-byte word.

• Perform a byte substitution for each byte of the word using the same "S-box" in the SubBytes step of the encryption rounds
• XOR the bytes obtained from the previous step with a round constant.

The round constant is a word whose three rightmost bytes are always zero.

Therefore, XOR’ing with the round constant amounts to XOR’ing with just its leftmost byte.

The round constant for the $i^{th}$round is noted $Rcon[i]$.

$$Rcon[i] = (RC[i], 0 , 0 ,0 )$$

The only non-zero byte in the round constants, $RC[i]$, obeys the following recursion:

$$RC[1] = 0x01 \\ RC[i] = 0x02 \cdot RC[i-1]$$

The multiplication applied here is the same as in Mix Column operation when multiplying by 2.

Python implementation

def expand_key(master_key):
    """
    Expands and returns a list of key matrices for the given master_key.
    """

    # Round constants https://en.wikipedia.org/wiki/AES_key_schedule#Round_constants
    r_con = (
        0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
        0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
        0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
        0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
    )

    # Initialize round keys with raw key material.
    key_columns = bytes2matrix(master_key)
    iteration_size = len(master_key) // 4

    # Each iteration has exactly as many columns as the key material.
    i = 1
    while len(key_columns) < (N_ROUNDS + 1) * 4:
        # Copy previous word.
        word = list(key_columns[-1])

        # Perform schedule_core once every "row".
        if len(key_columns) % iteration_size == 0:
            # Circular shift.
            word.append(word.pop(0))
            # Map to S-BOX.
            word = [s_box[b] for b in word]
            # XOR with first byte of R-CON, since the others bytes of R-CON are 0.
            word[0] ^= r_con[i]
            i += 1
        elif len(master_key) == 32 and len(key_columns) % iteration_size == 4:
            # Run word through S-box in the fourth iteration when using a
            # 256-bit key.
            word = [s_box[b] for b in word]

        # XOR with equivalent word from previous iteration.
        word = bytes(i^j for i, j in zip(word, key_columns[-iteration_size]))
        key_columns.append(word)

    # Group key words in 4x4 byte matrices.
    return [key_columns[4*i : 4*(i+1)] for i in range(len(key_columns) // 4)]