On présente ici les méthodes de cryptographie et de cryptanalyse qui ont été utilisées pendant des siècles, jusqu'aux années 1950.
Notez dès à présent que les techniques actuelles n'ont plus rien à voir avec ce folklore...
On peut considérer que le chiffrement par substitution est le plus élémentaire des chiffrements.
C'est le code de César :
Le chiffrement de César est donc un décalage de $k$ unités dans l'alphabet. Pour déchiffrer, on effectue un décalage de $k$ unités dans l'autre sens.
Si l'on devine que le chiffrement est obtenu par décalage, et si l'on ne connaît pas la clé : il suffit d'essayer toutes les possibilités.
Le chiffrement de César opère une translation (modulo 26) de $k$ cases.
On peut améliorer le chiffrement par substitution en utilisant une permutation quelconque de l'alphabet. C'est-à-dire : une bijection de {A, ..., Z } dans lui-même.
Cette fois-ci, en l'absence de la clé de chiffrement, tester toutes les possibilités est illusoire.
En effet, pour l'image du A, on a 26 possibilités ; pour le B, 25, etc. Soit $26 ! = 403291461126605635584000000$ possibilités...
On retrouve le principe de Kerckhoffs (1883) : la sécurité du système ne repose pas sur le secret de l'algorithme, mais sur celui de la clé.
On pourrait considérer Al-Kindi comme le père de la cryptanalyse. Au $IX^e$ siècle, il décrivit la technique d'analyse des fréquences, dans un manuscrit consacré au déchiffrement des messages.
On suppose connaître la langue dans laquelle le message est écrit.
En français, le $e$ apparaît en moyenne dans 16% des cas. Viennent ensuite le $a$ et le $i$, avec des fréquences respectives de 9,5% et 8,5%. On remplace alors les symboles du cryptogramme par les lettres en fonction de leur fréquence.
Pour que ça marche, le texte chiffré doit être assez long.
De plus, si cette analyse permet de repérer les $e$, $a$ et $i$, sans forcément bien les différentier, il n'en va pas de même avec les lettres à faible fréquence. Il reste donc un travail d'interprétation à faire, derrière, d'autant plus dûr que le chiffré est court.
Enfin, La disparition, de Georges Perec, est un livre sans $e$...
On peut mal orthographier le message en clair, avant de le chiffrer (écrire phonétiquement, etc.)
On peut aussi remplacer chaque lettre par plusieurs substituts, en nombre inversement proportionnel à la fréquence de la lettre.
Par exemple, la lettre $a$ apparaissant en français neuf fois plus souvent que la lettre $z$ (je crois), on remplacera donc chaque $z$ par 9 $z$, pour que ces lettres aient la même fréquence dans le texte crypté.
Dans le chiffrement par substitution :
Dans le chiffrement par transposition (ou par permutation) :
Ce mode de chiffrement est tout aussi ancien que le chiffrement par substitution. Cette méthode était employée à Sparte, au $V^e$ siècle av. J.-C...
La scytale spartiate est un bâton autour duquel on enroule une bande de cuir.
L'expéditeur écrit le message dans le sens de la longueur de la scytale : lorsqu'il déroule la lanière, le texte perd son sens.
Pour déchiffrer, le destinataire doit enrouler à nouveau la lanière sur sa scytale.
L'analyse des fréquences ne donne rien contre ce chiffrement : les lettres ne sont que déplacées.
On peut cependant l'adapter, en faisant l'analyse des fréquences des couples de lettres.
On ne cherchera donc que parmi les $\sigma^{-1}$ tels que chaque $q$ est suivi de $u$, etc.
Pour contre-attaquer, on peut s'arranger pour qu'il n'y ait pas de couple de lettres remarquables.
Le peintre italien Alberti a le premier proposé, au XVième siècle, d'utiliser 2 ou plusieurs alphabets chiffrés, et de passer de l'un à l'autre au cours du chiffrement.
Vigenère, au XVIième siècle, a développé l'idée d'Alberti, en utilisant 26 alphabets distincts pour chiffrer un message.
Les chiffrements antérieurs par substitution peuvent être qualifiés de chiffrement par substitution monoalphabétique, celui de Vigenère de chiffrement polyalphabétique.
On considère, à titre d'exemple :
| Alphabet ordinaire | a | b | c | d | e | f | |
| Alphabet chiffré | 1 | B | C | D | E | X | A |
| Alphabet chiffré | 2 | M | A | V | B | R | U |
La traduction de FADE sera donc AMER (on alterne entre les deux alphabets chiffrés).
On commence par constituer un carré de Vigenère :
| a | b | c | d | e | ... | x | y | z | |
| 1 | B | C | D | E | F | ... | Y | Z | A |
| 2 | C | D | E | F | G | ... | Z | A | B |
| 3 | D | E | F | G | H | ... | A | B | C |
| 4 | E | F | G | H | I | ... | B | C | D |
| . | . | . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . | . | . |
| 25 | Z | A | B | C | D | ... | W | X | Y |
| 26 | A | B | C | D | E | ... | X | Y | Z |
On a un message à chiffrer : lemessageachiffrer.
On s'est mis d'accord sur une clé de chiffrement, par exemple : cledechiffrement.
On peut donc obtenir le cryptogramme :
| clé | c | l | e | d | e | c | h | i | f | f | r | e | m | e |
| message | l | e | m | e | s | s | a | g | e | a | c | h | i | f |
| cryptogramme | n | p | q | h | w | u | h | o | j | f | ... | ... | ... | ... |
En effet, à l'intersection de la ligne commençant par C (ligne 2) et de la colonne commençant par L, se trouve N, etc.
Le chiffre de Vigenère ne peut être attaqué par l'analyse des fréquences. De plus, il possède un nombre énorme de clés. Il a donc longtemps été considéré comme inviolable...
Réalisez le chiffre de Vigenère.
Le chiffre de Vigenère était considéré inviolable jusqu'au milieu XIXième. Babbage, vers 1850, réussit le premier à le casser.
Dans le chiffre de Vigenère, une lettre, donc un mot, est chiffré de différentes manières, selon sa position dans le texte.
Toutefois, si un même mot intervient un nombre de fois supérieur à la longueur du mot-clé, il sera chiffré au moins 2 fois de la même façon.
Babbage cherche donc les séquences de lettres qui apparaissent plus d'une fois dans le texte chiffré.
Cela peut provenir :
Si la séquence répétée est assez longue (au moins 4 lettres), alors on est sûrement dans le premier cas.
Ayant relevé les séquences qui se répètent, on note le nombre de symboles entre ces deux répétitions. La longueur du mot-clé doit être un diviseur de ces écarts, donc de leur PGCD. On est donc à peu près assuré de la longueur $l$ du mot-clé, mais on n'en connaît pas encore les lettres $k_1 k_2 ... k_l$.
La ligne $k_1$ du carré de Vigenère a été utilisée pour chiffrer les lettres aux places $1, l + 1, 2l + 1, ...$
Les lettres du chiffré ayant la même position ont donc été obtenues par un chiffrement monoalphabétique (décalage), utilisant l'alphabet de la ligne $k_1$. On peut donc pratiquer, sur cet ensemble de lettres, une analyse des fréquences.
Comme il s'agit d'un chiffrement par permutation circulaire (une translation, un code de César), l'analyse des fréquences est aisée.
Trouver la translation revient aussi à trouver $k_1$. On recommence alors le travail avec les lettres numérotées $2, 2 + l, 2 + 2l$, ...
Même si l'on n'a aucune idée de la longueur du mot-clé, on peut procéder à une analyse des fréquences des lettres dans chacune des progressions arithmétiques de raison $l$, pour tout $l$.
La mise en évidence de translations sur les tableaux de répartition des fréquences conduirait à la détermination des $k_i$ et de $l$.
Le point faible du chiffre de Vigenère réside dans sa nature cyclique : si on réussit à déterminer la longueur du mot-clé, le texte chiffré sera traité comme une série de $l$ chiffres monoalphabétiques.
On pourra alors résoudre chaque chiffre par une analyse des fréquences.
Si le mot-clé est long :
Si le mot-clé est aussi long que le message, la technique de cryptanalyse mise au point par Babbage ne peut fonctionner.
Cependant, même dans ce cas, il existe d'autres moyens d'attaque :
On peut ainsi, par essais et erreurs, essayer de placer des mots usuels dans le texte clair, en déduire des lettres du mot-clé, lettres que l'on gardera ou rejettera selon que la succession des lettres obtenues ne semble pas possible.
Ainsi donc, une clé dont la longueur est égale à celle du message n'assure pas à elle seule la sécurité.
Améliorez votre chiffre de Vigenère pour qu'il soit plus résistant aux attaques type Babbage.
Vers 1918, les cryptographes testèrent des clés aléatoires :
Ce système de Vernam, ou One-time pad, est impossible à briser : selon la théorie de l'information développée par Shannon à la fin des années 1940, c'est un système cryptographique parfait.
Cela vient du fait que l'information apportée par le message chiffré sur le message clair, ou sur la clé, est nulle. Et ce, même si l'on connaît un ou plusieurs messages chiffrés et leur cryptogramme.
Un tel système était utilisé encore récemment pour le téléphone rouge, entre la Maison Blanche et le Kremlin.
Mais ce système, parfait en théorie, est défectueux en pratique. Il faudrait arriver à engendrer des clés aléatoires très longues. Ces clés devraient être disponibles simultanément pour les émetteurs et les récepteurs.
Mettre en place le chiffrement de Vernam, pour des textes binaires :