> For the complete documentation index, see [llms.txt](https://www.ctfrecipes.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.ctfrecipes.com/cryptography/symmetric-cryptography/aes/block-encryption-procedure/key-expansion-key-schedule.md).

# Key Expansion / Key Schedule

Each round use its own round key into the "[**Add Key**](/cryptography/symmetric-cryptography/aes/block-encryption-procedure/add-key.md)" 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

{% hint style="info" %}
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
  {% endhint %}

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

{% hint style="info" %}
Here is 4 words for AES-128, 6 for AES-192 and 8 for AES-256
{% endhint %}

The next words are calculated following these graph :

<figure><img src="/files/BPhGHPWy790RFggXwSlQ" alt=""><figcaption><p>Figure 1. AES 128 Expansion key</p></figcaption></figure>

<figure><img src="https://github.com/Hakumarachi/theCTFRecipe/blob/master/.gitbook/assets/image%20(5).png" alt=""><figcaption><p>Figure 2. AES 192 Expansion key</p></figcaption></figure>

<figure><img src="/files/XNzXXHXLSNwD6SyK38hN" alt=""><figcaption><p>Figure 3. AES 256 Expansion key</p></figcaption></figure>

## Algorithm steps

{% hint style="warning" %}
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.
{% endhint %}

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]`

{% hint style="info" %}
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.
  {% endhint %}

### 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} \\
$$

{% hint style="info" %}
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.
{% endhint %}

### 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})
$$

{% hint style="info" %}
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
{% endhint %}

### 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 ](/cryptography/symmetric-cryptography/aes/block-encryption-procedure/byte-substitution.md)step of the encryption rounds
* XOR the bytes obtained from the previous step with a round constant.

{% hint style="info" %}
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.
{% endhint %}

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]
$$

{% hint style="warning" %}
The multiplication applied here is the same as in [Mix Column operation](/cryptography/symmetric-cryptography/aes/block-encryption-procedure/mix-column.md) when multiplying by 2.
{% endhint %}

## Python implementation

```python
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)]
```