TPE : cryptographie

Le chiffre de Vigenère

Maintenant avec la méthode des fréquences d'Al Kindi on se rend bien compte des faiblesses de la cryptographie par substitution monoalphabétique comme pour le chiffre de César. Or entre le chiffre de César et le XVI^e siècle, aucun procédé nouveau de cryptograghie d'une part sûre (pour les moyens de l'époque) et d'autre part simple d'utilisation ne fut mis en place. Un diplomate français de la Renaissance, Blaise de Vigenère

Blaise de Vigenère (1523-1596) était un diplomate, cryptographe et alchimiste français. Le chiffrement de Vigenère lui doit son nom. Il est possible qu'au XIX^e, il lui ait été faussement attribué.

imagina de faire varier le décalage du code de César en fonction d'une clef. Il s'agit du premier chiffre de substitution polyalphabétique

substitution polyalphabétique (chiffre de) : chiffre de substitution où l'alphabet chiffré change au cours du chiffrement, comme dans le chiffre de Vigenère. Ce changement s'exécute selon une clef.

.
Le tableau ci-dessous est le carré de Vigenère, il permet le chiffrement d'une substitution polyalphabétique. Dans ce tableau à double entrées, les lettres minuscules correspondent à l'alphabet clair (il s'agit d'une convention), les colones correspondent aux différents alphabets chiffrés en fonction de la clef (alphabet crypté et clef sont en majuscules, c'est aussi par convention).

Voyons comment chiffrer CRYPTOGRAPHIE avec le chiffre de Vigenère. Nous choisissons une clef, par exemple : TPE.
On chiffre d'abord le c avec le T de la clef, cela nous donne V.

Puis on chiffre le r avec le P de la clef, on obtient G.

Le y est chiffré par le E de la clef, on obtient C.

Le p est chiffré par le T de la clef, on obtient I.

On procède de même jusqu'à la fin. CRYPTOGRAPHIE chiffré par le procédé de Vigenère avec une clef TPE donne : VGCIISZGEIWMX

Les coïncidences de Friedman

Le chiffre de Vigenère met en échec tout cryptanalyse s'appuyant directement sur l'analyse de fréquences, il sera longtemps considéré comme "le chiffre indéchiffrable". Ce n'est en effet qu'au XIX^e siècle qu'un réel procédé algorythmique sera mis en place pour déchiffrer une pareille substitution polyalphabétique.
William Friedman

William Friedman (1891-1969), cryptologue dans l'armée américaine. Inventeur de l'indice de coïncidence, Friedman participera à l'effort de guerre contre les Japonais dès 1939 en s'attaquant au code 97. Après la guerre, il devient cryptologue en chef à la NSA.

a trouvé une formule simple associant à chaque texte un nombre. La considération de ce nombre, appelé indice de coïncidence, permet de déchiffrer les chiffres de Vigenère comme ceux de tout chiffrement polyalphabétique (ainsi que les chiffrements produits par la machine Enigma).

L'invention de l'indice de coïncidences est typique de l'ère industrielle. Auparavant il aurait été pratiquement inexploitable. Les calculs sont trop longs à faire à la main (à grande échelle surtout). Cependant, l'invention de la mécanographie les a rendus possible dès les débuts du XX^e siècle. Ceux effectués sur cette page ont été réalisés sans l'aide de l'informatique.

L'idée de Friedman est d'introduire un indice invariable par permutation des lettres. Sa valeur n'est donc pas modifiée par une substitution alphabétique simple, telle que celles engendrées par le code de César. Il permet ainsi de retrouver facilement la longueur d'une clef de Vigenère.
On appelle indice de coïncidence d'un texte la probabilité de tirer au hasard deux lettres identiques dans ce texte.

Si le nombre de A est égale à N_A, le nombre de façons de tirer deux A au hasard dans le texte est :

Si le nombre de B est égale à N_B, le nombre de façons de tirer deux B au hasard dans le texte est :

etc. (Explication détaillée)

En faisant la somme de tout ceci, on obtient le nombre de couples formés de deux lettres identiques.
Le nombre de couples quelconques dans le texte est égale à :

donc la probabilité pour que deux lettres coïncident vaut :

A partir des fréquences usuelles, on peut ainsi déterminer l'indice de coïncidence moyen d'un texte français. En faisant la somme des carrés des fréquences des lettres données dans le tableau des fréquences d'Al-Kindi, nous obtenons 0.0746 qui est donc l'indice de coïncidence moyen des textes écrits en français.

Dans le cas du message :

HOXDZXYBTEIOAOWNZBJYZMMKSDJESOWSASJBJKHMWYHRFXYPTVQOROSDFECRJB GOXNJCMKNVQYSCIKWQJXYYZVJCTVJSQNJVFWTXYKLXJPNOWOQENDHOXDZXUOYSY FFVVENWTEXCJNJBFITXXESCTVIKYTJESOGYZMMOTEAOWDJDJDJXZOJDQKSEVEJLFSL XFXYNFXXVJPWKNCHBJCXYSLQOZNTBYSQOXDJDJXIEIKSCQRJBGOXYZCQKSEJZFVJNF XXCTXQSYFJBYYZVFVZWNOWOUVJEYVJCUSJNXNFXXVJCLVFOZVXSQNTBYCTEWSFXY MTWROXYZBNBFSYESOSPFXYWFVFNJSQPFSYESCTWROSKYEWOGOWMJVJMMKZNJ WJXYSQKKBTSIVJCUKWPZWXXJPTXYZFCKBNCXYSXJBXKSKWSSONVIYWDIKSCQOXYQ ONVQKRKNXXEWCFZTSYBNXJDWKSAZSQVJSQKIOZHYBTEXBTELOXKZMTDJNWYND

Calculons l'indice de coïncidence du texte si la clef de chiffrement a pour longueur 1 :

lettre	A	B	C	D	E	F	G	H	I	J	K	L	M
n	4	18	20	15	21	23	4	6	10	42	24	6	11
n(n-1)	12	306	380	210	420	506	12	30	90	1722	552	30	110

lettre	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
n	26	31	7	19	7	38	21	4	24	25	44	35	21
n(n-1)	650	930	42	342	42	1406	420	12	552	600	1892	1190	420

La somme des occurences est égale à 506, celle des n(n-1), 12878. L'indice de coïncidence de ce texte chiffré est donc égal à 12878 divisé par 506 x 505 = 255 530 soit 0,05 si la clef du chiffrement a pour longueur 1. Cet indice ne correspond pas à l'indice moyen d'un texte écrit en français. Par conséquent, la clef n'a pas pour longueur 1.

Calculons l'indice de coïncidence du texte si la clef de chiffrement a pour longueur 2 :

Pour une clef de chiffrement de longueur 2, une lettre sur deux est chiffrée de la même façon. Ainsi dans notre message, les lettres suivantes sont chiffrées de la même façon si la longueur de la clef du chiffrement est égale à 2 :

HXZYTIAWZJZMSJSWAJJHWHFYTQRSFCJGXJMNQSIWJYZJTJQJFTYLJNWQNHXZUYY FVNTXJJFTXSTIYJSGZMTAWJJJZJQSVJFLFYFXJWNHJXSQZTYQXJJIISQJGXZQSJFJF XTQYJYZFZNWUJYJUJXFXJLFZXTYTWFYTRXZNFYSSFYFFJQFYSTRSYWGWJJMZJ JYQKTIJUWZXJTYFKNXSJXSWSNIWISQXYQNQRNXWFTYNJWSZQJQIZYTXTLXZTJWN

lettre	A	B	C	D	E	F	G	H	I	J	K	L	M
n	3	0	1	0	0	21	4	5	9	42	2	4	4
n(n-1)	6	0	0	0	0	420	12	20	72	1722	2	12	12

lettre	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
n	13	0	0	17	4	19	20	4	2	17	21	23	18
n(n-1)	156	0	0	272	12	342	380	12	2	272	420	506	306

La somme des occurences (n) est égale à 253, celle de n(n-1), 4958. L'indice de coïncidence de ce texte chiffré est donc égal à 4958 divisé par 253 x 252 = 63756 soit 0,078 si la longueur de la clef du chiffrement vaut 2. L'indice de coïncidence moyen d'un texte écrit en français étant 0,0746 notre indice qui vaut 0.078 rend hautement probable que la longueur de la clef soit égale à 2.

La méthode des fréquences permet maintenant de retrouver le message clair en obtempérant comme pour le chiffre de César. En effet en sachant que la clef à pour longueur 2, on divise le texte en deux (car une lettre sur deux est crypté de la même façon) et on procède à une analyse des fréquences sur chacun de ces textes. Ici, on trouve qu'une lettre sur deux est chiffrée selon une clef F et que l'autre partie l'est selon une clef K : on trouve par conséquent que la clef vaut FK.
Ainsi le texte clair est le suivant :

C'EST UN TROU DE VERDURE OU CHANTE UNE RIVIERE ACCROCHANT FOLLEMENT AUX HERBES DES HAILLONS DARGENT OU LE SOLEIL DE LA MONTAGNE FIERE LUIT C'EST UN PETIT VAL QUI MOUSSE DE RAYONS UN SOLDAT JEUNE BOUCHE OUVERTE TETE NUE ET LA NUQUE BAIGNANT DANS LE FRAIS CRESSON BLEU DORT IL EST ETENDU DANS L'HERBE SOUS LA NUE PALE DANS SON LIT VERT OU LA LUMIERE PLEUT LES PIEDS DANS LES GLAEULS IL DORT SOURIANT COMME SOURIRAIT UN ENFANT MALADE IL FAIT UN SOMME NATURE BERCE LE CHAUDEMENT IL A FROID LES PARFUMS NE FONT PAS FRISSONNER SA NARINE IL DORT DANS LE SOLEIL LA MAIN SUR SA POITRINE TRANQUILLE IL A DEUX TROUS ROUGES AU COTE DROIT

On reconnaît la poésie célèbre d'Arthur Rimbaud, le Dormeur du Val.