Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
- Accueil
- » Cryptographie
- » Problème de cryptologie complexe sous Python
- » Répondre
Répondre
Résumé de la discussion (messages les plus récents en premier)
- gielev
- 27-01-2015 22:45:49
Personellement c'est gielev qui m'a amené à comprendre comment le procédé Vigenère a été cassé par Kasiski…Mais je ne suis pas plus attiré pour autant par les devinettes dont se jouent gielev et LeSingeMalicieux
T'es trop bon Totomm. A tout seigneur tout honneur.
Je dois te dire que c'est toi qui a déchiffré le truc en premier. Sur ce coup là je n'ai rien vu.
C'est en lisant ton post que j'ai été amené à vouloir tester une petite "moulinette" que j'ai écrite il y a de nombreuses années déjà.
J'ai donc extrait un morceau de phrase sans majuscules et pas trop court. Et ma moulinette m'a livré "marc" et ses permutations, fonctions de la position dans le texte où je prenais mon morceau de phrase.
Bien sûr j'aurai pu trouver marc tout de suite d'après tes indications numériques. Mon P.S. à propos du nom du prof était aussi le clin d'oeil que je faisais à ce sujet.
Donc encore une fois bravo à toi qui a trouvé le système employé par le prof de hogdush.
Je ne m'en suis pas joué de celui là.
Quant à mon intérêt pour certaines devinettes, je fais un tri assez strict. Actuellement c'est le crypto de Pinto qui m'intéresse. Et la raison en est qu'il s'agit de plus qu'une devinette puisque c'est un crypto réel issu d'une archive historique...
Enfin je suis content si j'ai pu te rendre service en te permettant de comprendre la méthode de Kasiski.
Il y a encore d'autres trucs pour trouver les longueurs de clé des Vigenère (quand elle ne sont pas trop longues par rapport au texte)
Mais ici on n'a pas du Vigenère "pur" alors je ne sais pas si elles marcheraient.
gielev
- totomm
- 27-01-2015 19:55:03
Bonsoir,
je dois essayer de trouver un programme sous python permettant de déchiffrer un texte crypté sans en connaitre la clé.
On ne sait donc pas si hogdush devait écrire un programme genre test de Kasiski comme proposé par gielev au post #22
Ou écrire un programme type yoshi donnant le texte en clair…connaissant les 3 substitutions à effectuer.
Je ne suis pas féru de cryptanalyse, mais j'ai déchiffré assez vite ce texte en comprenant (dans les parties dialogues) qu'il y avait plusieurs substitutions de type "César" (mono-alphabétique), ce qui est donc bien du poly… et wikipedia m'a fourni la table de Vigenère qui m'a fait comprendre la clé "Marc" ("marc" en fait) citée par gielev.
Le professeur a dû se donner du mal pour éliminer les caractères accentués du texte original !
Il voulait rester sur une table de Vigenère à 26 caractères et une clé de 4 caractères. S'il n'avait pas converti ces caractères accentués, ils seraient restés inchangés dans le texte crypté qui aurait été immédiatement déchiffrable. Il a simplement oublié les û, ô et â.
Je ne comprend donc pas pourquoi on pourrait mettre en doute les compétences de ce professeur qui a certainement voulu donner un exercice pas trop difficile…
Personellement c'est gielev qui m'a amené à comprendre comment le procédé Vigenère a été cassé par Kasiski…Mais je ne suis pas plus attiré pour autant par les devinettes dont se jouent gielev et LeSingeMalicieux
- LeSingeMalicieux
- 27-01-2015 15:05:16
Re,
Et puis tant qu'à être "drôle" je trouve regrettable ^_^ qu'il n'ait pas eu l'idée d'une transfo du même acabit sur les majuscules !
Ça se fait ça : 2 clés ? C'est pas du surchiffrage comme le message de Pinto... D'ailleurs dans son cas, il faudrait déterminer qui de la poule ou de l’œuf était le 1er !
Ah oui tiens ça c'est une excellente idée ! Un chiffrement sur les minuscules, et un autre sur les majuscules !
Effectivement ce n'est pas un surchiffrement (surchiffrage ? On dit comment ?) puisqu'un même caractère du clair n'est pas chiffré une fois, puis une seconde fois. Mais c'est une excellente idée (je me répète) dans le sens ou casser un tel chiffre serait intéressant.
Dans mon cas je connais quelques méthodes qui utilisent plusieurs clefs (chiffrements à deux carrés, trois carrés ou quatre carrés), mais je n'ai jamais été confronté à un crypto qui utilise, selon une règle bien entendu, deux méthodes de chiffrement différentes à appliquer sur différents caractères du clair (ou du crypto).
Pour ce qui est du crypto de Pinto, j'ai déjà pas mal travaillé dessus, mais j'attends d'affiner mes résultats avant de vous en faire part, afin de ne pas apporter plus de questions que de réponses. En tout cas il est probable que tes talents en italien (si j'ai bien compris tu maîtrises cette langue) nous soient utiles.
@+
- yoshi
- 27-01-2015 14:37:24
Re,
Dans ce cas, un caractère du clair n'est pas forcément toujours substitué par le même caractère.
Sûr ! Ça m'a assez foutu dedans...
Et puis tant qu'à être "drôle" je trouve regrettable ^_^ qu'il n'ait pas eu l'idée d'une transfo du même acabit sur les majuscules !
Ça se fait ça : 2 clés ? C'est pas du surchiffrage comme le message de Pinto... D'ailleurs dans son cas, il faudrait déterminer qui de la poule ou de l’œuf était le 1er !
En plus hogdush pourra ainsi apprendre quelque chose à son prof ;)
S'il repasse un jour par là, mais je suis pessimiste...
En l'occurrence, si c'est comme certains profs de techno chargés d'enseigner l'informatique que j'ai pu voir à l’œuvre il y a un temps certain, ils n'en savaient plus que leurs élèves que parce qu'ils avaient une leçon d'avance (maintenant, ils en baveraient !)...
Je me demande dans la classe du jeune hodgush combien auront trouvé, et combien auront trouvé seuls !
Vale tibi !
@+
- yoshi
- 27-01-2015 14:32:45
Re,
Dans ce cas, un caractère du clair n'est pas forcément toujours substitué par le même caractère.
Sûr ! Ça m'a assez foutu dedans...
Et puis tant qu'à être "drôle" ^_^ je trouve regrettable qu'il n'ait pas eu l'idée d'une transfo du même acabit sur les majuscules !
Ça se fait ça : 2 clés ? C'est pas du surchiffrage comme le message de Pinto... D'ailleurs dans son cas, il faudrait déterminer qui de la poule ou de l’œuf était le 1er !
En plus hogdush pourra ainsi apprendre quelque chose à son prof ;)
En l'occurrence, si c'est comme certains profs de techno chargés d'enseigner l'informatique que j'ai pu voir à l’œuvre il y a un temps certain, ils n'en savaient plus que leurs élèves que pa
Je me demande dans la classe du jeune hodgush combien auront trouvé, et combien auront trouvé seuls !
En plus hogdush pourra ainsi apprendre quelque chose à son prof ;)
- LeSingeMalicieux
- 27-01-2015 14:15:04
Re,
Désolé yoshi, je ne souhaitais pas remettre tes compétences en cause, mais juste apporter ma pierre à l'édifice.
En tout cas, et même si je n'ai pas beaucoup fait de python dans ma vie, je trouve ton code vraiment optimisé (et c'est un compliment) !
D'autre part, je m'insurge contre le prof de hogdush. Ceci n'est absolument pas une substitution monoalphabétique.
Le principe de la substitution monoalphabétique est de toujours remplacer un même caractère par un autre (lettre, chiffre, symboles, etc.).
Dans notre cas il s'agit de substitution polyalphabétique, où un caractère du clair est substitué par un autre (là encore : lettre, chiffre, symboles, etc.) suivant une règle préétablie. Dans ce cas, un caractère du clair n'est pas forcément toujours substitué par le même caractère.
Rien de méchant dans cette précision, mais j'aime assez voir la vérité rétablie.
En plus hogdush pourra ainsi apprendre quelque chose à son prof ;)
@+
- yoshi
- 27-01-2015 11:42:54
Re,
Moi, oui...
Mais je me suis mis à la place de hodgush...
Pour lui, j'écris ça :
# -*- coding: UTF-8 -*-
Cle=[14,0,9,24]
Texte=""
Alpha=[chr(97+i) for j in range(2) for i in range(26)]
id=-1
with open("texte_code.txt","r") as f_r:
Liste_lignes=f_r.readlines()
f_r.close()
with open("texte_decode.txt","w") as f_w:
for ligne in Liste_lignes:
for l in ligne:
if l not in Alpha:
Texte+=l
else :
id+=1
if id > 3:
id =0
pos=Alpha.index(l)
car=Alpha[pos+Cle[id]]
Texte+=car
f_w.write(Texte)
Texte=""
f_w.close()
Pour moi, ça devient :
# -*- coding: UTF-8 -*-
Cle, Texte,id=[14,0,9,24],"",-1
Alpha=[chr(97+i) for j in range(2) for i in range(26)]
with open("texte_code.txt","r") as f_r:
Liste_lignes=f_r.readlines()
f_r.close()
with open("texte_decode.txt","w") as f_w:
for ligne in Liste_lignes:
for l in ligne:
if l not in Alpha:
Texte+=l
else :
id+=1
id=id%4
Texte+=Alpha[Alpha.index(l)+Cle[id]]
f_w.write(Texte)
Texte=""
f_w.close()
Pas sûr que cela lui paraisse aussi clair...
Mais c'est plus rapide.
@+
- LeSingeMalicieux
- 27-01-2015 10:18:10
Bonjour,
Quelqu'un a-t-il une idée du roman dont il s'agit ?
Sans certitude aucune il peut s'agir de la nouvelle Espion en herbe de Leif Davidsen.
En effet, cet auteur est Danois, et dans le texte décrypté on remarque un certain Per, prénom d'origine scandinave (Forme scandinave et bretonne de Peter).
De plus, la longueur du crypto suggère bien le format de la nouvelle, et la fin du texte décrypté me semble bien être une fin d'histoire :
J'en ai conclu que :
- les majuscules ne sont pas touchées
- la 1ere minuscule d'un mot était décalée de -17 caractères, soit + 9
- la 2e minuscule d'un mot était décalée de -2 caractères, soit + 24
- la 3e minuscule d'un mot était décalée de -12 caractères, soit + 14
- la 4e était inchangée.J'ai donc créé un alphabet double (plus facile à programmer) :
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'].
Sinon après avoir opéré ton décalage tu fais un modulo 26 (reste de la division entière - opérateur % en python) sur ton résultat, et tu peux alors utiliser un simple alphabet ;)
Bonne journée
- yoshi
- 26-01-2015 21:21:51
Bonsoir,
Notre interlocuteur se serait-il découragé avant l'heure ?
Voilà un autre passage décodé :
«Il ne parle guere, ce petit», dit le Douanier par une soiree claire ou le parfum des fleurs du sureau et des eglantines envahissait tout.
«C'est vraiment un bon petit, repondit sa mere.
- Il te ressemble.
- Oui. Tout le monde le dit. Per tient de son pere. »
Alors le Douanier soupira et Tom vit que sa mere prenait sa main, comme pour le consoler.
« Je ne sais pas ce qu'on devrait faire, dit sa mere.
- Je ne peux pas me resoudre a la quitter.
- Non. Bien sûr.
- Il faut que tu essaies de me comprendre.
- C'est ce que je fais. Seulement, je ne sais pas ce que, moi, je dois faire.
- Elle ne doit rien savoir. Elle ne le supporterait pas.
- Non. Bien sûr. »
Tom s'etira sur le transat et il ouvrit les yeux tout grands. Le Douanier retira sa main d'un air deroute. Le lendemain soir, il donna de l'argent a Tom pour qu'il aille au kiosque a glaces s'acheter un enorme eskimo et regarder la television avec les enfants des touristes allemands. Il y avait un film de cow-boys a la tele. Il n'y en avait presque jamais, et il avait la permission de rester jusqu'a la fin parce que c'etaient les grandes vacances et que la nuit ne tombait pas. Tom ne comprenait pas pourquoi ils n'allaient pas ensemble chez le Douanier pour regarder la tele chez lui, mais, bref, les grandes personnes se comportaient souvent si curieusement. Les Allemands, les enfants comme les grandes personnes, parlaient de maniere bizarre. Mais c'etaient des gens pacifiques, pas du tout la race guerriere que disait son pere. Tom ne comprenait pas un mot de ce qu'ils disaient, mais il aimait bien les droles de sons etrangers qui leur sortaient de la bouche quand ils parlaient. C'etait tout a fait different du danois et different aussi de la langue que parlaient les indiens et les cow-boys a la tele. Cette langue-la s'appelait l'anglais, disait Per qui n'arretait pas de dire allright a tout bout de champ.
Je posterai le script demain...
Quelqu'un a-t-il une idée du roman dont il s'agit ?
@+
- yoshi
- 25-01-2015 15:03:38
Bonjour,
Bon, je suis bientôt au bout du bout...
Lecture, enregistrement, ça colle.
Je viens de m'apercevoir pourtant que remplacer les û (seule lettre accentuée) par des u n'était pas une bonne idée : ça me met un bazar terrible... après.
Je corrige et je relance, on va voir.
Programme pas long : 24 lignes sans l'en-tête...
C'est bon !
Donc, hogdush, voilà un plan (qui est celui du prog que j('ai écrit) qui reprend et détaille ce que tu as proposé.
1. Créer une liste Cle=[14,0,9,24]
2. Initialiser une variable Texte à vide : Texte=""
3. Créer un double Alphabet : de a à z, puis on recommence.
Tiens voilà en une ligne avec une "list comprehension" :
Alpha=[chr(97+i) for j in range(2) for i in range(26)]
4. Initialiser une variable d'index (que j'ai appelée id) qui va permettre de chercher le décalage via Cle[id].
Bien sûr [tex] id \in [0,1,2,3][/tex] sinon, punition : index out of range !
5. Ouverture du fichier "texte_code.txt".
Syntaxe :
with open("texte_code.txt","r") as nom_que_tu_veux:
Stockage d'une liste (lui donner un nom) des lignes du fichier texte_code.txt avec la méthode : readlines()
fermeture fichier
6. Ouverture en écriture (même syntaxe, en remplaçant "r" par "w") d'un deuxième fichier que tu appelleras aussi comme tu veux.
Tu vas alors lire chaque ligne de la liste_de_lignes que tu as créée, l'une après l'autre : 1ere boucle for..
for ligne in liste_de lignes:
Là, tu ouvre une 2e boucle qui va lire chaque caractère de la variable ligne (qui est une chaîne) :
for carac in ligne:
7. Traitement
Si carac n'est pas dans Alpha:
tu stockes carac dans Texte par concaténation
sinon:
tu incrémentes id de 1
Si id >3:
id = 0
Tu cherches l'index de carac dans Alpha : c'est la méthode .index() --> fichier.index(carac)
Tu ajoutes à cette valeur d'index, le décalage donné par Cle[id]. Tu obtiens un nouvel index.
Tu extrais de Alpha le caractère ayant cette valeur d'index, caractère que tu concatènes à ta variable Texte.
A la sortie de la 2e boucle :
tu écris le contenu de la variable Texte dans le bon fichier
puis tu réinitialises la variable Texte à vide
En sortie de 1ere boucle, pour faire "propre" tu fermes le fichier dans lequel tu as écrit.
Pour éviter les complications tu mets texte_code.txt et ton script Python dans le même dossier...
A toi de jouer.
Questions ?
@+
- gielev
- 25-01-2015 12:49:24
J'aimerais bien avoir de l'aide pour déterminer la taille de la clé car je ne sais pas ce qu'il faut que j'écrive dans la fonction
Le mieux que tu puisses faire est à mon avis
- d'écrire une procédure qui te permette de retirer du crypto toutes les majuscules, les caractères accentués, la ponctuation
- d'écrire ensuite une autre procédure qui en faisant varier la longueur du mot clé te permette de calculer les indices de coïncidences de toutes les sous-chaines en faisant en sorte que dès que l'IC moyen trouvé est proche de celui du français (0,076) ta procédure s'arrête.
- de traiter ensuite statistiquement les n sous-chaînes obtenues à partir de la connaissance de n (longueur du mot-clé) pour essayer de trouve le E
remarque : chercher le Q n'est pas mal non plus (ouais les gars j'ai fait exprès ! :)))) en cherchant un caractère qui soit toujours suivi d'un même autre... et en espérant qu'il n'y ait pas cinq coqs qui caquètent...
- yoshi
- 25-01-2015 12:43:13
Re,
Il fallait donc lire que vos décalages étaient 14, 0, 9, 24 dans cet ordre...
Moyennant quoi le titre et les premières phrases deviennent :
Espion en herbe
Tom trouvait que les grandes personnes avaient une drole d'odeur, forte et bonne. Ils ne sentaient pas mauvais, non, mais pas du tout comme les enfants. Ils sentaient presque tous la fumee de tabac, l'odeur de tabac des femmes etait differente de celle des hommes. Plus melangee, comme ce qu'elles se mettaient dans les cheveux quand elles se les frisaient. Leur odeur de tabac se melangeait avec du parfum et ca la sucrait. Les hommes sentaient le tabac pour pipe..
@+
- totomm
- 25-01-2015 11:42:13
Bonjour,
Mes explications ont été un peu confuses, mais avec la clé donnée par gielev, et même si j'avais déjà déchiffré (décrypté ? Excusez-moi, ami nérosson, vous qui aviez si bien précisé le bon terme...) entièrement le texte, je redonne :
m :-12, a : 0, r : -17, c : -2 en reécrivant tels quels les majuscules et tous les signes hors de la zone de a à z.
On commence avec "Eepzqz ee jqrsg"
E reste E, e donne s (-12), p donne p (0) , z donne i (-17), q donne o (-2), z donne n (-12), espace reste espace,
e donne e (0), e donne n (-17), espace reste espace, j donne h (-2),q donne e (-12), etc.
le chapeau de û est codé avant le u donc reste et on le retrouve comme pour brûlot, fâchait...mais toutes les autres accentuations ne figurent pas dans le texte que j'ai copié-collé.
Bonne suite.
- yoshi
- 25-01-2015 09:57:48
Bonjour,
Désolé, je dois être particulièrement bouché : je n'arrive à rien et je n'ai pas le temps de jouer aux devinettes...
Vous êtes tous trop forts pour moi, je crois qu'il est temps que je retourne jouer aux "petits chevaux" :-))
Ce sont des décalages (César ! ) sur 4 positions successives pour les minuscules de a à z.
Décalages pour 4 caractères successifs : -17, -2, -12, 0. C'est tout.
J'en ai conclu que :
- les majuscules ne sont pas touchées
- la 1ere minuscule d'un mot était décalée de -17 caractères, soit + 9
- la 2e minuscule d'un mot était décalée de -2 caractères, soit + 24
- la 3e minuscule d'un mot était décalée de -12 caractères, soit + 14
- la 4e était inchangée.
J'ai donc créé un alphabet double (plus facile à programmer) :
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'].
Je prends : "Eepzqz"
Je laisse le E
Je prends la position du 1er "e" dans Alpha : 5 et j'ajoute 9 : le caractère d'index 14 est un n.
J'ai donc "En"
Je passe au "p"
Position 15, décalage 24. Caractère d'index 39 : "n"...
On a donc n
On passe au "z"
Position 25, décalage 14. Caractère d'index 39 : n.
J'ai donc "Ennn"...
Inutile que je poursuive donc !
D'autre part, la clé "Marc" et vos décalages me semblent incompatibles...
La programmation en elle-même ne sera pas vraiment un problème : virtuellement, c'est fait (je refais, mais j'ai déjà en stock deux variantes de codage/décodage Vigenère. Mon problème est aussi la majuscule de Marc !)
Voilà ce que j'obtiens pour le tire et la première phrase :
Ennnqi nc sofsp
Tjk trouvait que uti bpfpycx aofjzxbvd vtfkzly fxs drole o'jbjwm, odhfn et wmspz.
Ce n'est pas très loin...
D'autre part : quid des "û" ? On les prend comme des u ?
@+
- totomm
- 24-01-2015 23:46:30
Bonsoir,
@hogdush : Voila qui semble sur la bonne voie. Mais, quant à (ce que vous avez écrit)
"la taille de la clé,l'autre qui va déterminer les fréquences d'apparition de chaque chaine de caractère
ensuite dire que la lettre qui revient le plus ds chaque motif correspond à la lettre E,..." :
la taille de la clé : gielev a montré que la clé est "Marc" sur la table de Vigenère , laquelle a été utilisée justement pour éliminer la visibilité des fréquences en substitution mono-alphabétique pure.
Faites simplement que tous les caractères lus successivement qui seraient en dehors de l'intervalle des minuscules a à z soient re-écrits tels quels et que la substitution avec la clé ne porte que sur les caractères dans cet intervalle.
Allez, en Python c'est sûrement yoshi qui vous conseillera éventuellement le mieux sur la structure et la syntaxe de votre programme.