# Generation of Rijndael S-box [duplicate]

I'm an electrical engineering student and was doing a brief research regarding the round transformations of the AES-128 and came across the Wikipedia article describing the generation of the substitution box (https://en.wikipedia.org/wiki/Rijndael_S-box) from the mathematical point of view. In the corresponding article it was explained that a given element of the extension field GF(2^8) is initially inverted with respect to x^8+x^4+x^3+x+1. Subsequently, the result (inverse element) is undergoing an affine transformation. The transformation itself is actually comprehensible. However, I do not understand the corresponding C-implementation at all. My naive approach to understand the below shown implementation was to think of the matrix multiplication as a linear combination of the columns of this matrix weighted with the bits of the inverse element. Since the columns of this matrix seem to be cyclicly shifted this could somehow explain the execution of ROTL8 in the affine transformation. In the end, the addition with 0x63 is actually quite clear.

#define ROTL8(x,shift) ((uint8_t) ((x) << (shift)) | ((x) >> (8 - (shift))))

void initialize_aes_sbox(uint8_t sbox[256]) {
uint8_t p = 1, q = 1;

/* loop invariant: p * q == 1 in the Galois field */
do {
/* multiply p by 3 */
p = p ^ (p << 1) ^ (p & 0x80 ? 0x11B : 0);

/* divide q by 3 (equals multiplication by 0xf6) */
q ^= q << 1;
q ^= q << 2;
q ^= q << 4;
q ^= q & 0x80 ? 0x09 : 0;

/* compute the affine transformation */
uint8_t xformed = q ^ ROTL8(q, 1) ^ ROTL8(q, 2) ^ ROTL8(q, 3) ^ ROTL8(q, 4);

sbox[p] = xformed ^ 0x63;
} while (p != 1);

/* 0 is a special case since it has no inverse */
sbox[0] = 0x63;
}


Would it be possible to explain how the matrix multiplication in the affine transformation can be interpreted as the addition (XOR) of the rotated terms (ROTL8) of the inverse element?

Best regards

Ratbald

• I've just searched 0x63 in this site and first hit crypto.stackexchange.com/q/40132/18298 Nov 19 '20 at 19:03
• It may be crucial to note here that the affine transformation isn't just a generic matrix-vector multiplication but rather one binary encoding of the actually intended operation which the standard defines as $$b_i'=b_i\oplus b_{(i+4)\bmod 8}\oplus b_{(i+5)\bmod 6}\oplus b_{(i+7)\bmod 8}$$ for all bits of a byte indexed by $i$.
– SEJPM
Nov 19 '20 at 19:14
• Crossposted with Stack Overflow stackoverflow.com/q/64916389/1820553 Nov 19 '20 at 21:25
• Does this answer your question? Need help understanding math behind Rijndael S-Box Nov 24 '20 at 8:37