Forum de mathématiques - Bibm@th.net

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Je donne: procédé, texte clair, cryptogramme. Je demande : les clés

Bonjour à tous,

Dans une discussion intitulée « Code inviolable ? », qui a fait couler beaucoup d' « encre », un internaute proposait un cryptogramme à décrypter, ajoutant que si personne n'y parvenait, il faudrait en conclure qu'il était l'auteur d'un code inviolable.

Dans un post du 21/4, Ju Bicycle expliquait avec clarté à quel point une telle argumentation était... (soyons poli) déraisonnable.

D'une façon générale, seuls des procédés relativement simples et classiques peuvent être cassés par l'analyse d'un seul cryptogramme. Dans un forum, il faut bien en passer par là, mais dans la réalité, les cryptanalystes travaillent généralement sur l'ensemble du trafic d'un réseau, ce qui est très différent.

D'autre part, contrairement à un principe fondamental de la cryptologie, il ne décrivait pas le procédé employé, alors que (pardon de le répéter), la résistance à la cryptanalyse doit se fonder exclusivement sur la ou les clés.

Mon souci ici, est d'essayer de démontrer que MÊME AVEC UN MAXIMUM DE RENSEIGNEMENTS, un procédé QUI N'EST PAS INVIOLABLE peut résister aux efforts des cryptanalystes si toutes les données ne concernent qu' un seul chiffrement. Prenant, j'en conviens, quelques risques, (un autre peut réussir où j'ai échoué) je voudrais proposer ici un problème à ceux que cela pourrait intéresser : JE FOURNIS LA DESCRIPTION DU PROCEDE DE CHIFFREMENT (COMPLETEE PAR UN EXEMPLE), LE TEXTE CLAIR ET LE CRYPTOGRAMME CORRESPONDANT, et je demande seulement que l' on trouve les clés ayant servi à effectuer le chiffrement.

Ce procédé, très célèbre, s'appelle l' « ADFGX » et n'est pas inviolable, puisqu'il a été décrypté en 1917 par le génial cryptanalyste Georges Painvin.

Il se décompose en deux phases :
a) une substitution au moyen d'un carré de 25 contenant un alphabet incohérent. Chaque lettre du clair est remplacée par ses coordonnées . Ces coordonnées, identiques pour les colonnes et les lignes, sont désignées par les lettres A, D, F, G, X. Voici un exemple de ce genre de carré . C'est celui qui servira pour l'exemple de chiffrement que je compte donner.

Je précise au passage que les Allemands remplacèrent très vite le carré de 25 par un carré de 36, afin d'y inclure les 10 chiffres, ce qui nécessita une coordonnée supplémentaire : L' « ADFGX » devint alors l' « ADFGVX » qui fut, lui aussi décrypté par Georges Painvin.

b) cette première opération donnait une suite de lettres, qu'on appelle l'antigramme, laquelle était transformée par une transposition à tableau classique, ce qui avait pour effet de « briser » les bigrammes représentant les lettres claires. L'exemple qui va suivre utilise le carré de 25 ci-dessus et la clé de transposition suivante :

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

Exemple de chiffrement :

Texte clair :  Stimson déclara deux points un gentleman ne lit pas le courrier d' autrui

Antigramme :

DXXXD GFADX DDXGF FXDAD GDXAG GXAFF XDGAF XAFDD DGXGX XDXGA XGAAX DXGXX GDXDF AXAXG XGXDG DDGXX AFXAD XGDXD ADDDG AGGGG DGXDG GFFXA GAXXG GGADG

Tableau de transposition :

Cryptogramme :

XAFGA   XDFFG   FGXDA   GDDGD   AAFAA   XXXXX   XGDGG   DAXDD   DDAAD   XADGD   GGXXD   XXXGG   DFFXX   XDGXD   GDAXA   GXXDD   XXDDG   GDAGD   GGXXG   DXAXF   XDFGA   GDGAG   AXFFG   GGXGX

VOICI MAINTENANT LE CHALLENGE PROPOSE :

Texte clair :

je vous adresse quelques renseignements interessants primo une note sur le frein hydraulique de cent vingt secundo une note sur les troupes de couverture tertio une note relative a madagascar

N.B. J'ai pris pour texte clair un extrait du fameux bordereau de l' affaire Dreyfus.

Cryptogramme :

GGDDA   DDFFD   AXDDD   GDXDG   AXAFD   GFGFX   GDAFG   GGXFX   FXAAD   XDGXD   DFAXF   GFAFG   DGGAA   DGFXA   DFGGG   FGAFF   XGGGF   XDFXD   GGDDG   FAFDA   DGGFA   XDADA   FXDDA   GGFFD   DDDGA   GAXAF   ADDFD   XDFAD   DDDDD   DAADF   AAADD   XDXDX   DAFDD   GGXGF   AGGFG   FDDFG   ADGDD   GDAXG   AGFXG   FGFFX   FXAGD   FFXDD   FAFGX   XDFAG   FXDGF   GDDDF   DAAFF   FAGFX   XAADD   DXFXD   FDADA   XDDFD   AAAXA   XFDFA   FGFFD   FFFAD   AADAD   XDGDG   GADDA   FXDFF   GDXGA   GFDDD   GDGGF   DXXXF   AGDF

Peut-on à partir de tous ces renseignements (comment faire plus : procédé, texte clair, crypto), retrouver les deux clés, à savoir le carré de 25 et la clé de transposition ? Georges Painvin, en plus de ses exceptionnelles capacités, disposait quotidiennement de nombreux messages.

J'espère que Gielev et d'autres voudront bien se pencher sur la question. Et pourquoi pas Dan Andrew lui-même, qui serait sans doute enchanté de prendre sa revanche et de me mettre le nez dans mon caca ?

Dernière modification par nerosson (18-06-2010 12:53:39)

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : Je donne: procédé, texte clair, cryptogramme. Je demande : les clés

Salut à tous...
Comme je l'ai précisé sur un autre fil je suis occupé sur un autre crypto. De plus je n'ai jamais décrypté d'ADFG(V)X... à ma grande honte car c'est une grosse lacune pour qui s'intéresse comme moi à la cryptographie "classique". Néanmoins je connais un peu la technique ce qui me permet de donner pour l'instant une courte réponse avec peut-être des indications pour qui veut se lancer dans ce challenge.
Nous possédons le clair, donc il est possible de procéder au comptage de chaque lettre présente...
Je suppose qu'il n'y a pas de nulle (est-ce une bonne hypothèse je n'en sais rien encore... mais je devine que si des nulles ont ét rajoutées cela va se compliquer singulièrement).
Il faudrait donc, à partir du texte chiffré, tester diverses répartitions en colonnes de longueurs variables,
effectuer pour chacune d'elles un comptage des bigrammes et vérifier l'adéquation de ce comptage avec celui des lettres du texte clair. C'est là qu'on voit que l'existence de nulles pourrait poser problème.
Une fois l'adéquation trouvée on obtient immédiatement le carré de 25 et simultanément l'ordre exact des colonnes donc la clé de transposition utilisée.
Pour répondre à la question de Nerosson, je dirais oui on peut avec les renseignements donnés retrouver les 2 clés. Cela étant la recherche peut prendre du temps.
A +
gielev

ju_bicycle

Membre

Inscription : 31-08-2009

Messages : 79

Re : Je donne: procédé, texte clair, cryptogramme. Je demande : les clés

Je dirai même plus, ià la main ca risque de prendre un temps relativement long...Avec un petit code bien arrangé ca devrait être faisable sans trop de problème (a vérifier of course) j'essairai de jeter un oeil ce week-end
++
Julien

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Je donne: procédé, texte clair, cryptogramme. Je demande : les clés

Salut à tous,

Horreur !!! En relevant mon crypto, j'ai redoublé un groupe. Je m'étais pourtant relu.... C'EST MAINTENANT CORRIGE. Si cela a perturbé le travail de quelqu'un, je lui présente mes excuses.

Gielev, c'est un travail totalement honnête : S'il y avait des lettres nulles, il faudrait une convention qui figurerait dans le procédé. D'ailleurs, le texte clair, où, pour éliminer toute ambiguïté, j'ai supprimé toute ponctuation, tout accent et où les espaces ne doivent pas être pris en compte, se compose de 162 lettres. Le crypto en fait exactement le double, soit 324. C'est d'ailleurs en vérifiant ce point que j'ai découvert cette sottise de groupe redoublé.

A part ça, je suis content que certains s'intéressent à mon problème. Cependant, je persiste à faire quelques réserves sur le bel optimisme de mes correspondants....Il est vrai que l'informatique, à laquelle je ne connais pratiquement rien, réserve parfois des surprises.

Dernière modification par nerosson (18-06-2010 13:38:49)

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : Je donne: procédé, texte clair, cryptogramme. Je demande : les clés

salut à tous
oh non je suis loin d'être optimiste... car si la technique que j'ai exposée paraît simple sa mise en oeuvre et le temps de calcul seront très longs.
Même si on connaissait la longueur de la clé de transpo. par exemple 18 il y aurait 18! permutations de colonnes à tester soit de l'ordre de 10^15...
Si on ne connait pas cette longueur il faut partir de 1! (absurde j'en conviens) et ajouter 2!+3!+4!+ etc...combinaisons jusqu'à trouver la bonne...
Donc un bon programme et un ordi puissant sont nécessaires pour arriver au but.
Mais ça c'est un peu de la force brute... il y a peut-être un autre moyen.
Je ne le vois pas car il faudrait trouver une faiblesse du crypto or on a déjà tout, clair, crypto, méthode...

Dernière modification par gielev (20-06-2010 09:09:16)

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : Je donne: procédé, texte clair, cryptogramme. Je demande : les clés

Je corrige un peu mon propos ce matin... en effet le nombre total de combinaisons est un peu inférieur, ha! ha!
En effet si on envisage une transposition sur 10 colonnes on aura 4 colonnes "longues" suivies de  6 colonnes "courtes". Il y aura alors non pas 10! = 3628800 combinaisons à tester mais 4! x 6! = 17280 soit 210 fois moins... Et d'une ! (mais on n'est pas sorti de l'auberge pour autant)
On peut peut-être encore diminuer ce nombre en se disant que dans ce tableau de transposition les colonnes impaires ne peuvent être tout à fait quelconques si le carré de 25 est construit avec une clé.(par exemple les digrammes commençant par X seraient moins nombreux...) Si le carré de 25 est totalement incohérent cette remarque ne vaut pas... voilà de deux !

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Je donne: procédé, texte clair, cryptogramme. Je demande : les clés

Salut, Gielev,

Te revoilà. J'en conclus que tu es revenu la "tête" basse de sur le site "cadrans chiffrants" de Pierre Baud. Il t'avait pourtant prévenu qu'il avait fait tout son possible pour faire échec à toute cryptanalyse.

Bon ! Il se trouve que moi, je le connais, Pierre Baud. On a peiné sur les mêmes cryptos. J'étais chez lui quand il a brûlé le brouillon de son chiffrement. J'ai profité de ce qu'il était en train d' engueuler sa femme pour sauver un tout petit morceau  du papier en question. Ca pourrait sûrement te mettre le pied à l'étrier.

Tu veux que je t'en fournisse la copie ?

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : Je donne: procédé, texte clair, cryptogramme. Je demande : les clés

salut Nerosson,
Concernant le crypto de P.Baud je suis toujours dessus. Je manque un peu de temps c'est pour cela que ça n'avance pas très vite.
J'ai écrit ma procédure d'extraction des morceaux de clés dont je dispose grâce au mot probable.
Je suis en train de les tester sur le crypto (avec les 11 variantes possibles) pour déterminer la longueur exacte de la clé. (il y a 429 x 11 variations de clés à étudier).
De temps en temps je mets ça de côté. Et je réfléchis à ton crypto ADFGX. Je pense à un truc concernant les colonnes "paires" et "impaires" mais je ne sais pas encore comment je vais faire ça.
Donc pour l'instant j'ai pas encore besoin d'aide sur le crypto de Baud. Mais merci quand même j'y penserai le cas échéant.
gielev

karlun

Membre

Inscription : 05-05-2010

Messages : 216

Re : Je donne: procédé, texte clair, cryptogramme. Je demande : les clés

Toc! toc! toc!

Bonsoir,

Puis-je?

Je ne connais pas du tout la cryptographie.
Mais les cherchailles m'intéressent.

J'ai apprécié les explications fournies par l'honorable Nerosson concernant la description du procédé de chiffrement  "ADFGX".

Les observations de Gielev sont pertinentes.
Est-il trop tôt pour prendre en compte l'observation suivante?
Si le nombre de colonnes est inconnu au moins peut-on être assuré que le fond (le bas) de celles-ci (dans un ordre chaotique) sera rythmable (encore faut-il trouver la (les) bonne(s) longueur(s)) puisque la fin du message est "a madagascar" soit 22 éléments dont 5 paires identiques.

C'est sur cette base que j'essaie d'avancer. Mais faut du temps.

a+-*/

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : Je donne: procédé, texte clair, cryptogramme. Je demande : les clés

Toc! toEst-il trop tôt pour prendre en compte l'observation suivante?
Si le nombre de colonnes est inconnu au moins peut-on être assuré que le fond (le bas) de celles-ci (dans un ordre chaotique) sera rythmable (encore faut-il trouver la (les) bonne(s) longueur(s)) puisque la fin du message est "a madagascar" soit 22 éléments dont 5 paires identiques.

C'est une excellente observation !
Jusqu'à présent je m'étais contenté d'utiliser le clair pour déterminer le fréquences de chaque lettre du clair.
Mais il est évident que si on s'intéresse en plus à leur position ce pourrait être un plus notable.
Il faut chercher en fait un schéma du genre a-une lettre-a-une lettre-a-une lettre-a pour "amadaga".
Je vais y réfléchir dès que possible...
gielev

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : Je donne: procédé, texte clair, cryptogramme. Je demande : les clés

Salut Nerosson,
Je vais essayer de m'attaquer à ton problème.
Je vais juste quémander un indice...
Dans un autre fil tu as écrit que "le chiffreur est connu pour avoir un goût regrettable pour les rectangles parfaits".
Est-ce le cas ici aussi ?
gielev

Dernière modification par gielev (02-07-2010 08:44:19)

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : Je donne: procédé, texte clair, cryptogramme. Je demande : les clés

Salut, Gielev,

Non, ce n' est pas le cas ici.

D'ailleurs, dans une discussion qui vise à montrer que, dans le cas d'un procédé qui, dans une utilisation en réseau, peut être décrypté, le décryptement devient PRATIQUEMENT impossible si l'on ne dispose que d'un cryptogramme, la règle normale était de ne pas imposer de difficulté exceptionnelle, mais de ne pas non plus faire de cadeau.

C'est ce que j'ai essayé de faire ici.

karlun

Membre

Inscription : 05-05-2010

Messages : 216

Re : Je donne: procédé, texte clair, cryptogramme. Je demande : les clés

cherch-jour aaaaaaaaah-tousse.

Si le nombre de colonnes est inconnu au moins peut-on être assuré que le fond (le bas) de celles-ci (dans un ordre chaotique) sera rythmable (encore faut-il trouver la (les) bonne(s) longueur(s)) puisque la fin du message est "a madagascar" soit 22 éléments dont 5 paires identiques.

Devant tant de possibilités selon le nombre de colonnes induisant un nombre de lignes et en plus n'étant pas toujours mêmes (+/1) pfff! là j'sais pas où chercher.

Ce (+/-1) de lignes par colonne se re-produit (terme intéressant) pour chaque pas si bien que cette observation  "a madagascar" ne peut pas constituer au départ un indice suffisant.

Si un indice me semble devoir être cherché c'est, en premier, le nombre de colonne (cf Gielev).
J'attends des nouvelles de Gielev mais Nerosson nous a prévenu que ce travail était sans issue malgré la clarté des données de départ.

Ah!   +-*/