Finite fields

Ciphers work on bytes, and they need to do arithmetic with them: multiply two bytes, divide one by another, and always get a byte back. Ordinary arithmetic doesn’t do that (200 × 200 is far too big for a byte), and the obvious fix, wrapping round, breaks division. This page builds the arithmetic that does work, a finite field, starting from a clock. Along the way it answers a question left open on the DSP site’s pseudo-random bits page: why only some choices of taps make a shift register go round every state.

1 · Clocks with a prime number of hours

A clock wraps round: on a 12-hour clock, 9 o’clock plus 5 hours is 2 o’clock. Arithmetic that wraps like this is called arithmetic mod n (for “modulo”): do the sum as usual, then keep only the remainder after dividing by n. On a clock of 7, 5 + 4 = 9, which leaves 2 over after dividing by 7, so 5 + 4 = 2 (mod 7). Multiplying works the same way: 3 × 5 = 15 = 2 × 7 + 1, so 3 × 5 = 1 (mod 7).

The answers always stay on the clock, which is the point. Adding and multiplying are always possible. Subtracting is too: going backwards round the clock. The interesting one is dividing. Dividing by 3 means multiplying by whatever undoes multiplying by 3, its inverse: the number that 3 times gives 1. On a clock of 7, that’s 5, since 3 × 5 = 1. So ”÷ 3” is ”× 5”.

The multiplication table on a clock of n: each cell is (row × column) mod n. A 1 (highlighted) means the row’s number has an inverse: the column it’s in. On a clock of 7, every row but 0 has exactly one 1, so every non-zero number can be divided by. Switch to a clock of 8: the even rows have no 1, and some of their cells are 0 (red) although neither number is: 2 × 4 = 8, which is 0 on a clock of 8.

The difference is that 7 is prime (it can’t be split into smaller whole numbers multiplied together) and 8 isn’t (8 = 2 × 4). On a clock of 8, two non-zero numbers can multiply to 0, and a number that can be multiplied to 0 can’t have an inverse: if 2 had one, multiplying both sides of 2 × 4 = 0 by it would give 4 = 0. On a clock with a prime number of hours, that never happens, and every non-zero number has an inverse.

Arithmetic where you can add, subtract, multiply and divide (by anything but 0), and the usual rules hold, is called a field. Ordinary fractions are a field; so is a clock of 7. A field with a finite number of things in it is a finite field, and a clock with a prime number of hours, p, gives one: written GF(p), after Évariste Galois, who studied them around 1830.

2 · Bytes as polynomials

A byte has 256 values, and 256 isn’t prime, so a clock of 256 won’t do. The way round it is to stop reading a byte as a number, and read it as a polynomial: a sum of powers of x, one for each bit that’s 1.

the byte 0101 0111 = x⁶ + x⁴ + x² + x + 1

(reading the bits from the right: bit 0 is the 1, bit 1 the x, bit 2 the x², and so on). FIPS-197, the standard that defines AES, writes bytes in hex in braces: that byte is {57}.

The coefficients, the bits, are each 0 or 1, and they do their arithmetic on a clock of 2: 1 + 1 = 0. So adding two polynomials is adding their bits, place by place, on a clock of 2: XOR. Nothing carries from one place to the next. Subtracting is the same as adding (going back 1 on a clock of 2 is going forward 1), so it’s XOR too.

Multiplying is long multiplication, done the same way: one row for each 1 in the second number, shifted along by its place, and the rows added with XOR. With no carries. A small example by hand:

(x + 1) × (x + 1) = x² + x + x + 1 = x² + 1, since x + x = 0

in bits: 11 × 11 = 110 XOR 11 = 101, where ordinary multiplication gives 3 × 3 = 9 = 1001

This is carry-less multiplication. Because nothing carries, it’s simpler for hardware than ordinary multiplication, and modern processors have an instruction for it.

3 · Keeping it to a byte

Multiplying two bytes this way gives up to 15 bits. To get back to a byte, do what the clock did: divide, and keep the remainder. Here the divisor is a polynomial of degree 8, so every remainder has degree 7 or less: a byte. Dividing is long division with XOR: while the number is too long, XOR in the divisor, shifted to line up with its top bit. Each XOR clears the top bit, so it gets shorter until it fits.

Which polynomial to divide by? The same rule as for clocks: it must be one that can’t be split into smaller polynomials multiplied together. Such a polynomial is irreducible, the polynomial version of prime. Otherwise two non-zero bytes can multiply to 0, just as 2 × 4 did on the clock of 8: x² + 1 = (x + 1)(x + 1), so with x² + 1 as the divisor, (x + 1) × (x + 1) leaves no remainder at all. AES uses x⁸ + x⁴ + x³ + x + 1, which is irreducible, and the arithmetic of bytes it gives is the finite field GF(2⁸): 256 values, all of them bytes, and every non-zero one with an inverse.

FIPS-197’s own example, {57} • {83}, a line at a time. First the carry-less long multiplication: a row for each 1 in b, added with XOR. Then the reduction: each time the result is longer than 8 bits, XOR in AES’s polynomial (orange), lined up with the top bit, until it fits. The answer is {c1}, as in the standard. Try other bytes: the answer is always a byte, and the tests check this multiply against the site’s AES code for thousands of pairs.

Multiplying by x alone is the most common step, and it’s just a shift left by one place: if a 1 falls off the top (past x⁷), XOR in the polynomial’s lower bits, {1b}, to put it back. That’s called xtime in the standard, and any multiplication can be built from it, as the long multiplication above was.

And every non-zero byte has an inverse: the byte that multiplies with it to give {01}.

The inverse of every byte in GF(2⁸) with AES’s polynomial: the row gives the first hex digit, the column the second, and the cell is the inverse. Click a byte: its inverse is highlighted too (inverses come in pairs), and the tiles check that they multiply to {01}. FIPS-197’s example is {53}, whose inverse is {ca}. 0 has none, as on a clock.

This table is the first half of AES’s S-box, the step that scrambles each byte: take the byte’s inverse, then shuffle its bits in a fixed way. (The block ciphers page puts it to work.) Inverses are chosen because they’re about as far from a simple pattern as arithmetic gets, which is what a cipher needs.

4 · Primitive: the powers that go everywhere

Now take powers of x: 1, x, x², x³, … reduced each time by the polynomial. With finitely many values, they must eventually come back to 1 and go round again. The number of steps that takes is the order of x. There are 2ⁿ − 1 non-zero values for a polynomial of degree n, so the order can be at most that. If x goes through every one of them before coming back, the polynomial is called primitive.

That’s exactly what an LFSR does. Read a shift register’s bits as a polynomial: each step shifts every bit along one place, which is multiplying by x, and the feedback XORs in the taps when a bit falls off the end, which is reducing by the polynomial the taps describe. (That’s the “Galois” way of wiring the register. The DSP page wires it the “Fibonacci” way, XORing the taps into the incoming bit; it’s a rearrangement of the same thing, and goes round in the same number of steps.) Started from 00001, which is 1, after k steps the register holds xᵏ, reduced. It’s back where it started when xᵏ = 1: an LFSR’s period is the order of x, and it visits every non-zero state exactly when its polynomial is primitive.

Every non-zero value for the chosen polynomial, round a circle (1 at the top, the rest in order), and the powers of x (or of x + 1) joined in turn until they come back to 1. Start with the DSP page’s taps 5 and 3, x⁵ + x³ + 1: the path goes through all 31. Try the other 5-bit choices, which are the 16 rows of the DSP page’s table: the period there is the number of powers here, every time (checked in the tests). Slide Show the first down to watch the path drawn a step at a time.

So which polynomials are primitive? Two facts settle it for 5 bits:

A reducible polynomial can’t be. It isn’t a field, and its register behaves like smaller registers, one for each factor, running side by side; it comes back to the start when all of them do. x⁵ + x + 1 = (x² + x + 1)(x³ + x² + 1): the parts have periods 3 and 7, so the whole has period 21, the first number both divide.
For an irreducible polynomial, the order divides 2ⁿ − 1. In a field, multiplying by x can be undone, so it moves every non-zero value round a loop, and every loop is as long as the one through 1 (multiply that loop by any value a, and it becomes the loop through a). The loops share out all 2ⁿ − 1 values equally, so their length divides 2ⁿ − 1.

For 5 bits, 2⁵ − 1 = 31 is prime, so the order of x divides 31: it’s 1 or 31, and it isn’t 1 (x isn’t 1). Every irreducible polynomial of degree 5 is primitive. There are 6 of them, and they’re the 6 rows of the DSP table that go all the way round.

Eight bits is different: 255 = 3 × 5 × 17 isn’t prime, so an irreducible polynomial can have x go round a shorter loop instead, of a length that divides 255. Of the 30 irreducible polynomials of degree 8, 16 are primitive. AES’s isn’t: x comes back to 1 after 51 steps. It doesn’t need to be, since AES only needs a field, not a long register. And in the same field, x + 1, {03}, does go through all 255. Choose AES’s polynomial in the figure, then powers of x + 1. There’s a 4-bit example too: x⁴ + x³ + x² + x + 1 is irreducible, but x goes round in 5 steps, not 15.

5 · Where fields turn up

AES does its arithmetic in GF(2⁸): the S-box starts from inverses, and its MixColumns step multiplies by fixed bytes (see block ciphers).
Reed–Solomon codes, which correct errors on CDs, QR codes and in deep-space links, treat a block of data as a polynomial over GF(2⁸) (error-correcting codes on the DSP site).
CRCs are the remainder after dividing a message, as one long polynomial, by a fixed one: the long division of section 3 (the CRC section of the DSP site’s LFSR page).
Maximal-length LFSRs use primitive polynomials, as section 4 showed: for noise, for scrambling, and for the codes radar and GPS use.

Summary

A field is arithmetic where adding, subtracting, multiplying and dividing (by anything but 0) all work.
A clock with a prime number of hours is one: GF(p). With a non-prime number, some numbers multiply to 0 and can’t be divided by.
A byte is a polynomial with bits for coefficients. Adding is XOR; multiplying is long multiplication with XOR (no carries); dividing by an irreducible polynomial and keeping the remainder keeps every answer a byte. That’s GF(2⁸), AES’s arithmetic: {57} • {83} = {c1}.
Powers of x go round a loop; its length is the order of x, and an LFSR’s period. A primitive polynomial sends x through all 2ⁿ − 1 non-zero values. When 2ⁿ − 1 is prime (as for 5 bits), every irreducible polynomial is primitive; for 8 bits, 16 of the 30 are, and AES’s isn’t.