How does this code calculating AES S-Box work?

Question

How does this code calculating the AES S-Box work? I don't understand the overall calculation procedure. Code is attached below:

function generate(irreducible_poly){
    try{
        p = parseInt(eval(irreducible_poly.replace(/x/g, '10')), 2);
    } catch(err){
        console.log('Irreducible Polynomial invalid');
        return;
    }

    let t = new Uint32Array(256);
    for (let i = 0, x = 1; i < 256; i ++) {
        t[i] = x;
        x ^= (x << 1) ^ ((x >>> 7) * p);
    }

    let Sbox = new Uint32Array(256);
    Sbox[0] = 0x63;
    for (let i = 0; i < 255; i ++) {
        let x = t[255 - i];
        x |= x << 8;
        x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
        Sbox[t[i]] = (x ^ 0x63) & 0xFF;
    }

    return Sbox;
}


// Inverse of Sbox
function inverse(sbox){
    let InvSbox = new Uint32Array(256);
    for (let i =0; i < 256; i++){
        InvSbox[i] = sbox.indexOf(i);
    }

    return InvSbox;
}

Answer 1

Big picture: this code needs to compute the inverse modulo binary irreducible polynomial $P$ of every non-zero binary polynomial $R$ of degree less than that of $P$. Towards this, it has selected a generating polynomial $G=1+x$, and tabulates $Q_i=G^i\bmod P$, which reaches all the desired $R$. The multiplicative inverse of $R=Q_i$ is $Q_{255-i}$.

---

This code evaluates the AES S-box and it's inverse as follows:

1. (code block starting in try) It evaluates p = 0x11b = 283 that represents the binary polynomial $P=1+x+x^3+x^4+x^8$ as an integer: the value obtained when evaluating this polynomial for integer $x=2$. This common convention is used in AES to map binary polynomials to integers.

2. (code block starting in let t) It computes table t[i] representing the binary polynomial $Q_i=(1+x)^i\bmod P$ per this convention. That $Q_i$ is computed per the recurrence $Q_{i+1}=Q_i\,(1+x)\bmod P$ with $Q_0=1$, translating¹ to t[i+1] = t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p)) with t[0] = 1 under said convention.

   For example: $Q_0$ is the (binary) polynomial $1$, represented by t[0] = 1. $Q_1=1+x$, represented by t[1] = 3. $Q_2=(1+x)^2=1+x^2$, represented by t[2] = 5. $Q_7=(1+x)^7=1+x+x^2+x^3+x^4+x^5+x^6+x^7$, represented by t[2] = 0xff = 255. $Q_8=(1+x)^8\bmod P=(1+x^8)\bmod P=x+x^3+x^4$, represented by t[8] = 0x1a = 26.

3. (code block starting in let Sbox) Tabulating $Q_i=(1+x)^i\bmod P$ was useful because $(1+x)^{255}\bmod P=1$, therefore $Q_{255-i}$ is the multiplicative inverse of $Q_i$. And $Q_i$ reaches all non-zero binary polynomials of degree $<8$ (that is $1+x$ is a generator). Therefore integer t[255 - i] represents the multiplicative inverse of the polynomial that integer t[i] represents. And when in the loop i goes from 0 to 254 that yields the multiplicative inverse of each of the 255 non-zero polynomials of degree $<8$. The loop then merely applies² the affine transformation specified in the rest of the definition of the AES S-box. The zero polynomial is special-cased.

   For example: when in the loop i = 8, t[i] is t[8] = 0x1a = 26 representing $Q_8=x+x^3+x^4$, and t[255-i] (going to x, unrelated to $x$) is t[247] = 0xfd = 253 representing the polynomial $Q_{247}=1+x^2+x^3+x^4+x^5+x^6+x^7$. That $Q_{247}$ is the multiplicative inverse of $Q_8$. By the definition of the AES S-box, there only remains to apply the affine transformation² to x, then set the result in Sbox[t[i]] = Sbox[26].

4. (function inverse) The inverse table is computed by searching each entry in the table. That works but is inefficient. InvSbox[i] = sbox.indexOf(i); could be replaced by the straightforward and more efficient InvSbox[sbox[i]] = i;.

---

¹ Justification: in t[i+1] = t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p))

• t[i] is an integer in $[0,2^8)$ and represents $Q_i$ of degree $<8$
• t[i] << 1 is an even integer in $[0,2^9)$ and represents $Q_i\,x$.
• t[i] >>> 7 is either 0 or 1. It's the coefficient of the term of order $x^7$ in $Q_i$.
• (t[i] >>> 7) * p is correspondingly either 0 or 0x11b = 283, representing $0$ or $P$.
• (t[i] << 1) ^ ((t[i] >>> 7) * p) correspondingly represents $(Q_i\,x)$ or $(Q_i\,x)+P$, and (by examination of the two cases) is an integer in $[0,2^8)$, thus represents a binary polynomial of degree $<8$, which thus is $(Q_i\,x)\bmod P$.
• t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p)) is thus an integer in $[0,2^8)$ and represents $Q_i+(Q_i\,x)\bmod P)=Q_i\,(1+x)\bmod P=Q_{i+1}$, of degree $<8$.

In C, the standard likely-constant-time idiom for this expression would be (essentially with & - used instead of multiplication):
t[i+1] = t[i] ^ ((t[i] << 1) ^ (p & -(t[i] >> 7))).
Note: some overzealous C compilers will wrongly bark at the -, silence them.

---

² The statement x |= x << 8;duplicates the bits in variable x (representing the modular inverse of $Q_i$) so that subsequent right shifts become equivalent to rotation when it comes to the low-order 8 bits. The statement x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7); implements the circulant matrix multiplication. Then ^ 0x63 (representing polynomial $1+x+x^5+x^6$) is the constant addition, and & 0xFF keeps the low-order 8 bits (terms of degree $<8$), undoing the duplication.