Histoire de la cryptographie
| Sommaire |
|
1.1 Les premières méthodes de chiffrement 1.1.1 Le plus vieux document crypté |
Dans l'Antiquité
Les premières méthodes de chiffrement
Le plus vieux document crypté
Le premier « document » crypté connu remonte à l'Antiquité. Il s'agit d'une tablette d'argile, retrouvée en Irak, et datant du XVIe siècle av. J.-C. Un potier y avait gravé sa recette secrète en supprimant des consonnes et en modifiant l'orthographe des mots.
La technique grecque
Entre le XXe et VIIe siècles av. J.-C., on utilise une scytale, également appelée bâton de Plutarque, pour encrypter les messages.
Seule une personne, disposant d'un bâton de diamètre identique à celui ayant servi à écrire le message, peut le déchiffrer.
La principale faiblesse de ce système réside dans le fait qu'un bâton d'un diamètre approximativement égal suffit à déchiffrer le texte. La sécurité réside donc sur le secret autour du procédé d'encryptage.
Nabuchodonosor
Aux alentours de -600, Nabuchodonosor, roi de Babylone, employait une méthode originale: il écrivait sur le crâne rasé de ses esclaves, attendait que leurs cheveux aient repoussé, et ils les envoyait à ses généraux. Il suffisait ensuite de raser à nouveau le messager pour lire le texte.
On remarque dans ce procédé une certaine fiabilité : en effet l'interception du message par un tiers est tout de suite remarquée.
Les premiers « vrais » systèmes de cryptographie
Il faut attendre -200 pour voir apparaître les premiers « vrais » systèmes de cryptographie. Ce sont essentiellement des chiffrements par substitution.
Il en existe 4 types de substitutions:
- mono-alphabétique : remplace chaque lettre du message par une autre lettre de l'alphabet
- poly-alphabétique : utilise une suite de chiffres mono-alphabétiques (la clé) réutilisée périodiquement
- homophonique : fait correspondre à chaque lettre du message en clair un ensemble possible d'autres caractères
- polygrammes : substitue un groupe de caractères dans le message par un autre groupe de caractères
Le code de César
Le code de César est la méthode cryptographique, mono-alphabétique, la plus ancienne communément admise par l'Histoire.
Méthode de chiffrement :
Son système est simple, il consiste à décaler les lettres de l'alphabet d'un nombre n. Par exemple, si on remplace A par D (n=3), on remplace B par E, C par F...
Le texte que nous souhaitons coder étant le suivant : « decaler les lettres de l'alphabet »
Le texte codé est alors : « ghfdohu ohv ohwwuhv gh o'doskdehw »
Les limites de ce procédé
Malheureusement, on comprendra que ce système est très peu sûr, puisqu'il n'y a que 26 lettres dans l'alphabet donc seulement 26 façons de crypter un message avec le code de César. Pourtant sa simplicité conduisit les officiers sudistes à le réemployer durant la guerre de Sécession. L'armée russe en fit de même en 1915.
Un système connu et pourtant...
Il est à noter que le code de César a été utilisé sur des forums internet sous le nom de ROT13 (rot-ation de 13 lettres ou A-->N...). Le ROT13 n'a pas pour but de rendre du texte confidentiel, mais plutôt d'empêcher la lecture involontaire (d'une réponse à une devinette, ou de l'intrigue d'un film, etc.). Son utilisation est simple: il suffit de re-crypter un texte, codé en ROT13, une deuxième fois pour obtenir le texte en clair.
Le carré de Polybe
L'historien grec Polybe est à l'origine du premier procédé de chiffrement par substitution homophonique.
Méthode de chiffrement:
C'est un système de transmission basé sur un carré de 25 cases (on peut agrandir ce carré à 36 cases, afin de pouvoir ajouter les chiffres ou pour chiffrer des alphabets comportant davantage de lettres, comme l'alphabet cyrillique).
En français, on supprime le W, qui sera remplacé par V. Il existe une variante où ce sont I et J qui se partagent la même case. Chaque lettre peut être ainsi représentée par un groupe de deux chiffres: celui de sa ligne et celui de sa colonne. Ainsi e=(1;5), u=(5;1), n=(3;4)...
Un moyen de transmission original
Polybe proposait de transmettre ces nombres au moyen de torches. Une torche à droite et cinq à gauche pour transmettre la lettre e par exemple. Ce procédé permettait donc de transmettre des messages sur de longues distances.
Son originalité
Les cryptologues modernes ont vu dans le « carré de 25 » plusieurs caractéristiques extrêmement intéressantes:
- la conversion de lettres en chiffres,
- la réduction de nombres, de symboles,
- la représentation de chaque lettre par deux éléments séparés.
Ce système de chiffrement peut être compliqué avec un mot de passe. Par exemple, si le mot de passe est DIFFICILE, on commencera à remplir le carré avec les lettres de ce mot, après avoir supprimé les lettres identiques, puis on complètera le tableau avec les lettres inutilisées.
De l'Antiquité à la guerre
Le chiffre de Vigenère
Blaise de Vigenère est l'auteur d'un des premiers systèmes « à mot de passe », c'est-à-dire un système de substitution poly-alphabétique. Cette méthode dominera trois siècles durant.
Méthode de chiffrement
On reporte les lettres de l'alphabet sur une grille de 26 x 26 cases; le première rangée contenant A, B, ..., les colones suivantes sont chacune décalée d'une position par rapport à la précédente. Le texte chiffré s'obtient en prenant l'intersection, de la ligne qui commence par la lettre à coder, avec la colonne qui commence par la première lettre du mot de passe, et ainsi de suite. Dès que l'on atteint la fin du mot de passe, on recommence à la première lettre. Pour décoder, il suffit de faire la même chose dans l'autre sens.
Les points forts de cette méthode
Cet algorithme de cryptographie comporte beaucoup de points forts. Il est très facile d'utilisation, et le décryptage est tout aussi facile si on connaît la clé. La grande caractéristique du chiffre de Vigenère est qu'il est impossible par une analyse statistique simple de retrouver où sont certaines lettres. Un autre avantage réside dans le fait que l'on peut produire une infinité de clés.
Le point faible de cet algorithme
Le principal point faible de ce système est qu'il est attaquable par analyse fréquentielle. De plus, il faut bien transmettre la clé au destinataire à un moment ou à un autre avec tous les risques que cela comporte.
Le chiffre de Delastelle
L'inventeur de ce système est un français nommé Félix-Marie Delastelle. Il utilise une grille de chiffrement/déchiffrement analogue à celle du chiffre de Polybe.
Méthode de chiffrement :
Tout d'abord, il faut regrouper les lettres du message clair 5 par 5 (au besoin, on rajoute des nulles pour arriver à un multiple de cinq).
Pour déchiffrer, on effectue l'opération dans le sens inverse.
Une simple adaptation
Le chiffre de Delastelle diffère peu de celui de Polybe. Il est présenté ici cependant pour montrer la diversité des méthodes de cryptage, mais aussi que la plupart de ces méthodes sont de simples adaptations de méthodes déjà existantes.
Grand chiffre du roi Louis XIV
Les historiens disposent de quelques documents qui ont été chiffrés par ce qu'on nomme le Grand chiffre du roi Louis XIV, et qui n'était en principe utilisé que pour des communications d'une importance extrême. C'est dire l'intérêt pour les historiens de connaître le contenu de ces documents, ou même simplement le sujet dont ils parlaient. Hélas, faute d'information même statistique sur la nature des textes, et de connaissance ne serait-ce que de quelques mots de leur contenu, et malgré la puissance des ordinateurs actuels et la compétence des services du Chiffre, aucun décryptage de ce code n'a encore abouti, ce qui peut laisser perplexe : y a-t-il vraiment quelque chose qui est codé sur ces documents, ou bien s'agit-il de simple bruit pour disperser l'attention des intercepteurs éventuels et le vrai message était-il transmis par des procédés de stéganographie ?
Lors de la Seconde Guerre mondiale :
La Machine Enigma
Enigma.jpg
Inventée pour les civils
L'histoire de la machine Enigma commence en 1919, quand un ingénieur hollandais, Hugo Alexander, dépose un brevet de machine à chiffrer électromécanique. Ses idées sont reprises par le Dr Arthur Scherbius, qui crée à Berlin une société destinée à fabriquer et à commercialiser une machine à crypter civile : l'Enigma. Cette société fait un fiasco, mais la machine Enigma a attiré l'attention des militaires.
Le fonctionnement d'Enigma
Le codage effectué par la machine Enigma est à la fois simple et astucieux. Chaque lettre est remplacée par une autre, l'astuce est que la substitution change d'une lettre à l'autre. La machine est alimentée par une pile électrique. Quand on appuie sur une touche du clavier, un circuit électrique est fermé, et une lampe s'allume qui indique quelle lettre codée l'on substitue. Concrètement, le circuit électrique est constitué de plusieurs éléments en chaîne:
- le tableau de connexions : il permet d'échanger des paires de l'alphabet, deux à deux, au moyen de fiches. Il y a 6 fiches qui permettent donc d'échanger 12 lettres. Un tableau de connexions est donc une permutation très particulière où on a échangé au plus 6 paires. Par exemple, dans le tableau suivant (avec simplement 6 lettres), on a échangé A et C, D et F, tandis que B et E restent invariants.
- les rotors : un rotor est également une permutation, mais cette fois quelconque. À chaque lettre en entrée correspond une autre lettre.
On peut composer les rotors, c'est-à-dire les mettre les uns à la suite des autres. La machine Enigma disposera, au gré de ses évolutions successives, de 3 à 6 rotors. Parmi ces rotors, seuls 3 sont utilisés pour le codage, et on a le choix de les placer dans l'ordre que l'on souhaite (ce qui constituera une partie de la clé). Surtout, les rotors sont cylindriques, et ils peuvent tourner autour de leur axe. Ainsi, à chaque fois qu'on a tapé une lettre, le premier rotor tourne d'un cran, et la permutation qu'il engendre est changée. Observons ce changement sur la figure suivante : le rotor transforme initialement D en B. Lorsqu'il tourne d'un cran, cette liaison électrique D--->B se retrouve remontée en C--->A.
Chaque rotor possède donc 26 positions. À chaque fois qu'une lettre est tapée, le premier rotor tourne d'un cran. Après 26 lettres, il est revenu à sa position initiale, et le second rotor tourne alors d'un cran. On recommence à tourner le premier rotor, et ainsi de suite... Quand le second rotor a retrouvé sa position initiale, c'est le troisième rotor qui tourne d'un cran.
- Le réflecteur : Au bout des 3 rotors se situe une dernière permutation qui permet de revenir en arrière. On permute une dernière fois les lettres 2 par 2, et on les fait retraverser les rotors, et le tableau de connexion.
Résumons sur la machine simplifiée suivante (6 lettres, 2 rotors) comment est codée la lettre A :
- on traverse le tableau de connexions : on obtient C
- on traverse les 2 rotors : on obtient successivement A et F
- on traverse le réflecteur où on obtient E, puis on renvoie dans les rotors pour obtenir F, A et finalement C après le tableau de connexions.
Remarquons que si on avait tapé C, le courant aurait circulé dans l'autre sens et on aurait obtenu A.
Nombre de clés possibles
Il y a trois éléments à connaître pour pouvoir coder un message avec la machine Enigma :
- la position des 6 fiches du tableau de connexion: d'abord, il faut choisir 12 lettres parmi 26. C'est donc le nombre de combinaisons de 12 parmi 26, soit 26! /(12!14!). Maintenant, il faut choisir 6 paires de lettres parmi 12, soit 12!/6!, et comme la paire (A,D) donne la même connexion que la paire (B,A), il faut encore diviser par 26. On trouve finalement 100 391 791 500.
- l'ordre des rotors: il y a autant d'ordres que de façons d'ordonner 3 éléments : 3!=6.
- la position initiale des rotors: chaque rotor ayant 26 éléments, il y a 26*26*26=17 576 choix.
On multiplie tout cela, et on obtient plus de 1016 possibilités, ce qui est énorme pour l'époque !
Il est important de remarquer que les permutations employées dans les rotors et les réflecteurs ne peuvent pas être considérées comme faisant partie du secret. En effet, toutes les machines utilisent les mêmes, et il suffit donc d'en avoir une à disposition. Les Anglais, par exemple, en ont récupéré une pendant la guerre dans un sous-marin coulé. Ceci est une illustration d'un principe général en cryptographie, dit principe de Kerckhoffs, qui veut que tout le secret doit résider dans la clé secrète de chiffrement et de déchiffrement, et pas dans une quelconque confidentialité de l'algorithme (ici de la machine) qui ne peut être raisonnablement garantie.
Point forts et faiblesses
Nous avons déjà décrit les points forts de la machine Enigma. Pour l'essentiel, c'est le nombre de clés énorme, et la réversibilité : si, avec la même clé secrète initiale, on tape le message clair, on obtient le message codé, et avec le message codé, on obtient le message clair.
L'une des failles de la machine Enigma est que jamais la lettre A ne sera codée par un A. Cela élimine un certain nombre de cas à inspecter. Une des autres faiblesse dépend plutôt du protocole utilisé par les Allemands : certains opérateurs - par exemple, ceux qui informaient de la météo - prenaient peu de précautions et commençaient toujours leurs messages par les mêmes mots (typiquement « Mon général... »). Les Anglais connaissaient ainsi pour une partie du message à la fois le texte clair et le texte codé, ce qui aide à retrouver la clé. Et comme c'est la même clé qui sert pour toutes les machines Enigma de l'armée allemande pour un jour donné, une erreur de protocole dans un message peut compromettre la sécurité de tous les autres!
Enigma et UNIX
Un étudiant s'amusa un jour à programmer en langage C la simulation du fonctionnement d'une machine Enigma. Ce programme fut inclus dans les distributions UNIX sous le nom de crypt (utilisable comme une commande UNIX). Jusqu'à la déclassification des travaux du groupe de Bletchley Park, les bureaux d'études d'engineering croyaient ce codage très sûr et l'utilisaient pour s'échanger leurs informations confidentielles. Pour la plus grande joie, n'en doutons pas, de la National Security Agency, qui en voyait son travail considérablement facilité!
Les Navajos
Bien que les moyens de cryptages électromécaniques, tels que la machine Enigma, aient prouvé leur efficacité en terme de sécurité, ils n'en restent pas moins encombrants et lents car nécessitant une double saisie des messages. Ces deux inconvénients majeurs rendant ce procédé quasiment inexploitable en milieu hostile, ils poussèrent les Américains à chercher un moyen de cryptage assurant une communication efficace sur le terrain lors de la guerre qui les opposa aux Japonnais.
Ce procédé fut imaginé par l'ingénieur américain Philip Johnston. Ce dernier ayant grandi dans les réserves navajos, il eut l'idée d'utiliser leur langue comme procédé cryptographique. La méconnaissance quasi totale de cette langue ainsi que sa construction grammaticale très particulière, la rendant impénétrable aux étrangers, décidèrent de son utilisation.
Cependant un problème majeur demeurait : les mots usuels employés par l'armée n'existaient pas dans la langue navajo. Il fut donc décidé de trouver une correspondance entre des mots navajos et le dialecte militaire. Cette table de correspondance fut établie par association d'idées afin de la rendre plus facilement mémorisable. Le terme « bombardier » fut par exemple traduit par « buse » alors que les « bombes » larguées par ces engins devenaient des « œufs » dans la langue navajo.
Voilà comment les Parleurs-de-code (Windtalkers) navajos prirent part à la campagne du Pacifique. Leur bravoure au combat fut reconnue de manière officielle par le gouvernement américain lorsqu'il leur dédia, en 1982, la journée du 14 août.
Liens externes
Travaux scolaires faits par des lycéens de terminale scientifique
Bibliographie
- L'histoire des codes secrets de Simon Singh.
- Un ouvrage passionnant sur l'histoire de la cryptographie. Il se lit comme un roman.
| Image manquante Key-crypto-sideways.png | Portail Cryptologie - Accédez d'un seul coup d’œil à toute la série des articles « Cryptologie » de Wikipédia. |