Can someone explain to me the relevance of the static matrix used for the mixcolumns operation in aes encryption.i.e the relevance of why the byte is multiplied by 2 + next byte multiplied by 3 + next byte +next byte
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
migrated from stackoverflow.com Aug 2 '12 at 17:16
This question came from our site for professional and enthusiast programmers.
Well, how that matrix works is important for the security properties of AES. To see why it is important, we need to consider state differences, that is, if we consider two different inputs to AES and how they both flow through the cipher, how does those two differ in the internal state of the cipher at various places.
The important property of the mixcolumn operation is that it is a Maximum Distance Separable (or MDS) operation. That is, if we consider two distinct inputs to a single column of the mixcolumn operation, and the two inputs differ in $A$ bytes, and if the two corresponding outputs differ in $B$ bytes, then $A+B \ge 5$.
This implies that if two consider two inputs to a single column of the mixcolumn, if those two inputs differ in a single byte (that is, $A=1$), then the two outputs will always have different values for each byte (that is, $B=4$).
If you go through how this applies to AES, that means that if round $I$, two encryptions has an internal state that differs in a single byte, then at round $I+2$, the two encryptions will have states that differs in all 16 bytes (and hence AES has wonderful avalanche).
More generally, this behavior allows us to prove strength against differential and linear attacks; in that any differential or linear characteristic will necessarily go through a large number of sboxes; the resulting probability that the differential/linear characteristic will survive all those sboxes is negligible.
All this may not be true (or, at least, would be considerably harder to prove), if we replace the mixcolumn operation with an operation that is not MDS.