ALGORITHME DE CHIFFREMENT SYMETRIQUE : LE RINJDAEL

Télécharger le fichier pdf d’un mémoire de fin d’études

ALGORITHME DE CHIFFREMENT SYMETRIQUE : LE RINJDAEL

Introduction et historique d’AES

En janvier 1997, le NIST (National Institut of Standards and Technologies) lança un appel d’offre pour un algorithme qui remplacerait le DES qui commençait à être désuet. Ce nouvel algorithme, l’AES (Advanced Encryption Standard) devait naturellement être plus sécuritaire mais aussi, il devait être simple et convenir à toutes sortes d’ordinateurs vu qu’il était destiné à être rendu public. La différence majeure résidait dans la clé qui devait être composée de 128, 192 ou 256 bits, soit nettement davantage que la clé du DES.
Le 15 juin 1998, une vingtaine de projets avaient été proposés soit par des entreprise, comme IBM, des groupes de chercheurs universitaires ou par des petits groupes de savants. Pendant deux ans, les experts évaluent les différents algorithmes.
Le 2 octobre 2000, le NITS annonce alors l’algorithme retenu: Rijndael, créé par deux belges, à savoir Joan Daemen et Vincent Rijmen.
Le Rijndael, ou le AES, est de la même forme que le DES, mais il utilise deux fois plus de bits, soit 128. Ceci augmente le niveau de difficulté pour trouver la clé car elle est deux fois plus longue. De plus, en plus de simplement multiplier le message par la clé comme on le faisait auparavant avec le DES, on inflige au message codé une série d’opérations bijectives connues de l’encodeur et du décodeur. Ainsi, les messages peuvent encore se promener de l’expéditeur jusqu’au récepteur sans craindre du déchiffrement, du moins pour l’instant.[2]

Description générale

Principe de conception

La sécurité d’un cryptogramme ne doit pas se poser sur la téchnique de chiffrement elle-même, donc l’algorithme, puisque l’algorithme peut être retrouvé tôt ou tard, c’est ce qui rend les chiffrement de César ou celui de Vingenère pas du tout sûr.
En effet, un schéma qui serait à la fois sûr et efficace doit se poser sur la clé de chiffrement, ainsi même si un attaquant a en sa possession l’algorithme, sans la clé le déchiffrement du cryptogramme reste impossible.
En outre, Claude Shannon a montré que : « la combinaison de confusion et diffusion permettait d’obtenir une sécurité convenable ».
La confusion : est le fait de masquer la relation entre le clair et le chiffré, ce sont les chiffrements par substitution qui utilisent principalement le système de confusion.
Le diffusion : c’est cacher la redondance en répartissant l’influence d’une clé sur tout le chiffré.[2]

Disposition de l’algorithme AES

Pour faciliter la description de Rijndael, il faut disposer les octets des blocs selon une matrice de M = [4, Nb] et les octets de la clé selon une matrice K = [4, Nk], où Nb et Nk valent 4, 6 ou 8 selon les longueurs respectives des blocs et de la clé. [11]

Opérations élémentaires

La substitution d’octet

La substitution d’octet s’applique à chaque octet de la matrice du bloc que l’on chiffre. Chaque octet est vu comme un élément du corps 256 (le choix du polynôme définissant ce corps est fixé). On calcule l’inverse de chaque octet dans ce corps (la valeur 0 est laissé inchangé) et on applique une transformation F2 linéaire sur le résultat. [6]

Le décalage de lignes

Le décalage de lignes consiste à décaler cycliquement par la gauche la deuxième ligne d’un cran, la troisième ligne de deux crans (trois si nb = 8), et la quatrième ligne de trois crans (quatre si nb = 8). La première ligne reste inchangée. [6]

L’opération sur les colonnes

L’opération sur les colonnes est définie en considérant chaque colonne comme un polynôme de degré inférieur à 4 sur F256. On multiplie alors cette colonne par un polynôme fixé modulo 1 [12]

Dérivation de clés partielles

Là encore, il est pratique de disposer les octets des clés partielles en une matrice constituée de 1 colonnes de quatre octets chacune. Les Nk premières colonnes sont remplies par les octets de la clé. Pour calculer les colonnes suivantes, on prend les octets de la dernière colonne remplie, on les permute, et on applique la substitution décrite précédemment à chacun d’eux. Les colonnes de rang Nk+2 à 2k sont obtenues de proche en ajoutant (XOR) les colonnes 2 à Nk à la colonne précédente. On obtient les colonnes suivantes en ajoutant successivement la deuxième, puis la troisième, ainsi de suite jusqu’à la Nk-ième. Les blocs de Nk colonnes suivants sont obtenus de manière semblable.[7]

Modes opératoires

Le chiffrement se fait par blocs, sachant qu’un message ou fichier n’est pas composé uniquement d’un seul bloc.

ECB

La façon la plus immédiate pour chiffrer le message est de le chiffrer par bloc successive, avec la même clé. Toutefois cette méthode, dite ECB (Electronic Code-Book), présente des inconvénients. En particulier, lorsque deux blocs du message (ou de deux messages) clair sont identiques. C’est visible sur le chiffré. De plus un attaquant actif peut permuter des blocs chiffrés et/ou en supprimer de telle façon que le clair modifié ait encore un sens, du sens initial. La méthode ECB a toutefois l’avantage d’être parallélisable, de laisser la liberté de chiffrer-déchiffrer les blocs dans n’importe quel ordre et, en cas de perte d’un bloc chiffré, de ne pas bloquer le déchiffrement des blocs restants.[4]

CBC

Pour pallier ces inconvénients, on utilise souvent des modes opératoires permettant de chiffrer en chaînes les blocs. Ainsi, avant le chiffrement d’un bloc, le mode CBC (Cipher Bloc Chaining) consiste à masquer par le résultat du chiffrement de bloc précédent au moyen de l’opération XOR. Le premier bloc clair est lui aussi masqué par une valeur habituellement notée IV (Initial Value) et de préférence variable (la date et l’heure peuvent faire une bonne IV), pour que deux chiffrements successifs du même message soient différents. Il faut noter que si le destinataire reçoit un bloc chiffré avec des bits erronés, cela affecte le déchiffrement de ce bloc et du suivant mais pas des autres. [4]

OFB

Pour déchiffrer un message en mode ECB ou CBC, il faut avoir reçu chaque bloc complet avant de pouvoir obtenir n’importe quel bit du bloc clair correspondant. Cependant, certaines applications nécessitent le déchiffrement du flux de données au fur et à mesure de leur arrivée, même si la transmission est faite par petit morceau. Ceci est possible en utilisant le mode OFB (Output FeedBack) qui consiste à itérer la fonction de chiffrement sur une valeur initiale IV et à utiliser le flot de bits pseudo-aléatoires obtenus pour masquer les bits clairs à l’aide de l’opération XOR. Il est, cette fois-ci, important que la valeur initiale soit différente de cette méthode : un attaquant actif peut modifier des bits du message clair en modifiant les bits correspondants du chiffré (ce qui peut être aussi un avantage, si un bit du message chiffré est modifié par erreur au cours de la transmission, seul le bit correspondant du message clair sera affecté). [4]

CFB

Le mode CFB (Cipher FeedBack) est proche du mode OFB mais le flot de bits pseudo-aléatoires dépend cette fois-ci des blocs chiffrés. Un attaquant peut encore modifier un bit clair en modifiant le bit correspondant du chiffré, de ce fait le bloc suivant une fois déchiffré sera complètement différent du bloc original. [4]

Principe de fonctionnement de l’AES

Le principe de fonctionnement de l’AES est décrit dans la figure 2.13. En premier lieu, on ajoute bit à bit le message avec la clé secrète K0. Puis, comme pour tous les algorithmes de chiffrement par blocs, on itère une fonction F, paramétrée par des sous-clés qui sont obtenues de la clé maître par un algorithme de cadencement de clés.
La fonction F itérée lors du chiffrement est décrite figure 2.14. Celle-ci prend en entrée des blocs de 128 bits répartis sur 16 octets. Tout d’abord, on applique à chaque octet la même permutation S. Ensuite on applique aux 16 octets une seconde permutation P. Au résultat obtenu, on ajoute alors bit à bit la sous-clé de 128 bits obtenue par l’algorithme de cadencement de clé.
L’algorithme de cadencement de clé permet de calculer la clé Ki du iéme tour en fonction de la sous-clé Ki-1 du (i-1)ème tour, K0 étant la clé secrète. Celui-ci est décrit dans la figure 3.10 Les 16 octets de la clé Ki-1 sont pris 4 à 4. Aux 4 derniers octets, on commence par faire subir une permutation, puis on réutilise la même permutation S que celle de la fonction F afin de permuter les bits de chaque octet. Ensuite, on additionne au premier octet du nouvel ensemble l’élément ai. Cet élément est un octet qui dépend du numéro i du tour considéré. Enfin pour obtenir Ki, on ajoute bit à bit les 4 octets obtenus aux 4 premiers octets de Ki-1, puis le résultat obtenu est additionné aux 4 octets suivants et ainsi de suite. [7]
Voici brièvement comment sont construites les permutations et à quoi correspond la constante ai. Techniquement et pour des soucis de facilité, un octet peut être considéré comme un élément d’un ensemble à 256 éléments appelé corps fini, sur lequel existent toutes sortes d’opérations simples, notamment des opérations d’additions, de multiplications et d’inversions. La permutation S susmentionnée correspond à l’inversion sur cet ensemble. La permutation P est spécifiée comme étant une opération très simple, s’implantant facilement. L’élément ai correspond à l’élévation à la puissance i d’un élément du corps. De telles considérations permettent d’implémenter très efficacement l’AES. [7]
Tout au long du processus, la clé est dérivée en continu de façon à ce qu’à chaque tour la clé subisse une transformation appelée « cadencement de clé ». Un tel processus est décrit dans la Figure 2.15

Performances et fiabilité de l’algorithme AES

Du fait de la combinaison de confusion, de la diffusion et l’addition de clés partielles jusqu’à 10 tours au mois pour chaque bloc, et en utilisant le mode CBC, avec une longueur de clé de 128 bits ; l’AES résiste très bien à la cryptanalyse linéaire et différentielle.
On ne connait pas de clé faible pour l’AES, la meilleure attaque actuellement est la recherche exhaustive de la clé qui reste encore très coûteuse.
Il faut rechercher une clé parmi un 2128 soit 34028236692093846346374607431768211456 clés à tester avec quelques restrictions ;
Considérons par exemple que notre machine peut tester une clé à la secondes, alors il nous faut à peu près 149 milliards d’années pour finir le travail.

Table des matières

INTRODUCTION GENERALE
CHAPITRE 1 – INTRODUCTION A LA CRYPTOGRAPHIE
I.1 Histoire de la cryptologie.
I.1.1 Les premières méthodes de chiffrement
1.1.2 Les premiers systèmes cryptographiques
1.1.3 La Cryptographie moderne
1.2 Principaux systèmes de chiffrement
1.2.1 Systèmes classiques
1.2.1.1 Substitution
1.2.1.2 Transposition
1.2.3 Systèmes modernes
1.2.4 Systèmes de chiffrement quantique
1.3 Principe général du chiffrement
1.3.1 Clé de chiffrement
1.3.2 Chiffrement à clé secrète
1.3.3 Chiffrement à clé publique
1.4 Algorithme cryptographique
1.4.1 Algorithme à clé secrète
1.4.2 Algorithme à clé publique
1.4.3 Choix d’algorithme
1.4.5 Cryptosystème hybride
CHAPITRE 2 – ALGORITHME DE CHIFFREMENT SYMETRIQUE : LE RINJDAEL
2.1 Introduction et historique d’AES
2.2 Description générale
2.2.1 Principe de conception
2.2.2 Disposition de l’algorithme AES
2.3 Opérations élémentaires
2.3.1 La substitution d’octet
2.3.2 Le décalage de lignes
2.3.3 L’opération sur les colonnes
2.3.4 L’addition de clé partielle
2.4 Dérivation de clés partielles
2.5 Modes opératoires
2.5.1 ECB
2.5.2 CBC
2.5.3 OFB
2.5.4 CFB
2.6 Principe de fonctionnement de l’AES
2.7 Performance et fiabilité de l’algorithme l’AES
2.8 Conclusion
CHAPITRE 3 – ALGORITHME DE CHIFFREMENT ASYMETRIQUE : RSA
3.1 Introduction au RSA
3.1.1 Un algorithme de chiffrement asymétrique
3.2 Théorie des nombres
3.2.1 Les nombres entiers et utilisations
3.2.2 Les nombres premiers et divisibilité
3.2.3 Le modulo
3.2.4 La puissance modulaire
3.2.5 Le pgcd – primalité d’un nombre avec un autre
3.2.5.1 L’algorithme d’Euclide
3.3 Technique utilisée dans RSA
3.3.1 Génération des clés
3.3.1.2 La clé de chiffrement e
3.3.1.3 La clé de déchiffrement d
3.3.2 Chiffrement et déchiffrement
3.4 Autre utilisation de l’algorithme RSA à part le chiffrement
3.4.1 Signature RSA
3.4.2 Authentification
3.4.2.1 Enjeu
3.4.2.2 Preuves
3.4.2.3 Méthodes de vérification
3.5 Attaques au RSA
3.5.1 Factorisation d’un grand nombre entier
3.5.2. Attaques elementaires
3.5.2.1 Common Modulus
3.5.2.2 Blinding
3.5.3. Petite valeur de d
3.5.4 Petite valeur de e
3.5.5 Attaques sur l’implémentation
3.5.5.1 Attaque temporelle
3.5.5.2 Random Faults
3.6 Paramètres idéals pour la génération des clés
3.7 Conclusion
CHAPITRE 4 – CRYPTOSYSTEME HYBRIDE RSA – AES
4.1 Un cryptosystème hybride
4.2 Protocole d’échange de clé de session avec RSA
4.4 Etablissement d’une transmission sécurisée
4.6 Conclusion
CHAPITRE 5 – LA CRYPTOGRAPHIE A MADAGASCAR
5.1 Situation actuelle de Madagascar
5.2 Avenir de la cryptographie à Madagascar
CONCLUSION GENERALE
ANNEXES
ANNEXE 1 : Algorithmes de test de primalité
ANNEXE 2 : Code sources et algorithme RSA
ANNEXE 3 : Code sources et algorithme AES
ANNEXE 4 : Les résultats du concours effectué par la NIST
ANNEXE 5 : La programmation
ANNEXE 6 : Les interfaces graphique du logiciel de RSARijndael
ANNEXE 7 : Démonstrations
ANNEXE 8 : La Bibliothèque C/C++ pour grand nombre Miracl

Télécharger le rapport complet