Algorithme de cryptage DES : Data Encryption Standard
DES est un algorithme de cryptage extrêmement rapide au niveau du chiffrement/déchiffrement. Même si actuellement l'utilisation de DES comme seul moyen de cryptage n'est plus fiable, il est encore utilisé en combinaison avec d'autres systèmes, ou sous sa forme triple DES.
Historique du cryptage DES
Feistal Horst, un chercheur des laboratoires IBM, propose dans les années '60 un algorithme de cryptage très fiable dont la simplicité permet un codage aisé sur un circuit électronique. Ce projet est retenu sous le nom de code LUCIFER.
En 1972, le NBS lance un appel d'offre pour un algorithme de cryptage. Comme le cahier des charges de la demande est fort proche des possibilités qu'offre le projet LUCIFER, IBM y apporte quelques modifications qu'il réponde à la norme demandée.
L'algorithme de IBM est donc retenu en 1977 par le NBS sous le nom DES : Data Encryption Standard.
DES est validé en 1978 par l' sous le nom DEA.
Le plus petit changement dans le plaintext (fichier en clair) ou dans la clé produit un grand changement dans le ciphertext (fichier crypté). Ce phénomène porte le nom d'effet d'avalanche.
DES est un algorithme à clé symétrique, c'est-à-dire que nous appliquons la même clé pour chiffrer et pour déchiffrer. Ceci suppose que la personne qui chiffre et celle qui déchiffre possèdent la même clé et que celle-ci ait été échangée par un moyen sécurisé.
Principes de l'algorithme de cryptage DES
DES est un algorithme symétrique, qui combine transpositions et substitutions :
- La transposition est le fait de déplacer des éléments du fichier clair (plain text) dans le fichier crypté (cypher text). Les transpositions permettent d'éclater dans le fichier crypté la redondance présente dans le fichier clair.
Dans le cas de l'algorithme DES, nous rencontrerons aussi le terme permutation au lieu de transposition. - La substitution est la transformation d'un élément du fichier clair en un autre élément dans le fichier chiffré. Les substitutions non linéaires permettent de compliquer la liaison entre le fichier crypté et les clés secrètes.
Le processus de cryptage nécessite 16 étapes numérotées de 0 à 15, comprenant chacune des transpositions et substitutions.
Le fichier clair (plain text) est découpé en blocs de 64 bits.
Nous utiliserons une clé de 8 octets (64 bits) dont seuls 56 bits serviront au codage. Les 8 bits restant (les bits 8, 16, 24, 32, 40, 48, 56, et 64) étant des bits de parités. Cette clé initiale donnera naissance aux 16 clés de 48 bits nécessaires, chaque niveau de clé se basant sur la clé de niveau supérieur.
Chiffrement à l'aide de DES
Le fichier clair (plain text) est découpé en blocs de 64 bits, chaque bloc étant traité séparément.
Phase 1 : Transposition initiale du bloc de 64 bits
Chaque bloc subit une transposition initiale suivant la table suivante :
Nous sommes toujours en possession d'un bloc de 64 bits, mais dont les éléments ont changé de place (par exemple, le bit 1 se retrouve à la place du bit 40, le bit 40 se retrouve à la place du bit 28, etc.).
Phase 2 : 16 itérations
Division en blocs de 32 bits
Ce bloc de 64 bits est découpé en deux blocs de 32 bits, L0 (Left zero) et R0 (Right zero). Chaque bloc est placé dans une mémoire tampon (buffer) car nous en aurons besoin ultérieurement.
Expansion à 48 bits et transpositions
Chaque bloc (L0 et R0) est traité simultanément, mais dans nos explications, nous n'allons en traiter qu'un seul.
Comme la clé correspondant à cette étape (K0) est composée de 48 bits et que notre bloc est composé de 32 bits, nous allons le soumettre à une nouvelle table de transposition dans laquelle un bit peut se trouver deux fois (par exemple, le bit 1 de la sortie de notre table précédente se retrouve à la position 2, et en même temps à la position 48) :
Application de la clé de 48 bits
Comme nous sommes maintenant en présence de blocs de 48 bits (du bloc R ou L 0), ces derniers sont soumis avec les 48 bits de la clé K0 à un opérateur logique XOR, ce qui nous donne un bloc de 48 bits en sortie.
Vous pouvez consulter la partie sur la génération des clés dans la prochaine section.
Sélection (passage de 48 à 32 bits)
Notre bloc de 48 bits est ensuite divisé en 8 vecteurs de 6 bits, chaque vecteur étant finalement traité dans une table de sélection qui permet 4 bits en sortie. Nous avons donc à nouveau un bloc de 32 bits (8 vecteurs de 4 bits).
| n° de vecteur | Valeur des bits extérieurs | Valeurs des bits intérieurs | |||||||||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ||
| 0 | 0 (00) | 14 | 4 | 13 | 1 | 2 | 15 | 77 | 8 | 3 | 10 | 6 | 12 | 5 | 9 | 0 | 7 |
| 1 (01) | 0 | 15 | 7 | 4 | 14 | 2 | 13 | 1 | 10 | 6 | 12 | 1 | 9 | 5 | 3 | 8 | |
| 2 (10) | 4 | 1 | 14 | 8 | 13 | 6 | 2 | 11 | 15 | 12 | 9 | 7 | 3 | 10 | 5 | 0 | |
| 3 (11) | 15 | 12 | 8 | 2 | 4 | 9 | 1 | 7 | 5 | 11 | 3 | 14 | 10 | 0 | 6 | 13 | |
| 1 | 0 | 15 | 1 | 8 | 14 | 11 | 6 | 3 | 4 | 9 | 7 | 2 | 13 | 12 | 0 | 5 | 10 |
| 1 | 3 | 13 | 4 | 7 | 15 | 2 | 8 | 14 | 12 | 0 | 1 | 10 | 6 | 9 | 11 | 5 | |
| 2 | 0 | 14 | 7 | 11 | 10 | 4 | 13 | 1 | 5 | 8 | 12 | 6 | 9 | 3 | 2 | 15 | |
| 3 | 13 | 8 | 10 | 1 | 3 | 4 | 15 | 2 | 11 | 6 | 7 | 12 | 0 | 5 | 14 | 9 | |
| 2 | 0 | 10 | 0 | 9 | 14 | 6 | 3 | 15 | 5 | 1 | 13 | 12 | 7 | 11 | 4 | 2 | 8 |
| 1 | 13 | 7 | 0 | 9 | 3 | 4 | 6 | 10 | 2 | 8 | 5 | 14 | 12 | 11 | 15 | 1 | |
| 2 | 13 | 6 | 4 | 9 | 8 | 15 | 3 | 0 | 11 | 1 | 2 | 12 | 5 | 10 | 14 | 7 | |
| 3 | 1 | 10 | 13 | 0 | 6 | 9 | 8 | 7 | 4 | 15 | 14 | 3 | 11 | 5 | 2 | 12 | |
| 3 | 0 | 7 | 13 | 14 | 3 | 0 | 6 | 9 | 10 | 1 | 2 | 8 | 5 | 11 | 12 | 4 | 15 |
| 1 | 13 | 8 | 11 | 5 | 6 | 15 | 0 | 3 | 4 | 7 | 2 | 12 | 3 | 10 | 14 | 9 | |
| 2 | 10 | 6 | 9 | 0 | 12 | 11 | 7 | 13 | 15 | 1 | 3 | 14 | 5 | 2 | 8 | 4 | |
| 3 | 3 | 15 | 0 | 6 | 10 | 1 | 13 | 8 | 9 | 4 | 5 | 11 | 12 | 7 | 2 | 14 | |
| 4 | 0 | 2 | 12 | 4 | 1 | 7 | 10 | 11 | 6 | 8 | 5 | 3 | 15 | 13 | 0 | 14 | 9 |
| 1 | 14 | 11 | 2 | 12 | 4 | 7 | 13 | 1 | 5 | 0 | 15 | 10 | 3 | 9 | 8 | 6 | |
| 2 | 4 | 2 | 1 | 11 | 10 | 13 | 7 | 8 | 15 | 9 | 12 | 5 | 6 | 3 | 0 | 14 | |
| 3 | 11 | 8 | 12 | 7 | 1 | 14 | 2 | 13 | 6 | 15 | 0 | 9 | 10 | 4 | 5 | 3 | |
| 5 | 0 | 12 | 1 | 10 | 15 | 9 | 2 | 6 | 8 | 0 | 13 | 3 | 3 | 4 | 14 | 7 | 5 |
| 1 | 10 | 15 | 4 | 2 | 7 | 12 | 9 | 5 | 6 | 1 | 13 | 14 | 0 | 11 | 3 | 8 | |
| 2 | 9 | 14 | 15 | 5 | 2 | 8 | 12 | 3 | 7 | 0 | 4 | 10 | 1 | 13 | 1 | 6 | |
| 3 | 4 | 3 | 2 | 12 | 9 | 5 | 15 | 10 | 11 | 14 | 1 | 7 | 6 | 0 | 8 | 13 | |
| 6 | 0 | 4 | 11 | 2 | 14 | 15 | 0 | 8 | 13 | 3 | 12 | 9 | 7 | 5 | 10 | 6 | 1 |
| 1 | 13 | 0 | 11 | 7 | 4 | 9 | 1 | 10 | 14 | 3 | 5 | 12 | 2 | 15 | 8 | 6 | |
| 2 | 1 | 4 | 11 | 13 | 12 | 3 | 7 | 14 | 10 | 15 | 6 | 8 | 0 | 5 | 9 | 2 | |
| 3 | 6 | 11 | 13 | 8 | 1 | 4 | 10 | 7 | 9 | 5 | 0 | 15 | 14 | 2 | 3 | 12 | |
| 7 | 0 | 13 | 2 | 8 | 4 | 6 | 15 | 11 | 1 | 10 | 9 | 3 | 14 | 5 | 0 | 12 | 7 |
| 1 | 1 | 15 | 13 | 8 | 10 | 3 | 7 | 4 | 12 | 5 | 6 | 11 | 0 | 14 | 9 | 2 | |
| 2 | 7 | 11 | 4 | 1 | 9 | 12 | 14 | 2 | 0 | 6 | 10 | 13 | 15 | 3 | 5 | 8 | |
| 3 | 2 | 1 | 14 | 7 | 4 | 10 | 8 | 13 | 15 | 12 | 9 | 0 | 3 | 5 | 6 | 11 | |
Chaque vecteur (ligne) de la table d'expansion et transitions est numéroté, et est composé de 6 bits.
Le premier bit et le dernier bit nous fournissent le numéro de ligne, entre 0 et 3, et les 4 bits intermédiaires nous fournissent le numéro de colonne.
Exemple
Pour notre exemple, prenons au hasard une série de 6 bits : 011001
Nous sommes dans le premier vecteur (ligne 0).
Les bits extérieurs (01) nous indiquent la deuxième ligne (ligne 1).
Les bits intérieurs (1100) nous indiquent la 12ème colonne.
Dans la table de division et positionnement, l'intersection entre la ligne 1 du vecteur 0 et la colonne 12 nous donne la valeur 9, qui sera codée sur 4 bits de manière binaire normale : 1001.
Si nous procédons de la même manière pour chacun des 8 vecteurs, nous nous trouvons à nouveau en possession d'un bloc de 32 bits (8 vecteurs de 4 bits).
Transpositions du bloc de 32 bits
Les blocs de 32 bits subissent ensuite une série de transpositions selon la table suivante :
Opérateur XOR
Imaginons que nous étions occupés à traiter le bloc de 32 bits R0, nous devons à présent le soumettre avec le bloc L0 (qui a été mémorisé plus tôt) à l'opérateur logique XOR. Cette opération nous renvoie un tableau de 32 bits.
Phase 3 : Transposition finale sur 64 bits
Nous devons exécuter au total 16 fois les opérations de la phase 2.
A la 16ème itération, les deux blocs de 32 bits de gauche et de droite sont réunis en un bloc de 64 bits dans la table suivante :
Génération des clés de DES
Comme nous l'avons vu précédemment, la clé secrète utilisée dans l'algorithme DES est une clé de 64 bits, dont 56 servent au chiffrement, et 8 servent de bits de parités (les bits 8, 16, 24, 32, 40, 48, 56, et 64) .
Nous devrons générer 16 clés depuis ce bloc de 56 bits, une pour chaque itération.
Le bloc clé de 56 bits subit une première série de transpositions et une division en 2 blocs de 28 bits selon les tables suivantes :
de la clé
de la clé
Les deux blocs subiront chacun un décalage vers la gauche, en fonction du niveau d'itération (le numéro d'étape, de 0 à 15), selon l'ordre suivant : 1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1.
Ensuite, les 2 blocs de 28 bits sont rassemblés en un bloc de 56 bits. Ce bloc de 56 bits est mémorisé car il nous servira pour générer la clé suivante, puis il subira une série de transpositions avec oubli pour obtenir un bloc de 48 bits selon cette table :
Nous sommes en possession d'une clé de 48 bits que nous pourrons soumettre à une porte logique XOR avec les 48 bits du message.
La clé du niveau suivante est générée de la même manière, mais en partant du bloc de 56 bits que nous venons d'obtenir en réunissant les 2 blocs de 28 bits.
Déchiffrement de DES
L'algorithme de cryptage DES est symétrique, ce qui signifie que nous allons utiliser les mêmes étapes, en utilisant les mêmes clés, mais en inversant l'ordre des clés (de la clé 15 à la clé 0).
Modes opératoires de DES
Le mode opératoire est la manière dont les blocs sont présentés à l'algorithme.
Considérons x i les blocs en clair, y i les blocs chiffrés et E k la fonction d'encryption avec une clé K.
ECB - Electronic Code Book : les blocs sont traités de manière indépendante, ce qui permet de rendre le chiffrement ou déchiffrement parallèle.Ce mode est souvent utilisé, mais il est sensible à une attaque par dictionnaire.
y i = eK (x i )
CBC - Cipher Block Chaining : moins utilisé, mais nettement plus sûr que ECB, ce mode opératoire utilise le bloc précédent lors du calcul d'un bloc, ce qui lie tous les blocs entre eux (une erreur dans l'émission empêche le déchiffrement de toutes les données).
y 0 = valeur initiale y i = eK (y i -1 XOR x i ) avec i >= 1
CFB - Cipher FeedBack (chiffrement à rétroaction) : Une clé partielle basée sur le bloc chiffré précédemment nous permet de chiffrer le bloc suivant.
z i = eK(y i -1)
y i = x i XOR z i avec i >= 1OFB - OutPut FeedBack (chiffrement à rétroaction de sortie) : les blocs ne sont pas liés entre eux (pourtant, deux blocs identiques en clair donnent deux blocs chiffrés différents). Cet aspect nous assure une certaine sécurité face aux erreurs de transmissions.
Une valeur initiale z0 sert à créer des clés telles que z i = Ek (z i-1 ).
Cette valeur sert à créer des blocs chiffrés tels que y i = x i XOR z i.
Triple DES
En 1979, IBM découvre que la longueur de clé de 56 bits est devenue insuffisante pour assurer un niveau de sécurité acceptable lors d'une utilisation isolée de DES. Il était possible d'augmenter la longueur des clés, mais les dispositifs de cracking pour des clés plus longues étaient déjà présents.
La parade utilisée (et qui est toujours efficace à l'heure actuelle) est d'effectuer trois codages successifs à l'aide de 2 clés différentes, d'où le nom "triple DES".
Chiffrement triple DES
Deux clés sont générées : K1 et K2.
- Le fichier subit un premier chiffrement (encryption) à l'aide de la clé K1.
- Le résultat subit un déchiffrement à l'aide de la clé K2. Comme le chiffrement a été réalisé à l'aide d'une autre clé, le fichier est modifié, mais pas déchiffré.
- La troisième opération consiste à chiffrer le tout à l'aide de la clé K1.
Déchiffrement triple DES
Pour le déchiffrement triple DES, les opérations inverses sont réalisées :
- Déchiffrement à l'aide de la clé K1.
- Chiffrement à l'aide de la clé K2.
- Déchiffrement à l'aide de la clé K1.
Compatibilité DES et triple DES
Pour assurer la compatibilité entre DES et triple DES, il suffit de rentrer deux fois la même clé dans l'algorithme triple DES. La compatibilité est ainsi assurée en chiffrement ou en déchiffrement, mais au détriment du niveau de sécurité (nous retombons au niveau de DES simple).
English translation
You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.
Thank you in advance.
Document created the 24/06/2005, last modified the 26/10/2018
Source of the printed document:https://www.gaudry.be/en/crypto-des.html
The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.
