19.2 The Rijndael Algorithm

Team-Fly

---

19.2 The Rijndael Algorithm

Rijndael is a symmetric block encryption algorithm with variable block and key lengths. It can process blocks of 128, 192, and 256 bits and keys of the same lengths, where all combinations of block and key lengths are possible. The accepted key lengths correspond to the guidelines for AES, though the "official" block length is only 128 bits. Each block of plain text is encrypted several times with a repeating sequence of various functions, in so-called rounds. The number of rounds is dependent on the block and key lengths (see Table 19.4).

Table 19.4: Number of Rijndael rounds as a function of block and key length

	Block length (bits)
Key length (bits)	128	192	256
128	10	12	14
192	12	12	14
256	14	14	14

Rijndael is not a Feistel algorithm, whose essential characteristic is that blocks are divided into left and right halves, the round transformations applied to one half, and the result XOR-ed with the other half, after which the two halves are exchanged. DES is the best-known block algorithm built along these lines. Rijndael, on the other hand, is built up of separate layers, which successively apply various effects to an entire block. For the encryption of a block the following transformations are sequentially applied:

1. The first round key is XOR-ed with the block.

2. L_r − 1 regular rounds are executed.

3. A terminal round is executed, in which the MixColumn transformation of the regular rounds is omitted.

Each regular round of step 2 consists of four individual steps, which we shall now examine:

1. Substitution: Each byte of a block is replaced by application of an S-box.

2. Permutation: The bytes of the block are permuted in a ShiftRow transformation.

3. Diffusion: The MixColumn transformation is executed.

4. Round key addition: The current round key is XOR-ed with the block.

The layering of transformations within a round is shown schematically in Figure 19.1.

Figure 19.1: Layering of transformations in the Rijndael rounds

Each layer exercises a particular effect within a round and thus on each block of plain text:

1. Influence of the key

   XOR-ing with the round key before the first round and as the last step within each round has an effect on every bit of the round result. In the course of encryption of a block there is no step whose result is not dependent in every bit on the key.

2. Nonlinear layer

   The S-box substitution is a nonlinear operation. The construction of the S-box provides almost ideal protection against differential and linear cryptanalysis (see [BiSh] and [NIST]).

3. Linear layer

   The ShiftRow and MixColumn transformations ensure an optimal mixing up of the bits of a block.

In the following description of the internal Rijndael functions L_b will denote the block length in 4-byte words, L_k the length of the user key in 4-byte words (that is, L_b, L_k Î {4, 6, 8}), and L_r the number of rounds as indicated in Table 19.4.

Plain text and encrypted text are input, respectively output, as fields of bytes. A block of plain text, passed as a field m₀,..., , will be regarded in the following as a two-dimensional structure as depicted in Table 19.5,

Table 19.5: Representation of message blocks

b0,0	b0,1	b0,2	b0,3	b0,4	...
b1,0	b1,1	b1,2	b1,3	b1,4	...
b2,0	b2,1	b2,2	b2,3	b2,4	...
b3,0	b3,1	b3,2	b3,3	b3,4	...

where the bytes of plain text are sorted according to the following ordering:

with i = n mod 4 and j = ⌊n/4⌋.

Access to within the Rijndael functions takes place in different ways according to the operation. The S-box transformation operates bytewise, ShiftRow operates on rows (b_i,0, b_i,1, b_i,2,..., ) of , and the functions AddRoundKey and MixColumn operate on 4-byte words and access the values of by columns (b_0,j, b_1,j, b_2,j, b_3,j).

---

Team-Fly