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?
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
The bit indexes for the matrix are
For the AES 0x1F affine matrix, the bits are arranged in the following way:
For an input of
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.
The final result LSB first is