Quagmire 5, Vigenère à l’exponentielle
Temps de lecture : 5 minute(s)
Dans cet article, je me propose de faire partager à la communauté des cryptographes une découverte personnelle, qui n’est, en somme, qu’une extension logique de ce qu’est l’algorithme connu sous le nom de Quagmire IV. Logiquement, je l’ai donc appelé Quagmire V.
Cette découverte est, tout comme l’algorithme TCL, le fruit de mes recherches d’une solution pour l’énigme Kryptos (K4), qui reste, 30 ans après sa création, un mystère complet, personne n’ayant même réussi à savoir de quoi il est fait.
Je ne vais pas détailler ici ce que sont les algorithmes Quagmire I à Quagmire IV, qui tous découlent des travaux de Blaise de Vigenère, vous en trouverez l’explication accompagnée à chaque fois d’un exemple sur l’excellent site web de l’American Cryptogram Association.
Caractéristiques spécifiques de Quagmire V
Ce qui caractérise Quagmire V est la possibilité d’ajouter autant de clés (CT) que l’on souhaite. Eh oui, qui a décrété qu’on serait obligé de n’en utiliser qu’une seule ? Cela semble une différence mineure, mais nous verrons que cela porte la complexité à des niveaux stratosphériques.
Explication par comparaison avec Quagmire IV
Prenons le texte suivant, qui est un extrait des Misérables de Victor Hugo
LE SOIR APRES LE DINER ELLE FAISAIT ASSEZ HABITUELLEMENT DE LA TAPISSERIE DANS LE SALON OU QUELQUE OUVRAGE DE COUVENT ET JEAN VALJEAN LISAIT A COTE D ELLE UNE FOIS ELLE LEVA LES YEUX DE SON OUVRAGE ET ELLE FUT TOUTE SURPRISE DE LA FACON INQUIETE DONT SON PERE LA REGARDAIT
- Clé plein texte (PT) : HUGO
- Clé chiffre (CT) : VICTOR
- Indicateur : MISERABLES
- Position de l’indicateur : C
Nous pouvons à présent construire la tabula recta en la limitant aux seules lignes présentes dans la clé, ce que j’appelle keybula.
HUGOABCDEFIJKLMNPQRSTVWXYZ FGHJKLMNPQSUWXYZVICTORABDE UWXYZVICTORABDEFGHJKLMNPQS KLMNPQSUWXYZVICTORABDEFGHJ TORABDEFGHJKLMNPQSUWXYZVIC ZVICTORABDEFGHJKLMNPQSUWXY VICTORABDEFGHJKLMNPQSUWXYZ ICTORABDEFGHJKLMNPQSUWXYZV EFGHJKLMNPQSUWXYZVICTORABD TORABDEFGHJKLMNPQSUWXYZVIC KLMNPQSUWXYZVICTORABDEFGHJ
Ainsi, pour encrypter la première lettre qui est un L, nous cherchons la première ligne du tableau (alphabet PT), puis nous descendons d’une ligne (premier caractère de la clé, pour trouver X. Pour la deuxième lettre (E), nous faisons pareil mais descendons à la deuxième ligne du tableau, ce qui nous donnera un T, et ainsi de suite. J’ai colorisé les premières lettres du cryptogramme en violet dans le tableau ci-dessus. Quand on atteint le bas du tableau (et donc la longueur de l’indicateur), on reprend à la première ligne de l’indicateur, située immédiatement en dessous de l’alphabet de référence (PT).
Nous obtenons alors le cryptogramme suivant :
XTBAE PRZUW TDWFE LEIGI XTXBE QRQXP TKWCZ OAQXL PDIGJ DMTFW XZDBL FSCGA STUBK QKNWP XYTAV NCNMR GTNOS PRGGU PINOS DMTGD UTPPS OKSGP ZDYWT FUJEN OTUGH JEFPW QYYWB JKNMW RZIGP YEFVU PKNPC IWIBM PTDGH JEPOD OYLXB QCIQA SKWFB JRPBS JFYPM IGNXW NYTXP TMZGA PDPUB CRIFP SL
Même exemple, mais en utilisant plusieurs clés pour le chiffre (alphabets CT) – Quagmire V
Pour faire simple, prenons trois couleurs, disons ROUGE, VERT, BLEU, et transformons ces mots en alphabets (on écrit les mots, puis on ajoute dans l’ordre alphabétique toutes les lettres qui manquent pour faire un alphabet complet).
ROUGEABCDFHIJKLMNPQSTVWXYZ VERTABCDFGHIJKLMNOPQSUWXYZ BLEUACDFGHIJKMNOPQRSTVWXYZ
Ceux-ci seront utilisés de manière cyclique pour construire la tabula recta qui deviendra :
VICTORABDEFGHJKLMNPQSUWXYZ KLMNPQSTVWXYZROUGEABCDFHIJ | ROUGE GHIJKLMNOPQSUWXYZVERTABCDF | VERT QRSTVWXYZBLEUACDFGHIJKMNOP | BLEU UGEABCDFHIJKLMNPQSTVWXYZRO | ROUGE VERTABCDFGHIJKLMNOPQSUWXYZ | VERT EUACDFGHIJKMNOPQRSTVWXYZBL | BLEU EABCDFHIJKLMNPQSTVWXYZROUG | ROUGE JKLMNOPQSUWXYZVERTABCDFGHI | VERT BLEUACDFGHIJKMNOPQRSTVWXYZ | BLEU PQSTVWXYZROUGEABCDFHIJKLMN | ROUGE
Et le cryptogramme devient :
UPJBE FHACR CYBHE SKOHB UPLDE WHKUX CTBOJ GIKUJ WYDIN JVMGR UMTDP UYCHW LPZDO WSUTX UKGBU VZUOH DPVXV FHXHZ WIVXV JVMHT RPXSV GSZHX EYRWC UCPEV NPZIM QKDQR XKRWG QSUOR KMDIS BKDXZ WTVSA XEODU WPTIM QKWVT NKKAG WZORW LTBHG QHWDS PVRSQ XAUUR VKGAS DVAHW WYXCG MHOGX LJ
Génération des alphabets (CT)
On pourrait penser naïvement qu’il serait assez compliqué de générer suffisemment d’alphabets, attendu qu’ils font partie de la clé que les deux partie doivent posséder pour échanger des messages chiffrés, mais il n’en est rien.
Prenons par exemple le mot HERITAGE, nous en faisons un alphabet, puis procédons à sa décimation (par 7) :
HERITAGBCDFJKLMNOPQSUVWXYZ HBMVRDOXTJQZGLUECNWIFPYAKS HXUPMJCARZWSOLFBTEYVQNKDGI HAFNUZTDMSYICLQXRBKPWEGJOV HDQEFSRJUIKVTLWAMXGNYBOZCP HJWBQIMZFVGPRLYDUAOEKXCSTN HZYXWVUSQPONMLKJFDCBGATIRE HSKAYPFIWNCEULGZQJTXODRVMB HIGDKNQVYETBFLOSWZRACJMPUX HVOJGEWPKBRXQLCIYSMDTZUNFA HPCZOBYNGXMAWLTVKIUJRSFEQD HNTSCXKEOAUDYLRPGVFZMIQBWJ
Pour décimer, prenez la première lettre de la chaîne, puis la 7ème, puis la 14ème, et ainsi de suite en reprenant du début quand vous atteignez la fin de l’alphabet. Pour les lignes suivantes, appliquez le même principe en prenant pour alphabet de référence la ligne précédente.
Du coup, la keybula deviendrait (dans notre exemple) :
VICTORABDEFGHJKLMNPQSUWXYZ KLMNOPQSUVWXYZHERITAGBCDFJ NWIFPYAKSHBMVRDOXTJQZGLUEC ZWSOLFBTEYVQNKDGIHXUPMJCAR PWEGJOVHAFNUZTDMSYICLQXRBK FSRJUIKVTLWAMXGNYBOZCPHDQE DUAOEKXCSTNHJWBQIMZFVGPRLY DCBGATIREHZYXWVUSQPONMLKJF EULGZQJTXODRVMBHSKAYPFIWNC VYETBFLOSWZRACJMPUXHIGDKNQ IYSMDTZUNFAHVOJGEWPKBRXQLC
Et le cryptogramme deviendrait :
EHPJS KIAFF GOYAS MHQWG EHVVS VIUTZ GZYKM XRUTR VOGFY TQGSF
EAOVO UNPWT LHEVB VUOIZ EPHJP FMOMK BHLQF KIRWN VILQF TQGWM
ZHBYF XUMWZ IOWLK UGJED NHEFN QHFUF WPWLL QUOMF KAGFC LHFKN
VZLYU GDQLH VHOFN QHDGM NPMGL VMQXT LZYAL QIDLS OTWYZ GCOTF
UPHGC EQAWT VOBOL HIQSZ LF
Lien possible avec Kryptos (K4)
Est-ce qu’un tel algorithme aurait pu être utilisé pour encrypter la quatrième partie du cryptogramme de la stèle Kryptos, située au siège de la CIA à Langley ? Oui, sans aucun doute, et ceci expliquerait pourquoi aucune attaque basée sur Quagmire III et Quagmire IV n’a jamais donné aucun résultat.
Si c’est le cas, il reste à déterminer quelles sont les clés qui ont été utilisées pour créer les alphabets CT, parce qu’une attaque par la force brute est pratiquement impossible, vu la taille de l’espace de recherche. Il existe 26! (403.291.461.126.605.635.584.000.000) façons différentes de créer un seul alphabet, que dire de, disons, 7 alphabets qu’il faudrait alors multiplier par le nombre de mots à tester (plus de 120.000), le tout à multiplier par 26 de manière à prendre en compte toutes les positions de l’indicateur dans l’alphabet de référence ?
Mot de la fin
J’ai souhaité publier cette découverte tout simplement parce qu’elle dépasse largement le cadre de la recherche d’une solution pour Kryptos K4, et qu’elle ajoute une petite pièce au grand puzzle de la cryptographie classique, et plus particulièrement, un petit frère à la descendance déjà nombreuse du chiffre de Vigenère.
Il va sans dire que la science appartient à tous, et que si je revendique la paternité de l’invention, celle-ci ressort clairement du domaine public en termes de propriété intellectuelle.
