Galois field step in XEX mode

Question

I'm reading through the XEX mode spec, and I want to make sure I've understood the $\alpha^j$ step correctly:

$X = E_K(I) \oplus \alpha^j$

$C = E_K(M \oplus X) \oplus X$

where:

• $M$ is the plaintext message
• $I$ is the number of the sector
• $\alpha$ is the polynomial $2^n$ over the finite field $GF(2^{128})$
• $j$ is the block index within the sector

So, to compute $\alpha^j$, assuming that my language has native 128-bit int support, I envision something like this:

UInt128 a_j = 1 << (j % 128);

Is this literally it, or am I missing a key point here?

Answer 1

$GF(2^{128})$ is a finite field with $2^n$ elements. There are a number of ways to represent this field. For example, a binary vector of length 128, or polynomials of degree 127 where the coefficients are 0 or 1. You could even choose to represent them as integers between $0$ and $2^{128}-1$. These are the elements of the finite field. In addition to the elements you need two operations, call them $\boxplus$ and $\boxdot$ (we often call them addition and multiplication). To be a field, the elements must be closed under both operations, associative under both operations, commutative under both operations, there must exist an additive and multiplicative identity, there must exist additive and multiplicative inverses for every element, and multiplication must distribute over addition (see this for additional details).

So for a given representation, you must specify what $\boxplus$ and $\boxdot$ mean and show that the properties I just listed hold.

It is very tempting to want to think of $GF(2^{128})$ as simply the integers modulo $2^{128}$ ($\mathbb{Z}_{2^{128}}$). Part of this probably comes from the fact that $\mathbb{Z}_p$ where $p$ is prime, is in fact a finite field. It turns out that $\mathbb{Z}_{2^{128}}$ is not a finite field. In other words, using integer addition and multiplication modulo $2^{128}$ does not get us all the properties listed above.

So, $\alpha^j\neq 1<<j\ \%\ 128$. You could represent $\alpha$ as a 128 bit integer, but the operations to compute $\alpha^j$ would be very different from simple integer arithmetic. I'd suggest using a finite field library. For more details on the arithmetic, see the other question you asked.