Why are these two calculations in $GF(2^5)$ not equal

Question

I have a quick question about Galois fields, since there seems to be something I have misunderstood way back in university.

Addition and subtraction in Galois fields are both done using XOR operations. They are the same.

Multiplication with $2$ are done by shifting the bits of a value once to the left and reducing with the irreducible polynomial, when the value "overflows" the size of the galois field.

Example that explains what I do not understand then:

Assume we have the Galois field $GF(2^5)$ and the irreducible polynomial $x^5+x^2+1$ (in bits: $100101$).

We also have the value $4$ (in bits $00100$).

Now, if I want to calculate $4*15$ within $GF(2^5)$, I can do it by: \begin{array}{ccll} T1 & = 00100 & = 4 & \\ T2 & = 01000 & = (T1)*2 & = 4*2\\ T4 & = 10000 & = (T2 )*2 & = 4*4\\ T8 & = 00101 & = (T4 )* 2 & = 4*8. \end{array} We had to reduce here. \begin{array}{} T16 & = 01010 & = (T8) * 2 & = 4*16\\ T15 & = 01110 & = T16-T1 & = 4*15 \end{array} Now, however we could have calculated it instead by doing: $$T15 = T8 + T4 + T2 + T1$$

which would give the result: $$11001 = 00101 + 10000 + 01000 + 00100$$

How come we get the value $11001$ by doing it one way, and $01110$ by doing it another? Both seems valid within the math rules defined for Galois fields.

I encountered this problem while implementing a mix columns operation in a cipher, where this difference caused me to produce different ciphertexts than the expected test-vectors.

Answer 1

$T16-T1\neq T15$. You are doing binary arithmetic when the field is not binary numbers, you've just encoded them as binary. In your field, it is not true that $16-1 = x^4 - x = 1+x+x^2+x^3=15$.

For instance, in any field of characteristic $2$, $T1+T1=0\neq T2$. You can't do that kind of addition. You are essentially confusing $\mathbb GF(32)$ with $\mathbb Z/32\mathbb Z$. They are very different things.

It seems to me that you are asking:

In the field $F=\mathbb F_2[x]/\langle x^5+x^2+1\rangle$, what is $x^2(1+x+x^2+x^3)$?

You get $$\begin{align}x^2\cdot 1&=x^2\\x^2\cdot x&=x^3\\ x^2\cdot x^2&=x^4\\ x^2\cdot x^3&=x^5=x^2+1 \end{align}$$

So $x^2(1+x+x^2+x^3)=x^2+x^3+x^4+(1+x^2)=1+x^3+x^4$.

You can't encode $x^4$ as "$16$" and $1\in F$ as "$1$" and simply do binary subtraction yielding $x^4-1=1+x+x^2+x^3$.