03c-gf256-arithmetic.ipynb

Kernel: SageMath 10.5

GF(256) Arithmetic

Module 03c | Galois Fields and AES

The field inside every AES byte.

Question: A single AES byte, say 0x53, is simultaneously an integer (83), a bit-string (01010011), and a polynomial ($x^6 + x^4 + x + 1$). You can XOR two bytes (addition), but can you multiply them? Divide them? Invert them?

Yes, because bytes live in GF(256), a field. In this notebook, you'll do arithmetic with bytes the way AES does.

Objectives

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

1. Construct GF(256) using the AES irreducible polynomial

2. Convert between bytes, bit-strings, and GF(256) polynomials

3. Perform addition (XOR), multiplication, and inversion in GF(256)

4. Build xtime, the fundamental multiplication-by-$x$ operation

5. Understand why GF(256) is the right choice for a byte-oriented cipher

Bridge from 03b

In 03b you built GF($2^n$) for small $n$ (2, 3, 4). Now we go to $n = 8$: GF($2^8$) = GF(256). The construction is identical, quotient GF(2)$[x]$ by an irreducible polynomial of degree 8, but the specific polynomial is chosen by the AES standard:

$$m(x) = x^8 + x^4 + x^3 + x + 1$$

This polynomial is irreducible over GF(2) and has the hex representation 0x11B.

The AES Field: GF(256)

# The AES irreducible polynomial
R.<x> = GF(2)[]
aes_mod = x^8 + x^4 + x^3 + x + 1
print(f'AES modulus: {aes_mod}')
print(f'Irreducible? {aes_mod.is_irreducible()}')
print(f'Hex: 0x11B (bit 8 + bit 4 + bit 3 + bit 1 + bit 0 = 100011011)')
print()

# Construct GF(256)
F.<a> = GF(2^8, modulus=aes_mod)
print(f'Field: {F}')
print(f'Order: {F.order()} elements')
print(f'Modulus: {F.modulus()}')
print(f'Is a field? {F in Fields()}')
print()
print('Each element is a polynomial of degree <= 7 with GF(2) coefficients.')
print('That is: 8 bits = 1 byte. GF(256) elements ARE bytes.')

Byte ↔ Polynomial Conversion

Every byte (0x00 to 0xFF) corresponds to a unique element of GF(256). The bit representation is read as polynomial coefficients:

F.<a> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)

def byte_to_gf256(byte_val):
    """Convert a byte (0-255) to a GF(256) element."""
    return sum(GF(2)((byte_val >> i) & 1) * a^i for i in range(8))

def gf256_to_byte(elem):
    """Convert a GF(256) element to a byte (0-255)."""
    p = elem.polynomial()
    return sum(int(p[i]) << i for i in range(8))

# Examples
test_bytes = [0x00, 0x01, 0x02, 0x53, 0x83, 0xFF]
print('Byte Binary Polynomial Back')for b in test_bytes:
    elem = byte_to_gf256(b)
    back = gf256_to_byte(elem)
    print(f'  0x{b:02X}  {b:08b}  {str(elem)}  0x{back:02X}')

print()
print('The conversion is a perfect bijection: 256 bytes ↔ 256 field elements.')

Addition: XOR

Addition in GF(256) is polynomial addition with GF(2) coefficients. Since each coefficient is a bit, this is bitwise XOR, exactly as in 03a, but now with 8-bit vectors.

# Addition = XOR
F.<a> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)

p = byte_to_gf256(0x53)  # 01010011 = x^6 + x^4 + x + 1
q = byte_to_gf256(0xCA)  # 11001010 = x^7 + x^6 + x^3 + x

result = p + q
result_byte = gf256_to_byte(result)

print(f'0x53 = {p}')
print(f'0xCA = {q}')
print(f'Sum  = {result}')
print(f'     = 0x{result_byte:02X}')
print()
print(f'Verify with XOR: 0x53 ^ 0xCA = 0x{0x53 ^^ 0xCA:02X}')
print()
print('Key properties of GF(256) addition:')
print(f'  Self-inverse: 0x53 + 0x53 = 0x{gf256_to_byte(p + p):02X} (always 0)')
print(f'  So subtraction = addition = XOR (just like in GF(2))')

Multiplication: Polynomial Product mod $m(x)$

Multiplication is where GF(256) gets interesting. You multiply the polynomials, then reduce modulo the AES polynomial $m(x) = x^8 + x^4 + x^3 + x + 1$.

Checkpoint: Multiply 0x53 × 0xCA in GF(256). This is NOT integer multiplication (83 × 202 = 16766). It's polynomial multiplication reduced mod $m(x)$. Predict: will the result be larger or smaller than the inputs?

# Multiplication in GF(256)
F.<a> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)

p = byte_to_gf256(0x53)
q = byte_to_gf256(0xCA)

product = p * q
product_byte = gf256_to_byte(product)

print(f'0x53 × 0xCA in GF(256):')
print(f'  ({p}) × ({q})')
print(f'  = {product}')
print(f'  = 0x{product_byte:02X}')
print()

# Show the unreduced product for comparison
R2.<y> = GF(2)[]
p_poly = sum(GF(2)((0x53 >> i) & 1) * y^i for i in range(8))
q_poly = sum(GF(2)((0xCA >> i) & 1) * y^i for i in range(8))
unreduced = p_poly * q_poly
aes_m = y^8 + y^4 + y^3 + y + 1
reduced = unreduced % aes_m

print(f'Step by step:')
print(f'  Unreduced product: {unreduced}  (degree {unreduced.degree()})')
print(f'  Mod {aes_m}: {reduced}  (degree <= 7, fits in a byte)')

The xtime Operation

Multiplication by $x$ (= 0x02) is the fundamental building block. AES calls it xtime. Every GF(256) multiplication can be built from repeated xtime and XOR.

$$\texttt{xtime}(b) = \begin{cases} b \ll 1 & \text{if high bit is 0} \\ (b \ll 1) \oplus \texttt{0x1B} & \text{if high bit is 1} \end{cases}$$

The 0x1B comes from the AES polynomial: $x^8 \bmod m(x) = x^4 + x^3 + x + 1 = \texttt{0x1B}$.

# xtime: multiply by x in GF(256)
def xtime(b):
    """Multiply byte b by 0x02 in GF(256)."""
    result = b << 1  # shift left = multiply by x
    if result & 0x100:  # if degree >= 8, reduce
        result ^^= 0x11B  # XOR with m(x) = x^8 + x^4 + x^3 + x + 1
    return result & 0xFF

# Verify xtime against SageMath
F.<a> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)
two = byte_to_gf256(0x02)

print('xtime verification (multiply by 0x02):')
print('Input xtime SageMath Match')test_vals = [0x01, 0x02, 0x04, 0x53, 0x80, 0xCA, 0xFF]
for b in test_vals:
    xt = xtime(b)
    sage_result = gf256_to_byte(byte_to_gf256(b) * two)
    print(f'  0x{b:02X}    0x{xt:02X}    0x{sage_result:02X}    {"✓" if xt == sage_result else "✗"}')

print()
print('Notice: xtime(0x80) involves reduction because 0x80 = x^7,')
print('and x^7 * x = x^8, which exceeds degree 7.')
print(f'  x^8 mod m(x) = x^4 + x^3 + x + 1 = 0x{0x1B:02X}')

General Multiplication via xtime

To multiply by an arbitrary byte, use the "Russian peasant" method: decompose one factor into powers of 2 and accumulate with xtime.

# General GF(256) multiplication using xtime
def gf256_mul(a, b):
    """Multiply bytes a and b in GF(256) using xtime."""
    result = 0
    temp = a
    for i in range(8):
        if b & (1 << i):
            result ^^= temp
        temp = xtime(temp)
    return result

# Verify against SageMath for several pairs
F.<a> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)

pairs = [(0x53, 0xCA), (0x02, 0x87), (0x03, 0x6E), (0x57, 0x13), (0xFF, 0xFF)]
print('A B gf_mul Sage Match')for p, q in pairs:
    ours = gf256_mul(p, q)
    sage_val = gf256_to_byte(byte_to_gf256(p) * byte_to_gf256(q))
    print(f'  0x{p:02X}  0x{q:02X}    0x{ours:02X}    0x{sage_val:02X}    {"✓" if ours == sage_val else "✗"}')

print()
print('This is exactly how AES implements multiplication in hardware/software:')
print('no big-integer arithmetic needed, just shifts and XORs.')

Multiplicative Inverse

Every nonzero byte has a unique multiplicative inverse in GF(256). This is the core of the AES S-box (notebook 03d).

Checkpoint: What is the inverse of 0x53 in GF(256)? It's the byte $b$ such that 0x53 × $b$ = 0x01. You can find it via the extended Euclidean algorithm (Module 04) or by Fermat's little theorem: $b^{-1} = b^{254}$ since $|\text{GF}(256)^*| = 255$.

# Multiplicative inverses in GF(256)
F.<a> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)

# Method 1: SageMath's built-in inverse
elem = byte_to_gf256(0x53)
inv = elem^(-1)
inv_byte = gf256_to_byte(inv)
print(f'0x53 inverse: 0x{inv_byte:02X}')
print(f'Check: 0x53 × 0x{inv_byte:02X} = 0x{gf256_to_byte(elem * inv):02X}')
print()

# Method 2: Fermat's little theorem (b^(-1) = b^254)
def gf256_inv_fermat(b):
    """Inverse via b^254 = b^(-1) in GF(256)."""
    if b == 0:
        return 0  # convention: 0 maps to 0 in AES
    result = b
    for _ in range(253):  # b^254 = b * b * ... * b (254 times)
        result = gf256_mul(result, b)
    return result

# Verify for several bytes
print('Inverse table (selected bytes):')
print('Byte Inv Product')for b in [0x01, 0x02, 0x03, 0x53, 0xCA, 0xFF]:
    inv_b = gf256_inv_fermat(b)
    prod = gf256_mul(b, inv_b)
    print(f'  0x{b:02X}  0x{inv_b:02X}    0x{prod:02X}')

print()
print('Every nonzero byte has an inverse, and b × b^(-1) = 0x01 always.')

The Full Inverse Table

Let's build the complete 256-byte inverse table, this is the first step of the AES S-box construction.

# Build the complete GF(256) inverse table
F.<a> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)

inv_table = [0] * 256  # 0 maps to 0 by convention
for b in range(1, 256):
    elem = byte_to_gf256(b)
    inv_table[b] = gf256_to_byte(elem^(-1))

# Display as a 16×16 grid (like the AES spec)
print('GF(256) Inverse Table (row = high nibble, col = low nibble):')
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' {inv_table[i*16+j]:02X}', end='')
    print()

print()
# Verify: inv(inv(b)) = b for all b
double_inv_ok = all(inv_table[inv_table[b]] == b for b in range(1, 256))
print(f'inv(inv(b)) = b for all nonzero b? {double_inv_ok}')
print('(The inverse is an involution on GF(256)*)')

Common mistake: "GF(256) multiplication is just regular multiplication mod 256." Absolutely not. Regular multiplication mod 256 produces zero divisors (e.g., $16 \times 16 = 256 \equiv 0$). GF(256) multiplication uses polynomial arithmetic mod an irreducible polynomial, no zero divisors, every nonzero element is invertible. That's what makes it a field, and that's why AES uses it.

The Generator and Multiplicative Group

# The multiplicative group of GF(256)
F.<a> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)

# 0x03 is a generator of GF(256)*
g = byte_to_gf256(0x03)
print(f'Generator g = 0x03 = {g}')
print(f'Order of g: {g.multiplicative_order()}')
print(f'GF(256)* has order {F.order() - 1} = 255')
print()

# Build exp and log tables
exp_table = [0] * 256
log_table = [None] * 256
power = F(1)
for i in range(255):
    b = gf256_to_byte(power)
    exp_table[i] = b
    log_table[b] = i
    power *= g
exp_table[255] = exp_table[0]  # wrap around

print('First 16 powers of 0x03:')
for i in range(16):
    print(f'  0x03^{i:3d} = 0x{exp_table[i]:02X}')
print('  ...')
print(f'  0x03^254 = 0x{exp_table[254]:02X}')
print(f'  0x03^255 = 0x{exp_table[255]:02X} (wraps to 0x03^0)')
print()
print('With exp/log tables, multiplication becomes:')
print('  a × b = exp[log[a] + log[b] mod 255]')
print('This is how fast AES implementations work.')

Exercises

Exercise 1 (Worked)

Multiply 0x57 × 0x83 in GF(256) using xtime, showing each step. Verify with SageMath.

# Exercise 1 (Worked), Step-by-step GF(256) multiplication
a_val = 0x57
b_val = 0x83  # binary: 10000011 = 2^7 + 2^1 + 2^0

print(f'Multiply 0x{a_val:02X} × 0x{b_val:02X} in GF(256):')
print(f'  0x{b_val:02X} = {b_val:08b} = x^7 + x + 1')
print(f'  So 0x{a_val:02X} × 0x{b_val:02X} = 0x{a_val:02X}×x^7 + 0x{a_val:02X}×x + 0x{a_val:02X}×1')
print()

# Build powers of x times a_val using xtime
print('Building powers via xtime:')
powers = [a_val]
temp = a_val
for i in range(1, 8):
    temp = xtime(temp)
    powers.append(temp)
    print(f'  0x{a_val:02X} × x^{i} = xtime^{i}(0x{a_val:02X}) = 0x{temp:02X}')

print()
# Accumulate: bits 7, 1, 0 of b are set
result = powers[7] ^^ powers[1] ^^ powers[0]
print(f'Result: 0x{powers[7]:02X} ⊕ 0x{powers[1]:02X} ⊕ 0x{powers[0]:02X} = 0x{result:02X}')
print()

# Verify
F.<alpha> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)
sage_result = gf256_to_byte(byte_to_gf256(a_val) * byte_to_gf256(b_val))
print(f'SageMath verification: 0x{sage_result:02X}  Match: {result == sage_result}')

Exercise 2 (Guided)

Build the complete 256-entry exp and log tables using generator 0x03. Then implement multiplication using only table lookups (no polynomial arithmetic).

# Exercise 2 (Guided), Log/exp table multiplication
F.<a> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)
g = byte_to_gf256(0x03)

# TODO: Build exp_table[i] = byte value of g^i for i in 0..254
# Hint: start with power = F(1), multiply by g each step
exp_tab = [0] * 256
log_tab = [0] * 256
# TODO: fill exp_tab and log_tab

# TODO: Implement table-based multiplication
def gf256_mul_table(a, b):
    """Multiply using exp/log tables. Return 0 if either input is 0."""
    if a == 0 or b == 0:
        return 0
    # TODO: return exp_tab[(log_tab[a] + log_tab[b]) % 255]
    pass

# TODO: verify against gf256_mul for all 256×256 pairs (or a sample)
# Hint: test at least 1000 random pairs

Exercise 3 (Independent)

1. Verify that 0x03 is a generator of GF(256)* by showing its order is 255.

2. Is 0x02 a generator? What is its order? Find all elements whose order divides 51 but not 17.

3. AES's MixColumns uses multiplication by 0x01, 0x02, and 0x03. Why are these sufficient? (Hint: in GF(256), 0x03 = 0x02 + 0x01, so multiplication by 0x03 is xtime(b) XOR b.)

# Exercise 3 (Independent), Your code here

Summary

Concept	Key idea
GF(256)	The AES field, constructed as GF(2)$[x]\,/\,(x^8 + x^4 + x^3 + x + 1)$. Elements are bytes (8-bit polynomials)
Addition = XOR	Adding two GF(256) elements is bitwise XOR, no reduction needed
Multiplication	Polynomial multiplication reduced mod $m(x)$. The xtime operation (multiply by $x$) is the fundamental building block
Multiplicative inverse	Every nonzero byte has a unique inverse. This is the key property that makes GF(256) a field, not just a ring
xtime	Multiply by 0x02: shift left, and if the high bit was set, XOR with 0x1B. All GF(256) multiplications decompose into xtime and XOR
Exp/log tables	Using generator 0x03, multiplication becomes table lookup: $a \times b = \text{exp}[\text{log}[a] + \text{log}[b] \bmod 255]$

Crypto foreshadowing: The AES S-box (notebook 03d) applies two operations to each byte: (1) take the multiplicative inverse in GF(256), then (2) apply an affine transformation over GF(2). The field inverse provides nonlinearity, the single most important property for resisting linear and differential cryptanalysis.

Next: AES S-box Construction, building the S-box from field inverses and affine maps.