Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
2  
$GF(p^n)$ is a set of vectors: the field does not by itself do any computations, it simply exists and it has no inputs and no outputs. $GF(2^8)$, for example, is the set of $256$ $8$-bit bytes. To add two elements of the field, you do a bit-by-bit sum modulo $2$ (a.k.a. XOR) of the two bytes; in this case, subtraction is also the XOR of the bytes. Multiplication (in the form described in my answer) is more complicated to implement. For easier ways, you need to understand more about finite fields (see references in answer by SquareRootOfTwentyThree). –  Dilip Sarwate May 25 '12 at 10:52
    
@DilipSarwate, A field is not just a set of elements. It is a set of elements with operations (typically called addition and multiplication, but not necessarily what you think of when you hear those names). Further, the operations must satisfy certian properties (closed under addition, closed under multiplication, is commutative under addition and multiplication, etc) –  mikeazo May 25 '12 at 11:46
2  
@mikeazo Yes, I know all that. I was trying, in the short space available or comments, to disabuse the OP of the notion that a field is a function. He seems to be thinking that $GF(\cdot)$ is a function that applies to its argument $p^n$ to create something else. In this context, the key point is that the field does not by itself do anything and that it is not a function, it is a set. –  Dilip Sarwate May 25 '12 at 12:02
    
@DilipSarwate, you are correct and I see now where you are going. A field is not an operator. You represent elements of some fields as polynomials, but you don't typically use that polynomial as an operator. –  mikeazo May 25 '12 at 12:06
    
I'm still lost. I understand vectors as a small set of numbers. So, a vector has a size and a set of values - essentially an array. A vector $[a,b,c,d]$ has a length of 4 and four values - $a$, $b$, $c$, and $d$. If a field is a set of vectors, I envision it as: field = array(array(a1,b1,c1,d1),array(a2,b2,c2,d2),...). Is this correct? If so, how are a1, b1, etc. computed initially, ignoring operators? Or do we just populate them with something (e.g. a key) and then do operations on them? –  Polynomial May 25 '12 at 14:40
show 3 more comments

5 Answers 5

up vote 21 down vote accepted

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)$.

share|improve this answer
    
This is an amazing answer. I get it now! :) –  Polynomial May 27 '12 at 9:16
2  
Something makes me uncomfortable about the fact stated in the "specifically, an irreducible monic polynomial of order $n$" fragment of that answer. Such polynomial can be primitive, or not, and that creates two classes of representations of $GF(p^n)$ as vectors of $n$ integers in $[0,p−1]$: those that use a primitive polynomial, and the others; but they are still all isomorphic, and I find that counterintuitive. Is there a simple way to characterize the properties of the two kind of representations? –  fgrieu Dec 16 '12 at 20:36
add comment

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.

share|improve this answer
    
<<*snip*>> - I've put this comment as an update to the question. –  Polynomial May 25 '12 at 5:43
add comment

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).

share|improve this answer
1  
While this is correct, I suppose it doesn't help too much, since it uses some more unknown terms like "quotient ring" and "irreducible polynomial". –  Paŭlo Ebermann May 27 '12 at 10:21
    
But surely an answer not including these terms would be "brushing things under the carpet"? I am not going to write a book about finite fields on here, but instead I have related the notion of finite fields to something much easier to understand, polynomials. It seems to me that the original poster knows what a field actually is so should know what a ring is. The quotient part may be unfamilliar but can read about that (or rely on the fact that there are already ways to implement these). The term "irreducible polynomial" should already be understood...but takes seconds to understand if not. –  fretty May 27 '12 at 10:31
add comment

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.

share|improve this answer
    
+1 for the nice introduction to sage –  moeso Apr 27 at 16:20
add comment

Finite fields are a fascinating subject, but it's not really something you can understand from a forum.

I really recommend you take a book about number theory and spend some time with it. It will help you greatly for the rest of your life.

For instance, I like "A Computational Introduction to Number Theory and Algebra" by Victor Shoup. The whole book is available as PDF, Finite Fields are the subject of Chapter 20. If you have less time, A Course in Number Theory and Cryptography by Neal Koblitz is good too.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.