AES key schedule (original) (raw)

From Wikipedia, the free encyclopedia

Method for expanding key to round keys in AES

The Advanced Encryption Standard uses a key schedule to expand a short key into a number of separate round keys. 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.[note 1] The key schedule produces the needed round keys from the initial key.

Values of rci in hexadecimal

i 1 2 3 4 5 6 7 8 9 10
rci 01 02 04 08 10 20 40 80 1B 36

The round constant rconi for round i of the key expansion is the 32-bit word:[note 2]

r c o n i = [ r c i 00 8 00 8 00 8 ] {\displaystyle rcon_{i}={\begin{bmatrix}rc_{i}&00_{8}&00_{8}&00_{8}\end{bmatrix}}} {\displaystyle rcon_{i}={\begin{bmatrix}rc_{i}&00_{8}&00_{8}&00_{8}\end{bmatrix}}}

where rci is an eight-bit value defined as :

r c i = { 1 if i = 1 2 ⋅ r c i − 1 if i > 1 and r c i − 1 < 80 16 ( ( ( 2 ⋅ r c i − 1 ) ⊕ 11B 16 ) mod 100 16 ) if i > 1 and r c i − 1 ≥ 80 16 {\displaystyle rc_{i}={\begin{cases}1&{\text{if }}i=1\\2\cdot rc_{i-1}&{\text{if }}i>1{\text{ and }}rc_{i-1}<80_{16}\\(((2\cdot rc_{i-1})\oplus {\text{11B}}_{16}){\text{ mod }}{\text{100}}_{16})&{\text{if }}i>1{\text{ and }}rc_{i-1}\geq 80_{16}\end{cases}}} {\displaystyle rc_{i}={\begin{cases}1&{\text{if }}i=1\\2\cdot rc_{i-1}&{\text{if }}i>1{\text{ and }}rc_{i-1}<80_{16}\\(((2\cdot rc_{i-1})\oplus {\text{11B}}_{16}){\text{ mod }}{\text{100}}_{16})&{\text{if }}i>1{\text{ and }}rc_{i-1}\geq 80_{16}\end{cases}}}

where ⊕ {\displaystyle \oplus } {\displaystyle \oplus } is the bitwise XOR operator and constants such as 0016 and 11B16 are given in hexadecimal. Equivalently:

r c i = x i − 1 {\displaystyle rc_{i}=x^{i-1}} {\displaystyle rc_{i}=x^{i-1}}

where the bits of rci are treated as the coefficients of an element of the finite field G F ( 2 8 ) [ x ] / ( x 8 + x 4 + x 3 + x + 1 ) {\displaystyle {\rm {{GF}(2^{8})[x]/(x^{8}+x^{4}+x^{3}+x+1)}}} {\displaystyle {\rm {{GF}(2^{8})[x]/(x^{8}+x^{4}+x^{3}+x+1)}}}, so that e.g. r c 10 = 36 16 = 00110110 2 {\displaystyle rc_{10}=36_{16}=00110110_{2}} {\displaystyle rc_{10}=36_{16}=00110110_{2}} represents the polynomial x 5 + x 4 + x 2 + x {\displaystyle x^{5}+x^{4}+x^{2}+x} {\displaystyle x^{5}+x^{4}+x^{2}+x}.

AES uses up to _rcon_10 for AES-128 (as 11 round keys are needed), up to _rcon_8 for AES-192, and up to _rcon_7 for AES-256.[note 3]

AES key schedule for a 128-bit key.

Define:

Also define RotWord as a one-byte left circular shift:[note 6]

RotWord ⁡ ( [ b 0 b 1 b 2 b 3 ] ) = [ b 1 b 2 b 3 b 0 ] {\displaystyle \operatorname {RotWord} ({\begin{bmatrix}b_{0}&b_{1}&b_{2}&b_{3}\end{bmatrix}})={\begin{bmatrix}b_{1}&b_{2}&b_{3}&b_{0}\end{bmatrix}}} {\displaystyle \operatorname {RotWord} ({\begin{bmatrix}b_{0}&b_{1}&b_{2}&b_{3}\end{bmatrix}})={\begin{bmatrix}b_{1}&b_{2}&b_{3}&b_{0}\end{bmatrix}}}

and SubWord as an application of the AES S-box to each of the four bytes of the word:

SubWord ⁡ ( [ b 0 b 1 b 2 b 3 ] ) = [ S ⁡ ( b 0 ) S ⁡ ( b 1 ) S ⁡ ( b 2 ) S ⁡ ( b 3 ) ] {\displaystyle \operatorname {SubWord} ({\begin{bmatrix}b_{0}&b_{1}&b_{2}&b_{3}\end{bmatrix}})={\begin{bmatrix}\operatorname {S} (b_{0})&\operatorname {S} (b_{1})&\operatorname {S} (b_{2})&\operatorname {S} (b_{3})\end{bmatrix}}} {\displaystyle \operatorname {SubWord} ({\begin{bmatrix}b_{0}&b_{1}&b_{2}&b_{3}\end{bmatrix}})={\begin{bmatrix}\operatorname {S} (b_{0})&\operatorname {S} (b_{1})&\operatorname {S} (b_{2})&\operatorname {S} (b_{3})\end{bmatrix}}}

Then for i = 0 … 4 R − 1 {\displaystyle i=0\ldots 4R-1} {\displaystyle i=0\ldots 4R-1}:

W i = { K i if i < N W i − N ⊕ SubWord ⁡ ( RotWord ⁡ ( W i − 1 ) ) ⊕ r c o n i / N if i ≥ N and i ≡ 0 ( mod N ) W i − N ⊕ SubWord ⁡ ( W i − 1 ) if i ≥ N , N > 6 , and i ≡ 4 ( mod N ) W i − N ⊕ W i − 1 otherwise. {\displaystyle W_{i}={\begin{cases}K_{i}&{\text{if }}i<N\\W_{i-N}\oplus \operatorname {SubWord} (\operatorname {RotWord} (W_{i-1}))\oplus rcon_{i/N}&{\text{if }}i\geq N{\text{ and }}i\equiv 0{\pmod {N}}\\W_{i-N}\oplus \operatorname {SubWord} (W_{i-1})&{\text{if }}i\geq N{\text{, }}N>6{\text{, and }}i\equiv 4{\pmod {N}}\\W_{i-N}\oplus W_{i-1}&{\text{otherwise.}}\\\end{cases}}} {\displaystyle W_{i}={\begin{cases}K_{i}&{\text{if }}i<N\\W_{i-N}\oplus \operatorname {SubWord} (\operatorname {RotWord} (W_{i-1}))\oplus rcon_{i/N}&{\text{if }}i\geq N{\text{ and }}i\equiv 0{\pmod {N}}\\W_{i-N}\oplus \operatorname {SubWord} (W_{i-1})&{\text{if }}i\geq N{\text{, }}N>6{\text{, and }}i\equiv 4{\pmod {N}}\\W_{i-N}\oplus W_{i-1}&{\text{otherwise.}}\\\end{cases}}}

  1. ^ Non-AES Rijndael variants require up to 256 bits of expanded key per round
  2. ^ In FIPS-197 the r c i {\displaystyle rc_{i}} {\displaystyle rc_{i}} value is the least significant byte at index 0
  3. ^ 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). The remaining constants for i ≥ 11 are: 6C, D8, AB, 4D, 9A, 2F, 5E, BC, 63, C6, 97, 35, 6A, D4, B3, 7D, FA, EF and C5
  4. ^ Other Rijndael variants require max(N, B) + 7 round keys, where B is the block size in words
  5. ^ Other Rijndael variants require BR words of expanded key, where B is the block size in words
  6. ^ Rotation is opposite of byte order direction. FIPS-197 byte addresses in arrays are increasing from left to right[ref 1] in little endian but rotation is from right to left. In AES-NI[ref 2] and in the Linux kernel's lib/crypto/aes.c[ref 3], the byte ordering is increasing from right to left in little endian but rotation is from left to right.
  1. ^ "Federal Information Processing Standards Publication 197 November 26, 2001 Announcing the ADVANCED ENCRYPTION STANDARD (AES)" (PDF). p. 8. Retrieved 2020-06-16.
  2. ^ "Intel® Advanced Encryption Standard (AES) New Instructions Set" (PDF). p. 13.
  3. ^ "aes.c". GitHub. Retrieved 2020-06-15.