Advanced Encryption Standard (AES)

Explanation The Advanced Encryption Standard (AES) specifies a FIPS-approved cryptographic algorithm that can be used to protect electronic data. The AES algorithm is a symmetric block cipher that can encrypt (encipher) and decrypt (decipher) digital information. The AES algorithm is capable of using cryptographic keys of 128, 192, and 256 bits to encrypt and decrypt data in blocks of 128 bits.

3.4 The State#

Internally, the algorithms for the AES block ciphers are performed on a two-dimensional (four-by-four) array of bytes called the state. In the state array, denoted by $s$, each individual byte has two indices: a row index $r$ in the range $0\le r<4$ and a column index $c$ in the range $0\le c<4$. An individual byte of the state is denoted by either $s_{r,c}$ or $s[r,c]$.

In the specifications for the AES block cipher algorithms in Section 5, the first step is to copy the input array of bytes ${in}_0,{in}_1,\dots ,{in}_{15}$ to the state array $s$ as follows:

A sequence of transformations is then applied to the state array, after which its final value is copied to the output array of bytes ${out}_0,{out}_1,\dots ,{out}_{15}$ as follows:

The correspondence between the indices of the input and output with the indices of the state array is illustrated in Fig. 1.

Figure 1. State array input and output

3.5 Arrays of Words#

A word is a sequence of four bytes; a block consists of four words. The four columns of state array $s$ are interpreted as an array $v$ of four words as follows, in the notation of Fig. 1:

Thus, the column index $c$ of $s$ becomes the index for $v$, and the row index $r$ of $s$ becomes the index for the four bytes in each word.

Given a one-dimensional array $u$ of words, $u[i]$ denotes the word that is indexed by $i$, and the sequence of four words $u[i],u[i+1],u[i+2],u[i+3]$ is denoted by $u[i..i+3]$.

4.2 Multiplication in GF(2⁸)#

The symbol $\bullet$ denotes multiplication in $\mathrm{GF}\left(2^8\right)$. Conceptually, this multiplication is defined on two bytes in two steps: 1) the two polynomials that represent the bytes are multiplied as polynomials, and 2) the resulting polynomial is reduced modulo the following fixed polynomial:

Within both steps, the individual coefficients of the polynomials are reduced modulo 2.

Thus, if $b(x)$ and $c(x)$ represent bytes $b$ and $c$, then $b\bullet c$ is represented by the following modular reduction of their product as polynomials:

The modular reduction by $m(x)$ may be applied to intermediate steps in the calculation of $b(x)c(x)$; consequently, it is useful to consider the special case that $c(x)=x$ (i.e., $c=\{\text{02}\}$). In particular, the product $b\bullet \{\text{02}\}$ can be expressed as a function of $b$, denoted by xTimes$(b)$, as follows:

Multiplication by higher powers of $x$ (such as $\{\text{04}\}$, $\{\text{08}\}$, and $\{\text{10}\}$) can be implemented by the repeated application of xTimes(). For example, let $b=\{\text{57}\}$:

These products facilitate the computation of any multiple of $\{\text{57}\}$. For example, because $\{\text{13}\}=\{\text{10}\}\oplus \{\text{02}\}\oplus \{\text{01}\}$, it follows that

5. Algorithm Specifications#

The general function for executing AES-128, AES-192, or AES-256 is denoted by Cipher(); its inverse is denoted by InvCipher().¹

The core of the algorithms for Cipher() and InvCipher() is a sequence of fixed transformations of the state called a round. Each round requires an additional input called the round key; the round key is a block that is usually represented as a sequence of four words (i.e., 16 bytes).

An expansion routine, denoted by KeyExpansion(), takes the block cipher key as input and generates the round keys as output. In particular, the input to KeyExpansion() is represented as an array of words, denoted by key, and the output is an expanded array of words, denoted by w, called the key schedule.

The block ciphers AES-128, AES-192, and AES-256 differ in three respects: 1) the length of the key; 2) the number of rounds, which determines the size of the required key schedule; and 3) the specification of the recursion within KeyExpansion(). For each algorithm, the number of rounds is denoted by Nr, and the number of words of the key is denoted by Nk. (The number of words in the state is denoted by Nb for Rijndael in general; in this Standard, $Nb=4$.) The specific values of Nk, Nb, and Nr are given in Table 3. No other configurations of Rijndael conform to this Standard.

For implementation issues relating to the key length, block size, and number of rounds, see Section 6.3.

Table 3. Key-Block-Round Combinations

The three inputs to Cipher() are: 1) the data input in, which is a block represented as a linear array of 16 bytes; 2) the number of rounds Nr for the instance; and 3) the round keys. Thus,

The inverse permutations are defined by replacing Cipher() with InvCipher() in Eq. 5.1.

The specifications of Cipher(), KeyExpansion(), and InvCipher() are given in Sections 5.1, 5.2, and 5.3, respectively.

5.1 Cipher()#

The rounds in the specification of Cipher() are composed of the following four byte-oriented transformations on the state:

• SubBytes() applies a substitution table (S-box) to each byte.
• ShiftRows() shifts rows of the state array by different offsets.
• MixColumns() mixes the data within each column of the state array.
• AddRoundKey() combines a round key with the state.

The four transformations are specified in Sections 5.1.1–5.1.4. In those specifications, the transformed bit, byte, or block is denoted by appending the symbol ${}^{\prime }$ as a superscript on the original variable $(\text{i.e., by }{b}_i^{\prime },b^{\prime },s_{i,j}^{\prime },\text{or }{s}^{\prime })$.

The round keys for AddRoundKey() are generated by KeyExpansion(), which is specified in Section 5.2. In particular, the key schedule is represented as an array $w$ of $4\ast (Nr+1)$ words.

Cipher() is specified in the pseudocode in Alg. 1.

Algorithm 1 Pseudocode for Cipher()

1:$\text{procedure}\text{CIPHER}(in,Nr,w)$

2:$state\leftarrow in$$▹$ See Sec. 3.4

3:$state\leftarrow \text{ADDROUNDKEY}(state,w[\mathrm{0..3}])$$▹$ See Sec. 5.1.4

4:$\text{for}round\text{from}1\text{to}Nr-1\text{do}$

5:$state\leftarrow \text{SUBBYTES}(state)$$▹$ See Sec. 5.1.1

6:$state\leftarrow \text{SHIFTROWS}(state)$$▹$ See Sec. 5.1.2

7:$state\leftarrow \text{MIXCOLUMNS}(state)$$▹$ See Sec. 5.1.3

8:$state\leftarrow \text{ADDROUNDKEY}(state,w[4\ast round..4\ast round+3])$

9:$\text{end for}$

10:$state\leftarrow \text{SUBBYTES}(state)$

11:$state\leftarrow \text{SHIFTROWS}(state)$

12:$state\leftarrow \text{ADDROUNDKEY}(state,w[4\ast Nr..4\ast Nr+3])$

13:$\text{return}state$$▹$ See Sec. 3.4

14:$\text{end procedure}$

The first step (Line 2) is to copy the input into the state array using the conventions from Sec. 3.4. After an initial round key addition (Line 3), the state array is transformed by Nr applications of the round function (Lines 4–12); the final round (Lines 10–12) differs in that the MixColumns() transformation is omitted. The final state is then returned as the output (Line 13), as described in Section 3.4.

5.1.1 SubBytes()#

SubBytes() is an invertible, non-linear transformation of the state in which a substitution table, called an S-box, is applied independently to each byte in the state. The AES S-box is denoted by SBox().

Let $b$ denote an input byte to SBox(), and let $c$ denote the constant byte $\{\text{01100011}\}$. The output byte $b^{\prime }=\text{SBOX}(b)$ is constructed by composing the following two transformations:

1. Define an intermediate value $\tilde{b}$, as follows, where $b^{-1}$ is the multiplicative inverse of $b$, as described in Section 4.4:

2. Apply the following affine transformation of the bits of $\tilde{b}$ to produce the bits of $b^{\prime }$:

The matrix form of Eq. (5.3) is given by Eq. (5.4) below:

Figure 2 illustrates how SubBytes() transforms the state.

Figure 2. Illustration of SubBytes()

The AES S-box is presented in hexadecimal form in Table 4. For example, if $s_{r,c}=\{\text{53}\}$, then the substitution value would be determined by the intersection of the row with index ‘5’ and the column with index ‘3’ in Table 4, so that $s_{r,c}^{\prime }=\{\text{ed}\}$.

Table 4. SBox(): substitution values for the byte xy (in hexadecimal format)

5.1.2 ShiftRows()#

ShiftRows() is a transformation of the state in which the bytes in the last three rows of the state are cyclically shifted. The number of positions by which the bytes are shifted depends on the row index r, as follows:

ShiftRows() is illustrated in Figure 3. In that representation of the state, the effect is to move each byte by r positions to the left in the row, cycling the left-most r bytes around to the right end of the row. The first row, where $r=0$, is unchanged.

Figure 3. Illustration of ShiftRows()

5.1.3 MixColumns()#

MixColumns() is a transformation of the state that multiplies each of the four columns of the state by a single fixed matrix, as described in Section 4.3, with its entries taken from the following word:

Thus,

so that the individual output bytes are defined as follows:

Figure 4 illustrates MixColumns().

Figure 4. Illustration of MixColumns()

5.1.4 AddRoundKey()#

AddRoundKey() is a transformation of the state in which a round key is combined with the state by applying the bitwise XOR operation. In particular, each round key consists of four words from the key schedule (described in Section 5.2), each of which is combined with a column of the state as follows:

where round is a value in the range $0\le round\le Nr$, and $w[i]$ is the array of key schedule words described in Section 5.2. In the specification of Cipher(), AddRoundKey() is invoked $Nr+1$ times — once prior to the first application of the round function (see Alg. 1) and once within each of the Nr rounds, when $1\le round\le Nr$.

The action of this transformation is illustrated in Fig. 5, where $l=4\ast round$. The byte address within words of the key schedule was described in Sec. 3.5.

Figure 5. Illustration of AddRoundKey()

5.2 KeyExpansion()#

KeyExpansion() is a routine that is applied to the key to generate $4\ast (Nr+1)$ words. Thus, four words are generated for each of the $Nr+1$ applications of AddRoundKey() within the specification of Cipher(), as described in Section 5.1.4. The output of the routine consists of a linear array of words, denoted by $w[i]$, where $i$ is in the range $0\le i<4\ast (Nr+1)$.

KeyExpansion() invokes 10 fixed words denoted by $Rcon[j]$ for $1\le j\le 10$. These 10 words are called the round constants. For AES-128, a distinct round constant is called in the generation of each of the 10 round keys. For AES-192 and AES-256, the key expansion routine calls the first eight and seven of these same constants, respectively. The values of $Rcon[j]$ are given in hexadecimal notation in Table 5:

Table 5. Round constants

The value of the left-most byte of $Rcon[j]$ in polynomial form is $x^{j-1}$. Note that for $j>0$, these bytes may be generated by successively applying xTimes() to the byte represented by $x^{j-1}$ (see Eq. 4.5).

Two transformations on words are called within KeyExpansion(): RotWord() and SubWord(). Given an input word represented as a sequence $[a_0,a_1,a_2,a_3]$ of four bytes,

and

The expansion of the key proceeds according to the pseudocode in Alg. 2. The first Nk words of the expanded key are the key itself. Every subsequent word $w[i]$ is generated recursively from the preceding word, $w[i-1]$, and the word Nk positions earlier, $w[i-Nk]$, as follows:

• If $i$ is a multiple of Nk, then $w[i]=w[i-Nk]\oplus \text{SUBWORD}(\text{ROTWORD}(w[i-1]))\oplus Rcon[i/Nk]$.
• For AES-256, if $i+4$ is a multiple of 8, then $w[i]=w[i-Nk]\oplus \text{SUBWORD}(w[i-1])$.
• For all other cases, $w[i]=w[i-Nk]\oplus w[i-1]$.

Algorithm 2 Pseudocode for KeyExpansion()

1:$\text{procedure}\text{KEYEXPANSION}(key)$

2:$i\leftarrow 0$

3:$\text{while}i\le Nk-1\text{do}$

4:$w[i]\leftarrow key[4\ast i..4\ast i+3]$

5:$i\leftarrow i+1$

6:$\text{end while}$$▹$ When the loop concludes, $i=Nk$.

7:$\text{while}i\le 4\ast Nr+3\text{do}$

8:$temp\leftarrow w[i-1]$

9:$\text{if}i\mathrm{mod}Nk=0\text{then}$

10:$temp\leftarrow \text{SUBWORD}(\text{ROTWORD}(temp))\oplus Rcon[i/Nk]$

11:$\text{else if}Nk>6\text{and}i\mathrm{mod}Nk=4\text{then}$

12:$temp\leftarrow \text{SUBWORD}(temp)$

13:$\text{end if}$

14:$w[i]\leftarrow w[i-Nk]\oplus temp$

15:$i\leftarrow i+1$

16:$\text{end while}$

17:$\text{return}w$

18:$\text{end procedure}$