# OMAC: multiplication in a finite field - how can I compute the correct polynomial

We explain the notation used in the deﬁnition of OMAC. The value of iL (line 40: i an integer in {2, 4} and L ∈ {0, 1}n) is the n-bit string that is obtained by multiplying L by the n-bit string that represents the number i. The multiplication is done in the ﬁnite ﬁeld GF(2n) using a canonical polynomial to represent ﬁeld points. The canonical polynomial we select is the lexicographically ﬁrst polynomial among the irreducible polynomials of degree n that have a minimum number of nonzero coefﬁcients. For n = 128 the indicated polynomial is x128 + x7 + x2 + x + 1. In that case, 2L = L << 1 if the ﬁrst bit of L is 0 and 2L = (L << 1) ⊕ 012010000111 otherwise, where L << 1 means the left shift of L by one position (the ﬁrst bit vanishing and a zero entering into the last bit). The value of 4L is simply 2(2L). We warn that to avoid side-channel attacks one must implement the doubling operation in a constant-time manner.

I was basically just given that the polynomial to use in the finite multiplication for n = 128 is x128 + x7 + x2 + x + 1. I want my implementation to be abstract in that it isn't reliant on the specifics of the cypher being used. To allow the block size n to be any number rather than hardcoding 128 or a few others, how can I have my software compute the correct polynomial?

-
Blocksize is an esential feature of a block algorithm. Attempting to decouple blocksize from a block algorithm is likely to introduce a weakness. The polynomial is a generator for the finite field GF(2^n). There may be several generators for a particular field, and there are reasons to pick one generator over another. In order to choose a generator you must first identify all generators for a field and then determine which generator has the best characteristics, then get someone to check your work. – this.josh Jun 22 '11 at 7:26
Plus, I'm probably in the wrong place. This is really a math question. – jnm2 Jun 23 '11 at 13:14
Yes this is a math problem, except when picking a polynomial as the generator. In security we are looking for a generator that acts like a Galouis counter, a generator that produces every element of the field once for 2^n (number of elements in the field) operations. – this.josh Jun 23 '11 at 17:59

@D.W. gives the important and correct answer, of course. Do not reimplement your own cryptographic library (or, at least, do it to learn and for fun, but do not trust it !).

Now, for the details, the text you quote actually gives all the details which are needed, albeit in a rather terse mathematical way. The important sentence is this one:

The canonical polynomial we select is the lexicographically ﬁrst polynomial among the irreducible polynomials of degree n that have a minimum number of nonzero coefﬁcients.

When you compute with binary polynomials modulo a polynomial P of degree n, you get a finite field (denoted GF(2n)) only if P is irreducible.

There are 2n binary polynomials of degree n; they can all be written as:

P = p0 + p1X + p2X2 + ... + pn-1Xn-1 + Xn

where each pi is either 0 or 1. Note that for binary polynomials, we compute all values in GF(2), so addition is XOR and multiplication is AND.

For faster implementations, we prefer it when the number of non-zero pi is minimal; it is also better if the non-zero pi are for small values of i. It is easy to see that, for P to be irreducible, p0 must be equal to 1, and there must be an odd number of non-zero pi for i between 1 and n-1. As the EAX specification says, we try all polynomials until we reach one which is irreducible; we begin with the polynomials with only one non-zero pi (there are n-1 of them), and, if none is irreducible, then we try the polynomials with three non-zero pi values (there are (n-1)(n-2)(n-3)/6 of them). And we begin with those where the pi are for the lowest possible values i, i.e. we start at 1+X+X2+X3+Xn.

So all you would have to do would be to enumerate the binary polynomials of degree n, with the minimum number of non-zero coefficients, in lexicographic order, and test them for irreducibility. For that test, see the Handbook of Applied Cryptography, chapter 4, section 4.5.1.

-

Don't. For most people, there is no reason to implement your own crypto library. Get an existing crypto library with an implementation of CMAC (aka AES-OMAC1), and use that code. Implementing it yourself is error-prone (with the risk of security problems) and often misses out on performance optimizations found in standard libraries. For most purposes, there is no reason to implement it yourself, and little reason to use any other cipher than AES, or in particular, a block cipher with anything other than a 128-bit block size.

-