Abstract Algebra

29th January 2025

Guess what, I've not made much progress on implementing HTTPS. It's safe to say that it turned out to be very complicated, no surprise there.

I like to approach this kind of challenge by first getting a complete overview of the whole problem, then implementing it from the bottom up. To that end, I’ve read the tech specs and some books, I even watched some uni lectures I found on YouTube, and the good news is I now have a fairly good understanding of the steps required to implement an HTTPS server. I have actually learnt quite a bit, I’ve just not turned that into code yet.

As for the implementation, I decided to start with AES (Advanced Encryption Standard), which is the algorithm responsible for actually encrypting the data. It is just one of many acronyms I’m going to need to implement, but core to the whole process and something I can do in isolation from the rest of the process. There are few steps to the AES algorithm, called layers, which are essentially data manipulation and maths. This is good, I understand maths and can turn maths into code, write enough code and eventually I'll have an HTTPS server. The problem is I don’t understand the maths. It’s not normal maths.

One of the layers in AES calls for some multiplication, which shouldn't be an issue. I learnt how to multiply decades ago. One of the guides I was looking at helpfully showed an example:

0001₂ × 0011₂ = 0011₂

For those not fluent in binary this would typically look like this in your everyday decimal (aka normal numbers):

1 × 3 = 3

No problems so far but the second example flummoxed me:

Err, nooooo? When I was at school, 3 multiplied by 3 equaled 9. Didn't it?

The third example made sense again:

And then back to weird:

Do I actually understand maths?

One book I was reading, Implementing SSL/TLS by Joshua Davies, commented at one point “This probably doesn’t look much like multiplication to you, and honestly it isn’t”, it also pointed out that adding and multiplying in AES have been redefined to other operations/functions. It didn’t really explain why and just gave the code required to perform the operations, hinting it has something to do with finite fields. I think the book was written before “trust me bro” was a meme, but that is the vibe I was getting. There is nothing wrong with that approach, except I wanted to understand why.

I did some more research and found a collection of lectures Understanding Cryptography presented by Christof Paar and backed up by a textbook he co-authored. This did an excellent job of explaining what a finite field is and why 3 multiplied by 3 sometimes seems to equal 5. However it got a bit hand-wavey about how that would be implemented.

What didn’t help is that the code from the first book didn’t seem to bear any relevance to the theory I now understood from the second. What I needed was something that bridged the gap. To be fair that’s my responsibility, I can’t be expected to be spoon fed these things, this is what study is. So I did a lot of scribbling on scraps of paper and some serious staring at the ceiling whilst thinking about how basic maths really does work. The good news is that it eventually clicked!

I'm a big fan of the Feynman Technique which helps you learn something by pretending to teach it to someone else. This helps identify the holes in your understanding and makes sure you really do get it. If you can't explain it, you don't understand it. That's what a large part of this blog is, me learning stuff by explaining it. With that in mind, I present my primer on finite fields and how they apply to cryptography.

Sets

Finite fields belong to a branch of mathematics called Abstract Algebra. This is the study of sets and the operations you can perform on them.

A set is a collection of unique things. The things, called elements, can be anything but are normally numbers. Sets can have a finite number of elements, for example the decimal digits 0 to 9, or they can be infinite like the set of natural numbers. There are a bunch of rules and observations regarding sets and a whole sub branch of mathematics called set theory which we don't need to delve too deep into. We do however need to understand some of the notations used with sets.

You can define the elements of a set using words, the language can seem a bit formal but the intention is to be completely unambiguous.

"Let A be a set whose elements are the first five even natural numbers."

This is called a semantic definition. Or you can use a comma separated list between curly brackets to enumerate the elements.

A = {2, 4, 6, 8, 10}

For sets that have an obvious pattern you can use eclipses (...) as a shortcut. For example, a set of the first 100 natural numbers would be:

N = {1, 2, 3, 4, …, 100}

For infinite sets you can use the eclipse at the start or the end to show the set extends forever. For example, the set of integers would be:

Z = {..., -3 ,-2 ,-1 ,0 ,1, 2, 3, …}

Groups

Now we have sets we need to do stuff with the elements in them, what we need is operations. In general an operation is a function that takes as input elements from a set and outputs a result from the same set. A typical example is addition, it takes two elements, adds them together and returns the result.

An algebraic structure is when you combine a set with a number of operations and a number of conditions that the structure must meet. For example, a “group” is type of algebraic structure that consists of a set, an operation and meets the following rules:

1. The operation maps every pair of elements in the set to another element of the set.
2. The operation needs to be commutative.
3. The operation needs to be associative.
4. There is an identity element.
5. Every element has an inverse.

Let's consider the set {1, 2, 3, …, 8} with the operation addition and if this meets the criteria to be a group? Initially it seems ok, for example 2 + 3 = 5, however it's quickly evident there are pairs of inputs that when added together result in a number not in the set, for example 4 + 5 = 9. In fact over half the pairs of inputs result in numbers not in the set. Therefore we fail our first condition and can't consider this set with this operation a valid group.

To fix this we need more numbers, that's the thing with addition we always need a bigger number. The good thing is we can have infinite sets, we could instead use the set of natural numbers aka {1, 2, 3, …} which means no matter what pair of elements you pick, the result will also be in the set and meets the first of our criteria.

The second condition, that the operation must be commutative, is a fancy way of saying we can provide the elements to the operator in any order and get the same result. Addition meets this requirement. For example 2 + 3 and 3 + 2 both result in 5. In contrast subtraction is not commutative, 2 - 3 = -1 where 3 - 2 = 1.

The third condition, that the operation must be associative, means we can do repeated operations in any order and get the same result. Addition also meets this requirement. For example (2 + 3) + 4 = 9 and 2 + (3 + 4) = 9.

An identity element is something that can be paired with any other element and results in that other element. For addition, 0 is the identity element, add 0 to any other number and you get that number. The set of natural numbers does not include 0 and so combined with addition does not form a valid group. The set of whole numbers extends the natural numbers by adding 0, so switching to whole numbers means we can meet the first four criteria.

The inverse of addition is subtraction. If you add 3 to a number, to get back to that number you need to subtract 3. However we don’t have access to subtraction, only addition, but we can fake it by adding negative numbers. If you add 3 to a number, to get back to that number you need to add -3. Therefore the inverse of 3 is -3. The formal definition is when an element is paired with its inverse the result is the identity element, for example 3 + (-3) = 0.

The set of whole numbers contains no negatives so fails to meet criteria five and therefore fails to form a valid group with addition. To meet all criteria we need to switch to the set of integers which extends the whole numbers by adding all the negative numbers.

So the set of integers and addition form a valid group, which is kind of interesting but who cares? Well mathematicians care because groups help define how things like numbers actually work and from there they can make proofs from which they can build more complicated structures and do really smart things. You and I may take how numbers work for granted, but someone has to make sure they work how we think they do, and groups help mathematicians do that.

Computer scientists care because when they build a computer that they claim can do arithmetic, they want to be confident that the arithmetic will always work, or at least know how it is likely to break. As we just saw, for addition to work everytime we need an infinite set of integers. But computers can’t support an infinite number of integers, or even just one infinitely sized integer, at some point they will run out of memory, so computers have limits and groups help prove that.

As a result, when designing a computer or program to add numbers together you have to account for potential failures and report errors. If you've ever seen an overflow error on a computer or calculator, you've had first hand experience of this. Alternatively, if you really need your operation to succeed every time, if you need a valid group but can't use an infinite set, you can’t use addition and instead need a different operation.

Modular Arithmetic

Enter modular addition. Modular addition is where numbers wrap around to the beginning once they reach a certain value. The most familiar example of this is time and the 12 hour clock face. If the time is 10 o’clock and you add 4 hours, instead of the time now being 14 o’clock it is actually 2 o’clock because after the time reached 12 it wrapped back to 1.

Just like time and a clock, you can wrap around multiple times. Take 10, add 24 and you will wrap around 2 times and end up back at 10. In this modular system 10, 22, 34, 46, etc. are all equivalent to each other. Even -2 and -14 are equivalent to 10. It doesn't matter how far you go in either direction, every number will be equivalent to one of 12 numbers. This is essentially modular arithmetic.

Modular arithmetic allows the formation of a valid group with a finite set of numbers, in the clock example this is the set {1, 2, …, 12}. It passes the first rule as all pairs map to another element, wrapping round to 1 when required. It passes the second and third rules as the operation is commutative and associative. There is an identity element, which in this case is 12 because if you add 12 to any number you get back that number as it will wrap around once.

At first it might seem that elements don’t have an inverse because there are no negative numbers, if you add 3 how do you get back to where you started? The answer is to take advantage of the wrapping, if you add 3, to get back to where you started you need to add an additional 9. Looking at the formal definition, when an element is paired with its inverse the result is the identity element. The identity element is 12, so when you add 3 what do you need to add to get to 12? 9, it’s 9, we all knew that. A potentially tricky one is the inverse of 12, my intuition wants to say the inverse is 0 but because 0 is not part of the set we can’t use it and instead have to use 12, 12 is its own inverse.

A cleaner example would be to consider the 24 hour clock with midnight being the zeroth hour. The set would then be {0, 1, 2, …, 23} and the identity element would now be 0. The inverse of 3 would now be 21, the inverse of 10 would be 14 and the inverse of 0 would be 0. It’s the same idea but having 0 in the set means there’s less unnecessary wrapping around.

Starting at zero also allows us to consider modular arithmetic as the remainder from integer division. Take a number and divide that number by the modulus (the number of elements in the set) and the remainder will be congruent with the original number and one of the numbers in the set. For example, if the time now is 10:00 and you want to know what the time will be in 100 hours, first add 100 to 10 to get 110, then divide that by 24 but ignore the result (it’s 4 if you really needed to know) and instead take note of the remainder, which is 14, so the time will be 14:00 (or 2pm).

This operation of performing integer division but only returning the remainder is called the modulo operator, abbreviated to mod in mathematical notation:

110 mod 24 = 14

This is how I’m most familiar with using modular arithmetic, most programming languages have a modulo operator and so this is how I’m used to seeing it written down. However mathematical texts (and some books on cryptography) tend to use a different notation style that initially had me confused:

110 ≡ 14 (mod 24)

The triple line equals like symbol means equivalent and the (mod 24) in brackets applies to the whole expression not just the right hand side of the equivalent symbol. This expression should be read as “one hundred and ten is equivalent to fourteen in modulus twenty four”.

Back to computers. A typical 8 bit byte can be used to store a total of 256 numbers, it is fairly common to therefore use a byte to store the numbers from 0 to 255, i.e. the set {0, 1, 2, …, 255}. This is a finite set just like our clock example, so if we couple this with modular arithmetic which will wrap around should addition result in 256 or higher, we get a valid group and a system that avoids overflow errors. This is a common strategy in computer science. In a lot of places like the C programming language it’s actually the default behaviour. It’s not without pitfalls, especially for newer programmers who are not aware that they are not actually performing addition, they are performing modular addition. I’ve been using numbers like this for decades and so I’m very comfortable with it. I just never realised till now that I was using a group.

Fields

Fields, like groups, are an algebraic structure, but have two operations. Because there are two operations, it helps to give them names so they can be discussed and defined and those names are addition and multiplication. Crucially they don’t have to be the addition and multiplication we normally associate with numbers, but they do have to meet the rules listed below, so they will behave similarly to the addition and multiplication we are familiar with.

1. Both operations map every pair of elements in the set to another element of the set.
2. Both operations need to be commutative.
3. Both operations need to be associative.
4. There is an identity element for each operation, 0 for addition, 1 for multiplication.
5. Every element has an additive inverse.
6. Every element except 0 has a multiplicative inverse.
7. Multiplication distributes over addition.

As I did with groups, I want to first consider fields with normal addition and multiplication and what sets this will work with. We already know that a finite set, like {1, 2, …, 8}, will not work because addition fails with this set, but for the record, multiplication fails for the same reason, not all pairs map to an element. 3 x 4 for example results in 12 which is not part of the set. Using the infinite set of natural numbers, which fixes this for addition, will also fix this for multiplication.

Multiplication like addition is both commutative and associative. Which is handy

The identity elements have already been specified by rule four, 0 for addition and 1 for multiplication. We already know this works for addition and it only takes a moment’s thought to confirm any number multiplied by 1 is itself, so that checks out nicely.

We already know that to get the inverse elements for addition we have to expand to the set of integers so we have negative numbers, does this also help with multiplication? First, what is the inverse of multiplication? Well if I multiply a number by 2, to get it back to the original number I would have to divide it by 2 or half it, or put another way multiply it by the fraction ½. This pattern works for all numbers, the multiplicative inverse of a number is the fraction 1 over that number. For 3 it’s ⅓ for 10 it’s 1/10 etc. This means the set of integers is not going to work, our field requires fractions, we instead need to use the set of rational numbers.

There is no inverse for 0, because you can’t divide anything by 0, the fraction 1/0 does not exist. Recalling the formal definition of an inverse, when an element is paired with its inverse the result is the identity element. So what number multiplies with 0 to get 1? Well nothing, because every number multiplied by 0 is 0. Thankfully the elders of mathematics gave us an out for this one when writing the rules for a field, by not requiring a multiplicative inverse for 0.

The last requirement basically describes how addition and multiplication interact in a single equation. It asserts that a × (b + c) = (a × b) + (a × c). This is true for addition and multiplication, multiplying out the brackets was one of those exercises drummed into us at school, so we know it's true. But let's work through a trivial example to reassure ourselves it works:

2 × (1 + 3) = (2 × 1) + (2 × 3)
      2 × 4 = 2 + 6
          8 = 8

With that we have a valid field, the most noteworthy part being we had to switch from the set of integers to the set of rational numbers to meet the multiplicative inverse requirement. I’ve always known that division was a pain in the butt.

Prime Fields

Back to computers again, and we can’t use the infinite set of rational numbers to support multiplication, but can modular arithmetic help out? Let’s take a look. Modular arithmetic works much the same with multiplication as it does for addition, if the number gets too big it wraps back around to the beginning. Let’s consider the set of the first 8 whole numbers aka {0, 1, …, 7}. 2 × 3 = 6, no problem there, 3 × 4 = 12 ≡ 4 (mod 8), also valid. It’s fairly easy to see that this meets all the requirements for a field except for the multiplicative inverse, which needs some more thought.

We can’t use fractions for the inverse as they are not in set. But maybe as with addition we can use the wrap-around properties of modular arithmetic to find an inverse. There are only eight elements in the set let's check them all. We can skip 0 because the rules let us. 1 is also easy because 1 is it’s own inverse, 1 × 1 = 1 and 1 is the identity element. 2 is the first problem, the plan is to keep multiplying it by each element in the hope that one of them will wrap around to the identity element (i.e. 1). 2 × 1 = 2, well we knew that but had to start somewhere, 2 × 2 = 4, no good, 2 × 3 = 6, still no good, 2 x 4 = 8 ≡ 0 (mod 8), it wrapped around but not to 1, 2 × 5 = 10 ≡ 2 (mod 8), ah, we are back to where we started, jumping over the identity element. It’s easy to see that this pattern would continue, and there is no element that would result in 1. Therefore this set and modular arithmetic do not form a valid field.

It does however hint at a possible solution, what if the set had an odd number of elements, then when we wrapped around we should at some point land on 1. Let's try a set of seven elements, {0, 1, …, 6}. The inverse for 0 and 1 work the same as last time. 2 initially works the same, but 2 × 4 = 8 ≡ 1 (mod 7), success! What about the other elements? Turns out all of them have a pair that results in the identity element aka an inverse.

3 × 5 = 15 ≡ 1 (mod 7)
4 × 2 = 8 ≡ 1 (mod 7)
5 × 3 = 15 ≡ 1 (mod 7)
6 × 6 = 36 ≡ 1 (mod 7)

As a result a set with the first seven whole numbers and modular arithmetic forms a valid field. This is known as a finite field of order seven, in notation this is written as GF(7). GF stands for Galois Field, another name for a finite field, named after Évariste Galois a French mathematician who did a lot of the groundwork that became abstract algebra.

It turns out that all sets with a prime number of elements form a valid finite field with modular arithmetic. It wasn’t a coincidence that I picked a set of seven elements for my example. These fields are also referred to as prime fields. They all work as our example, the elements of the set are the integers from 0 to p-1 where p is a prime number and the operations are addition and multiplication modulo p.

Extension Fields

The problem we face in computing and specifically in cryptography, we want to use sets that are not a prime number of elements, for example encryption wants a set that is 256 elements in size.

The good news is mathematicians like Galois worked out that for sets with pⁿ elements, where p is a prime number and n is a positive integer, there exists a valid finite field. For the prime fields n will be 1. Fields where n is greater than 1 are called extension fields. More good news is 2 is a prime number and 2⁸ is equal to 256 so we should be able to have a valid finite field with 256 elements.

But first a smaller example, 2³ = 8, so there should also be a valid finite field with eight elements but we already tried that and it failed. The trick to extension fields, is the elements are not numbers, they are polynomials.

Polynomials

A polynomial is an expression consisting of the sum of many terms. A term consists of a coefficient and a number of variables raised to a power. It would be easier to explain with an example:

3x² + 7x - 6

This polynomial has three terms, 3x², 11x and -6. The coefficient for the first term is 3, the second 7 and the third -6. This polynomial has only one variable, x. In the first term it’s raised to the power 2, so this would be called a 2nd degree term. In the second there is no power written down, but technically this is raised to power 1, and would be called a 1st degree term. In the third term there is no variable listed, but this could be written as x⁰, which always evaluates to 1 and why it’s not normally shown. This third term could be called a zero degree term, but is normally called the constant term. It’s not normal but perfectly valid to write this polynomial like this:

3x² + 7x¹ - 6x⁰

The finite field with eight elements, aka GF(8) or GF(2³), consists of the elements {0, 1, x, x + 1, x², x² + 1, x² + x, x² + x + 1}. It might be hard to spot the pattern at first, but maybe this table will help clear things up.

The coefficients of these elements can be one of two values, 0 or 1. There are two possible values because the prime number in this field is 2. Each element has three terms. There are three terms because the prime number in this field is raised to the power of 3. The elements in this polynomial are formed from all the possible combinations of coefficients over all three terms.

For those familiar with binary, you might have spotted that the coefficients count up in a binary sequence. More on this later.

As a quick aside, the finite field with nine elements aka GF(3²) would have three possible values for the coefficient and two terms.

In general the elements of a extension field GF(pⁿ) will consists of pⁿ polynomials, each with up to n terms and each term with have coefficients from the field GF(p).

Addition in GF(2ⁿ)

If we are going to form a field with a set of polynomials, we are going to have to remind ourselves how to add and multiply polynomials together. Let's start with addition. This is the relatively simple process of grouping terms together that are raised to the same power and adding their coefficients together. For example:

(3x² + 7x - 6) + (x² + 3x + 2) = 4x² + 10x - 4

In this example the 3x² is added to the x² to make 4x², the 7x is added to the 3x to make 10x, finally the -6 is added to the 2 to make -4. Simple.

Addition in extension fields this works much the same, except the coefficients are from prime fields and so the simple addition is replaced with modular addition. For example in GF(2³) if we where to add x + 1 to x we don’t get 2x + 1 as you might expect because 2 is not part of the set {0, 1} and instead wraps round to 0 so you actually get 0x + 1 or simply 1.

(x + 1) + x = 2x + 1
            ≡ 0x + 1
            ≡ 1

At first this seems very alien if you are still applying value to these “numbers”, how can you add two numbers together and get less? That is the mental gymnastics you need to perform, these are not numbers, they are just elements in a set and addition, despite its name, is just a function that allows you to combine two elements of the set to get a third in a predictable and repeatable way.

Here is a table that shows the results of addition for all possible pairs in a finite field of order eight.

The additive inverse, aka subtraction, works much the same way with our other groups and fields with modular arithmetic. What do we need to add to each element to get back to the identity element (which is 0)? Considering each term separately, we can take advantage of the wrap around effect of the coefficients to zero them out.

A neat side effect of GF(2ⁿ) fields is every element is its own inverse. This is because the coefficients can only have the value 0 or 1 and adding 1 to 1 wraps back round to 0. Adding 0 to 0 also gives 0, which was hopefully obvious. The point is adding a coefficient to itself will always result in 0. The effect of this can be seen in the table above, the diagonal from top left to bottom right always results in 0.

This is also why texts on AES encryption will often describe addition and subtraction as the same thing. It's because adding elements and subtracting elements has the same result. What they don't always explain is this is because of the nature of GF(2ⁿ) fields.

Multiplication in GF(2ⁿ)

Let’s remind ourselves how multiplication works with polynomials. We take each term in one polynomial and multiply it by each of the terms in the other, then add the results together. To multiply each term, we add the powers and multiply the coefficients. For example:

3x² × 4x = 12x³

A complete example:

This works similarly in our extension field:

x(x + 1) = x² + x

The question is what happens when the multiplication results in something that is not in the set, for example:

(x + 1)(x² + x) = x³ + 2x² + x

First, like with addition the coefficient in the 2x² term will wrap around to 0, essentially removing that term. The remaining x3 + x is still not in our set, and again the answer is to use modular arithmetic, divide this by the modulus and take the remainder.

In our previous examples with natural numbers the modulus was in general the number of elements in the set, the polynomial equivalent is to use an irreducible polynomial of order one higher than supported by the set. In other words our set has terms raised up to the power of two (x²) so we need a polynomial with an term of power three (x³).

Irreducible in this context means the polynomial can not be factored, a bit like a prime number. It seems like there is no easy way to find an irreducible polynomial, every thing I've read on the subject seems to brute force it by testing each possible polynomial of that order to see if it can be factored. Also there is often more than one possibility, so when the field is defined (like in cryptography) it’s documented which polynomial to use as a modulus.

For GF(2³) we can use the irreducible polynomial x3 + x + 1. Which means I now need to divide a polynomial…I don’t think I ever did that at school, or I have at least purged it from my memory. It turns out you use a long division method very similar to the long division I do remember from school. Basically sort the two polynomials with the high order terms first, then divide the first term in the dividend by the first term in the divisor, multiply the divisor by that result and subtract it from the dividend to get a new polynomial and repeat. Our example looks like this.

We only had to do one iteration, the result was 1 (which we don’t care about) and the remainder is 1, which is the answer we are looking for. And so in GF(2³) the result of multiplying x + 1 with x2 + x is 1.

Here is a more complicated example which is the result of multiplying x2 with x2 + x.

In this instance we had to do two iterations, the result being x + 1 (which we can discard) and the remainder is x2 + 1 which is the answer we are looking for.

The following table shows all the results of multiplication in a finite field of order eight using x3 + x + 1 as the modulus.

Now we need to know what the multiplicative inverse for each element in the set is (except for 0). In other words what element should we multiply something by to get back to the identity element of 1. We could cheat and just use the table above, handley each row has a result equal to 1 in it, and that indicates the inverse.

But thinking forwards, that’s not going to scale to when I have 256 elements, there must be a way to compute it? There is, it’s called the Extended Euclidean Algorithm and that will be a future blog post because I need to start bringing this post to a close.

Representing Polynomials

At this point we have a field with 2³ aka eight elements and it meets all of our criteria to be a valid field. We can scale this up to 2⁸ or 256 elements by using polynomials up to the 7th degree (x⁷). All the maths is the same, just with more terms. The next thing to understand is how we would store polynomials in a computer and how we perform these operations on them.

I pointed out earlier that the coefficients for each term can have the value 0 or 1, and if you consider the coefficients in isolation they count up in a binary sequence. This hints as to how we can represent these 2ⁿ polynomials in a computer, we use a bit array to represent the coefficients.

For GF(2⁸) we need 8 bits, and therefore can be stored in a single byte. In code, this is done using normal unsigned 8 bit integers. The key is to remember they are not normal numbers and you can’t use the normal addition and multiplication operators on them and get the results we want.

It is at this point we can eventually address my initial confusion as to why numbers seemingly did not add up. Let’s work though the first example again:

0001₂ × 0011₂ = 0011₂

That works as expected, and it is completely coincidental that the result is also the same if you do normal binary multiplication. Let's look at the second example:

0011₂ × 0011₂ = 0101₂

And now it makes sense. We were doing multiplication all along, it was just we were doing multiplication in an Galois Field 2⁸ with polynomials represented as bit arrays. Obvious with hindsight.

Code

With the theory nailed down, we are now ready to write some code to perform addition and multiplication in these fields.

Addition it turns out it is really easy. Remember in addition we add the coefficients of each term of the same order. For our bit arrays this means adding the n^th bit in each array together. Also because the coefficients are from GF(2) they can only have the values 0 or 1 and wrap around as appropriate. The following truth table shows what happens to each bit when adding them together:

This is the same truth table as an Exclusive Or (XOR), and therefore we can perform addition by simply performing a bit wise XOR. In C this is the ^ operator. There is no need to even write a function, but if you really wanted to it would like something like this:

unsigned char poly_add(unsigned char a, unsigned char b) {
	return a ^ b;
}

Multiplication is slightly more complicated. We have to really think about what multiplication is and break it down into smaller steps. So let's go back to school once again and do some long multiplication. If we had to multiply two large numbers together using pen and paper, we wouldn’t do it in one step, instead we would do it digit at a time.

     4936
 ×    211
     4936
    49360
 + 987200
  1041496

Note how for each digit of the second number we create a new line, making sure to shift the result one place to the left and add in an extra zero, finally adding the subtotals together. This shifting the subtotals to the left effectively multiplies it by 10, because we are working in base 10. We can do something similar with our bit arrays of polynomials, the effect being the result is multiplied by x.

We can use this bit shifting and addition to perform multiplication. For example to multiply the polynomial x2 + 1 by x2 + x + 1 we would do the following:

    x2 + 1 ⇒     101
x2 + x + 1 ⇒ ×   111
                  101
                 1010
             +  10100 
                11011 ⇒ x4 + x3 + x + 1

This would be correct for GF(2⁸) but incorrect for GF(2³) as this is not an element of that field. We need to reduce this value using our modulus x3 + x + 1, I’ll return to that in a moment. First let’s explore another example:

x2 + x + 1 ⇒     111
    x2 + 1 ⇒ ×   101
                  111
                    0
             +  11100 
                11011 ⇒ x4 + x3 + x + 1

In this example the second subtotal is 0 because the second digit in the second bit array is also 0. Perhaps obvious, but worth noting that this subtotal can be skipped. Keep in mind though that even though there was nothing to add to the total, the bit shifting still happened so when we get to the third subtotal it has been shifted twice.

With all this in mind the code to perform this multiplication is as follows:

unsigned char ploy_mul(unsigned char a, unsigned char b) {
	unsigned char result = 0;

	for (int i=0; i<8; i++) {
		if (b & 0x01) {
			result ^= a;
		}
		a <<= 1;
		b >>= 1;
	}

	return result;
}

The variable result is set to 0 and incrementally updated for each digit in b. The check in the if if (b & 0x01) is doing a bit wise comparison to see if the rightmost bit is set to 1 and only adding a to the result if required. The a <<=1; bit shifts the first number (a) to the left, effectively multiplying it by x for the next iteration. The b >>= 1; bit shifts the second number to the right so the next digit we need to check in the if condition is always the rightmost bit.

This code however has a problem, it doesn’t account for when the result gets too big. We know the solution is to divide the result by the irreducible polynomial and take the remainder, but how to code that and not overflow? Consider the following example in GF(2³) as both a polynomial and the equivalent bit array manipulations.

The insight here is that because the bit shifting is effectively always multiplying by x, we know when an overflow is going to occur whenever the leftmost bit is 1 before we shift. We also know that because we are only ever multiplying by x, the result of the division when required will always be 1 and thus the value to subtract will always be the irreducible polynomial and will always only require one iteration to work out the reminder. We can therefore shortcut the entire division part and just perform a subtraction, which as we know is equivalent to addition for GF(2ⁿ) and for a bit array is a simple bitwise XOR. This makes the code for dealing with overflow remarkably concise.

unsigned char gf2_3_mul(unsigned char a, unsigned char b) {
	unsigned char result = 0;

	for (int i=0; i<3; i++) {
		if (b & 0x01) {
			result ^= a;
		}
		if (a & 0x04) {
			a = (a << 1) ^ 0x0b; // shortcut for getting the remainder
		} else {
			a <<= 1;
		}
		b >>= 1;
	}

	return result;
}

This code works nicely for GF(2³) but would not work for other fields. This is because the loop only checks 3 bits of the bit array and the modulus is encoded in that 0x0b, this is hexadecimal for the binary 1011 or the polynomial x3 + x + 1.

For AES, which uses GF(2⁸), the irreducible polynomial used is x8 + x4 + x3 + x + 1. A new wrinkle in our code is that if we are using 8 bit integers to store our bit arrays, we can’t have an intermediate step with a polynomial higher than the 7th degree. For example we couldn’t store that irreducible polynomial as it would require 9 bits. Similarly, take the byte 1100 0001 and shift it left you will end up with 1000 0010, the leftmost 1 got truncated.

As it happens this is not an issue, if we look back at our examples, the extra term (extra bit) that is generated when multiplying by x is always cancelled out when computing the remainder as part of the modular arithmetic. In our GF(2³) examples, when the left shift generates a 3rd degree term (x³) the irreducible polynomial is subtracted, which also has a 3rd degree term, removes it immediately.

Our code for GF(2³) is using 8 bit integers, so it has the space to briefly create and remove the 3rd degree term. We could however ignore this term, make note when it’s going to be created to trigger the modulo arithmetic but not bother to add the then remove the term. This is exactly the strategy we need to employ for GF(2⁸) where we do not have the space to store the 8th degree term (x⁸) even temporarily.

The code for AES multiplication therefore looks like this:

unsigned char aes_mul(unsigned char a, unsigned char b) {
	unsigned char result = 0;

	for (int i=0; i<8; i++) {
		if (b & 0x01) {
			result ^= a;
		}
		a = (a << 1) ^ (a & 0x80 ? 0x1b : 0);
		b >>= 1;
	}

	return result;
}

When a is bit shifted, a check is made to see if the leftmost bit was 1 and would therefore be truncated and require some modulo arithmetic. If so the polynomial x4 + x3 + x + 1 (encoded in hexadecimal as 0x1b) is added/subtracted from the result. It doesn’t need the x⁸ term because that will have already been truncated/removed by the bit shifting.

13 lines of code

Which brings me to the end of this post. All this effort to work out how to perform addition and multiplication. Why? Well AES encryption requires a structure that supports 256 elements and two operations that can go forwards and (crucially) backwards. For that we need a field and I now know what a field is and how this one works. So with any luck I can now implement the actual algorithm.

From one particular point of view, all I’ve written so far is 13 lines of code. Not massive progress. I could have just copied these lines from any number of text books or websites and moved on. But I didn’t. I wanted to understand them. And I really do. It’s taken six months and eight thousand words to convince myself, but I can now say with well earnt confidence, I now understand the maths behind AES encryption. Well some of it.

TC