La méthode de Kasiski et les principes de la cryptographie moderne
Cryptographie · Lecture ~8–10 min
Du chiffrement monoalphabétique aux chiffrements polyalphabétiques
Comme nous l’avons vu précédemment, une attaque statistique contre un chiffrement par substitution monoalphabétique est possible car la correspondance entre les lettres du texte clair et celles du texte chiffré est fixe.
Chaque lettre du texte clair est toujours remplacée par la même lettre chiffrée, ce qui préserve les fréquences caractéristiques de la langue. Cela rend l’analyse fréquentielle particulièrement efficace.
Une façon naturelle de contrer cette faiblesse est de faire en sorte que différentes occurrences d’un même caractère du texte clair soient chiffrées différemment. Cette idée conduit aux chiffrements polyalphabétiques, dont le plus célèbre est le chiffrement de Vigenère.
Le chiffrement de Vigenère
Le chiffrement de Vigenère consiste à appliquer plusieurs chiffrements par décalage (chiffrements de César) en séquence. Une courte chaîne secrète est choisie comme clé.
Chaque caractère du texte clair est combiné avec le caractère correspondant de la clé, et la clé est répétée autant de fois que nécessaire.
Exemple
Chiffrons le message tellhimaboutme avec la clé cafe.
- Texte clair :
tellhimaboutme - Clé :
cafe - Clé répétée :
cafecafecafeca - Texte chiffré :
WFRQKJSFEPAYPF
Chaque lettre est décalée selon la valeur de la lettre correspondante de la clé, généralement en travaillant modulo 26.
Comment casser le chiffrement de Vigenère
Supposons que la longueur de la clé soit t, appelée la période.
Le texte chiffré peut alors être divisé en t sous-séquences, chacune correspondant à un chiffrement par décalage unique.
Chaque sous-séquence peut être attaquée indépendamment à l’aide de méthodes statistiques :
- Calculer la distribution de fréquence des lettres.
- Tester les 26 décalages possibles.
- Choisir celui dont la distribution correspond le mieux à celle de l’anglais.
Il existe également des variantes améliorées de cette attaque qui ne nécessitent pas de deviner explicitement le texte clair, mais comparent directement les distributions statistiques.
La méthode de Kasiski
Une attaque plus puissante contre Vigenère est la méthode de Kasiski.
Idée principale
La première étape consiste à identifier des motifs répétés de longueur 2 ou 3 (bigrams ou trigrams) dans le texte chiffré.
Ces répétitions sont souvent dues à des séquences fréquentes du langage naturel qui ont été chiffrées avec la même portion de la clé.
L’observation fondamentale de Kasiski est que la distance entre deux occurrences d’un même motif répété est généralement un multiple de la longueur de la clé.
En calculant ces distances et en prenant leur plus grand commun diviseur, on peut souvent déterminer la période du chiffrement.
Exemple illustratif
Texte clair : the man and the woman retrieved the letter from the office
Clé répétée : beadsbeadsbeadsbeads...
VMF QTP FOH MJJ XSFCS SIMTNFZXF YIS EIYUIK HWPQ MJJ QSLV TGJKGF
Principes fondamentaux de la cryptographie moderne
- Définition rigoureuse : toute analyse cryptographique commence par une définition précise de la sécurité.
- Hypothèses explicites : toute hypothèse non prouvée doit être clairement formulée et aussi minimale que possible.
- Preuve formelle : une construction cryptographique doit être accompagnée d’une preuve de sécurité rigoureuse.
Qu’est-ce qu’un chiffrement sûr ?
- Impossible de retrouver la clé secrète.
- Impossible de retrouver le texte clair.
- Impossible de déterminer même une partie du texte clair.
- Impossible d’extraire toute information significative.
Un schéma de chiffrement est sûr si aucun adversaire ne peut calculer une quelconque fonction du texte clair à partir du texte chiffré.