03d-aes-sbox-construction.ipynb

Kernel: SageMath 10.5

AES S-box Construction

Module 03d | Galois Fields and AES

Field inverse + affine transform = the most important lookup table in cryptography.

Question: The AES S-box maps each byte to another byte, a simple 256-entry table. But it's not random. It's constructed from exactly two mathematical operations: (1) take the multiplicative inverse in GF(256), and (2) apply an affine map over GF(2). Why these two steps? What properties do they give the S-box that a random table wouldn't?

By the end of this notebook, you'll build the S-box from scratch and understand why it resists both linear and differential cryptanalysis.

Objectives

By the end of this notebook you will be able to:

1. Compute the GF(256) multiplicative inverse of any byte

2. Apply the AES affine transformation as a matrix-vector product over GF(2)

3. Construct the complete 256-entry AES S-box from first principles

4. Verify your S-box matches the official AES specification

5. Explain why the S-box provides nonlinearity and high algebraic degree

Bridge from 03c

In 03c you built GF(256) arithmetic: addition (XOR), multiplication (polynomial product mod $m(x)$), and inversion. You also built the complete 256-byte inverse table.

The S-box takes this inverse table and applies one more transformation, an affine map, to break the algebraic structure and create the nonlinearity that AES needs.

Setup: GF(256) with the AES Polynomial

# Setup: GF(256) and conversion utilities (from 03c)
R.<x> = GF(2)[]
F.<a> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)

def byte_to_gf256(b):
    return sum(GF(2)((b >> i) & 1) * a^i for i in range(8))

def gf256_to_byte(elem):
    p = elem.polynomial()
    return sum(int(p[i]) << i for i in range(8))

def byte_to_bits(b):
    """Convert byte to GF(2) column vector (LSB first)."""
    return vector(GF(2), [(b >> i) & 1 for i in range(8)])

def bits_to_byte(v):
    """Convert GF(2) vector back to byte."""
    return sum(int(v[i]) << i for i in range(8))

print('GF(256) ready. Conversion utilities loaded.')

Step 1: The Multiplicative Inverse

The first step of the S-box maps each byte $b$ to its multiplicative inverse $b^{-1}$ in GF(256). By convention, $0 \mapsto 0$ (since 0 has no inverse).

Why the inverse? Because it provides maximum nonlinearity, the inverse function over GF($2^n$) achieves the theoretical best nonlinearity score among all power maps.

# Step 1: Multiplicative inverse table
inv_table = [0] * 256
for b in range(1, 256):
    inv_table[b] = gf256_to_byte(byte_to_gf256(b)^(-1))

# Display
print('GF(256) Inverse Table (first step of S-box):')
print('     ', end='')
for j in range(16):
    print(f' .{j:X}', end='')
print()
print('    ' + '-' * 52)
for i in range(16):
    print(f' {i:X}. |', end='')
    for j in range(16):
        print(f' {inv_table[i*16+j]:02X}', end='')
    print()

print()
print('Problem: the inverse alone has too much algebraic structure.')
print('It satisfies x * inv(x) = 1, an algebraic relation an attacker could exploit.')
print('We need to break this structure with a non-algebraic transformation.')

Step 2: The Affine Transformation

After inverting, AES applies an affine map over GF(2). This is a matrix multiplication plus a constant vector:

$$\texttt{S-box}(b) = A \cdot b^{-1} + c$$

where $A$ is a specific $8 \times 8$ matrix over GF(2) and $c$ is the constant vector 0x63.

Why this specific matrix and constant? The designers of AES (Daemen and Rijmen) chose $A$ and $c$ to satisfy three constraints simultaneously:

1. Invertibility, $A$ must be invertible over GF(2) so that decryption can undo the affine step via $A^{-1}$.

2. Circulant structure, each row is a rotation of the first row. This means the transformation can be implemented as a fixed bit-rotation + XOR pattern, which is extremely efficient in hardware.

3. Resistance to known attacks, the combination of $A$ and $c = \texttt{0x63}$ was chosen so the full S-box has no fixed points ($S(b) \neq b$), no "opposite" fixed points ($S(b) \neq \bar{b}$), and maximum nonlinearity among circulant affine maps.

The constant $c = \texttt{0x63}$ breaks the symmetry $S(0) = 0$ that the inverse alone would give (since $0 \mapsto 0$ under inversion), ensuring the S-box has no zero fixed point.

The matrix $A$ is a circulant matrix based on the polynomial $x^4 + x^3 + x^2 + x + 1$ (= 0x1F):

# The AES affine transformation matrix (over GF(2))
A = matrix(GF(2), [
    [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]
])

# The constant vector c = 0x63 = 01100011
c = byte_to_bits(0x63)

print('Affine transformation matrix A:')
print(A)
print()
print(f'Constant vector c = 0x63 = {c}')
print()
print(f'A is invertible? {A.is_invertible()}')
print(f'det(A) = {A.det()}')
print()
print('The affine map is: S(b) = A * inv(b) + c')
print('where inv(b) and the result are both 8-bit vectors over GF(2).')

Checkpoint: Why does $A$ need to be invertible? Because AES must be decryptable. The inverse S-box uses $A^{-1}$ to undo the affine step: $b^{-1} = A^{-1} \cdot (\texttt{S-box}(b) + c)$.

Building the Complete S-box

# Build the AES S-box from scratch
sbox = [0] * 256

for b in range(256):
    # Step 1: Multiplicative inverse in GF(256)
    if b == 0:
        inv_bits = byte_to_bits(0)
    else:
        inv_byte = gf256_to_byte(byte_to_gf256(b)^(-1))
        inv_bits = byte_to_bits(inv_byte)
    
    # Step 2: Affine transformation
    result_bits = A * inv_bits + c
    sbox[b] = bits_to_byte(result_bits)

# Display the S-box as a 16×16 grid
print('AES S-box (built from first principles):')
print()
print('     ', end='')
for j in range(16):
    print(f' .{j:X}', end='')
print()
print('    ' + '-' * 52)
for i in range(16):
    print(f' {i:X}. |', end='')
    for j in range(16):
        print(f' {sbox[i*16+j]:02X}', end='')
    print()

Verification Against the Official S-box

Let's verify our construction matches the AES specification (FIPS 197):

# Official AES S-box from FIPS 197
official_sbox = [
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16
]

# Compare
match = sbox == official_sbox
mismatches = sum(1 for i in range(256) if sbox[i] != official_sbox[i])
print(f'Our S-box matches FIPS 197? {match}')
print(f'Mismatches: {mismatches} / 256')
print()

# Spot checks
for b in [0x00, 0x01, 0x53, 0xFF]:
    print(f'S-box[0x{b:02X}] = 0x{sbox[b]:02X}  (official: 0x{official_sbox[b]:02X})')

Why Both Steps Are Needed

Common mistake: "The inverse alone would be a fine S-box." No! The inverse is a power map ($b \mapsto b^{254}$), which means it satisfies algebraic equations over GF(256). Algebraic attacks (like XL and Gröbner basis methods) can exploit this. The affine step breaks the pure algebraic structure.

Conversely, an affine map alone would be linear, trivially breakable. You need both: the inverse for nonlinearity, and the affine map to disrupt algebraic relations.

# Demonstrating why both steps matter

# Property 1: The S-box is a bijection (permutation)
print('=== S-box is a bijection ===')
print(f'Distinct output values: {len(set(sbox))}')
print(f'Expected (if bijection): 256')
print()

# Property 2: No fixed points S(b) = b
fixed = [b for b in range(256) if sbox[b] == b]
print(f'Fixed points (S(b) = b): {len(fixed)}')
# Also check: no "opposite" fixed points S(b) = ~b
opp_fixed = [b for b in range(256) if sbox[b] == b ^^ 0xFF]
print(f'Complement fixed points (S(b) = ~b): {len(opp_fixed)}')
print()

# Property 3: Nonlinearity
# The nonlinearity is the minimum Hamming distance from any affine function
# For an 8-bit S-box, maximum possible nonlinearity is 120; AES achieves 112
print('=== Nonlinearity ===')
print('Computing Walsh spectrum (may take a moment)...')

max_walsh = 0
for a_mask in range(1, 256):  # output mask
    for b_mask in range(256):  # input mask
        walsh_sum = 0
        for x in range(256):
            in_bit = bin(x & b_mask).count('1') % 2
            out_bit = bin(sbox[x] & a_mask).count('1') % 2
            walsh_sum += (-1)^(in_bit ^^ out_bit)
        max_walsh = max(max_walsh, abs(walsh_sum))

nonlinearity = (256 - max_walsh) // 2
print(f'Nonlinearity: {nonlinearity}')
print(f'Maximum possible for 8-bit: 120')
print(f'AES achieves {nonlinearity}/120, very close to optimal.')

The Inverse S-box

For decryption, AES needs the inverse S-box: $\texttt{InvSbox}(y) = (A^{-1}(y + c))^{-1}$.

# Build the inverse S-box
inv_sbox = [0] * 256
for b in range(256):
    inv_sbox[sbox[b]] = b

# Verify it's truly the inverse
roundtrip = all(inv_sbox[sbox[b]] == b for b in range(256))
print(f'InvSbox(Sbox(b)) = b for all b? {roundtrip}')
print()

# Display
print('Inverse S-box:')
print('     ', end='')
for j in range(16):
    print(f' .{j:X}', end='')
print()
print('    ' + '-' * 52)
for i in range(16):
    print(f' {i:X}. |', end='')
    for j in range(16):
        print(f' {inv_sbox[i*16+j]:02X}', end='')
    print()

print()
# Verify using the formula: A^(-1) * (y + c), then GF(256) inverse
A_inv = A.inverse()
for test_b in [0x00, 0x53, 0xCA]:
    y = sbox[test_b]
    y_bits = byte_to_bits(y)
    undo_affine = A_inv * (y_bits + c)
    undo_byte = bits_to_byte(undo_affine)
    if undo_byte == 0:
        recovered = 0
    else:
        recovered = gf256_to_byte(byte_to_gf256(undo_byte)^(-1))
    print(f'InvSbox(0x{y:02X}) = 0x{recovered:02X}  (expected 0x{test_b:02X})')

Checkpoint: The S-box and inverse S-box are both permutations of $\{0, \ldots, 255\}$. If you compose them, apply S-box then inverse S-box, you get the identity. This is essential for AES decryption to work correctly.

Exercises

Exercise 1 (Worked)

Compute S-box(0x53) by hand, showing both the inverse step and the affine step.

# Exercise 1 (Worked), S-box(0x53) step by step
b = 0x53
print(f'Computing S-box(0x{b:02X}):')
print()

# Step 1: Multiplicative inverse in GF(256)
inv_elem = byte_to_gf256(b)^(-1)
inv_byte = gf256_to_byte(inv_elem)
print(f'Step 1: 0x{b:02X}^(-1) in GF(256) = 0x{inv_byte:02X}')
print(f'  Verify: 0x{b:02X} × 0x{inv_byte:02X} = 0x{gf256_to_byte(byte_to_gf256(b) * inv_elem):02X}')
print()

# Step 2: Affine transformation
inv_bits = byte_to_bits(inv_byte)
print(f'Step 2: Apply affine map A * inv + c')
print(f'  inv as bits: {inv_bits}')
result_bits = A * inv_bits + c
result = bits_to_byte(result_bits)
print(f'  A * inv:     {A * inv_bits}')
print(f'  + c (0x63):  {result_bits}')
print(f'  = 0x{result:02X}')
print()

print(f'S-box(0x{b:02X}) = 0x{result:02X}')
print(f'Official:      0x{official_sbox[b]:02X}')
print(f'Match: {result == official_sbox[b]}')

Exercise 2 (Guided)

Build the inverse S-box using the formula $\texttt{InvSbox}(y) = (A^{-1}(y \oplus c))^{-1}$ (not by inverting the forward table). Verify it matches.

# Exercise 2 (Guided), Build inverse S-box from formula
A_inv = A.inverse()

inv_sbox_formula = [0] * 256
for y in range(256):
    # TODO: Step 1 - undo affine: apply A^(-1) * (y_bits + c)
    y_bits = byte_to_bits(y)
    # Hint: undo_bits = A_inv * (y_bits + c)
    undo_bits = None  # TODO
    undo_byte = 0  # TODO: bits_to_byte(undo_bits)
    
    # TODO: Step 2 - take GF(256) inverse (handle 0 specially)
    # Hint: if undo_byte == 0 then result = 0, else ...
    inv_sbox_formula[y] = 0  # TODO

# Verify against the table-inversion method
# match = inv_sbox_formula == inv_sbox
# print(f'Formula matches table inversion? {match}')

Exercise 3 (Independent)

1. The AES S-box has no fixed points ($S(b) \neq b$ for all $b$). Verify this. Is this property guaranteed by the construction, or is it a coincidence of the specific matrix $A$ and constant $c$?

2. Construct an alternative S-box using a different affine constant $c' = \texttt{0x05}$ instead of $\texttt{0x63}$. Does it still have no fixed points? What is its nonlinearity?

3. What happens if you skip the affine step entirely and use only the inverse as the S-box? Count fixed points and compute the algebraic degree. (Hint: the algebraic degree of $x^{254}$ over GF($2^8$) is 7, while the full S-box has degree 7 too, but the affine step changes which degree-7 polynomial it is.)

# Exercise 3 (Independent), Your code here

Summary

Concept	Key idea
S-box construction	GF(256) multiplicative inverse followed by an affine transformation over GF(2)
Inverse provides nonlinearity	The field inverse achieves near-optimal nonlinearity (112/120), resisting linear and differential attacks
Affine map breaks algebraic structure	Without it, the pure inverse satisfies exploitable algebraic equations. The affine step disrupts these relations
No fixed points	$S(b) \neq b$ and $S(b) \neq \bar{b}$ for all $b$, thanks to the specific choice of matrix $A$ and constant $c = \texttt{0x63}$
Bijection	The S-box is a permutation of all 256 bytes, essential for AES decryption to work
Inverse S-box	Uses $A^{-1}$ to undo the affine step, then takes the GF(256) inverse again

Crypto foreshadowing: The S-box is SubBytes, just one of four AES round operations. In notebook 03e, we'll see MixColumns, which uses matrix multiplication over GF(256). The interplay between SubBytes (nonlinear, byte-level) and MixColumns (linear, column-level) is what makes AES secure.

Next: AES MixColumns as Field Ops, matrix multiplication over GF(256).