Forum de mathématiques - Bibm@th.net

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

La transposition simple améliorée

Salut à tous,

La transposition simple a connu une période d'utilisation active. Mais son emploi fut le plus souvent consacré au surchiffrement des codes.

Pourquoi surchiffrait-on les codes ? Dès lors qu'on parle des codes et de leur surchiffrement, une digression à leur sujet est inévitable.

Laissez-moi d'abord vous conter une anecdote qui, à première vue, n'a rien à voir avec la cryptographie : au temps déjà lointain où je venais d' acquérir la télévision, j'ai assisté au lancement (je ne sais plus dans quel pays) d'un bateau : il glissa majestueusement sur sa rampe de lancement, arriva en eau profonde, s'inclina tout doucement sur bâbord...et coula !

Avec un code, il peut arriver quelque chose d'assez analogue : il demande des mois de travail, on l'imprime, on l'édite, on le diffuse à ses utilisateurs, on le met en service, après quoi, il peut très bien arriver qu'il soit compromis le lendemain, et cela sans que ses utilisateurs le sachent. On ne doit donc pas se fier à un code pour la protection du secret.

Alors pourquoi en fabriquait-on ?

a) un code transforme un texte clair en une suite de groupes de chiffres (plus rarement de lettres) plus courte que le texte d' origine (un groupe codique peut remplacer une expression et parfois même une phrase entière).
b) il est ensuite beaucoup plus aisé de soumettre ces groupes codiques à un moyen de surchiffrement,
c) un code employé « à nu » (sans surchiffrement) permettait tout de même de soustraire les messages à la connaissance des intermédiaires qui participaient à leur acheminement et, par conséquent au public. Il faut bien se rendre compte que, sur l'ensemble des messages que l'on chiffre, il y en a une grande partie dont les gouvernements étrangers se foutent éperdument. L'itinéraire et l'horaire d' un transport de fonds importe peu à la C.I.A., mais il n'est pas souhaitable que cela soit connu de Pierrot-le-fou. Le déroulement d'une enquête sur la probité d'un fonctionnaire (qui est peut-être irréprochable) n'a pas à être connu du grand public.

Dans le présent post, on sera bien obligé de se contenter de l' étude de la transposition de lettres, puisque l'on ne dispose pas de codes.

Étant donné que, même en cas de surchiffrement codique, c' était sur la transposition que reposait le sécurité, on a cherché à l'améliorer. Pour cela, on a utilisé l'une ou l'autre des deux méthodes suivantes :
a) le relèvement de lettres du tableau suivant des diagonales, préalablement au relèvement des autres lettres en colonnes.
b) l'introduction de case noires dans le tableau.

Un bon exemple vaut toujours mieux qu'on long discours (surtout qu'ici, vous avez l'un et l'autre...). Voici donc deux exemples de transpositions améliorées :

a) transposition à diagonales.

Dans cet exercice la règle est la suivante : six diagonales, orientées alternativement vers la gauche, puis vers la droite, et  dont le point de départ est déterminé par les six premiers nombres premiers contenus dans la clé. Attention : les diagonales ne partent pas du chiffre de la clé, mais de la lettre qui se trouve en dessous.

Texte clair :

Rougissant le ciel noir de flamboîments lugubres
A l'horizon, brûlaient les villages insubres ;
On entendait au loin barrir un éléphant.
Et là-bas, sous le pont, adossé contre une arche,
Hannibal écoutait, pensif et triomphant,
Le piétinement sourd des légions en marche.

Tableau de transposition :

Cryptogramme :

IBNSR  STCPU  ESOOI  OANON  SELLU  ILEBR
NADOE  CIISA  ETIAR  ARUER  LEULP  IIBIG
TNONT  RAISU  ESISH  UESET  TOTNR  ETPGS
STEPC  NNREE  NNERE  OULHL  DPTHF  ENLNR
SOERF  LINEN  EINES  ZEATS  ITCSB  BAADR
AVELO  HSISL  GEROU  ALLNU  OUNIE  EGAOL
AHAAE  MMETU  NBHDI  MRAIA  DNTET  EBNCL
MNMNL  TAOO-

Remarque : le reproche que l'on peut faire à ce procédé est que le relèvement du tableau en vue d'obtenir le crypto est assez délicat, à cause du risque de relever deux fois la même lettre, particulièrement en cas de croisement de deux diagonales. On peut y parer partiellement en marquant les lettres litigieuses par un fléchage, comme cela a été fait dans le tableau ci-dessus, au croisement de la diagonal13 avec les diagonales 2 et 5.

b) transposition à cases noires :

On trouvera plus loin la grille qui a servi à déterminer la position des cases noires de cet exemple.

Texte clair :

Comme un vol de gerfauts hors du charnier natal,
Fatigués de porter leurs misères hautaines,
De Palos de Moguer, routiers et capitaines
Partaient, ivres d'un rêve héroïque et brutal.

Tableau de transposition :

Cryptogramme :

REMOT  AVECT  ETDAN  RTESA  OIRQU  HNODE
IANOR  ERTVL  LDLTE  SEEUS  IETEB  MTEPR
PTRUO  SARHL  UNEUC  FRSIC  IEESR  ESUII
OTMUI  EEEGA  NERDU  FAOIS  DEALU  SEPUT
AGRMS  RROAN  DSNEH  BVATP  RAGHI  UAER-

Dans cet exemple, posant en principe que le réseau emploie des clés ne dépassant pas 25, j'ai confectionné un tableau de 25 colonnes contenant des cases noires réparties de façon aléatoire. Les clés plus courtes n'utilisent, en partant du côté gauche, qu'une partie de ce tableau. Ce tableau est reproduit ci-dessous :

Dans tous les cas d'utilisation de ce genre de transposition que j'ai connus, l'emplacement des diagonales ou des cases noires découlait d'une règle constante quelle que soit la clé. C'est une chose qui m'a toujours laissé perplexe : en effet, dès lors qu'on a affaire à une règle constante, elle se rattache au procédé. Donc, si l'on se réfère au deuxième principe de Kerkhoffs, elle est censée être connue de l'adversaire.

Or, puisqu'on donne aux correspondants d'un réseau un carnet dans lequel ils pourront choisir, pour chaque message, une clé parmi plusieurs dizaines, pourquoi ne pas leur fournir également un carnet dans lequel ils pourront choisir, pour chaque message, une disposition particulière des diagonales ou des cases noires ?

Ceci présenterait un avantage qui me semble important : même si l'expéditeur et le(s) destinataire(s) d'un message coche(nt) la clé utilisée afin de ne pas la réemployer, un autre membre du réseau pourra également l'utiliser. Par contre, il serait beaucoup plus improbable que deux correspondants choisissent à la fois la même clé et la même disposition de diagonales (ou de cases noires). On réduirait ainsi considérablement le risque d'analogies de chiffrement. Bien entendu, le conditionnement du message comporterait, sous une forme camouflée, non seulement l'indication de la clé utilisée, mais aussi celle de la disposition de diagonales choisies (ou de case noires).

Je vais maintenant proposer à la sagacité des internautes un cryptogramme résultant d'un chiffrement par transposition à diagonales appliquant exactement les mêmes règles que l'exemple donné plus haut. J'ai débarrassé le crypto de son conditionnement pour ne garder que les groupes codiques proprement dits. Cet exercice me parait facile, au point que j'ai hésité à vous le proposer, mais il ne faut pas non plus décourager l'amateur.

De la surveillance du trafic des deux correspondants et des heures d' acheminement des messages, on peut déduire l'extrême probabilité que le texte clair débute exactement ainsi « suite votre message numéro quarante six ».

GXILD  ECTET  MEASO  DDIEV  QNKON  TUPAM
ETTAI  IEMAN  SESTR  VDSSM  TMSFA  SREPU
NENSI  TDTRI  ENIKI  AEDIU  EIELO  TOAST
NEIOA  HEREE  LERFI  RRUNA  TIESM  TRFOO
SLEDC  ENMEN  UNLLA  PSERF  ECUEI  ICAVE
AIRLU  RIIMB  EONAY  TINRA  AIBRA  SCEIT
OEEOZ  ALEPN  E----

N.B. Gielev, si tu t'imagines que j'ai à nouveau utilisé un texte de Hérédia, c'est que tu me prends pour une bille ! ! !

Dernière modification par nerosson (10-02-2013 16:46:11)

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : La transposition simple améliorée

bonsoir tout le monde,
non je n'ai pas encore la solution.
J'ai tout au plus pris le temps de faire une analyse sommaire pour constater qu'il y a 191 caractères et que le Q et le X n'apparaissent qu'une fois. Il s'agira donc de les caser dans ce qui doit donner quarante six. Et il y a le G au début...
Rien d'autre pour l'instant.
Pas trop le temps non plus pour le moment.
Alors Nerosson patiente un peu ou cache la solution si tu la donnes.
Et bien sûr je me doute bien que tu n'es pas une bille et qu'il faudra chercher autre chose que du Hérédia...
A plus
gielev
P.S. faut que je travaille à la méthode crayon papier parce que là Excel ou autre tableur ne me sert pas vraiment...

le lendemain,
Après avoir laissé le problème posé par Nerosson tourner "en tache de fond pendant la nuit" j'en ai conclu que le G donne le nombre de colonnes.
je crois aussi qu'en l'absence du début du clair que Nerosson nous indique, déchiffrer un truc comme ça doit être très complexe... (à vérifier)
A plus

re !
je crois que ça y est je commence à y voir clair.
Je débute la rédaction du tuto en même temps donc ça prendra un peu de temps avant que je donne la solution ici. Faut que j'aille bosser !

▼voilà le travail !

Suite votre message numéro quarante six point Il nous faudrait un kamikaze point il serait souhaitable de convaincre le nomme Freddy de faire le sacrifice de sa vie point le retentissement serait considérable et la perte minime

Dernière modification par gielev (12-02-2013 16:12:59)

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : La transposition simple améliorée

euh... voilà, c'était pour dire que j'ai fini le travail hier... voir post édité ci-dessus
gielev
P.S. je n'ai pas cherché la clé...

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : La transposition simple améliorée

Salut à tous,

Bravo, Gielev, je n'en attendais pas moins de toi.

Je vais mettre au propre ma solution pour la donner sous spoiler, mais elle sera vraisemblablement très voisine de la tienne.

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : La transposition simple améliorée

Salut à tous

▼ma solution

Cryptogramme

GXILD    ECTET    MEASO    DDIEV    QNKON    TUPAM
ETTAI    IEMAN    SESTR    VDSSM    TMSFA    SREPU
NENSI    TDTRI    ENIKI    AEDIU    EIELO    TOAST
NEIOA    HEREE    LERFI    RRUNA    TIESM    TRFOO
SLEDC    ENMEN    UNLLA    PSERF    ECUEI    ICAVE
AIRLU    RIIMB    EONAY    TINRA    AIBRA    SCEIT
OEEOZ    ALEPN    E----

Expression probable : « Suite votre message numéro quarante six ».

Cette expression contient un G et un X. Le crypto commence par « GX » . Ce sont les seuls G et X du crypto. On sait que celui-ci commence par la diagonale (oblique à gauche) du nombre clé 2. La position de ces deux lettres l'une par rapport à l'autre dans le tableau de transposition est donc :

  G
X

L'expression probable se trouve au début du tableau de transposition, donc la seule disposition possible est :

S U I T E V O T R E M E S S A G E N U
M E R O Q U A R A N T E S I X

il s' en suit que la clé est de 19. Le cryptogramme ayant 191 lettres, le tableau de transposition comporte dix lignes pleines et une lettre. D'autre part, le nombre de la clé situé au-dessus du G est 2. La diagonale du nombre-clé comporte dix lettres : G, X, I, L, D , E, C, T, E, T.

La diagonale du nombre-clé 3 (oblique à droite) commence donc par ME : une seule position possible : le nombre-clé 3 se trouve en onzième position et sa diagonale comporte neuf lettres : M, E, A, S, O, D, D, I, E.

Pour les données qui suivent voir la tableau ci-dessous.

La diagonale du nombre-clé 3 (oblique à droite) commence donc par ME : une seule position possible : le nombre-clé 3 se trouve en onzième position et sa diagonale comporte neuf lettres : M, E, A, S, O, D, D, I, E.

La diagonale du nombre-clé 5 (oblique à gauche) commence donc par VQ. Le nombre clé 5 se trouve donc en sixième position et sa diagonale comporte 6 lettres : V, Q, N, K, O, N.

La diagonale du nombre-clé 7 (oblique à droite) commence donc par TU. Il y a deux T dans la première ligne du tableau. Celui qui est en dixième position donnerait un début de diagonale TA : il ne peut pas être retenu. Pour celui qui est en quatrième position, on ne connait que la première lettre (T) de la diagonale, parce que la lettre de deuxième ligne a déjà été prélevée par la diagonale du nombre-clé 5. la diagonale du nombre-clé 7 comporte 8 lettres, parce que deux de ses lettres ont déjà été prélevées par les diagonales 2 et 5. Elle se compose des lettres : T, U, P, A, M, C, E, T, T.

La diagonale (oblique à gauche) du nombre-clé 11 commence donc par AI. Le nombre clé 11 se trouve donc en quinzième position et la diagonale comporte 9 lettres, parce qu'une lettre a déjà été prélevée par la diagonale du nombre clé 3. Elle se compose des lettres : A, I, I, E, M, A, N, S, E,

La diagonale du nombre -clé 13 (oblique à droite) commence par ST ; Il y a trois S en première ligne. Le S de la première case est à rejeter parce que la diagonale commencerait par SE. Restent les deux S de « message ». Ils sont possibles tous les deux, parce que, dans les deux cas la deuxième lettre a déjà été prélevée (par les diagonales des nombres clés 2 et 11).

Faisons le point.

Si l'on fait partir la diagonale du deuxième S du mot « message », cette diagonale fera 5 lettres : S, T, R, V, D.   (une lettre déjà prélevée par la diagonale du nombre clé 2), ce qui implique que la colonne du nombre-clé 1 commence par SS, ce qui est possible si   l'on part du premier S du mot « message ». La colonne 1 aurait alors 7 lettres : S, S, M, T, M, S, F. (trois lettres ayant déjà été prélevées par les diagonales des nombres-clés 2, 7et 11)  ce qui implique que la colonne du nombre clé 2 commence par AS. Or, si l'on veut bien se reporter à l'ébauche de tableau ci-dessus, on voit que les commencements de colonnes, compte tenu des prélèvements de lettres effectués sont : S, U, I, O, E, U, O, T, R, E, T, E , S, S, ?, P, E, N, U. Pas de A dans tout cela, et la seule colonne dont on connait pas le départ et que j'ai notée par un « ? » a déjà un nombre-clé (11). Donc l'hypothèse du deuxième S du mot message est à rejeter.

Donc la solution est le premier S du mot « message » qui reçoit le nombre clé 13, dont la diagonale comporte les six lettres (STRVDS (une lettre ayant été prélevée par la diagonale 11). Ceci implique que la colonne de nombre clé 1   commence par SM. On a de nouveau deux hypothèses possibles : la colonne de rang 1 et la colonne de rang 14 dont on ne connait que la première lettre, les trois suivantes ayant déjà été prélevées par les diagonales 2, 11 et 13. Etudions l'hypothèse que la colonne de nombre clé 1 soit celle de rang 14. Elle aurait donc sept lettres (SMTMSFA)., ce qui impliquerait que la colonne du nombre-clé 2, que l'on connait (c'est aussi un numéro de diagonale), qui a déjà trois lettres prélevées par les diagonales 2, 3 et 13) ait 7 lettres (SREPUNE), ce qui impliquerait que la colonne du nombre-clé 3 commence par N, ce qui ne serait possible que pour la colonne de rang 18, qui comporterait 8 lettres (NSITDTRI) (deux lettres déjà prélevées par les diagonales des nombres clés 3 et 13). La colonne du nombre-clé 4 commencerait par EN et aurait 8 lettres (ENIKIAED), deux lettres ayant été prélevées par les diagonales des nombres-clés 2 et 11. La colonne du nombre clé 5 commencerait alors par IU, ce qui est impossible, car, dans les colonnes qui nous reste une seule commence par un I, qui est suivi d'un R.

Il faut reconnaître que l'impossibilité que de l'hypothèse de la colonne du nombre-clé 1 soit située au rang 14 s'est révélée particulièrement longue et laborieuse, mais, si l'on veut demeurer dans le domaine d'une logique rigoureuse, il faut en passer par là.

Nous savons maintenant que le nombre-clé 1 se trouve en début de clé. On a maintenant sept chiffres clés (1, 2, 3, 5, 7, 11, 13). Il en reste 12 à trouver parmi lesquels six correspondent à des colonnes dont on connait les deux premières lettres et six dont on connait la première lettre.

Dans ces conditions, il paraît superflu de détailler la mise en place de ces colonnes :

Texte clair :

Suite votre message numéro 46.
Il nous faudrait un kamikaze. Il serait souhaitable de convaincre le nommé Freddy de faire le sacrifice de sa vie. Le retentissement serait considérable et la perte minime.

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : La transposition simple améliorée

bonjour
mon tuto se trouve ici :
http://gielev.free.fr/TranspoDiagonalesNerossonV2.pdf
Si je commence comme Nerosson, à un moment donné j'utilise le fait qu'il y a 2 digrammes OA très proches pour continuer.
Bonne lecture
gielev