Cryptographie symétrique Article, Signification, Explication

La cryptographie symétrique, également dite à clef secrète (par opposition à la cryptographie à clef publique), est la plus ancienne forme de chiffrement. On a des traces de son utilisation par les Égyptiens vers 2000 av. J.-C. Plus proche de nous, on peut citer le célèbre chiffre de Jules César, dont une version est le ROT13.

Table of contents

1 Clef et sécurité 2 Petite taxinomie du chiffrement symétrique classique 3 Techniques de l'âge moderne 4 Voir aussi :

Clef et sécurité

L'un des concepts fondamentaux de la cryptographie symétrique est la clef, qui est une information devant permettre de chiffrer et de déchiffrer un message et à laquelle doit se réduire la sécurité de la communication. Un algorithme comme le ROT13 par exemple n'a pas de clef, il suffit de savoir que cette méthode a été utilisée pour chiffrer un message et on peut avoir accès au texte clair. En d'autres termes, ici, le secret réside dans la méthode utilisée, ce qui n'est pas satisfaisant, car les algorithmes finissent toujours par être connus --- e.g. celui du dvd que sept lignes de programme en perl, dues à K. Winstein et M. Horowitz, permettent de casser. On peut modifier le ROT13 en changeant la valeur du décalage, cette valeur devenant alors la clef. Mais hélas, l'ensemble des clefs possibles --- l'espace des clefs --- est trop petit : il n'y a que 26 décalages possibles. Bien qu'un peu plus fastidieux, cela reste accessible même à la main.

On voit se dégager de cet exemple l'importance de cette clef et les restrictions. Auguste Kerckhoffs (La cryptographie militaire, 1883) est certainement l'un des premiers à avoir pleinement compris cela : pour espérer être sûr, l'algorithme doit pouvoir être divulgué. C'est ce que l'on appelle désormais le principe de Kerckhoffs. Il faut ajouter que cette clef doit pouvoir prendre suffisamment de valeurs pour qu'une attaque exhaustive --- essai systématique de toutes les clefs --- ne puisse être menée à bien car trop longue. On parle de sécurité calculatoire.

Cette sécurité calculatoire est bien évidemment dépendante du temps, les performances des moyens de calcul allant croissant, un système de chiffrement est confronté à une adversité toujours plus forte, alors que le message chiffré ne change plus. L'illustration de ce problème est le DES, ce système est devenu obsolète à cause du trop petit nombre de clefs qu'il peut utiliser (pourtant 2⁵⁶). On pense que, actuellement, 2⁸⁰ est un strict minimum. À titre indicatif, le dernier standard choisi par les américains en décembre 2001, l'AES, utilise des clefs dont la taille est au moins de 128 bits, autrement dit il y en a 2¹²⁸. Pour donner un ordre de grandeur sur ce nombre, cela fait environ 3.4 10³⁸ clefs possibles; l'âge de l'univers étant de 10¹⁰ années, si on suppose qu'il est possible de tester 1000 milliards de clefs par seconde (soit 3.2 10¹⁹ clefs par an) il faudra encore plus d'un milliard de fois l'âge de l'univers. Dans un tel cas on peut raisonnablement penser que notre algorithme est sûr. Cependant, c'est faire une hypothèse très forte sur l'algorithme que de supposer que le seul moyen de le casser est de mener une attaque exhaustive : nombreuses sont les failles que peuvent receler un algorithme et encore plus nombreuses sont les mauvaises utilisations d'un algorithme.

La question que pose cette notion de sécurité calculatoire est celle d'une sécurité absolue. On sait depuis Claude Shannon et son article Communication theory of secrecy system (1949) que le chiffrement de Gilbert Vernam qui consiste à ajouter au message en clair une clef de la même longueur (voir XOR) est parfaitement sûr. C'est le seul pour lequel nous soyons capables de prouver une telle chose. Hélas, l'inconvénient est évident pour chiffrer un message de n bits il faut au préalable avoir échangé une clef de n bits avec le destinataire du message, et cela par une voie absolument sûre, sinon chiffrer devient inutile. Très peu de cas nécessitent un tel système, mais c'était toutefois le système utilisé pour le téléphone rouge entre Moscou et Washington.

Petite taxinomie du chiffrement symétrique classique

Jusqu'aux communications numériques, les systèmes utilisaient l'alphabet et combinaient les substitutions --- les symboles sont changés mais restent à leur place ---, les transpositions --- les symboles ne sont pas modifiés mais changent de place. Lorsque la substitution appliquée depend de la place de la lettre dans le texte, on parle de substitution polyalphabetique ---e.g. le chiffre de Vigenère, Enigma---, en opposition à la substitution monoalphabetique où la substitution est la même pour toute les lettres ---e.g. un décalage simple.

Dans la série des substitutions figurent bien entendu les décalages, où chaque lettre du message à chiffrer est transformée en la lettre n positions plus loin dans l'alphabet, en rebouclant, i.e. la lettre suivant 'z' est 'a'. Le décalage simple --- un seul décalage identique pour toutes les lettres du message --- est également connu sous le nom de chiffre de Jules César. Sur le même thème mais tout en compliquant, nous avons le chiffre de Blaise de Vigenère, qui n'utilise pas un décalage mais un nombre quelconque n, le premier décalage est utilisé pour chiffrer la lettre numéro 1, puis la 1+n, 1+2n, ... le second décalage pour la lettre numéro 2, 2+n, 2+2n... Usuellement, la valeur de ces décalages est donnée par un mot de longueur n dont la ieme lettre donne la valeur du ieme décalage. Clarifions par un exemple.

Message clair   : wikipedia
Mot clef        : crypto
Message chiffre : yzixirfzy

Un 'a' dans le mot clef correspond à un décalage de 0, un 'b' à un décalage de 1, ect. Dans notre exemple, la clef a 6 lettres, dont les lettre 1 ('w') et 8 ('d') sont chiffrées par le même décalage, à savoir 2.
La machine Enigma utilisée par les Allemands durant la seconde guerre mondiale est également basée sur les substitutions, mais avec un mécanisme beaucoup plus sophistiqué.
Une autre forme de la substitution est le dictionnaire: au lieu de changer les symboles du message un a un, ce sont des mots entiers que l'on remplace.

Pour les transpositions on modifie l'ordre des symboles du texte clair. Une technique consiste à se donner un mot clef, à écrire le message sous ce mot clef et à lire le texte en colonne, par ordre alphabétique.

Message           : wikipediaestuneencyclopedielibre
Mot clef          : crypto

on ecrit sous       wikipe
le mot clef	     diaest
                    uneenc
                    yclope
                    dielib
                    re****

lettre du mot clef
(ordre alphabétique) coprty

on ordonne les	  weiipk
colonnes            dteisa
                    ucenne
                    yeocpl
                    dbliie
                    r**e**
                  

Message chiffre   : wduydr etceb* ieeol* iincie psnpi* kaele*

Les astérisques sont ajoutés pour le déchiffrement et les espacess dans le message chiffré uniquement pour la lisibilité.

Techniques de l'âge moderne

Depuis l'avènement du numérique, les paradigmes du chiffrement symétrique ont bien changé. D'une part, la discipline s'est formalisée, même si la conception de système de chiffrement garde inévitablement un aspect artisanal. En effet dans ce domaine, la seule chose que l'on sache prouver est la résistance face à des types d'attaques connues, pour les autres... D'autre part, la forme du texte chiffre ayant change, les méthodes ont suivi. Les algorithmes modernes chiffrent des suites de bits.

On distingue deux types d'algorithmes, les algorithmes en blocs, qui prennent n bits en entrée et en ressortent n, et les algorithmes à flots, qui chiffrent bit par bit sur le modèle du chiffre de Vernam. Dans ce dernier cas, l'algorithme engendre une suite de bits qui est ajoute (cf. XOR) à la suite binaire à chiffrer. Les techniques utilisées pour générer la suite que l'on ajoute --- appelée suite chiffrante --- sont diverses, mais utilisent le plus souvent des registres à décalage à rétroaction linéaire.

La seconde famille d'algorithmes, ceux en blocs, sont en général construit sur un modèle itératif. Ce modèle utilise une fonction 'F qui prend une clef k et un message de 'n' bits. C'est cette fonction 'F qui est itérée un certain nombre de fois, on parle de nombre de tour. À chaque tour, la clef k utilisée est changée et le message que l'on chiffre est le résultat de l'itération précédente.

C₁=F(k₁, M) ;

C₂=F(k₂, C₁) ;

...

C_r=F(k_r, C_r-1) ;

Les clef k_i utilisées sont déduites d'une clef maître K qui est la quantité secrète que doivent partager emmetteur et destinataire. L'algorithme générant ces clefs à partir de K est appelé l'algorithme de cadencement de clefs.

Pour qu'un tel système puisse fonctionner, la fonction F utilisée doit être une permutation, c'est-à-dire qu'il faut pour toute clef k et message M pouvoir recalculer M a partir de F(k',M''), autrement le déchiffrement n'est pas possible et par conséquent on ne dispose pas d'un algorithme utilisable. Formellement, cela signifie qu'il existe une fonction G vérifiant

G(k, F(k,M))= M.

La sécurité d'un tel système réside essentiellement a deux endroits, l'algorithme de cadencement de clef et la robustesse de la fonction F. Si l'algorithme de cadencement est mal conçu, les k_i peuvent être déductible les unes des autres, au mal reparti, ... Dire de la fonction 'F qu'elle est robuste signifie qu'on la suppose difficile à inverser sans connaître la clef k ayant servie dans le calcul de C=F(k,M). En d'autres termes, connaissant seulement C, F et 'G, on ne doit pas pouvoir retrouver le message M, si ce n'est en effectuant une recherche exhaustive de la clef k, c'est-à-dire en calculant

1) X=G(k, C);

2) Y=F(k,X);

et cela pour toutes les clefs k jusqu'à ce que l'on en trouve une pour laquelle Y est égal à C. On est alors assure d'avoir le message M qui n'est autre que X. Le problème étant que si k est constitue de l bits, il faut en moyenne 2^l/2=2^l-1 essais. En prenant l assez grand, on peut être sur que cela n'est pas réalisable en pratique: supposons que l'on puisse essayer 10⁹ (un milliard) clef par seconde, soit environ 2³⁰, il y a 31557600 secondes par an, soit 2²⁵, en conséquence on peut tester 2⁵⁵ clefs par an. Si on prend pour l une valeur de 80 bits, il faudrait 2²⁴ ans, plus de 1 million d'années.

Une technique très rependue pour fabriquer des fonctions F est celle du schéma de Fiestel. Dans ce schéma, le message à chiffrer est découpé en 2 blocs de n/2 bits, M=(L,R) et le message chiffré est

C=(R,L+f(k,R))

où le '+' est le XOR et f est une fonction quelconque, on n'a plus à supposer que c'est une permutation. En effet, on peut retrouver M à partir de la clef k

1) connaissant C, on connaît R qui est sa partie gauche,

2) on calcule f(k,R),

3) on ajoute le résultat du calcul précédent à la partie droite de C, et on retrouve L,

cela sans restriction sur f. Clairement, dans ce schéma, la robustesse de F repose sur la fonction f.

Voir aussi :

• Chiffrement de Vigenère

C'est un article concernant le Cryptographie symétrique. La page contient la signification du Cryptographie symétrique , Description et explication au sujet de Cryptographie symétrique