# Histoire de la cryptologie

Cet article résume l’histoire de la cryptologie de l’Antiquité à aujourd'hui. La cryptologie regroupe à la fois la cryptographie, associée aux techniques de chiffrement d’un message clair, et la cryptanalyse qui concerne l’analyse et le déchiffrement du message codé.

## Les premières méthodes de chiffrement de l'Antiquité
### Le plus vieux document chiffré

Le premier « document » chiffré 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

La première grande compilation des procédés cryptographique et stéganographique pratiqués durant l'Antiquité est celle du chapitre 31 de la Poliorcétique d'Énée le Tacticien, datant du IVe siècle av. J.-C.
Entre le Xe et le VIIe siècle av. J.-C. semble attestée une technique de chiffrement par transposition, c'est-à-dire reposant sur le changement de position des lettres dans le message, en utilisant un bâton de diamètre déterminé appelé scytale. On enroulait en hélice une bande de cuir autour de la scytale avant d'y inscrire un message. Une fois déroulé, le message était envoyé au destinataire qui possédait un bâton identique, nécessaire au déchiffrement. Cependant, l'utilisation de la scytale lacédémonienne comme procédé cryptographique n'est explicitement affirmée que par Plutarque et Aulu-Gelle, auteurs de la fin de l'Antiquité, et n'est pas mentionnée par Énée le Tacticien : dès lors, la scytale a-t-elle véritablement été un procédé cryptographique ?

### Histiée et la révolte de l'Ionie

Dans le Tome V des Histoires d'Hérodote, est reportée une technique de stéganographie qu'aurait employée le souverain de Milet durant La Révolte de l'Ionie.
Histiée aurait sélectionné son plus fidèle esclave, lui ayant ensuite fait raser la tête et tatouer (imprimé) un ordre de révolte sur le crâne ; Dès que les cheveux eurent repoussé, il l'envoya à Aristagoras qui lui rasa de nouveau la tête afin de lire le message.
   « XXXV. (...). Sur ces entrefaites, il arriva de Suses un courrier qui lui enjoignait de prendre les armes. Cet ordre était empreint sur la tête du courrier. Histiée, voulant mander à Aristagoras de se soulever, ne trouva pas d'autre moyen pour le faire avec sûreté, parce que les chemins étaient soigneusement gardés. »
— Hérodote, L'Enquête - Livre V (Terpsichore)

### Une technique des anciens Hébreux?

À partir de l'an mil, une technique de chiffrement par substitution (temura) est évoquée dans le Sefer HaZohar : il s’agit d'interpréter certains passages équivoques du livre de Jérémie (Jr 25 26, Jr 51 1 et Jr 51 41, Ve siècle av. J.-C.) comme une façon de nommer secrètement certains lieux.
Le chiffre le plus cité, appelé atbash, est une méthode de substitution alphabétique inversée. Son nom est formé par les initiales des premières et dernières lettres de l'alphabet hébreu aleph, tav, beth, shin.
Elle consiste à remplacer chaque lettre du texte en clair par une autre lettre de l'alphabet choisie de la manière suivante : A devient Z, B devient Y, etc.

### 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 existe trois types de substitutions :
* monoalphabétique : remplace chaque lettre du message par une autre lettre de l'alphabet ;
* polyalphabétique : utilise une suite de chiffres monoalphabétiques (la clé) réutilisée périodiquement ;
* 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, par substitution monoalphabétique, la plus ancienne (Ier siècle av. J.-C.).
Cette méthode est utilisée dans l'armée romaine, et bien qu'elle soit beaucoup moins robuste que la technique Atbash, la faible alphabétisation de la population la rend suffisamment efficace.

#### 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 chiffrer étant le suivant : « décaler les lettres de l'alphabet ».
Le texte chiffré est alors : « ghfdohu ohv ohwwuhv gh o'doskdehw ».

#### Limites du 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 25 façons de chiffrer un message avec le code de César (on ne peut substituer une lettre par elle-même). Pourtant, sa simplicité conduisit les officiers sudistes à le réemployer durant la guerre de Sécession. L'armée russe fit de même en 1915.

#### Un système connu et pourtant

Le code de César a été utilisé sur des forums Internet sous le nom de ROT13 (rotation 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 rechiffrer 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.

## Du Moyen Âge à la Première Guerre mondiale

* IXe siècle : Le savant arabe Al-Kindi écrit le premier manuscrit traitant de cryptanalyse Risalah fi Istikhraj al-Mu'amma (Manuscrit sur le déchiffrement de messages cryptographiques)$^,$. Il y fait la plus ancienne description de l’analyse des fréquences des lettres du texte chiffré, associée aux chiffrements par substitution monoalphabétique tels que celui utilisé par César. Cette méthode de cryptanalyse fut probablement utilisée pour déchiffrer les documents administratifs et économiques de l’Empire arabe, mais aussi pour reconstituer la chronologie des révélations du Coran.
* 1379 : Gabriele de Lavinde, secrétaire du pape, écrit un recueil de codes et de clés appelé nomenclateur. Ce dictionnaire permet de chiffrer des mots ou des syllabes courants et sera utilisé pendant plusieurs siècles par les diplomates européens et américains.

### XVe siècle

* 1412 : Les connaissances de la civilisation arabe dans le domaine de la cryptologie sont exposées dans Subh al-a sha, une encyclopédie en 14 volumes écrite par l'Égyptien al-Qalqashandi.
* 1467 : Le savant italien Leon Battista Alberti expose pour la première fois le chiffrement par substitution polyalphabétique qu'il applique à l'aide d'un disque à chiffrer. Ce procédé consiste à remplacer chaque lettre du texte en clair par une lettre d'un autre alphabet et à changer plusieurs fois d'alphabet de substitution au cours du chiffrement, rendant la cryptanalyse par analyse de fréquence inefficace. Le principe du disque à chiffrer sera repris et amélioré par le colonel Wadsworth en 1817, puis par Charles Wheatstone en 1867. Alberti présente aussi pour la première fois le surchiffrement codique, c'est-à-dire le chiffrement du texte déjà chiffré une première fois, technique qui ne sera réellement utilisée que plusieurs siècles plus tard.
* 1474, un contemporain d'Alberti, Cicco Simonetta, cryptanalyste au service du duc de Milan, écrit Liber Sifrorum, un traité de cryptanalyse.

### XVIe siècle

* 1518 : Le moine bénédictin Jean Trithème écrit Polygraphiæ, le premier livre imprimé traitant de cryptologie, dans lequel il expose un procédé stéganographique consistant à remplacer chaque lettre du texte en clair par un groupe de mots, le texte chiffré ressemblant alors à un poème. Trithème expose aussi une technique de chiffrement par substitution polyalphabétique à l'origine de la technique connue sous le nom de chiffre de Vigenère.
* 1553 : Giovan Battista Bellaso publie le livre La Cifra, un recueil de clés littérales utilisées dans les chiffrements par substitution polyalphabétique, faciles à retenir et à utiliser, qu'il appelle « mots de passe ».
* 1563 : L'Italien Giambattista della Porta expose dans son livre De Furtivis Literarum Notis, vulgo de ziferis les connaissances en cryptologie connues jusqu'à cette époque. Il expose une technique de substitution diagrammatique consistant à remplacer chaque couple de lettres du texte en clair par un symbole et présente un procédé de chiffrement par substitution polyalphabétique utilisant onze alphabets différents qui restera efficace pendant trois siècles.

#### Le chiffre de Vigenère

En 1586, le diplomate français Blaise de Vigenère présente dans son livre Traité des chiffres, ou Secrètes manières d'écrire une technique de chiffrement par substitution polyalphabétique inspirée de celle de Trithème. Le chiffrement de Vigenère ne sera cassé qu'en 1854.

##### Méthode de chiffrement

Le chiffrement utilise une clé littérale ou mot de passe, dont chaque lettre indique le décalage alphabétique à appliquer sur le texte en clair.
On reporte les lettres de l'alphabet sur une grille de 26 × 26 cases ; la première rangée contenant A, B,… les colonnes suivantes sont chacune décalées 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échiffrement 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. Il fallut attendre près de trois siècles pour qu'il soit cryptanalysé au milieu du XIXe siècle. Voir Cryptanalyse du chiffre de Vigenère.

### XVIIe siècle

* 1623 : Dans son livre De dignitate et augmentis scientiarum, Francis Bacon expose une technique stéganographique qui consiste à représenter chaque lettre du texte en clair par un groupe de cinq lettres A ou B. Le texte chiffré résultant est ainsi constitué d'une succession de ces deux lettres. Ce procédé est équivalent à un codage binaire des lettres de l'alphabet sur 5 bits (de type Code Baudot), préfigurant le codage numérique des lettres sur 8 bits utilisé actuellement en informatique (code ASCII).
* 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, ils durent attendre longtemps la solution de ce mystère. Vers 1893, Étienne Bazeries les en délivra finalement après presque deux siècles de perplexité.

### XIXe siècle

* Les moyens de transmissions sont utilisés avec un système de codage dès le XIXe siècle — et même depuis 1794 pour le télégraphe optique de Chappe, qu'entre 1834 et 1835, deux banquiers, les célèbres frères jumeaux Joseph et François Blanc, détourneront, de connivence avec deux employés du télégraphe entre Bordeaux et Tours, pour transmettre avec leur propre code des informations avant qu'elles n'arrivent par les voies officielles$^,$.
* 1854 : Un pionnier du télégraphe, Charles Wheatstone, apporte sa contribution à la cryptologie en inventant le chiffrement de Playfair, du nom de celui qui l'a fait connaître. Cette technique est basée sur une méthode de substitution diagrammatique consistant à remplacer un couple de lettres adjacentes par un autre couple choisi dans une grille qui constitue la clé. Voir Code commercial (cryptologie)
* 1854, l'Anglais Charles Babbage déchiffre le chiffrement par substitution polyalphabétique de Vigenère, exposé en 1586. Cependant, il ne publie pas ses travaux et cette avancée importante dans l'histoire de la cryptanalyse est attribuée au Polonais Friedrich Kasiski en 1863.
* 1883 : Le Hollandais Auguste Kerckhoffs publie un ouvrage sur la cryptologie : La cryptographie militaire. Il y expose notamment quelques règles à respecter pour concevoir un bon système cryptographique, toujours valables actuellement, dont la principale est la suivante : la sécurité d'un système ne doit pas reposer sur le secret de la méthode de chiffrement (voir Sécurité par l'obscurité).

#### Le chiffre de Delastelle

L'inventeur de ce système est 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 par groupes de 5 par 5 (au besoin, on rajoute des nulles pour arriver à un multiple de 5).
Pour déchiffrer, on effectue l'opération dans le sens inverse.

##### Une simple adaptation

Ce chiffre diffère peu de celui de Polybe. Il est présenté ici pour montrer la diversité des méthodes de chiffrement : la plupart de ces méthodes sont de simples adaptations de méthodes déjà existantes.

## La Première Guerre mondiale

La Première Guerre mondiale marque la victoire tant attendue de la cryptanalyse face à la cryptographie, empêtrée dans des impératifs d'efficacité.
Pendant la guerre de 14-18, la maîtrise cryptanalytique des Français les aide considérablement à déchiffrer les messages ennemis. En 1914, le premier déchiffrement est fait par le commandant Louis Thévenin qui donne aux alliés un avantage important dès le début du conflit (association du chiffre et de la sécurité de l'information n°28/2000). L'État-major met en place un service spécial appelé le « cabinet noir » et chargé de déchiffrer les messages allemands. Le déchiffrement, le 1er juin 1918, d'un radio télégramme allemand par le lieutenant Georges Painvin s'est ainsi révélé déterminant pour contrer une des dernières offensives allemandes. Évoquant ce lieutenant, Georges Clemenceau aurait prétendu qu'à lui tout seul, il valait un corps d'armée.
Le télégramme Zimmermann, intercepté en 1917 par le Royaume-Uni qui cryptanalysa son contenu, a accéléré l'entrée en guerre des États-Unis.
La rapidité des transmissions a bénéficié des progrès du XIXe siècle, et est désormais instantanée, mais le déchiffrage des messages chiffrés, réalisé à la main, reste très lent, nécessitant souvent plusieurs heures.
Le chiffrement-déchiffrement entièrement manuel est donc susceptible d'être erroné. Il doit être relativement simple et rapide à appliquer (une heure environ) pour transmettre les informations à temps et éviter les erreurs de codage dues au stress du champ de bataille. Les chiffres utilisés n'assurent ainsi pas un niveau satisfaisant de sécurité, mais aujourd'hui avec l'informatique, le recours aux machines permet de dire qu'on est entré, avec la cryptologie, dans l'ère de la science.

## Lors de la Seconde Guerre mondiale

La cryptologie a joué un rôle décisif pendant la Seconde Guerre mondiale. Les exploits des alliés en matière de cryptanalyse auraient permis d'écourter la guerre (de un à deux ans, selon certains spécialistes). Churchill citait la cryptologie comme l'un des facteurs clés de la victoire.

### La machine Enigma
#### Inventée pour les civils

L'histoire de la machine Enigma commence en 1919, quand un ingénieur hollandais, Hugo Alexander Koch, dépose un brevet de machine à chiffrer électromécanique. Ses idées sont reprises par le D$^r$ Arthur Scherbius, qui crée à Berlin une société destinée à fabriquer et à commercialiser une machine à chiffrer civile : l'Enigma. Cette société fait un fiasco, mais la machine Enigma a attiré l'attention des militaires.

#### Le fonctionnement d'Enigma

Le chiffrement 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 lettre d'un tableau d'affichage s'allume qui indique par quelle substitution le chiffrement a été effectué. 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 en place dans la machine, 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 trois 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 chiffrée la lettre A :
* le courant traverse le tableau de connexions : on obtient C ;
* il traverse les 2 rotors : on obtient successivement A et F ;
* il traverse le réflecteur où on obtient E, puis il repasse 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 déchiffrer un message chiffré au moyen d'une 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!) = 9 657 700 ; maintenant, il faut choisir 6 paires de lettres parmi 12, soit 12!/6!, et comme la paire (A, B) donne la même connexion que la paire (B, A), il faut encore diviser par 2$^6$ ; 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 10$^{16}$ possibilités, ce qui est énorme pour l'époque.
Les circuits du courant électrique à l'intérieur de la machine ne peuvent pas être considérés comme faisant partie du secret. En effet, toutes les machines d'un même modèle utilisent les mêmes, et il suffit donc d'en avoir une à disposition. Les Britanniques, par exemple, en ont récupéré plusieurs qu'ils ont copiées en nombre. D'ailleurs, le principe d'Enigma est connu, les Britanniques en fabriquent une version très améliorée, la machine Typex. 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é de chiffrement et de déchiffrement, et non pas dans une quelconque confidentialité de l'algorithme (ici de la machine) qui ne peut être raisonnablement garantie.

#### Points forts et faiblesses

Nous avons déjà décrit les points forts de la machine Enigma. Pour l'essentiel, c'est le nombre presque infini de clés, et la réversibilité : si, avec la même clé, on tape le message clair, on obtient le message chiffré, et avec le message chiffré, 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. Autre caractéristique, deux lettres différentes frappées à la suite (ex. AB) ne donnent jamais, deux fois de suite, la même lettre chiffrée (ex. CC). Cela élimine un certain nombre de combinaisons. Autre faiblesse, les fautes des chiffreurs : certains chiffreurs envoient des messages du même format avec des mots récurrents. C'est le cas des messages météo qui circulent par Enigma, mais aussi dans des réseaux moins protégés. Les Britanniques connaissent alors, pour une partie du message, à la fois le texte clair et le texte chiffré. Et comme la même clé sert à toutes les machines Enigma d'un même réseau, pour un jour donné, une erreur de protocole dans un message compromet tous les messages de ce réseau, ce jour-là !

#### Le déchiffrement des messages Enigma

Le service de renseignements polonais fut le premier à attaquer le chiffre Enigma, dans les années 1930. Les Polonais travaillèrent ensuite en collaboration avec le service cryptographique du 2e bureau français, dirigé par le colonel Gustave Bertrand, aidé par les informations de la taupe Hans-Thilo Schmidt (« Asche » pour les services français, était aussi nommée « Source T » par les services du Contre-Espionnage français). Finalement, une collaboration s'instaura avec les services britanniques, qui rassemblèrent leurs spécialistes (en particulier Alan Turing) cryptographes à Bletchley Park.
L'Enigma navale est sensiblement différente des autres versions. La position initiale est indiquée par des combinaisons de lettres manipulées à partir de tables de bigrammes. Les chiffreurs de la Kriegsmarine ne font pas de fautes. Codés avant d'être chiffrés, les messages sont trop courts pour donner prise au déchiffrement. Le trafic des U-Boot est illisible.
Les bombes électromécaniques utilisées pour reconstituer la clé des messages Enigma sont réglées par des Wrens (marinettes) d'après les instructions des cryptanalystes. Une fois découverte la clé quotidienne d'un réseau, les messages sont déchiffrés par les équipes de déchiffrement. Le rôle des bombes est juste de trouver la clé. Trois à quatre mille messages étaient déchiffrés chaque jour par les 9 000 hôtes de Bletchley Park.

#### 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'ingénierie estimaient ce chiffrement très sûr et l'utilisaient pour échanger leurs informations confidentielles, pour la plus grande joie de la National Security Agency qui voyait son travail considérablement facilité.

### Le chiffre Lorenz
#### Le chiffre des hauts dirigeants allemands

Si la machine Enigma est la plus connue, l'attaque de la machine de Lorenz, utilisée par le haut commandement ennemi pour chiffrer ses téléimpressions, est à l'origine d'immenses progrès des sciences et des techniques.

#### Casser du code ?

Le chiffre Enigma n'a jamais été « cassé ». Les fautes des chiffreurs et la puissance des bombes (plusieurs centaines à la fin de la guerre) ont permis de trouver, certains jours, la clé quotidienne de certains réseaux. Il s'agit d'une attaque par force brute.

#### L'analyse du chiffre Lorenz

Le chiffre Lorenz pratiquait le chiffrement par flot (stream cipher). Ce type de chiffrement a une faiblesse : il devient trivial à inverser lorsque deux messages sont chiffrés avec la même clé.
En considérant qu'A est le texte clair, que B est la clé, et que le message chiffré est A + B ou A', si deux messages sont chiffrés avec la même clé, A' = A + B et C' = C + B, il suffit de faire l'addition des deux textes chiffrés pour éliminer la clé.
A' + C' = (A + B) + (C + B) = (A + C) + (B + B) = A + C puisque B + B = 0.
Puisque tous les effets de la clé sont maintenant retirés, il ne reste qu'à faire une analyse statistique pour séparer les deux textes A et C et retrouver ainsi chacun d'eux. La clé devient aussi triviale à calculer (elle est égale à A' + A).
C'est la plus grande faiblesse de ce chiffre.
Un chiffreur a transmis un long message pour recevoir en réponse un NACK (message non reçu). Plutôt que de respecter les règles et produire une nouvelle clé, il a repris la même clé et a renvoyé son message. S'il avait renvoyé exactement le même texte lettre par lettre, l'attaque n'aurait pas été possible. Par contre, en utilisant un diminutif ici et un synonyme là, il a techniquement envoyé ce second message chiffré avec la même clé.
Après avoir retrouvé les deux messages et la clé unique, celle-ci a révélé ses secrets. La technique utilisée chiffrait les lettres sur cinq bits où chaque bit traversait un canal de chiffrement différent. La clé a montré certaines répétitions. De celles-ci a été déduit tout le principe de la génération de la clé et celui de la machine Lorenz. Une autre distinction entre Enigma et Lorenz est que les Alliés avaient mis la main sur plusieurs Enigma qu'ils ont copiées en nombre. Au contraire, les Alliés ne virent une authentique machine Lorenz qu'après la fin de la guerre.

#### La faiblesse du chiffre Lorenz

Si le mécanisme de génération de clé de Lorenz était maintenant connu, il ne suffisait pas à déchiffrer les autres messages chiffrés. De plus, l'analyse statistique de la clé montrait que celle-ci resterait aléatoire sur chaque canal même si elle était contrôlée par des paramètres non aléatoires comme la prépondérance de certaines lettres dans une langue.
Une faiblesse dans le code Lorenz a malgré tout été trouvée. Deux lettres consécutives identiques produisaient un résultat constant sur chacun des cinq canaux dans le texte chiffré. Un exemple est le doublon « SS », en plus de ceux imposés par la langue.

#### Retombées de la guerre du chiffre Lorenz

Trouver une faille est une chose, l'exploiter en est une autre. En effet, l'analyse statistique nécessaire pour retrouver ces doublons demandait une puissance indisponible par les moyens connus. Or, c'est à cette époque que fut développée l'arme ultime du déchiffrement, l'ordinateur Colossus.
C'est donc grâce à Colossus que le chiffre Lorenz a pu être cassé. Le détail de ses algorithmes déborde toutefois les objectifs de cette section.
Le plus grand hommage est prononcé par un Allemand qui compare l'effort massif des Alliés aux attaques nucléaires contre le Japon.

### Le code navajo

Bien que les moyens de chiffrements électromécaniques, telle la machine Enigma, aient prouvé leur efficacité en matière de sécurité, ils n'en restent pas moins encombrants et lents.
Un chiffre transmis en morse est quasiment inexploitable en première ligne. Les Américains cherchaient un moyen de codage qui protège les échanges de phonie à la radio, sur le terrain, lors de la guerre qui les opposa aux Japonais.
L'ingénieur américain Philip Johnston, qui avait grandi dans les réserves navajos, eut l'idée d'utiliser leur langue comme code. Pratiquement inconnue, cette langue, d'une construction grammaticale très particulière, est impénétrable.
Cependant, un problème existait : les mots usuels de l'armée n'existaient pas dans la langue navajo. Il fut donc décidé d'inventer des équivalents entre des mots navajos et le dialecte militaire. Ce lexique fut établi par associations d'idées afin de le 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 guerre 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

## Cryptologie moderne
### Claude Shannon

Claude Shannon est considéré par plusieurs comme le père de la cryptographie mathématique. Il a travaillé pendant plusieurs années dans les Laboratoires Bell où il a produit un article intitulé A Mathematical Theory of Cryptography (Une théorie mathématique de la cryptographie). Cet article a été écrit en 1945 et a été publié dans le Bell System Technical Journal en 1949. Shannon a continué son travail en produisant un autre article intitulé A Mathematical Theory of Communication. La guerre avait poussé Shannon à s'intéresser à la cryptographie parce que les messages secrets sont une application intéressante de la théorie de la communication. Il est communément admis que son premier article, publié en 1949, a été le point de départ du développement de la cryptologie moderne.
Shannon a défini les deux principaux objectifs de la cryptologie : le secret et l'authentification. Il a mis l'accent sur l'exploration du secret et, trente-cinq ans plus tard, G. J. Simmons aborderait la question de l'authentification. L'article A Mathematical Theory of Communication souligne l'un des aspects les plus significatifs de l'œuvre de Shannon : la transition de la cryptologie de l'art à la science.
Dans ses articles, Shannon a décrit les deux types de secrets. Les premiers sont ceux conçus avec l'intention de protéger un message contre des adversaires disposant de ressources infinies pour décoder un message (le secret théorique), et les seconds sont ceux qui visent à protéger un message contre des adversaires ayant des ressources limitées pour décoder un message (le secret pratique). La plupart des travaux de Shannon concernent le secret théorique. Shannon a introduit une définition de l'invulnérabilité d'un chiffrement. Un chiffrement invulnérable est considéré comme « un secret parfait ». Shannon a démontré que le secret parfait ne pouvait être obtenu qu'avec une clé secrète dont la longueur est égale la longueur de l'information à chiffrer.
Le travail de Shannon a influencé la recherche sur la cryptographie jusque dans les années 1970 comme le démontre le fait que les développeurs de la cryptographie à clé publique, Martin Hellman et Whitfield Diffie, ont mentionné les articles de Shannon comme une de leurs influences principales. Son travail a également influencé les conceptions modernes de chiffrement à clé secrète. À la fin des travaux de Shannon, les progrès de la cryptographie ont ralenti jusqu'à ce que Hellman et Diffie présentent leur document sur la cryptographie à clé publique.

### Les années 1970

Dans les années 1970, l'utilisation des ordinateurs a permis trois avancées majeures publiques (c'est-à-dire non secrètes et non contrôlées par les services de renseignement) :
* le développement d'un standard public de chiffrement ;
* le développement de l'échange de clés Diffie-Hellman ;
* le développement du chiffrement asymétrique.

#### Le développement d'un standard public de chiffrement

La première de ces avancées fut la publication du projet Data Encryption Standard (DES) dans le Federal Register (en) le 17 mars 1975. Le chiffrement DES avait été proposé par un groupe de recherche d'IBM, à l'invitation du National Bureau of Standards (maintenant National Institute of Standards and Technology ou NIST), dans le but de développer des moyens de communication électroniques sécurisés pour les entreprises telles que les banques et d'autres grandes organisations financières. Après des conseils et des modifications par la National Security Agency (NSA), le chiffrement a été adopté et publié en tant que Federal Information Processing Standard Publication (FIPS ; en français, publication d'un standard fédéral de traitement d'information) en 1977 (actuellement le FIPS 46-3).
DES était basé sur une clé secrète de 56 bits. DES a été le chiffrement accessible au public et béni par une agence nationale, telle que la NSA. La publication des spécifications de ce chiffrement par le NBS a grandement stimulé l'intérêt public et universitaire pour la cryptographie.
En 1984, le chiffrement DES à 56 bits est renforcé et devient la variante DESX basée sur une clé de 119 bits. Le chiffrement est renforcé une seconde fois pour devenir la variante Triple DES basée sur une clé de 168 bits en 1998. Le chiffrement DES vieillissant a été officiellement remplacé par le chiffrement Advanced Encryption Standard (AES) en 2001, lorsque le National Institute of Standards and Technology (NIST) a annoncé le Federal Information Processing Standard (FIPS) 197. Après un concours ouvert, NIST a sélectionné un chiffrement présenté par deux cryptographes belges comme le nouveau standard nommé AES. Bien que le standard AES soit, en 2016, largement implanté, des variantes de DES qui avaient été incorporées dans de nombreuses normes nationales et organisationnelles (comme le Triple DES) subsistent encore dans certaines applications.
À cause des avancées de la cryptanalyse et de l'augmentation de la puissance des ordinateurs, le standard original DES avec sa clé de 56 bits est clairement inadéquat pour protéger un message contre des attaques par force brute. Une telle attaque, menée par l'association Electronic Frontier Foundation en 1997, a réussi à briser ce chiffrement en 56 heures.

#### Le développement de l'échange de clés Diffie-Hellman

Le deuxième développement, en 1976, était peut-être encore plus important, car il a fondamentalement changé le fonctionnement des systèmes cryptographiques. Ce fut la publication de l'article New Directions in Cryptography (Nouvelles directions en cryptographie) par Whitfield Diffie et Martin Hellman. Cet article a introduit une méthode radicalement nouvelle de distribuer les clés cryptographiques, ce qui a résolu un des problèmes fondamentaux de la cryptographie : la distribution des clés. Ce mode de distribution des clés est appelé l'échange de clés Diffie-Hellman. L'article a également stimulé le développement presque immédiat d'une nouvelle classe d'algorithmes de chiffrement, les algorithmes de chiffrement asymétrique.
Avant cette date, tous les algorithmes de chiffrement (anciens et modernes) avaient été des algorithmes de chiffrement symétrique dans lesquels la même clé cryptographique est utilisée avec l'algorithme sous-jacent à la fois par l'expéditeur et le destinataire, qui doivent tous les deux connaître la clé et la garder secrète. Toutes les machines électromécaniques utilisées dans la Seconde Guerre mondiale utilisaient ce type d'algorithme, tout comme le code de César et le code Atbash des Hébreux et tous les systèmes de chiffrement à travers l'histoire. En pratique, la distribution des clés et leur protection posent de grands défis et réduisent considérablement la possibilité d'utiliser ce type de chiffrement et sa sécurité, surtout lorsqu'un grand nombre de personnes doivent connaître la clé.
Dans de tels systèmes, la clé devait être échangée entre les parties qui communiquent d'une façon sécuritaire avant toute utilisation (le terme généralement utilisé est « via un canal sécurisé ») comme un courrier fiable avec une mallette menottée à son poignet, un contact en face à face ou un pigeon fidèle. Cette exigence n'est jamais anodine et elle devient très rapidement ingérable lorsque le nombre de participants augmente ou lorsque des canaux sécurisés ne sont pas disponibles pour l'échange de clés ou lorsque les clés doivent être fréquemment changées. De plus, si un émetteur envoie des messages à plusieurs personnes d'un groupe et que chaque destinataire d'un message doit être le seul à pouvoir le déchiffrer, l'émetteur doit échanger une clé via un canal sécurisé avec chaque personne du groupe. Un système de ce type est connu comme un chiffrement à clé secrète ou à clés symétriques. L'échange de clés Diffie-Hellman (et les améliorations et les variantes suivantes) a simplifié l'opération de tels systèmes et les a rendus plus sûrs que ce qui avait été possible auparavant dans toute l'histoire.

#### Le développement du chiffrement asymétrique

Le chiffrement asymétrique utilise une paire de clés mathématiquement liées, dont chacune déchiffre le chiffrement effectué par l'autre. Ces algorithmes ont la propriété supplémentaire que l'une des clés appariées ne peut être déduite de l'autre par tout procédé connu autre que de très nombreux essais et erreurs. Un algorithme de ce type est appelé algorithme de chiffrement à clé publique ou algorithme à clé asymétrique. Avec un tel algorithme, une seule paire de clés suffit pour permettre à une personne de communiquer avec plusieurs destinataires. En désignant une clé de la paire comme privée (toujours secrète), et l'autre comme publique (souvent largement disponible), aucun canal sécurisé n'est nécessaire pour l'échange de clés. Tant que la clé privée reste secrète, la clé publique peut être largement connue durant une longue période sans compromettre la sécurité, permettant de réutiliser la même paire de clés indéfiniment.
Pour que deux utilisateurs d'un algorithme à clés asymétriques puissent communiquer en toute sécurité sur un canal non sécurisé, chaque utilisateur doit connaître sa clé publique et sa clé privée ainsi que la clé publique de l'autre utilisateur. Voici un scénario de base : Alice et Bob ont chacun une paire de clés qu'ils ont possiblement utilisées pendant des années avec de nombreux autres utilisateurs. Au début de leur conversation, ils échangent leurs clés publiques en clair sur un canal non sécurisé. Alice chiffre ensuite un message en utilisant sa clé privée, puis chiffre à nouveau le résultat en utilisant la clé publique de Bob. Le message doublement chiffré est ensuite envoyé d'Alice à Bob sur un canal non sécurisé. Bob reçoit le flux de bits et le déchiffre en utilisant sa propre clé privée, puis le déchiffre de nouveau en utilisant la clé publique d'Alice. Si le résultat final est reconnaissable comme un message, Bob est certain que le message provient de quelqu'un qui connaît la clé privée d'Alice (probablement Alice elle-même si elle a bien protégé sa clé privée), et que quiconque a écouté le message sur le canal non sécurisé n'a pu déchiffrer le message parce qu'il n'avait pas la clé privée de Bob.
Les algorithmes de chiffrement asymétrique dépendent pour leur efficacité d'une classe de fonctions mathématiques appelées fonctions à sens unique, qui nécessitent relativement peu de puissance de calcul à exécuter, mais de vastes quantités de calcul pour inverser, si l'inversion est possible. Un exemple classique d'une fonction à sens unique est la multiplication de très grands nombres premiers. Il est facile de multiplier deux grands nombres premiers, mais très difficile de trouver les facteurs du produit de deux grands nombres premiers.
En raison des caractéristiques des fonctions à sens unique, la plupart des clés possibles sont de mauvais choix comme clés de chiffrement ; seule une petite fraction des clés possibles est acceptable. Conséquemment, les algorithmes de chiffrement asymétrique nécessitent des clés très longues pour atteindre le même niveau de sécurité que les clés de chiffrement symétrique qui sont relativement plus courtes. La nécessité de générer des paires de clés très longues et d'effectuer les opérations de chiffrement et de déchiffrement en utilisant ces longues clés rendent les algorithmes de chiffrement asymétrique coûteux en calcul comparativement à la plupart des algorithmes de chiffrement symétrique. Étant donné que ceux-ci peuvent utiliser comme clé secrète n'importe quelle suite de bits (au hasard, ou du moins imprévisibles), une clé secrète jetable peut être rapidement générée pour utilisation à court terme dans une seule session. Par conséquent, il est de pratique courante d'utiliser de longues clés asymétriques pour échanger une clé symétrique jetable beaucoup plus courte (mais tout aussi forte). L'algorithme de chiffrement asymétrique lent envoie, en toute sécurité, une clé de session symétrique ; l'algorithme de chiffrement symétrique, plus rapide, prend ensuite le relais pour le reste de la communication.

#### Découvertes gardées secrètes par le service de renseignements du Royaume-Uni

La cryptographie asymétrique, l'échange de clés Diffie-Hellman et le plus connu des algorithmes de cryptographie asymétrique (appelé habituellement le chiffrement RSA) semblent avoir été développés indépendamment par le Government Communications Headquarters (GCHQ), le service de renseignements électroniques du gouvernement du Royaume-Uni, avant le premier article sur cette branche de la cryptographie, publié par Diffie et Hellman en 1976. En effet, le GCHQ a publié des documents affirmant qu'il avait développé la cryptographie à clé publique avant la publication de l'article de Diffie et Hellman. Divers articles classifiés secrets ont été rédigés au GCHQ pendant les années 1960 et 1970 et ont finalement conduit à des algorithmes essentiellement identiques au chiffrement RSA et à l'échange de clés Diffie-Hellman en 1973 et 1974, soit quelques années avant la publication de ces algorithmes par des universitaires américains. Certains de ces articles ont maintenant été publiés et les inventeurs (James Ellis, Clifford Cocks et Malcolm Williamson) ont rendu publics leurs travaux.

### Le hachage

En plus de permettre les trois avancées majeures mentionnées précédemment, les ordinateurs ont permis de développer des fonctions de hachage cryptographiques et de les utiliser dans divers contextes.
Le hachage est une fonction appliquée à une chaîne de caractères ou de bits pour produire une valeur de hachage (une suite de bits). La valeur de hachage est une empreinte numérique du message. La valeur de hachage est également appelée message digest ou somme de contrôle. La fonction de hachage fournit une sortie de longueur fixe : quelle que soit la longueur du message qu'on lui soumet, la fonction de hachage produit toujours une valeur de hachage contenant le même nombre de bits.
Une fonction de hachage cryptographique est une fonction de hachage qui possède certaines caractéristiques. En particulier, une fonction de hachage cryptographique est une fonction à sens unique, c'est-à-dire une fonction dont l'inverse est impossible à calculer, même en utilisant une grande puissance de calcul durant une longue période de temps.

#### Utilisations des fonctions de hachage cryptographiques
##### Vérification de l'intégrité d'un message

Le hachage permet de déterminer si un message a été changé dans la transmission. Si la valeur de hachage du message reçu est différente de celle produite avant l'envoi du message, le message a été modifié.
Il est important de noter que le hachage est différent du chiffrement. Le hachage est une opération à sens unique (non réversible) qui est utilisé pour transformer un message en une valeur de hachage (une suite de bits). En comparant la valeur de hachage d'un message avant et après la transmission, on peut voir si le message a été altéré durant la transmission. Il est impossible de recréer un message à partir de sa valeur de hachage parce qu'il y a perte d'information. Le chiffrement est une opération réversible (donc sans perte d'information) qui est utilisée pour transformer un texte clair en texte chiffré incompréhensible par un adversaire. Arrivé à destination, le message chiffré peut être déchiffré pour être compréhensible par le destinataire.

##### Signature de documents

Les algorithmes de cryptographie qui permettent de vérifier l'authenticité d'une signature numérique sur un document ne fonctionnent pas de façon efficace sur des documents volumineux. On utilise donc le hachage pour produire une empreinte d'un document qui peut être traitée plus facilement par un algorithme de vérification de signature.

##### Validation de mot de passe

Le hachage cryptographique est utilisé par les systèmes informatiques pour valider un mot de passe sans en garder une copie. Il serait imprudent pour un système informatique de conserver une copie des mots de passe de ses utilisateurs, car ces mots de passe pourraient être volés par des employés responsables de l'entretien du système ou des pirates informatiques. Plutôt que de conserver les mots de passe, les systèmes informatiques hachent les mots de passe immédiatement après leur création et ne conservent que leur valeur de hachage. Lors de la validation d'un mot de passe, le système hache le mot de passe fourni par l'utilisateur et compare la valeur de hachage obtenue avec la valeur de hachage enregistrée lors de la création du mot de passe.
Comme les fonctions de hachage cryptographiques sont des fonctions à sens unique, un intrus qui aurait accès à la table des valeurs de hachage des mots de passe ne pourrait utiliser cette information pour calculer les mots de passe.

### Cryptographie et gouvernements

Les développements publics de la cryptographie des années 1970 ont brisé le quasi-monopole détenu par les organismes gouvernementaux sur la cryptographie de haute qualité. Pour la première fois, les organismes non gouvernementaux ont eu accès à une cryptographie de qualité dont les codes sont incassables — même par les gouvernements.
Des controverses et des conflits, à la fois publics et privés, ont commencé plus ou moins immédiatement. Ces conflits ont reçu le nom de Crypto Wars en français : « guerres de la cryptographie ». Ces guerres se poursuivent aujourd’hui, même dans les pays occidentaux démocratiques. Dans de nombreux pays, par exemple, l’exportation de la cryptographie est soumise à des restrictions. Jusqu’en 1996, l’exportation d'algorithmes cryptographiques utilisant des clés de plus de 40 bits était fortement limitée aux États-Unis. En 2004, l’ancien directeur du FBI, Louis Freeh, témoignant devant la Commission nationale sur les attaques terroristes contre les États-Unis, a appelé à de nouvelles lois contre l’utilisation publique du chiffrement.
L’une des personnes les plus militantes en faveur de cryptage fort pour l’usage public a été Phil Zimmermann. Il a développé, puis distribué Pretty Good Privacy (PGP), un système de cryptographie de très haute qualité. Il a distribué une version gratuiciel de PGP quand il s’est senti menacé par une législation alors en cours d’examen par le gouvernement américain qui exigerait l’inclusion de portes dérobées dans tous les produits cryptographiques développés aux États-Unis. Son système a été distribué dans le monde entier peu de temps après sa distribution aux États-Unis. Le département de la Justice des États-Unis a mené une longue enquête criminelle sur Phil Zimmermann pour violation alléguée de restrictions à l’exportation. Le département de la Justice a finalement abandonné son enquête et la distribution gratuite de PGP a continué dans le monde entier. PGP a même fini par devenir un standard Internet ouvert (RFC 2440 ou OpenPGP).

### Cryptanalyse moderne

Bien que le chiffrement AES et les chiffrements asymétriques de bonne qualité soient largement considérés comme incassables, des conceptions et des implantations déficientes de chiffrements sont encore parfois mises en production, ce qui a conduit à des bris de chiffrement au cours des dernières années.
Des exemples notables de systèmes cryptographiques cassés sont :
* le WEP, le premier système de cryptage Wi-Fi ;
* le Content Scrambling System utilisé pour le chiffrement et le contrôle de l'utilisation de DVD ;
* les chiffrements A5/1 et A5/2 utilisés dans les téléphones cellulaires GSM ;
* le chiffrement Crypto-1 (en) utilisé dans les cartes à puce Mifare classiques largement déployées de la compagnie NXP Semiconductors, une division essaimée de Philips.
Tous les chiffrements mentionnés au paragraphe précédent sont des chiffrements symétriques.
Jusqu'à présent, aucun des algorithmes mathématiques utilisés dans la cryptographie à clés publiques n'a été prouvé comme incassable. Conséquemment, des découvertes mathématiques ou l'augmentation de la puissance des ordinateurs pourraient les rendre non sécuritaires. Cependant, peu de cryptologues prévoient de telles percées dans un futur prévisible. En revanche, des avancées mathématiques et l'augmentation graduelle de la puissance et de la disponibilité des ordinateurs affaiblissent les algorithmes de chiffrement et forcent les cryptographes à utiliser des clés de plus en plus longues.

### Cryptographie post-quantique

En cryptographie, la cryptographie post-quantique (parfois appelée quantum-proof, quantum-safe ou quantum-resistant) fait référence à des algorithmes cryptographiques (généralement des algorithmes à clé publique) qui sont censés être protégés contre une attaque cryptanalytique par un ordinateur quantique. Le problème avec les algorithmes actuellement populaires est que leur sécurité repose sur l'un des trois problèmes mathématiques difficiles : le problème de la factorisation d'entiers, le problème du logarithme discret ou le problème du logarithme discret à courbe elliptique. Tous ces problèmes pourraient être facilement résolus sur un ordinateur quantique suffisamment puissant exécutant l'algorithme de Shor.
Même si les ordinateurs quantiques actuels manquent de puissance de traitement pour casser tout algorithme cryptographique réel, de nombreux cryptographes conçoivent de nouveaux algorithmes pour se préparer à une époque où l'informatique quantique deviendra une menace. Ce travail a suscité une plus grande attention de la part des universitaires et de l'industrie grâce à la série de conférences PQCrypto depuis 2006 et plus récemment par plusieurs ateliers sur la cryptographie quantique sûre organisés par l'Institut européen des normes de télécommunications (ETSI) et l'Institute for Quantum Computing (en)$^,$.
Contrairement à la menace que représente l'informatique quantique pour les algorithmes à clé publique actuels, la plupart des algorithmes cryptographiques symétriques actuels et des fonctions de hachage sont considérés comme relativement sûrs contre les attaques des ordinateurs quantiques. Bien que l'algorithme quantique de Grover accélère les attaques contre les chiffrements symétriques, doubler la taille de la clé peut bloquer efficacement ces attaques. Ainsi, la cryptographie symétrique post-quantique n'a pas besoin de différer significativement de la cryptographie symétrique actuelle.

### Algorithmes

La recherche en cryptographie post-quantique se concentre principalement sur cinq approches différentes :

### Cryptographie basée sur les réseaux

Cette approche comprend des systèmes cryptographiques tels que Ring learning with errors (ring-LWE), les anciens schémas de chiffrement NTRU et la nouvelle signature NTRU et signatures BLISS. Certains de ces schémas, comme le chiffrement NTRU, ont été étudiés pendant de nombreuses années sans que personne trouve d'attaque réalisable. D'autres, comme les algorithmes ring-LWE, ont des preuves que leur sécurité se réduit à un problème dans le pire des cas. Le groupe d'étude sur la cryptographie post-quantique parrainé par la Commission européenne a suggéré que la variante Stehle – Steinfeld de NTRU soit étudiée pour la normalisation plutôt que l'algorithme NTRU. À cette époque, NTRU était encore breveté. Des études ont indiqué que NTRU peut avoir des propriétés plus sûres que d'autres algorithmes basés sur les réseaux.

### Cryptographie multivariée

Cela inclut les systèmes cryptographiques tels que le schéma Rainbow (Unbalanced Oil and Vinegar) qui est basé sur la difficulté de résoudre des systèmes d'équations multivariées. Diverses tentatives pour construire des schémas de chiffrement d'équations multivariées sécurisés ont échoué. Cependant, des schémas de signature multivariés comme Rainbow pourraient fournir la base d'une signature numérique sécurisée quantique.
De nos jours, il existe de nouveaux types d'attaques de récupération de clé contre le schéma de signature Rainbow. Les nouvelles attaques surpassent les attaques précédemment connues pour tous les ensembles de paramètres soumis au NIST et rendent pratique la récupération de clé pour les paramètres SL 1. Concrètement, étant donné une clé publique Rainbow pour les paramètres SL 1 de la soumission du second tour. Elle renvoie la clé secrète correspondante après en moyenne 53 heures (un week-end) de temps de calcul sur un ordinateur portable standard.

### Cryptographie basée sur le hachage

Cela inclut les systèmes cryptographiques tels que les signatures Lamport, le schéma de signature Merkle, XMSS, SPHINCS et les schémas WOTS. Les signatures numériques basées sur le hachage ont été inventées à la fin des années 1970 par Ralph Merkle et ont été étudiées depuis comme une alternative intéressante aux signatures numériques basées sur la théorie des nombres comme RSA et DSA. Leur principal inconvénient est que pour toute clé publique basée sur le hachage, il existe une limite au nombre de signatures pouvant être signées à l'aide de l'ensemble de clés privées correspondant. Ce fait avait réduit l'intérêt pour ces signatures jusqu'à ce que l'intérêt soit ravivé en raison du désir d'une cryptographie résistante aux attaques des ordinateurs quantiques. Il ne semble pas y avoir de brevets sur le schéma de signature Merkle et il existe de nombreuses fonctions de hachage non brevetées qui pourraient être utilisées avec ces schémas. Le schéma de signature basé sur le hachage avec état XMSS développé par une équipe de chercheurs sous la direction de Johannes Buchmann est décrit dans la RFC 8391. Notez que tous les schémas ci-dessus sont des signatures uniques ou limitées dans le temps, Moni Naor et Moti Yung ont inventé le hachage UOWHF en 1989 et a conçu une signature basée sur le hachage (le schéma Naor-Yung) qui peut être utilisée pour une durée illimitée (la première signature de ce type qui ne nécessite pas de propriétés de trappe).

### Cryptographie basée sur les codes

Cela inclut les systèmes cryptographiques qui reposent sur des codes correcteur d'erreurs, tels que les algorithmes de chiffrement McEliece et Niederreiter et le schéma de signature Courtois, Finiasz et Sendrier associé. La signature McEliece originale utilisant des codes Goppa aléatoires a résisté à un examen minutieux pendant plus de 40 ans. Cependant, de nombreuses variantes du schéma McEliece, qui cherchent à introduire plus de structure dans le code utilisé afin de réduire la taille des clés, se sont révélées peu sûres. Le groupe d'étude sur la cryptographie post-quantique parrainé par la Commission européenne a recommandé le système de chiffrement à clé publique McEliece comme candidat pour une protection à long terme contre les attaques des ordinateurs quantiques.

### Cryptographie basée sur les isogénies

La cryptographie basée sur les isogénies ou sur les courbes elliptiques (en anglais, elliptic curve cryptography ou ECC) regroupe un ensemble de techniques cryptographiques qui utilisent une ou plusieurs propriétés des courbes elliptiques, ou plus généralement d'une variété abélienne. L'usage des courbes elliptiques en cryptographie a été suggéré, de manière indépendante, par Neal Koblitz et Victor S. Miller en 1985. L'utilisation de ces propriétés permet d'améliorer les primitives cryptographiques existantes, par exemple en réduisant la taille des clés cryptographiques, ou de construire de nouvelles primitives cryptographiques qui n'étaient pas connues auparavant.