Rijndael key schedule

From Wikipedia, the free encyclopedia

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.

Contents

[edit] Common operations

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

[edit] Rotate

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

1d2c3a4f

And rotates it eight bits to the left:

2c3a4f1d

[edit] 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 = 0x7 + 0x6 + 0x5 + 0x4 + 0x3 + 0x2 + 1x + 0 = x, and we compute

rcon(i) = x(254 + i)

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

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

in \mathbb{F}_{2}.

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[255] = {

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}

[edit] S-box

The key schedule uses Rijndael's S-box.

[edit] 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 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

[edit] The key schedule

[edit] 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

[edit] 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 32 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
  4. Step three is repeated until at least b bytes of expanded key are generated

[edit] Test vectors

Here is the expanded key for a 128-bit key consisting entirely of null characters:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
62 63 63 63 62 63 63 63 62 63 63 63 62 63 63 63 
9b 98 98 c9 f9 fb fb aa 9b 98 98 c9 f9 fb fb aa 
90 97 34 50 69 6c cf fa f2 f4 57 33 0b 0f ac 99 
ee 06 da 7b 87 6a 15 81 75 9e 42 b2 7e 91 ee 2b 
7f 2e 2b 88 f8 44 3e 09 8d da 7c bb f3 4b 92 90 
ec 61 4b 85 14 25 75 8c 99 ff 09 37 6a b4 9b a7 
21 75 17 87 35 50 62 0b ac af 6b 3c c6 1b f0 9b 
0e f9 03 33 3b a9 61 38 97 06 0a 04 51 1d fa 9f 
b1 d4 d8 e2 8a 7d b9 da 1d 7b b3 de 4c 66 49 41 
b4 ef 5b cb 3e 92 e2 11 23 e9 51 cf 6f 8f 18 8e

Here is the expanded key for a 192-bit key consisting entirely of null characters:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 62 63 63 63 62 63 63 63 
62 63 63 63 62 63 63 63 62 63 63 63 62 63 63 63 
9b 98 98 c9 f9 fb fb aa 9b 98 98 c9 f9 fb fb aa 
9b 98 98 c9 f9 fb fb aa 90 97 34 50 69 6c cf fa 
f2 f4 57 33 0b 0f ac 99 90 97 34 50 69 6c cf fa 
c8 1d 19 a9 a1 71 d6 53 53 85 81 60 58 8a 2d f9 
c8 1d 19 a9 a1 71 d6 53 7b eb f4 9b da 9a 22 c8 
89 1f a3 a8 d1 95 8e 51 19 88 97 f8 b8 f9 41 ab 
c2 68 96 f7 18 f2 b4 3f 91 ed 17 97 40 78 99 c6 
59 f0 0e 3e e1 09 4f 95 83 ec bc 0f 9b 1e 08 30 
0a f3 1f a7 4a 8b 86 61 13 7b 88 5f f2 72 c7 ca 
43 2a c8 86 d8 34 c0 b6 d2 c7 df 11 98 4c 59 70

Here is the expanded key for a 256-bit key consisting entirely of null characters:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
62 63 63 63 62 63 63 63 62 63 63 63 62 63 63 63 
aa fb fb fb aa fb fb fb aa fb fb fb aa fb fb fb 
6f 6c 6c cf 0d 0f 0f ac 6f 6c 6c cf 0d 0f 0f ac 
7d 8d 8d 6a d7 76 76 91 7d 8d 8d 6a d7 76 76 91 
53 54 ed c1 5e 5b e2 6d 31 37 8e a2 3c 38 81 0e 
96 8a 81 c1 41 fc f7 50 3c 71 7a 3a eb 07 0c ab 
9e aa 8f 28 c0 f1 6d 45 f1 c6 e3 e7 cd fe 62 e9 
2b 31 2b df 6a cd dc 8f 56 bc a6 b5 bd bb aa 1e 
64 06 fd 52 a4 f7 90 17 55 31 73 f0 98 cf 11 19 
6d bb a9 0b 07 76 75 84 51 ca d3 31 ec 71 79 2f 
e7 b0 e8 9c 43 47 78 8b 16 76 0b 7b 8e b9 1a 62 
74 ed 0b a1 73 9b 7e 25 22 51 ad 14 ce 20 d4 3b 
10 f8 0a 17 53 bf 72 9c 45 c9 79 e7 cb 70 63 85

[edit] References

[edit] See also

Languages