Génération d’équations booléennes pour l’AES

Génération d’équations booléennes pour l’AES

« Let it further be agreed, that by the combination xy shall be represented that class of things to which the names or descrip- tions represented by x and y are simultaneously applicable. Thus, if x alone stands for « white things », and y for « sheep », let xy stand for « white sheep » ; and in like manner, if z stand for « hor- ned things », and x and y retain their previous interpretations, let zxy represent « horned white sheep », i.e. that collection of things to which the name « sheep », and the descriptions « white » and « horned » are together applicable. »est appelée variable booléenne si elle n’accepte que des valeurs appartenant à B, c’est-à-dire, si et seulement si xÀ titre d’exemple, la S-box de l’AES est une fonction booléenne vectorielle avec n = m = 8.Enfin, nous pouvons définir une fonction booléenne aléatoire comme étant une fonction booléenne f dont les valeurs sont des variables aléatoires indépendantes et identiquement distribuées, c’est-à-dire := 16 fonctions boo- léennes de degré deux. Ces 16 fonctions booléennes sont présentées dans le ta- bleau de la figure 4.1 page 61. Parmi les fonctions booléennes de degré 2, les plus connues sont les fonctions OR, AND et XOR (voir fig. 4.3 p. 62), (voir fig. 4.4 p. 62) et (voir fig. 4.2 p. 61). Le programme que nous avons développé pour réaliser ces visualisations est disponible sur Internet [81, VisBool3d]. Il a pour objectif de représenter les fonctions booléennes de degré deux en trois dimen- sions. La hauteur des colonnes correspond à la valeur obtenue en appliquant la fonction booléenne choisie à l’abscisse et à l’ordonnée correspondante.Le support supp(f ) d’une fonction booléenne est l’ensemble des éléments x tel que f (x) ̸= 0, le poids de Hamming wt(f ) d’une fonction booléenne est le cardinal de son support et nous avons donc :

Il existe de multiples représentations des fonctions booléennes [66]. Nous allons nous intéresser à la plus simple – la table de vérité – et à celle que nous utiliserons par la suite – une représentation dans GF (2).Les différentes valeurs prises par une fonction booléenne peuvent être présentées sous la forme d’un tableau appelé table de vérité. La table de vérité caractérise une fonction booléenne.Une fonction booléenne peut également être présentée sous la forme d’une suite de conjonctions comprenant des disjonctions, des négations et/ou des variables. Il s’agit alors de la forme normale conjonctive (CNF). Ainsi, la séquence f = (a∨b)∧(¬a∨b) est la forme normale conjonctive de la fonction f . À l’inverse, une fonction booléenne peut être présentée sous la forme d’une suite de disjonctions comprenant des conjonctions, des négations et/ou des variables. Il s’agit alors de la forme normale disjonctive (DNF). Ainsi, la séquence g = (a ∧ b) ∨ (¬a ∧ b) est la forme normale disjonctive de la fonction g. Les CNF et DNF existent et ne sont pas uniques [66].Intéressons nous maintenant à la représentation des fonctions booléennes dans GF (2).L’ensemble B = {0, 1} associé aux opérations ∧, ∨ et ¬ est l’algèbre boo- léenne Best la taille de son support. Enfin, la distance de Hamming entre deux fonctions booléennes f et g est la taille de l’ensemble {x ∈ F.

Cette représentation des fonctions booléennes dans GF (2) est appelée expansion de Reed-Muller ou polynômes de Zhegalkin ([152] page 169) ou, plus couram- ment, forme normale algébrique ou Algebraic Normal Form (ANF) en anglais. Le degré de AN F (f ) correspond au plus haut degré des monômes de AN F (f ) à coefficients non nuls. Enfin, la forme normale algébrique d’une fonction boo- léenne existe et est unique.En résumé, toute fonction booléenne peut être représentée, de façon unique, par sa forme normale algébrique sous la forme de l’équation :Après cette présentation des fonctions booléennes, nous disposons des outils né- cessaires à l’élaboration de systèmes d’équations booléennes décrivant l’Advanced Encryption standard. Afin d’avancer progressivement nous allons commencer par appliquer notre méthode sur le mini-aes puis nous l’étendrons à l’AES.