python-aes-sbox-gf28-inverse

Answer

The S-box is S[x] = affine(ginv(x)). Two classic bugs are addressed explicitly:

1. Inverse of 0x00 — must be 0x00 (0 has no inverse; AES defines 0 → 0), never a division-by-zero or None.
2. Reduction overflow past degree 7 — when a byte's high bit (0x80) is set, a << 1 creates a degree-8 term. Reduce by XORing with 0x1B (x⁸ ≡ x⁴+x³+x+1 mod 0x11B) — and check the bit before shifting, or the reduction fires too late.

REDUC = 0x11B  # x^8 + x^4 + x^3 + x + 1

def gmul(a: int, b: int) -> int:
    """GF(2^8) multiply, reducing mod 0x11B."""
    p = 0
    while b:
        if b & 1:
            p ^= a
        b >>= 1
        hi = a & 0x80                 # degree-8 overflow about to happen
        a = (a << 1) & 0xFF
        if hi:
            a ^= 0x1B                 # x^8 == 0x1B (mod 0x11B)
    return p

def gpow(a: int, e: int) -> int:
    r, base = 1, a
    while e:
        if e & 1:
            r = gmul(r, base)
        base = gmul(base, base)
        e >>= 1
    return r

def ginv(a: int) -> int:
    """Multiplicative inverse; Fermat: a^254. 0x00 -> 0x00 (not div-by-zero)."""
    if a == 0:
        return 0
    return gpow(a, 254)   # a^(2^8 - 2)

def _rotl8(x: int, n: int) -> int:
    return ((x << n) | (x >> (8 - n))) & 0xFF

def affine(x: int) -> int:
    """b'_i = b_i ^ b_(i+4) ^ b_(i+5) ^ b_(i+6) ^ b_(i+7) ^ c_i, c = 0x63."""
    return (x ^ _rotl8(x, 1) ^ _rotl8(x, 2) ^ _rotl8(x, 3) ^ _rotl8(x, 4) ^ 0x63) & 0xFF

def sbox() -> list[int]:
    return [affine(ginv(b)) for b in range(256)]

The affine rotation trick: b' = b ^ rotl(b,1) ^ rotl(b,2) ^ rotl(b,3) ^ rotl(b,4) ^ 0x63, which implements the 8×8 circulant bit-matrix plus constant.