infoclick solution informatique (Gers) - version particulier

DES, le chiffrement à clé secrète

Le 15 mai 1973 le NBS (National Bureau of Standards, aujourd'hui appeléNIST - National Institute of Standards and Technology) a lancé un appel dans le Federal Register (l'équivalent aux Etats-Unix du Journal Officiel en France) pour la création d'un algorithme de chiffrementrépondant aux critères suivants:

• ayant un haut niveau de sécurité lié à une clé de petite taille servant au chiffrement et au déchiffrement
• compréhensible
• ne devant pas dépendre de la confidentialité de l'algorithme
• adaptable et économique
• efficace et exportable

C'est un système de chiffrement par blocs de 64 bits, dont 8 bits (un octet)servent de test de parité (pour vérifier l'intégrité de la clé). Chaque bit de parité de la clef (1 tous les 8 bits) sert à tester un des octets de la clef par parité impaire, c'est-à-dire que chacun des bits de parité est ajusté de facon à avoir un nombre impair de '1' dans l'octet à qui il appartient. La clé a donc une longueur "utile" de 56 bits, ce qui signifie que seuls56 bits servent dans l'algorithme.

L'algorithme consiste à faire des combinaisons, des substitutions et des permutations entre le texte à chiffrer et la clé, en faisant en sorte que les opérations puissent se faire dans les deux sens (pour le déchiffrement). On appelle code produit la combinaison entre substitutionset permutations.La clé est codée sur 64 bits et formée de 16 blocs de 4 bits, généralement notésk₁ à k₁₆. Etant donné que "seulement" 56 bits servent réellement à chiffrer, il y a 2⁵⁶ (soit 7.2*10¹⁶) possibilitésde clés différentes !

L'algorithme du DES

Les grandes lignes de l'algorithme sont les suivantes:

• Fractionnement du texte en blocs de 64 bits (8 octets)
• Permutation initiale des blocs
• Découpage des blocs en deux parties: gauche et droite, nommées G et D
• Etapes de permutation et de substitution répétées 16 fois (appelées rondes)
• Recollement des parties gauche et droite puis permutation initiale inverse

Fractionnement du texte

Permutation initiale

Dans un premier temps, chaque bit d'un bloc est soumis à la permutation initiale,pouvant être représentée par la matrice de permutation initiale (notée PI) suivante :

PI	58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

Cette matrice de permutation indique,en parcourant la matrice de gauche à droitepuis de haut en bas, que le 58^ème bitdu bloc de texte de 64 bits se retrouve en première position, le 50^èmeen seconde position et ainsi de suite.

Scindement en blocs de 32 bits

Une fois la permutation initiale réalisée, le bloc de 64 bits estscindé en deux blocs de 32 bits, notés respectivement G et D (pour gauche et droite,la notation anglo-saxonne étant L et R pour Left and Right).On note G₀ et D₀ l'état initial de ces deux blocs :

G0	58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8

D0	57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

Il est intéressant de remarquer que G₀ contient tousles bits possédant une position paire dans le message initial, tandis que D₀contient les bits de position impaire.

Rondes

Les blocs G_n et D_n sont soumis à un ensemblede transformation itératives appelées rondes, explicitéesdans ce schéma, et dont les détails sont donnés plus bas :

Fonction d'expansion

Les 32 bits du bloc D₀ sont étendus à 48 bitsgrâce à une table (matrice) appelé table d'expansion (notée E), dans laquelle les 48bits sont mélangés et 16 d'entre eux sont dupliqués :

E	32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1

Ainsi, le dernier bit de D₀ (c'est-à-dire le 7^èmebit du bloc d'origine) devient le premier, le premier devient le second, ...
De plus, les bits 1,4,5,8,9,12,13,16,17,20,21,24,25,28 et 29 de D₀ (respectivement57, 33, 25, l, 59, 35, 27, 3, 6l, 37, 29, 5, 63, 39, 31 et 7 du bloc d'origine) sont dupliquéset disséminés dans la matrice.

OU exclusif avec la clé

La matrice résultante de 48 bits est appelée D'₀ ou bien E[D₀].L'algorithme DES procède ensuite à un OU exclusif entre la première clé K₁et E[D₀]. Le résultat de ce OU exclusif est une matrice de 48 bits que nousappelerons D₀ par commodité (il ne s'agit pas du D₀ de départ!).

Fonction de substitution

D₀ est ensuite scindé en 8 blocs de 6 bits, noté D_0i.Chacun de ces blocs passe par des fonctions de sélection (appelées parfoisboîtes de substitution ou fonctions de compression), notées généralement S_i.
Les premiers et derniers bits de chaque D_0i détermine (en binaire) la ligne de la fonctionde sélection, les autres bits (respectivement 2, 3, 4 et 5) déterminent la colonne. La sélectionde la ligne se faisant sur deux bits, il y a 4 possibilités (0,1,2,3). La sélection de la colonnese faisant sur 4 bits, il y a 16 possibilités (0 à 15). Grâce à cette information, la fonctionde sélection "sélectionne" une valeur codée sur 4 bits.

Voici la première fonction de substitution, représentée par unematrice de 4 par 16 :

S1	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

Soit D₀₁ égal à 101110. Les premiers et derniersbits donnent 10, c'est-à-dire 2 en binaire. Les bits 2,3,4 et 5 donnent 0111, soit 7 en binaire.Le résultat de la fonction de sélection est donc la valeur situé à la ligne n°2,dans la colonne n°7. Il s'agit de la valeur 11, soit en binaire 111.

Chacun des 8 blocs de 6 bits est passé dans la fonction de sélection correspondante,ce qui donne en sortie 8 valeurs de 4 bits chacune. Voici les autres fonctions de sélection :

S2	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 15 1 8 14 6 11 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 15 4 2 11 6 7 12 0 5 14 9

S3	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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

S4	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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 1 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

S5	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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

S6	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 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 11 6 3 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13

S7	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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

S8	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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 1 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 1 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11

Chaque bloc de 6 bits est ainsi substitué en un bloc de 4 bits.Ces bits sont regroupés pour former un bloc de 32 bits.

Permutation

Le bloc de 32 bits obtenu est enfin soumis à une permutation Pdont voici la table :

P	16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25

OU Exclusif

L'ensemble de ces résultats en sortie de P est soumis à un OU Exclusifavec le G₀ de départ (comme indiqué sur le premier schéma) pour donnerD1, tandis que le D₀ initial donne G₁.

Itération

L'ensemble des étapes précédentes (rondes) estréitéré 16 fois.

Permutation initiale inverse

A la fin des itérations, les deux blocs G₁₆ et D₁₆sont "recollés, puis soumis à la permutation initiale inverse :

PI-1	40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25

Le résultat en sortie est un texte codé de 64 bits !

Génération des clés

Etant donné que l'algorithme du DES présenté ci-dessus est public,toute la sécurité repose sur la complexité des clés de chiffrement.

L'algorithme ci-dessous montre comment obtenir à partir d'une clé de 64 bits(composé de 64 caractères alphanumériques quelconques) 8 clés diversifiées de 48 bits chacune servant dans l'algorithme du DES :

Dans un premier temps les bits de parité de la clé sont éliminésafin d'obtenir une clé d'une longueur utile de 56 bits.

La première étape consiste en une permutation notéeCP-1 dont la matrice est présentée ci-dessous :

CP-1	57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4

Cette matrice peut en fait s'écrire sous la forme de deux matrice G_iet D_i (pour gauche et droite) composées chacune de 28 bits :

Gi	57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36

Di	63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4

On note G₀ et D₀ le réésultat;de cette premièrepermutation.

Ces deux blocs subissent ensuite une rotation à gauche, de telles façons que les bits enseconde position prennent la première position, ceux en troisième position la seconde, ...
Les bits en première position passent en dernière position.

Les 2 blocs de 28 bits sont ensuite regroupés en un bloc de 56 bits. Celui-cipasse par une permutation, notée CP-2, fournissant en sortie un bloc de 48 bits,représentant la clé K_i.

CP-2	14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 51 45 44 49 39 56 34 53 46 42 50 36 29 32

Des itérations de l'algorithme permettent de donner les 16 clésK₁ à K₁₆ utilisées dans l'algortihme du DES.

LS	1 2 4 6 8 10 12 14 15 17 19 21 23 25 27 28

TDES, une alternative au DES

En 1990 Eli Biham et Adi Shamir ont mis au point la cryptanalyse différentiellequi recherche des paires de texte en clair et des paires de texte chiffrées. Cetteméthode marche jusqu'à un nombre de rondes inférieur à 15, orun nombre de 16 rondes sont présentes dans l'algorithme présenté ci-dessus.

D'autre part, même si une clé de 56 bits donne un nombre énorme de possibilités,de nombreux processeurs permettent de calculer plus de 10⁶ clés par seconde, ainsi, utilisésparallèlement sur un très grand nombre de machines, il devient possible pour ungrand organisme (un Etat par exemple) de trouver la bonne clé...

Un solution à court terme consiste à chaîner troischiffrement DES à l'aide de deux clés de 56 bits (ce qui équivait àune clé de 112 bits). Ce procédé est appelé Triple DES,noté TDES (parfois 3DES ou 3-DES).

Le TDES permet d'augmenter significativement la sécurité du DES,toutefois il a l'inconvénient majeur de demander également plus de ressources pour leschiffrement et le déchiffrement.

En 1997 le NIST lança un nouvel appel à projet pour élaborer l'AES(Advanced Encryption Standard), un algorithme de chiffrement destiné à remplacer le DES.

Le système de chiffrement DES fût réactualisé tous les 5 ans. En 2000 lors de la dernière révision, après un processus d'évaluation qui a duré 3 années, l'algorithme conçu conjointement par deux candidats belges, Messieurs Vincent Rijmen et Joan Daemen fût choisi comme nouveau standard par le NIST. Ce nouvel algorithme baptisé RIJNDAEL par ses inventeurs, remplacera dorénavant le DES.

Plus d'informations

L'algorithme du DES étant public (tout comme celuidu TDES ou de l'AES), vous pouvez accéder aux spécificationssur le site du NIST :
http://csrc.nist.gov/encryption/tkencryption.html