AES demonstration tool

Modulo et congruences

L'opération modulo retourne le reste d'une division entière.
ex : 12 % 5 = 2 (% est le symbole de l'opération modulo)

$\begin{array}{l} D a n s ℤ, \\ A \equiv B m o d P \Leftrightarrow A = B + k \cdot P; k \in ℤ \end{array}$
Cela se lit : A congru à B modulo P.
Soit, que A et B sont équivalents, à de multiples soustractions ou additions de P près.

Ainsi on peut définir :

12 congru à 5 modulo 7 : $12 \equiv 5 m o d 7 \Leftrightarrow 12 + (- 1) * 7$
12 congru à 33 modulo 7 : $12 \equiv 33 m o d 7 \Leftrightarrow 12 + (3) * 7$
12 congru à -2 modulo 7 : $12 \equiv - 2 m o d 7 \Leftrightarrow 12 + (- 2) * 7$

Dans la suite de ce cours, il faut garder à l'esprit que toutes les opérations de somme seront modulées par 2.
Ainsi, tous coefficients rencontrés sera égal a 0 ou 1.
De plus, dans ce cas, la somme et la différence sont équivalentes ( pour tout élément X et -X sont congrus à X modulo 2).

Il est aussi possible de faire des congruences sur des polynômes
En effet, si les polynômes ont des coefficients entiers, alors la factorisation, soustraction, addition et division sont possibles.

Les ensembles : Groupes

Un groupe G est un ensemble muni d'une opération binaire * telle que :

L'opération * est une loi de composition interne. Cela signifie que :
$\forall α, β \in G; α * β \in G$
L'operation * est associative, soit :
$\forall a, b, c \in G; a * (b * c) = (a * b) * c$
L'opération * possède un élément neutre, soit :
$\exists e \in G, \forall α \in G; α * e = e * α$
L'opération * admet l'existence d'un élément inverse :
$\forall α \in G, \exists α^{- 1}; α * α^{- 1} = α^{- 1} * α = e$
Si l'opération * est commutative, G est abélien :
$G a b é l i e n \Leftrightarrow \forall α, β \in G; α * β = β * α$

Les ensembles : Corps

Un corps F est un ensemble tel que :

Tout élément de F forme un groupe additif , avec 0 comme élément neutre pour l'opération +
Tout élément de F (sauf 0) forme un groupe multiplicatif, avec 1 comme élément neutre pour l'opération *
Quand les deux groupes sont joins, la loi de distributivité s'applique :
$\forall a, b, c \in F; a * (b + c) = a * b + a * c$

Corps de Gallois

Un corps de Gallois GF(N) est un corps avec un nombre finis d'élément
Pour l'AES, on utilise un corps premier. C'est à dire un corps de la forme : $G F (p^{n})$ avec p premier et $n \in ℕ$

Représentation sous forme de polynômes

Tout nombre entier peut aisément être exprimé sous forme de puissance de 2, et ainsi être converti en binaire.
En binaire, une suite de 8 bits est un octet.
Le bit le plus à droite d'un octet est appelé bit de poids faible. Il correspond à 2⁰ = 1.
Le bit le plus à gauche d'un octet est appelé bit de poids fort. Il correspond à 2⁷ = 128.
Dans le cadre de l'AES, on utilise GF(2⁸), soit une extension du corps de gallois GF(2¹).

Pour représenter ces éléments on utilise des polynômes dont les coefficients sont compris dans GF(2) (soit {0 ; 1}).
On peut donc représenter tout ces polynômes tels que :
$\begin{matrix} A \in G (2^{8}); & A = a_{7} \cdot X^{7} + a_{6} \cdot X^{6} + a_{5} \cdot X^{5} + a_{4} \cdot X^{4} + a_{3} \cdot X^{3} + a_{2} \cdot X^{2} + a_{1} \cdot X^{1} + a_{0} \cdot X^{0} \end{matrix}$
avec $a_{i} \in {0; 1}$
Les opérations usuelles étant possibles avec des polynômes, GF(2⁸) représente l'ensemble des polynômes de degré inférieur ou égal à 7 (et de coefficients < 2).
Pour la compréhension future des applications, il faut bien différencier les polynômes de leur signification.
Pour l'AES, les polynômes sont issus de la conversion en binaire du texte clair.
Cela ne correspond donc pas à une valeur de l'ensemble des entiers naturels. Il faut rester dans GF(2⁸), donc rester sous forme polynômiale.

Calculs polynômiaux : Somme

La somme se fait par puissance :
$A + B = (a_{7} + b_{7}) * X^{7} + (a_{6} + b_{6}) * X^{6} + (a_{5} + b_{5}) * X^{5} + (a_{4} + b_{4}) * X^{4} + (a_{3} + b_{3}) * X^{3} + (a_{2} + b_{2}) * X^{2} + (a_{1} + b_{1}) * X + (a_{0} + b_{0}) * 1$
Comme les coefficients prennent leurs valeurs dans GF(2), la somme est modulée par 2.
Elle correspond alors à un "OU" exclusif.
En effet :

Si les coefficients valent tout les deux 0, alors leurs somme donnera 0.
$0 \equiv 0 m o d 2 \Leftrightarrow 0 + (0) * 2$
Dans le cas où ils sont tout les deux égaux à 1, alors la somme congru à 0 modulo 2.
$2 \equiv 0 m o d 2 \Leftrightarrow 0 + (- 1) * 2$
Dans le cas où les coefficients sont 0 et 1, alors la somme congru à 1 modulo 2.
$1 \equiv 1 m o d 2 \Leftrightarrow 0 + (0) * 2$

Ce qui correspond à la table de vérité du "OU exclusif".

Calculs polynômiaux : Multiplication

Dans le cas de la multiplication, il est possible de dépasser 2⁷. Pour compenser cela, on module la multiplication par un polynôme :
$\forall A, B \in G (2^{8}); A * B = A (X) \times B (X) m o d P (X)$
Avec P(X) un polynôme irréductible (ici : qui ne peut pas être factorisé). Dans le cas de l'AES, ce polynôme fait partie du standard. il s'agit de :
$P (X) = X^{8} + X^{4} + X^{3} + X + 1$

Exemple :
$\begin{array}{cl} S o i t & A = X^{5} + X^{4} + 1, B = X^{5} + X^{2} + X \\ d o n c & A \cdot B = (X^{5} + X^{4} + 1) \cdot (X^{5} + X^{2} + X) \\ d o n c & A \cdot B = X^{10} + X^{9} + X^{7} + X^{6} + X^{6} + X^{5} + X^{5} + X^{2} + X \end{array}$

Les coefficients se trouvent dans GF(2), on applique donc tout d'abord l'opération "+" modulée par 2 (correspondand à un XOR)
$\begin{array}{cl} A i n s i A \cdot B & = X^{10} + X^{9} + X^{7} + (X^{6} + X^{6}) + (X^{5} + X^{5}) + X^{2} + X \\ = X^{10} + X^{9} + X^{7} + X^{2} + X \end{array}$

Dans l'exemple, le polynôme a un degré supérieur à 7. Il faut donc utiliser le polynôme P(x) donné précédemment pour moduler.
Pour moduler ce résulat, il faut éléver P(x) a un degré égal au polynôme à réduire.
$\begin{array}{l} A i n s i, d e g r é (A \cdot B) = 10, d e g r é (P) = 8 \\ o r 10 - 8 = 2 \\ A i n s i, A \cdot B \equiv A \cdot B + P \cdot X^{2} m o d P \end{array}$
$\begin{array}{cl} O r A \cdot B + P \cdot X^{2} & \equiv X^{10} + X^{9} + X^{7} + X^{2} + X + (X^{8} + X^{4} + X^{3} + X + 1) \cdot X^{2} m o d P \\ \equiv X^{10} + X^{10} + X^{9} + X^{7} + X^{6} + X^{5} + X^{3} + X^{2} + X^{2} + X m o d P \\ \equiv X^{9} + X^{7} + X^{6} + X^{5} + X^{3} + X m o d P \end{array}$

On peut voir que le degré du polynôme est toujours strictement supérieur à 7.
On répète donc l'opération.
$\begin{array}{cl} O r A \cdot B + P \cdot X & \equiv X^{9} + X^{7} + X^{6} + X^{5} + X^{3} + X + (X^{8} + X^{4} + X^{3} + X + 1) \cdot X m o d P \\ \equiv X^{9} + X^{9} + X^{7} + X^{6} + X^{5} + X^{5} + X^{4} + X^{3} + X^{2} + X + X m o d P \\ \equiv X^{7} + X^{6} + X^{4} + X^{3} + X^{2} m o d P \end{array}$

Désormais, le résultat est d'un degré strictement inférieur à 8. Il est donc compris par construction (degré inférieur ou égal à 7 et coefficients inférieurs à 2) dans le corps de Gallois utiisé (GF(2⁸)).
Il est donc possible de le représenter sous sa forme binaire (sous la forme d'un octet), avec seulement ses coefficients :
$R = (1 1 0 1 1 1 0 0)_{2}$