[Risolto] Crittoanalisi Statistica (cifrario Cesare)

[claire_419]

Salve a tutti! Sto cercando di realizzare un programma in C che, dato in input un testo cifrato attraverso il cifrario di Cesare, ne trovi il testo in chiaro e la chiave segreta. Ho studiato un po' i sistemi di crittanalisi e ho capito che devo usare il Metodo Statistico, che si serve del calcolo delle frequenze delle singole lettere nel testo.
Ora detto così sembra semplice, però non riesco a trovare un algoritmo adeguato da trasformare poi in codice. Una volta trovate le lettere con maggior frequenza mi blocco :-S
Qualcuno saprebbe suggerirmi un metodo più dettagliato?

[l3on4rdo]

Ti conviene stampare il grafico delle frequenze, come primo approccio.
E analizzarlo "ad occhio".

Però non ho capito.
Tu le frequenze delle di tutte le lettere del testo cifrato le riesci a trovare?

[claire_419]

si si le frequenze di tutte le lettere del testo le riesco a trovare con un semplice ciclo. Il mio problema è che una volta trovate le lettere con maggior frequenza so che probabilmente corrisponderanno a quelle più frequenti nella lingua italiana (cioè a e i o) però come faccio a sapere con certezza qual è la vera corrispondenza e quindi trovare la chiave? 

[l3on4rdo]

ps:
Ho ritrovato questa discussione in cui si parlava di contare le occorrenze delle lettere di una stringa.
Lì si programmava in C++, mentre tu stai sviluppando in C, ma la sostanza è più o meno la stessa.

Devi calcolare le occorrenze di tutte le lettere, perché se ricordo bene (ma mi pare di sì) la crittoanalisi statistica risale alla lettera rappresentata da un "simbolo" tramite la frequenza con cui questa ricorre nel testo.
Ti conviene perciò calcolare tutte le frequenze, per poter poi produrre una sorta di "istogramma" (dico "sorta" perché tecnicamente non è un istogramma) e confrontarlo con un istogramma delle frequenze delle lettere nella lingua in cui tu supponi che il testo sia stato scritto.
Questo se supponi che nel testo sia stata fatta una sola sostituzione.
Altrimenti le cose si complicano un po', ma io partirei da un "esperimento" semplice per poi magari sfruttare pezzi di codice già scritto per affrontare un problema più complesso.

[claire_419]

Grazie del consiglio, ora controllo la discussione, anche se l'intoppo non è trovare le frequenze (fin lì ci sono), ma passare da frequenze a chiave, o meglio come capire che sicuramente quella è la chave corretta..

[l3on4rdo]

Avevo scritto il precedente messaggio prima della tua precisazione, poi l'ho inviato lo stesso.

si si le frequenze di tutte le lettere del testo le riesco a trovare con un semplice ciclo. Il mio problema è che una volta trovate le lettere con maggior frequenza so che probabilmente corrisponderanno a quelle più frequenti nella lingua italiana (cioè a e i o) però come faccio a sapere con certezza qual è la vera corrispondenza e quindi trovare la chiave?  

O posti un po' di codice, e la discussione è una discussione di Programmazione.
Oppure è una discussione generica sulla crittografia e andrebbe spostata (per questioni di maggiore visibilità).

Se la tua discussione non è strettamente tecnica su questioni di programmazione, ma solo su come ricondurre le frequenze alle lettere, ti consiglio di leggere i primi due/tre capitoli di questo libro
È davvero molto chiaro e lo trovi praticamente in ogni biblioteca comunale.

ps: io l'ho ripreso ora in prestito, così in caso ti passo qualche dritta che trovo lì.

[claire_419]

ok spero di trovarlo! comunque il codice che ho fatto fin'ora è questo:

Codice: Seleziona tutto

   //CRITTOANALISI CIFRARI DI CESARE

#include<stdio.h>

int pos(char c);
int man(void)
{
   char *nome_file1, *nome_file2;
   nome_file1=malloc(50*sizeof(char));
   nome_file2=malloc(50*sizeof(char));
   printf("Inserisci il nome del file da criptare\n");
   scanf("%s", nome_file1);
   printf("Inserisci il nome del file di destinazione\n");
   scanf("%s", nome_file2);

}


void analisi(char *nome_file1, char *nome_file2)
{
   f=fopen(nome_file1, "r");
   g=fopen(nome_file2, "w");
   if(f==NULL) {
      printf("Impossibile aprire!\n");
      exit(EXIT_FAILURE);   }
   
   char ch;
   double f, max_1, max_2, max_3, max_4;
   int frequenze[26]={0};
   int count=0; //conta il n° di lettere totali
   
   while ((fscanf(f, "%c", &ch))!=EOF) {
   
      if((ch>='a' && ch<='z') || (ch>='A' && ch<= 'Z')) {
         count++;
         frequenze[pos(ch)]++;  }
      
      for(int i=0; i<26; i++)
        frequenze[i]=frequenze[i]*100/count;  //ora frequenze segna la percentuale di frequenza per ogni lettera
   }
   
}

int pos(char c)
{
   char lett[26]={'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'};
   int i;
   c=toupper(c);
   for(i=0; i<26; i++)
      if(lett[i]==c)
      return i;      
}


  però forse in effetti è più una discussione di crittografia che di programmazione..

[claire_419]

in realtà quel codice ha qualche errore di troppo.. ecco quasto è corretto:

Codice: Seleziona tutto

//CRITTOANALISI CIFRARI DI CESARE

#include<stdlib.h>
#include<stdio.h>
#include<ctype.h>
void analisi(char *nome_file1, char *nome_file2);
int pos(char c);
int man(void)
{
   char *nome_file1, *nome_file2;
   nome_file1=malloc(50*sizeof(char));
   nome_file2=malloc(50*sizeof(char));
   printf("Inserisci il nome del file da criptare\n");
   scanf("%s", nome_file1);
   printf("Inserisci il nome del file di destinazione\n");
   scanf("%s", nome_file2);

   analisi(nome_file1, nome_file2);
   
   return 0;
}


void analisi(char *nome_file1, char *nome_file2)
{
   FILE *f, *g;
   
   f=fopen(nome_file1, "r");
   g=fopen(nome_file2, "w");
   if(f==NULL) {
      printf("Impossibile aprire!\n");
      exit(EXIT_FAILURE);   }
   
   char ch;
   
   int frequenze[26]={0};
   int count=0; //conta il n° di lettere totali
   
   while ((fscanf(f, "%c", &ch))!=EOF) {
   
      if((ch>='a' && ch<='z') || (ch>='A' && ch<= 'Z')) {
         count++;
         frequenze[pos(ch)]++;  }
      
      for(int i=0; i<26; i++)
        frequenze[i]=frequenze[i]*100/count;  //ora frequenze segna la percentuale di frequenza per ogni lettera
   }
   
}

int pos(char c)
{
   char lett[26]={'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'};
   int i;
   c=toupper(c);
   for(i=0; i<26; i++)
      if(lett[i]==c)
      return i;      
}


[Bakuriu]

Innanzitutto se la cifratura è il cifrario di cesare, allora esistono al più 26 alfabeti cifranti, quindi provarli 1 a 1 è un algoritmo a tempo costante.

Se invece ti interessa la crittografia monoalfabetica, io farei una cosa di questo tipo:
1) Fai l'analisi delle frequenze (NB: il testo dev'essere sufficientemente lungo, se è qualcosa come < 200 caratteri non è affatto detto che tu riesca a trovare la chiave)
2) Associ ad ogni frequenza le lettere che può rappresentare (qui potresti metterci un parametro per determinare quanto vicina dev'essere la frequenza etc. NB: la stessa lettera potrebbe essere plausibile per più frequenze)
3) A partire da questo schema cominci a provare le combinazioni possibili, provi a decifrare e controlli se il testo contiene una serie di parole comuni in italiano, se il numero di parole che trovi è elevato vuol dire che c'è qualcosa di buono nella decodifica. Ad esempio se trovi che XTERP è decodificato come "tempo" allora è molto plausibile che X=t,T=e,E=m,R=p,P=o.
Ovviamente devi controllare che questa combinazione torni bene anche per altre parole comuni. Se va bene per 4-5 parole comuni vuol dire che al 99% sono corrette -> assegni quei valori in modo che tutte le prove successive le usino.


Almeno, questo è quello che farei a mano... non esiste un algoritmo che ti dia sempre il risultato corretto senza fare un po' di prove... in fondo è comunque statistico, quindi ti conviene partire da una "soluzione" approssimata e migliorarla ad ogni iterazione.

Altre tecniche potrebbero essere quelle di cercare match non esatti... ad esempio cerco università, ma nei match mi va bene anche un*vers*tà, dove * vuol dire qualsiasi carattere... in fondo trovare unlversltà vuol solo dire che la *l* non va bene ma le altre lettere si.
Gli algoritmi per fare matching non esatti sono però più complicati da implementare, e probabilmente sarebbe un overkill.

[claire_419]

ok grazie mille! un'ultima domanda, forse stupida, ma per controllare che il testo contenga delle parole corrette in italiano dovrei usare qualche sorta di dizionario e cercarle lì dentro o ci sono alternative migliori?

[Zoff]

Dai un occhiata quì: http://www.csee.umbc.edu/~stephens/cryp ... tools.html

In italiano c'è la problematica delle lettere accentate.

[Zoff]

Altrimenti propongo questo script in python che implementa un algoritmo euristico che per tentativi arriva (se addestrato adeguatamente) ad una soluzione in un tempo ragionevole (minuti o ore).

Il funzionamento è semplice.
Lo script train.py si occupa di addestrare l'algoritmo creando un apposito file.
Per generare questo file si usa:

Codice: Seleziona tutto

python train.py < testo_da_addestramento.txt

Fatto questo viene generato un file: ngram_table.bin

Una volta ottenuto il file si può avviare l'algoritmo di decrittazione.
L'algoritmo proporrà di volta in volta i suoi "tentativi" e la sua analisi di correttezza della soluzione.

Per avviare la decrittazione:

Codice: Seleziona tutto

python gasimple.py < testo_da_decifrare.txt

Per chi avesse dubbi sulla legittimità di questi discorsi ricordo che fare affidamento a cifrari di sostituzione monoalfabetici al giorno d'oggi è assolutamente inutile.
Vanno bene solo a scopo didattico o per "giochetti".

Ecco un tool grafico invece per giocare con la cifratura: http://www.cryptool.org/ è per windows ma funziona quasi decentemente su wine (ha solo dei glitch grafici sui diagrammi)

[claire_419]

Grazie mille! ci dò subito un'occhiata!

[l3on4rdo]

Per chi avesse dubbi sulla legittimità di questi discorsi ricordo che fare affidamento a cifrari di sostituzione monoalfabetici al giorno d'oggi è assolutamente inutile.
Vanno bene solo a scopo didattico o per "giochetti".

Ovviamente tutti sanno che il metodo più sicuro è preparare un inchiostro con 30 grammi di allume in mezzo litro d'aceto per poi usarlo per scrivere sul guscio di un uovo (precedentemente bollito fino a farlo diventare "sodo").
La soluzione penetra nel guscio, che è poroso, senza lasciar traccia, e tinge l'albume solidificato; quest'ultimo potrà essere letto sbucciando l'uovo.

Appena trovo un modo per far entrare l'uovo nella ram divento miliardario

ps:  :P

edit:
lo sanno anche i polli! 
(scusate, non ho proprio resistito... uovo... polli...  )

[Bakuriu]

ok grazie mille! un'ultima domanda, forse stupida, ma per controllare che il testo contenga delle parole corrette in italiano dovrei usare qualche sorta di dizionario e cercarle lì dentro o ci sono alternative migliori?

Cerca su internet qualcosa tipo le 500 parole italiane più usate e mettile in una lista.


Comunque io prima cercherei di semplificare il problema, ammettendo solo le 26 lettere minuscole dell'alfabeto nel messaggio. Quindi niente spazi/lettere accentate/punteggiatura etc.

Dopodichè volendo puoi estendere il ragionamento ai 256 caratteri ASCII e vedere spazi e altri simboli come lettere.
Ma allora bisognerebbe rigenerare tutte le statistiche sulle frequenze delle lettere per includere questi caratteri, e come parole più frequenti potresti incontrare anche combinazioni di parola + segno di punteggiatura.(tipo: etc.)

edit:
Piccolo dettaglio. Per sostituire le lettere nei vari "guess" ti consiglio di sfruttare il metodo str.translate e la funzione del modulo string: maketrans:

Codice: Seleziona tutto

>>> import string
>>> def encode(plain_text, key):
...     '''Encodes the given plain_text using a monoalphabetic cipher
...     whose key is *key*.
...     '''
...     return plain_text.translate(string.maketrans(string.ascii_lowercase, key))
...
>>> encode('prova', 'cdefghijklmnopqrstuvwxyzab')
'rtqxc'


Come vedi in una riga di codice applichi qualsiasi cifratura monoalfabetica, inoltre str.translate è molto più efficiente di fare ogni volta str.replace.