Soluzione di Lorenzo Cameroni

(incollo la sua mail)

FIXME formattazione dokuwiki


Invio in allegato (un po' all'ultimo) la mia soluzione.

Purtroppo il codice è poco commentato perché non ho avuto tempo di dargli una sistemata finale.

In breve l'idea è un bruteforce sulle 26^3 = 17576 possibili configurazioni iniziali, analizzato in automatico in base alla frequenza relativa delle lettere: poiché i messaggi cifrati sono presumibilmente in italiano (o inglese, come poi ho scoperto), la frequenza relativa delle lettere deve tendere a quella dell'italiano (inglese) all'aumentare della lunghezza dei messaggi.

Tra tutte le combinazioni iniziali dei rotori viene quindi scelta quella che minimizza una funzione distanza tra le frequenze relative.

La brevità dei messaggi cifrati non consente un'analisi affidabile sul singolo messaggio, ma utilizzando più messaggi (anche solo una decina si ottengono buoni risultati.

I file allegati sono

- enigmaduino.c

  Il motore di decifratura (copiato dai sorgenti pubblicati e adattato al codice C puro)
  Se invocato con un solo argomento stampa a video tutti i possibili testi cifrati (o decifrati) preceduti dalla combinazione iniziale dei rotori
  Se invocato con 4 argomenti usa i primi 3 come posizione iniziale dei rotori e il quarto come testo da (de)cifrare. Il formato di output è il medesimo ma viene stampata solo la riga richiesta.

- analizza.c

  Il motore di analisi: il programma è basato su una mia implementazione di un riconoscimento linguistico mediante n-grammi ed è stato riadattato per questa sfida.
  Va invocato con il primo argomento la lunghezza degli n-grammi da usare (si consiglia 1 ) e come secondo argomento il nome di un file di testo nella lingua in cui si presume siano scritti i messaggi criptati.
  Il programma legge da standard input una riga alla volta e stampa la stessa riga preceduta dalla distanza calcolata dalle frequenze nel file dato.

- analizza.sh

  Uno script che esegue i due programmi precedenti (dopo che sono stati compilati) e stampa a video i risultati dell'analisi
  Va invocato con 2 argomenti: il primo è il nome di un file di testo nella lingua in cui si presume siano scritti i messaggi criptati, il secondo è la cartella in cui si trovano (solo) i file di testo contenenti i messaggi cifrati.
  Esempo: $ ./analizza.sh divinacommedia.txt dati/

Inoltre sono allegati - divinacommedia.txt

  Contiene la divina commedia in formato testuale

- dati/

  Cartella contenente un po' di messaggi cifrati per poter testare il sistema

Con i dati allegati si ottiene il seguente output

$ gcc -Wall -o analizza analizza.c
$ gcc -Wall -o enigmaduino enigmaduino.c
$ ./analizza.sh divinacommedia.txt dati/

distanza minima       : 2831 (massima 2982)
codice corrispondente : 7-11-16
n° frasi analizzate   : 21
Testi decifrati:

-> perchlezebrehannolestrisceenonsonoapoiscelospiegalanturingch <-
-> rtalanturingyeardandennettoncharlesdarwinandalanturingaperfe <-
-> vrticegeekcentenarioturingsaledanzadedragonesaniversarioblad <-
-> rtalanturingyeardandennettoncharlesdarwinandalanturingaperfe <-
-> rtursulawjyearssinceturingsbirthtodaythankhimforthatmachiney <-
-> txipiquelaraedecidaincluirrecursividadeldaanterioralcentenar <-
->  rtrisciencelegoturingmachine  <-
->  rtrisciencelegoturingmachine  <-
-> rtalanturingyearhappythbirthdayalanturingletsgetturingtrendi <-
-> didyouknowalanturingwasanaccomplishedmarathonerpbhanearolymp <-
-> didyouknowalanturingwasanaccomplishedmarathonerpbhanearolymp <-
-> tentukantujuanturingbbrpminggukedpndanpersiapkanfisikkendara <-
->  theresaninteractiveturingmachineongooglesfkmkows  <-
-> rttxipivrticegeekcentenarioturingsaledanzadedragonesaniversa <-
-> rtoxfordwordsconversationswithcomputersspeakwithelizaarealex <-
-> rtnewscientistturingcompetitionresultswhatwouldthefirstconsc <-
-> alegoturingmachinehttptcomgioklvahlegoswhatcantyoudocomputer <-
-> justwonderingwhatwouldgooglecomeupwithtomorrowforonehundredy <-
-> rttxipivrticegeekcentenarioturingsaledanzadedragonesaniversa <-
-> rtcornerhousemcrrtholmesandtaylorthecreatorukpremieretomorro <-
-> alegoturingmachinehttptcomgioklvahlegoswhatcantyoudocomputer <-

$

Con qualche sorpresa ho notato che i risultati dell'analisi non variano considerevolmente se al posto della divina commedia viene utilizzato un testo in inglese.

Saluti e grazie per la sfida

Lorenzo Cameroni


Allegato

pub/arduino/turing/cameroni.txt · Last modified: 2012/06/26 12:16 by came88
CC Attribution-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0