Décryptement d'une transposition à tableau, par Pierre Baud

• Accueil
• Cryptographie
• Stéganographie
• Cryptanalyse
• Lexique

Selon le mot du Commandant Bazeries, une transposition est une salade de lettres du texte clair. Il est donc évident que ce principe se distingue au premier coup d'oeil d'un chiffrement par substitution (où les éléments du clair sont remplacés par d'autres) du fait que la fréquence des lettres demeure la même que celle du texte clair.

Dans cette étude, nous nous limiterons à la transposition rectangulaire, dite « transposition à tableau ».

Une transposition à tableau s'effectue à partir d'une clé numérique, composée des nombres de 1 à n, rangés dans un ordre incohérent. Précisons que, dans la pratique, n dépasse rarement 25. Un moyen simple, rapide et très usité d'obtenir une clé de transposition est de partir d'une clé littérale, (mot ou expression) de la longueur souhaitée. On numérote ensuite les lettres dans l'ordre alphabétique. Si une même lettre apparaît plusieurs fois, elle est numérotée successivement de la gauche vers la droite. Une exemple concret rendra les choses plus claires :

Texte clair :

« Après avoir quitté les bords de la Mer rouge pour ceux de la Méditerranée, les Phéniciens s'adonnèrent aussitôt à la grande navigation ».

On inscrit alors le texte sous la clé par lignes successives. Ensuite, on obtient le cryptogramme en relevant le tableau obtenu par colonnes prises dans l'ordre des numéros fournis par la clé :

Cryptogramme

Déchiffrement

Différentes applications de la transposition à tableau

Bien entendu, si le code était « compromis », et donc connu du décrypteur, celui-ci se retrouvait devant un problème assez peu différent de celui d'une transposition de texte clair.

Par contre, dans le cas d'un code désordonné, totalement inconnu du décrypteur, la tâche de celui-ci devenait alors d'une incroyable difficulté. Elle nécessitait une équipe nombreuse, exceptionnellement compétente, travaillant avec diligence et acharnement sur un trafic abondant, où l'on finit toujours par trouver par ci par là un « accident de chiffrement » : coïncidence malheureuse (ou heureuse : cela dépend du point de vue où l' on se place), correction d'un message indéchiffrable, maladresse d'un chiffreur peu compétent. On peut aussi être puissamment aidé par des renseignements sur le trafic ennemi : objet du texte d'un message, renseignements sur les habitudes de style d'un rédacteur, espionnage, etc, la plus fructueuse des aubaines étant le vol de textes clairs. Parfois le résultat obtenu payait au centuple les immenses efforts accomplis.

Le surchiffrement par transposition à tableau peut bien entendu s'appliquer avec profit à d'autres procédés. Par exemple, le Playfair : si un surchiffrement par transposition à tableau est appliqué à un chiffrement en Playfair, les bigrammes qui composent ce premier chiffrement se trouvent dissociés..

Mais un surchiffrement par transposition à tableau peut aussi s'appliquer...à lui-même : c'est ce qu'on appelle la double transposition qui s'opère ainsi : lorsqu'un texte clair a été chiffré par une transposition à tableau, le cryptogramme ainsi obtenu (qu'on appelle alors antigramme parce qu'il ne constitue qu'une phase intermédiaire) fait l'objet d'une seconde transposition (de préférence avec une autre clé) qui donnera le cryptogramme définitif. Dans la pratique, on « court-circuite » le relèvement de l'antigramme, c'est à dire que le relèvement des colonnes du premier tableau est reporté directement en lignes horizontales dans le deuxième tableau.

Exemple

Texte clair

Premier tableau                                               Deuxième tableau

Cryptogramme

ELIPP NATSP ESNEL EEGET EQSKE INUTI STNTO VNTST TRUXN LILGL SSTUR INMIL EEESE SUNUR AUIQE APDEE RPSVM CIEII SKEHI ENTNE XDITA SNLCE SEIVS EPCEE TEUIA ELNQA CLNIB RSOUI NRESS EEAEE URSSD TUSTA NROLU ANNNI ATT

Décryptement d'une transposition à tableau

A moins que l'on dispose de renseignements subsidiaires, le décryptement d'une transposition à tableau est souvent un travail long, comportant de nombreux tâtonnements. Le principe de base consiste à rechercher une juxtaposition verticale de deux portions du cryptogramme permettant d'obtenir des bigrammes particulièrement vraisemblables. C'est plus facile à dire qu'à faire :

1)Dans l'ignorance de la longueur de la clé et, par conséquent de la hauteur du tableau, on ne peut savoir sur quelle longueur doit porter la juxtaposition
2)Le cryptogramme comportant une majorité de lettres fréquentes, une suite de bigrammes vraisemblables peut parfaitement être le fruit du hasard,
3)la succession entre une fin de mot et le début du suivant peut donner des bigrammes totalement aberrants (voyeZ Xavier, harenG Mariné, un boN Xérès, ), qui détourneront le chercheur d'une hypothèse pourtant juste.

Ne soyons cependant pas totalement défaitiste. Des cas favorables peuvent aussi exister : une hypothèse valable sur l'objet du message peut fournir un ou des mots probables, des informations, souvent déduites du décryptement de messages précédents, fourniront des indications sur la manière dont l'expéditeur libelle son message, l'incompétence ou l'inattention du chiffreur permettront parfois une « entrée ».

La manière la plus commode de réaliser des juxtapositions paraît être de faire deux bandes de papier sur chacune desquelles on inscrira verticalement le texte complet du cryptogramme. En les faisant coulisser l'une par rapport à l'autre, on pourra réaliser toutes les juxtapositions possibles.

Passons dans le domaine concret avec le cryptogramme suivant :

RETAC SMALC EESIN SCSNT EEQDI EODOT HAMSE IHUHE SNPTS ESAIN FMSES CUEES ONRES TSFEE NSTRE OPRDA IDECE ETECL EFOEA PHGIL ELHTA OTRRN SOE

On observe que dans tout le cryptogramme, la lettre « Q » apparaît une seule fois. Il est permis d'espérer que le chiffreur a omis de supprimer la lettre « U » qui la suit toujours (sauf en fin de mot : cinq, coq). Le cryptogramme ne comporte que deux « U ». Nous allons donc tenter deux juxtapositions et, dans l'ignorance de leur hauteur, nous prendrons cinq bigrammes au-dessus et au-dessous du bigramme QU.

S	M			S	M		Pas de chance ! On observe que les deux juxtapositions présentent de grandes similitudes. On optera donc, sans certitude, pour la juxtaposition telle qu'elle est délimitée ci-contre parce que : a) elle contient deux fois le bigramme « ES » b) « DE » est préférable à « DH » c) au-dessus et au-dessous, « SM » et « OO » sont des bigrammes peu vraisemblables. A mon avis, il vaut mieux faire un « pavé » trop court que trop long. Nous allons tenter de partir de ce pavé et tenter de l'élargir. Dans la bande de papier contenant verticalement le cryptogramme, nous allons rayer les deux séquences déjà utilisées. Ensuite, nous chercherons une séquence juxtaposable donnant des trigrammes satisfaisants, en donnant la préférence au côté droit du pavé,et en recherchant un des trigrammes « QUI » ou QUE » qui, sans être certains, possèdent une probabilité élevée. Encore une fois, il faut travailler sur des probabilités, pas sur des certitudes. Parmi les trois ou quatre possibilités intéressantes, je retiens la suivante à cause des trigrammes « ECH » et « DES »  :
N	S			N	S
T	E			T	E
E	I			E	S
E	H			E	C
Q	U			Q	U
D	H			D	E
I	E			I	E
E	S			E	S
O	N			O	O
D	P			D	N

 

N	S	I		Après avoir rayé cette nouvelle séquence dans la bande de relèvement vertical, nous cherchons une séquence susceptible de fournir des quadrigrammes acceptables. Nous en trouvons quatre : N S I R N S I G N S I L N S I F T E H E T E H I T E H E T E H O E S U T   E S U L   E S U F   E S U E E C H A   E C H E   E C H O   E C H A Q U E C   Q U E L   Q U E E   Q U E P D E S S   D E S H   D E S A   D E S H I E N M   I E N T   I E N P   D E S H E S P A   E S P A   E S P H   E S P I
T	E	H
E	S	U
E	C	H
Q	U	E
D	E	S
I	E	N
E	S	P

 

N	S	I	G	N	E		J'opte pour le deuxième pavé, en raison de : a) « ient » (fin de verbe) b) « nsig » (hypothèses : « signe » ou « signa »), c) « esul (hypothèse : « résulte » ou résulta »).
T	E	H	I	S	T
E	S	U	L	T	A
E	C	H	E	R	C
Q	U	E	L	E	S
D	E	S	H	O	M
I	E	N	T	P	A
E	S	P	A	R	L

Ces hypothèses permettent d'ajouter deux séquences au pavé.

Remarquons au passage que :

a) au fur et à mesure que des séquences sont rayées dans les bandes verticales, le nombre des hypothèses va se réduire,
b) le découpage en colonnes du cryptogramme va se préciser,
c) au fur et a mesure que le pavé s'élargit, les hypothèses se font de plus en plus assurées.

Le pavé suivant sera fourni par les hypothèses « histoire », « résultat »ou « résultant » ou « résultait », « cherch », « des hommes ».

					R	O	D	O		Le pavé est maintenant suffisamment large et le relevé vertical suffisamment fragmenté pour qu'il soit superflu de détailler la progression. Le pavé est donc complété comme suit :
N	S	I	G	N	E	D	A	N
T	E	H	I	S	T	O	I	R
E	S	U	L	T	A	T	D	E
E	C	H	E	R	C	H	E	S
Q	U	E	L	E	S	A	C	T
D	E	S	H	O	M	M	E	S
I	E	N	T	P	A	S	E	F
E	S	P	A	R	L	E	T	E

Il ne reste plus maintenant qu'à reporter en tête les colonnes les plus longues pour retrouver le tableau de transposition d'origine.

Texte clair

« Hérodote consigne dans cette histoire le résultat de ses recherches afin que les actions des hommes ne soient pas effacées par le temps ».

Clef numérique

Par comparaison entre le cryptogramme et le tableau, on rétablit sans difficulté la clé numérique :

12-9-1-4-10-8-6-11-2-13-3-7-5

Recherche de la clé littérale

Il peut être intéressant de connaître, non seulement la clé numérique, mais aussi la clé littérale. Cela peut permettre de savoir dans quelle catégorie de mots ou d'expressions l'expéditeur puise ses clés.

Pour cela, on inscrit sous chaque nombre de la clé numérique une série de quelques lettres dans l'ordre alphabétique, en commençant par le début de l'alphabet pour le chiffre 1, puis en décalant progressivement pour les nombres suivants, pour arriver aux dernières lettres de l'alphabet pour le nombre le plus élevé.

Il ne faut pas perdre de vue que, en raison du fait que la même lettre peut être présente plusieurs fois dans la clé, il n'y a pas forcément décalage alphabétique lorsqu'on se déplace de la gauche vers la droite. Par contre, lorsqu'on se déplace de la droite vers la gauche, on a nécessairement une nouvelle lettre plus éloignée de l'origine de l'alphabet.

Par ailleurs, il me semble préférable de n'inclure dans ces séquences que les lettres fréquentes, sinon on risque de se perdre dans des colonnes de lettres trop longues.

Exemple :

Les transpositions améliorées

La transposition de texte clair est surtout le domaine des chiffreurs amateurs, de petites structures ne disposant pas de codes, ou de clandestins ne devant pas prendre le risque qu'implique toujours la détention de documents suspects. Si l'on ne dispose d'aucun renseignement sur l'expéditeur, ses habitudes de rédaction du texte clair, si chaque clé n'est utilisée qu'une fois, si le chiffreur est compétent, la durée du décryptement peut se révéler décourageante pour un décrypteur réduit à ses propres moyens. D'autant plus que la difficulté peut être accrue par une certain nombre d'artifices, dont nous ne citerons que les deux principaux :

1)relèvement de plusieurs diagonales préalablement au relèvement en colonnes, le prix à payer étant le risque d'erreur au cours du relèvement.
2)Présence de cases noires dans le tableau, réparties selon une disposition convenue. Si cette convention est bien choisie, la dispersion des cases noires peut avoir l'apparence de l'incohérence.

La transposition à clé indéfinie

La transposition à clé indéfinie, présentée pour la première fois par le Commandant Baudouin en 1939, est une extrapolation de la transposition à tableau. Elle en diffère par le fait que la clé est d'une longueur égale à celle du texte clair. Il en résulte que, sous chaque nombre de la clé numérique, on trouve, non pas une colonne de lettres, mais seulement une seule et unique lettre du texte clair. On obtient le cryptogramme en relevant ces lettres dans l'ordre croissant des nombres-clés.

La clé numérique est réalisée de la manière classique : à partir d'une clé littérale, on numérote les lettres selon l'ordre alphabétique, les lettres répétées étant numérotées de la gauche vers la droite.

Exemple de chiffrement

Pour la réalisation du cryptogramme, la solution la plus simple est la suivante :on écrit d'abord, dans l'ordre croissant et par groupes de cinq les nombres de 1 à n, n étant le nombre le plus élevé de la clé numérique. Ensuite, on prend, dans le tableau ci-dessus, les lettres du texte clair dans l'ordre où elles se présentent et on les reporte sous le nombre qui leur correspond.

Cryptogramme

Déchiffrement

Au déchiffrement, on numérotera de 1 à n les lettres du cryptogramme. Ensuite, on établira la clé numérique d'après la clé littérale. Enfin, sous chaque nombre de la clé numérique, on inscrira la lettre portant même numéro dans le cryptogramme.

Exemple de déchiffrement

Cryptogramme (avec lettres numérotées)

Déchiffrement (A chaque nombre on attribue la lettre ayant le même numéro dans le cryptogramme)

Valeur du procédé

En matière de conception de procédés de chiffrement, le problème est toujours de concilier la simplicité d'emploi avec la sûreté cryptologique.

En ce qui concerne ce dernier point, il ne paraît pas douteux que ce procédé est sensiblement supérieur à la transposition à tableau du fait qu'il ne comporte pas de colonnes juxtaposables.

Par contre, en ce qui concerne son utilisation, on ne peut nier qu'il présente deux points faibles importants :
1 – il est long à mettre en oeuvre,
2 – les risques d'erreurs sont importants, particulièrement en ce qui concerne la réalisation de la clé numérique.

Dans ces conditions, on est amené à se demander si l'informatique ne pourrait pas venir au secours de la méthode « papier-crayon ».

Exercices

Nous allons maintenant proposer aux internautes qui pourraient être intéressés par ce genre de problème quatre exercices basés sur des cryptogrammes chiffrés par transposition à tableau et un cinquième dont les cryptogrammes sont chiffrés par transposition à clé indéfinie. Ils seront présentés comme suit:

1) un ou plusieurs indices destinés à aider le décrypteur à démarrer son attaque,
2) le ou les cryptogramme(s),
3) un ou plusieurs indices plus précis, destinés à ceux qui ne seraient pas parvenus à attaquer le décryptement. Toutefois, ces indices seront chiffrés en « Jules César », avec décalage d'une lettre vers l'arrière au déchiffrement. Ce procédé dérisoire n'a pas pour but d'imposer au décrypteur une complication supplémentaire, mais d'éviter éventuellement à celui-ci de lire, en quelque sorte involontairement, des renseignements dont il n'a peut-être nul besoin.

Premier exercice

On sait que ce message est échangé entre deux trafiquants d'alcools.

EIXOI RDZAO TCAEE POTEI IDEAI MEODB NFYRE NNURS CAUOS RACTN IREES VEPAR ENLST OIWPR BETGN TSVSN ANHAN SRRVI MUMTD AAENS ONXHA IREGT RESIS DANUR SIEEM PEOAU KSLA

Indice complémentaire

Solution

Deuxième exercice

Ces deux messages ont été envoyés par un même expéditeur à deux destinataires différents.

OPEDU RCODE LOSEC NOESM AESTJ IAETR RPANC TEELI LRSAU CENER UVANP MTIRI NOANE SRVNG EQEOA EEEEN EMSUR IPNEP TUEIR EAEAH

OPEDU RCIRT ODELO SEMOA CNOES MRRDD AESTJ IAFEE ETRRP AINAN CTEEL IOSLL RSAUC EERAN ERUVA NRPIP MTIRI EONNO ANESR ECOVN GEQEO NONAE EEENR TTEMS URIPD EMNEP TUEPE NRIRE AEAHN RB

1 – Ceci est une double transposition.
2 – Le chiffreur a une inadmissible prédilection pour les rectangles parfaits.
3 – Le texte commence vraisemblablement par « Suite votre message numéro ».

NEEON TSEDI RISDM UTPLN ETYOH KAMRS ENSGO UECIE IELAR EMPDS TPUSH OETVS AECRG IORUE ASTEV TMEIA HRERR VAAUV RDERT DEEEE MURAS NOOTI PIUOP RLKEG QOTNN ERANT UEODE EARND SSERO EEZEZ OPRST ADBRE LHEEG EEERL RVRFE AEERY NAURN OENJR CFAEK

Indice complémentaire

KDBQX OSNFQ ZLLDB NLONQ SDBDM SPTZS QDUHM FSPTH MYDKD SSQDR RNHSD MCDBN LONRZ MSDME ZBSDT QROQD LHDQR SQNHR OZQBH MPOZQ SQDHY DCNMB KDRRD TKDRK NMFTD TQRQZ HRNMM ZAKDR CDBKD RCNMM ZMSCD RQDBS ZMFKD ROZQE ZHSRR NMSSQ DHYDD SPTHM YD

Solution

Cinquième exercice

Ces cinq messages sont chiffrés par des clés de transposition indéfinies
Ils ne semblent pas pouvoir être décryptés séparément : c'est seulement en les comparant qu'on peut tirer de déductions permettant de résoudre le problème
Le premier groupe est un groupe-clé indiquant la clé littérale à utiliser.

Premier message

De 1ère division à Q.G. Message N° 17 du 4 déc à 16.00

ZZZI2 EBOIC URMSS MAOSE SAREI ECUEA IPDUB SNXCT NTNSE LEELT OREXI TDZCT OEINO PTSEO OETTE RMLEA ALCL

Deuxième message

De Q.G. à 1ère division. Message N° 114 du 4 déc à 16.45

ZVII4 AEFGF EITIB LODRN HMSEA ECRVE S

Troisième message 

De 1ère division à Q.G. Message N° 17 du 4 décembre à 17.10

ZZZI2 EBOID PURLM ATSEO EMNIE CUEAA RUEDZ SCECS TNESE SLTXL TCESE ITNOC OOEIN OPETS XTBTO RMLRA ALIE

Quatrième message

De 3ème division à QG. Message N° 21 du 7 décembre à 08.00

ZVII4 FTENR MTMTO REMAA NDSOI SENDN N

Cinquième message

De 2ème division à Q.G. Message N° 11 du 9 décembre à 15.00

ZVII4 UEEDE EUOSI STRCP QGNRA ESPSK E

Indices complémentaires :

1. KDOQD LHDQF QNTOD CDBGZ PTDBQ XOSNF QZLLD DRSTM FQNTO DBKDP THHMC HPTDK ZBKDZ TSHKH RDQ 

2. KDOQD LHDQD SKDSQ NHRHD LDLDR RZFDR NMSLD LDNQH FHMDL DLDFQ NTODB KDDSL DLDKN MFTDT QKDCD TWHDL DLDRR ZFDDR SSQDR BNTQS CDCTB SHNMK DCDTW HDLDL DRRZF DRHFM ZKDPT DKDOQ DLHDQ DRSHM CDBGH EEQZA KDKDS QNHRH DLDLD RRZFD DRSKD QDBGH EEQDL DMSCT OQDLH DQ 

3. KDRCD TWHDL DPTZS QHDLD DSBHM PTHDL DBQXO SNFQZ LLDRN MSKDL DLDFQ NTODB KDHKR RNMSC NMBBG HEEQD RZUDB KZLDL DBKDD SNMSK ZLDLD KNMFT DTQKZ QDBGD QBGDC DKDTQ BKDKH SSDQZ KDRDQ ZTSHK D 

4. CDTWH DLDLD RRZFD RNMNA IDSDS ZMSBN MMTHK DRSZH RDCDS QNTUD QKDSD WSDBK ZHQOZ QZMZF QZLLD CTBQX OSNFQ ZLLD 

Solution

Références

Pierre Baud, 22.12.2008