Playing with Finite Fields (or, "tfw gf(2^8)")

It’s been a bit! Cryptography is fun, but so is coding theory, so we’re gonna take a dive in that direction starting today.

If you’ve ever scanned a QR code before, you’ve probably noticed that you don’t need to get a very good picture of the code to have it work. In fact, as Wikipedia shows, you can literally tear off part of the code and it will still scan fine.

The trick is error correction codes. These are special algorithms for encoding information. If certain parts of the message are lost or modified, the original message can still be decoded. There is a limit to how much damage can be done to the encoded message, but as long as the damaged message is “close enough” to the undamaged one, the original message can be decoded from it.

Today begins our journey to implement such a code from scratch. We’ll go right for the one QR codes use, called a Reed-Solomon code. These algorithms are built around finite fields–in our case the field \(\operatorname{GF}(2^8)\)–so we’ll start by explaining finite field operations today.

A first date with \(\small{\operatorname{GF}(2^8)}\)

First, what is the finite field \(\operatorname{GF}(2^8)\)?

Simply put, it’s the unique field of order \(2^8 = 256\). (Don’t worry about the unique part! We’ll show now that it exists, and at the end that it’s unique.)

To work with this field, we want an explicit construction. Let \(\mathbb{Z}_2\) be the integers mod 2, i.e. \(\mathbb{Z}/2\mathbb{Z}\). Then we can define

where \(f(X) \in \mathbb{Z}_2[X]\) is any irreducible polynomial of degree \(8\).

We note this is indeed a field, and that by subtracting off multiples of \(f(X)\), every element of this field can be uniquely represented by a polynomial of degree \(< 8\) in \(\mathbb{Z}_2[X]\). Moreover, no matter what irreducible degree \(8\) polynomial we choose for \(f(X)\), we’ll get the same field up to isomorphism.

To make this a little more concrete, one element of \(GF(2^8)\) might be given by the polynomial

and another might be given by the polynomial

To keep things simple, we’ll tend to conflate an element of our field with the polynomial of degree \(< 8\) representing it. We’ll also fix a “standard” choice of \(f\):

We can add \(g\) and \(h\) (remember the coefficients are mod 2) in \(\operatorname{GF}(2^8)\) to get

Since the degree is still \(< 8\), there’s no need to reduce. To multiply \(f\) and \(g\), we can perform the multiplication in \(\mathbb{Z}_2[X]\) and then reduce mod \(f\):

This reduction can be done by polynomial long division, taking the remainder of \(g(X) \cdot h(X)\) divided by \(f(X).\)

Lastly, for inverses, we can use the extended Euclidean algorithm. Given a polynomial \(g(X) \in \mathbb{Z}_2[X],\) the extended Euclidean algorithm finds \(a(X), b(X) \in \mathbb{Z}_2[X]\) such that

where the latter inequality holds since \(f(X)\) is irreducible. In this case, \(b(X) g(X) \in 1 + (f(X))\), so \(b(X)\) is inverse to \(g(X)\) in \(\operatorname{GF}(2^8)\).

Coding it up!

With just this, we have enough to begin writing our own implementation of \(\operatorname{GF}(2^8)\)! We’ll do it in Python (of course) and represent polynomials as lists of coefficients, starting with the highest-degree monomial.

First, our modulus…

# MOD is the coefficients of the modulus we choose for GF(2^K),
# which here is x^8 + x^4 + x^3 + x + 1
MOD = [1, 0, 0, 0, 1, 1, 0, 1, 1]

…and some basic utility functions…

# trim leading zeros from a polynomial (list of coefficents, 
# starting with the largest-degree monomial)
def _trim(poly):
    if _is_zero(poly):
        return []

    return poly[-(_degree(poly) + 1):]


# test if a polynomial is zero
def _is_zero(poly):
    return all([coeff == 0 for coeff in poly])

Next, a function to get the degree of a polynomial:

# get the degree of a polynomial 
def _degree(poly):
    if _is_zero(poly):
        return None

    # get the highest-degree monomial with non-zero coefficient
    exps = range(len(poly) - 1, -1, -1)
    degree = max([exp for exp, coeff in zip(exps, poly)
                  if coeff == 1])
    return degree

Now we can get into the real nitty-gritty. Adding two polynomials in \(\mathbb{Z}_2[X]\) is just xoring, but since our input polynomials might be different lengths, we’ll want to zero-pad our arguments first:

# add two binary polynomials (i.e. as elts of Z/2Z[X])
def _add(poly_a, poly_b):
    # zero-extend the shorter
    len_diff = len(poly_a) - len(poly_b)
    if len_diff > 0:
        poly_b = [0] * len_diff + poly_b
    elif len_diff < 0:
        poly_a = [0] * (-len_diff) + poly_a

    # just xor each coefficient
    return [coeff_a ^ coeff_b 
            for coeff_a, coeff_b in zip(poly_a, poly_b)]

Next, multiplying in \(\mathbb{Z}_2[X]\). To do this, we’ll create a result polynomial called prod and accumulate partial sums into it. To we multiply \(a(X)\) and \(b(X)\), we can simply take each monomial in \(a(X)\), multiply them by \(b(X)\) (which just consists of “shifting over” the coefficients, since each monomial has a coefficient of \(1\)), and sum the results.

# multiply two binary polynomials
def _multiply(poly_a, poly_b):
    # create a product with all zeros
    prod = [0 for _ in 
            range((len(poly_a) - 1) + (len(poly_b) - 1) + 1)]

    # go through all self's terms
    exps = range(len(poly_a)-1, -1, -1)
    for exp, coeff_a in zip(exps, poly_a):
        # if a term is nonzero
        if coeff_a == 1:

            # create a partial sum by shifting other's coefficients
            part_sum = poly_b + exp * [0]
            part_sum = (len(prod) - len(part_sum)) * [0] + part_sum

            # add it into the product
            prod = _add(prod, part_sum)

    return prod

Now, we want a function to reduce one polynomial mod another using long division. We can do this by repeatedly taking our modulus, “shifting” it up (i.e. multiplying it by some power of \(X\)) until it’s the same degree as our polynomial, and then subtracting out the shifted modulus. We’ll also record what multiple we took of the modulus, and total that up into a quotient.

# divide one polynomial by another
def _reduce(poly, mod):
    # get mod degree
    mod_degree = _degree(mod)

    # remove leading zeroes from mod
    mod = _trim(mod)

    # create quotient
    quot = [0 for _ in range(len(poly))]

    # long division to reduce
    while True:
        # get poly degree
        poly_degree = _degree(poly)

        # if we're fully reduced, break
        if poly_degree is None or poly_degree < mod_degree:
            break

        # shift mod to cancel out the highest monomial
        shift_amount = poly_degree - mod_degree
        shift_mod = mod + [0] * shift_amount

        # subtract result out of poly
        poly = _add(poly, shift_mod)

        # add corresponding value to quotient
        quot[-(shift_amount + 1)] = 1

    return quot, poly

We now have all the groundwork laid! Let’s define a class for elements of \(\operatorname{GF}(2^8).\) The only attribute of the class is a list of coefficients, again starting with the highest-degree monomial. (Also, __str__ and __repr__ are safe to ignore, but I wanted to include them just for completeness.)

class QRFiniteField:
    """
    An element of the finite field GF(2^8).

    Attributes
    ----------
    coeffs : list[int]
        A list of binary coefficients, starting with highest-degree
        monomial, of the element of GF(2^8).
    """

    def __init__(self, coeffs):
        self.coeffs = _trim(coeffs)

    def __str__(self):
        if _is_zero(self.coeffs):
            poly = '0'
        else:
            # get list of exponents, then monomials
            exps = range(len(self.coeffs) - 1, -1, -1)
            monos = [f'x^{exp}' if exp != 0 else '1'
                     for coeff, exp in zip(self.coeffs, exps)
                     if coeff == 1]

            # join together with plusses
            poly = ' + '.join(monos)
        return poly

    def __repr__(self):
        # add some context for repr
        return f'<value {self} in field GF(2^8)>'

Adding in our finite field is just as in \(\mathbb{Z}_2[X]\):

    def __add__(self, other):
            # adding is just adding binary polynomials
            coeffs = _add(self.coeffs, other.coeffs)
            return QRFiniteField(coeffs)

Multiplying is the same, but now with reduction:

    def __mul__(self, other):
            # multiply as regular binary polynomials
            prod = _multiply(self.coeffs, other.coeffs)

            # reduce the product
            _, prod = _reduce(prod, MOD)

            # return the result
            return QRFiniteField(prod)

Lastly, to compute inverses, we just implement the extended Euclidean algorithm.

    def inv(self):
            """
            Compute the inverse of this element in GF(2^8).

            Returns
            -------
            QRFiniteField:
                The inverse of this element.
            """
            # use extended euclidean method
            # set initial values
            r_last, r_cur = self.coeffs, MOD
            s_last, s_cur = [1], []  # polynomials 1, 0

            # iterate until we're done
            while True:
                # calculate next values
                q_cur, r_next = _reduce(r_last, r_cur)
                s_next = _add(s_last, _multiply(q_cur, s_cur))

                if _is_zero(r_next):
                    # quit if no remainder
                    break
                else:
                    # otherwise, step forward
                    r_last, r_cur  = r_cur, r_next
                    s_last, s_cur = s_cur, s_next

            # the inverse is stored in s_cur at the end
            return QRFiniteField(s_cur)

Finally, we can run some tests and assert things work:

if __name__ == '__main__':
    # run a basic test from Wikipedia, Finite Fields
    a = QRFiniteField([0, 1, 0, 1, 0, 0, 1, 1])
    b = QRFiniteField([1, 1, 0, 0, 1, 0, 1, 0])

    assert a.inv().coeffs == b.coeffs
    assert (a * a.inv()).coeffs == [1]

And lo and behold, things really work! If you’re curious, or want to play with the code, it’s available at this repository. I’ll be adding code there in the next entries in this series.

For the curious reader, there are certainly lots of ways to optimize finite field arithmetic. The C example here on Wikipedia shows a neat trick for speeding up multiplication in \(\operatorname{GF}(2^8)\), which performs multiplication and reduction simultaneously.

A little math, as a treat

I promised proofs, and here they are! These aren’t critical to understanding how to work with \(\operatorname{GF}(2^8)\) in practice, but since I couldn’t find somewhere that had all these arguments in one place, I thought I’d collect them here for the curious reader:

\(\operatorname{GF}(2^8)\) is a field: To see that \(\operatorname{GF}(2^8)\) is a field, it sufficies to show that \((f(X))\) is a maximal ideal in \(\mathbb{Z}_2[X]\). This is true, because if \((f(X))\) weren’t maximal, it would be contained in some maximal ideal \(\mathfrak{m}\) containing \(g(X) \notin (f(X)).\) But since \(f(X)\) is irreducible, it is coprime to any such polynomial \(g(X)\). By Bezout’s lemma, we can find \(a(X), b(X) \in \mathbb{Z}_2[X]\) such that

But then since \(f(X), g(X) \in \mathfrak{m}\), we have \(1 \in \mathfrak{m}\), a contradiction. Thus \(\operatorname{GF}(2^8)\) is a field.

Elements of \(\operatorname{GF}(2^8)\) are represented by polynomials of degree \(< 8\): Next, we claim any element of this ring can be uniquely represented by a polynomial of degree \(< 8\). Indeed, if \(g(X) \in \mathbb{Z}_2[X]\) is a representative of some element of \(\operatorname{GF}(2^8)\), then we can use polynomial long division to write

where \(a(x), r(x) \in \mathbb{Z}_2[X]\) and \(\operatorname{deg} r(x) < 8.\) Since \(g(X)\) and \(r(X)\) differ by a multiple of \(f(X)\), then \(r(X)\) is also a representative of our element of \(\operatorname{GF}(2^8)\). This shows our claim.

These representatives are unique: Moreover, we claim any two elements with distinct representatives of degree \(< 8\) are distinct. If this wasn’t the case, we’d have equal elements of \(\operatorname{GF}(2^8)\) with representatives \(g(X), h(X)\) which are distinct but both have degree \(< 8.\) Subtracting \(g\) and \(h\), we would get a representative \(g(X) - h(X) \neq 0\) of \(0 \in \operatorname{GF}(2^8)\) with degree \(< 8\). But this is impossible, as the quotient map

only sends multiples of \(f(X)\) to \(0\), meaning \(g(X) - h(X)\) can’t be a representative of \(0\).

\(\operatorname{GF}(2^8)\) is well defined: Lastly, we want to show that our choise of \(f(X)\) doesn’t matter. It is sufficient to show the stronger statement that all finite fields of order \(2^8\) are isomorphic. Take any field \(F\) of order \(2^8\). \(F\) must have characteristic \(2\) (as \(F\)’s characteristic must divide its order). We claim that \(F\) is isomorphic to the splitting field of

It sufficies to show that every element of \(F\) is a root of \(h(X)\), as then \(h(X)\) must split into

And indeed, \(0 \in F\) is clearly a root of \(h(X)\), and any other \(a \in F^\times\) must have order dividing \(\lvert F^\times \rvert = 2^8 - 1,\) meaning \(a\) is a root of \(X^{2^8 - 1} - 1\) and thus also a root of \(h(X) = X^{2^8} - X.\) Since splitting fields are unique up to isomorphism, we have all fields of order \(2^8\) are isomorphic.

Thanks for reading! Let me know if you liked this article, or if there’s any improvements I can make for future ones. 🦊