Cryptographie à clef secrète

La cryptographie symétrique, également dite à clé secrète (par opposition à la cryptographie à clé 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 chiffre de Jules César, dont le ROT13 est une variante.

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

Clé et sécurité

L'un des concepts fondamentaux de la cryptographie symétrique est la clé, qui est une information devant permettre de chiffrer et de déchiffrer un message et sur laquelle peut reposer toute la sécurité de la communication. Un algorithme comme le ROT13 par exemple n'a pas de clé, 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 type de secret ne satisfait pas les utilisateurs de chiffrement, car la conception d'un bon algorithme est très difficile, une fois découvert il n'offre plus de sécurité, et tous les messages qui ont été chiffré par lui deviennent accessibles. On peut modifier le ROT13 en changeant la valeur du décalage, cette valeur devenant alors la clé. L'ensemble des clés possibles — l'espace des clés — offre alors 26 décalages possibles. Bien qu'un peu plus fastidieux, le déchiffrement reste accessible même à la main. Et avec des ordinateurs, on peut tester des milliards de milliards de clés.

On voit se dégager de cet exemple l'importance de cette clé 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 clé doit pouvoir prendre suffisamment de valeurs pour qu'une attaque exhaustive — essai systématique de toutes les clés — 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 clés 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^{[Qui ?]} en décembre 2001, l'AES, utilise des clés 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³⁸ clés possibles ; l'âge de l'univers étant de 10¹⁰ années, si on suppose qu'il est possible de tester 1 000 milliards de clés par seconde (soit 3,2×10¹⁹ clés 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 peut 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 clé 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. L'inconvénient est que pour chiffrer un message de n bits, il faut au préalable avoir échangé une clé 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 le Kremlin et la Maison Blanche.

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 — et les transpositions — les symboles ne sont pas modifiés mais changent de place. Lorsque la substitution appliquée dépend de la place de la lettre dans le texte, on parle de substitution polyalphabétique — e.g. le chiffre de Vigenère, Enigma —, en opposition à la substitution monoalphabétique où la substitution est la même pour toutes les lettres — e.g. un décalage simple.

Dans la série des substitutions figurent 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 i^e lettre donne la valeur du i^e décalage. Clarifions par un exemple.

Message clair   : wikipedia
Mot clé         : crypto
Message chiffre : yzixisfzy

Un 'a' dans le mot clé correspond à un décalage de 0, un 'b' à un décalage de 1, etc. Dans notre exemple, la clé a 6 lettres, donc les lettres 1 ('w') et 7 ('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 clé, à écrire le message sous ce mot clé et à lire le texte en colonne, par ordre alphabétique.

Message           : wikipediaestuneencyclopedielibre
Mot clé           : crypto

on écrit sous       wikipe
le mot clé          diaest
                    uneenc
                    yclope
                    dielib
                    re****

lettre du mot clé
(ordre alphabétique) coprty

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

Message chiffré   : wduydr etceb* ieeol* iincie psnpi* kaele*

Les astérisques sont ajoutés pour le déchiffrement et les espaces dans le message chiffré uniquement pour la lisibilité. Le message, s'il était par exemple envoyé à un destinataire qui connaît le mot clé, serait le suivant :

Message chiffré   : wduydretceb*ieeol*iinciepsnpi*kaele*

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 chiffré ayant changé, 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 ajouté (cf. XOR) à la suite binaire à chiffrer. Les techniques utilisées pour générer la suite que l'on ajoute -- appelée la 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, est en général construite sur un modèle itératif. Ce modèle utilise une fonction F qui prend une clé k et un message M de n bits. C'est cette fonction F qui est itérée un certain nombre de fois, on parle de nombre de tours. À chaque tour, la clé 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 clés k_i utilisées sont déduites d'une clé maître K qui est la quantité secrète que doivent partager émetteur et destinataire. L'algorithme générant ces clés à partir de K est appelé l'algorithme de cadencement de clés.

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 clé k et message M pouvoir recalculer M à 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 à deux endroits, l'algorithme de cadencement de clé et la robustesse de la fonction F. Si l'algorithme de cadencement est mal conçu, les k_i peuvent être déductibles les unes des autres, ou mal réparties, … Dire de la fonction F qu'elle est robuste signifie qu'on la suppose difficile à inverser sans connaître la clé k ayant servi 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 clé k, c'est-à-dire en calculant

1) X = G(k,C) ;

2) Y = F(k,X) ;

et cela pour toutes les clés k jusqu'à ce que l'on en trouve une pour laquelle Y est égal à C. On est alors assuré d'avoir le message M qui n'est autre que X. Le problème étant que si k est constitué 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) clés par seconde, soit environ 2³⁰, il y a 31 557 600 secondes par an, soit 2²⁵, en conséquence on peut tester 2⁵⁵ clés 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 répandue pour fabriquer des fonctions F est celle du schéma de Feistel. Dans ce schéma, le message à chiffrer est découpé en 2 blocs de ⁿ⁄₂ 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 clé 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

• Cryptologie
• Cryptographie asymétrique
• Cryptographie hybride
• Chiffre de Vigenère
• TAREC

• Portail de la cryptologie