Cryptographie!

Vaincre les chiffrements par transposition

  Étonnamment, les chiffrements par transposition sont plutôt plus sûrs que les chiffrements par substitution; par exemple, alors qu'il est très facile avec un ordinateur de vaincre automatiquement le chiffre de Vigenère, c'est beaucoup plus difficile pour un chiffre par transposition. Bien souvent, il faut un élément supplémentaire, comme un mot probable, pour espérer pouvoir déchiffrer le message.

  Nous allons expliquer sur un exemple le décryptage d'un message chiffré posté par Nérosson sur le forum du site. Voici ce message :
HSELO CLTNT LANYR OVCRC LUTOU SDLOI QOCSE TLROO OOIET VOIRO ESSOT SOAMT ENOIE AEMTU CLURE PQEIE AETAE ETEET NOOPN EBNSC RIFOR TEERT UIIDN IMIIR DMETO EXIDO UDNYN ORFSN DLNUN RIOSA NEEEC EPIEI ETMIU ESEIN SIFNI SINPE VOAER GTRAE PIEEA IPVBS SRCII LNIUI FOROS ALTAB UNNRS NDENE NSOSE IEEEN RFBTN LSRST AT
Nérosson précisait que les décryptements des messages précédents sur ce canal ont aussi révélé une chose de toute première importance : les messages commencent toujours sous la forme : de (expéditeur) à (destinataire). Or, ici, nous savons que l'expéditeur est Freddy et que le destinataire est Yoshi. Le message clair commence donc par DE FREDDY A YOSHI.

  Une analyse des fréquences des lettres du texte, qui donne dans l'ordre des fréquences EIONSTRA, fait tout de suite penser à l'usage d'une transposition. Voyons comment procéder. On suppose que le lecteur est très familier avec les méthodes de chiffrement par transposition. Les outils en ligne évoqués sont disponibles sur cette page.
Etape 1 : Trouver la longueur de la clé
  On va commencer par trouver la longueur de la clé de chiffrement. La première lettre du texte chiffré est H. Elle correspond très certainement au H de YOSHI qui apparait en début de message. Le H étant en 13è position dans le message clair, ceci indique que la clé fait au moins 13 caractères. On s'aide ensuite des deux Y qui sont dans le début du message clair. Ce sont des lettres rares, et elles n'apparaissent que deux fois dans le texte chiffré : en 14è et 134è position. Celui qui est en 14è position nous intéresse particulièrement. Il apparait dans l'étape de chiffrement après avoir lu toute la colonne du H initial et éventuellement une ou plusieurs autres colonnes. S'il y avait plusieurs colonnes lues avant d'arriver au Y, les colonnes aurait une longueur maximale de 7, ce qui donne une clé d'au moins 252/7=36 caractères : trop long pour espérer décrypter le message!

  On part donc de l'hypothèse que la colonne comprenant la lettre H dans l'étape de chiffrement comporte 13 caractères. Il y a alors deux possibilités :
  • le tableau comprend des colonnes de hauteur 13 et des colonnes de hauteur 12. Ceci revient à une clé de longueur 20 (entier juste au-dessus de 252/13), et il doit alors y avoir, puisque le message fait au total 252 caractères, 12 colonnes de 13 caractères (les premières) et 8 colonnes de 12 caractères. Mais c'est impossible, car alors la colonne de H, qui est la 13è du tableau, ne comporterait que 12 caractères et non 13! Cette hypothèse est à exclure.
  • le tableau comprend des colonnes de hauteur 13 et des colonnes de hauteur 14. Ceci revient à une clé de longueur 19, et à fabriquer un tableau avec 5 colonnes de 14 caractères, et 14 colonnes de 13 caractères : on fera désormais cette hypothèse dans la suite!
Etape 2 : le relèvement du tableau
  On va désormais essayer de fabriquer le tableau de chiffrement, qui comprend donc 5 colonnes de 14 caractères, et 14 colonnes de 13 caractères. On va d'abord tenter de retrouver le contenu des colonnes, sans prendre garde à l'ordre dans lequel elles apparaissent. Pour cela, on fabrique ces colonnes à partir du message chiffré en prenant successivement des blocs de 13 ou 14 lettres. Le choix d'un bloc de 13 ou 14 lettres est guidé par plusieurs éléments :
  • les têtes de colonnes du tableau sont les premières lettres du message : on en connait déjà 14, DEFREDDYAYOSHI.
  • les colonnes qui peuvent avoir 14 caractères correspondent forcément à des têtes de colonne qui sont D,E,F,R,E (les 5 premières lettres du message).
  • les deux premières têtes de colonne ont été identifiées. Il s'agit du H et du Y en 14è position. Ces deux premières colonnes ont une hauteur égale à 13.
  • le deuxième Y est en position 134=14+120=14+3*14+6*13. Ainsi, il y aura entre le premier Y et le deuxième Y 3 colonnes à 14 éléments et 6 colonnes à 13 élements.
Il faut alors essayer, un peu à tâtons, différentes combinaisons possibles de l'endroit où on prélève 14 lettres ou 13 lettres dans le message chiffré pour arriver à fabriquer un tableau répondant aux contraintes évoquées ci-dessus. Par exemple, si on commence en mettant les 3 colonnes de 14 lettres juste après celle de Y, et les deux dernières tout à la fin, c'est-à-dire en ayant la suite de longueur de colonnes suivantes (13,13,14,14,14,13,13,13,13,13,13,13,13,13,13,13,13,14,14) - en rouge, les colonnes dont on est sûr de la longueur, on obtient :
HYDOTTENEDYIIFGBOSE
SRLOSUTERMNOENTSRNN
EOOIOCABTEOSTIRSODR
LVIEALENUTRAMSARSEF
OCQTMUESIOFNIIECANB
CROVTRTCIESEUNPILET
LCCOEEERDXNEEPIITNN
TLSINPEINIDESEELASL
NUEROQTFIDLCEVENBOS
TTTOIENOMONEIOAIUSR
LOLEEIORIUUPNAIUNES
AURSAEOTIDNISEPINIT
NSOSEAPERNREIRVFREA
  OOM            ET
  On n'est pas si loin d'avoir toutes les lettres de DEFREDDYAYOSHI, mais il manque encore un R et un D. On doit chercher dans le tableau comment les faire apparaitre en première ligne en permutant des longueurs de colonne. Pour cela, ces D et ces R ne peuvent se trouver que dans les premières lignes ou les dernières lignes du tableau. Le seul D qui convient est celui situé sur la 3ème ligne, à l'avant-dernière colonne. Ceci implique de faire apparaitre les deux colonnes de 14 qui sont après le Y avant ce D, et donc que le tableau se termine nécessairement par deux colonnes de 13. Avec la nouvelle répartion (13,13,14,14,14,13,13,13,13,13,13,13,13,13,13,14,14,13,13), on obtient :
HYDOTTENEDYIIFGBRDN
SRLOSUTERMNOENTSOER
EOOIOCABTEOSTIRSSNF
LVIEALENUTRAMSARAEB
OCQTMUESIOFNIIECLNT
CROVTRTCIESEUNPITSN
LCCOEEERDXNEEPIIAOL
TLSINPEINIDESEELBSS
NUEROQTFIDLCEVENUER
TTTOIENOMONEIOAINIS
LOLEEIORIUUPNAIUNET
AURSAEOTIDNISEPIREA
NSOSEAPERNREIRVFSET
  OOM          ON  
  Il manque encore un S et un A. Le S apparait naturellement sur la deuxième ligne, colonne 16. Pour le faire apparaitre sur la première ligne, il suffit de décaler une des deux dernières colonnes de 14 par exemple à la colonne du F (car le G en tête de colonne n'est pas très engageant). De plus, la colonne de R doit nécessairement avoir pour hauteur 14 pour ne pas faire disparaitre le dernier D, et on propose maintenant la répartition 13,13,14,14,14,13,13,13,13,13,13,13,13,14,13,13,14,13,13 :
HYDOTTENEDYIIFTSRDN
SRLOSUTERMNOENRSOER
EOOIOCABTEOSTIARSNF
LVIEALENUTRAMSECAEB
OCQTMUESIOFNIIPILNT
CROVTRTCIESEUNIITSN
LCCOEEERDXNEEPELAOL
TLSINPEINIDESEENBSS
NUEROQTFIDLCEVAIUER
TTTOIENOMONEIOIUNIS
LOLEEIORIUUPNAPINET
AURSAEOTIDNISEVFREA
NSOSEAPERNREIRBOSET
  OOM        G  N
  Il manque encore un A! Une façon raisonnable de l'obtenir, sans faire disparaitre de E par exemple, est de décaler les colonnes de 14 qui apparaissent en position 5 et 6 pour les mettre en position 7 et 8, c'est-à-dire de choisir la répartition suivante : 13,13,14,13,13,14,14,13,13,13,13,13,13,14,13,13,14,13,13. On obtient alors le tableau suivant, où toutes les lettres de DEFREDDYAYOSHI apparaissent dans la première ligne :
HYDOOEANEDYIIFTSRDN
SRLOTMEERMNOENRSOER
EOOISTTBTEOSTIARSNF
LVIEOUANUTRAMSECAEB
OCQTACESIOFNIIPILNT
CROVMLECIESEUNIITSN
LCCOTUTRDXNEEPELAOL
TLSIEREINIDESEENBSS
NUERNEEFIDLCEVAIUER
TTTOOPTOMONEIOIUNIS
LOLEIQNRIUUPNAPINET
AURSEEOTIDNISEVFREA
NSOSAIOERNREIRBOSET
   O   EP      G  N  
  Est-ce gagné pour autant? Pas vraiment, car les lettres qui restent dans la première ligne, après le début du message, sont T,N,N,O,I, et ces lettres doivent constituer le début d'un mot. Ce n'est pas impossible, mais ce n'est pas la seule solution. Par exemple, avec la répartion très proche 13,13,14,13,13,14,13,13,14,13,13,13,13,14,13,13,14,13,13, on obtient le tableau :
HYDOOEAPEDYIIFTSRDN
SRLOTMENEMNOENRSOER
EOOISTTEREOSTIARSNF
LVIEOUABTTRAMSECAEB
OCQTACENUOFNIIPILNT
CROVMLESIESEUNIITSN
LCCOTUTCIXNEEPELAOL
TLSIERERDIDESEENBSS
NUERNEEINDLCEVAIUER
TTTOOPTFIONEIOIUNIS
LOLEIQNOMUUPNAPINET
AURSEEORIDNISEVFREA
NSOSAIOTINREIRBOSET
   O  E  R    G  N
  Cette fois, les lettres qui restent sont O,P,T,I,N, dont l'anagramme est POINT. C'est aussi une possibilité. Comme on le voit, il y a à ce stade plusieurs possibilités à envisager. Nous n'étudierons dans la suite qu'une possibilité, la bonne, c'est-à-dire la dernière!
Etape 3 : Le jeu des anagrammes
  La dernière étape consiste à remettre les colonnes précédentes de sorte d'obtenir le message clair; il faut donc faire des anagrammes judicieux! On peut partir par exemple de la 14è et 17è colonne, qui correspondent au bigramme FR du message clair. On peut les faire suivre de la 6è ou de la 9è colonne, qui commencent toutes deux par un E. Si on essaie avec la 9ème colonne, on obtient le résultat suivant :
FRE
NOE
ISR
SAT
ILU
NTI
PAI
EBD
VUN
ONI
ANM
ERI
RSI
GNR
Les trigrammes EBD et GNR qui apparaissent sont très peu vraisemblables… C'est donc que que l'enchaînement est plutôt 14,17,9, et même 6,14,17,9, qui correspond donc à EFRE. On continue ensuite avec les D, et ainsi de suite (c'est très aisé avec l'outil en ligne mentionné plus haut), pour obtenir le message final suivant :
DE FREDDY A YOSHI POINT LE NOMME NEROSSON TERRORISTE NOTOIRE S EST FAIT SAUTER AVEC LA BOMBE QU IL CONFECTIONNAIT POINT LES SERVICES MUNICIPAUX ONT COLLECTE LES DEBRIS DE L INTERESSE EN VUE DE LEUR INCINERATION POINT TOUTEFOIS IL MANQUE UN OEIL POINT PRIERE DE FAIRE SAVOIR SI NEROSSON ETAIT BORGNE
La suite des aventures de Nérosson est sur le forum.
En conclusion…
  Le décryptage d'un message chiffré par transposition n'est pas impossible si on dispose d'informations supplémentaires, mais il reste très laborieux. Et encore, on disposait ici d'informations très fortes, puisqu'on connaissait le début du message. On comprend aussi mieux pourquoi les cruciverbistes furent appelés à la rescousse à Bletchey Park lors de la Seconde Guerre Mondiale. Leurs talents pouvaient être bien utiles dans l'arme du renseignement!
Consulter aussi