The AES cipher

The Advanced Encryption Standard (AES) has been selected by the National Institute of Standards and Technology (NIST) after a five-year long competition. The original name of the cipher is Rijndael from the names of the two inventors, the cryptographers Joan Daemen and Vincent Rijmen. As any modern cipher, AES is the composition of rather simple operations and contains a non-linear component to avoid known-plaintexts attacks (as the one we have seen on the Hill cipher). The composed operations give a non-idempotent cipher that is iterated for a fixed number of rounds.

Rijndael has been selected because it resulted to be the best one providing:

  • high security guarantees
  • high performance
  • flexibility (different key length)

All of these features are, in fact, crucial for any modern cipher.  Its predecessor, the Data Encryption Standard (DES) is still in use after almost 40 years, in a variant called Triple DES (3DES), which aims at improving the key length. In fact, DES key of only 56 bits is too short to resist brute-forcing on modern, parallel computers.

Mathematical background

AES works on the Galois Field with 2^8 elements noted \mathbf{GF}(2^8). Intuitively, it it the set of all 8-bit digits with sum and multiplications performed by interpreting the bits as (binary) coefficients of polinomials. For example, element 11010011 can be seens as x^7 + x^6 + x^4 + x + 1 while 00111010 is x^5+x^4+x^3 + x. The sum will thus be x^7+x^6+x^4+x+1+x^5+x^4+x^3+x=x^7+x^6+x^5+x^3+1, since two 1’s coefficient becomes 0, modulo 2, and the term disappears (for example x + x = 2x = 0x = 0). We see that sum and subtraction are just the bit-wise xor of the binary numbers, i.e., 11010011 \oplus 00111010 = 11101001 which is x^7+x^6+x^5+x^3+1.

Product is done modulo the irreducible polinomial x8 + x4 + x3 + x + 1. Irreducible means that it cannot be written as the product of two other polinomials (it is, intuitively, the equivalent of primality). For example, (x^7 + x^6 + x^4 + x + 1) \times (x^5+x^4+x^3 + x) gives

x^{12} + x^{11} + x^9 + x^6 + x^5+x^{11}+x^{10}+x^8+x^5+x^4+x^{10}+x^9+x^7+x^4+x^3+x^8+x^7+x^5+x^2+x = x^{12}+x^6+x^5+x^3+x^2+x

Now to divide x^{12}+x^6+x^5+x^3+x^2+x by x^8 + x^4 + x^3 + x + 1 and find