Rijndael key schedule

AES (Rijndael) uses a key schedule to expand a short key into a number of separate round keys. This is known as the Rijndael key schedule. The three AES variants have a different number of rounds. Each variant requires a separate 128-bit round key for each round plus one more. The key schedule produces the needed round keys from the initial key.

Common operations

Rijndael's key schedule utilizes a number of operations, which will be described before describing the key schedule.

Rotate

The rotate operation takes a 32-bit word like this (in hexadecimal):

1D 2C 3A 4F

and rotates it eight bits to the left such that the high eight bits "wrap around" and become the low eight bits of the result.

2C 3A 4F 1D

Rcon

Rcon is what the Rijndael documentation calls the exponentiation of 2 to a user-specified value. Note that this operation is not performed with regular integers, but in Rijndael's finite field. In polynomial form, 2 is $2 = 00000010 = 0 x^7 + 0 x^6 + 0 x^5 + 0 x^4 + 0 x^3 + 0 x^2 + 1 x + 0 = x$ , and we compute

\textrm{rcon}(i) = x^{i-1}

in $\mathbb{F}_{2^8}$ or equivalently,

\textrm{rcon}(i) = x^{i-1} \bmod x^8 + x^4 + x^3 + x + 1

in $\mathbb{F}_{2}[x]$ .

Where i is taken as round number.

For example, the $rcon(1) = 1$ , the $rcon(2) = 2$ , the $rcon(3) = 4$ , and the $rcon(9)$ is the hexadecimal number 0x1b (27 in decimal).

unsigned char rcon[256] = {
    0x8d, 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, 
    0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 
    0x74, 0xe8, 0xcb, 0x8d, 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, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc, 
    0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d, 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, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94, 
    0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d, 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, 0x72, 0xe4, 0xd3, 0xbd, 0x61, 0xc2, 0x9f, 
    0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d, 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, 0x72, 0xe4, 0xd3, 0xbd, 
    0x61, 0xc2, 0x9f, 0x25, 0x4a, 0x94, 0x33, 0x66, 0xcc, 0x83, 0x1d, 0x3a, 0x74, 0xe8, 0xcb, 0x8d
}

Only the first some of these constants are actually used – up to rcon[10] for AES-128 (as 11 round keys are needed).

rcon[0] is not used in AES algorithm.

The Rijndael variants with larger block sizes use more of these constants, up to rcon[29] for Rijndael with 128-bit keys and 256 bit blocks (needs 15 round keys of each 256 bit, which means 30 full rounds of key expansion, which means 29 calls to the key schedule core using the round constants).

S-box

The key schedule uses Rijndael's S-box.

Key schedule core

This operation is used as an inner loop in the key schedule, and is done in the following manner:

The input is a 32-bit word and an iteration number i. The output is a 32-bit word.
Copy the input over to the output.
Use the above described rotate operation to rotate the output eight bits to the left
Apply Rijndael's S-box on all four individual bytes in the output word
On just the first (leftmost) byte of the output word, exclusive OR the byte with 2 to the power of (i-1). In other words, perform the rcon operation with i as the input, and exclusive or the rcon output with the first byte of the output word

The key schedule

Constants

Since the key schedule for 128-bit, 192-bit, and 256-bit encryption are very similar, with only some constants changed, the following keysize constants are defined here:

n has a value of 16 for 128-bit keys, 24 for 192-bit keys, and 32 for 256-bit keys
b has a value of 176 for 128-bit keys, 208 for 192-bit keys, and 240 for 256-bit keys (with 128-bit blocks as in AES, it is correspondingly larger for variants of Rijndael with larger block sizes).

Key schedule description

Rijndael's key schedule is done as follows:

The first n bytes of the expanded key are simply the encryption key.
The rcon iteration value i is set to 1
Until we have b bytes of expanded key, we do the following to generate n more bytes of expanded key:
- We do the following to create 4 bytes of expanded key:
  1. We create a 4-byte temporary variable, t
  2. We assign the value of the previous four bytes in the expanded key to t
  3. We perform the key schedule core (see above) on t, with i as the rcon iteration value
  4. We increment i by 1
  5. We exclusive-OR t with the four-byte block n bytes before the new expanded key. This becomes the next 4 bytes in the expanded key
- We then do the following three times to create the next twelve bytes of expanded key:
  1. We assign the value of the previous 4 bytes in the expanded key to t
  2. We exclusive-OR t with the four-byte block n bytes before the new expanded key. This becomes the next 4 bytes in the expanded key
- If we are processing a 256-bit key, we do the following to generate the next 4 bytes of expanded key:
  1. We assign the value of the previous 4 bytes in the expanded key to t
  2. We run each of the 4 bytes in t through Rijndael's S-box
  3. We exclusive-OR t with the 4-byte block n bytes before the new expanded key. This becomes the next 4 bytes in the expanded key.
- If we are processing a 128-bit key, we do not perform the following steps. If we are processing a 192-bit key, we run the following steps twice. If we are processing a 256-bit key, we run the following steps three times:
  1. We assign the value of the previous 4 bytes in the expanded key to t
  2. We exclusive-OR t with the four-byte block n bytes before the new expanded key. This becomes the next 4 bytes in the expanded key

References

FIPS PUB 197: the official AES standard (PDF file)
Description of Rijndael's key schedule
schematic view of the key schedule for 128 and 256 bit keys for 160-bit keys on Cryptography Stack Exchange
Flash Application with Rijndael's key schedule (functional; text in Portuguese)
Flash Video Describing the AES key schedule