•Corso di Sicurezza su reti
•Lezione del 2 marzo 2004
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: Esempi
Steganografia: Esempi
Erodoto (Histories):
Erodoto (Histories):
Demerato in esilio avvisa gli spartani del
progetto di invasione da parte di Serse, re dei Persiani
Istieo incoraggia Aristagora di Mileto a ribellarsi
a Serse
Espediente dello schiavo, sul cui capo
rasato è stato tatuato un messaggio
Espediente della tavoletta di cera
Gorgo, sorella di Cleomenes e moglie di Leonidas (re
Dopo la crescita dei capelli, il corriere viene
spartano) scoprì la presenza del messaggio ...
Barbara Masucci - DIA – Università di Salerno
inviato da Aristagora
2
Barbara Masucci - DIA – Università di Salerno
3
Steganografia: Problemi
Steganografia: Esempi
¾ Cina
¾ Se il corriere è attentamente perquisito il
messaggio può essere scoperto
¾ Messaggi dipinti su striscioline di seta,
appallottolate, ricoperte di cera e inghiottite dal
corriere
¾ Raschiando tavolette di cera
¾ Rasando il capo al corriere
¾ Sbucciando le uova
¾…
¾ Plinio il vecchio
¾ Comunicazione mediante inchiostro simpatico
ottenuto dal lattice di titimabo
La segretezza è perduta al momento
dell’intercettazione
¾ Gian Battista Porta
¾ Comunicazione mediante uovo sodo e una sorta di
“inchiostro simpatico”
Barbara Masucci - DIA – Università di Salerno
1
4
Barbara Masucci - DIA – Università di Salerno
5
•1
•Corso di Sicurezza su reti
•Lezione del 2 marzo 2004
Crittografia
Crittografia
Trasformazione
+
Segretezza
Dall’antichità fino a pochi anni fa:
¾ Essenzialmente comunicazioni private
¾ Usi Militari e Diplomatici
χρυπτοσ
Crittografia
γραφια
λογοσ
Oggi: studio di tecniche ed applicazioni che
Cryptos = segreto
dipendono dall’esistenza di problemi difficili
Grafien = scrittura
6
Barbara Masucci - DIA – Università di Salerno
Scritture segrete
7
Barbara Masucci - DIA – Università di Salerno
Cifrari simmetrici
Trasformazione delle parole per renderne
incomprensibile il significato
Città di Menet Khufu (Nilo), 4000 anni fa
Incisione funebre (geroglifico)
scopo trasformazione:
conferire dignità e
onoreficenza al defunto
Alice
canale insicuro
Altre trasformazioni, scopo:
– mistero
– senso dell’arcano
– conferire potere magico alle parole
8
Barbara Masucci - DIA – Università di Salerno
Cifrari simmetrici
9
Metodi antichi di cifratura
Algoritmo di
decifratura
m
Bob
Barbara Masucci - DIA – Università di Salerno
¾ Erodoto
¾ Scytala spartana, 500 a.C. (Plutarco in Vite parallele)
¾ Polibio, 118 a.C. (Libro X delle Storie)
m
1
2
3
4
5
Alice
canale insicuro
Algoritmo di
cifratura
Barbara Masucci - DIA – Università di Salerno
1
A
F
L
Q
V
2
B
G
M
R
W
3
C
H
N
S
X
4
D
IJ
O
T
Y
5
E
K
P
U
Z
testo in chiaro:
testo cifrato:
Bob
10
C
A
S
A
(1,3) (1,1) (4,3) (1,1)
Barbara Masucci - DIA – Università di Salerno
11
•2
•Corso di Sicurezza su reti
•Lezione del 2 marzo 2004
Cifrario di Cesare
Metodi antichi di cifratura
100100-44 a.C.
Bibbia: tre tipi di cifratura
Svetonio (Vitae Caesarorum): lettera di Cesare a Cicerone
¾ Atbash: alfabeto rovesciato (Aleph, taw, beth, shin)
cifratura di “Babilonia” nel libro di Geremia
¾ Albam: alfabeto diviso in due metà
¾ Atbah: relazione numerica
per le prime nove:
lettera da sostituire + lettera sostituente = 10
per le rimanenti:
lettera da sostituire + lettera sostituente = 28
12
Barbara Masucci - DIA – Università di Salerno
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
X ← M+3 mod 26
OMNIA GALLIA EST DIVISA IN PARTES TRES
RPQLD JDOOLD HVW GLYLVD LQ SDUWHV WUHV
testo cifrato
Cifrari a sostituzione
monoalfabetica
Cifrari con shift
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
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
Cifrari con shift
Chiave K
testo in chiaro:
testo cifrato:
X ← M+K mod 26
13
Barbara Masucci - DIA – Università di Salerno
C
T
A
O
S
P
A
O
K∈{0,1,…,25}
¾ 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
Quante chiavi sono possibili?
Improponibile!
14
Barbara Masucci - DIA – Università di Salerno
Analisi statistica
Frequenze occorrenze lettere
¾ Ogni lettera cambia “abito”, ma conserva la sua
“identità”
14
12
¾ Frequenza
¾ Vicinanza con altre lettere (q è sempre seguita da u,…)
¾ Altre regole (mai due vocali di seguito,…)
10
8
le
6
¾ Calcolo della frequenza relativa delle lettere nel cifrato
¾ Confronto con la distribuzione standard delle frequenze per
quel linguaggio
2
¾ Il cifrario può essere
regolarità del linguaggio
rotto
Barbara Masucci - DIA – Università di Salerno
considerando
15
Barbara Masucci - DIA – Università di Salerno
4
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
16
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
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
Barbara Masucci - DIA – Università di Salerno
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
Y
0,0
2,3
0,8
Z
0,9
0,3
0,0
17
•3
•Corso di Sicurezza su reti
•Lezione del 2 marzo 2004
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
18
Nomenclatori
ÕÑ®
Barbara Masucci - DIA – Università di Salerno
19
¾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
¾ Compilazione e trasporto del repertorio
¾ Se cade in mani ostili, ripetizione della
distribuzione
¾ Non molto più sicuro della singola sostituzione
monoalfabetica
¾ La liberazione di Maria dalla prigionia in
Inghilterra
¾ L’uccisione di Elisabetta
¾ Una ribellione alla religione protestante
¾Sir Francis Walsingham, segretario di
stato, provò che Maria aveva preso parte
alla congiura
20
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
Barbara Masucci - DIA – Università di Salerno
3.15 per
La congiura di Babington
¾ In aggiunta all’alfabeto cifrante si usa un
insieme di parole in codice
¾ Svantaggi:
Barbara Masucci - DIA – Università di Salerno
(scelti a caso!)
¾ Si abbassano le frequenze dei simboli del testo cifrato
Aumento frequenze dei corrispondenti simboli
Barbara Masucci - DIA – Università di Salerno
E
ÕÑ®
22
Barbara Masucci - DIA – Università di Salerno
21
Oltre la cifratura
monoalfabetica
Due approcci:
¾ Utilizzo di più alfabeti cifranti
¾ Leon Battista Alberti
¾ Vigenère
¾ Utilizzo di cifrature di più lettere per volta
¾ Porta
¾ Playfair
Barbara Masucci - DIA – Università di Salerno
23
•4
•Corso di Sicurezza su reti
•Lezione del 2 marzo 2004
Disco di Alberti
Leon Battista Alberti
Leon Battista Alberti,
Proposta di usare più alfabeti cifranti e di
sostituirli durante la cifratura
architetto italiano, XV secolo
testo in chiaro
Alfabeto
piano
I Alfabeto
cifrante
II Alfabeto
cifrante
Leone
hbttv
Cifrario di Porta
Giovanni Battista Porta,
A
0
26
52
78
104
130
156
182
208
234
260
286
312
338
364
390
416
442
468
494
520
546
572
598
624
650
B
1
27
53
79
105
131
157
183
209
235
261
287
313
339
365
391
417
443
469
495
521
547
573
599
625
651
C
2
28
54
80
106
132
158
184
210
236
262
288
314
340
366
392
418
444
470
496
522
548
574
600
626
652
D
3
29
55
81
107
133
159
185
211
237
263
289
315
341
367
393
419
445
471
497
523
549
575
601
627
653
E
4
30
56
82
108
134
160
186
212
238
264
290
316
342
368
394
420
446
472
498
524
550
576
602
628
654
F
5
31
57
83
109
135
161
187
213
239
265
291
317
343
369
395
421
447
473
499
525
551
577
603
629
655
G
6
32
58
84
110
136
162
188
214
240
266
292
318
344
370
396
422
448
474
500
526
552
578
604
630
656
H
7
33
59
85
111
137
163
189
215
241
267
293
319
345
371
397
423
449
475
501
527
553
579
605
631
657
I
8
34
60
86
112
138
164
190
216
242
268
294
320
346
372
398
424
450
476
502
528
554
580
606
632
658
J
9
35
61
87
113
139
165
191
217
243
269
295
321
347
373
399
425
451
477
503
529
555
581
607
633
659
K
10
36
62
88
114
140
166
192
218
244
270
296
322
348
374
400
426
452
478
504
530
556
582
608
634
660
L
11
37
63
89
115
141
167
193
219
245
271
297
323
349
375
401
427
453
479
505
531
557
583
609
635
661
N
13
39
65
91
117
143
169
195
221
247
273
299
325
351
377
403
429
455
481
507
533
559
585
611
637
663
O
14
40
66
92
118
144
170
196
222
248
274
300
326
352
378
404
430
456
482
508
534
560
586
612
638
664
P
15
41
67
93
119
145
171
197
223
249
275
301
327
353
379
405
431
457
483
509
535
561
587
613
639
665
Q
16
42
68
94
120
146
172
198
224
250
276
302
328
354
380
406
432
458
484
510
536
562
588
614
640
666
R
17
43
69
95
121
147
173
199
225
251
277
303
329
355
381
407
433
459
485
511
537
563
589
615
641
667
S
18
44
70
96
122
148
174
200
226
252
278
304
330
356
382
408
434
460
486
512
538
564
590
616
642
668
T
19
45
71
97
123
149
175
201
227
253
279
305
331
357
383
409
435
461
487
513
539
565
591
617
643
669
U
20
46
72
98
124
150
176
202
228
254
280
306
332
358
384
410
436
462
488
514
540
566
592
618
644
670
Barbara Masucci - DIA – Università di Salerno
25
Barbara Masucci - DIA – Università di Salerno
Cifrario di Porta
primo cifrario per digrammi [1563]
M
12
38
64
90
116
142
168
194
220
246
272
298
324
350
376
402
428
454
480
506
532
558
584
610
636
662
testo cifrato con
rotazione “AL”
Utilizzato nella guerra di secessione
24
Barbara Masucci - DIA – Università di Salerno
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
DI S CO
U B X MG
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
V
21
47
73
99
125
151
177
203
229
255
281
307
333
359
385
411
437
463
489
515
541
567
593
619
645
671
W
22
48
74
100
126
152
178
204
230
256
282
308
334
360
386
412
438
464
490
516
542
568
594
620
646
672
X
23
49
75
101
127
153
179
205
231
257
283
309
335
361
387
413
439
465
491
517
543
569
595
621
647
673
Y
24
50
76
102
128
154
180
206
232
258
284
310
336
362
388
414
440
466
492
518
544
570
596
622
648
674
Z
25
51
77
103
129
155
181
207
233
259
285
311
337
363
389
415
441
467
493
519
545
571
597
623
649
675
testo in chiaro:
testo cifrato:
DO
92
MA NI
312 346
Chiave: permutazione arbitraria di:
¾ numeri del cifrato
¾ lettere su righe e colonne
Uso di caratteri speciali per alfabeto testo cifrato
26
Cifrario di Porta
27
Barbara Masucci - DIA – Università di Salerno
Cifrario di Vigenère
Blaise de Vigenère, 1586
Cifrario a sostituzione polialfabetica
testo in chiaro
M = M0M1M2…Mn
Ci ← Mi +Ki mod t mod 26
testo cifrato
C = C0C1C2…Cn
chiave K = K0K1K2…Kt-1
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
28
Barbara Masucci - DIA – Università di Salerno
29
•5
•Corso di Sicurezza su reti
•Lezione del 2 marzo 2004
Cifrario di Vigenère
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
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
Q R
R S
S T
T U
U V
V W
W X
X Y
Y Z
Z A
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
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
H I J K L M
I J K L M N
J K LM N O
K L MN O P
L M NO P Q
M NOP Q R
N O P Q R S
O P QR S T
P Q RS T U
Q R S T U V
R S TU V W
S T UVW X
T U VW X Y
U VWX Y Z
V W XY ZA
W X Y Z A B
X Y ZA B C
Y Z AB CD
Z A B C D E
A B CD E F
B C DE F G
C D EF G H
D E FG HI
E F GH I J
F G HI J K
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
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
P
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
Q
R
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
R S T U V
S T U V W
T U VW X
U V W X Y
V W X Y Z
W X Y Z A
X Y Z A B
Y Z A B C
Z A B C D
A B CD E
B C D E F
C D E F G
D E F G H
E F G H I
F G HI J
G H I J K
H I J K L
I J K L M
J K L M N
K L M N O
L M NO P
M N O P Q
N O P QR
O P Q R S
P QR S T
Q R S T U
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
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
Barbara Masucci - DIA – Università di Salerno
Cifrario a sostituzione polialfabetica
testo in chiaro
M = M0M1M2…Mn
Ci ← Mi +Ki mod t mod 26
testo cifrato
C = C0C1C2…Cn
chiave K = K0K1K2…Kt-1
¾ Considerato inviolabile per molto tempo
t
¾ Numero possibili chiavi = 26
30
Barbara Masucci - DIA – Università di Salerno
31
Educational Tools for
Cryptography
Cifrario di Vigenère
¾ http://www.cs.newcastle.edu.au/Research/DSG/
¾ etc.zip, 270 KB, luglio 1999
¾ Resiste all’analisi delle frequenze
¾ Una lettera cifrata corrisponde a più simboli in chiaro
¾ Esiste un numero grande di chiavi
¾Autore: Andrew White
¾Windows
¾Cifrari a sostituzione, con shift, Vigenere,
analisi statistica
¾ Babbage (1834) e Kasiski (1863) furono i primi a
cimentarsi nella crittoanalisi
¾ 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
32
Barbara Masucci - DIA – Università di Salerno
ETC
33
Griglie
Girolamo Cardano, XVI secolo
N
Z
L
I
O
Barbara Masucci - DIA – Università di Salerno
34
E
Z
C
N
S
L
O
A
D
T
M
D
M
I
R
E
E
M
N
A
Barbara Masucci - DIA – Università di Salerno
35
•6
•Corso di Sicurezza su reti
•Lezione del 2 marzo 2004
Griglie
Griglie con rotazioni
¾ Usato dalla Germania poco prima della fine della I Guerra Mondiale
¾ Quadrato invariante per rotazioni di 90° con 4 occorrenze di 1,…,9
¾ Un solo quadrato per ogni intero
Girolamo Cardano, XVI secolo
N
Z
L
I
O
E
Z
C
N
S
L
O
A
D
T
M
D
M
I
R
E
E
M
N
A
5
9
8
7
6
5
36
Barbara Masucci - DIA – Università di Salerno
5
9
8
7
6
5
6
2
4
3
2
9
7
3
1
1
4
8
8
4
1
1
3
7
di 90°
9
2
3
4
2
6
griglia ruotata
griglia ruotata
8
4
1
1
3
7
9
2
3
4
2
6
5
6
7
8
9
5
37
Griglie con rotazioni
di 180°
di 270°
A
T
D
C
C
G
5
6
7
8
9
5
Barbara Masucci - DIA – Università di Salerno
7
3
1
1
4
8
Barbara Masucci - DIA – Università di Salerno
Griglie con rotazioni
griglia
griglia ruotata
6
2
4
3
2
9
A
M
O
O
M
I
A
E
A
Z
H
I
R
N
M
N
A
I
M
T
A
Z
N
O
O
O
C
O
I
L
griglia
griglia ruotata
di 90°
griglia ruotata
di 180°
griglia ruotata
di 270°
testo cifrato: AAARMOTMENTODOAMACCOZNZOCMHANIGIIIOL
testo in chiaro: ATTACCHIAMODOMANIAMEZZOGIORNOCONMIL
38
Barbara Masucci - DIA – Università di Salerno
39
I crittogrammi Beale
Crittografia e Letteratura
La vicenda inizia nel 1822 a Lynchburg, Virginia
Protagonisti:
¾ Jules Verne, “Viaggio al centro della Terra”
¾ decifrazione di una pergamena con caratteri runici
¾
¾
¾
¾
¾
¾ Edgar Allan Poe, “Lo scarabeo d'oro” (1843)
¾ messaggio scritto dal pirata Capitano Kidd, dice dove è
nascosto il tesoro
5 3 I I I 3 0 5 ) ) 6* ;48 26)4 I . ) 4 I );80 6*
A GOOD GLASS IN THE BISHOP`S HOSTEL IN
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
; 48 I8E60 ) ) 85 ; II ( ; : I *8 I 83(88 ) 5* I
THE DEVIL`S SEAT FORTY-ONE DEGREES AND
Barbara Masucci - DIA – Università di Salerno
40
Barbara Masucci - DIA – Università di Salerno
41
•7
•Corso di Sicurezza su reti
•Lezione del 2 marzo 2004
I crittogrammi Beale
I crittogrammi Beale
Nel 1822 Beale affidò a Morris una scatola chiusa a
chiave chiedendogli di custodirla
Beale non tornò mai e Morris non ricevette la
chiave di decifratura
Nel 1845 Morris aprì la scatola
¾ La scatola conteneva documenti cifrati
Se Beale non fosse tornato entro 10 anni, Morris
avrebbe dovuto aprirla
¾ 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
¾ La chiave necessaria alla decifratura sarebbe stata
recapitata a Morris nel 1832
¾ l’ammontare del tesoro
¾ la sua ubicazione
¾ la ripartizione del tesoro tra gli eredi
Barbara Masucci - DIA – Università di Salerno
42
I crittogrammi Beale
43
Barbara Masucci - DIA – Università di Salerno
I crittogrammi Beale
¾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
L’opuscolo
Barbara Masucci - DIA – Università di Salerno
44
Il secondo crittogramma
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…
Barbara Masucci - DIA – Università di Salerno
46
Un crittogramma
Barbara Masucci - DIA – Università di Salerno
45
La chiave
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
47
•8
•Corso di Sicurezza su reti
•Lezione del 2 marzo 2004
Il crittogramma decifrato
¾Il primo e il terzo crittogramma di Beale sono inviolati
da più di un secolo
" 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."
Barbara Masucci - DIA – Università di Salerno
I crittogrammi Beale
¾ 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
48
Cifrario di Playfair
Cifrario di Playfair
Progettato da Charles Wheatstone buon amico del
Barone Lyon Playfair, XIX secolo
M
C
E
L
U
O
H
F
P
V
N
Y
G
Q
W
A
B
IJ
S
X
R
D
K
T
Z
M
C
E
L
U
Cifrario usato dai britannici.
Anche dall’Australia durante
la II guerra mondiale.
Anche rettangoli 4x7, 4x8,…
Barbara Masucci - DIA – Università di Salerno
50
O
H
F
P
V
N
Y
G
Q
W
A
B
IJ
S
X
R
D
K
T
Z
M
C
E
L
U
O
H
F
P
V
N
Y
G
Q
W
A
B
IJ
S
X
R
D
K
T
Z
testo in chiaro: AT TA CX CO
testo cifrato:
RS SR BU HM
Barbara Masucci - DIA – Università di Salerno
51
Il telegramma di
Zimmermann
Cifrario di Playfair
¾Migliore rispetto alla cifratura
monoalfabetica: 26x26=676 digrammi
¾La decifrazione di un
telegramma tedesco,
intercettato dagli inglesi nel
1917, influì sul corso della
storia
¾Ma la struttura del testo rimane!
¾Analisi condotta in base alla frequenza
dei digrammi più comuni nella lingua
¾Il telegramma spinse gli
Stati Uniti a riconsiderare la
loro politica di neutralità
¾Es. es, er, on, re, el, er, de.
Barbara Masucci - DIA – Università di Salerno
49
Barbara Masucci - DIA – Università di Salerno
52
Barbara Masucci - DIA – Università di Salerno
53
•9
•Corso di Sicurezza su reti
•Lezione del 2 marzo 2004
Il telegramma di
Zimmermann
Il telegramma di
Zimmermann
Nel 1915 un U-boot tedesco in immersione affondò il
transatlantico Lusitania
Zimmermann, ministro tedesco degli esteri progettò
un piano:
¾ 1198 vittime, tra cui 128 civili americani
¾ Indurre il Messico e il Giappone ad attaccare gli USA
¾ In tal modo gli USA non avrebbero avuto il tempo di
impegnarsi in Europa e la Gran Bretagna si sarebbe arresa
Per evitare l’entrata in guerra degli USA, la Germania
promise che gli U-boot sarebbero emersi prima di
attaccare
Nel 1917 la Germania decise di venir meno al suo
impegno
¾ L’impiego senza restrizioni della flotta sottomarina avrebbe
costretto la Gran Bretagna alla resa
¾ Bisognava fare presto ed evitare agli USA di entrare in
guerra cambiando il corso del conflitto
54
Barbara Masucci - DIA – Università di Salerno
Il telegramma di
Zimmermann
Il 16 gennaio 1917, Zimmermann inviò un telegramma
cifrato a von Bernstorff, ambasciatore tedesco a
Washington
¾ Il telegramma doveva essere ritrasmesso a von Eckhardt,
ambasciatore tedesco a Città del Messico
¾ L’ambasciatore lo avrebbe consegnato al presidente
messicano
55
Barbara Masucci - DIA – Università di Salerno
Decifratura del telegramma
Il telegramma fu intercettato dalla Gran Bretagna e
decifrato dai suoi crittoanalisti
¾ Non fu inviato subito agli americani
Il 1 febbraio 1917 la Germania comunicò agli USA la
decisione sull’uso illimitato degli U-boot
¾ Gli USA decisero di restare neutrali
¾ Bisognava mostrare loro il contenuto del telegramma senza
svelare il ruolo dei crittoanalisti britannici
Un agente britannico in Messico trafugò la versione
messicana del telegramma e la rese pubblica
¾ Il 2 aprile 1917 gli USA decisero di entrare in guerra
56
Barbara Masucci - DIA – Università di Salerno
Un cifrario perfetto
One-time Pad
One-time pad, Gilbert Vernam, impiegato AT&T, 1917
testo in chiaro
M = M0M1M2…Mn
Ci ← Mi ⊕Ki
57
Barbara Masucci - DIA – Università di Salerno
testo in chiaro
M = M0M1M2…Mn
testo cifrato
C = C0C1C2…Cn
Ci ← Mi ⊕Ki
testo cifrato
C = C0C1C2…Cn
chiave K = K0K1K2…Kn
(bit indipendenti e casuali)
chiave K = K0K1K2…Kn
cifrario perfetto: M e C sono indipendenti
Prob (M=M´) = Prob (M=M´ |C=C´)
(bit indipendenti e casuali)
Esempio:
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
lunghezza chiave = lunghezza testo in chiaro
58
Barbara Masucci - DIA – Università di Salerno
59
•10
•Corso di Sicurezza su reti
•Lezione del 2 marzo 2004
One-time Pad
Cifrario di Che Guevara
Messaggio
diviso in gruppi
di 5 cifre
Usato da:
¾ Spie russe
¾ Linea rossa Washington-Mosca
¾ Che Guevara per mandare messaggi a Fidel Castro
random pad
¾ Scoperto nel 1969
¾ Messaggi scritti in Spagnolo
¾ Relazione fissa tra lettere e numeri
Somma senza
riporto
One time pad su
alfabeto decimale
60
Barbara Masucci - DIA – Università di Salerno
Cilindri cifranti
Barbara Masucci - DIA – Università di Salerno
61
Cilindro di Thomas Jefferson
Circa 1790 - 1800
(Terzo presidente US)
Cilindro di 15cm e 36 dischi di legno
A S
C H
Z E
X O
G V
J I
R L
B A
Numero possibili ordinamenti dei dischi = 36! ≈ 3.72 ·1041
Prime descrizioni: Francis Bacon, 1605
62
Barbara Masucci - DIA – Università di Salerno
Barbara Masucci - DIA – Università di Salerno
Rotori
63
Rotori
Costruiti a partire dal 1918
Costruzione della prima macchina: E. H. Hebern [1918]
Primo brevetto [1921], Hebern Electric Code, Inc. prima
azienda crittografica americana, bancarotta [1926]
¾ U. S. Navy, usa macchine a 5 rotori della Hebern [1929-1930]
B. Hagelin, svedese, costruì:
testo in chiaro
A
B
C
D
...
A
B
C
D
¾ B-21 [1925], usata dall’esercito svedese
testo cifrato
¾ B-211
¾ C-36 per i Francesi [1934]
¾ C-48 (prodotte 140.000 macchine!), chiamate M-209 quando
usate dall’esercito americano nella II guerra mondiale
Per alcuni, movimento come odometro
Barbara Masucci - DIA – Università di Salerno
¾ azienda svizzera dal 1948: C-52 CD-55, T-55, CD-57
64
Barbara Masucci - DIA – Università di Salerno
65
•11
•Corso di Sicurezza su reti
•Lezione del 2 marzo 2004
Enigma
Enigma
Sviluppata da Arthur Scherbius [1918]
Usata nella II Guerra Mondiale
testo in chiaro
Barbara Masucci - DIA – Università di Salerno
66
involuzione
A
B
testo cifrato C
D
67
Barbara Masucci - DIA – Università di Salerno
Enigma
Enigma: odometro
testo in chiaro
A
B
testo cifrato C
D
ruota ad ogni carattere
ruota quando il primo rotore
passa una fissata posizione,
riflessore
ruota quando il secondo rotore
passa una fissata posizione
rimane fermo una volta quando
passa per la posizione che fa
ruotare il terzo rotore
Con tre rotori, la cifratura torna al punto iniziale dopo
26x25x26=16900 sostituzione diverse
Barbara Masucci - DIA – Università di Salerno
68
Barbara Masucci - DIA – Università di Salerno
Le chiavi di Enigma
Chiave giornaliera
Rotori o scambiatori:
1.
¾ 26x25x26=16900 combinazioni possibili
Assetto del pannello
¾
Unità cifrante:
2.
Pannello a prese multiple:
3.
¾ I tre rotori (1,2,3) potevano essere inseriti in 6 diverse
posizioni: 123, 132, 213, 231, 312, 321
¾ Gli abbinamenti di 6x2 lettere sono 12 su 26 cioè
100391791500
Es. A/L – P/R – T/D – B/W – K/F – O/Y
Disposizione dei rotori
¾
1 -3 – 2
¾
Q–C–W
¾
¾
¾
¾
Es chiave giornaliera QCW
Chiave messaggio PGH, ripetuta PGHPGH
Cifratura di PGHPGH tramite QCW, Æ KIVBJE
Cifratura e trasmissione del messaggio tramite PGH
Orientamento dei rotori
Per maggiore sicurezza si utilizza una chiave di messaggio:
Numero di chiavi totali: 10 milioni di miliardi…
Barbara Masucci - DIA – Università di Salerno
69
70
Barbara Masucci - DIA – Università di Salerno
71
•12
•Corso di Sicurezza su reti
•Lezione del 2 marzo 2004
Crittoanalisi in Polonia
Crittoanalisi in Polonia
Rejewski sfrutta la ripetizione della chiave di
messaggio per ricostruire l’assetto iniziale di Enigma
¾ Compilazione del repertorio del numero di collegamenti e degli
assetti dei rotori (circa 1 anno di lavoro)
¾ Progettazione di “bombe” per la ricerca della chiave giornaliera
¾ Studio delle concatenazioni
¾ Il numero di collegamenti non dipende dal pannello a
prese multiple
¾ Poiché i rotori potevano essere posti in sei posizioni diverse
occorrevano sei “bombe” che funzionavano in parallelo
¾ Scoperta dell’assetto dei rotori che ha generato le
concatenazioni osservate
¾ Nel 1938, modifiche ad Enigma
¾ 6 x 16900 = 101400…cento miliardi di volte più piccolo
del numero di chiavi possibili!
L OKRGM
MVTXZ E
J KTMPE
DVY PZX
AB C D E F G H I J K L M N O P Q R S T U V W X Y Z
F Q H P L W O G BM V R X U Y C Z I T N J E A S D K
Concatenazioni:
Numero di collegamenti:
A -> F -> W -> A
3
B -> Q -> Z -> K -> V -> E -> L -> R -> I -> B
9
C -> H -> G -> O -> Y -> D -> P -> C
7
J -> M -> X -> S -> T -> N -> U -> J
7
Barbara Masucci - DIA – Università di Salerno
72
Crittoanalisi a Bletchley Park
¾ Nel 1939 il materiale dei polacchi fu trasferito alla Government
Code and Cipher School di Bletchley Park, Inghilterra
¾ Da 200 a 7000 persone in 5 anni (matematici, scienziati, linguisti,
maestri di scacchi)
Barbara Masucci - DIA – Università di Salerno
73
Crittoanalisi a Bletchley Park
¾Il contributo più significativo fu dato da Alan Turing
¾ Individuazione di “crib”, frammenti di testo in chiaro che
possono essere dedotti dal testo cifrato
¾ Esame dei bollettini metereologici, trasmessi periodicamente
¾ WETTER = tempo atmosferico, presente in posizioni fisse
¾ Progettazione di un circuito che collegava tre Enigma, con
¾ Alcune debolezze di Enigma:
assetti a, a+1, a+3
¾ Nessuna lettera cifra sè stessa
¾ Una lettera non cifra lettere contigue
¾ Se LET1 cifra LET2
allora LET2 cifra LET1
¾ Utilizzo di cillies, chiavi semplici (es. qweqwe)
Barbara Masucci - DIA – Università di Salerno
¾ Aggiunti due nuovi rotori e pannello a prese multiple modificato da 6
a 10 coppie di lettere
¾ Numero delle combinazioni dei rotori: da 6 a 60…necessarie altre
54 “bombe”…
¾ Numero lettere scambiate: da 12 a 20 (su 26 possibili)
¾ Numero di possibili chiavi: 159 miliardi di miliardi!
74
Crittoanalisi a Bletchley Park
Barbara Masucci - DIA – Università di Salerno
75
Crittoanalisi a Bletchley Park
¾ Idea: annullare gli effetti del pannello a prese multiple
¾ Il circuito è percorso dalla corrente solo quando tutte e 3 le
macchine sono nel giusto assetto
¾ Creare 26 circuiti, collegando le 26 uscite del primo gruppo di rotori
con i 26 ingressi del secondo gruppo
¾ Per controllare tutti gli orientamenti, con tre rotori e 60 combinazioni,
necessari 60 gruppi di tre macchine che lavorano in parallelo
¾ Procedimento automatizzato, ma non semplificato (159 miliardi di
miliardi di combinazioni per ogni macchina)
Solo 16.900 combinazioni
per ogni macchina!
Controllo degli assetti cento
milioni di volte più facile!
Barbara Masucci - DIA – Università di Salerno
76
Barbara Masucci - DIA – Università di Salerno
77
•13
•Corso di Sicurezza su reti
•Lezione del 2 marzo 2004
Crittoanalisi a Bletchley Park
Crittoanalisi a Bletchley Park
¾ Nel 1940, costruzione di “Victory”, la prima “bomba di Turing”
¾ La Marina tedesca usava una versione più sofisticata di Enigma
¾ 10.000 sterline
¾ Dodici gruppi di rotori collegati elettricamente
¾ Lenta (7 giorni per scoprire una chiave giornaliera)
¾
¾
¾
¾
¾ Cinque mesi dopo, costruzione di “Agnus Dei”
8 rotori invece di 5
26 possibili orientamenti per il riflessore
Messaggi privi di formule stereotipate (niente crib)
Procedura per le chiavi di messaggio basato su
sostituzioni di bigrammi
¾ Veloce (un’ora per scoprire una chiave giornaliera)
¾ Necessitava di un crib di partenza
¾ Conseguenze:
Testo chiaro ipotetico:
Porzione del crittogramma:
wet t e r n u l l s ech s
IPRENLWKMJJSXCPLEJWQ
¾ La risposta di Bletchley Park:
Testo chiaro ipotetico:
Porzione del crittogramma:
wet t e r nu l l s ech s
I P R E N LW K M J J S X C P L E J W Q
Barbara Masucci - DIA – Università di Salerno
78
¾ 50 navi colate a picco al mese
¾ 50.000 marinai alleati deceduti
¾ Attaccare le navi tedesche in punti determinati per costringerle ad
inviare messaggi da cui ottenere crib
¾ Trafugare le chiavi giornaliere mediante attacchi alle navi tedesche
Barbara Masucci - DIA – Università di Salerno
79
Simulatori di Enigma
Crittoanalisi a Bletchley Park
Impatto della decifrazione di Enigma secondo David Kahn:
Enigma applet
“Ha ridotto la perdita di vite umane.
Non solo vite di soldati alleati e russi, ma grazie alla minor durata
del conflitto, anche di tedeschi, italiani e giapponesi.
Alcuni di loro che videro la fine del conflitto, avrebbero avuto una
sorte diversa in mancanza di quelle decifrazioni.
E’ questo il debito di tutti noi verso i crittoanalisti di Bletchley Park.”
¾ http://homepages.tesco.net/~andycarlson/enigma/enigma_j.html
¾ Versioni on-line e standalone, v2.3, 2001
I successi di Bletchley Park rimasero segreti, fino al 1974
Barbara Masucci - DIA – Università di Salerno
80
Bibliografia
81
Bibliografia
David Kahn,
The codebreakers: the Story of Secret
Writing
Macmillan, New York 1967
Simon & Schuster Trade
1200 pp., October 1996
Barbara Masucci - DIA – Università di Salerno
Barbara Masucci - DIA – Università di Salerno
Simon Singh,
Codici & Segreti
Rizzoli ed., 1999
82
Barbara Masucci - DIA – Università di Salerno
83
•14