I quote a wikipedi para that says

The operation consists in the modular multiplication of two four-term polynomials whose coefficients are elements of ${\displaystyle \operatorname {GF} (2^{8})} $. The modulo used for this operation is $ x^{4}+1$.

The first four-term polynomial coefficients are defined by the state column ${\displaystyle {\begin{bmatrix}b_{3}&b_{2}&b_{1}&b_{0}\end{bmatrix}}} $, which contains four bytes. Each byte is a coefficient of the four-term so that

${\displaystyle b(x)=b_{3}x^{3}+b_{2}x^{2}+b_{1}x+b_{0}}$

The doubt i have is are $ b_3, b_2,b_1,b_0$ all polynomial in $GF(2^8)$. for example if i have an $8$ bit number $11111111$ does $b_3=1+x+x^2+x^3+x^4$ i.e the polynomial associated with the $5$ most significant bits? i am really confused about this ? can someone explain with any example of how the Mix Columns algo work?


You should consider the field $\textrm{GF}(2^8)$ as a "given", a way to multiply and add bytes (the addition is just XOR, the multiply could be given as a table of 256 by 256 entries; you'll see we need only very few entries:

Then the column represented by $b_3x^3 + b_2x^2 + b_1x+b_0$ is multiplied by $(3x^3 + x^2 + x +2)$ in the usual way, but modulo $x^4+1$ as said, so we consider $x^4$ and $1$ to be the same, as $x^5$ and $x$ etc. and in general $x^n$ is just reduced to $x^{n \pmod{4}}$.

So first the usual multiplication gives

$$ 3b_3 x^6 + (3b_2 + b_3)x^5 + (b_3+b_2+3b_1)x^4 + (2b_3+b_2+b_1+3b_0)x^3 + (2b_2 + b_1 + b_0)x^2 + (2b_1+b_0)x + 2b_0$$

where (!) $3b_3$ is just the multiplication in $\textrm{GF}(2^8)$, so we only need the rows in the multiplication table corresponding to $2$ and $3$ are these are the only non-trivial coefficients that are used in the field multiplications.

Then we can use that $x^6 \equiv x^2, x^5 \equiv x, x^4 \equiv 1$ to get a third degree polynomial (gathering coefficients again):

$$(2b_3 + b_2+b_1+2b_0)x^3 + (3b_3 + 2b_2 + b_1 + b_0)x^2 + (b_3+3b_2+2b_1+b_0)x+ (b_3+b_2+3b_1+2b_0)$$

(maybe some small mistakes here..., check the computations by hand, I'm doing them from screen; less optimal) The additions are still xor's of course. This shows formulae to find the new values of the column from the old one, and if done properly we get a nice circular matrix multiplication. We only need multiplication with a small number of coefficients anyway, also for the inverse, and this multiplication of bytes is indeed in itself a modular bit-polynomial multiplication. The above had multiplications on byte level, so one level of abstraction up.

I think the Wikipedia explanation is quite adequate and covers these points too.

In practice, we either compute it in hardware or using tables in software, never by actually computing with polynomials over finite fields.


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.