A group is the basic algebraic structure in abstract algebra, but there are many more. The only other algebraic structure you need to be familiar with is that of a field, specifically that of a finite field. This type of algebraic structure is frequently used in cryptography, such as in the Advanced Encryption Standard. The latter is the main symmetric encryption scheme that you will encounter in practice.

A field is derived from the notion of a group. Specifically, a field is a set of elements S equipped with two binary operators and , which meets the following conditions:

Note that, as with groups, the definition of a field is very abstract. It makes no claims about the types of elements in S, or about the operations and . It just states that a field is any set of elements with two operations for which the three above conditions hold. (The “zero” element in the second Abelian group can be abstractly interpreted.)

So what might be an example of a field? A good example is the set , or defined over standard addition (in place of above) and standard multiplication (in place of above).

First, meets the condition for being an Abelian group over addition, and it meets the condition for being an Abelian group over multiplication if you only consider the non-zero elements. Second, the combination of the set with the two operators meets the distributive condition.

It is didactically worthwhile to explore these claims by using some particular values. Let's take the experimental values 5, 2, and 3, some randomly selected elements from the set , to inspect the field . We will use these three values in order, as needed to explore particular conditions.

Let’s first explore if equipped with addition is an Abelian group.

The set equipped with addition clearly appears to be an Abelian group. Let’s now explore if equipped with multiplication is an Abelian group for all the non-zero elements.

The set clearly seems to meet the rules for being an Abelian group when conjoined with either addition or multiplication over the non-zero elements.

Finally, this set combined with both operators seems to meet the distributive condition. Let’s take 5, 2, and 3 as our values. We can see that .

We have now seen that equipped with addition and multiplication meets the axioms for a finite field when testing with particular values. Of course, we can also show that generally, but will not do so here.

A key distinction is between two types of fields: finite and infinite fields.

An infinite field involves a field where the set S is infinitely large. The set of real numbers equipped with addition and multiplication is an example of an infinite field. A finite field, also known as a Galois field, is a field where the set S is finite. Our example above of is a finite field.

In cryptography, we are primarily interested in finite fields. Generally, it can be shown that a finite field exists for some set of elements S if and only if it has elements, where is a prime number and a positive integer greater than or equal to one. In other words, if the order of some set S is a prime number ( where ) or some prime power ( where ), then you can find two operators and such that the conditions for a field are satisfied.

If some finite field has a prime number of elements, then it is called a prime field. If the number of elements in the finite field is a prime power, then the field is called an extension field. In cryptography, we are interested in both prime and extension fields. [2]

The main prime fields of interest in cryptography are those where the set of all integers is modulated by some prime number, and the operators are standard addition and multiplication. This class of finite fields would include , , , , , , and so on. For any prime field , the set of integers of the field is as follows: .

In cryptography, we are also interested in extension fields, particularly any fields with elements where . Such finite fields are, for instance, used in the Rijndael Cipher, which forms the basis of the Advanced Encryption Standard. While prime fields are relatively intuitive, these base 2 extension fields are probably not for anyone unfamiliar with abstract algebra.

To start, it is indeed true that any set of integers with elements can be assigned two operators that would make their combination a field (as long as is a positive integer). Yet, just because a field exists does not necessarily mean that it is easy to discover or particularly practical for certain applications.

As it turns out, particularly applicable extension fields of in cryptography are those defined over particular sets of polynomial expressions, rather than some set of integers.

For instance, suppose that we wanted an extension field with (i.e., 8) elements in the set. While there might be many different sets that can be used for fields of that size, one such set includes all unique polynomials of the form , where each coefficient is either 0 or 1. Hence, this set S includes the following elements:

So S would be the set . What two operations can be defined over this set of elements to ensure their combination is a field?

The first operation on the set S () can be defined as standard polynomial addition modulo 2. All you have to do is add the polynomials as you normally would, and then apply the modulo 2 to each of the coefficients of the resulting polynomial. Here are some examples:

The second operation on the set S () that is needed for creating the field is more complicated. It is a kind of multiplication, but not standard multiplication from arithmetic. Instead, you have to see each element as a vector and understand the operation as the multiplication of those two vectors modulo an irreducible polynomial.

Let’s first turn to the idea of an irreducible polynomial. An irreducible polynomial is one that cannot be factored (just as a prime number cannot be factored into components other than 1 and the prime number itself). For our purposes, we are interested in polynomials that are irreducible with respect to the set of all integers. (Note that you may be able to factor certain polynomials by, for example, the real or complex numbers, even if you cannot factor them using integers.)

For instance, consider the polynomial . This can be rewritten as . Hence, this is not irreducible. Now consider the polynomial . Using only integers, there is no way to further factor this expression. Hence, this is an irreducible polynomial with respect to the integers.

Next, let’s turn to the concept of vector multiplication. We will not explore this topic in depth, but you just need to understand a basic rule: Any vector division can take place as long as the dividend has a degree higher than or equal to that of the divisor. If the dividend has a lower degree than the divisor, then the dividend can no longer be divided by the divisor.

For instance, consider the expression . This clearly reduces further as the degree of the dividend, 6, is higher than the degree of the divisor, 5. Now consider the expression . This also reduces further, as the degree of the dividend, 5, and the divisor, 5, are equal.

However, now consider the expression . This does not reduce further, as the degree of the dividend, 4, is lower than the degree of the divisor, 5.

On the basis of this information, we are now ready to find our second operation for the set .

I have already said that the second operation should be understood as vector multiplication modulo some irreducible polynomial. This irreducible polynomial should ensure that the second operation defines an Abelian group over S and is consistent with the distributive condition. So what should that irreducible polynomial be?

As all vectors in the set are of degree 2 or lower, the irreducible polynomial should be of degree 3. If any multiplication of two vectors in the set yields a polynomial of degree 3 or higher, we know that modulo a polynomial of degree 3 always yields a polynomial of degree 2 or lower. This is the case because any polynomial of degree 3 or higher is always divisible by a polynomial of degree 3. In addition, the polynomial that functions as the divisor has to be irreducible.

It turns out that there are several irreducible polynomials of degree 3 that we could use as our divisor. Each of these polynomials defines a different field in conjunction with our set S and addition modulo 2. This means you have multiple options when using extension fields in cryptography.

For our example, suppose that we select the polynomial . This indeed is irreducible, because you cannot factor it using integers. In addition, it will ensure that any multiplication of two elements will yield a polynomial of degree 2 or less.

Let’s work through an example of the second operation using the polynomial as the divisor to illustrate how it works. Suppose that you multiply the elements with in our set S. We, then, need to calculate the expression . This can be simplified as follows:

We know that can be reduced as the dividend has a higher degree (4) than the divisor (3).

To start, you can see that the expression goes into a total of times. You can verify this by multiplying by , which is . As the latter term is of the same degree as the dividend, namely 4, we know this works. You can calculate the remainder of this division by as follows:

So after dividing by a total of times, we have a remainder of . Can this be further divided by ?

Intuitively, it might be appealing to say that can no longer be divided by , because the latter term seems larger. However, remember our discussion on vector division earlier. As long as the dividend has a degree larger or equal to the divisor, the expression can be further reduced. Specifically, the expression can go into exactly 1 time. The remainder is calculated as follows:

You might be wondering why evaluates to and not . Remember that the first operation of our field is defined modulo 2. Hence, the subtraction of two vectors yields exactly the same result as the addition of two vectors.

To sum up the multiplication of and : When you multiply those two terms, you get a degree 4 polynomial, , which needs to be reduced modulo . The degree 4 polynomial is divisible by exactly times. The remainder after dividing by exactly times is . This is indeed an element in our set .

Why would extension fields with base 2 over sets of polynomials, like in the example above, be useful for cryptography? The reason is that you can view the coefficients in the polynomials of such sets, either 0 or 1, as elements of binary strings with a particular length. The set S in our example above, for example, could be viewed instead as a set S that includes all binary strings of length 3 (000 through 111). The operations on S, then, can also be used to perform operations on these binary strings and produce a binary string of the same length.

[2] Extension fields become very counterintuitive. Instead of having elements of integers, they have sets of polynomials. In addition, any operations are performed modulo some irreducible polynomial.