We start by looking at arithmetic in the field • _2ⁿ, the finite field with 2ⁿ elements, where an element of • _2ⁿ is represented as a polynomial f(x) = a_{n− 1}xⁿ⁻¹ + a_n−2xⁿ⁻² + ... + a₁x+ a₀ with coefficients a_i in • ₂ (which is isomorphic to •₂). Equivalently, an element of •_2ⁿ can be represented simply as an n-tuple of polynomial coefficients, each representation offering its own advantages. The polynomial representation is well suited for manual calculation, while the representation as a tuple of coefficients corresponds well to a computer's binary representation of numbers. To demonstrate this, we notate •_2³ as a sequence of eight polynomials and again as eight 3-tuples with their associated numerical values (see Table 11-1).

Addition of polynomials proceeds by adding the coefficients in •₂: If f(x) := x² + x and g(x) := x² + x + 1, then f(x) + g(x) = 2x² + 2x + 1 = 1, since 1+1 = 0 in •₂. We can carry out addition of 3-tuples in •_2³ column by column. We see, then, for example, that the sum of (1 1 0) and (1 1 1) is (0 0 1):

Equation 11.1. 

The addition of digits takes place in •₂ and is not to be confused with binary addition, which can involve a carry. This process is reminiscent of our XOR function in Section 7.2, which executes the same operation in •_n for large n.

Multiplication in •_2³ is accomplished by multiplying each term of the first polynomial by each term of the second and then summing the partial products. The sum is then reduced by an irreducible polynomial of degree 3 (in our example modulo m(x) := x³ + x + 1):^[34]

Equation 11.2. 

This corresponds to the product of 3-tuples (1 1 0) • (1 1 1) = (1 0 0), or, expressed numerically, '06' • '07' = '04'.

The abelian group laws hold in •_2³ with respect to addition and in •_2³ {0} with respect to multiplication (cf. Chapter 5). The distributive law holds as well.

The structure and arithmetic of •_2³ can be carried over directly to the field •_2⁸, which is the field that is actually of interest in studying Rijndael. Addition and multiplication are carried out as in our above example, the only differences being that •_2⁸ has 256 elements and that an irreducible polynomial of degree 8 will be used for reduction. For Rijndael this polynomial is m(x) := x⁸ + x⁴ + x³ + x + 1, which in tuple representation is (1 0 0 0 1 1 0 1 1), corresponding to the hexadecimal number '011B'.

Multiplication of a polynomial

Equation 11.3. 

by x (corresponding to a multiplication • '02') is particularly simple:

Equation 11.4. 

where the reduction modulo m(x) is required only in the case a₇ ≠ 0, and then it can be carried out by subtracting m(x), that is, by a simple XOR of the coefficients.

For programming one therefore regards the coefficients of a polynomial as binary digits of integers and executes a multiplication by x by a left shift of one bit, followed by, if a₇ = 1, a reduction by an XOR operation with the eight least-significant digits '1B' of the number '011B' corresponding to m(x) (whereby a₇ is simply "forgotten"). The operation a • '02' for a polynomial f, or its numerical value a, is denoted by Daemen and Rijmen by b = xtime(a). Multiplication by powers of x can be executed by successive applications of xtime().

For example, multiplication of f(x) by x + 1 (or '03') is carried out by shifting the binary digits of the numerical value a of f one place to the left and XOR-ing the result with a. Reduction modulo m(x) proceeds exactly as with xtime. Two lines of C code demonstrate the procedure:

f ^= f << 1;    /* multiplication of f by (x + 1) */
if (f & 0x100) f ^= 0x11B;    /* reduction modulo m(x) */

Multiplication of two polynomials f and h in •_2⁸ {0} can be speeded up by using logarithms: Let g(x) be a generating polynomial^[35] of •_2⁸ {0}. Then there exist m and n such that f ≡ g^m and h ≡ gⁿ. Thus f • h ≡ g^m+n mod m(x).

From a programming point of view this can be transposed with the help of two tables, into one of which we place the 255 powers of the generator polynomial g(x) := x + 1 and into the other the logarithms to the base g(x) (see Tables 11-2 and 11-3). The product f • h is now determined by three accesses to these tables: From the logarithm table are taken values m and n for which g^m = f and gⁿ = h. From the table of powers the value g^{((n+m)mod255)} is taken (note that g^ord(g) = 1) Table 11-2 contains the powers of g twice in succession, and so one can avoid having to reduce the exponent of g in f • h = g^n+m.

With the help of this mechanism we can also carry out polynomial division in •_2⁸. Thus for f, g € •_2⁸ {0},

Equation 11.5. 

This procedure for polynomial multiplication in •_2⁸ is illustrated in the function polymul():

UCHAR
polymul (unsigned int f, unsigned int h)
{
  if ((f != 0) && (h != 0))
    {

return (AntiLogTable[LogTable[f] + LogTable[h]]);
  }
else
  {
    return 0;
  }
}

We now ratchet the complexity level up one notch and consider arithmetic with polynomials of the form f(x) = f₃x³ + f₂x² + f₁x + f₀ with coefficients f_i in •_2⁸, that is, coefficients that are themselves polynomials. The coefficients of such polynomials can be represented as fields of four bytes each. Now things begin to get interesting: While addition of such polynomials f(x) and g(x) again takes place by means of a bitwise XOR of the coefficients, the product h(x) = f(x)g(x) is calculated to be

Equation 11.6. 

with coefficients

After reduction of h(x) by a polynomial of degree 4, one again obtains a polynomial of degree 3 over •_2⁸.

For this Rijndael uses the polynomial m(x) := x⁴ + 1. Usefully, x^j mod M(x) = x^jmod4, so that h(x) mod m(x) can be easily computed as

Equation 11.7. 

with

Equation 11.8. 

From this one concludes that the coefficients d_i can be computed by matrix multiplication over •_2⁸:

Equation 11.9. 

It is precisely this operation with the constant, invertible modulo M(x), polynomial a(x) := a₃x³ + a₂x² + a₁x + a₀ over •_2⁸, with coefficients a₀(x) = x, a₁(x) = 1, a₂(x) = 1, and a₃(x) = x + 1, that is executed in the so-called MixColumns transformation, which constitutes a principal component of the round transformations of Rijndael.

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 11-4).

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:

Table 11-4. Number of Rijndael rounds as a function of block and key length

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

The layering of transformations within a round is shown schematically in Figure 11-1.

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

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 11-4.

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

Figure 11-1. Layering of transformations in the Rijndael rounds

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

Equation 11.10. 

with i = n mod 4 and j =

Access to

Encryption and decryption each require the generation of L_r round keys, called collectively the key schedule. This occurs through expansion of the secret user key by attaching recursively derived 4-byte words k_i = (k_0,i, k_1,i, k_2,i, k_3,i)) to the user key.

The first L_k words k₀, ..., k_Lk−1 of the key schedule are formed from the secret user key itself. For L_k € {4,6} the next 4-byte word k_i is determined by XOR-ing the preceding word k_i−1 with k_i-Lk. If i ≡ 0 mod L_k, then a function F_Lk (k,i) is applied before the XOR operation, which is composed of a cyclic left shift (left rotation) r(k) of k bytes, a substitution S(r(k)) from the Rijndael S-box (we shall return to this later), and an XOR with a constant c (

The constants c(j) are defined by c(j) := (rc(j)0, 0, 0), where rc(j) are recursively determined elements from •_2⁸: rc(1) := 1, rc(j) := rc(j − 1) • x = x^j−1 . Expressed in numerical values, this is equivalent to rc(1) := '01', rc(j) := rc(j − 1) • '02'. From the standpoint of programming, rc(j) is computed by a (j − 1)-fold execution of the function xtime described above, beginning with the argument 1, or more rapidly by access to a table (Tables 11-6 and 11-7).

For keys of length 256 bits (that is, L_k = 8) an additional S-box operation is inserted: If i ≡ 4 mod L_k, then before the XOR operation k_i−1 is replaced by S (k_i−1).

Thus a key schedule is built up of L_b • (L_r + 1) 4-byte words, including the secret user key. At each round i = 0, ..., L_r - 1 the next L_b 4-byte words k_Lb•i through kL_b•(i+1) are taken as round keys from the key schedule. The round keys are conceptualized, in analogy to the structuring of the message blocks, as a two-dimensional structure of the form depicted in Table 11-8.

For key lengths of 128 bits key generation can be understood from an examination of Figure 11-2.

Figure 11-2. Diagram for round keys for Lk = 4

There are no weak keys known, those whose use would weaken the procedure.

The substitution box, or S-box, of the Rijndael algorithm specifies how in each round each byte of a block is to be replaced by another value.

The S-box has the task of minimizing the susceptibility of the algorithm to methods of linear and differential cryptanalysis and to algebraic attacks. To accomplish this, the S-box operation should possess a high algebraic complexity in •_2⁸ and thus create a good extension to the ShiftRows and MixColumns operations. Not having such a function would support attacks within •_2⁸ and thereby decisively weaken the procedure.

In addition to the requirement of complexity the S-box function must of course be invertible; it must have no fixed points S(a) = a or complementary fixed points S(a) = ā; and it must also execute rapidly and be easy to implement.

All these desiderata were achieved through a combination of multiplicative inversion in •_2⁸ and the previously mentioned affine mapping from •_2⁸ to itself. The S-box consists of a list of 256 bytes, which are constructed by first thinking of each nonzero byte as a representative of •_2⁸ and replacing it with its multiplicative inverse (zero remains unchanged). Then an affine transformation over •₂ is calculated as a matrix multiplication and addition of (1 1 0 0 0 1 1 0):

Equation 11.11. 

In this representation x₀ and y₀ denote the least-significant, and x₇ and y₇ the most-significant, bits of a byte, where the 8-tuple (1 1 0 0 0 1 1 0) corresponds to the hexadecimal value '63'.

Through this construction, all of the requisite design criteria were satisfied. The substitution is thereby an ideal strengthening of the algorithm. Successive application of the construction plan to the values 0 to 255 leads to Table 11-9 (in hexadecimal form; read horizontally from left to right).

For decryption the S-box must be used backwards: The affine inverse transformation is used, followed by multiplicative inversion in •_2⁸. The inverted S-box appears in Table 11-10.

The next step in the cycle of a round consists in the permutation of a block at the byte level. To this end the bytes are exchanged within the individual lines (b_i,0, b_i,1, b_i,2, . . ., b_{i, Lb − 1}) of a block according to the schemata depicted in Tables 11-11 through 11-13.

In each first row (row index i = 0) no exchange takes place. In lines i = 1, 2, 3 the bytes are rotated left by c_Lb,i positions, from position j to position j - c_Lb,i mod L_b, where c_Lb,i is taken from Table 11-14.

For inverting this step, positions j in rows i = 1, 2, 3 are shifted to positions j + c_Lb,i mod L_b.

After the rowwise permutation in the last step, in this step each column (b_i,j), i = 0 ,..., 3, j = 0 ,..., L_b of a block is taken to be a polynomial over •_2⁸ and multiplied by the constant polynomial a(x) := a₃x³ + a₂x² + a₁x + a₀, with coefficients a₀(x) = x, a₁(x) = 1, a₂(x) = 1, a₃(x) = x + 1, and reduced modulo M(x) := x⁴ + 1. Each byte of a column thus interacts with every other byte of the column. The rowwise operating ShiftRows transformation has the effect that in each round, other bytes are mixed with one another, resulting in strong diffusion.

We have already seen (see page 244) how this step can be reduced to a matrix multiplication

Equation 11.12. 

with multiplication and addition carried out over •_2⁸. For multiplication by '02' (respectively x) the function xtime() has already been defined; multiplication by '03' (respectively x +1) has already been handled similarly (cf. page 247).

For inverting the MixColumns transformation every column (b_i,j) of a block is multiplied by the polynomial r (x) := r₃x³ + r₂x² + r₁x + r₀ with coefficients

Table 11-12. ShiftRows for blocks oflength 192 bits (Lb = 6)

Table 11-13. ShiftRows for blocks of length 256 bits (Lb =8)

r₀(x) = x³+x²+x, r₁(x) = x³+1, r₂(x) = x³+x²+1, and r₃(x) = x³+x+1 and reduced modulo M(x) := x⁴+1. The corresponding matrix is

Equation 11.13. 

The last step of a round carries out an XOR of the round key with the block:

Equation 11.14. 

for j = 0,..., L_b − 1. In this way, every bit of the result of a round is made dependent on every key bit.

Encryption with Rijndael is encapsulated in the following pseudocode according to [DaRi], Section 4.2–4.4. The arguments are passed as pointers to fields of bytes or 4-byte words. The interpretation of the fields, variables, and functions employed is provided in Tables 11-15 through 11-17.

Key generation:

KeyExpansion (byte CipherKey, word ExpandedKey)
{
  for (i = 0; i < Nk; i++)
    ExpandedKey[i] = (CipherKey[4*i], CipherKey[4*i + 1],
      CipherKey[4*i + 2], CipherKey[4*i + 3]);
  for (i = Nk; i < Nb * (Nr + 1); i++)
  {
    temp = ExpandedKey[i - 1];
    if (i % Nk == 0)
      temp = SubBytes (RotBytes (temp)) ^ Rcon[i/Nk];
    else if ((Nk == 8) && (i % Nk == 4))
       temp = SubBytes (temp);
    ExpandedKey[i] = ExpandedKey[i - Nk] ^ temp;
  }
}

Round functions:

Round (word State, word RoundKey)
{
  SubBytes (State);
  ShiftRows (State);
  MixColumns (State);
  AddRoundKey (State, RoundKey)
}
FinalRound (word State, word RoundKey)
{
  SubBytes (State);
  ShiftRows (State);
  AddRoundKey (State, RoundKey)
}

Entire operation for encrypting a block:

Rijndael (byte State, byte CipherKey)
{
  KeyExpansion (CipherKey, ExpandedKey);
  AddRoundKey (State, ExpandedKey);
  for (i = 1; i < Nr; i++)
    Round (State, ExpandedKey + Nb*i);
  FinalRound (State, ExpandedKey + Nb*Nr);
}

There exists the possibility of preparing the round key outside of the function Rijndael and to pass the key schedule ExpandedKey instead of the user key CipherKey. This is advantageous when it is necessary in the encryption of texts that are longer than a block to make several calls to Rijndael with the same user key.

Rijndael (byte State, byte ExpandedKey)
{
  AddRoundKey (State, ExpandedKey);
  for (i = 1; i < Nr; i++)
    Round (State, ExpandedKey + Nb*i);
  FinalRound (State, ExpandedKey + Nb*Nr);
}

Especially for 32-bit processors it is advantageous to precompute the round transformation and to store the results in tables. By replacing the permutation and matrix operations by accesses to tables, a great deal of CPU time is saved, yielding improved results for encryption, and, as we shall see, for decryption as well. With the help of four tables each of 256 4-byte words of the form

Equation 11.15. 

(for w = 0, ..., 255, S(w) denotes, as above, the S-box replacement), the transformation of a block b = (b_0,j,b_1,j,b_2,j,b_3,j), j = 0,...,L_b − 1, can be determined quickly for each round by the substitution

Equation 11.16. 

with d(i,j) := j + c_{Lb, i} mod L_b (cf. ShiftRows, Table 11-14) and k_j = (k_0,j, k_1,j, k_2,j, k_3,j) as the jth column of the round key.

For the derivation of this result, see [DaRi], Section 5.2.1. In the last round the MixColumns transformation is omitted, and thus the result is determined by

Equation 11.17. 

Clearly, it is also possible to use a table of 256 4-byte words, in which

Equation 11.18. 

with a right rotation r(a, b, c, d) = (d, a, b, c) by one byte. For environments with limited memory this can be a useful compromise, the price being only a slightly increased calculation time for the three rotations.

For Rijndael decryption one runs the encryption process in reverse order with the inverse transformations. We have already considered the inverses of the transformations SubBytes, ShiftRows, and MixColumns, which in the following are represented in pseudocode by the functions InvSubBytes, InvShiftRows, and InvMixColumns. The inverted S-box, the distances for inversion, the ShiftRows transformation, and the inverted matrix for the inversion of the MixColumns transformation are given on pages 251-252. The inverse round functions are the following:

InvFinalRound (word State, word RoundKey)
{
  AddRoundKey (State, RoundKey);
  InvShiftRows (State);
  InvSubBytes (State);
}

InvRound (word State, word RoundKey)
{
  AddRoundKey (State, RoundKey);
  InvMixColumns (State);
  InvShiftRows (State);
  InvSubBytes (State);
}

The entire operation for decryption of a block is as follows:

InvRijndael (byte State, byte CipherKey)
{
  KeyExpansion (CipherKey, ExpandedKey);
  InvFinalRound (State, ExpandedKey + Nb*Nr);
  for (i = Nr - 1; i > 0; i--)
    InvRound (State, ExpandedKey + Nb*i);
  AddRoundKey (State, ExpandedKey);
}

The algebraic structure of Rijndael makes it possible to arrange the transformations for encryption in such a way that here, too, tables can be employed. Here one must note that the substitution S and the InvShiftRows transformation commute, so that within a round their order can be switched. Because of the homomorphism property f(x + y) = f(x) + f(y) of linear transformations the InvMixColumns transformation and addition of the round key can be exchanged when InvMixColumns was used previously on the round key. Within a round the following course is taken:

InvFinalRound (word State, word RoundKey)
{
  AddRoundKey (State, RoundKey);
  InvSubBytes (State);
  InvShiftRows (State);
}

InvRound (word State, word RoundKey)
{
  InvMixColumns (State);
  AddRoundKey (State, InvMixColumns (RoundKey));
  InvSubBytes (State);
  InvShiftRows (State);
}

Without changing the sequence of transformations over both functions ordered one after the other, they can be redefined as follows:

AddRoundKey (State, RoundKey);

InvRound (word State, word RoundKey)
{
  InvSubBytes (State);
  InvShiftRows (State);
  InvMixColumns (State);
  AddRoundKey (State, InvMixColumns (RoundKey));
}

InvFinalRound (word State, word RoundKey)
{
  InvSubBytes (State);
  InvShiftRows (State);
  AddRoundKey (State, RoundKey);
}

With this is created the analogous structure to that for encryption. For reasons of efficiency the application of InvMixColumns to the round key in InvRound() is postponed until the key expansion, where the first and last round keys of InvMixColumns are left untouched. The "inverse" round keys are generated with

InvKeyExpansion (byte CipherKey, word InvEpandedKey)
{
  KeyExpansion (CipherKey, InvExpandedKey);
  for (i = 1; i < Nr; i++)
    InvMixColumns (InvExpandedKey + Nb*i);
}

The entire decryption operation of a block is now as follows:

InvRijndael (byte State, byte CipherKey)
{
  InvKeyExpansion (CipherKey, InvExpandedKey);
  AddRoundKey (State, InvExpandedKey + Nb*Nr);
  for (i = Nr - 1; i > 0; i--)
    InvRound (State, InvExpandedKey + Nb*i);
  InvFinalRound (State, InvExpandedKey);
}

In analogy to encryption, tables can be precomputed for this form of decryption. With

Equation 11.19. 

(for w = 0, ...,255, S⁻¹(w) denotes the inverse S-box replacement) the result of an inverse round operation on a block b = (b_0,j,b_1,j,b_2,j,b_3,j), j = 0, ..., L_b − 1, can be determined by

Equation 11.20. 

for j = 0, ..., L_b − 1 with d⁻¹ (i, j) := j − ^cL_b,i mod L_b (cf. page 250) and the jth column

Again in the last round the MixColumns transformation is omitted, and thus the result of the last round is given by

Equation 11.21. 

To save memory one can also make do in decryption with a table of only 256 4-byte words, in which

Equation 11.22. 

with a right rotation r(a, b, c, d) = (d, a, b, c) of one byte.

Implementations for various platforms have verified the superior performance of Rijndael. The bandwidth suffices for realizations for small 8-bit controllers with small amounts of memory and key generation on the fly up through current 32-bit processors. For purposes of comparison, Table 11-18 provides encryption rates for the candidates RC6, Rijndael, and Twofish, as well as for the older 8051 controller and the Advanced Risc Machine (ARM) as a modern 32-bit chip card controller.

Because of the more complex InvMixColumns operation, the times for decryption and encryption can diverge, depending on the implementation, though this effect can be completely compensated by using the tables described previously. Of course, the times depend on, in addition to the key length, the block length and the number of rounds (see Table 11-4). For comparison, on a Pentium III/200 MHz, throughput of about 8 MByte per second for a key of length 128 bits, about 7 Mbyte per second for 192-bit keys, and about 6 MByte per second for 256-bit keys for blocks of length 128 bits is achievable in both directions. On the same platform, the DES in C can encrypt and decrypt about 3.8 MByte per second (see [Gldm], http://fp.gladman.plus.com).

The classical operating modes Electronic Code Book (ECB), Cipher Block Chaining (CBC), Cipher Feedback (CFB), and Output Feedback (OFB) for block ciphers were updated by NIST for use with AES and provided with appropriate test vectors (see [FI81, N38A]). Consideration of additional operating modes, which had begun already in the framework of standardization of AES and which relates to the use of modes of operation in Internet communication, has resulted in the following operating modes:

For further details, investigations into security and cryptanalysis, computational times, and current information on AES and Rijndael the reader is referred to the literature cited above as well as the Internet sites of NIST and Vincent Rijmen, which in turn contain many links to further sources of information:

In the downloadable source code to this book there is an implementation of AES in the file aes.c, which can be used to deepen an understanding of the procedure and to do some experimentation.