Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
possible duplicate of Where is the S-Box generated in Rijandel/AES? –  e-sushi Oct 13 '13 at 1:03
1  
@e-sushi This does not answer the question at all. I want to know how the S-Box is generated, not how it's used or when it is constructed. –  ConditionRacer Oct 13 '13 at 1:17
1  
Then I misunderstood your question. If you're looking for the design decisions of the fixed S-Boxes and how Rijmen calculated them, I personally can only point you to "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
1  
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
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
    
Thank you so much, that was perfect. –  ConditionRacer Oct 13 '13 at 15:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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