17
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – e-sushi
    Oct 13, 2013 at 1:33
  • 1
    $\begingroup$ This is a partial (at least) answer to your question $\endgroup$
    – rath
    Oct 13, 2013 at 4:51
  • $\begingroup$ Page 50,51 of The Block Cipher Companion provide a clear explanation of how the S-box is designed $\endgroup$ Oct 18, 2013 at 10:46

1 Answer 1

17
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – ddddavidee
    Aug 11, 2015 at 6:14
  • $\begingroup$ I think I got it. It was, actually, trivial. ;-) $\endgroup$
    – ddddavidee
    Aug 13, 2015 at 6:08
  • $\begingroup$ Maybe a litte bit late, can you elaborate on how bits are XOR'd against each other in one bit row? $\endgroup$ Nov 15, 2015 at 11:31
  • 1
    $\begingroup$ @ThomasWagenaar Bit 7 = 0 xor 0 xor 0 xor 1 xor 0 xor 0 xor 1 xor 1 = 1 $\endgroup$ Nov 16, 2015 at 6:24
  • $\begingroup$ How did you get the inverse of 0x53? I'm finding that 0x53 doesn't have any inverse $\endgroup$
    – user38956
    Mar 28, 2017 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.