Inside the AES S-box
The AES (Advanced Encryption Standard) algorithm takes in blocks of 128 or more bits [1] and applies a sequence of substitutions and permutations. The substitutions employ an "S-box", named the Rijndael S-box after its designers [2], an invertible nonlinear transformation that works on 8 bits at a time.
There are 256 = 16 i- 16 possible 8-bit numbers, and so the S-box can be represented as a 16 by 16 table mapping inputs to outputs. You can find the tables representing the S-box and its inverse in this text file in org-mode format.
This post will look in detail at how the entries of that table are filled. A high-level description of the design is as follows. For an 8-bit number x,
- Invert in GF(28)
- Multiply by a matrix L
- Add a constant c.
Next we dive into what each of these steps mean. And at the end we'll work an example in detail.
My source is The Block Cipher Companion by Knudsen and Robshaw.
Inversion in GF(28)Steps 1 and 3 take the inverse of a number as a member of the finite field GF(28), a finite field with 28 elements.
The number of elements in a finite field determines the field, up to isomorphism. That is, in a sense there is only one field with 28 = 256 elements. In fact there are 30 different fields with 256 elements (see this post for where that number came from). The 30 fields are isomorphic, but when we're doing actual calculations, rather than abstract theory, we need to specify which representation we're using.
Finite fields can be specified as polynomials modulo an irreducible polynomial. To carry out our calculations we need to specify a particular irreducible 8th degree polynomial with binary coefficients. The one that AES uses is
p(x) = x8 + x4 + x3 + x + 1.
So by taking the inverse in GF(28) we mean to take an 8-bit number y, interpret it as a polynomial with binary coefficients, and find another 8-bit number x-1 such that when we multiply them as polynomials, and take the remainder after dividing by p(x) we get the polynomial 1.
There's one wrinkle in this procedure: only 255 of the 256 elements of GF(28) have an inverse. There is no inverse for 0, but for our purposes we'll take the inverse of 0 to be 0.
Multiplication by LThe matrix L we need here is the 8 by 8 binary matrix whose entries are
10001111 11000111 11100011 11110001 11111000 01111100 00111110 00011111
When we say to multiply x-1 by L we mean to think of x-1 as a vector over the field of two elements, and carry out matrix multiplication in that context.
Additive constantThe constant that we add is 0x63. The reason an additive constant was chosen was so that a zero input would not map to a zero output. Note that "addition" here is vector addition, and is carried out over the field of two elements, just as the multiplication above. This amounts to XOR of the bits.
Manual calculation exampleTo make everything above more concrete, we'll calculate one entry of the table by hand.
Lets start with input y = 0x11 = 0b10001. We represent y as the polynomial f(x) = x4 + 1 and look for a polynomial g(x) such that the remainder when f(x) g(x) is divided by p(x) defined above is 1.
The process of finding g is complicated-maybe I'll blog about it in the future-but I claim
g(x) = x7 + x5 + x4 + x2
which means the inverse of y in GF(28), represented in binary, is 0b10110100 = 0xB4. You can find a table of inverses here.
Next we multiply the matrix L by the vector made from the bits of y-1. However, there is a gotcha here. When Knudsen and Robshaw say to multiply the bits of y-1 by L, they assume the bits are arranged from least significant to most significant. Since the bits of y-1 are 10110100, we multiply L by the vector
[0, 0, 1, 0, 1, 1, 0, 1].
This multiplication gives us the vector
[1, 0, 0, 0, 0, 1, 1, 1].
Next we add the vector formed from the bits of 0x63, again from least significant to most significant. That means we lay out 0x63 = 0b01100011 as
[1, 1, 0, 0, 0, 1, 1, 0].
This gives us the result
[0, 1, 0, 0, 0, 0, 0, 1].
Reading the bits from least significant to most, this gives 0x82.
In sum, we've verified that the AES S-box takes 0x11 to 0x82, as stated in the table.
Related posts[1] The Rijndael block cipher operates on blocks whose size is a multiple of 32 bits. The AES standard adopted Rijndael with block sizes 128, 192, and 256.
[2] "Rijndael" is a play on the designers of the cipher, Vincent Rijmen and Joan Daemen.