Le Carré de Vigenère a été l’un des chiffrements les plus efficace durant des siècles. Ce n’est qu’en 1856 que Charles Babbage, inventeur anglais, a réussi à briser le cryptage de John Hall Brock Thwaites, pensant qu’il venait d’inventer une toute nouvelle méthode de chiffrement, alors qu’il avait juste réinventer ce que Blaise de Vigenère avait mis en place dès 1586.
L’analyse fréquentielle étant inadapté, il va nous falloir réviser notre copie et trouver une méthode. Pour Charles Babbage, tout n’était pas à jeter. Il manquait juste une première étape pour décrypter le message.
Voici donc un exemple expliqué de la cryptanalyse du Carré de Vigenère.
Le message chiffré
XAUNMEESYIEDTLLFGSNBWQ UFXPQTYORUTYIINUMQIEUL SMFAFXGUTYBXXAGBHMIFII MUMQIDEKRIFRIRZQUHIENO OOIGRMLYETYOVQRYSIXEOK IYPYOIGRFBWPIYRBQURJIY EMJIGRYKXYACPPQSPBVESI RZQRUFREDYJIGRYKXBLOPJ ARNPUGEFBWMILXMZSMZYXP NBPUMYZMEEFBUGENLRDEPB JXONQEZTMBWOEFIIPAHPPQ BFLGDEMFWFAHQ
Note : Pour plus de difficulté, les espaces et caractères spéciaux ont été supprimés.
Les étapes du décryptage
- Détermination de la longueur de la clé : Analyse de la répétition de groupe de lettre et de leurs espacements
- Analyse fréquentielle par lettre de la clé : Méthode semblable à la cryptanalyse monoalphabétique (mais en plus simple)
- Définition de la clé
1. Détermination de la longueur de la clé
Le tableau ci-dessus référence les répétitions de trois séquences de lettres avec les espaces de répétitions. Par exemple, la séquence U-M-Q-I se répète après 30 lettres et les nombres 1, 2, 3, 5, 6, 10, 15 et 30 sont appelés ses facteurs parce qu’ils divisent 30 exactement, sans laisser de reste. Ces facteurs suggèrent 8 possibilités :
1. la clef est constituée de 1 lettre et se répète 30 fois entre 2 occurrences 2. la clef est constituée de 2 lettres et se répète 15 fois entre 2 occurrences 3. la clef est constituée de 3 lettres et se répète 10 fois entre 2 occurrences 4. la clef est constituée de 5 lettres et se répète 6 fois entre 2 occurrences 5. la clef est constituée de 6 lettres et se répète 5 fois entre 2 occurrences 6. la clef est constituée de 10 lettres et se répète 3 fois entre 2 occurrences 7. la clef est constituée de 15 lettres et se répète 2 fois entre 2 occurrences 8. la clef est constituée de 30 lettres et se répète 1 fois entre 2 occurrences
La dernière est à exclure, puisque O-I-G-R se répète après 25 caractères seulement. De même, la première possibilité doit être exclue parce qu’une clef d’une seule lettre est celle d’un alphabet monoalphabetique. Pour indiquer les autres possibilités, des x sont placés sur le tableau dans les colonnes appropriées. Et il apparaît clairement que toutes les périodes sont divisibles par 5.
Maintenant que nous avons établit que le mot clef est en 5 lettres L1-L2-L3-L4-L5, il ne nous reste plus qu’à appliquer l’analyse des fréquences sur les sous-textes des lettres L1 , L2, L3, L4 et L5. La première lettre du message chiffré avec L1, la deuxième avec L2, la troisième avec L3, la quatrième avec L4, la cinquième avec L5 puis la sixième avec L1 et ainsi de suite.
X, E, E, F, W, P, R, I, I etc. sont chiffrés avec L1 A, E, D, G, Q, Q, U, N, E etc. sont chiffrés avec L2 U, S, T, S, U, T, T, U, U etc. sont chiffrés avec L3 N, Y, L, N, F, Y, Y, M, L etc. sont chiffrés avec L4 M, I, L, B, X, O, I, Q etc. sont chiffrés avec L5
Lorsque l’on compare les fréquences des lettres avec une répartition usuelle, on remarque rapidement que nous avons une succession de pics et de vallées avec une forte correspondance entre les colonnes E et I des alphabets chiffrés et usuels. On peut donc supposer que l’alphabet de chiffrement corresponds avec la ligne E du Carré de Vigenère. Et donc que la première lettre L1 du mot est E. De la même manière, nous obtenons M pour la lettre L2. Au final, c’est le mot EMAUX qui est la clef de chiffrement.
Maintenant que nous avons le mot clef, nous obtenons un début de texte clair : « toutpasselartrobusteseula…« . Après quelques aménagement d’espace et caractères spéciaux, nous obtenons un texte clair :
Tout passe – L’art robuste
Seul a l’éternité
Le buste
Survit à la cité.Et la médaille austère
Que trouve un laboureur
Sous terre
Révèle un empereur.Les dieux eux-mêmes meurent,
Mais les vers souverains
Demeurent
Plus forts que les airains.Sculpte, lime, cisèle ;
L’Art de Théophile Gautier – Poème extrait du recueil Émaux et Camées
Que ton rêve flottant
Se scelle
Dans le bloc résistant !
Conclusion
A présent que le Carré de Vigenère n’est plus inviolable mais la méthode de décryptage est couteuse en temps. Aujourd’hui, les algorithmes permettent une meilleure analyse pour des raisons de temps de traitement et de possibilités. Il est plus facile pour un logiciel de compter centaines, voir milliers de lettre d’un document pour en établir la fréquence.
Autant les cryptanalystes comme Charles Babbage n’avaient que leur cerveau et leur crayon pour briser un chiffre, autant les ordinateurs proposent des solutions que l’humain devra évaluer pour déterminer la clé.
