3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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\}$$

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Mayank Varia Aug 4 '13 at 16:20
  • $\begingroup$ 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. $\endgroup$ – Ruby Aug 7 '13 at 21:02
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.