Algorithme DES/3DES

To the non-french speaker, note that you can translate the articles using the Google Trad widget situated at the bottom of all pages.


DES pour Data Encryption Standard est un algorithme de chiffrement symétrique par bloc développé dans les années 1970 et publié pour la première fois par le FIPS (Federal Information Processing Standard) le 15 janvier 1977.

A l’origine l’algorithme s’appelait Lucifer. Il a été créé par Horst Feistel en 1971 pour les besoins de l’entreprise IBM. La NSA a tout simplement repris et modifié une partie de cet algorithme pour sortir l’algorithme DES. Bien évidemment de nombreux cryptanalystes et mathématiciens ont pensé que la NSA avait backdooré l’algorithme DES afin de garder le contrôle sur les communications chiffrées alors qu’à priori elle aurait fait tout l’inverse (mais ça, ça ne reste que des suppositions… 😉 ).

Tout au long de cette explications je vais vous parler de table de permutation. Ces tables sont fixes et prédéfinies et à chaque fois que nous nous en servirons je vous mettrais une image avec leurs contenues. Ces images sont tirées d’un post Wikipédia : Les constantes DES.

I/ Fonctionnement de l’algorithme DES

DES repose sur un réseau de Feistel à 16 étages. Si vous ne savez pas ce qu’un réseau de Feistel je vous invite fortement à lire cet article où j’explique comment ces algorithmes fonctionnent. L’algorithme prend en paramètres d’entrées un message à chiffrer et une clé de 64 bits même si en réalité seuls les 56 premiers bits sont utilisés.

Capture d’écran du 2019-04-26 16-01-46.png

L’algorithme s’effectue en deux étapes :
– Création des clés de chiffrement
– Chiffrement des données

  • Première étape : création des clés de chiffrement

Tout au long de cette étape nous allons générer les 16 clés de chiffrement que l’on utilisera durant la phase de chiffrement des données. Si nous créons 16 clés maintenant c’est tout simplement parce que notre réseau de Feistel est sur 16 étages. On utilisera donc une clé différente par étage (premier étage = première clé, second étage = seconde clé etc…)

Pour commencer nous allons permuter les bits qui composent notre clé initiale via l’utilisation de la table de permutation PC-1 :

Capture d’écran du 2019-04-26 15-23-25.png

Ainsi le premier bit de notre clé devient le 57ème, le deuxième bit devient le 49ème etc… Jusqu’à ce que notre clé ait été complètement permuté. Cette clé on va la noter C1 :

Capture d’écran du 2019-04-26 16-03-21.png

Puis on va diviser cette clé en deux parties de taille égale que l’on notera P et P’ pour la suite de l’explication.

Capture d’écran du 2019-04-26 16-05-03.png

Sur ces deux blocs P et P’ nous allons effectuer une permutation d’un ou deux bits vers la gauche ce qui nous donnera une nouvelle de chiffrement composée de P1 et P1′. Puis à partir de P1 et P1′ nous allons effectuer une nouvelle permutation afin d’obtenir une seconde clé composée de P2 et P2′. Cette opération, nous allons l’effectuer 16 fois afin d’obtenir 16 clés de chiffrement. Attention cependant, suivant le numéro de la clé, un ou deux bits seront permutés. Ce niveau de permutation est fixe et établie par la table de décalage :

Capture d’écran du 2019-04-26 14-00-31.png

En conséquence on appliquera une permutation d’un bit vers la gauche pour la première clé mais une permutation de deux bits sur la gauche pour la 13ème.

Capture d’écran du 2019-04-26 16-17-32.png

A partir de ce moment nous disposons de 16 clés de chiffrement. Sur ces 16 clés nous allons effectuer une nouvelle permutation via la table PC-2 :

Capture d’écran du 2019-04-26 13-47-40.png

Et nous obtiendrons nos 16 clés de chiffrement définitives :

Capture d’écran du 2019-04-26 16-22-19.png

Ce qui nous permettra de passer à la seconde étape : le chiffrement des données.

  • Seconde étape : chiffrement de données

DES est un algorithme de chiffrement par bloc ce qui veut dire que le message à chiffrer sera décomposé en plusieurs blocs de taille égale (ici 64 bits).

Capture d’écran du 2019-04-26 16-27-42.png

Sur chacun de ces blocs de 64 bits une nouvelle permutation est effectuée via la table IP (Initial Permutation) :

Capture d’écran du 2019-04-26 13-29-37

Ici nous ne nous intéresserons qu’à un seul bloc que l’on notera B1 :

Capture d’écran du 2019-04-26 16-36-45.png

Ensuite débute l’utilisation du réseau de Feistel ou il faudra découper notre bloc B1  en deux blocs de taille égale notés L0 et R0 sur le schéma :

800px-Schéma_de_Feistel.svg

Pour résumé, on va prendre le bloc R0 et le faire passer par une fonction F qui prend en paramètre la première clé de chiffrement symbolisé par K0 sur le schéma (pour le premier étage).

Il en résulte un bloc de sortie qui sera xorée avec le bloc L0. Puis on permutera les valeurs de sorte que le bloc L1 vaille R0 et le bloc R1 vaille L0. Ces étapes seront effectuées 15 autres fois avec les 15 autres clés de chiffrement.

Tout l’intérêt de l’algorithme repose donc sur une fonction : la fonction  F que je vais détailler ci-dessous.

Chaque bloc de données entrant dans la fonction F a une taille fixe de 64 bits. Avant tout ce bloc va être couper en deux blocs de 32 bits puis étendus à 48 bits. Pour cela une troisième table de permutation est utilisée, la table de développement :

Capture d’écran du 2019-04-26 14-14-22.png

Globalement il faut juste retenir que deux bits sur quatre sont dupliqués. Le bloc obtenu sera ensuite xoré avec la clé de chiffrement K et modifier via ce qu’on appelle des boites de permutation (ou S box) qui, elles aussi, sont constantes :

Capture d’écran du 2019-04-26 14-24-56.png

Le fonctionnement de ces tables est assez simple. Jusque là nous disposions d’un bloc de données de 48 bits soit 8 sous blocs de 6 bits. Or nous ce que nous voulons c’est un bloc de 32 bits. Pour cela deux opérations seront à effectuer  :

-Récupérer le premier et le dernier bit du sous bloc en base 2 et le convertir en base 10 (on notera le résultat R1).
-Récupérer les quatre bits restant du sous bloc en base 2 et les convertir en base 10 (on notera le résultat R2).

Puis nous utiliserons la boite de permutation S1 (puisque nous travaillons sur le premier sous bloc) :

Capture d’écran du 2019-04-26 14-35-38.png

La valeur R1 obtenu sera la ligne à utiliser tandis que la valeur R2 sera la valeur de la colonne. Par exemple si R1 vaut 2 et R2 vaut 14 alors notre valeur de sortie sera 5 :

Capture d’écran du 2019-04-26 14-40-20.png

Ainsi de 8 sous blocs de 6 bits nous allons obtenir 8 sous blocs de 4 bits soit un autre bloc de 32 bits qui sera encore une fois passer dans une table de permutation appelé « table de permutation » :

Capture d’écran du 2019-04-26 14-42-28.png

Ces opérations on les répétera encore 15 fois jusqu’à atteindre le bas de notre réseau de Feistel duquel on obtiendra un bloc de données de 64 bits que l’on passera dans une dernière table de permutation : la table de permutation finale :

Capture d’écran du 2019-04-26 14-46-03.png

Et ainsi on obtiendra notre message chiffré :

Capture d’écran du 2019-04-26 17-09-08.png

Pour le déchiffrement, et comme pour tous les algorithmes basés sur un schéma de Feistel, il faudra effectuer les mêmes opérations dans le sens inverse. Quant à 3DES c’est le même principe, on effectuera juste l’ensemble de ces opérations trois fois.

Un commentaire

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l'aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s