Need help understanding math behind Rijndael S-Box

Question

in Rijndael SubBytes() step all bytes of input block are substituted based on a lookup table S-Box. S-Box is initialized by taking all elements of $GF(2^8)$, calculating their multiplicative inverse and then calculating their affine transform.

Here is C code which does that as found on wikipedia page.

#include <stdint.h>

#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 ? 0x1B : 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;
}

I cant wrap my head around how multiplicative inverse is being calculated here. I assume p here acts as input while q is its inverse. Hence $p*q = 1$.

I want to understand how exactly this works because I am trying to implement a function that initializes Rijndael inverse S-Box, where first the inverse affine transform is calculated and then the multiplicative inverse.

Answer 1

The code is using the fact that the Rijndael's^* Galois field has the following generators^†:

3 5 6 9 11 14 17 18 19 20 23 24 25 26 28 30 31 33 34 35 39 40 42 44 48 49 60 62 63 65 69 70 71 72 73 75 76 78 79 82 84 86 87 88 89 90 91 95 100 101 104 105 109 110 112 113 118 119 121 122 123 126 129 132 134 135 136 138 142 143 144 147 149 150 152 153 155 157 160 164 165 166 167 169 170 172 173 178 180 183 184 185 186 190 191 192 193 196 200 201 206 207 208 214 215 218 220 221 222 226 227 229 230 231 233 234 235 238 240 241 244 245 246 248 251 253 254 255

A multiplicative generator $g$ means that $\langle g \rangle$ generates all of the element of $\operatorname{GF}(2^8) \text{ - } \{0\}$ or equivalently, $\mathbb{F}_{2^8}^*$. More formally, they form the cyclic multiplicative group of the finite field. The zero case handled at the end.

The choice of 3 in the code

/* multiply p by 3 */
p = p ^ (p << 1) ^ (p & 0x80 ? 0x1B : 0); 

is simply due to the optimization that 3 enables the smallest calculations to generate all of the elements. The 3 is actually a numerical expression of $x+1 \in \operatorname{GF}(2^8)$ in polynomial representation. Therefore, the above code is the multiplication of the current $p$ with $x+1$ as p ^ (p << 1). The ^ (p & 0x80 ? 0x1B : 0) part is the reduction with the primitive polynomial of the field by the equality $x^8 = x^4 + x^3 + x + 1$, in hex 0x1B where $x^8 + x^4 + x^3 + x + 1$ is the irreducable AES polynomial to that used to extend $\operatorname{GF}(2)$ to $\operatorname{GF}(2^8)$

The code is also using the fact that ;

$$1 = pq=pq \cdot 3 \cdot 3^{−1}=3p \cdot 3^{−1}q=1$$ now call $p′=3p$ and $q′ = 3^{−1}q$ and get $p′q′=1$. In this way, $p$ and $q$ get all valus of the table - expect 0 - since 3 is a generator. Then, by using the $q$, the affine transformation is computed for the table.

What is the advantage here?

• No need to find the inverse by using the Ext-GCD or its better versions.
• No multiplication is used for generating the elements.

---

_{^* Rijndael $\neq$ AES (Actually, Rijndael $\supseteq$ AES). Rijndael is an AES candidate that won the competition and standardized as AES. The Rijndael is designed for 128, 192, or 256 key and block sizes. The AES has fixed block size 128 and have the 128, 192, or 256 bits key sizes.}

_{^† SageMath code to find all of those generators. Need sorting.}

R.<x> = PolynomialRing(GF(2), 'x')
S.<y> = GF(2^8, modulus=x^8+x^4+x^3+x+1, repr='int')   

for i,x in enumerate(S):
    if x == 0:
        continue
    if x.multiplicative_order() == 255:
        print("{} {}".format(i, x))

Answer 2

The AES field is $GF(2^8)$ where each element has a representation as a polynomial of degree at most $7$ with coefficient in $GF(2)$, and every calculation is done modulo $x^8 + x^4 + x^3 + x + 1$.

The multiplicate group of $GF(2^8)$ has $255$ elements, and the element $x+1$ generates the whole group, and is the element of smallest degree with this characteristic: basically, every element (except $0$) can be written as a power of $x+1$. For instance, we have $x^2 + x + 1 = (x + 1)^{198}$.

The inverse of $x + 1$ happens to be $x^7 + x^6 + x^5 + x^4 + x^2 + x$. You might notice the relation of these elements in the source code, the coefficients of $x + 1$ can be represented with 11 in binary, and 3 in hexadecimal. Its inverse has the binary representation 11110110 or f6 in hexadecimal.

Putting everything together, the operations in the loop become clearer. The value $p$ is initialized at $1$, and $q$ to the inverse of $1$. Then, the first two parts of the loop multiply $p$ by $x+1$ and $q$ by $(x+1)^{-1}$. The affine transformation is applied on $q$ and stored in the S-BOX for the corresponding value $p$. This is correct, since as you stated, the invariant $p\cdot q = 1$ assures that $q$ is always the inverse of $p$.

Since $(x+1)^n$ will run through all elements (except $0$) for $n$ from $1$ to $255$, then no element will be ommitted. The loop will stop at $(x+1)^{255} = 1$ after the corresponding calculation.

The special case of $0$ is done outside the loop since it has no inverse.