Steganografia
Crittografia classica
Occultamento
del messaggio
Barbara Masucci
Steganografia
Dipartimento di Informatica ed Applicazioni
Università di Salerno
[email protected]
Steganos = coperto
http://www.dia.unisa.it/professori/masucci
Grafien = scrittura
Barbara Masucci - DIA – Università di Salerno
Steganografia: Problemi
Steganografia: Esempi
¾ Erodoto
¾ Se il corriere è attentamente perquisito il
messaggio può essere scoperto
¾ Comunicazione mediante scrittura su tavoletta di legno in
seguito ricoperta di cera
¾ Comunicazione mediante schiavo a cui è stato rasato il capo
¾ Raschiando tavolette di cera
¾ Rasando il capo al corriere
¾ Avvicinando il foglio ad una fonte di calore
¾ Sbucciando le uova
¾ Plinio il vecchio
¾ Comunicazione mediante inchiostro simpatico ottenuto dal
lattice di titimabo
¾ Gian Battista Porta
La segretezza è perduta al momento
dell’intercettazione
¾ Comunicazione mediante uovo sodo e una sorta di “inchiostro
simpatico”
Barbara Masucci - DIA – Università di Salerno
1
2
Barbara Masucci - DIA – Università di Salerno
3
Crittografia
Cifrari simmetrici
Trasformazione
+
Segretezza
Operazioni:
trasposizioni e sostituzioni
m
m
Crittografia
Alice
canale insicuro
Cryptos = nascosto,
segreto
Grafien = scrittura
4
Barbara Masucci - DIA – Università di Salerno
Cifrari a trasposizione
Basate su matrici
¾ Permutazione del testo in chiaro
I simboli del testo in chiaro cambiano posizione
nel testo cifrato
Barbara Masucci - DIA – Università di Salerno
EGGSOESIRMGEOAST
GSESRAGIOEEGTOMS
MSAGOERT
ES GI SGEO
4
1
3
2
5
M
E
S
S
A
G
G
I
O
S
E
G
R
E
T
4
1
3
2
5
E
G
G
S
O
E
S
I
R
M
G
E
O
A
S
O
Ripetizione trasposizione
Esempio
¾ MSAGOERTESGISGEO
5
Tecniche di trasposizione
Trasposizione:
¾ MESSAGGIO SEGRETO
Bob
Barbara Masucci - DIA – Università di Salerno
T
6
Barbara Masucci - DIA – Università di Salerno
7
Cifrario di Cesare
Tecniche di trasposizione
100100-44 a.C.
Svetonio (Vitae Caesarorum): lettera di Cesare a Cicerone
¾ Usate da sole sono facili da analizzare
¾ Le lettere del testo in chiaro sono visibili
¾ LTEETRE DEL TSETO IN CIHRAO SNOO
VSIBILII
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
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
testo in chiaro
¾ Possono essere usate insieme a tecniche con
sostituzione
X ← M+3 mod 26
OMNIA GALLIA EST DIVISA IN PARTES TRES
RPQLD JDOOLD HVW GLYLVD LQ SDUWHV WUHV
testo cifrato
Barbara Masucci - DIA – Università di Salerno
8
Cifrario di Cesare
Cifrari con shift
¾ Proviamolo insieme, collegandoci al link
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
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
¾ http://www.dia.unisa.it/professori/masucci/sicurezza0506/
tutorial
¾ Shift – Cifratura
¾ Accettare il certificato di protezione dell’applet, e poi
Start Applet
¾ Inserire 3 nella casella Shift
¾ Per decifrare, scegliere
Shift - Decifratura
Barbara Masucci - DIA – Università di Salerno
9
Barbara Masucci - DIA – Università di Salerno
Cifrari con shift
Chiave K
X ← M+K mod 26
K∈{0,…,25}
Quante chiavi sono possibili?
10
Barbara Masucci - DIA – Università di Salerno
11
Cifrario con shift
Crittoanalisi
Dato un testo cifrato
¾ Provo tutte le possibili chiavi
Facile da fare
¾ Poco tempo
Una sola chiave mi darà un testo in chiaro con
senso compiuto
¾ È il messaggio originale
12
Barbara Masucci - DIA – Università di Salerno
Cifrari a sostituzione
monoalfabetica
Crittoanalisi
K
RX KTSXPBD HIPHTGP
13
EK XGFKCOQ UVCUGTC
1
SY LUTYQCE IJQIUHQ
14
FL YHGLDPR VWDVHUD
2
TZ MVUZRDF JKRJVIR
15
GM ZIHMEQS WXEWIVE
3
UA NWVASEG KLSKWJS
16
HN AJINFRT XYFXJWF
4
VB OXWBTFH LMTLXKT
17
IO BKJOGSU YZGYKXG
5
WC PYXCUGI MNUMYLU
18
JP CLKPHTV ZAHZLYH
6
XD QZYDVHJ NOVNZMV
19
KQ DMLQIUW ABIAMZI
7
YE RAZEWIK OPWOANW
20
LR ENMRJVX BCJBNAJ
8
ZF SBAFXJL PQXPBOX
21
MS FONSKWY CDKCOBK
9
AG TCBGYKM QRYQCPY
22
NT GPOTLXZ DELDPCL
10
BH UDCHZLN RSZRDQZ
23
OU HQPUMYA EFMEQDM
11
CI VEDIAMO STASERA
24
PV IRQVNZB FGNFREN
DJ WFEJBNP TUBTFSB
25
QW JSRWOAC GHOGSFO
12
Barbara Masucci - DIA – Università di Salerno
13
Barbara Masucci - DIA – Università di Salerno
Alfabeto in
chiaro
Alfabeto
cifrante
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
O C T M B W L A K J D X I N E Y S U P F Z R Q H V G
testo in chiaro:
testo cifrato:
C
T
A
O
S
P
A
O
¾ Numero di chiavi da provare: 26!=4 x 1026
Con 106 computer, ognuno che prova 109 chiavi al secondo, la
ricerca esaustiva richiede 104 anni
Improponibile!
14
Barbara Masucci - DIA – Università di Salerno
15
Cifrari a sostituzione
monoalfabetica
Cifrari a sostituzione
monoalfabetica con chiave
Frase chiave: JULIUS CAESAR
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
J U L I S C A E R B D F G H K M N O P Q T V W X Y Z
Quante chiavi sono possibili?
Più di 26, ma meno di 26!
Barbara Masucci - DIA – Università di Salerno
16
Cifrari a sostituzione
monoalfabetica con chiave
17
Barbara Masucci - DIA – Università di Salerno
Crittoanalisi
¾ Ogni lettera cambia “abito”, ma conserva la sua
“identità”
¾ Frequenza
¾ Vicinanza con altre lettere (q è sempre seguita da u,…)
¾ Altre regole (mai due vocali di seguito,…)
¾ Il cifrario può essere
regolarità del linguaggio
rotto
considerando
le
¾ Calcolo della frequenza relativa delle lettere nel cifrato
¾ Confronto con la distribuzione standard delle frequenze per
quel linguaggio
Barbara Masucci - DIA – Università di Salerno
18
Barbara Masucci - DIA – Università di Salerno
19
Crittoanalisi
Frequenze occorrenze lettere
Edgar Allan Poe, “Lo scarabeo d'oro” (1843)
14
12
10
8
6
4
2
0
A B C D E F G H I
A
B C
italiano 10,3 0,9 4,3
inglese
7,3 1,3 3,5
francese 8,3 1,3 3,3
D
E
F G
3,8 12,6 0,8 2,0
4,3 12,8 3,0 2,0
3,8 17,8 1,3 1,3
53++!305))6*;4826)4+.)4+);806*;48!8`60))85;]8*:+*8!83(88)5*!;
46(;88*96*?;8)*+(;485);5*!2:*+(;4956*2(5*-4)8`8*; 4069285);)6
!8)4++;1(+9;48081;8:8+1;48!85;4)485!528806*81(+9;48;(88;4(+?3
4;48)4+;161;:188;+?;
J K L M N O P Q R S T U V W X Y Z
H
I
J K
1,1 11,6 0,0 0,0
3,5 7,8 0,3 0,5
1,3 7,3 0,8 0,0
L
6,6
3,7
5,8
M
2,6
2,8
3,2
N
6,6
7,8
7,2
O
8,7
7,5
5,7
P
3,2
2,8
3,7
Q
0,6
0,5
1,2
R
6,7
8,5
7,3
S
6,1
6,0
8,3
T
6,1
9,3
7,2
U
3,0
3,0
6,3
V
1,5
1,5
1,8
W
0,0
1,5
0,0
X
0,0
0,5
0,0
Barbara Masucci - DIA – Università di Salerno
Y
0,0
2,3
0,8
Z
0,9
0,3
0,0
20
Barbara Masucci - DIA – Università di Salerno
Crittoanalisi
Crittoanalisi
53++!305))6*;4826)4+.)4+);806*;48!8`60))85;]8*:+*8!83(88)5*!;
46(;88*96*?;8)*+(;485);5*!2:*+(;4956*2(5*-4)8`8*; 4069285);)6
!8)4++;1(+9;48081;8:8+1;48!85;4)485!528806*81(+9;48;(88;4(+?3
4;48)4+;161;:188;+?;
caratteri
8
;
4
+ )
*
5
6
! 1
0
9 2
: 3
?
`
- .
occorrenze
33
26
19
16
13
12
11
8
6
5
4
3
2
1
53++!305))6*;4826)4+.)4+);806*;48!8`60))85;]8*:+*8!83(88)5*!;
46(;88*96*?;8)*+(;485);5*!2:*+(;4956*2(5*-4)8`8*; 4069285);)6
!8)4++;1(+9;48081;8:8+1;48!85;4)485!528806*81(+9;48;(88;4(+?3
4;48)4+;161;:188;+?;
Assumiamo che 8
corrisponda al carattere e
7 occorrenze di ;48
Assumiamo che
;>t
4>h
8>e
…poi
Barbara Masucci - DIA – Università di Salerno
21
22
5 rappresenta
!
"
8
"
3
"
4
"
6
"
*
"
+
"
a
d
e
g
h
i
n
o
(
"
r
;
"
t
A good glass in the bishop's hostel in the devil's seat
twenty-one degrees and thirteen minutes northeast
and by north main branch seventh limb east side
shoot from the left eye of the death's-head a bee
line from the tree through the shot fifty feet out.
Barbara Masucci - DIA – Università di Salerno
23
Nulle
Omofoni
¾ Molti simboli per cifrare singoli caratteri frequenti
¾ Aggiungere simboli meno frequenti
¾ in posizioni da non alterare il significato
testo in chiaro:
testo cifrato:
testo in chiaro: QUELQRAMODELQLAGO...
testo cifrato:
…
12.6 per E
24
Nomenclatori
(scelti a caso!)
3.15 per
ÕÑ®
Barbara Masucci - DIA – Università di Salerno
25
La congiura di Babington
¾Nel 1586 Maria Stuarda, regina di Scozia, fu
condannata a morte per aver cospirato contro la
cugina Elisabetta
¾La congiura, organizzata da Anthony
Babington, prevedeva
¾ In aggiunta all’alfabeto cifrante si usa un
insieme di parole in codice
¾ Svantaggi:
¾ Compilazione e trasporto del repertorio
¾ Se cade in mani ostili, ripetizione della
distribuzione
¾ Non molto più sicuro della singola sostituzione
monoalfabetica
Barbara Masucci - DIA – Università di Salerno
ÕÑ®
¾ Si abbassano le frequenze dei simboli del testo cifrato
Aumento frequenze dei corrispondenti simboli
Barbara Masucci - DIA – Università di Salerno
E
¾ La liberazione di Maria dalla prigionia in
Inghilterra
¾ L’uccisione di Elisabetta
¾ Una ribellione alla religione protestante
¾Sir Walsingham, segretario di stato, provò che Maria
aveva preso parte alla congiura
26
Barbara Masucci - DIA – Università di Salerno
27
La congiura di Babington
Maria e Babington comunicavano grazie a
¾ Un corriere (Gilbert Gifford)
¾ Un birraio, che nascondeva i messaggi dentro lo zipolo delle
botti di birra
¾ Un cifrario, costituito da
¾ 23 simboli che sostituivano le lettere
¾ Un nomenclatore di 35 simboli, che sostituivano parole o frasi
¾ 4 nulle e un simbolo per le doppie
Gifford consegnava a Walsingham tutti i messaggi, che
venivano decifrati da Thomas Phelippes
¾ Maria firmò la sua condanna a morte rispondendo alla lettera
di Babington
¾ Babington e complici furono arrestati e squartati vivi
¾ Maria fu decapitata l’8 febbraio 1857
28
Barbara Masucci - DIA – Università di Salerno
Cifrario di Playfair
Due approcci:
¾ Utilizzo di cifrature di più lettere per volta
¾ Playfair
¾ Hill
¾ Utilizzo di più alfabeti cifranti
¾ Leon Battista Alberti
¾ Vigenère
Barbara Masucci - DIA – Università di Salerno
29
Cifrario di Playfair
Lettere di ogni coppia diverse
Cifratura multilettera di Playfair
¾ Si introduce un simbolo fittizio
¾Cifra due simboli insieme
¾Utilizza una matrice 5x5
¾ Pallone = pa lx lo ne
Si individuano le due lettere nella matrice
¾Costruita a partire da una parola chiave per
facilità di memorizzazione
M
M O
O N
N A
A R
R
¾I J equivalenti
C
C
E
E
LL
U
U
Barbara Masucci - DIA – Università di Salerno
Oltre la cifratura
monoalfabetica
H
H
F
F
P
P
V
V
Y
Y
G
G
Q
Q
W
W
B
B
IJ
IJ
S
S
X
X
D
D
K
K
T
T
Z
Z
¾ Se individuano un rettangolo
¾ Ciascuna lettera sostituita dalla lettera che si trova nella
stessa riga del rettangolo
¾ Se individuano una colonna
¾ Ciascuna lettera sostituita dalla seguente nella colonna
¾ Se individuano una riga
¾ Ciascuna lettera sostituita dalla seguente nella riga
30
Barbara Masucci - DIA – Università di Salerno
31
Cifrario di Playfair
M
M
C
C
E
E
LL
U
U
O
O
H
H
F
F
P
P
V
V
N
N
Y
Y
G
G
Q
Q
W
W
A
A
B
B
IJ
IJ
S
S
X
X
R
R
D
D
K
K
T
T
Z
Z
M
C
E
L
U
O
H
F
P
V
N
Y
G
Q
W
A
B
IJ
S
X
Cifrario di Playfair
R
D
K
T
Z
testo in chiaro: AT TA CX CO
testo cifrato:
RS SR BU HM
Barbara Masucci - DIA – Università di Salerno
32
Cifrario di Playfair
33
Cifrario di Hill
Cifratura multi-lettera
¾Migliore rispetto alla cifratura
monoalfabetica: 26x26=676 digrammi
¾ m lettere in chiaro successive
¾ m lettere di testo cifrato
¾ Sostituzione data da equazioni lineari
¾Ma la struttura del testo rimane!
¾Analisi condotta in base alla frequenza
dei digrammi più comuni nella lingua
Per m=3 la cifratura è
¾ c1=(k11p1+ k12p2+ k13p3) mod 26
¾ c2=(k21p1+ k22p2+ k23p3) mod 26
¾ c3=(k31p1+ k32p2+ k33p3) mod 26
¾Es. es, er, on, re, el, er, de.
Barbara Masucci - DIA – Università di Salerno
Barbara Masucci - DIA – Università di Salerno
34
Barbara Masucci - DIA – Università di Salerno
35
Cifrario di Hill
k11 k12 k13
c1
c2 = k12 k22 k23 ×
c3
k13 k32 k33
Cifrario di Hill
p1
p2 mod 26
p3
m=3, primi 3 caratteri
¾ PAY = (15, 0, 24)
c1
15
17 17 5
c2 = 21 18 21 × 0 mod 26
24
c3
2 2 19
La chiave K è la matrice dei coefficienti k
Es. P=PAYMOREMONEY
Chiave
17 17 5
21 18 21
2 2 19
¾ Testo cifrato: (11,13,18) = LNS
Testo cifrato completo: LNSHDLEWMTRW
36
Barbara Masucci - DIA – Università di Salerno
Cifrario di Hill
Come per Playfair la cifratura di Hill
¾ Nasconde le frequenze delle singole lettere
¾ Quindi K deve essere invertibile
K=
K-1=
4 9 15
15 17 6
24 0 17
p1
k’11 k’12 k’13
p2 = k’12 k’22 k’23 ×
p3
k’13 k’32 k’33
Barbara Masucci - DIA – Università di Salerno
37
Cifrario di Hill
Per la decifratura si usa la matrice inversa
17 17 5
21 18 21
2 2 19
Barbara Masucci - DIA – Università di Salerno
Attacchi possibili
c1
c2 mod 26
c3
38
¾ Se si conoscono m coppie testo in chiaro/cifrato
¾ Si riesce a recuperare la chiave!
Barbara Masucci - DIA – Università di Salerno
39
Cifrario di Vigenère
Cifrario di Alberti
Blaise de Vigenère, 1586
¾ Usa più alfabeti cifranti e li sostituisce
durante la cifratura
Cifrario a sostituzione polialfabetica
testo in chiaro
M = M0M1M2…Mn
Alfabeto
piano
I Alfabeto
cifrante
CCi ←
M +K
mod 26
i ← Mi i +Ki imod
modt t mod 26
testo cifrato
C = C0C1C2…Cn
chiave K = K0K1K2…Kt-1
A B C D E F G H I L M N O P Q R S T U V ZZ
E U F A V O D N P H S G T M I L B R Z C QQ
C M U N B I P L OV A T G S D R H Q F Z E
II Alfabeto
cifrante
Leone
hbttv
40
Barbara Masucci - DIA – Università di Salerno
Cifrario di Vigenère
A B C
B C D
C D E
D E F
E F G
F G H
G H I
H I J
I J K
J K L
K L M
L M N
M N O
N O P
O P Q
P Q R
Q R S
R S T
S T U
T U V
U V W
V W X
W X Y
X Y Z
Y Z A
Z A B
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
G H I J K L M
H I J K L M N
I J K LM N O
J K L MN O P
K L M NOP Q
L M NOP Q R
M N OP QR S
N O P QR S T
O P QRS T U
P Q R S T U V
Q R S TU V W
R S T UVW X
S T U VW X Y
T U VWX Y Z
U V W XY ZA
V W X Y Z A B
W X Y ZA B C
X Y Z AB CD
Y Z A B C D E
Z A B CD E F
A B C DE F G
B C D EF G H
C D E FG HI
D E F GH I J
E F G HI J K
F G H I J K L
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
O P
P Q
Q R
R S
S T
T U
U V
V W
W X
X Y
Y Z
Z A
A B
B C
C D
D E
E F
F G
G H
H I
I J
J K
K L
L M
M N
N O
Q R S T U V
R S T U V W
S T U VW X
T U V W X Y
U V W X Y Z
V W X Y Z A
W X Y ZA B
X Y Z A B C
Y Z A B C D
Z A B CD E
A B C D E F
B C D E F G
C D E F G H
D E F G H I
E F G HI J
F G H I J K
G H I J K L
H I J K L M
I J K L M N
J K L M N O
K L M NO P
L M N OP Q
M N O P QR
N O P QR S
O P QR S T
P QR S T U
Barbara Masucci - DIA – Università di Salerno
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
X Y
Y Z
Z A
A B
B C
C D
D E
E F
F G
G H
H I
I J
J K
K L
L M
M N
N O
O P
P Q
QR
R S
S T
T U
U V
V W
WX
Testo in chiaro: CODICE MOLTO SICURO
Chiave: REBUS
CODIC EMOLT OSICU RO testo in chiaro
REBUS REBUS REBUS RE chiave
TSECU VQPFL FWJWM IS testo cifrato
Barbara Masucci - DIA – Università di Salerno
41
Cifrario di Vigenère
Z
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
42
Barbara Masucci - DIA – Università di Salerno
43
Cifrario di Vigenère
Un cifrario perfetto
One-time pad, Gilbert Vernam, impiegato AT&T, 1917
¾ Considerato inviolabile per molto tempo
¾ Numero possibili chiavi =
26t
testo in chiaro
¾ Resiste all’analisi delle frequenze
¾ Una lettera cifrata corrisponde a più simboli in chiaro
M = M0M1M2…Mn
¾ Babbage (1834) e Kasiski (1863) furono i primi a
cimentarsi nella crittoanalisi
C = C0C1C2…Cn
(bit indipendenti e casuali)
Esempio:
44
One-time Pad
1 0 0 1 0 1 1 1 0 1 1 0 testo in chiaro
0 0 1 1 1 0 1 0 1 0 1 0 chiave
1 0 1 0 1 1 0 1 1 1 0 0 testo cifrato
Barbara Masucci - DIA – Università di Salerno
45
One-time Pad
Unconditionally secure
¾Indipendentemente dal tempo e dalle risorse
a disposizione è impossibile decifrare il testo
cifrato
¾Esaminando tutte le chiavi possibili
otteniamo anche tutti i messaggi possibili!
¾La casualità della chiave non ci consente di
distinguere tra i messaggi ottenuti
Barbara Masucci - DIA – Università di Salerno
testo cifrato
chiave K = K0K1K2…Kn
¾ Studio delle ripetizioni per individuare la lunghezza della
chiave
¾ Analisi delle frequenze in ognuno degli alfabeti cifranti
corrispondenti alle lettere della chiave
Barbara Masucci - DIA – Università di Salerno
C
Cii ←
←M
Mii⊕K
⊕Kii
46
1. Supponiamo che il messaggio
attaccarelavalleallalba sia cifrato con la
chiave efthjzcokmflwpaqhctrows
2. Ad esempio, esiste una chiave che
trasforma il testo cifrato nel messaggio
abbandonarevalleallalba
3. Trovatela!
Barbara Masucci - DIA – Università di Salerno
47
One-time Pad
testo in chiaro
M = M0M1M2…Mn
C
Cii ←
←M
Mii⊕K
⊕Kii
Crittografia e Letteratura
¾Jules Verne (1828-1905), “Mathias Sandorf”
¾ messaggio cifrato dal conte Sandorf, coinvolto in una
cospirazione anti-austriaca
testo cifrato
C = C0C1C2…Cn
¾Edgar Allan Poe (1809-1849), “Lo Scarabeo d‘Oro”
¾ messaggio cifrato dal pirata Capitano Kidd, dice dove è
nascosto il tesoro
chiave K = K0K1K2…Kn
(bit indipendenti e casuali)
¾Dan Brown, “Il Codice Da Vinci”
cifrario perfetto: M e C sono indipendenti
Prob (M=M´) = Prob (M=M´ |C=C´)
¾ O, Draconian Devil! Oh Lame Saint!
(Leonardo Da Vinci! The Mona Lisa!)
¾Ian Caldwell, Thomas Dustin “Il Codice del Quattro”
lunghezza chiave = lunghezza testo in chiaro
Barbara Masucci - DIA – Università di Salerno
¾ Steganografia e crittografia all’interno di un antico testo
48
I crittogrammi Beale
Nel 1822 Beale affidò a Morris una scatola chiusa a
chiave chiedendogli di custodirla
¾ La scatola conteneva documenti cifrati
Thomas Beale, avventuriero del selvaggio West
Robert Morris, gestore di un hotel di Lynchburg
Un tesoro sepolto del valore di 20 milioni di dollari
Tre crittogrammi
Un opuscolo pubblicato nel 1885
Barbara Masucci - DIA – Università di Salerno
49
I crittogrammi Beale
La vicenda inizia nel 1822 a Lynchburg, Virginia
Protagonisti:
¾
¾
¾
¾
¾
Barbara Masucci - DIA – Università di Salerno
Se Beale non fosse tornato entro 10 anni, Morris
avrebbe dovuto aprirla
¾ La chiave necessaria alla decifratura sarebbe stata
recapitata a Morris nel 1832
50
Barbara Masucci - DIA – Università di Salerno
51
I crittogrammi Beale
I crittogrammi Beale
Beale non tornò mai e Morris non ricevette la
chiave di decifratura
Nel 1845 Morris aprì la scatola
¾Morris tentò per 20 anni di decifrare i crittogrammi,
senza successo
¾Nel 1862 mostrò i crittogrammi ad un amico che, dopo
aver decifrato il secondo, pubblicò un opuscolo nel 1885
¾Il secondo crittogramma fu decifrato usando come
chiave la dichiarazione di indipendenza
¾ All’interno c’erano tre crittogrammi e una lettera per
Morris
¾ La lettera svelò che Beale aveva scoperto un
giacimento d’oro
¾ I tre crittogrammi indicavano
¾ l’ammontare del tesoro
¾ la sua ubicazione
¾ la ripartizione del tesoro tra gli eredi
52
Barbara Masucci - DIA – Università di Salerno
Barbara Masucci - DIA – Università di Salerno
53
Il secondo crittogramma
I crittogrammi Beale
L’opuscolo
Barbara Masucci - DIA – Università di Salerno
115, 73, 24, 807, 37, 52, 49, 17, 31, 62, 647, 22, 7, 15, 140, 47, 29, 107, 79, 84, 56, 239,
10, 26, 811, 5, 196, 308, 85, 52, 160, 136, 59, 211, 36, 9, 46, 316, 554, 122, 106, 95, 53, 58, 2, 42, 7,
35, 122, 53, 31, 82, 77, 250, 196, 56, 96, 118, 71, 140, 287, 28, 353, 37, 1005, 65, 147, 807, 24, 3, 8,
12, 47, 43, 59, 807, 45, 316, 101, 41, 78, 154, 1005, 122, 138, 191, 16, 77, 49, 102, 57, 72, 34, 73, 85,
35, 371, 59, 196, 81, 92, 191, 106, 273, 60, 394, 620, 270, 220, 106, 388, 287, 63, 3, 6, 191, 122, 43,
234, 400, 106, 290, 314, 47, 48, 81, 96, 26, 115, 92, 158, 191, 110, 77, 85, 197, 46, 10, 113, 140, 353,
48, 120, 106, 2, 607, 61, 420, 811, 29, 125, 14, 20, 37, 105, 28, 248, 16, 159, 7, 35, 19, 301, 125, 110,
486, 287, 98, 117, 511, 62, 51, 220, 37, 113, 140, 807, 138, 540, 8, 44, 287, 388, 117, 18, 79, 344, 34,
20, 59, 511, 548, 107, 603, 220, 7, 66, 154, 41, 20, 50, 6, 575, 122, 154, 248, 110, 61, 52, 33, 30, 5,
38, 8, 14, 84, 57, 540, 217, 115, 71, 29, 84, 63, 43, 131, 29, 138, 47, 73, 239, 540, 52, 53, 79, 118, 51,
44, 63, 196, 12, 239, 112, 3, 49, 79, 353, 105, 56, 371, 557, 211, 505, 125, 360, 133, 143, 101, 15,
284, 540, 252, 14, 205, 140, 344, 26, 811, 138, 115, 48, 73, 34, 205, 316, 607, 63, 220, 7, 52, 150,
44, 52, 16, 40, 37, 158, 807, 37, 121, 12, 95, 10, 15, 35, 12, 131, 62, 115, 102, 807, 49, 53, 135, 138,
30, 31, 62, 67, 41, 85, 63, 10, 106, 807, 138, 8, 113, 20, 32, 33, 37, 353, 287, 140, 47, 85, 50, 37, 49,
47, 64, 6, 7, 71, 33, 4, 43, 47, 63, 1, 27, 600, 208, 230, 15, 191, 246, 85, 94, 511, 2, 270, 20, 39, 7,
33, 44, 22, 40, 7, 10, 3, 811, 106, 44, 486, 230, 353, 211, 200, 31, 10, 38, 140, 297, 61, 603, 320,
302, 666, 287, 2, 44, 33, 32, 511, 548, 10, 6, 250, 557, 246, 53, 37, 52, 83, 47, 320, 38, 33, 807, 7,
44, 30, 31, 250, 10, 15, 35, 106, 160, 113, 31, 102, 406, 230, 540, 320, 29, 66, 33, 101, 807, 138, 301,
316, 353, 320, 220, 37, 52, 28, 540, 320, 33, 8, 48, 107, 50, 811, 7, 2, 113, 73, 16, 125, 11, 110, 67,
102, 807, 33, 59, 81, 158, 38, 43, 581, 138, 19, 85, 400, 38, 43, 77, 14, 27, 8, 47, 138, 63, 140, 44,
35, 22, 177, 106, 250, 314, 217, 2, 10, 7, 1005, 4, 20, 25, 44, 48…
Un crittogramma
54
Barbara Masucci - DIA – Università di Salerno
55
La chiave
Il crittogramma decifrato
DECLARATION OF INDEPENDENCE
When(1) in(2) the(3) course(4) of(5) human(6) events(7) it(8)
becomes(9) necessary(10) for(11) one(12) people(13) to(14) dissolve(15) the(16)
political(17) bands(18) which(19) have(20) connected(21) them(22) with(23)
another(24) and(25) to(26) assume(27) among(28) the(29) powers(30) of(31)
the(32) earth(33) the(34) separate(35) and(36) equal(37) station(38) to(39)
which(40) the(41) laws(42) of(43) nature(44) and(45) of(46) nature's(47) god(48)
entitle(49) them(50) a(51) decent(52) respect(53) to(54) the(55) opinions(56)
of(57) mankind(58) requires(59) that(60) they(61) should(62) declare(63) the(64)
causes(65) which(66) impel(67) them(68) to(69) the(70) separation(71) we(72)
hold(73) these(74) truths(75) to(76) be(77) self(78) evident(79) that(80) all(81)
men(82) are(83) created(84) equal(85) that(86) they(87) are(88) endowed(89)
by(90) their(91) creator(92) with(93) certain(94) unalienable(95) rights(96)
that(97) among(98) these(99) are(100) life(101) liberty(102) and(103) the(104)
pursuit(105) of(106) happiness(107) that(108) to(109) secure(110) these(111)
rights(112) governments(113) are(114) instituted(115) among(116) men(117) …
Barbara Masucci - DIA – Università di Salerno
56
Barbara Masucci - DIA – Università di Salerno
57
Il telegramma di
Zimmermann
I crittogrammi Beale
¾Il primo e il terzo crittogramma di Beale sono inviolati
da più di un secolo
¾ I crittogrammi potrebbero essere stati alterati dall’autore
dell’opuscolo per impedirne la decifratura
¾E il tesoro?
¾ Qualcuno potrebbe averlo trovato utilizzando gli indizi
dell’unico crittogramma decifrato
¾L’intera storia potrebbe essere una montatura, ispirata
dal romanzo di Edgar Allan Poe
¾Ancora oggi crittoanalisti e cacciatori di tesori sono
affascinati dalla vicenda
Barbara Masucci - DIA – Università di Salerno
" I have deposited in the county of Bedford, (Virginia) about four miles
from Buford, in an excavation or vault, six feet below the surface of
the ground, the following articles belonging jointly to the parties whose
names are given in number three herewith. The first deposit consisted
of ten hundred and fourteen pounds of gold and thirty eight hundred
and twelve pounds of silver deposited Nov. Eighteen Nineteen. The
second was made Dec. Eighteen Twenty one and consisted of nineteen
hundred and eighty eight of silver, also jewels obtained in St. Louis in
exchange to save transportation and valued at thirteen thousand
dollars. The above is securely packed in iron pots with iron covers the
vault is roughly lined with stone and the vessels rest on solid stone and
are covered with others. Paper number one describes the exact locality
of the vault so that no difficulty will be had in finding it."
58
¾La decifrazione di un
telegramma tedesco,
intercettato dagli inglesi nel
1917, influì sul corso della
storia
¾Il telegramma spinse gli
Stati Uniti a riconsiderare la
loro politica di neutralità
Barbara Masucci - DIA – Università di Salerno
59
Il telegramma di
Zimmermann
Il telegramma di Zimmerman
¾La Germania voleva evitare che gli USA prendessero
le difese della Gran Bretagna
¾Zimmermann, mediante un telegramma cifrato,
propose al Messico e al Giappone di attaccare gli USA
¾Il telegramma fu intercettato dalla Gran Bretagna e
decifrato dai suoi crittoanalisti
¾In seguito alla visione del telegramma, gli USA
decisero di entrare in guerra
Barbara Masucci - DIA – Università di Salerno
60
61
Barbara Masucci - DIA – Università di Salerno
Rotori
Macchine cifranti
Cifratura
Costruiti a partire dal 1918
¾ richiede tempo
¾ ripeterla aumenta il tempo
Meccanizzazione
¾ Disco di Alberti (1400)
¾ Cilindri cifranti (1600)
¾ Cilindri di Thomas Jefferson
testo in chiaro
A
B
C
D
¾ 3° presidente Stati Uniti (1800)
¾ 36 dischi di legno
¾ Ordine dischi: 36!
¾ Ognuno 26 posizioni
Barbara Masucci - DIA – Università di Salerno
62
...
Barbara Masucci - DIA – Università di Salerno
C
B
D
A
testo cifrato
63
Rotori
Rotori
Posizione dopo
un input
¾ Ogni cilindro opera una sostituzione
monoalfabetica
¾ Facile mettere più cilindri in cascata
¾ Rotori
¾ I cilindri ruotano
¾ Quello più destra ad ogni lettera cifrata
¾ Il secondo dopo 26 rotazioni del primo
¾ Il terzo dopo 26 rotazioni del secondo
¾ … come un contachilometri
Barbara Masucci - DIA – Università di Salerno
64
Rotori
Barbara Masucci - DIA – Università di Salerno
65
Enigma
¾ Con tre rotori: 263 = 17.576 diversi alfabeti cifranti
II Guerra Mondiale
¾ Si possono aggiungere altri rotori
¾ 4 rotori: 264=456.976
¾ 5 rotori: 265=11.881.376
Caratteristiche:
¾ 3 rotori
¾ Pannello a prese
multiple
¾ Involuzione
¾ Debolezza del cifrario di Vigenère
¾ Pochi alfabeti cifranti usati in ciclo
¾ Rotori: ciclo di sostituzione non si ripete quasi mai
¾ Occorrerebbero dei testi di lunghezza enorme
¾ Del tipo un intera enciclopedia con decine di volumi ciascuno con
migliaia di pagine
Barbara Masucci - DIA – Università di Salerno
66
Barbara Masucci - DIA – Università di Salerno
67
Enigma
Le chiavi di Enigma
Rotori o scambiatori:
¾ 26x26x26=17576 combinazioni possibili
Unità cifrante:
¾ I tre rotori (1,2,3) potevano essere inseriti in 6 diverse
posizioni: 123, 132, 213, 231, 312, 321
Pannello a prese multiple:
testo in chiaro
A
B
testo cifrato C
D
Barbara Masucci - DIA – Università di Salerno
involuzione
¾ Gli abbinamenti di 6x2 lettere sono 100.391.791.500
68
Numero di chiavi totali: 10 milioni di miliardi…
Barbara Masucci - DIA – Università di Salerno
Chiave giornaliera
1.
2.
¾Punti deboli di Enigma
Es. A/L – P/R – T/D – B/W – K/F – O/Y
¾ Nessuna lettera cifra se stessa
¾ Una lettera non cifra lettere contigue
¾ Utilizzo di cillies, chiavi semplici
Disposizione dei rotori
¾
3.
Enigma
Assetto del pannello
¾
1 -3 – 2
Orientamento dei rotori
¾
¾ qweqwe
Q–C–W
Per maggiore sicurezza si utilizza una chiave di messaggio:
¾
¾
¾
¾
Es chiave giornaliera QCW
Chiave messaggio PGH, ripetuta PGHPGH
Cifratura di PGHPGH tramite QCW, Æ KIVBJE
Cifratura e trasmissione del messaggio tramite PGH
Barbara Masucci - DIA – Università di Salerno
69
¾ Se L1 cifra L2 allora L2 cifra L1
¾ Invio della posizione iniziale rotori
¾Crittoanalisi possibile
¾ Creazione di “bombe” (Turing)
70
Barbara Masucci - DIA – Università di Salerno
71
Bibliografia
Enigma
¾Cryptography: Theory and Practice,
by D. Stinson (1995)
¾ cap. 1
¾Cryptography and Network Security
by W. Stallings (2003)
¾ cap. 2
¾Tesina su crittografia classica
¾ http://www.dia.unisa.it/professori/ads/
¾ Sicurezza su reti, a.a. 1995-1996
Barbara Masucci - DIA – Università di Salerno
72
Bibliografia
73
Bibliografia
David Kahn,
The codebreakers: the Story of Secret
Writing
Macmillan, New York 1967
Simon & Schuster Trade
1200 pp., October 1996
Simon Singh,
Codici & Segreti
Rizzoli ed., 1999
Barbara Masucci - DIA – Università di Salerno
Barbara Masucci - DIA – Università di Salerno
74
Barbara Masucci - DIA – Università di Salerno
75