Quagmire 5, Vigenère à l’exponentielle

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.

avatar

Philippe Huysmans

Webmaster du Vilain Petit Canard, citoyen de nationalité belge, né à Schaerbeek le 16.10.1966. Marié et père de deux enfants. Je vis en Belgique et j’exerce la profession d’Informaticien à Bruxelles. Mes articles

Vous aimerez aussi...