As mentioned in the previous chapter, the National Institute of Standards and Technology (NIST) held a competition between 1997 and 2000 to determine a new symmetric encryption standard. The Rijndael cipher turned out to be the winning entry. The name is a word play on the names of the Belgian creators, Vincent Rijmen and Joan Daemen.

The Rijndael cipher is a block cipher, meaning there is a core algorithm, which can be used with different specifications for key lengths and block sizes. You can, then, use it with different modes of operation to construct encryption schemes.

The committee for the NIST competition adopted a constricted version of the Rijndael cipher—namely one which requires 128-bit block sizes and key lengths of either 128 bits, 192 bits, or 256 bits—as part of the Advanced Encryption Standard (AES). This constricted version of the Rijndael cipher can also be used under multiple modes of operation. The specification for the standard is what is known as the Advanced Encryption Standard (AES).

In order to show how the Rijndael cipher works, the core of AES, I will illustrate the process for encryption with a 128-bit key. The key size has an impact on the number of rounds held for each block of encryption. For 128-bit keys, 10 rounds are required. With 192 bits and 256 bits, it would have been 12 and 14 rounds, respectively.

In addition, I will assume that AES is used in ECB-mode. This makes exposition slightly easier and doesn't matter for the Rijndael algorithm. To be sure, ECB mode is not secure in practice because it leads to deterministic encryption. The most commonly used secure mode with AES is CBC (Cipher Block Chaining).

Let's call the key . The construction with the above parameters, then, looks as in Figure 1, where stands for a part of the plaintext message of 128 bits and for a part of the ciphertext of 128 bits. Padding is added to the plaintext for the last block, if the plaintext cannot be evenly divided by the block size.

Each 128-bit block of text goes through ten rounds in the Rijndael encryption scheme. This requires a separate round key for each round ( through ). These are produced for each round from the original 128-bit key using a key expansion algorithm. Hence, for each block of text to be encrypted, we will use the original key as well as ten separate round keys. Note that these same 11 keys are used for each 128-bit block of plaintext that requires encryption.

The key expansion algorithm is long and complex. Working through it has little didactic benefit. You can look through the key expansion algorithm on your own, if you wish. Once the round keys are produced, the Rijndael cipher will manipulate the first 128-bit block of plaintext, , as seen in Figure 2. We will now go through these steps.

Round 0 of the Rijndael cipher is straightforward. An array is produced by an XOR operation between the 128-bit plaintext and the private key. That is,

In round 1, the array is first combined with the round key using an XOR operation. This produces a new state of .

Second, the byte substitution operation is performed on the current state of . It works by taking each byte of the 16-byte array and substituting it with a byte from an array called Rijndael’s S-box. Each byte has a unique transformation, and a new state of is produced as a result. Rijndael's S-box is displayed in Figure 3.

This S-Box is one place where abstract algebra comes into play in the Rijndael cipher, specifically Galois fields.

To start, you define each possible byte element 00 through FF as an 8-bit vector. Each such vector is an element of the Galois field GF(2^8) where the irreducible polynomial for the modulo operation is . The Galois field with these specifications is also called Rijndael’s Finite Field.

Next, for each possible element in the field, we create what is called the Nyberg S-Box. In this box, each byte is mapped onto its multiplicative inverse (i.e., so that their product equals 1). We then map those values from the Nyberg S-box to Rijndael’s S-Box using the affine transformation.

The third operation on the S array is the shift rows operation. It takes the state of S and lists all of the sixteen bytes in a matrix. The filling of the matrix starts on the top left and works its way around by going from top to bottom and then, each time a column is filled, shifting one column right and to the top.

Once the matrix of S has been constructed, the four rows are shifted. The first row stays the same. The second row moves one over to the left. The third moves two over to the left. The fourth moves three over to the left. An example of the process is provided in Figure 4. The original state of S is shown on the top, and the resultant state after the shift rows operation is shown below it.

In the fourth step, Galois fields make an appearance again. To start, each column of the S matrix is multiplied by the column of the 4 x 4 matrix seen in Figure 5. But instead of being regular matrix multiplication, it is vector multiplication modulo an irreducible polynomial, . The resulting vector coefficients represent the individual bits of a byte.

Multiplication of the first column of the S matrix with the 4 x 4 matrix above yields the result in Figure 6.

As a next step, all the terms in the matrix would have to be turned into polynomials. For instance, F1 represents 1 byte and would become , and 03 represents 1 byte and would become .

All the multiplications are then performed modulo . This results in the addition of four polynomials in each of the four cells of the column. After performing those additions modulo 2, you will end up with four polynomials. Each of these polynomials represents an 8-bit string, or 1 byte, of S. We will not perform all these calculations here on the matrix in Figure 6 as they are extensive.

Once the first column has been processed, the other three columns of the S matrix are processed in the same manner. Eventually, this will yield a matrix with sixteen bytes that can be transformed into an array.

As a final step, the array S is combined with the round key again in an XOR operation. This produces the state . That is,

Rounds 2 through 9 are just a repetition of round 1, mutatis mutandis. The final round looks very similar to the previous rounds, except that the mix columns step is eliminated. That is, round 10 is executed as follows:

The state is now set to , the first 128 bits of the ciphertext. Proceeding through the remaining 128-bit plaintext blocks yields the full ciphertext C.

What is the reasoning behind the different operations seen in the Rijndael cipher?

Without entering into the details, encryption schemes are assessed on the basis of the extent they create confusion and diffusion. If the encryption scheme has a high degree of confusion, it means that the ciphertext looks drastically different than the plaintext. If the encryption scheme has a high degree of diffusion, it means that any small change to the plaintext produces a drastically different ciphertext.

The reasoning for the operations behind the Rijndael cipher is they produce both a high degree of confusion and diffusion. The confusion is produced by the Byte substitution operation, while the diffusion is produced by the shift rows and mix columns operations.