Représentation algébrique de l’AES

Représentation algébrique de l’AES

Fondements mathématiques

La plupart des opérations dans Rijndael s’effectuent au niveau de l’octet ou sur un mot de quatre octets. L’octet est donc le plus petit élément d’information traité dans l’algorithme. Mathématiquement, ce dernier peut être considéré à la fois comme une chaîne binaire, un vecteur à coefficients dans GF(2) de dimension 8 et un élément de GF(28 ) c’est-à-dire, un polynôme de degré inférieur ou égal à 7 et dont les coefficients sont les bits (voir fig. 3.1 p. 36). La conception de l’AES s’articule autour des corps de Galois [155]. Un corps de Galois, est un corps contenant un nombre fini d’éléments. Toutes les opérations utilisées dans l’AES sont donc décrites par des opérations algébriques sur des corps finis de même caractéristique.  Figure 3.1 – Représentation d’un caractère dans l’AES Avant d’appréhender les opérations arithmétiques de base dans les corps de Galois, décrivons les structures algébriques nécessaires à la compréhension des propriétés des corps finis.

Les groupes

Les groupes constituent la structure algébrique de base des mathématiques, puisque à partir de ceux-ci sont créés les anneaux, les corps, les espaces vectoriels. . . [129] Soit G un ensemble non vide doté d’une loi de composition interne : ◦ : G × G ↦→ G Alors, G est un groupe noté (G, ◦), si : — sa loi de composition interne est associative ; — il existe un élément neutre e tel que e ◦ g = g ◦ e = g, ∀g ∈ G. L’élément e est unique et est aussi nommé élément identité ; — ∀g ∈ G il existe un unique g −1 ∈ G tel que g ◦ g −1 = g −1 ◦ g = e. L’ordre de (G, ◦) est la cardinalité de l’ensemble G. Si l’ordre de (G, ◦) est fini, alors (G, ◦) est un groupe fini. Enfin, un groupe, dont la loi de composition interne est commutative, est un groupe commutatif ou encore appelé groupe abélien. À titre d’exemple, l’ensemble des entiers relatifs Z muni de l’opération d’addition forme un groupe abélien noté (Z, +). Une permutation sur un ensemble non vide E est une bijection de E ↦→ E. L’ensemble des permutations de E, muni de l’opération de composition, forme un groupe nommé groupe symétrique de E et noté SE. Si E est fini et de cardinalité n > 0, n ∈ N, le groupe symétrique de cet ensemble E est nommé groupe symétrique d’indice n, il est noté Sn. L’orde de Sn est n!, les éléments de Sn sont des permutations. Un élément de Sn qui permute deux éléments de E et laisse les autres éléments inchangés est appelé une transposition. Soit deux groupes (G, •) et (H, ⋆), la fonction f : G ↦→ H est un homomorphisme de groupe si ∀g, g′ ∈ G alors f(g • g ′ ) = f(g) ⋆ f(g ′ ). Un homomorphisme de groupe bijectif est appelé isomorphisme. Dans ce cas, G et H sont dit isomorphes, ce qui se note par G ∼= H. Deux groupes isomorphes ont la même structure algébrique et peuvent être considérés comme représentant le même objet algébrique. 

Les anneaux

Soit A un ensemble non vide associé à deux opérations binaires internes + et • de A × A ↦→ A. Alors (A, +, •) est un anneau (voir fig. 3.2 p. 37) si : 37 3.1. Fondements mathématiques — (A, +) est un groupe abélien ; — l’opération • est associative ; — l’opération • est distributive sur + ; — il existe un élément 1 ∈ A tel que 1 • a = a • 1 = a, ∀a ∈ A. Ensemble : E + : E × E ↦→ E • : E × E ↦→ E Anneau commutatif : (E, +, •) Anneau : (E, +, •) Groupe abélien : (E, +) Groupe : (E, +) associatif ∀x, y, z ∈ E (x + y) + z = x + (y + z) elt neutre ∀x ∈ E, ∃0 ∈ E 0 + x = x + 0 = x inverse ∀x ∈ E, ∃ − x ∈ E x + (−x) = (−x) + x = 0 commutatif ∀x, y ∈ E x + y = y + x distributif ∀x, y, z ∈ E x • (y + z) = (x • y) + (x • z) (y + z) • x = (y • x) + (z • y) associatif ∀x, y, z ∈ E (x • y) • z = x • (y • z) elt neutre ∀x ̸= 0 ∈ E, ∃1 ∈ E 1 • x = x • 1 = x commutatif ∀x, y ∈ E x • y = y • x Figure 3.2 – Architecture d’un anneau L’élément identité de (A, +) est 0 et constitue le zéro de l’anneau (A, +, •). L’élément 1 est l’élément identité de l’anneau (A, +, •). Enfin, un anneau est commutatif si sa seconde loi est commutative. L’ensemble des entiers relatifs Z muni des opérations d’addition et de multiplication forme un anneau commutatif noté (Z, +, •). Un anneau commutatif (A, +, •) est un anneau intègre s’il ne contient aucun diviseur de zéro, c’est-à-dire si a • a ′ ̸= 0 ∀a, a′ ∈ A\{0}. Un élément non nul a ∈ A est dit inversible s’il existe a −1 ∈ A tel que a • a −1 = a −1 • a = 1. Soit l’anneau (A, +, •) et I un sous-ensemble non vide de A, I est un idéal de A, noté I ◁ A, si (I, +) est un sous groupe de (A, +) et si ∀i ∈ I et ∀a ∈ A alors Chapitre 3. Représentation algébrique de l’AES 38 i • a ∈ I et a • i ∈ I. Ainsi, quel que soit k ∈ Z, kZ est un idéal de (Z, +, •). Si S est un sous-ensemble non-vide de l’anneau A, alors l’idéal engendré par S est noté ⟨S⟩ et consiste en toutes les sommes finies de la forme ∑ai • si où ai ∈ A et si ∈ S. L’idéal I de l’anneau (A, +, •) est dit principal s’il existe un élément a ∈ A tel que I = a.A. Autrement dit, I est principal s’il peut être engendré par un élément a ∈ A. Un anneau commutatif est dit principal si tous ses idéaux sont principaux. Un anneau intègre dans lequel chaque idéal est un idéal principal est appelé anneau principal. Un anneau A est factoriel s’il est intègre, si tout élément non nul admet une décomposition en produit de facteurs irréductibles et si cette décomposition est unique à permutation près. C’est à dire ∀a ∈ A\{0} il existe u ∈ A∗ et p1, · · · , pr irréductibles tels que a = up1 · · · pr et que cette décomposition est unique.