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 03-12-2018 13:14:28

fraxn
Membre
Inscription : 27-11-2018
Messages : 26

Merxi

.

Dernière modification par fraxn (17-12-2018 16:06:57)

Hors ligne

#2 05-12-2018 18:11:18

Rossignol
Membre
Inscription : 19-06-2015
Messages : 290

Re : Merxi

Bonjour,

On ne peut pas utiliser un simulateur en ligne pour résoudre ce genre de crypto : il faut pouvoir programmer le simulateur.

Je n'ai pas pu faire tourner le simulateur fourni par le prof  N. Ollinger dans le zip: le script nigma.py est écrit en Python 2.7 (un vieux truc).

Je préfère utiliser le module Py-Enigma.

Voir mon IPython-notebook Enigma1

@+

Hors ligne

#3 09-12-2018 09:48:14

Rossignol
Membre
Inscription : 19-06-2015
Messages : 290

Re : Merxi

Le message d'erreur est clair : le format du ring_setting est mauvais. Il faut regarder la doc du module.
D'autre part, il est inutile de faire varier l'index du rotor 3 : ce rotor n'entraine aucun rotor car il n'y a pas de rotor 4 ! 
On peut faire :

start = time.time()
best_score = float('inf')
for r in itertools.permutations(['I', 'II', 'III'], 3):
    print('Rotors = ', r)
    for ri in itertools.permutations('ABCDEFGHIJKLMNOPQRSTUVWXYZ', 2):
        ri = 'A '+' '.join(ri)
        print('rings = ', ri)
        machine = EnigmaMachine.from_key_sheet(
        rotors = r,
        reflector = 'B',
        ring_settings = ri,
        plugboard_settings = '')
        for init in itertools.permutations('ABCDEFGHIJKLMNOPQRSTUVWXYZ', 3):
            machine.set_display(init)      # position initiale des rotors
            txt = machine.process_text(k3)
            score = logscore(txt)
            if score < best_score:
                best_score = score
                print(best_score, init)
                print(txt)
delta = int(time.time()-start)
print('----- termine en ',delta//60, 'min', delta%60, 'sec')

Je vous conseille de trouver d'abord l'ordre des rotors comme pour l'échauffement #2.
Ensuite, vous fixez cet ordre dans votre programme. Le work factor est alors de $26^5 = 11881376$.
Ça prend déjà "un certain temps", vous allez voir.

À noter que le message du défi #1 est brouillé au début. Mais le token tout à la fin est bien lisible !

@+

Hors ligne

#4 12-12-2018 12:08:11

vigevénère
Membre
Inscription : 12-12-2018
Messages : 9

Re : Merxi

Afin d'optimiser un peu tout ça, il n'est pas possible de faire un peu de multiprocessing ?

est ce que ça vaut le coup ? J'ai tenté les thread mais ça ralenti le calcul... par contre le multiprocess...

Un avis ?

Hors ligne

#5 15-12-2018 12:54:15

Rossignol
Membre
Inscription : 19-06-2015
Messages : 290

Re : Merxi

@vigevénère :

Le multiprocessing améliore les choses si l'on dispose d'un CPU avec plusieurs coeurs.
Mais le mieux est d'utiliser le GPU de la carte graphique.
Le module PyOpenCL permet de programmer en OpenCL depuis Python.

Avec une bonne carte graphique, on obtient des programmes très très rapides.
Par contre, la mise au point de ces programmes est très très lente...

Cela fait seulement quelques mois que je programme en OpenCL pour la cryptographie.

Le seul crypto que j'ai cassé avec OpenCL est un problème posé sur Reddit : un gars a proposé un crypto de 45758 caractères chiffré 3 fois de suite par une sorte de Vigenère, en utilisant trois clés de longueurs respectives 37, 41 et 43.

Ce triple chiffrement est équivalent à un seul chiffrement avec une clé dont la longueur est le ppcm de 37, 41 et 43, c'est-à-dire 37*41*43 = 65231.

Comme la longueur du crypto est plus petite que la longueur de la clé, il pensait être sauf : les méthodes classiques de résolution ne s'appliquent pas.

J'ai monté une attaque en utilisant l'indice de coïncidence. Le programme casse le crypto en moins de 2 minutes (15 secondes avec la nouvelle carte graphique que je viens d'installer sur mon ordi).

Écrire une "Bombe" en OpenCL est un projet interessant.
À suivre...

@fraxn :

Il faut tester les paires de lettres AB AC AD ...etc.

Si on trouve une paire qui fait baisser le score significativement, on la garde et on cherche une seconde paire qui, ajoutée à la première, fait encore baisser le score, et ainsi de suite jusqu'à trouver les 5 paires.
Facile à faire, mais long ...

La fin du message du défi #2 précise que pour avoir les points il faut déposer le token et
N OUBLIEZ PAS DE DECRIRE EN DETAIL VOTRE METHODE DE DECODAGE DANS VOTRE POST MORTEM (!?)

@+

Hors ligne

#6 16-12-2018 23:07:00

vigevénère
Membre
Inscription : 12-12-2018
Messages : 9

Re : Merxi

bonsoir Rossignol !

Avec un processeur de dernière génération AMD, avec 8 coeurs théoriques je devrais peut être le tenter (ma carte graphique étant une GTX960, je ne suis pas certain de la vitesse).

Je vais tout de même regarder pour l'openCL histoire de m'amuser un peu :p

Pour un ordre d'idée, votre programme a trouvé la clé en combien de temps ?

Pour le dernier point sur la fin du message (d'ailleurs, merci de l'avoir donné), c'est que le DM doit être rendu avec un "rapport" expliquant les méthodes utilisées. Ce fichier s'appelant modestement le "post mortem".

Merci encore pour votre aide, c'est très agréable de se sentir aidé sans qu'on nous donne non plus la réponse.

Bonne soirée,

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)?
trente deux moins sept
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