Lezione 19 e 20
Crittografia I
A) Tabella dei bigrammi
B) Riconoscimento automatico della lingua
C) Rottura dei codici
Fabio Scotti
Laboratorio di programmazione
per la sicurezza
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
1
Lezione 19 e 20
Fabio Scotti
Laboratorio di programmazione
per la sicurezza
Tabella dei bigrammi
Obiettivi :
•
Comprendere come la tabella dei bigrammi sia composta e come
possa essere usata per il riconoscimento automatico di una
lingua sia uno strumento utile e per la rottura dei codici
crittografici
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
2
Tabella dei bigrammi
• La frequenza delle lettere in una lingua è una
peculiarità che, se misurata da un
programma, aiuta a riconoscere la lingua e a
rompere il codice di Cesare.
• La tabella dei bigrammi è la frequenza con la
quale compaiono COPPIE di lettere in una
lingua.
• La tabella dei bigrammi è uno strumento che
discrimina ancora meglio una lingua e può
essere utile nella rottura di altri codici
crittografici.
3
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Esempio
Frequenza lettere:
...
n=65,
n=66,
n=67,
n=68,
n=69,
n=70,
n=71,
n=72,
A,
B,
C,
D,
E,
F,
G,
H,
freq=
freq=
freq=
freq=
freq=
freq=
freq=
freq=
0.103848
0.013314
0.103848
0.063906
0.071895
0.026628
0.037279
0.005326
Tabella bigrammi:
Spazio
A
B
C
D
....
Spazio
1
824
0
0
22
A
473
0
32
136
139
B
90
55
64
0
0
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
C
596
88
0
125
0
D
640
63
0
0
6
...
...
..
.
.
.
4
Lettura della tabella
Tabella bigrammi:
Spazio
A
B
C
D
....
Spazio
1
824
0
0
22
A
473
0
32
136
139
B
90
55
64
0
0
C
596
88
0
125
0
D
640
63
0
0
6
...
...
..
.
.
.
Come iniziano le parole
in questa lingua
Come finiscono le parole
in questa lingua
5
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Creazione della tabella
(1)
• E’ una tabella che deve contenere percentuali
(rapporto fra interi, quindi numeri razionali).
• La rappresentiamo in memoria come una
matrice di float:
float bigrammi [256][256]; // ascii
float bigrammi [512][512]; // ascii estesa
6
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Creazione della tabella
(2)
char c1, c2 ;
float bigrammi[256][256];
int numero_Bigram , temp1, temp2, i1 , i2;
… // apro in lettura il file e memorizzo il puntatore in Fp
… // inizializzo la matrice bigrammi a zero
while ( fscanf(Fp, "%c", &c1) == 1 )
{
while ( fscanf(Fp, "%c", &c2) == 1 )
{
if (( c1 < 0 ) || ( c1 > 256 )) || ((
{
// sono nella tabella ASCII ?
…
// inserire codice
}
temp1 = (int) c1;
temp2 = (int) c2;
c1 < 0 ) || ( c1 > 256 ))
// cast raccomandabile
// cast raccomandabile
bigrammi[temp1][temp2] = bigrammi[temp1][temp2] + 1;
numero_Bigram = numero_Bigram + 1 ;
}
}
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
7
Creazione della tabella
(3)
// normalizazzione della matrice
for (i=0; i1<256; i1++)
// normalizzazione dei conteggi
{
for (i=0; i2<256; i2++)
// normalizzazione dei conteggi
{
bigrammi[i1][i2] = bigrammi [i1][i2] / numero_Bigram * 100 ;
}
}
8
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Utile funzione
Uscita
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
Ingressi
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
é
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
char converti(char);
Con questa funzione, si
converte, carattere per
carattere, un testo in
una sequenza di
caratteri maiuscoli prima
di calcolare la frequenza
delle lettere.
9
Lezione 19 e 20
Fabio Scotti
Laboratorio di programmazione
per la sicurezza
Riconoscimento della lingua automatco
Obiettivi :
•
Essere in grado di scrivere programmi per l'identificazione
automatica della lingua di un testo
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
10
Riconoscimento automatico
• Il riconoscimento automatico della lingua è
utile in molte applicazioni quali:
– gli editor di testo (l’impiego dei dizionari dei
sinonimi, la correzione automatica, ecc..);
– in campo crittografico (rottura codici
crittografici semplici).
• In particolare ci focalizziamo sul
riconoscimento automatico della lingua in
base alla distribuzione delle lettere.
• Vengono esaminati i testi non crittati.
11
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Tabella delle frequenze
Frequenza lettere:
Lingua
a
b
Francese
26
20
Inglese
26
21,2
Italiano
26
20,5
Russo
31
26,5
Spagnolo
26
21
Tedesco
26
21,2
12
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Metodo di riconoscimento (1)
Frequenza lettere:
Esamino il file
Lingua
a
b
Francese
26
20
Inglese
26
21,2
Italiano
26
20,5
Russo
31
26,5
Spagnolo
26
21
Tedesco
26
21,2
Calcolo la frequenza
delle lettere
Confronto le frequenze
con quelle note
Determino la lingua
13
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Metodo di riconoscimento (2)
Frequenza lettere:
Esamino il file
Lingua
a
b
Francese
26
20
Inglese
26
21,2
Italiano
26
20,5
Russo
26,5
31
Spagnolo
26
21
Tedesco
26
21,2
Nel mezzo del cammin
di nostra vita …
Calcolo la frequenza
delle lettere
A = 25,6%
B = 19,8%
Confronto le frequenze
con quelle note
La lingua più
vicina
è l’italiano
Determino la lingua
14
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Usando tutte le frequenze
LINGUA INCOGNITA
PERCENTUALE DI OCCORRENZA
(frequenza lettera)
ITALIANO
10%
5%
A
E
E
A
B
C
C
…
D
D
B
Lettere
10%
Scarto percentuale
La somma totale degli scarti
è la distanza fra la lingua
incognita e l’italiano
5%
A
B
C
D
E
…
Lettere
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
15
Progettazione del programma
(1)
Cosa serve:
• una funzione produci_frequenza() che dato un
file ritorna il vettore delle frequenze delle
lettere;
• una funzione calcola_Distanza() che dati due
vettori di frequenze ritorna una distanza fra le
due lingue.
16
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Progettazione del programma
(2)
Come funzionerà il programma:
• usando produci_frequenza():
–
dati dei file di testo in italiano, inglese, francese, ecc...,
si calcolano le loro frequenze;
–
si calcola la frequenza delle lettere del file di lingua
incognita;
• usando calcola_Distanza() si confrontano le
frequenze del file di lingua incognita con quelle dei
file di lingua nota;
Possiamo affermare che il file di lingua incognita è
scritto nella lingua che ha minore scarto totale.
17
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Programma riconoscimento
// qui carichiamo
produci_frequenza(
produci_frequenza(
produci_frequenza(
(2)
le frequenze di riferimento
"promessiSposi.txt“
, frequenze_ITA , LUN_ALFABETO );
"othello.txt"
, frequenze_ENG , LUN_ALFABETO );
"marsigliese.txt"
, frequenze_FRA , LUN_ALFABETO );
produci_frequenza( "sconosciuta.txt" , frequenze_incognita , LUN_ALFABETO );
// confrontiamo le frequenze
// (aggiungere il codice che controlla il massimo)
distanza = calcola_Distanza(frequenze_incognita, frequenze_ITA , LUN_ALFABETO );
printf("la lingua incongnita dista %f dall'ITALIANO \n" , distanza ) ;
distanza = calcola_Distanza(frequenze_incognita, frequenze_FRA , LUN_ALFABETO );
printf("la lingua incongnita dista %f dal FRANCESE \n" , distanza ) ;
distanza = calcola_Distanza(frequenze_incognita, frequenze_ENG , LUN_ALFABETO );
printf("la lingua incongnita dista %f dall'INGLESE \n" , distanza ) ;
getchar();
exit(0);
} // main
18
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Programma riconoscimento
(3)
float calcola_Distanza(float frequenze_1[], float frequenze_2[] , int lunghezza_alfabeto )
{
float distanza;
distanza = 0 ;
// distanza euclidea (applico Pitagora in N dimensioni con N= lunghezza_alfabeto)
for( i = 0; i < lunghezza_alfabeto ; i = i+1 )
{
distanza = distanza + (frequenze_1[i]- frequenze_2[i])*(frequenze_1[i]- frequenze_2[i]);
}
distanza = sqrtf( distanza );
return distanza;
}
//
sqrtf radice quadrata per float
19
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Lezione 19 e 20
Fabio Scotti
Laboratorio di programmazione
per la sicurezza
Rottura dei codici
Obiettivi :
•
Comprendere come il riconoscimento automatico di una lingua
sia uno strumento utile per la rottura dei codici crittografici
•
Essere in grado di scrivere programmi per l'identificazione
automatica della lingua di un testo e la rottura dei codici
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
20
Esempi di rottura di codice
• Iniziamo ad esplorare le tecniche per rompere
i codici crittografici più semplici: il codice di
Cesare e i codici a sostituzione.
• In questa lezione descriviamo i procedimenti
e vediamo alcuni programmi ausiliari utili.
• Nelle prossime lezioni scriveremo programmi
che automaticamente romperanno il codice.
• Lavoriamo nell’ipotesi di conoscere la lingua
nel quale è stato scritto il messaggio crittato
(ipotesi successivamente rimuovibile).
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
21
Rottura del codice di Cesare
1. Calcolare le frequenze delle lettere nella
lingua in cui si immagina sia scritto il
messaggio crittato.
2. Calcoliare le frequenze delle lettere nel
messaggio crittato.
3. Sovrapporre le distribuzioni: una delle due
viene fatta traslare fino a quando si ottiene la
migliore sovrapposizione.
4. La quantità di lettere di cui si è dovuto
traslare l'alfabeto della distribuzione
costituisce la chiave del cifrario.
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
22
Esempio
MESSAGGIO CRITTATO
10%
ITALIANO
PERCENTUALE DI OCCORRENZA
(frequenza lettera)
A
5%
Z
Chiave = 0
A
E
C
C
B
Z
E
D
…
D
B
Lettere
10%
A
Chiave = 1
A
Z
E
C
5%
C
B
E
D
D
B
…
F
Lettere
10%
Chiave = 15
P
5%
O
Z
A
Q
B
R
C
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
S
D
T
E
…
23
Lettere
Rottura del codice con sostituzione (1)
• Nel caso del codice di Cesare basta trovare
UNA chiave per decrittare tutto il codice.
• Nei codici con sostituzione occorre trovare la
chiave con la quale è stata crittata ogni
lettera.
Ac
B&
…
24
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Rottura del codice con sostituzione (2)
• Si utilizza l’approccio con le frequenze di
lettera oppure con i bigrammi.
• Perché la statistica possa essere di supporto,
occorre che il testo cifrato sia abbastanza
lungo.
• E’ anche possibile unire molteplici testi
crittati, ma occorre essere certi che siano
stati crittati con lo stesso metodo e con la
stessa chiave.
25
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Rottura del codice con sostituzione (3)
• In primis si cerca di associare le vocali
(frequenza maggiore) guardando le
frequenze di lettera, poi le consonanti.
Crittato
Lingua
Decrittazione
‘k’: 25,8%
‘a’:26%
‘k’’a’
‘b’:20%
‘c’: 7%
…
‘s’: 20,1%
‘b’:20%
‘s’’b’
…
26
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Rottura del codice con sostituzione (4)
• In secundis si risolvono eventuali dubbi
confrontando la tabella dei bigrammi
ottenuta dal codice crittato e quella della
lingua.
Crittato
“df”: 0,25%
Lingua
“ab”:0,26%
Decrittazione
‘d’’a’ e ‘f’’b’
…
• Questo approccio permette dei controlli
incrociati. Ad esempio si controlla se tutti i
bigrammi mostrano ‘d’’a’ ecc.. (si usa la
conversione maggiormente presente).
27
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza
Controllo del successo
• Per automatizzare il tutto, occorre un criterio
per stabilire automaticamente se la rottura
del codice ha avuto successo.
• Quando i programmi di decrittazione
propongono una soluzione, è possibile
verificare che le parole presenti nella
soluzione appartengano a dei dizionari.
• Ad esempio se nessuna parola decrittata
appartiene ad un dizionario, allora la chiave è
sbagliata e occorre provare a decrittare con
altre chiavi.
28
Fabio Scotti – Università degli Studi – Laboratorio di programmazione per la sicurezza