Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#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 946

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

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
quatre-vingt dix-huit plus trois
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums