1. Page d'accueil
  2. Les mathématiques et théories abordées
  3. Par discipline
  4. Cryptologie

Test de Kasiski


Après l’épisode 1#05 et son hypothèse de Riemann pour décrypter des algorithmes asymétriques, voici l’épisode 1#06 et la cryptanalyse d’un algorithme symétrique… Décidemment, vous allez devenir des pros du décryptage de code !

Le test de Kasiski permet de casser le code de Vigenère. La méthode de cryptage de Vigenère est très simpliste comparée à ce que l’on utilise aujourd’hui. (cf : explication de son fonctionnement et démo)
(Allez-y, apprenez comment cela fonctionne… ici, on va le casser, ce code !)

En cryptanalyse, on utilise souvent les attaques statistiques pour essayer de trouver le codage. Pour cela, il faut avoir une idée de la langue du message crypté. Ensuite, on utilise une analyse d’un corpus de la langue ciblée pour connaître la fréquence d’apparition des lettres. Pour le français, vous pouvez prendre celui-ci (ou construire le votre…).

Le code de Vigenère a été pensé pour résister à cette attaque brute. En effet, un « e » est codé par plusieurs lettres différentes selon sa position dans le texte et la longueur de la clé. Cependant, plus la longueur de la clé est courte par rapport à la longueur du texte, plus le nombre de lettre codé par la même lettre de la clé est important. Si on trouve la taille de la clé, il suffit de réaliser une attaque statistique sur les groupes de lettres correspondant.

Prenons un exemple…

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

On va casser le code de ce texte. Il est en français. L’idée de Kasiski est de dire qu’en français on utilise souvent des mots de 2 lettres de manière répétée : le, la, un, et. On peut aussi considérer des groupes de 3 lettres fréquents : des, une. Mais considérons déjà les groupes de 2 lettres. Vu la manière de fonctionner de l’algorithme de Vigenère, il est possible que des « le » soient codés plusieurs fois par les mêmes lettres de la clé. On obtiendra alors les mêmes 2 lettres en sortie. Cherchons donc dans le texte des groupes de lettres qui se répètent…

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

Il y a 187 positions entre les deux OE. La clé est donc de longueur 17, 11 ou 187.

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

Entre les deux YY, il y a 122 positions, soit 11*11.

La clé est donc un mot de 11 caractères. Bien sûr, il faudrait continuer à chercher d’autres groupes pour en être convaincu : certains groupes peuvent ne pas être significatifs.

Coupons maintenant le texte en paquet de 11.

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

On sait maintenant que chaque colonne a été cryptée par la même lettre. Faisons une attaque statistique sur chaque colonne. La deuxième colonne est un bon exemple : il y a un très grand nombre de M. Or la lettre la plus utilisée en français est le E. De plus, si l’on considère une phrase normale, c’est bien la 2ème position qui a une très grande chance de contenir un E…

En prenant le carré de Vigenère, on voit que la deuxième lettre de la clé est un I.

De même avec la 3ème colonne : elle contient 3 R et 2 G. Si on suppose que les 3 R correspondent à 3 E dans le texte en clair, on obtient la lettre N comme clé.

La clé est donc : - I N - - - - - - - -

Prenons maintenant la dernière colonne : 4 C, 3 M et 3 J. On va donc prendre C = E et on obtient la lettre : Y comme clé.

La clé est donc : - I N - - - - - - - Y.

Vous pouvez continuer ainsi sur les autres colonnes également. Vous trouverez au final la clé : S I N G U L A R I T Y (quelle surprise…)

Et en décodant le texte :
« J e v i e n s t o u t j u s t e d e r e m a r q u e r l e c h a n g e m e n t q u i r e l e v e p l u s d e l a c o n s e c r a t i o n a m o n g o u t L a p a r t i e s i t e s r e l i e e a N u m b e r s s u r A l l o c i n e f r a c c u e i l l e e n e f f e t d e p u i s p e u N u m b e r s S i n g u l a r i t y e n p r e m i e r e p o s i t i o n d e l a t r e s c o u r t e l i s t e d e s i t e s d e f a n s »

Le test de Kasiski est un excellent exemple de cryptanalyse qui permet de bien appréhender la problématique que rencontrent les spécialistes du cryptage : le cryptage que je vend comme inviolable n’a-t-il pas des failles permettant de retrouver la clé ? Il existe de très nombreuses attaques qui ont été mises au point au fil du temps [1]. Bien sûr, les algorithmes de cryptages les plus récents comme AES ont été soumis aux attaques connues pour évaluer leur robustesse. Lorsqu’une attaque aura été inventée, il faudra trouver de nouveaux algorithmes qui tiendront compte de la nouvelle attaque.

Article par BubuLeMag. >> Réagir


[1] http://fr.wikipedia.org/wiki/Cryptanalyse [En français]


Rédigé initialement par BubuLeMag.
Dans Cryptologie et Par nom
Dernière modification de la page le 06/08/2008 à 22h42.