Introduction to Galois Fields for AES

Motivation

In the next few posts I want to discuss the Advanced Encryption Standard or better known as AES, which is the most famous symmetric cipher today.

But to do that unlike for DES I need to introduce a new type of mathematics. So in this post, I will introduce group theory and eventually get to finite fields. This is important because all operations of AES are based on finite fields.

Introduction to Galois Fields

Terminology: Galois Fields = Finite Fields. I will switch back and forth between these terms but they mean the same thing.

If you do not recognize the term field in mathematics then you may wonder what I am talking about. To describe that it will be better to break it down and first understand what a ring is, and to understand what a ring is we need to know what a group is.

Groups

The simplest thing I can introduce is a group. A group is essentially a set of numbers and an operation flowing these rules:

Definition of a group:
A group is a set of elements G with an operation ∘ that combines two elements of G. The group has the following properties:

The group operation is closed. That is, if a, b G, then a ∘ b = x ∈ G.
The group operation is associative.
There is an element 1 ∈ G called the neutral element or identity element, that if a ∘ 1 = 1 ∘ a = a for all a ∈ G.
For each a ∈ G there exists an element a^-1 ∈ G, called the inverse of a, such that a ∘ a^-1 = a^-1 ∘ a = 1.
A group G is abelian (or communative) if a ∘ b = b ∘ a, for all a, b ∈ G.

For any other fellow pure mathematicians, you may be wondering where the proof of these rules is. But that would add a lot to this already big post so you will just have to trust me and other smarter mathematicians that these are true.

But this will be a building block to lead us into rings and add more operations.

Rings

I wish I could dedicate more time to group theory and rings, but as this is a crypto-based blog and this post is a lead-up to AES I will skip defining rings.

But I won’t leave you with anything, rings are a lot like groups, and all the rules of a group are required in rings but rings add an additional operation, and that comes with a couple more rules that you could find on your own very easily.

Fields

In order to have all four basic operations (Addition, Subtraction, Multiplication, and Multiplicative Inverse(Division)) in a single structure, we need a set that contains all the properties below.

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

All elements of F form an additive group with the group operation “+” and the neutral element 0.
All elements of F except 0 form a multiplicative group with the group operation ” ⋅ ” and the neutral element 1.
When the two group elements are mixed, the distributivity law holds.

Example: ℝ, ℂ

This was an extremely informal and quick introduction to these structures. There is a lot to group theory and it would be impossible for me to introduce what usually takes a semester in university into a single blog post. But if you are only interested in crypto, and aren’t currently interested in the mathematics behind it, this is what will need to get into the Finite Fields in AES.

Finite Fields

You may be wondering that we know what a field is now, but how do we make a finite field? We have a theorem for that.

Finite Field Theorem:

A field with n elements is a Finite Field if n = p^m, for some integer n and prime integer p.

Examples of Finite Fields:

From this theorem we can distinguish between two cases:

Both of these fields are important in cryptography, especially interested in GF(2^m) for AES.

In crypto we are interested in how we can compute in these fields, when you learn more about crypto you may want to dive deeper into the mathematics of group theory. But for this post, we will focus on how we can compute in these fields.

Prime Fields Arithmetic

The most intuitive form of finite fields are prime fields so we will begin here. First thing we need to know are what the elements of a prime field are:

The elements of a prime field GF(p) are the integers: {0, 1, 2, … , p – 1}.

This should hopefully seem familiar, or atleast not to hard. But now we need to get into how we do the 4 basic operations ( +, -, ⋅ , ( )^-1 ).

Addition, Subtraction, and Multiplication in Prime Fields

Rules:
Let a, b, d, e ∈ GF(p) = {0, 1, …, p – 1}

a + b ≡ c mod p
a – b ≡ d mod p
a ⋅ b ≡ e mod p

Thankfully isn’t too bad, especially if you have read my Introduction to Modular Arithmetic post.

I will not show that these operations suffice the properties of a field, but believe me they work.

Multiplicative Inverse (Division) in Prime Fields

You may have noticed instead of calling this just division I have been referring to this as the multiplicative inverse. Truthfully it is just a better-fitting term, and the further we get into these posts you will start to see why.

This is actually a special case because we can’t do the same thing we did for the other 3 operations. Looking back at our definition we know if a ∈ GF(p) then there exists a^-1 ∈ GF(p) s.t. a ⋅ a^-1 ≡ 1 mod p. This was also referenced when I talked about the Affine cipher in The Shift Cipher post.

You may wonder then how we get a^-1 ? This would be done using the extended euclidean algorithm. This algorithm is very important in asymmetric cryptography which we will get into so look out for that.

Extension Field Arithmetic

In this part of the post, we will only focus on the AES Extension Field case which is GF(2^m), and in fact, the extension field we will be working on in AES is GF(2⁸).

Recall from prime fields we talked about the elements first, and that they were just simple integers. Well, this is the first time we will work with a set where the elements are not integers!

Element Representation

The elements of GF(2^m) are polynomials, meaning: a_{m – 1} x^{m – 1} + a_{m – 2} x^{m – 2} + … + a₁ x¹ + a₀ = A(x) ∈ GF(2^m).

Note that we only really care about the coefficients in a polynomial, therefore it is good to know what the coefficients can be: a_i ∈ GF(2) = {0, 1}. Which is a prime field! For any computer scientist, you may then notice that these are essentially bits, thus we could rather think of A(x) as a vector A(x) = (a_{m – 1,} a_{m – 2} , … , a₁ , a_{0 ).}

Example

Let GF(2³) be an extension field, and recall that the coefficients can be either 0 or 1. Then the elements of GF(2³) are:

GF(2³) = {0, 1, x, x + 1, x², x² + 1, x² + x, x² + x + 1},

or like I mentioned before as vectors of bits/ binary numbers:

GF(2³) = {000₂, 001₂, 010₂, 011₂, 100₂, 101₂, 110₂, 111₂}.

So now we have to understand how we compute with polynomials in finite fields.

Addition and Subtraction in Extension Fields

It turns out that these operations are straightforward. They are simply achieved by doing simple addition or subtraction of the coefficients and taking that modulo 2.

Definition:
Let A(x), B(x), C(x) ∈ GF(2^m), then:

C(x) = A(x) + B(x) = ∑_{i = 0}^{m – 1} c_i xⁱ , c_i ≡ a_i + b_i mod 2

and subtraction is computed as:

C(x) = A(x) – B(x) = ∑_{i = 0}^{m – 1} c_i xⁱ , c_i ≡ a_i – b_i ≡ a_i + b_i mod 2.

Notice that addition and subtraction are the same operation.

Example

Let GF(2³) be an extension field, and let A(x) = x² + x + 1 and B(x) = x² + 1. Then:

A(x) + B(x) = (1 + 1) x² + (1 + 0) x + (1 + 1)
= (0) x² + (1) x + 0.
= x.

Multiplication in Extension Fields

Your first intuition would probably just do normal polynomial multiplication, but this doesn’t work because oftentimes we would get a result that is not within our field, and if you recall a field must be closed.

But we can use a similar trick as we did with prime fields. In prime fields, we took our result modulo p. The same idea will apply here to extension fields, but instead, we have to reduce with a polynomial.

Therefore we need a polynomial that behaves like a prime. These polynomials are called irreducible polynomials, meaning these polynomials cannot be factored.

The irreducible polynomial for GF(2³) is P(x) = x³ + x + 1.

Definition:
Let A(x), B(x), C(x) ∈ GF(2^m), then:

C(x) ≡ A(x) ⋅ B(x) mod P(x)

Example

Let GF(2³) be an extension field, and let A(x) = x² + x + 1 and B(x) = x² + 1. Then:

C(x) = A(x) ⋅ B(x) = x⁴ + x³ + x + 1.

Then we need to factor by P(x) = x³ + x + 1 and take the remainder, which gives us:

C(x) = x² + x.

You may wonder where we get this P(x) from. Well in fact for ever finite field there are several of these irreducible polynomials. Note which is different from prime fields that only had 1.

Therefore with a given finite field the computations could be different based on which irreducible polynomial you use. Thus, if I gave you a finite field I must also give you a P(x). In fact this is built into the AES, and the irreducible polynomial of AES is P(x) = x⁸ + x⁴ + x³ + x + 1