Principe de MixColumn

MixColumn fait partie (avec ShiftRow) de l'étape de diffusion.
Son but est de faire intervenir de multiples bits dans le codage d'un seul.
Cela premet de rapidement lier (via des transformations matricielles) tout les éléments d'un bloc entre eux.
Le déchiffrement est alors plus complexe si l'on ne connait pas la clé.
On utilisera par la suite la matrice A représentant le bloc de données initial et la matrice B représentant le bloc de données après modification par MixColumn.
$\begin{array}{ccc}A& =& \left(\begin{array}{cccc}{A}_1& A_2& A_3& A_4\\ A_5& A_6& A_7& A_8\\ A_9& A_{10}& A_{11}& A_{12}\\ A_{13}& A_{14}& A_{15}& A_{16}\end{array}\right)\end{array},\begin{array}{ccc}C& =& \left(\begin{array}{cccc}{C}_1& C_2& C_3& C_4\\ C_5& C_6& C_7& C_8\\ C_9& C_{10}& C_{11}& C_{12}\\ C_{13}& C_{14}& C_{15}& C_{16}\end{array}\right)\end{array}$

Explication de la fonction

la fonction MixColumn est une opération d'algèbre linéaire.
Elle suit l'égalité suivante :
$\begin{array}{ccc}{C}_i& =& S\times A_i\end{array}$
Avec i l'indice de colonne pour les matrices A, C. Ainsi que S, une matrice à coefficient fixe spécifique à MixColumn.
Les coefficient de S sont des éléments de GF(2⁸), ils sont ici représentés sous formes hexadécimale :
$\left(\begin{array}{l}{C}_i\\ C_{i+4}\\ C_{i+8}\\ C_{i+12}\end{array}\right)=\left(\begin{array}{cccc}\mathrm{0x02}& \mathrm{0x03}& \mathrm{0x01}& \mathrm{0x01}\\ \mathrm{0x01}& \mathrm{0x02}& \mathrm{0x03}& \mathrm{0x01}\\ \mathrm{0x01}& \mathrm{0x01}& \mathrm{0x02}& \mathrm{0x03}\\ \mathrm{0x03}& \mathrm{0x01}& \mathrm{0x01}& \mathrm{0x02}\end{array}\right)\times \left(\begin{array}{l}{A}_i\\ A_{i+4}\\ A_{i+8}\\ A_{i+12}\end{array}\right) ; i\in \{1,2,3,4\}$
Sous forme d'octet, on a :
$\begin{array}{ccc}0x01& =& {00000001}_2\\ 0x02& =& {00000010}_2\\ 0x03& =& {00000011}_2\end{array}$

• La multiplication par 0x01 ne change rien, il s'agit de l'élément neutre de la multiplication.


• La multiplication par 0x02 équivaut à décaler tout les digits de l'octet de 1 cran vers la gauche. (cela équivaut à multiplier le polynôme correspondant par 2¹).
  Dans ce cas, il est possible que l'on sorte de GF(2⁸) (d'obtenir un polynôme de degré 8).
  Pour cela, il faut réduire par le polynôme caractéristique de l'AES (voir section Maths).


• La multiplication par 0x03 correspond à une multiplication par 0x02, suivit d'une addition (opération XOR dans GF(2⁸)

La somme finale est une suite de XOR, on obtient ainsi :
$\left\{\begin{array}{lcc}{C}_i& =& 0x02·A_i+0x03·A_{i+4}+0x01·A_{i+8}+0x01·A_{i+12}\\ C_{i+4}& =& 0x01·A_i+0x02·A_{i+4}+0x03·A_{i+8}+0x01·A_{i+12}\\ C_{i+8}& =& 0x01·A_i+0x01·A_{i+4}+0x02·A_{i+8}+0x03·A_{i+12}\\ C_{i+12}& =& 0x03·A_i+0x01·A_{i+4}+0x01·A_{i+8}+0x02·A_{i+12}\end{array}\right., i\in \{1,2,3,4\}$

Reversibilité de MixColumn

Si l'on reprend l'expression initiale de MixColumn, on voit qu'il s'agit d'un système à 4 inconnues et 4 équations.
Dans le cas du chiffrement, les inconnues sont C1, C2, C3 et C4. Dans le cas du déchiffrement, il s'agit de A1, A2, A3 et A4.
Inverser MixColumn revient à résoudre le système. Les coefficients de la transformation étant fixes on peut simplement implémenter le même calcul en utilisant la matrice issue de la résolution du système.
On obtient ainsi :
$\begin{array}{ccc}{A}_i& =& S\text{'}\times C_i\end{array}$
$\begin{array}{ccc}Avec S\text{'}& =& \left(\begin{array}{cccc}0x0E& 0x0B& 0x0D& 0x09\\ 0x09& 0x0E& 0x0B& 0x0D\\ 0x0D& 0x09& 0x0E& 0x0B\\ 0x0B& 0x0D& 0x09& 0x0E\end{array}\right)\end{array}$

Le déchiffrement de cette étape devient donc :

$\begin{array}{ccc}\left(\begin{array}{l}{A}_i\\ A_{i+4}\\ A_{i+8}\\ A_{i+12}\end{array}\right)& =& \left(\begin{array}{cccc}0x0E& 0x0B& 0x0D& 0x09\\ 0x09& 0x0E& 0x0B& 0x0D\\ 0x0D& 0x09& 0x0E& 0x0B\\ 0x0B& 0x0D& 0x09& 0x0E\end{array}\right)\times \left(\begin{array}{l}{C}_i\\ C_{i+4}\\ C_{i+8}\\ C_{i+12}\end{array}\right)\end{array}, i\in \{1,2,3,4\}$