# How are the AES S-Boxes calculated?

I'm trying to understand how the AES S-Boxes are calculated. I understand how the multiplicative inverse is calculated over GF(2^8), but I'm confused by the description of the affine transformation. I haven't been able to Google a good explanation of how the S-Box values are calculated. Can someone explain how this works, starting after the calculation of the multiplicative inverse?

-
Just in case you're also looking for the design decisions of the fixed S-Boxes and how Rijmen calculated them, check out "The Design of Rijndael: AES - The Advanced Encryption Standard" by Joan Daemen and Vincent Rijmen. It's a good read and explains it all. – e-sushi Oct 13 '13 at 1:33
This is a partial (at least) answer to your question – rath Oct 13 '13 at 4:51
Page 50,51 of The Block Cipher Companion provide a clear explanation of how the S-box is designed – figlesquidge Oct 18 '13 at 10:46

The affine transformation works similar to MixColumns, but operates on an array of 8 bits instead of 4 bytes. Confusion in various descriptions of the affine transform in AES comes from where the LSB of the input byte is located. Some show it at the top of the column, others show it at the bottom. I will be using the version shown in the Rijndael paper, with the LSB at the top of the column.

The matrix used in AES is a rotational matrix based on the value 0x1F, which is 00011111 in binary. The multiplication is performed in the field GF(2), as is the addition of the final vector 0x63. Addition in GF(2) is the same as xor.

The bit indexes for the matrix are 76543210, with 0 being the least significant bit and 7 being the most significant. Each column is the previous column rotated to the left by a single bit, as shown here:

0  7  6  5  4  3  2  1
1  0  7  6  5  4  3  2
2  1  0  7  6  5  4  3
3  2  1  0  7  6  5  4
4  3  2  1  0  7  6  5
5  4  3  2  1  0  7  6
6  5  4  3  2  1  0  7
7  6  5  4  3  2  1  0


For the AES 0x1F affine matrix, the bits are arranged in the following way:

1  0  0  0  1  1  1  1
1  1  0  0  0  1  1  1
1  1  1  0  0  0  1  1
1  1  1  1  0  0  0  1
1  1  1  1  1  0  0  0
0  1  1  1  1  1  0  0
0  0  1  1  1  1  1  0
0  0  0  1  1  1  1  1


For an input of 0x53 in AES, we first find its inverse, which is 0xCA, represented in binary as 11001010

The affine transformation is as follows. The input bits are multiplied against the bits of a given row, with the first bit the LSB of the input. Input bit 0 is only multiplied by row bit 0, and so on. Only when both values are one (logical AND) is the result one. Finally, all bits are XORd against eachother within that row to generate the transformed bit for that row.

Input = 0  1  0  1  0  0  1  1 (LSB First)
Row 0 = 1  0  0  0  1  1  1  1
Bit 0 = 0  0  0  0  0  0  1  1 = 0

Row 1 = 1  1  0  0  0  1  1  1
Bit 1 = 0  1  0  0  0  0  1  1 = 1

Row 2 = 1  1  1  0  0  0  1  1
Bit 2 = 0  1  0  0  0  0  1  1 = 1

Row 3 = 1  1  1  1  0  0  0  1
Bit 3 = 0  1  0  1  0  0  0  1 = 1

Row 4 = 1  1  1  1  1  0  0  0
Bit 4 = 0  1  0  1  0  0  0  0 = 0

Row 5 = 0  1  1  1  1  1  0  0
Bit 5 = 0  1  0  1  0  0  0  0 = 0

Row 6 = 0  0  1  1  1  1  1  0
Bit 6 = 0  0  0  1  0  0  1  0 = 0

Row 7 = 0  0  0  1  1  1  1  1
Bit 7 = 0  0  0  1  0  0  1  1 = 1


The final result LSB first is 01110001 or MSB first is 10001110 = 0x8E. This value is then added (XOR) to the final vector 0x63, giving an output of 0xED

-
Thank you so much, that was perfect. – ConditionRacer Oct 13 '13 at 15:42
I understand how this works but I cannot understand why the algorithm presented in the wikipedia (en.wikipedia.org/wiki/Rijndael_S-box#Forward_S-box) page is equivalent. – ddddavidee Aug 11 '15 at 6:14
I think I got it. It was, actually, trivial. ;-) – ddddavidee Aug 13 '15 at 6:08
Maybe a litte bit late, can you elaborate on how bits are XOR'd against each other in one bit row? – Thomas Wagenaar Nov 15 '15 at 11:31
@ThomasWagenaar Bit 7 = 0 xor 0 xor 0 xor 1 xor 0 xor 0 xor 1 xor 1 = 1 – Richie Frame Nov 16 '15 at 6:24