Principe de ByteSub

ByteSub est une application avec les propriétés suivantes :

• Bijective :
  $\begin{array}{ccc}\forall y\in F,& \exists !x\in E;& f\left(\begin{array}{c}x\end{array}\right)=y\end{array}$
  
• Non linéaire :
  $\begin{array}{ccc}ByteSub\left(A\right)+ByteSub\left(B\right)& \ne & ByteSub(A+B)\end{array}$
  

Dans notre cas, les ensembles E et F sont les mêmes. il s'agit de GF(2⁸).
La bijectivité permet de s'assurer que lors du chiffrement tout les éléments aient une image différente.
Ainsi lors du déchiffrement, il n'y aura pas d'incohérence, une fonction bijective étant inversible, tel que son inverse est aussi une fonction bijective.
$\begin{array}{ccc}\forall x\in E,& \exists !y\in F;& f^{-1}\left(\begin{array}{c}y\end{array}\right)=x\end{array}$

La non linéarité permet de se protéger de certaines attaques (voir sources).

Fonctionnement de ByteSub

Le but de ByteSub est d'effectuer une substitution octet (byte) par octet. Cela s'effectue en deux étapes distinctes.
Dans cette partie, on va reprendre A = $\begin{array}{ccc}{10011011}_2& =& 0x9B\end{array}$ , dans le but de créer un exemple.

ByteSub : passage à l'inverse

Tout d'abord on remplace la valeur $A=(a_7 a_6 a_5 a_4 a_3 a_2 a_1 a_0)$ (un mot du bloc de donnée) par son inverse dans GF(2⁸).
Étant donné que nous sommes dans un corps, il faut préciser quelle opération nous utilisons.
Dans ce cas, il s'agit de l'inverse dans le groupe multiplicatif, d'élément neutre 0x01.
Dans ce groupe, 0x00 n'ayant pas d'inverse, il est son propre inverse par convention.
Cela peut se faire via une table :

(Pour passer du binaire a l'héxadécimal, voir l'onglet sur l'algorithme AES).
Celle-ci peut directement être codée "en dur" dans un programme, elle ne varie jamais.
On a donc :
$\begin{array}{c}A=(a_7 a_6 a_5 a_4 a_3 a_2 a_1 a_0)\\ B\text{'}=\left(b{\text{'}}_{7}b{\text{'}}_{6}b{\text{'}}_{5}b{\text{'}}_{4}b{\text{'}}_{3}b{\text{'}}_{2}b{\text{'}}_{1}b{\text{'}}_0\right)=A^{-1}\end{array}$

Exemple :
Si l'on reprend l'inverse de A, on a donc :
A^-1 = $\begin{array}{ccc}B\text{'}={10001000}_2& =& 0x88\end{array}$

ByteSub : fonction non linéaire

Dans cette seconde étape, on modifie la valeur en la multipiant par un vecteur puis en sommant un terme constant, le tout modulo 2.
Le fait que cette fonction soit bijective permettra plus tard le déchiffrement de cette étape.

Ainsi :
$\begin{array}{ccc}Soit B& =& f(B\text{'});\end{array}$
Avec la fonction f() correspondant à :
$\left(\begin{array}{c}b0\\ b1\\ b2\\ b3\\ b4\\ b5\\ b6\\ b7\end{array}\right)\equiv \left(\begin{array}{cccccccc}1& 0& 0& 0& 1& 1& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 1& 1& 0& 0& 0& 1& 1\\ 1& 1& 1& 1& 0& 0& 0& 1\\ 1& 1& 1& 1& 1& 0& 0& 0\\ 0& 1& 1& 1& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1& 0\\ 0& 0& 0& 1& 1& 1& 1& 1\end{array}\right)\times \left(\begin{array}{c}b\text{'}0\\ b\text{'}1\\ b\text{'}2\\ b\text{'}3\\ b\text{'}4\\ b\text{'}5\\ b\text{'}6\\ b\text{'}7\end{array}\right)+\left(\begin{array}{c}1\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 0\end{array}\right) mod 2$

Exemple :
On reprend $\begin{array}{ccc}B\text{'}={10001000}_2& =& 0x88\end{array}$
Après calcul, on va trouver $\begin{array}{ccc}f(B\text{'})=B={00010100}_2& =& 0x14\end{array}$

ByteSub : simplification

Il est possible de simplifier cette étape. En effet, cette transformation f() est une bijection.
Chaque élément de GF(2⁸) possède une image unique et un antécédent unique. De plus, l'inverse d'un élément est unique.
En effet :
$\begin{array}{lll}Soit a,b,c,e\in GF\left(2^8\right);& b,c inverse de a& et e élément neutre\\ Alors& a*b=a*c=e& \\ Ainsi& (b*a)*b=(b*a)*c& car * associative\\ Ainsi& e*b=e*c& car b inverse de a\\ Donc& b=c& car e neutre\end{array}$
L'inverse est donc unique pour chaque élément, pour l'opération *.

Chaque élément de GF(2⁸) a donc un inverse unique et une image unique par f().
L'ensemble GF est finis, il est donc possible de calculer ByteSub pour chacun de ses éléments.
Cela donne la table suivante (ici en notation hexadécimale) :


On peut voir qu'il n'y a aucune symétrie ou de point spécifique.

Exemple :
SI l'on reprend A = $\begin{array}{ccc}{10011011}_2& =& 0x9B\end{array}$
On peut directement faire la correspondance (inverse et passage par f()).
Cela donne bien $\begin{array}{ccc}B={00010100}_2& =& 0x14\end{array}$

Inversibilité de f()

ByteSub étant bijective, il est possible de construire sa fonction inverse.
pour la fonction f(), elle représente un système de 8 inconnues à 8 équations, il est donc possible de le résoudre.
Cela permet d'obtenir la fonction suivante :

$\left(\begin{array}{c}b{\text{'}}_0\\ b{\text{'}}_1\\ b{\text{'}}_2\\ b{\text{'}}_3\\ b{\text{'}}_4\\ b{\text{'}}_5\\ b{\text{'}}_6\\ b{\text{'}}_7\end{array}\right)\equiv \left(\begin{array}{cccccccc}0& 1& 0& 1& 0& 0& 1& 0\\ 0& 0& 1& 0& 1& 0& 0& 1\\ 1& 0& 0& 1& 0& 1& 0& 0\\ 0& 1& 0& 0& 1& 0& 1& 0\\ 0& 0& 1& 0& 0& 1& 0& 1\\ 1& 0& 0& 1& 0& 0& 1& 0\\ 0& 1& 0& 0& 1& 0& 0& 1\\ 1& 0& 1& 0& 0& 1& 0& 0\end{array}\right)\times \left(\begin{array}{c}{b}_0\\ b_1\\ b_2\\ b_3\\ b_4\\ b_5\\ b_6\\ b_7\end{array}\right)+\left(\begin{array}{c}0\\ 0\\ 0\\ 0\\ 0\\ 1\\ 0\\ 1\end{array}\right) mod 2$

Inversibilité de l'inverse

De plus, comme on peut le voir dans la table des inverses, si a inverse de b alors b inverse de a.
On peut donc réutiliser cette table:

Ainsi, il est possible de remonter ByteSub. Tout d'abord en trouvant la fonction inverse f^-1().
Ensuite, de reprendre l'inverse du résultat, pour retomber sur l'élement initial.

Simplification du déchiffrement de ByteSub

De même que pour ByteSub, il est possible de précalculer le résultat pour chaque élément :



Si vous voulez, vous pouvez vérifier :

• qu'aucun élément n'est sa propre image
• qu'aucun élément n'est symétrique
• que la fonction est bien bijective