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)} \mod 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).

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), up to Rcon[8] for AES-192, up to Rcon[7] for AES-256.

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

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

See also