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.

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 , and we compute

in or equivalently,

in .

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).

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}

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 thus:

• The input is a 32-bit word and at 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

Key schedule description

Rijndael's key schedule is done as follows:

1. The first n bytes of the expanded key are simply the encryption key.
2. The rcon iteration value i is set to 1
3. 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 generating 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 generating a 128-bit key, we do not perform the following steps. If we are generating a 192-bit key, we run the following steps twice. If we are generating 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
• Flash Application with Rijndael's key schedule (functional; text in Portuguese)
• Flash Video Describing the AES key schedule

See also

• Advanced Encryption Standard