notes/docs/lectures/cryptography/06_finite_fields.md

Finite Field Arithmetic

• A finite field is a set containing a finite number of elements
  • This is sometimes called a Galois Field
• In a Galois field you can:
  • Add
  • Subtract
  • Multiply
  • Invert (divide)
• Fields are an extension of groups and related to rings

Groups

A group is a set of elements G together with an operation \circ that combines two elements of G

1. The operation \circ is closed
   • i.e. for all a,b \in G then a\circ b=c\in G
2. The operation is associative
   • i.e. a\circ(b\circ c) = (a\circ b)\circ c for all a,b,c \in G
3. There is an element 1\in G called a neutral element such that a\circ 1 = 1\circ a = a for all a\in G
4. For each a \in G there exists an element a^{-1}\in G called the inverse of a such that a\circ a^{-1} = a^{-1}\circ a = 1
5. A group G is abelian (commutative) if a\circ b = b \circ a for all a,b\in G

Example Group

• The set of integers \mathbb{Z}_m = \{0,1,...m-1\} with the operation addition modulo m form a group with the neutral element 0
• Every element would have an inverse where a + (-a) = 0 mod m
• This group would not form a group with multiplication, as not all elements would have an inverse
  • We wouldn’t have an inverse; we would need 5\times \frac15=1, but \frac15 \notin \mathbb{Z}

Fields

A field F is a set of elements with the following properties

1. All elements of F form an additive group with the group operation + and the neutral element 0
2. All elements of F except 0 form a multiplicative group with the group operation \times and the neutral element 1
3. When the two group operations are mixed, the distributivity law holds.
   • i.e. for all a,b,c \in F, a\cdot(b+c) = (a\cdot b) + (a\cdot c)

Example Field

• The set of real numbers \mathbb{R} is a field with neutral element 0 for addition and 1 for multiplication
• Every real number a has an additive inverse -a
• Every non-zero number a has a multiplicative inverse \frac{1}{a}

Finite Fields

A finite field only exists if it has p^m elements

Where:

• p is a prime
• m is a positive integer

Examples

• There is a field with 11 elements: GF(11)
• There is a field with 256 elements: GF(256) or GF(2^8)
• GF(12) is not a finite field (2^2 \cdot3)

Prime and Extension Fields

When m=1 it creates a prime field

When m>1 it creates an extension field

Prime Fields

• A prime field GF(p) contains the integers \{0,1,...p-1\}

• These operations satisfy the properties of fields (closure)

Inversion in Prime Fields

a \cdot a^{-1} \equiv 1 \space (mod \space p)

• A modular inverse exists when gcd(a,p) = 1
• Because p is prime, every number has a multiplicative inverse
  • gcd(a,p) = 1, \forall a \neq0 \in GF(p)
• a^{-1} can be calculated using the extended Euclidean algorithm

Extension Fields

• In prime fields, the elements are integers
• Elements in extension fields GF(2^m) are polynomials of degree m

a_{m-1}x^{m-1}, ..., a_1x + a_0 = A(x) \in GF(2^m)

where a_i \in GF(2) = \{0,1\}

The coefficients of the polynomial are elements in GF(2) the sub-field

Example GF(2^3)

• The field GF(2^3), sometimes called GF(8) is an extension field containing elements of the form: A(x) = a_2 x^2 + a_1x^1 + a_0
• It's often easier to simply write the coefficients (a_2, a_1, a_0) e.g. 001 or 101
• GF(2^3) = \{0, 1, x, x+1, x^2, x^2+1, x^2 + x, x^2 + x + 1\}
  • |GF(2^3)| = 8

Arithmetic in GF(2^3)

• Adding or subtracting two polynomials happens as expected, but adding the coefficients
  • A(x) = x^2 + x + 1
  • B(x) = x^2 + 1
  • A(x) + B(x) = (1+1)x^2 + (1)x + (1+1) = x
• mod 2 is simply xor
• Addition and subtraction are identical

Multiplication in GF(2^3)

• A(x) = x^2 + x + 1
• B(x) = x^2 + 1
• A(x) \cdot B(x) = (x^2 + x + 1)(x^2 + 1) = x^4 + x^3 + (1+1)x^2 + x + 1
• x^4 + x^3 + x + 1 however this is not in the field
• The result must be reduced by the result modulo an irreducible polynomial

A(x) \cdot B(x) = x^4 + x^3 + x + 1\space (mod \space x^3 + x + 1)

• This means we have to do polynomial long division

Inversion

• Inversion is performed in a similar way to prime fields, we find:
• A(x) \cdot A^{-1}(x) \equiv 1 \space (mod \space P(x))
  • A^{-1}(x) is calculated using the extended Euclidean algorithm

AES’ Finite Field

• AES uses the extension field GF(2^8) for many of its operations
• Operations are the same as those in other GF(2^m) fields, using the irreducible polynomial

  P(x) = x^8 + x^4 + x^3 + x + 1

• As you might expect, these polynomials are typically represented as single bytes