Galois fields in cryptography

Question

I don't really understand Galois fields, but I've noticed they're used a lot in crypto. I tried to read into them, but quickly got lost in the mess of heiroglyphs and alien terms. I understand they're sets of the form $GF(p^n)$ for $n\geq1$ where $p$ is prime and $n$ is an integer. From what I can tell, they're defined as the following:

$GF(p^n) = [f(0) \bmod p, f(1) \bmod p, \dotsc, f(p^n-1) \bmod p, f(p^n) \bmod p]$

for $f(x) = \sum_{i=0}^{n} \space x^ik_i$, i.e. an $n$-order polynomial with constants $K$.

I've seen mention that these fields are bijective, such that for an input set $A$ there is an output set $B$ containing the same values as $A$, but in a different order.

Is this correct? Does this have applications for creating s-boxes?

Update:
Thanks for the answers so far. I now understand that $GF(p^n)$ is an array of size-$n$ vectors, each element of which is computed as the result of some polynomial mod $p$, but I'm still not clear on the rest of it. I mostly understand how vector manipulation can be done on such a field, but I'm still non the wiser as to how I would use such a finite field, let alone impliment them in code. I don't really understand what $GF(p^n)$ looks like in terms of construction, which I guess is what I'm really looking for. If it's an array of vectors, each element of which is computed by some polynomial, how is the input to that polynomial decided? Is $GF$ a function, into which you provide such a value? Is the input value an integer, a vector, etc? If so, what's the meaning of the input value? How does the index of the vector in the set factor into the computation of its values?

For example:

$GF(p^n)[i] = \begin{bmatrix} v_0\\v_1\\v_2\\...\\v_{n-1} \end{bmatrix}$

Where $i$ is some index into the field, how are the vector elements $V$ computed? What inputs are provided?

Answer 1

The $GF$ in $GF(p^n)$ is not a function — it just stands for "Galois field (of $p^n$ elements)".

As for what a Galois field is, it's a finite set of things (which we might represent e.g. with the numbers from $0$ to $p^n-1$), with some mathematical operations (specifically, addition and multiplication, and their inverses) defined on them that let us calculate with these things as if they were ordinary numbers, but so that the results of the calculations always stay inside the finite set.

Specifically, we require the operations defined on the elements of this finite set to satisfy the field axioms, which include the usual associativity, commutativity and distributivity rules you probably learned in high school algebra class. In particular, we also require every element $a$ to have an additive inverse $-a$ and (if $a \ne 0$) a multiplicative inverse $1/a$, such that $a + (-a) = 0$ and $a \times (1/a) = 1$. Thus, as long as you just stick to algebraic manipulations using these rules, the Galois fields all look exactly like the field of real numbers you're familiar with.

To learn how to do arithmetic (i.e. actual calculations with actual numbers) in Galois fields, it's probably easiest (particularly if you're already familiar with modular arithmetic) to start with the prime Galois fields $GF(p)$. Arithmetic in these fields is simply ordinary addition and multiplication of integers modulo some prime $p$. For example, in $GF(3)$, there are three numbers ($0$, $1$ and $2$) with the following addition and multiplication rules (and their commutative variants):

$$\begin{aligned} 0 + 0 &= 0 & 1 + 1 &= 2 & 0 \times 0 &= 0 & 1 \times 1 &= 1 \\ 0 + 1 &= 1 & 1 + 2 &= 0 & 0 \times 1 &= 0 & 1 \times 2 &= 2 \\ 0 + 2 &= 2 & 2 + 2 &= 1 & 0 \times 2 &= 0 & 2 \times 2 &= 1 \\ \end{aligned}$$

The only unusual rules here are $1 + 2 = 0$, $2 + 2 = 1$ and $2 \times 2 = 1$; those are the cases where, in normal arithmetic, the result would've been equal to or greater than $3$, so it's "wrapped around" by subtracting $3$. From these rules, we can also determine the inverses. It turns out that $-0 = 0$, $-1 = 2$ and $-2 = 1$ (since $1 + 2 = 0$) and $1/1 = 1$ and $1/2 = 2$ (since $2 \times 2 = 1$), so they indeed do exist and belong to the field. (I'll leave verifying that the inverses are all unique, and that these rules indeed also satisfy all the other field axioms, as an exercise.)

Why do we require $p$ to be prime, then? Well, it turns out that if a number $m$ is not prime, then some numbers won't have multiplicative inverses modulo $m$: for example, there is no integer $a$ such that $2 \times a = 1 \pmod 4$. Thus, the integers modulo $m$ don't actually form a field (but only a ring) unless $m$ is prime.

However, if $m$ is a prime power — i.e. a number of the form $m = p^n$, for some prime $p$ and some positive integer $n$ — then we can still save things by changing the rules on how addition and multiplication work. This is where all that stuff about the vectors and polynomials comes in. However, what you should keep in mind is that they don't really represent any added complexity, just alternative ways of looking at things. Fundamentally, we're still dealing with a set of $p^n$ numbers and some arithmetic operations defined on them — it just turns out that, for example, the multiplication rule we'll need to use is pretty easy to describe if we identify each number in the field with a polynomial, at least if you still remember the rules for adding and multiplying (and dividing) polynomials that you may have also learned in high school.

So, let's start with vectors and addition. Given a number $a \in \{0, \dotsc, p^n-1\}$, we can represent it in a natural way with $n$ base-$p$ digits $a_0, \dotsc, a_{n-1}$, such that $$a = a_0 + a_1 p + a_2 p^2 + \dotsb + a_{n-1} p^{n-1}.$$

This is exactly how you'd represent a binary number modulo $2^n$ as a string of $n$ bits. We could also call the string a vector, since that's basically what a vector is: a finite-length sequence of numbers.

Now, when you normally add numbers together digit by digit, you need to keep track of carries. On the other hand, when you add two vectors together, it's simpler: you just add up the corresponding numbers in each vector separately. Now, it just turns out that the addition rule we'll need to use, to make the field axioms work in a field with $p^n$ elements, is exactly this "carryless addition". For example, in $GF(4)$ (which we often write as $GF(2^2)$ to emphasize that $4 = 2^2$ is indeed a prime power) the addition rules look like this:

$$\begin{aligned} 0 + 0 &= 0 & 0 + 2 &= 2 & 1 + 1 &= 0 & 1 + 3 &= 2 & 2 + 3 &= 1 \\ 0 + 1 &= 1 & 0 + 3 &= 3 & 1 + 2 &= 3 & 2 + 2 &= 0 & 3 + 3 &= 0 \\ \end{aligned}$$

They look a lot more logical if you write them out in binary:

$$\begin{aligned} 00 + 00 &= 00 & 00 + 10 &= 10 & 01 + 01 &= 00 & 01 + 11 &= 10 & 10 + 11 &= 01 \\ 00 + 01 &= 01 & 00 + 11 &= 11 & 01 + 10 &= 11 & 10 + 10 &= 00 & 11 + 11 &= 00 \\ \end{aligned}$$

Here you can see that we're just adding up the digits modulo $2$ and ignoring any carries. You might also recognize this "addition" rule as the same operation as bitwise XOR. This is not unique to $GF(4)$; the elements of $GF(2^n)$ for any $n$ can be represented as $n$-bit bitstrings, and their addition as bitwise XOR.

So, now we know how to add numbers in $GF(p^n)$. What about multiplication, then? Well, this is where the polynomials come in. You see, one way to describe the multiplication rule is to imagine that the digits $a_0, \dotsc, a_{n-1}$ of the number $a$ are the coefficients of a polynomial $$a[x] = a_0 + a_1 x + a_2 x^2 + \dotsb + a_{n-1} x^{n-1}$$ with the unknown $x$. (Here, the variable $x$ is purely a formal placeholder; we'll never assign it a value, so you'll never have to worry about "what's $x$?". It's just there so that we can use the high school algebra rules for manipulating polynomials in $x$.)

Then, to multiply two numbers $a$ and $b$, we just take their respective polynomials $a[x]$ and $b[x]$, multiply them together using the high school algebra rules (doing all the internal arithmetic modulo $p$), and take the coefficients of the result. This is all pretty simple: remember that polynomial multiplication is also pretty straightforward, being just like normal digit-by-digit multiplication except that, again, there are no carries.

But wait! Won't the multiplication sometimes give me terms of order $x^n$ or higher? If I include them in the digit string, wouldn't that result in a number larger than $p^n-1$?

Well, yes. That's why there's another step: after the multiplication, we need to reduce the result modulo a suitable polynomial (specifically, an irreducible monic polynomial of order $n$). That is to say, we take the result of the multiplication and divide it by this reducing polynomial (which we can again do with high school polynomial long division), again remembering to do all arithmetic on the coefficients modulo $p$, and keep the remainder (which will be of order $x^{n-1}$ or less). Of course, in practice it's usually more efficient to do the reduction during the multiplication, so that you don't need to store lengthy intermediate results.

OK, so where does that reducing polynomial come from? Well, it turns out that we have some latitude in choosing it, since there are usually several polynomials that will work. Each of them will give a different multiplication rule, although all the fields so constructed (and, more generally, all finite fields with $p^n$ elements) are isomorphic, in the sense that, for any two Galois fields $A$ and $B$ of $p^n$ elements, there's an invertible function $f: A \to B$ mapping one field to the other so that $f(a + b) = f(a) + f(b)$ and $f(a \times_A b) = f(a) \times_B f(b)$, where $\times_A$ and $\times_B$ denote the multiplication operators of the two fields. Thus, when we only care about the general algebraic properties of the field, and not about the specific representation of the numbers, it's common to speak of "the" Galois field of order $p^n$, even though it might have multiple representations.

If you're asked to calculate something in a specific Galois field, the reducing polynomial will normally be given for you. For example, if you're writing an AES implementation, it uses $GF(2^8)$ with the reducing polynomial $x^8 + x^4 + x^3 + x + 1$ (where, since $p=2$, all coefficients are either $0$ or $1$).

If you get to choose your own representation, and thus your own reducing polynomial, you should generally try to pick something that makes the calculations easy, subject to the irreducibility constraints stated above. Often this means picking something with as few non-zero coefficients as possible, and with all those coefficients occurring on low-order terms (except for the $x^n$ term, which must have a coefficient of $1$ for the polynomial to be monic and of order $n$, of course).

I could go into more detail on how to implement multiplication in binary Galois fields $GF(2^n)$, since what I've written above is still on a rather abstract level, and since — especially to someone coming from a programming background — the theory is often more complicated than the actual code (or at least looks that way). However, to be honest, I'm more familiar with the theoretical side of things myself, and in any case this answer is already more than long enough. Wikipedia does have a nice article on finite field arithmetic that you could start with, though.

Oh, and what about Galois fields that are not of order $p^n$ for some prime $p$ and positive integer $n$? Well, it turns out that there aren't any — you just can't satisfy the field axioms if the number of elements has two distinct prime factors. So, alas, there's no such thing as $GF(6)$ or $GF(10)$.

Answer 2

I think there are some gaps and some misunderstandings in what you say. A finite field or Galois field $GF(p^n)$ is a collection of $p^n$ $n$-dimensional vectors. Here, $p$ is a prime, and each coordinate in a vector is an integer in the range $[0,p-1]$; that is, an element of $GF(p)$. Thus, $$\mathbf A = (a_0, a_1, \ldots, a_{n-1}), ~~ a_i \in GF(p)$$ is an element of $GF(p^n)$. Since there are $p$ choices for each $a_i$, we have $p^n$ vectors. Formally, the elements of $GF(p^n)$ constitute a vector space over $GF(p)$. Thus, addition and subtraction in the field is vector addition and subtraction, where the arithmetic in each coordinate is done modulo $p$, that is, in $GF(p)$. Multiplication by a scalar, that is, an element of $GF(p)$ is also straightforward. If $b \in GF(p)$, then $$b\mathbf A = (ba_0, ba_1, \ldots, ba_{n-1}).$$ Multiplication and division of elements of $GF(p^n)$ is slightly trickier to explain and to understand. We can associate a polynomial $A(x)$ with each element $\mathbf A$ where $$\mathbf A = (a_0, a_1, \ldots, a_{n-1}) \leftrightarrow A(x) = a_0 + a_1x + a_2x^2 + \cdots + a_{n-1}x^{n-1}.$$ Then, $\mathbf A\cdot \mathbf B = \mathbf C$ where $$\mathbf C \leftrightarrow C(x) = A(x)B(x) \bmod M(x)$$ where $M(x) = m_nx^n + m_{n-1}x^{n-1} +\cdots + m_1 x + m_0$ is an irreducible polynomial of degree $n$ with coefficients in $GF(p)$. Here, irreducible means that $M(x)$ cannot be factored into two polynomials both of degree $< n$ and with coefficients in $GF(p)$. For convenience, $M(x)$ is generally chosen to be a monic polynomial meaning the coefficient of $x^n$ is $1$. I assume you know that $A(x)B(x) \bmod M(x)$ mean that we multiply $A(x)$ and $B(x)$ to get a polynomial of degree as much as $2n-2$, divide by $M(x)$, and take the remainder polynomial, which is of degree $< n$, as $C(x)$.

Turning to division, since $B(x)$ and $M(x)$ cannot have a common factor of positive degree, their greatest common divisor is $1$. Bezout's identity shows that the gcd $1$ can be expressed as $$1 = B(x)D(x) + E(x)M(x) \Rightarrow B(x)D(x) \equiv 1 \bmod M(x)$$ so that $D(x)$ acts as the multiplicative inverse of $B(x)$. Thus, division is defined as multiplication by the inverse: $$\mathbf A/\mathbf B = \mathbf A\cdot \mathbf B^{-1} = \mathbf A\cdot \mathbf D \leftrightarrow A(x)D(x) \bmod M(x).$$

Finally, with regard to your statement "I've seen mention that these fields are bijective,", please note that a field is a set, not a mapping. Mappings or functions can be bijective etc., sets cannot. What was probably intended to be conveyed to you was that the function that is being computed is a bijective mapping from $GF(p^n)$ to itself: each element of $GF(p^n)$ is mapped onto a unique image in $GF(p^n)$. A simple example of such a mapping is $T: \mathbf A \to T(\mathbf A) = \mathbf A\cdot\mathbf B$ where $\mathbf B$ is a fixed nonzero element of $GF(p^n)$. Thus, the forward map sends $\mathbf A$ to $\mathbf A\cdot\mathbf B$ while the reverse map sends $\mathbf G$ to $\mathbf G\cdot\mathbf B^{-1} = \mathbf G\cdot \mathbf D.$ Of course, for cryptographic applications, one might want to use more complicated bijective functions than this simple one used as an illustration. An s-box operating over $GF(2^8)$ sends bytes (elements of $GF(2^8)$) to bytes.

Answer 3

In addition to some of the other answers, what has helped me the most in understanding finite fields, or any algebraic structure for that matter is playing with them. For this, I have found Sage to be indispensible.

So, looking at Galois Fields in Sage goes something like this:

sage: f = GF(2^8, 'x')
sage: f
Finite field in x of size 2^8
sage: f.random_element()
x^7 + x^4 + x^3 + x^2 + 1
sage: x = f.gen()
sage: a = f(x^2 + x)
sage: b = f(x^4 + x^2 + 1)
sage: a
x^2 + x
sage: b
x^4 + x^2 + 1
sage: a+b
x^4 + x + 1
sage: a*b
x^6 + x^5 + x^4 + x^3 + x^2 + x

I could go on and on. Sage is built on python so for the most part it uses python syntax.

From this you can see how the field works. The field is made up of polynomials of degree $n-1$. The coefficients in the polynomial are integers modulo $p$. Now, how it is actually represented in a computer might vary. For $GF(2^8)$, it is quite easy to store all the coefficients (which are either $0$ or $1$) of a single element in a single byte of memory. Other fields where $p>2$ are different. You might store those in a computer as a vector of the coefficients of the polynomial.

Answer 4

Ok so you probably know that fields are interesting structures to study...they are places where arithmetic works nicely. Most cryptosystems depending heavily on numbers usually must take the numbers from some field in order for things to work out.

Now there are many fields with infinitely many elements, $\mathbb{Q}, \mathbb{R}, \mathbb{C}...$, but what might a finite field look like?

Well the situation is actually quite simple, it turns out that such a field can only have $p^n$ elements where $p$ is some prime and $n$ is some positive integer. Also for each possibility of $p,n$ there exists exactly one field of size $p^n$ (upto isomorphism, i.e. relabelling of the elements in a coherent way).

This field is usually denoted $GF(p^n)$ or $\mathbb{F}_{p^n}$. It is just notation for "the field of order $p^n$". Note that $\mathbb{F}_p$ is simply the integers mod $p$, a field we already know about.

Now how might we construct $\mathbb{F}_{p^n}$ in general? Well using a bit of abstract algebra we can construct such a field as follows:

1) Make a polynomial $f$ of degree $n$ that is irreducible mod $p$.

2) Consider the quotient ring $\mathbb{F}_p[x]/\langle f\rangle$. This must be a field since $f$ is irreducible over $\mathbb{F}_{p}$ and also this field must have $p^n$ elements by the fact that $f$ has degree $n$.

3) Thus by uniqueness of such fields $\mathbb{F}_{p^n} \cong \mathbb{F}_p[x]/\langle f\rangle$.

So you can implement the field arithmetic by just working with this polynomial quotient ring (something that a computer can handle easily).