Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 18-06-2016 14:47:27
- Dynastato
- Invité
Message secret à déchiffrer
Bonjour,
Il m'a été confié un mystérieux message crypté que je me tarde de décoder ! Il contient des symboles dans le genre "dièse", flèches, signes mathématiques, etc... Je me sens inspiré par une attaque par dictionnaire. Le hic est que les symboles peuvent légèrement changer en fonction du contexte.
Je me verrais bien réaliser un petit programme remplaçant sur une phrase, les symboles par des lettres en testant toutes les combinaisons et en les comparant à un dictionnaire.
Avez vous des conseils ?
Merciii
#2 18-06-2016 18:43:50
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 947
Re : Message secret à déchiffrer
Bonsoir,
Je me verrais bien réaliser un petit programme remplaçant sur une phrase, les symboles par des lettres en testant toutes les combinaisons et en les comparant à un dictionnaire.
Ton dictionnaire contiendrait quoi ? dictionnaire que tu réaliserais toi-même ?N
En utilisant que langage ? As-tu une bonne maîtrise de ce langage.
Dans tous les cas, commence via stylo/papier : écris en pseudo-code ce que chaque phase (à partir du moment où tu les auras définies)
est censée faire.
Et seulement quand ce sera fait et que tu seras satisfait, passe au codage...
Ton message a quelle longueur ? Plus il est court, plus uil sera difficile à décoder, mais moins long sera le temps que - en brute force - qu'il fera pour passer les combinaisons en revue...
Le hic est que les symboles peuvent légèrement changer en fonction du contexte.
Qu'est-ce que tu veux dire par là ? quel contexte ?
Et plus en amont encore, dans quel contexte, justement, s'inscrit ce message ? Il était censé t'être adressé ? A quelle occasion ? As-tu une idée de quoi il peut bien parler (attaque par mot probable).?
Bref, beaucoup de questions et vraiment peu de réponses pour te faire avancer...
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#3 18-06-2016 19:21:13
- Dynastato
- Invité
Re : Message secret à déchiffrer
J'utiliserais un dico informatisé déjà réalisé pour tester la validité des phrases générées.
Je précise que j'utilise Matlab et que je connais les bases de la programmation.
Le message fait une cinquantaine de mots.
Visiblement, lorsque les caractères présentent des accents ou autre, cela donne des symboles légèrement modifiés pour le message codé.
Mais je vais essayer de travailler sans pour simplifier le travail.
Concernant le message, je n'ai aucune idée de ce qu'il raconte !
J'ai commencé le programme et j'ai associé chaque symbole à un chiffre. J'en ai 26. Je vais tester toutes les associations "symboles-lettres" possibles sur quelques mots, puis comparer à un dico.
#4 18-06-2016 19:56:52
- Dynastato
- Invité
Re : Message secret à déchiffrer
J'ai un souci de mémoire avec ma méthode : quand je crée mon tableau avec toutes les permutations des 26 chiffres, j'obtiens évidemment une erreur concernant la mémoire. Comment palier ce problème ?
#5 21-06-2016 17:02:33
- Rossignol
- Membre
- Inscription : 19-06-2015
- Messages : 290
Re : Message secret à déchiffrer
Bonjour Dynastato,
Si vous voulez mon avis, la méthode que vous utilisez est vouée à l'échec. On peut contourner le problème d'espace mémoire en utilisant un itérateur qui va retourner un alphabet à chaque appel, mais le problème de temps d'exécution va persister.
Il y a $26! = 403291461126605635584000000$ alphabets possibles. En supposant un test toutes les nanosecondes, le temps nécessaire pour tester tous les alphabets est $\frac{26! \times 10^{-9}} {3600\times 24\times 365}\approx 12788288341$ années.
Même en étant patient ...
Puisqu'il semble que les espaces entre les mots soient conservés dans le crypto, vous pouvez utiliser les motifs des mots.
La fonction Python suivante renvoie le motif d'un mot :
def pattern(w):
"""Retourne le motif (pattern) du mot w
"""
icourant = ord('A') # pointe sur la lettre disponible courante
h = {} # dico des lettres déjà utilisées
p = '' # le motif
for c in w:
if c not in h: # première apparition de la lettre
h[c] = chr(icourant) # on l'enregistre
icourant += 1 # on pointe sur la lettre suivante
p += h[c] # on met le motif à jour
return p
Par exemple :
mot : MOTIF ELEMENT MATHEMATIQUE ANTICONSTITUTIONNELLEMENT
motif : ABCDE ABACADE ABCDEABCFGHE ABCDEFBGCDCHCDFBBIJJIKIBC
Le motif d'un mot est invariant par une substitution mono-alphabétique.
Par exemple, le mot 'ALPHABETIQUE' a pour motif 'ABCDAEFGHIJF'. Si on décale toutes ses lettres d'un rang (chiffre de César) on obtient 'BMQIBCFUJRVF' qui a le même motif :
ALPHABETIQUE BMQIBCFUJRVF
ABCDAEFGHIJF == ABCDAEFGHIJF
Donc, si dans un crypto on a le mot 'BMQIBCFUJRVF', on peut chercher les mots du dictionnaire qui ont le même motif que lui. Il n'y en a que quatre pour mon dico : 'ORTHOPEDIQUE', 'ALPHABETIQUE', 'ALPHABETISME', 'ASPHALTERONT'.
On a donc quatre possibilités d'alphabet déchiffrant. En croisant les résultats obtenus pour d'autres mots du crypto, on obtient en général le texte clair rapidement.
Je ne peux pas être plus précis, car je ne connais pas MATLAB.
Note : j'utilise les dictionnaires de l'ACA.
---
It is not necessary to be crazy to be a cryptanalyst. But it always helps.
Joseph Rochefort
Hors ligne
Pages : 1