Cryptographie!

Le chiffre homophone

Principe

La cryptographie par substitution mono-alphabétique simple ne résiste pas à l'analyse des fréquences. Si un E est toujours remplacé par le même symbole, ce symbole sera le plus fréquent dans le texte codé, et on pourra facilement le retrouver. Une idée très simple pour remédier à cela est que, pour chaque lettre, on prévoit non pas un, mais plusieurs symboles de substitution possibles. Au hasard, au fil du texte, c'est l'un ou l'autre des symboles qui sera choisi (et pas toujours le même). C'est ce que l'on appelle un chiffre homophone. Cette idée germa en Europe au début du XVè siècle (le premier exemple connu est un texte de Michele Steno, doge de Venise, datant de 1411, où il se contente d'associer plusieurs symboles aux voyelles).

Il y a plusieurs techniques pour mettre en oeuvre un chiffre homophone. On peut se contenter de remplacer toutes les lettres par le même nombre de symboles, ce qui divise un peu la fréquence de chaque symbole, mais n'empêche toutefois pas une analyse des fréquences. L'idéal, en réalité, est de prévoir un nombre de symboles de substitution proportionnel à la fréquence de la lettre dans l'alphabet. Par exemple, le E a une fréquence d'environ 17% dans la langue française. On prévoit de le remplacer par 17 symboles. Le W est très rare. Un seul symbole suffira! Avec les tableaux de fréquence des lettres en français, on peut imaginer le tableau de substitution suivant, où on remplace chaque lettre par un nombre à deux chiffres :

LettreFréquence Symboles
A8,01 09, 12, 33, 47, 53, 67, 78, 92
B0,8848
C3,2313, 41, 62
D3,9101, 03, 45, 79
E17,5214, 16, 24, 25, 31, 39, 44, 46, 55, 57, 64, 74, 81, 82, 87, 98
F1,0610
G1,066
H0,8823
I7,3532, 50, 70, 73, 83, 88, 93
J0,4415
K0,054
L5,7726, 37, 51, 84, 88
M2,922, 27, 56
N7,2218, 39, 58, 59, 66, 71, 91
O5,4300, 05, 54, 72, 90
P2,9407, 38, 95
Q1,1494
R6,6929, 35, 40, 42, 77, 80
S8,1711, 19, 36, 43, 65, 76, 86, 96
T7,0717, 20, 30, 49, 69, 75, 97
U608, 52, 60, 61, 63, 99
V1,4134
W0,0289
X0,4728
Y0,32
Z0,1221

Ainsi, avec le tableau de substitution précédent, le mot EVENEMENT pourra être codé 253455588756149117, mais ce n'est qu'une possibilité parmi beaucoup d'autres! C'est donc un chiffre pour lequel une analyse directe des fréquences ne peut pas être envisagée.

Bien sûr, ce chiffre n'est pas sans défauts. Le tableau précédent n'est pas très simple à construire (il ne faut pas qu'il y ait redondance), et il n'est pas non plus très simple à mémoriser! Ainsi, les gens qui communiquaient avec un chiffrement homophone fixaient souvent un tableau de substitution sans en changer. Si ce tableau tombait dans des mains ennemies, tous les messages chiffrés devenaient lisibles!

Une autre possibilité était de faire appel à une technique de mémorisation plus aisée pour construire un chiffrement homophone, en utilisant notamment le carré de Polybe. L'idée est d'écrire les 25 lettres (on identifie I et J, ou V et W) dans un tableau 5×5, comme le suivant :

A Z T F I
U B D E K
L M N O P
Q C S X R
V W G Y H

On remplace alors une lettre par un couple de lettres dont la première se situe sur la ligne de la lettre initiale et la seconde se situe sur la ligne de la lettre initiale. Par exemple, on peut remplacer B par n'importe quel couple UZ, UM, UC, UW, DZ, DM, DC, DW, EZ, EM, EC, EW, KZ, KM, KC, KW. La clé de chiffrement est alors le tableau, qui peut être aisé à construire (on se donne par exemple un mot pour remplir les premières cellules du tableau, puis on complète par l'ordre alphabétique). Le problème, cette fois, c'est qu'on peut à nouveau vaincre le chiffre par une analyse des fréquences. En effet, les couples associés à E (UF, UO, …) seront plus fréquents que les couples associés à B par exemple!

Une autre variante est donnée par le schéma suivant : on inscrit maintenant à gauche de chaque ligne et en haut de chaque colonne un certain nombre de chiffres, comme ci-dessous :

1,2,3,4,5 6 7 8 9
1,2,3,4,5 E A S T R
2 I B C D F
3 L G H K M
4 N O P Q V
5 U W X Y Z

On remplace alors chaque lettre par ses coordonnées dans le tableau, en mettant d'abord la ligne, puis la colonne. Ainsi, on peut remplacer E par 11,12,…,15,21,…,25,…,55, et A par 16,26,36,46,56. C'est mieux pour l'analyse des fréquences, mais cela redevient difficile de convenir d'une clé!

Le chiffre homophone est-il inviolable?

Puisqu'il résiste à une analyse des fréquences simples, on pourrait penser le chiffre homophone beaucoup plus sûr que les simples chiffres de substitution mono-alphabétique. Il n'en est rien, et cela apparut très vite (dès François Viète au XVIè siècle). L'idée pour casser ce code est de faire une analyse des fréquences non pas lettre par lettre, mais par bigramme, c'est-à-dire par couple de deux lettres. Par exemple, dans la langue française, la lettre Q est assez rare, et est presque toujours suivie de la lettre U. Ainsi, le Q sera toujours remplacé par le même symbole, et toujours suivi d'un U, donc de 5 ou 6 symboles différents. Si on a un texte assez long, on pourra identifer un symbole qui aura cette propriété. On identifiera du même coup le Q et les différents symboles possibles pour le U. Continuant ainsi, on sait que derrière le U on aura toujours une voyelle, ce qui donnera aussi d'autres informations…

Ainsi, si le décryptage d'un chiffre homophone est un peu plus long, il est largement maîtrisé par les meilleurs cryptanalystes dès la renaissance. Ce qui est étonnant, c'est que le chiffre homophone domina l'Europe de 1500 à 1750 (ou plus précisément une de ses variantes, les nomenclateurs, où on ajoute quelques symboles pour remplacer des mots usuels). Pourtant, les chiffres polyalphabétiques comme le carré de Vigenère existaient déjà, et leurs failles n'apparurent qu'au XIXè siècle! Pendant plusieurs siècles, les cryptanalystes auront donc eu une grande avance sur les cryptographes!

Le chiffrement homophone en pratique
Consulter aussi