Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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