Forum de mathématiques - Bibm@th.net

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

La transposition sans indice

Bonjour,

Pour éprouver les valeureux cryptographes, sans aucun indice, ce texte : Avez-vous les capacités  de décrypter ?

IETIS HRANO ATMME NEECI NONLS PEERL IVOUM QAEPE SSSTM AEELU
RDDEL TUERE TOLNR EPIOL BICDI EEMCL AHEPI ETOTF CNRPA RSNUA
TEDVA USTAR TERAU EMEPP CUTER SPIFT ITEMA EQNTB RRSEF EDUEE
DMOTU S----

Cordialement

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : La transposition sans indice

Ave,

Si l'on se réfère au sacro-saint principe de Kerkhoffs, nous devrions au moins savoir s'il s'agit d'une transposition simple ordinaire ou d' une transposition simple améliorée et si oui de quelle nature.

D'autre part, comme je le disais dans mon post 1 sur la transposition améliorée, les numéros de diagonales ou la position des cases noires étaient des données constantes, qui, à mon sens, ne se rattachent donc pas à la clé mais au procédé, et sont donc supposées connues.

A première vue, un examen sommaire de ton crypto ne révèle guère de particularités exploitables. Il y a bien deux "Q" qui pourraient peut-être exploités à condition qu'il s'agisse d'une transposition simple ordinaire, encore que, compte tenu du nombre de "U", ça représente un travail considérable et incertain.

Bien sûr, l'histoire de la crypto mentionne de nombreux messages isolés qui furent décryptés, mais :

1) l'histoire, ça représente beaucoup de siècles,
2) il s'agit presque toujours de messages dont le procédé (classique) prêtait nettement le flanc à une analyse sérieuse.

Comme je l'ai dit à de nombreuses reprises, le plus souvent, le décrypteur a droit à une moisson copieuse de cryptogrammes et le plus fréquemment, la première entrée est le fruit d'une coïncidence favorable, d'une maladresse de chiffrement ou d'un quelconque "accident de chiffrement".

Ces réserves étant exprimées, cela ne veut nullement dire que je ne veux pas essayer de relever ton défi, d'autre part Gielev doit déjà être en train d' affuter ses armes et, s'il y a une chance de succès, je le soupçonne d' être plus rapide que moi.

Dernière modification par nerosson (16-02-2013 14:59:07)

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : La transposition sans indice

Bonjour,

C'est une transposition simple ordinaire, donc pas de diagonales ni de cases noires.
J'ai essayé d'être le plus neutre possible.
Sauf maladresse flagrante de ma part, vous n'avez donc aucune "première entrée"
et je serai vraiment admiratif sur vos moyens si vous arrivez à décrypter....
et un peu ennuyé de vous avoir pris du temps si vous n'y arrivez pas....

Cordialement

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : La transposition sans indice

Salut à tous,

S.V.P. : si quelqu'un donne une solution, il la met sous spoiler. Merci.

Parce que j'ai l'impression que, partant à l'aveugle, si je trouve une solution, ça ne va pas tarder à être long.

En attendant, regardez le joli gadget que je me suis offert. Ca sert pas à grand chose, mais c'est joli, non ?

@totomm : excuse-moi de squatter ta discussion.

Dernière modification par nerosson (16-02-2013 18:29:49)

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : La transposition sans indice

Salut à tous
Je viens découvrir le crypto alors je vais m'y mettre.
À première vue cela risque d'être long vu ce qu'on a comme point de départ.
Le gadget un presse-papier? :)
Gielev

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : La transposition sans indice

re !
j'ai eu le temps de réfléchir un peu à ce crypto aujourd'hui.
@Totomm : les prochains jours je vais être plus occupé alors Totomm surtout sois patient et ne donne pas la solution.
Ca me prendra peut-être un peu de temps mais je pense tenir une idée d'attaque que j'espère bonne.
Mais pour l'exploiter c'est long.
A plus
gielev
P.S à priori je ne pense pas que tu aies commis une maladresse. Je dirais même qu'il est assez malin de ne pas avoir mis de W,X,Y,Z,G,J,K !
Ca me complique un peu le travail !

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : La transposition sans indice

bonjour,
j'en suis à essayer de cerner le nombre de colonnes possibles.
Les candidats mathématiquement possibles sont :
5,7,8,9,10,11,14,15,16,18,20,23,32,40,52
On remarquera qu'il n'y a aucun tableau complet possible genre 13x12 ou 6x26 mais mon analyse montre qu'il manque aussi les tableaux à 17,19,21,22 et bien d'autres colonnes.
Évidemment garder les valeurs faibles conduit à un nombre restreint de colonnes donc en principe à un nombre restreint de permutations de colonnes (= solution facile à laquelle je ne crois pas)
Garder les valeurs élevées conduit à des colonnes très courtes, respectivement de 3,4 ou 5 caractères. Je n'y crois pas non plus.
Aussi mes recherches vont-elles s'orienter vers des solutions plus "centrales" genre 14,15,16 ou 18...
@Totomm, fais moi signe si je m'égare...
@Nerosson, si Totomm ne réagit pas cela débroussaille un peu le terrain.
@tous : si j'arrive à déchiffrer ce truc je vous donnerai ma méthode ultérieurement. Pour aujourd'hui ce sera tout, je vais passer à autre chose pendant quelques temps...
gielev
P.S j'espère ne pas m'être planté dans mes calculs ! :(

Dernière modification par gielev (18-02-2013 11:23:51)

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : La transposition sans indice

Bonjour,

@gielev : oh non, vous ne vous égarez pas....

je me répète :
Je serai vraiment admiratif sur vos moyens (et méthodes) si vous arrivez à décrypter....
et un peu ennuyé de vous avoir pris du temps si vous n'y arrivez pas....

J'ai volontairement voulu qu'il n'y ait aucune "première entrée" sémantique et le moins d'indices possibles
Ce qui m'a stupéfait est le "MOTUS" final = "silence" qui se trouve là vraiment par hasard !

Cordialement

EDIT : Ma dernière phrase N'EST PAS un indice...

Dernière modification par totomm (18-02-2013 12:34:08)

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : La transposition sans indice

Salut à tous.

@totomm

Les seules possibilités d'entrée que j'ai pu déceler dans ce message sont :

QU  : Il y a deux Q et huit U, ce qui fait 16 possibilités d' association de deux portions de colonnes dont on ignore les limites supérieure et inférieure. Ce dernier point ajoute encore à l'incertitude concernant la vraisemblance de l'association considérée.

2) FF  : Il y a trois F, ce qui fait six possibilités d' association de portions de colonnes. De plus, l'hypothèse FF est bien plus incertaine que l' hypothèse QU.

J'ai ainsi réalisé 22 associations de colonnes qui sont presque toutes possibles et parmi lesquelles deux au moins sont bonnes. Mais comment les identifier ? Or pour les tester, il faudrait, pour chacune d'elles, faire de très nombreuses tentatives de rapprochement avec d' autres portions de colonnes, ce qui donnerait une multitude de de pavés larges de trois lettres dont une grande proportion serait possible.

Pour quelqu'un qui travaille "papier-crayon", il s' agirait d' un travail herculéen, devant lequel je déclare forfait. Gielev, qui utilise des moyens informatiques pour les rapprochements de colonnes, aura peut-être plus de succès que moi.

Je suis à peu près convaincu que les gens de la NSA, avec leurs monstrueux ordinateurs, viendraient à bout de ton problème en très peu de temps.

Une autre remarque : j'ai déjà répété à satiété qu'il fallait absolument éviter les rectangles parfaits : ton crypto en est un très bel exemple : je suis porté à croire que, s' il s'agissait un rectangle parfait, on rentrerait dedans comme dans du beurre. Mais je suis tellement convaincu que tu n'as pas fait une pareille bévue que je n'ai pas même pris la peine d' en vérifier la possibilité. J'espère que je n'ai pas eu tort. L'inégalité des longueurs de colonnes est un facteur de sécurité de première importance.

En dehors des voies de recherche énumérées ci-dessus, je n'ai trouvé dans ton crypto aucune de ces coïncidences favorables qui parfois nous mettent le pied à l'étrier. Je suis d'ailleurs en train de bûcher sur un exercice destiné à démontrer que, même avec un cryptogramme qui, comme le tien, n' est accompagné d' aucun indice, une coïncidence favorable permet parfois d' en venir à bout. J'espère pouvoir mettre ça sur le site demain ou après-demain.

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : La transposition sans indice

Bonsoir,

Je suis à peu près convaincu que les gens de la NSA, avec leurs monstrueux ordinateurs, viendraient à bout de ton problème en très peu de temps.

J'en suis aussi convaincu, sauf à s'arrêter quand l'assemblage prend un peu de sens. Il y en a un, avec des phrases en français bien faites.

@nerosson : Vos leçons plaisantes sont bien retenues : Bien sûr j'ai évité le rectangle parfait !!
J'ai choisi d'éviter tout indice sémantique pour qu'il ne reste que la grosse compilation des colonnes...

Cordialement

gielev

Membre

Inscription : 08-03-2007

Messages : 425

Re : La transposition sans indice

Pour quelqu'un qui travaille "papier-crayon", il s' agirait d' un travail herculéen, devant lequel je déclare forfait. Gielev, qui utilise des moyens informatiques pour les rapprochements de colonnes, aura peut-être plus de succès que moi.

Pour l'instant je n'ai réalisé aucun rapprochement de colonnes, ni sur le papier ni par moyens informatiques. Je me contente de calculer ce qui est impossible (voir mon post plus haut que j'avais écrit à ton intention pour te simplifier un peu le travail Nerosson). Cela explique aussi que j'avance plutôt lentement car en fait je ne dispose pas d'outils tout faits,mais je suis en train de me les concevoir.

Une autre remarque : j'ai déjà répété à satiété qu'il fallait absolument éviter les rectangles parfaits : ton crypto en est un très bel exemple : je suis porté à croire que, s' il s'agissait un rectangle parfait, on rentrerait dedans comme dans du beurre. Mais je suis tellement convaincu que tu n'as pas fait une pareille bévue que je n'ai pas même pris la peine d' en vérifier la possibilité. J'espère que je n'ai pas eu tort. L'inégalité des longueurs de colonnes est un facteur de sécurité de première importance.

Comme je l'ai écrit le rectangle parfait est impossible. Tu as bien fait de ne pas essayer.
Tu auras remarqué que Totomm m'a répondu que je ne m'égarais pas dans mes hypothèses.

En dehors des voies de recherche énumérées ci-dessus, je n'ai trouvé dans ton crypto aucune de ces coïncidences favorables qui parfois nous mettent le pied à l'étrier. Je suis d'ailleurs en train de bûcher sur un exercice destiné à démontrer que, même avec un cryptogramme qui, comme le tien, n' est accompagné d' aucun indice, une coïncidence favorable permet parfois d' en venir à bout. J'espère pouvoir mettre ça sur le site demain ou après-demain.

Si tu le mets en ligne faudra que tu aies la patience d'attendre que j'aie, soit trouvé la réponse du crypto de Totomm, soit jeté l'éponge...
Pour l'instant je ne la jette pas car j'ai encore des idées de calculs.
J'ai dans un premier temps réussi à réduire les 336 "situations" calculées à 56 éventuellement valables. Mais j'entrevois encore un calcul qui me permettra d'en éliminer un certain nombre. (au départ, à cause d'une erreur j'avais 687 situations ! herculéen effectivement, c'est pourquoi j'essaie de bien vérifier mes calculs avant d'avancer... et j'espère toujours que ce que je fais reste correct)
Je rappelle que je travaille sur les hypothèses 14,15,16,18 colonnes.
A plus,
gielev
@Totomm  je ferai un petit break prochainement mais cela ne signifiera pas que j'abandonne. Je préviendrais ici si c'est le cas. Mais j'espère bien pouvoir annoncer un succès.

un peu plus tard... c'est bien ce que je pensais. J'ai pu réduire mes 56 situations à 41 et éliminer l'hypothèse 14 colonnes.
@Totomm comme d'hab tu me dis si je m'égare... :) Je vais regarder le suivant etc... 16 et 18 sont les cas où j'ai le plus de situations... je crains que cela ne soit une de ces 2 solutions !

encore un peu plus tard ! Je ne suis plus qu'à 27 situations (avec toujours les hypothèses 15,16,18 colonnes)... ça commence à être gérable ! 27 situations signifie cependant encore un grand nombre de combinaisons qu'il va me falloir trier (61 combinaisons selon mes calculs).

Dernière modification par gielev (19-02-2013 09:24:35)

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : La transposition sans indice

Salut à tous.

Voici un cryptogramme à décrypter sans aucune autre indication que le procédé de chiffrement : transposition simple, sans diagonales ni cases noires.

VQQRU  URRIO  CPLMA  DTSDP VNCUT  MENDL
SFNES  NCLEO  HCSES  DCROR FEGLT  XRNII
OTMNE  AASMP  NAUER  CLSID EEESU  EACEA
IERUI  ULSAI  IEAEC  EESAN THEMX  ERCMI
EEANU  MIEOS  FEDAS  AIIET NEPUE  UUCMO
UMIUO  UUIRT  YEDN

▼ma solution

            10              20            30
VQQRU   URRIO   CPLMA   DTSDP   VNCUT   MEND

            40             50              60
SFNES   NCLEO   HCSES   DCROR   FEGLT   XRNII  

           70              80             90
OTMNE   AASMP   NAUER  CLSID   EEESU   EACEA

           100             110             120
IERUI   ULSAI   IEAEC   EESAN   THEMX   ERCMI

           130             140             150
EEANU   MIEOS   FEDAS   AIIET   NEPUE   UUCMO

           160
UMIUO   UUIRT   YEDN

On observe (lettres 2 et 3) QQ : ces deux lettres doivent être suivies de deux U. On trouve trois séquences uu : 5-6, 146-147 et 156 – 157. Remarquons que le V qui précède fait nécessairement partie de la même colonne

La première séquence UU est trop près de la séquence QQ.

Par rapport à la fin du crypto, la séquence 146-147 implique :
a) une colonne de 21 (le E qui précède UU faisant partie de la même colonne), ce qui n'est pas vraisemblable parce que cela suppose une clé trop courte.
b) deux colonnes de 10 et de 11 ce qui est possible (clé de 16 ou 17).

la séquence 156-157 implique une colonne de 10 (le O qui précède UU faisant nécessairement partie de la même colonne. La clé pourrait alors être :
a) soit de 17 : (6 x 9) + (11 x 10) = 54 + 110 = 164,
b) soit de 18 : (2 x 10) + 16 x 9) = 20 + 144 = 164.

J'ai donc trois hypothèses à envisager.

Je vais commencer par la troisième. Pourquoi ? Parce que c'est la plus facile à exploiter : le fait que la colonne du début de crypto commence par VQQ implique que la colonne de fin de crypto commence par OUU et, de ce fait,la colonne de fin de crypto fait 10 lettres, ce qui implique que la colonne de début de crypto en fait également 10 (puisqu'elle précède l'autre) (on a vu qu'il n'y en a pas de 11 dans l'hypothèse étudiée). Or dans cette hypothèse, il n'y a que deux colonnes de 10 . Les voilà identifiées, ce qui permet le découpage du crypto en colonnes, puisque toutes les autres colonnes sont de 9.

            10              20              30
VQQRU   URRIO   CPLMA   DTSDP   VNCUT   MENDL

            40             50               60
SFNES   NCLEO   HCSES   DCROR   FEGLT   XRNII

            70              80              90
OTMNE   AASPM   NAUER   CLSID   EEESU   EACEA

            100            110            120
IERUI   ULSAI   IEAEC   EESAN    THEMX   ERCM

           130              140            150
EEANU   MIEOS   FEDAS   AIIET    NEPUE   UUCMO

             160
UMIUO   UUIRT   YEDN

On a donc, à gauche du tableau les deux colonnes suivantes :

VO
QU
QU
RI
UR
UT
RY
RE
ID
ON

QU doit être suivi par une voyelle. Toutes sont possibles, mais E et I sont plus vraisemblables ce qui me suggère MIE (119) ou IIE (137).
J'opte pour IIE, parce que l'autre hypothèse me donne en première ligne VOM plutôt que VOI.
   

VOI
QUI
QUE
RIT
URN
UTE
RYP  
REU
IDE
ON

VOI suggère VOICI, VOILA, VOIR, VOIS, VOIT. RYP suggèrte CRYPTO ou CRYPTE.Je recherche dans les colonnes restantes une séquence compatible : une seule : 11.

VOIC
QUIP
QUEL
RITM
URNA
UTED
RYPt
REUS
IDED
ON

VOIC suggère VOICI. RYPTE suggère DECRYPTEMENT ou DECRYPTEUR
Quelques essais permettent de placer cinq colonnes supplémentaires.

VOICIUNEX
QUIPEUTAR
QUELACHAN
RITMEMESI
URNACOMMI
UTEDEUXPO
RYPTEMENT
REUSSIRAM
IDEDAUCUN
ON

   
On a placé neuf colonnes. Il n'en reste que neuf autres à placer. D' autre part, au fur et a mesure que  le pavé s'élargit, les hypothèses possibles se multiplient (exemple, chance, commis). Il semble donc superflu de détailler le reste de la reconstitution.

VOICIUNEXEMPLEDECE
QUIPEUTARRIVERLORS
QUELACHANCENOUSSOU
RITMEMESILECHIFFRE
URNACOMMISAUCUNEFA
UTEDEUXPOINTSLEDEC
RYPTEMENTDUMESSAGE
REUSSIRAMEMESANSLA
IDEDAUCUNEINDICATI
ON

Texte clair :

Voici un exemple de ce qui peut arriver lorsque la chance nous sourit, même si le chiffreur n'a commis aucune faute : le décryptement du message réussira même sans l'aide d'aucune indication.

Je ne conteste nullement que des cas aussi favorables se présentent rarement. Mais il ne faut pas perdre de vue que, dans la pratique, un décrypteur peut disposer de plusieurs dizaines de messages à analyser. Dans ce cas, une coïncidence favorable a beaucoup plus de chances de se produire.

La comparaison du cryptogramme avec le tableau de chiffrement permet de rétablir la clé numérique :

1-18-16-2-12-17-13-8-7-9-14-3-5-11-4-15-6-10

Reste la reconstitution de la clé alphabétique : ce sera pour demain.

Dernière modification par nerosson (19-02-2013 21:50:54)

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 348

Re : La transposition sans indice

Chapeau bas, monsieur Nerosson!

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : La transposition sans indice

Bonjour et merci. J'apprécie tout particulièrement.

@gielev.
La photo, c'est bien entendu un cadran chiffrant. Le disque intérieur est mobile. J'aurais préféré qu'il soit lui aussi en lettres.

Dernière modification par nerosson (21-02-2013 15:58:52)

GeorgeL

Invité

Re : La transposition sans indice

Bonsoir

Mon programme a trouve la solution en 30 secondes.

▼longueur

longueur de cle 20

▼crib

CESTTRESANODIN.....

▼cle

KCQLHSTDMBENAIGOFJRP

▼texte

CESTTRESANODINETSIMP
LEPOUREPROUVERLESCAP
ACITESDESAMATEURSDEC
HIFFREMENTQUIPRATIQU
ENTCEFORUMASSIDUMENT
POINTETLAMETHODEAETE
INTRODUITEPARLEMEMBR
ELEPLUSVENERABLE

Merci pour le defi,

George L.

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 348

Re : La transposition sans indice

Bonjour George,

  Pourrais-tu nous décrire le principe de fonctionnement de ton programme?

Fred.

GeorgeL

Invité

Re : La transposition sans indice

Bonjour Fred

Un fonctionement tres similaire aux methodes manuelles decrites sur ce site, et aussi par William Friedman dans

http://www.nsa.gov/public_info/declass/ … ysis.shtml   Part IV.

Surtout pour le cas de rectangles incomplets - "Hat Diagrams". Voire aussi

http://www.umich.edu/~umich/fm-34-40-2/  Chapter 12 - Section 12.3

1) Phase 1 du programme:

- Calculer le Bigram Score de toutes les possibilites de colones adjacentes i, j.
- Pour le cas incomplet - faire ce test a toutes les positions possibles de debut de texte de chaque colone (qui depend des types des autres colones , short ou long).
- construire une cle de depart qui reflecte le mieux ces donnees.

2) Phase 2 - un Hill Climbing

- on commence part la cle de la Phase 1, et on repete:

- faire un changement dans la cle.
- calculer le n-grams score de apres ce changement, si meilleur on garde la cle.
- repeter tant qu'on peut ameliorer le score.

- si le Hill Climbing se bloque sur un maximum local, on refait Phase 1 & 2.

(pardon pour les fautes d'orthographe et termes Franglais - j'ai quitte la France il y a tres longtemps).

J'espere que c'est assez clair.

Georges

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : La transposition sans indice

Bonjour,

et je serai vraiment admiratif sur vos moyens si vous arrivez à décrypter....
et un peu ennuyé de vous avoir pris du temps si vous n'y arrivez pas....

Je maintiens toute mon admiration pour celui dont les outils n'ont mis que 30 secondes pour trouver, et à tous ceux qui auront essayé !
Crypter pour être non déchiffrable n'est donc pas si évident : Il faut un grand professionnalisme !

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : La transposition sans indice

re,

La clé que j'avais utilisée est : "RETROUVERCESBONSMOTS"