# How to Compute C^2 in AES MixColumns Matrix?

In mix Columns we have:

$$C(x) = \{03\}X^3 + \{01\}X^2 + \{01\}X^1 + \{02\}$$

In Viktor Fischer's Paper on MixColumn and InvMixColumn Resource Sharing, in page 2, Equation 8, it's been said that $C^2(X)$ can be computed as follows: $$C^2(x) = \{04\}X^2 + \{05\}$$ Can anybody explain why is that?

-

hi Ruby i know how it comes. But before that i assume you have a good knowledge of finite field.

Actually, it's the problem of how to calculate $$C^2(x) = (\{03\}X^3 + \{01\}X^2 + \{01\}X^1 + \{02\})^2$$. Becuase the character of $K$(as in the paper) is 2, so $$C^2(X)=(\{03\}X^3)^2+(\{01\}X^2)^2+(\{01\}X^1)^2+(\{02\})^2$$. But you have to know the meaning of $\{03\}$ $\{02\}$ and $\{01\}$. They are elements of $F_2^8$. For example $\{03\}$ stands for $x+1$, so $(x+1)^2=x^2+1=\{05\}$. Like this we get:$$C^2(X)=\{05\}X^6+\{01\}X^4+\{01\}X^2+\{04\}$$ Next as $R=K[X]/(X^4+1)$, you have to put them in $R$ by $mod(X^4+1)$$(X^j mod (X^4+1)=X^{j mod 4}). so we get:$$C^2(X)=\{05\}X^2+\{01\}+\{01\}X^2+\{04\}$$. Next as \{05\}=x^2+1,\{01\}=1,\{04\}=x^2, so when we 'add'(this add in the finite field means XOR)then we get:$$C^2(x) = \{04\}X^2 + \{05\}$$- Good answer. One minor quibble with the statement "the character of K": the correct mathematical term is characteristic. See: en.wikipedia.org/wiki/Characteristic_(algebra). – Mayank Varia Aug 4 '13 at 16:20 Complete and accurate asnwer! and it also solved another problem! I had no idea what is the use of$mod(X^4+1)$and here I understand. – Ruby Aug 7 '13 at 21:02 thank you for pointing out this quibble @Mayank Varia – T.B Aug 8 '13 at 8:10 If you recall the notation defined in AES specifications (http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf), your question can be rewritten as: Given$C(x)=(a+1)\cdot x^3+x^2+x+a$in the finite field$GF(2^8)$defined as$GF(2)[a]$with$a^8 + a^4 + a^3 + a + 1=0$, check that$C^2\equiv a^2\cdot x^2+a^2+1 \pmod{x^4+1}\$.

Here is some PARI/GP code that does the computation:

C=((a+1)*x^3+x^2+x+a)*Mod(1,2)*Mod(1,a^8 + a^4 + a^3 + a + 1)*Mod(1,x^4+1)
lift(lift(lift(C^2)))


As expected the result is a^2*x^2 + (a^2 + 1).

-