In The Design of Rijndael page 39, It describe the design criteria for MixColumns step

  1. Dimensions. The transformation is a bricklayer transformation operatingon 4-byte columns.
  2. Linearity. The transformation is preferably linear over GF(2).
  3. LisDiffusion. The transformation has to have relevant diffusion power.
  4. Performance on 8-bit processors. The performance of the transformationon 8-bit processors has to be high.

However, it does not said why choose modulo $x^4+1$ operation in this step. I guess it is becasue it is the simplist polynomial operation otehr than modulo $x^4$, which will cause multiple zeros. I will glad if anyone tell me my guess is wrong.

  • 1
    $\begingroup$ I think you mean MixColumns step. Please edit so that other people asking this question in the future can find it. $\endgroup$ – user47922 May 18 '17 at 22:49
  • 2
    $\begingroup$ related: crypto.stackexchange.com/questions/15850/… $\endgroup$ – Richie Frame May 18 '17 at 23:32
  • $\begingroup$ Yes, it is MixColumns Step. It is a severe typo, thank for correction and thank e-sushi edit this post. $\endgroup$ – Rikeijin May 19 '17 at 2:14

The idea is that when you're multiplying two four-term (four-byte) polynomials together, you could wind up with a seven-byte polynomial, but you need to reduce it to another four-byte polynomial. They chose $x^4 + 1$ because

$x^i \mod (x^4 + 1) = x^{i \mod 4}$

See this for an example.


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.