Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

8.2 The Layers

We now describe the steps in more detail. The 128 input bits are grouped into 16 bytes of eight bits each, call them

a_{0, 0}, a_{1, 0}, a_{2, 0}, a_{3, 0}, a_{0, 1}, a_{1, 1}, \dots, a_{3, 3} .

$a_{0, 0}, a_{1, 0}, a_{2, 0}, a_{3, 0}, a_{0, 1}, a_{1, 1}, \dots, a_{3, 3} .$

These are arranged into a $4 \times 4$ $4 \times 4$ matrix

(\begin{array}{c} a_{0, 0} & a_{0, 1} & a_{0, 2} & a_{0, 3} \\ a_{1, 0} & a_{1, 1} & a_{1, 2} & a_{1, 3} \\ a_{2, 0} & a_{2, 1} & a_{2, 2} & a_{2, 3} \\ a_{3, 0} & a_{3, 1} & a_{3, 2} & a_{3, 3} \end{array}) .

$(\begin{array}{c} a_{0, 0} & a_{0, 1} & a_{0, 2} & a_{0, 3} \\ a_{1, 0} & a_{1, 1} & a_{1, 2} & a_{1, 3} \\ a_{2, 0} & a_{2, 1} & a_{2, 2} & a_{2, 3} \\ a_{3, 0} & a_{3, 1} & a_{3, 2} & a_{3, 3} \end{array}) .$

In the following, we’ll occasionally need to work with the finite field $G F (2^{8})$ $G F (2^{8})$ . This is covered in Section 3.11. However, for the present purposes, we only need the following facts. The elements of $G F (2^{8})$ $G F (2^{8})$ are bytes, which consist of eight bits. They can be added by XOR. They can also be multiplied in a certain way (i.e., the product of two bytes is again a byte), but this process is more complicated. Each byte $b$ $b$ except the zero byte has a multiplicative inverse; that is, there is a byte $b^{'}$ $b^{'}$ such that $b \cdot b^{'} = 00000001$ $b \cdot b^{'} = 00000001$ . Since we can do arithmetic operations on bytes, we can work with matrices whose entries are bytes.

As a technical point, we note that the model of $G F (2^{8})$ $G F (2^{8})$ depends on a choice of irreducible polynomial of degree 8. The choice for Rijndael is $X^{8} + X^{4} + X^{3} + X + 1$ $X^{8} + X^{4} + X^{3} + X + 1$ . This is also the polynomial used in the examples in Section 3.11. Other choices for this polynomial would presumably give equally good algorithms.

8.2.1 The SubBytes Transformation

In this step, each of the bytes in the matrix is changed to another byte by Table 8.1, called the S-box.

A table shows S-Box for Rijndael that shows various numerical values.

Table 8.1 Full Alternative Text

Write a byte as eight bits: abcdefgh. Look for the entry in the abcd row and efgh column (the rows and columns are numbered from 0 to 15). This entry, when converted to binary, is the output. For example, if the input byte is 10001011, we look in row 8 (the ninth row) and column 11 (the twelfth column). The entry is 61, which is 111101 in binary. This is the output of the S-box.

The output of SubBytes is again a $4 \times 4$ $4 \times 4$ matrix of bytes, let’s call it

(\begin{array}{c} b_{0, 0} & b_{0, 1} & b_{0, 2} & b_{0, 3} \\ b_{1, 0} & b_{1, 1} & b_{1, 2} & b_{1, 3} \\ b_{2, 0} & b_{2, 1} & b_{2, 2} & b_{2, 3} \\ b_{3, 0} & b_{3, 1} & b_{3, 2} & b_{3, 3} \end{array}) .

$(\begin{array}{c} b_{0, 0} & b_{0, 1} & b_{0, 2} & b_{0, 3} \\ b_{1, 0} & b_{1, 1} & b_{1, 2} & b_{1, 3} \\ b_{2, 0} & b_{2, 1} & b_{2, 2} & b_{2, 3} \\ b_{3, 0} & b_{3, 1} & b_{3, 2} & b_{3, 3} \end{array}) .$

8.2.2 The ShiftRows Transformation

The four rows of the matrix are shifted cyclically to the left by offsets of 0, 1, 2, and 3, to obtain

(\begin{array}{c} c_{0, 0} & c_{0, 1} & c_{0, 2} & c_{0, 3} \\ c_{1, 0} & c_{1, 1} & c_{1, 2} & c_{1, 3} \\ c_{2, 0} & c_{2, 1} & c_{2, 2} & c_{2, 3} \\ c_{3, 0} & c_{3, 1} & c_{3, 2} & c_{3, 3} \end{array}) = (\begin{array}{c} b_{0, 0} & b_{0, 1} & b_{0, 2} & b_{0, 3} \\ b_{1, 1} & b_{1, 2} & b_{1, 3} & b_{1, 0} \\ b_{2, 2} & b_{2, 3} & b_{2, 0} & b_{2, 1} \\ b_{3, 3} & b_{3, 0} & b_{3, 1} & b_{3, 2} \end{array}) .

$(\begin{array}{c} c_{0, 0} & c_{0, 1} & c_{0, 2} & c_{0, 3} \\ c_{1, 0} & c_{1, 1} & c_{1, 2} & c_{1, 3} \\ c_{2, 0} & c_{2, 1} & c_{2, 2} & c_{2, 3} \\ c_{3, 0} & c_{3, 1} & c_{3, 2} & c_{3, 3} \end{array}) = (\begin{array}{c} b_{0, 0} & b_{0, 1} & b_{0, 2} & b_{0, 3} \\ b_{1, 1} & b_{1, 2} & b_{1, 3} & b_{1, 0} \\ b_{2, 2} & b_{2, 3} & b_{2, 0} & b_{2, 1} \\ b_{3, 3} & b_{3, 0} & b_{3, 1} & b_{3, 2} \end{array}) .$

8.2.3 The MixColumns Transformation

Regard a byte as an element of $G F (2^{8})$ $G F (2^{8})$ , as in Section 3.11. Then the output of the ShiftRows step is a $4 \times 4$ $4 \times 4$ matrix $(c_{i, j})$ $(c_{i, j})$ with entries in $G F (2^{8})$ $G F (2^{8})$ . Multiply this by a matrix, again with entries in $G F (2^{8})$ $G F (2^{8})$ , to produce the output $(d_{i, j})$ $(d_{i, j})$ , as follows:

(\begin{array}{c} 00000010 & 00000011 & 00000001 & 00000001 \\ 00000001 & 00000010 & 00000011 & 00000001 \\ 00000001 & 00000001 & 00000010 & 00000011 \\ 00000011 & 00000001 & 00000001 & 00000010 \end{array}) (\begin{array}{c} c_{0, 0} & c_{0, 1} & c_{0, 2} & c_{0, 3} \\ c_{1, 0} & c_{1, 1} & c_{1, 2} & c_{1, 3} \\ c_{2, 0} & c_{2, 1} & c_{2, 2} & c_{2, 3} \\ c_{3, 0} & c_{3, 1} & c_{3, 2} & c_{3, 3} \end{array})

$(\begin{array}{c} 00000010 & 00000011 & 00000001 & 00000001 \\ 00000001 & 00000010 & 00000011 & 00000001 \\ 00000001 & 00000001 & 00000010 & 00000011 \\ 00000011 & 00000001 & 00000001 & 00000010 \end{array}) (\begin{array}{c} c_{0, 0} & c_{0, 1} & c_{0, 2} & c_{0, 3} \\ c_{1, 0} & c_{1, 1} & c_{1, 2} & c_{1, 3} \\ c_{2, 0} & c_{2, 1} & c_{2, 2} & c_{2, 3} \\ c_{3, 0} & c_{3, 1} & c_{3, 2} & c_{3, 3} \end{array})$

= (\begin{array}{c} d_{0, 0} & d_{0, 1} & d_{0, 2} & d_{0, 3} \\ d_{1, 0} & d_{1, 1} & d_{1, 2} & d_{1, 3} \\ d_{2, 0} & d_{2, 1} & d_{2, 2} & d_{2, 3} \\ d_{3, 0} & d_{3, 1} & d_{3, 2} & d_{3, 3} \end{array}) .

$= (\begin{array}{c} d_{0, 0} & d_{0, 1} & d_{0, 2} & d_{0, 3} \\ d_{1, 0} & d_{1, 1} & d_{1, 2} & d_{1, 3} \\ d_{2, 0} & d_{2, 1} & d_{2, 2} & d_{2, 3} \\ d_{3, 0} & d_{3, 1} & d_{3, 2} & d_{3, 3} \end{array}) .$

8.2.4 The RoundKey Addition

The round key, derived from the key in a way we’ll describe later, consists of 128 bits, which are arranged in a $4 \times 4$ $4 \times 4$ matrix $(k_{i, j})$ $(k_{i, j})$ consisting of bytes. This is XORed with the output of the MixColumns step:

(\begin{array}{c} d_{0, 0} & d_{0, 1} & d_{0, 2} & d_{0, 3} \\ d_{1, 0} & d_{1, 1} & d_{1, 2} & d_{1, 3} \\ d_{2, 0} & d_{2, 1} & d_{2, 2} & d_{2, 3} \\ d_{3, 0} & d_{3, 1} & d_{3, 2} & d_{3, 3} \end{array}) ⨁ (\begin{array}{c} k_{0, 0} & k_{0, 1} & k_{0, 2} & k_{0, 3} \\ k_{1, 0} & k_{1, 1} & k_{1, 2} & k_{1, 3} \\ k_{2, 0} & k_{2, 1} & k_{2, 2} & k_{2, 3} \\ k_{3, 0} & k_{3, 1} & k_{3, 2} & k_{3, 3} \end{array})

$(\begin{array}{c} d_{0, 0} & d_{0, 1} & d_{0, 2} & d_{0, 3} \\ d_{1, 0} & d_{1, 1} & d_{1, 2} & d_{1, 3} \\ d_{2, 0} & d_{2, 1} & d_{2, 2} & d_{2, 3} \\ d_{3, 0} & d_{3, 1} & d_{3, 2} & d_{3, 3} \end{array}) ⨁ (\begin{array}{c} k_{0, 0} & k_{0, 1} & k_{0, 2} & k_{0, 3} \\ k_{1, 0} & k_{1, 1} & k_{1, 2} & k_{1, 3} \\ k_{2, 0} & k_{2, 1} & k_{2, 2} & k_{2, 3} \\ k_{3, 0} & k_{3, 1} & k_{3, 2} & k_{3, 3} \end{array})$

= (\begin{array}{c} e_{0, 0} & e_{0, 1} & e_{0, 2} & e_{0, 3} \\ e_{1, 0} & e_{1, 1} & e_{1, 2} & e_{1, 3} \\ e_{2, 0} & e_{2, 1} & e_{2, 2} & e_{2, 3} \\ e_{3, 0} & e_{3, 1} & e_{3, 2} & e_{3, 3} \end{array}) .

$= (\begin{array}{c} e_{0, 0} & e_{0, 1} & e_{0, 2} & e_{0, 3} \\ e_{1, 0} & e_{1, 1} & e_{1, 2} & e_{1, 3} \\ e_{2, 0} & e_{2, 1} & e_{2, 2} & e_{2, 3} \\ e_{3, 0} & e_{3, 1} & e_{3, 2} & e_{3, 3} \end{array}) .$

This is the final output of the round.

8.2.5 The Key Schedule

The original key consists of 128 bits, which are arranged into a $4 \times 4$ $4 \times 4$ matrix of bytes. This matrix is expanded by adjoining 40 more columns, as follows. Label the first four columns $W (0), W (1), W (2), W (3)$ $W (0), W (1), W (2), W (3)$ . The new columns are generated recursively. Suppose columns up through $W (i - 1)$ $W (i - 1)$ have been defined. If $i$ $i$ is not a multiple of 4, then

W (i) = W (i - 4) \oplus W (i - 1) .

$W (i) = W (i - 4) \oplus W (i - 1) .$

If $i$ $i$ is a multiple of 4, then

W (i) = W (i - 4) \oplus T (W (i - 1)),

$W (i) = W (i - 4) \oplus T (W (i - 1)),$

where $T (W (i - 1))$ $T (W (i - 1))$ is the transformation of $W (i - 1)$ $W (i - 1)$ obtained as follows. Let the elements of the column $W (i - 1)$ $W (i - 1)$ be $a, b, c, d$ $a, b, c, d$ . Shift these cyclically to obtain $b, c, d, a$ $b, c, d, a$ . Now replace each of these bytes with the corresponding element in the S-box from the SubBytes step, to get 4 bytes $e, f, g, h$ $e, f, g, h$ . Finally, compute the round constant

r (i) = 00000010^{(i - 4) / 4}

$r (i) = 00000010^{(i - 4) / 4}$

in $G F (2^{8})$ $G F (2^{8})$ (recall that we are in the case where $i$ $i$ is a multiple of 4). Then $T (W (i - 1))$ $T (W (i - 1))$ is the column vector

(e \oplus r (i), f, g, h) .

$(e \oplus r (i), f, g, h) .$

In this way, columns $W (4), \dots, W (43)$ $W (4), \dots, W (43)$ are generated from the initial four columns.

The round key for the $i$ $i$ th round consists of the columns

W (4 i), W (4 i + 1), W (4 i + 2), W (4 i + 3) .

$W (4 i), W (4 i + 1), W (4 i + 2), W (4 i + 3) .$

8.2.6 The Construction of the S-Box

Although the S-box is implemented as a lookup table, it has a simple mathematical description. Start with a byte $x_{7} x_{6} x_{5} x_{4} x_{3} x_{2} x_{1} x_{0}$ $x_{7} x_{6} x_{5} x_{4} x_{3} x_{2} x_{1} x_{0}$ , where each $x_{i}$ $x_{i}$ is a binary bit. Compute its inverse in $G F (2^{8})$ $G F (2^{8})$ , as in Section 3.11. If the byte is 00000000, there is no inverse, so we use 00000000 in place of its inverse. The resulting byte $y_{7} y_{6} y_{5} y_{4} y_{3} y_{2} y_{1} y_{0}$ $y_{7} y_{6} y_{5} y_{4} y_{3} y_{2} y_{1} y_{0}$ represents an eight-dimensional column vector, with the rightmost bit $y_{0}$ $y_{0}$ in the top position. Multiply by a matrix and add the column vector $(1, 1, 0, 0, 0, 1, 1, 0)$ $(1, 1, 0, 0, 0, 1, 1, 0)$ to obtain a vector $(z_{0}, z_{1}, z_{2}, z_{3}, z_{4}, z_{5}, z_{6}, z_{7})$ $(z_{0}, z_{1}, z_{2}, z_{3}, z_{4}, z_{5}, z_{6}, z_{7})$ as follows:

(\begin{array}{c} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{array}) (\begin{matrix} y_{0} \\ y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ y_{5} \\ y_{6} \\ y_{7} \end{matrix}) + (\begin{matrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{matrix}) = (\begin{matrix} z_{0} \\ z_{1} \\ z_{2} \\ z_{3} \\ z_{4} \\ z_{5} \\ z_{6} \\ z_{7} \end{matrix}) .

$(\begin{array}{c} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{array}) (\begin{matrix} y_{0} \\ y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ y_{5} \\ y_{6} \\ y_{7} \end{matrix}) + (\begin{matrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{matrix}) = (\begin{matrix} z_{0} \\ z_{1} \\ z_{2} \\ z_{3} \\ z_{4} \\ z_{5} \\ z_{6} \\ z_{7} \end{matrix}) .$

The byte $z_{7} z_{6} z_{5} z_{4} z_{3} z_{2} z_{1} z_{0}$ $z_{7} z_{6} z_{5} z_{4} z_{3} z_{2} z_{1} z_{0}$ is the entry in the S-box.

For example, start with the byte $11001011$ $11001011$ . Its inverse in $G F (2^{8})$ $G F (2^{8})$ is $00000100$ $00000100$ , as we calculated in Section 3.11. We now calculate

(\begin{array}{c} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{array}) (\begin{matrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}) + (\begin{matrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{matrix}) = (\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}) .

$(\begin{array}{c} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{array}) (\begin{matrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{matrix}) + (\begin{matrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{matrix}) = (\begin{matrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \end{matrix}) .$

This yields the byte 00011111. The first four bits 1100 represent 12 in binary and the last four bits 1011 represent 11 in binary. Add 1 to each of these numbers (since the first row and column are numbered 0) and look in the 13th row and 12th column of the S-box. The entry is 31, which in binary is 00011111.

Some of the considerations in the design of the S-box were the following. The map $x \mapsto x^{- 1}$ $x \mapsto x^{- 1}$ was used to achieve nonlinearity. However, the simplicity of this map could possibly allow certain attacks, so it was combined with multiplication by the matrix and adding the vector, as described previously. The matrix was chosen mostly because of its simple form (note how the rows are shifts of each other). The vector was chosen so that no input ever equals its S-box output or the complement of its S-box output (complementation means changing each 1 to 0 and each 0 to 1).

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for
8.2 The Layers

8.2 The Layers

8.2.1 The SubBytes Transformation

Table 8.1 S-Box for Rijndael

8.2.2 The ShiftRows Transformation

8.2.3 The MixColumns Transformation

8.2.4 The RoundKey Addition

8.2.5 The Key Schedule

8.2.6 The Construction of the S-Box

Table of Contents for 8.2 The Layers

Create new playlist

Sign In

Sign Up

Table of Contents for
8.2 The Layers