03a-binary-fields-gf2.ipynb

Kernel: SageMath

The Binary Field GF(2)

Module 03a | Galois Fields and AES

The simplest field has only two elements, and it powers all of modern computing.

Question: Every computer stores data as bits, 0s and 1s. You can XOR two bits and AND two bits. But did you know that XOR and AND are actually addition and multiplication in a field?

A field with just two elements, where $1 + 1 = 0$. That sounds broken, but it's the foundation of AES, error-correcting codes, and all of GF($2^n$) arithmetic.

By the end of this notebook, you will see that bits aren't just data, they are field elements.

Objectives

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

1. Construct GF(2) in SageMath and list its elements

2. Verify all field axioms for GF(2) and explain why each holds

3. Identify XOR as field addition and AND as field multiplication

4. Explain why $1 + 1 = 0$ in GF(2) and why this is not a bug

5. Work with bit-vectors as vectors over GF(2)

Bridge from Module 02

In Module 02 you built rings and fields from scratch. You saw that a field is a ring where every nonzero element has a multiplicative inverse, and that $\mathbb{Z}/p\mathbb{Z}$ is a field when $p$ is prime.

The smallest prime is $p = 2$. So $\mathbb{Z}/2\mathbb{Z}$ should be a field with just two elements: $\{0, 1\}$. This is GF(2), and it is the starting point for everything in this module.

Module 02 concept	Module 03 application
$\mathbb{Z}/p\mathbb{Z}$ is a field	GF(2) = $\mathbb{Z}/2\mathbb{Z}$, the smallest field
Polynomial rings over a field	GF($2^n$) = GF(2)$[x]$ / (irreducible)
Quotient rings	How we build GF(256) for AES

# GF(2): the field with two elements
F = GF(2)
print(f'Field: {F}')
print(f'Elements: {list(F)}')
print(f'Characteristic: {F.characteristic()}')
print(f'Order (number of elements): {F.order()}')
print(f'Is a field? {F in Fields()}')

SageMath confirms: GF(2) has two elements, characteristic 2, and is a field.

Characteristic 2 means $1 + 1 = 0$. This single fact is the source of all the "weirdness" in binary fields, and also what makes them perfect for computers.

Addition in GF(2) Is XOR

The addition table for GF(2) is identical to the XOR truth table. Compare:

# Addition table for GF(2)
F = GF(2)
print('GF(2) Addition Table:')
print('  a | b | a + b')
print('  --|---|------')
for a in F:
    for b in F:
        print(f'  {a} | {b} |   {a + b}')

print()
print('XOR Truth Table:')
print('  a | b | a XOR b')
print('  --|---|--------')
for a in range(2):
    for b in range(2):
        print(f'  {a} | {b} |    {a ^^ b}')

print()
print('They are identical! GF(2) addition = XOR.')
print()
print('The key line: 1 + 1 =', F(1) + F(1))
print('In GF(2), every element is its own additive inverse: -1 = 1')

Checkpoint: In GF(2), addition and subtraction are the same operation. Why? Because $a - b = a + (-b) = a + b$ (since $-b = b$ for every element). This is why XOR is used for both encryption and decryption in stream ciphers: XOR is its own inverse.

Multiplication in GF(2) Is AND

Now let's look at multiplication:

# Multiplication table for GF(2)
F = GF(2)
print('GF(2) Multiplication Table:')
print('  a | b | a * b')
print('  --|---|------')
for a in F:
    for b in F:
        print(f'  {a} | {b} |   {a * b}')

print()
print('AND Truth Table:')
print('  a | b | a AND b')
print('  --|---|--------')
for a in range(2):
    for b in range(2):
        print(f'  {a} | {b} |    {a & b}')

print()
print('Identical again! GF(2) multiplication = AND.')
print()
# Multiplicative inverse: 1 is the only nonzero element
print('Multiplicative inverse of 1:', F(1)^(-1))
print('(0 has no inverse, as in any field.)')
print()
print('So GF(2) is a field where + = XOR, * = AND.')

Why $1 + 1 = 0$: Characteristic 2

Common mistake: "If $1 + 1 = 0$, then the field is broken, you can't have $2 = 0$!" But GF(2) has no element called "2." The only elements are 0 and 1. When you add 1 to itself, the result must be one of $\{0, 1\}$. It can't be 1 (that would make 1 the additive identity, but 0 already is). So $1 + 1 = 0$. This is called characteristic 2, the number of times you add 1 to get 0.

This is not a bug. It's what makes binary arithmetic work: carries disappear, addition has no "overflow" in the usual sense, and every element is its own negative.

# Characteristic 2 in action
F = GF(2)
one = F(1)

print('Adding 1 repeatedly:')
total = F(0)
for i in range(1, 6):
    total += one
    print(f'  1 added {i} time(s): {total}')

print()
print(f'Characteristic of GF(2): {F.characteristic()}')
print(f'This means: 1 + 1 = {one + one} (adding 1 exactly {F.characteristic()} times gives 0)')
print()

# Consequence: every element is its own negative
for a in F:
    print(f'-{a} = {-a}  (so {a} + {-a} = {a + (-a)})')
print()
print('Since -a = a for all elements, subtraction = addition = XOR.')

Verifying All Field Axioms

GF(2) has only 2 elements, so we can check every axiom exhaustively. A field needs:

• $(F, +)$ is an abelian group (identity 0, every element has an additive inverse)

• $(F^*, \times)$ is an abelian group (identity 1, every nonzero element has a multiplicative inverse)

• The distributive law holds

With only 2 elements, this is a very small amount of checking:

# Exhaustive field axiom check for GF(2)
F = GF(2)
elems = list(F)

print('=== Addition: abelian group ===')
print(f'Identity: 0 = {F.zero()}')
for a in elems:
    print(f'  {a} + 0 = {a + F.zero()},  inverse of {a}: {-a}  (check: {a} + {-a} = {a + (-a)})')

# Closure + commutativity + associativity (exhaustive)
add_ok = all(
    (a + b) in elems and (a + b == b + a) and
    all((a + b) + c == a + (b + c) for c in elems)
    for a in elems for b in elems
)
print(f'Closure, commutativity, associativity all hold? {add_ok}')
print()

print('=== Multiplication: abelian group on F* = {{1}} ===')
nonzero = [a for a in elems if a != 0]
print(f'F* = {nonzero}')
print(f'Identity: 1 = {F.one()}')
for a in nonzero:
    print(f'  {a}^(-1) = {a^(-1)}  (check: {a} * {a^(-1)} = {a * a^(-1)})')

mul_ok = all(
    (a * b) in elems and (a * b == b * a) and
    all((a * b) * c == a * (b * c) for c in elems)
    for a in elems for b in elems
)
print(f'Closure, commutativity, associativity all hold? {mul_ok}')
print()

print('=== Distributive law ===')
dist_ok = all(
    a * (b + c) == a * b + a * c
    for a in elems for b in elems for c in elems
)
print(f'a*(b+c) = a*b + a*c for all {len(elems)**3} triples? {dist_ok}')
print()
print('GF(2) satisfies ALL field axioms.')

Checkpoint: GF(2) is trivially a field because $F^* = \{1\}$, there's only one nonzero element, and $1 \times 1 = 1$, so it's its own inverse. The real power of GF(2) isn't in the field itself, but in what you can build on top of it: polynomial rings, vector spaces, and extension fields like GF($2^8$) = GF(256).

Bit-Vectors as GF(2) Vector Spaces

A byte (8 bits) is a vector in $\text{GF}(2)^8$. This isn't just an analogy, it's the literal mathematical structure. Adding two bytes component-wise over GF(2) is XOR:

# Bytes as vectors in GF(2)^8
V = VectorSpace(GF(2), 8)
print(f'Vector space: {V}')
print(f'Dimension: {V.dimension()}')
print(f'Size: {V.cardinality()} vectors (= 256 possible bytes)')
print()

# Example: two bytes as GF(2) vectors
byte_a = V([1, 0, 1, 0, 0, 1, 1, 0])  # 0xA6 = 10100110
byte_b = V([0, 1, 1, 0, 1, 0, 1, 1])  # 0x6B = 01101011

print(f'Byte A:     {byte_a}   (0xA6)')
print(f'Byte B:     {byte_b}   (0x6B)')
print(f'A + B:      {byte_a + byte_b}   (XOR)')
print()

# Verify this matches Python's XOR
xor_result = 0xA6 ^^ 0x6B
print(f'Python XOR: 0xA6 ^ 0x6B = {hex(xor_result)} = {bin(xor_result)}')
print()
print('Vector addition over GF(2) = bitwise XOR. Same operation.')

This is exactly what AES's AddRoundKey step does: XOR the state with the round key. It's vector addition in $\text{GF}(2)^{128}$.

Polynomials over GF(2)

The real payoff of GF(2) comes when we build polynomial rings over it. A polynomial over GF(2) has coefficients that are 0 or 1, so it's just a bit-string read as polynomial coefficients:

# Polynomial ring over GF(2)
R.<x> = GF(2)[]
print(f'Ring: {R}')
print()

# Polynomials over GF(2), coefficients are bits!
p1 = x^7 + x^4 + x^2 + 1     # bit-string: 10010101 = 0x95
p2 = x^6 + x^5 + x^3 + x     # bit-string: 01101010 = 0x6A

print(f'p1 = {p1}')
print(f'p2 = {p2}')
print()

# Addition of polynomials = XOR of coefficients
print(f'p1 + p2 = {p1 + p2}')
print(f'  (coefficient-wise addition in GF(2) = XOR of bit-strings)')
print()

# Multiplication is more interesting, polynomial multiplication with GF(2) coefficients
print(f'p1 * p2 = {p1 * p2}')
print(f'  (degree grows, this is NOT just XOR)')
print()

# Key insight: byte 0x95 as a polynomial
byte_val = 0x95
bits = [(byte_val >> i) & 1 for i in range(8)]
poly = sum(GF(2)(b) * x^i for i, b in enumerate(bits))
print(f'Byte 0x{byte_val:02x} = {bin(byte_val)} as polynomial: {poly}')

Checkpoint: A byte like 0xA3 is the bit-string 10100011. As a GF(2) polynomial, what is it? Write it as $a_7 x^7 + \cdots + a_0$. Check: which bits are 1? Those are the nonzero coefficients.

This byte ↔ polynomial correspondence is the key idea behind GF(256). In notebook 03b, we will take this polynomial ring and quotient out by an irreducible polynomial to create the finite field GF($2^8$) that AES uses.

Exercises

Exercise 1 (Worked)

Verify that GF(2) satisfies the field axiom: for every nonzero $a$, there exists $a^{-1}$ with $a \cdot a^{-1} = 1$. Then show that $x^2 = x$ for all $x$ in GF(2). (This property is called idempotence and is special to GF(2), it fails in every other field.)

# Exercise 1 (Worked), Multiplicative inverses and idempotence in GF(2)
F = GF(2)

# Part 1: Multiplicative inverses of nonzero elements
print('=== Multiplicative inverses ===')
for a in F:
    if a != 0:
        print(f'{a}^(-1) = {a^(-1)}  (check: {a} * {a^(-1)} = {a * a^(-1)})')
print('Only one nonzero element, 1, and 1*1 = 1. Trivially satisfied.')
print()

# Part 2: x^2 = x for all x in GF(2)  (idempotence)
print('=== Idempotence: x^2 = x ===')
for a in F:
    print(f'{a}^2 = {a^2}  (equals {a}? {a^2 == a})')

print()
print('Both 0^2 = 0 and 1^2 = 1. This works because GF(2) has characteristic 2.')
print('In GF(3), 2^2 = 4 ≡ 1 ≠ 2, so idempotence fails. GF(2) is special.')

Exercise 2 (Guided)

Convert the byte 0xCB (binary 11001011) to a polynomial over GF(2), and convert the polynomial $x^5 + x^3 + x + 1$ back to a byte. Then add the two polynomials and verify the result matches XOR of the bytes.

# Exercise 2 (Guided), Byte ↔ polynomial conversion
R.<x> = GF(2)[]

# Step 1: Convert 0xCB to polynomial
byte_val = 0xCB
# TODO: extract bits and build polynomial
# Hint: bit i is (byte_val >> i) & 1, coefficient of x^i
bits = [(byte_val >> i) & 1 for i in range(8)]
poly_cb = sum(GF(2)(b) * x^i for i, b in enumerate(bits))  # TODO: uncomment after trying yourself
print(f'0x{byte_val:02X} = {bin(byte_val)} as polynomial: {poly_cb}')

# Step 2: Convert x^5 + x^3 + x + 1 back to a byte
poly2 = x^5 + x^3 + x + 1
# TODO: extract coefficients and build byte value
# Hint: poly2[i] gives the coefficient of x^i
byte2 = 0  # TODO: compute this using poly2[i] for i in range(8)
print(f'{poly2} as byte: TODO')

# Step 3: Add the polynomials and verify = XOR of bytes
poly_sum = poly_cb + poly2
# TODO: convert poly_sum back to a byte and check it equals byte_val ^^ byte2
print(f'Sum polynomial: {poly_sum}')
print(f'XOR of bytes:   {hex(byte_val ^^ byte2)}')

Exercise 3 (Independent)

The Hamming weight of a bit-vector is the number of 1s. In GF(2) terms, it's the sum of the vector's components (computed in $\mathbb{Z}$, not GF(2)!).

1. Write a function that takes a byte (0-255) and returns its Hamming weight.

2. How many bytes have Hamming weight exactly 4? (These form an important subset in coding theory.)

3. The XOR of two bytes $a \oplus b$ has Hamming weight equal to the Hamming distance between $a$ and $b$. Verify this for $a = \text{0x3C}$ and $b = \text{0xA5}$.

# Exercise 3 (Independent), Your code here

Summary

Concept	Key idea
GF(2)	The smallest field, just $\{0, 1\}$, with characteristic 2 so $1 + 1 = 0$
Addition = XOR	GF(2) addition is exactly the XOR gate, and subtraction is the same operation
Multiplication = AND	GF(2) multiplication is exactly the AND gate
Self-inverse elements	Every element is its own additive inverse ($-a = a$), so addition and subtraction are identical
Bytes as vectors	A byte is a vector in $\text{GF}(2)^8$, and XOR of bytes is vector addition over GF(2)
Bytes as polynomials	A byte is also a polynomial in $\text{GF}(2)[x]$ of degree $\leq 7$, with polynomial addition equal to XOR

Crypto foreshadowing: AES operates entirely over GF(2) and its extension GF($2^8$). AddRoundKey is GF(2) vector addition (XOR). SubBytes, MixColumns, and the key schedule all use GF($2^8$) arithmetic, which we build starting in notebook 03b.

Next: Extension Fields: GF($2^n$), how to build larger fields from GF(2) using irreducible polynomials.