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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://www.ctfrecipes.com/cryptography/symmetric-cryptography/aes/block-encryption-procedure/key-expansion-key-schedule.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.