•Barbara Masucci
•17/03/2004
Steganografia
Crittografia Classica
Occultamento
del messaggio
Alfredo De Santis
Sicurezza su Reti
Steganografia
Steganos = coperto
Crittografia Classica
0
Crittografia Classica
Steganografia: Esempi
Erodoto (Histories):
1
Steganografia: Esempi
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 ...
Crittografia Classica
Grafien = scrittura
inviato da Aristagora
2
Steganografia: Esempi
Crittografia Classica
3
Steganografia: Esempi
q Cina
q Cina
q Plinio il vecchio
q Plinio il vecchio
– Messaggi dipinti su striscioline di seta,
appallottolate, ricoperte di cera e inghiottite dal
corriere
– Messaggi dipinti su striscioline di seta,
appallottolate, ricoperte di cera e inghiottite dal
corriere
– Comunicazione mediante inchiostro simpatico
ottenuto dal lattice di titimabo
– Comunicazione mediante inchiostro simpatico
ottenuto dal lattice di titimabo
q Gian Battista Porta
q Gian Battista Porta
– Comunicazione mediante uovo sodo e una sorta di
“inchiostro simpatico”
Trasparente quando è asciutto e marroncino se esposto
a calore moderato (legato alla presenza di carbonio)
– Comunicazione mediante uovo sodo e una sorta di
“inchiostro simpatico”
Inchiostro con 30 grammi di allume e ½ litro di aceto, penetrava
nel guscio che era poroso, e tingeva l’albume solidificato
Crittografia Classica
•Corso di Sicurezza su Reti
4
Crittografia Classica
5
•1
•Barbara Masucci
•17/03/2004
Steganografia: Problemi
Trasformazione delle parole per renderne
incomprensibile il significato
Se il corriere è attentamente perquisito il
messaggio può essere scoperto
–
–
–
–
Scritture segrete
Città di Menet Khufu (Nilo), 4000 anni fa
Raschiando tavolette di cera
Rasando il capo al corriere
Sbucciando le uova
…
Incisione funebre (geroglifico)
scopo trasformazione:
conferire dignità e
onoreficenza al defunto
La segretezza è perduta al momento
dell’intercettazione
Altre trasformazioni, scopo:
– mistero
– senso dell’ arcano
– conferire potere magico alle parole
Crittografia Classica
6
Crittografia Classica
Crittografia
7
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
dipendono dall’esistenza di problemi difficili
Cryptos = segreto
Grafien = scrittura
Crittografia Classica
8
Crittografia e civiltà antiche
q Cina: nessuna forma di crittografia pur
essendo la scrittura antichissima
q India: crittografia sviluppata e praticata
– Artha-Sastra servizi di spionaggio
– Latila-Vistara esalta Budda, scritture perpendicolari,
disordinate
– Kama-Sutra tra le 64 arti (yoga), la 45-esima
mlecchita-vikalpa che le donne debbono conoscere …
Crittografia Classica
•Corso di Sicurezza su Reti
10
Crittografia Classica
9
Scritture segrete e testi sacri
Bibbia: tre tecniche di cifratura
– 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
Crittografia Classica
11
•2
•Barbara Masucci
•17/03/2004
Daniele
Festa in onore di Baldassarre … (re babilonese)
… una mano apparsa dal cielo scrive sulla parete …
MENE MENE TELEK UPHARSIN
Il messaggio profetizzava la fine delle ricchezze
del regno babilonese e la sua spartizione tra Medi
e Persiani…
Gorgo
Erodoto (Histories):
Demerato in esilio avvisa gli spartani del
progetto di invasione da parte di Serse, re dei Persiani
Espediente della tavoletta di cera
Gorgo, sorella di Cleomenes e moglie di
Leonidas (re spartano) scoprì la presenza del
messaggio ...
… il primo crittoanalista della storia!
Crittografia Classica
12
Alcuni metodi antichi di cifratura
Crittografia Classica
13
Cifrario di Cesare
100-44 a.C.
q Erodoto
q Scytala spartana, 500 a.C. (Plutarco in Vite parallele)
q Polibio
1
2
3
4
5
1
A
F
L
Q
V
2
B
G
M
R
W
3
C
H
N
S
X
4
D
IJ
O
T
Y
testo in chiaro:
testo cifrato:
5
E
K
P
U
Z
Svetonio (Vitae Caesarorum): lettera di Cesare a Cicerone
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
X ← M+3 mod 26
testo in chiaro
C
A
S
OMNIA GALLIA EST DIVISA IN PARTES TRES
RPQLD JDOOLD HVW GLYLVD LQ SDUWHV WUHV
A
(1,3) (1,1) (4,3) (1,1)
Crittografia Classica
testo cifrato
14
Cifrari con shift
Crittografia Classica
15
Cifrari a sostituzione
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
chiave:
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
chiave K
K∈{0,1,…,25}
X ← M+K mod 26
testo in chiaro:
C
A
S
A
testo cifrato:
T
O
P
O
Quante chiavi sono possibili?
Quante chiavi sono possibili?
Crittografia Classica
•Corso di Sicurezza su Reti
16
Crittografia Classica
17
•3
•Barbara Masucci
•17/03/2004
Cifrari a sostituzione
Analisi statistica
q Ogni lettera cambia “abito”, ma conserva la sua
“identità”
chiave:
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:
C
A
S
A
testo cifrato:
T
O
P
O
– Frequenza
– Vicinanza con altre lettere (q è sempre seguita da u,…)
– Altre regole (mai due vocali di seguito,…)
q Il cifrario può essere rotto considerando le
regolarità del linguaggio
Quante chiavi sono possibili?
– Calcolo della frequenza relativa delle lettere nel cifrato
– Confronto con la distribuzione standard delle frequenze
per quel linguaggio
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!
Crittografia Classica
18
Crittografia Classica
Omofoni
Frequenze occorrenze lettere
q Molti simboli per cifrare singoli caratteri
frequenti
14
12
10
8
testo in chiaro:
6
testo cifrato:
4
2
0
A B C
italiano 10,3 0,9 4,3
inglese
7,3 1,3 3,5
francese 8,3 1,3 3,3
19
A B C D E
F G H I
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 L M N
1,1 11,6 0,0 0,0 6,6 2,6 6,6
3,5 7,8 0,3 0,5 3,7 2,8 7,8
1,3 7,3 0,8 0,0 5,8 3,2 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
Crittografia Classica
Y
0,0
2,3
0,8
20
Nulle
Crittografia Classica
21
– Compilazione e trasporto del repertorio
testo in chiaro: QUELQRAMODELQLAGO...
…
q Aumento frequenze dei corrispondenti simboli
•Corso di Sicurezza su Reti
q Si abbassano le frequenze dei simboli del
testo cifrato
12.6 per E
3.15 per • Õ Ñ ®
q In aggiunta all’alfabeto cifrante si usa un
insieme di parole in codice
q Svantaggi:
– in posizioni da non alterare il significato
Crittografia Classica
(scelti a caso!)
Nomenclatori
q Aggiungere simboli meno frequenti
testo cifrato:
Z
0,9
0,3
0,0
E
•Õ Ñ ®
22
– Se cade in mani ostili, ripetizione della
distribuzione
– Non molto più sicuro della singola sostituzione
monoalfabetica
Crittografia Classica
23
•4
•Barbara Masucci
•17/03/2004
La congiura di Babington
q Nel 1586 Maria Stuarda, regina di Scozia,
fu condannata a morte per aver cospirato
contro la cugina Elisabetta
q La congiura, organizzata da Anthony
Babington, prevedeva
– 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
– La liberazione di Maria dalla prigionia in
Inghilterra
– L’uccisione di Elisabetta
– Una ribellione alla religione protestante
q 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
q Sir Francis Walsingham, segretario di
stato, provò che Maria aveva preso parte
alla congiura
Crittografia Classica
24
Crittoanalisi
Of the character 8 there are
;
"
4
"
+ )
"
*
"
5
"
6
"
! 1
"
0
"
9 2
"
: 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;+?;
26
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;+?;
(
"
r
;
"
t
25
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;+?;
messaggio scritto dal pirata Capitano Kidd, dice dove è nascosto il tesoro
5 represents a
!
"
d
8
"
e
3
"
g
4
"
h
6
"
i
*
"
n
+
"
o
Crittografia Classica
Crittoanalisi
Edgar Allan Poe, “Lo scarabeo d'oro” (1843)
Crittografia Classica
La congiura di Babington
q Maria e Babington comunicavano grazie a
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.
33.
26.
19.
16.
13.
12.
11.
8.
6.
5.
4.
3.
2.
1.
Let us assume 8, then, as e.
7 occorrenze di ;48
Assumiamo che ; [ t
4[ h
8[ e
…poi
Crittografia Classica
27
Few persons can be made to believe
that it is not quite an easy thing to
invent a method of secret writing
which shall baffle investigation.
Yet it may be roundly asserted
that human ingenuity cannot
concoct a cipher which human
ingenuity cannor resolve.
Edgar Allan Poe
Crittografia Classica
•Corso di Sicurezza su Reti
28
Crittografia Classica
29
•5
•Barbara Masucci
•17/03/2004
Oltre la cifratura
monoalfabetica
Cifrario di Porta
Giovanni Battista Porta, primo cifrario per digrammi [1563]
Due approcci:
q Utilizzo di cifrature di più lettere per volta
– Porta
– Playfair
q Utilizzo di più alfabeti cifranti
– Leon Battista Alberti
– Vigenère
Crittografia Classica
30
DO
92
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
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
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
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
Crittografia Classica
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
31
Cifrario di Porta
Cifrario di Porta
testo in chiaro:
testo cifrato:
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
MA NI
312 346
Chiave: permutazione arbitraria di:
– numeri del cifrato
– lettere su righe e colonne
Uso di caratteri speciali per alfabeto testo cifrato
Crittografia Classica
32
Cifrario di Playfair
T
A
F
W
O
Z
U
G
X
S
C
IJ
N
B
Y
L
E
R
D
P
M
H
K
V
Q
Cifrario usato dai britannici.
Anche dall’Australia durante
la II guerra mondiale.
Anche rettangoli 4x7, 4x8,…
Crittografia Classica
•Corso di Sicurezza su Reti
33
Cifrario di Playfair
Progettato da Charles Wheatstone buon amico
del Barone Lyon Playfair, XIX secolo
M
H
K
V
Q
Crittografia Classica
34
T
A
F
W
O
Z
U
G
X
S
C
IJ
N
B
Y
L
E
R
D
P
testo in chiaro: DO MA NI
testo cifrato: WP TH BN
Crittografia Classica
35
•6
•Barbara Masucci
•17/03/2004
Leon Battista Alberti
architetto italiano, XV secolo
Disco di Alberti
Leon Battista Alberti,
architetto italiano, XV secolo
Proposta di usare più alfabeti cifranti e di
sostituirli durante la cifratura
testo in chiaro
Alfabeto
piano
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 Z
E U F A V O D N P H S G T M I L B R Z C Q
C M U N B I P L O V A T G S D R H Q F Z E
I Alfabeto
cifrante
II Alfabeto
cifrante
Crittografia Classica
leone
hbttv
testo cifrato con
rotazione “AL”
Utilizzato nella guerra di secessione
36
Crittografia Classica
Cifrari a sostituzione polialfabetica
Cifrario di Vigenère [1586] (Blaise de Vigenère, 1523-1596)
testo in chiaro
M = M0M1M2…M n
Ci ← Mi +Ki mod t mod 26
testo cifrato
C = C0C1C2…Cn
Quadrato di
Vigenère
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
Crittografia Classica
38
Cifrari a sostituzione polialfabetica
M = M0M1M2…M n
Ci ← Mi +Ki mod t mod 26
testo cifrato
C = C0C1C2…Cn
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
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
VW
W X
X Y
Y Z
Z A
A B
B C
C D
D E
E F
F G
I J K L
J K L M
K L MN
L MN O
M NO P
NO P Q
OPQR
PQR S
Q RS T
R S T U
S T U V
T UVW
U VW X
VWXY
WXY Z
X Y Z A
Y Z A B
Z AB C
A BC D
B CD E
C DE F
D EF G
E F GH
F GH I
G HI J
H I J K
M
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
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
R S
S T
T U
U V
VW
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
O P
P Q
S
T
U
V
W
X
Y
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
T U V
U VW
VW X
WX Y
X Y Z
Y Z A
Z A B
A B C
B C D
CD E
D E F
EF G
F G H
G H I
HI J
I J K
J K L
KL M
L M N
M N O
NO P
OP Q
P QR
QR S
R S T
S T U
Crittografia Classica
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
Z
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
Y
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
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
39
Cifrari a sostituzione polialfabetica
testo in chiaro
M = M0M1M2…M n
Ci ← Mi +Ki mod t mod 26
testo cifrato
C = C0C1C2…Cn
m Babbage (1834) e Kasiski (1863) furono i primi a cimentarsi nella
crittoanalisi
m Studio delle ripetizioni per individuare la lunghezza della chiave (indice
di coincidenza)
m Analisi delle frequenze in ognuno degli alfabeti cifranti corrispondenti
alle lettere della chiave (indice mutuo di coincidenza)
mConsiderato inviolabile per molto tempo
m Numero possibili chiavi = 26t
m Resiste all’analisi delle frequenze
Una lettera cifrata corrisponde a più simboli in chiaro
•Corso di Sicurezza su Reti
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
chiave K = K0K1K2…Kt-1
chiave K = K0K1K2…Kt-1
Crittografia Classica
C
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
Cifrario di Vigenère [1586] (Blaise de Vigenère, 1523-1596)
Cifrario di Vigenère [1586] (Blaise de Vigenère, 1523-1596)
testo in chiaro
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
Q R
R S
S T
T U
U V
VW
W X
X Y
Y Z
Z A
37
40
Crittografia Classica
41
•7
•Barbara Masucci
•17/03/2004
Griglie
Griglie
Girolamo Cardano, XVI secolo
N
Z
L
I
O
E
Z
C
N
S
L
O
A
D
T
M
D
M
I
R
Girolamo Cardano, XVI secolo
E
E
M
N
A
N
Z
L
I
O
Crittografia Classica
E
Z
C
N
S
7
3
1
1
4
8
8
4
1
1
3
7
9
2
3
4
2
6
A
M
O
O
M
I
A
E
A
Z
H
I
R
N
M
N
A
I
M
T
A
Z
N
O
griglia
griglia ruotata
7
3
1
1
4
8
8
4
1
1
3
7
di 90°
9
2
3
4
2
6
griglia ruotata
griglia ruotata
di 180°
di 270°
5
6
7
8
9
5
Crittografia Classica
45
I crittogrammi Beale
q La vicenda inizia nel 1822 a Lynchburg, Virginia
q Protagonisti:
griglia
O
O
C
O
I
L
6
2
4
3
2
9
44
Griglie con rotazioni
43
Griglie con rotazioni
5
9
8
7
6
5
5
6
7
8
9
5
Crittografia Classica
A
T
D
C
C
G
E
E
M
N
A
Crittografia Classica
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
6
2
4
3
2
9
M
D
M
I
R
42
Griglie con rotazioni
5
9
8
7
6
5
L
O
A
D
T
griglia ruotata
di 90°
griglia ruotata
di 180°
griglia ruotata
di 270°
–
–
–
–
–
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
testo cifrato: AAARMOTMENTODOAMACCOZNZOCMHANIGIIIOL
testo in chiaro: ATTACCHIAMODOMANIAMEZZOGIORNOCONMIL
Crittografia Classica
•Corso di Sicurezza su Reti
46
Crittografia Classica
47
•8
•Barbara Masucci
•17/03/2004
I crittogrammi Beale
I crittogrammi Beale
q Nel 1822 Beale affidò a Morris una scatola chiusa
a chiave chiedendogli di custodirla
q Beale non tornò mai e Morris non ricevette la
chiave di decifratura
q Nel 1845 Morris aprì la scatola
– La scatola conteneva documenti cifrati
q 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
Crittografia Classica
48
I crittogrammi Beale
Crittografia Classica
49
I crittogrammi Beale
q Morris tentò per 20 anni di decifrare i crittogrammi,
senza successo
q Nel 1862 mostrò i crittogrammi ad un amico che, dopo
aver decifrato il secondo, pubblicò un opuscolo nel
1885
q Il secondo crittogramma fu decifrato usando come
chiave la dichiarazione di indipendenza
L’opuscolo
Crittografia Classica
50
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…
Crittografia Classica
•Corso di Sicurezza su Reti
52
Un crittogramma
Crittografia Classica
51
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) disso lve(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) …
Crittografia Classica
53
•9
•Barbara Masucci
•17/03/2004
Il crittogramma decifrato
" 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."
Crittografia Classica
54
Il telegramma di
Zimmermann
– I crittogrammi potrebbero essere stati alterati
dall’autore dell’opuscolo per impedirne la decifratura
q E il tesoro?
– Qualcuno potrebbe averlo trovato utilizzando gli
indizi dell’unico crittogramma decifrato
q L’intera storia potrebbe essere una montatura,
ispirata dal romanzo di Edgar Allan Poe
q Ancora oggi crittoanalisti e cacciatori di tesori
sono affascinati dalla vicenda
Crittografia Classica
55
Il telegramma di
Zimmermann
q Nel 1915 un U-boot tedesco in immersione affondò il
transatlantico Lusitania
q La decifrazione di un
telegramma tedesco,
intercettato dagli inglesi nel
1917, influì sul corso della
storia
q Il telegramma spinse gli
Stati Uniti a riconsiderare
la loro politica di neutralità
Crittografia Classica
I crittogrammi Beale
q Il primo e il terzo crittogramma di Beale sono
inviolati da più di un secolo
– 1198 vittime, tra cui 128 civili americani
q Per evitare l’entrata in guerra degli USA, la
Germania promise che gli U-boot sarebbero emersi
prima di attaccare
q 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
56
Crittografia Classica
57
Il telegramma di
Zimmermann
Il telegramma di
Zimmermann
q Zimmermann, ministro tedesco degli esteri
progettò un piano:
Il telegramma fu
intercettato dalla Gran
Bretagna e decifrato
dai suoi crittoanalisti
– 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
q 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
Crittografia Classica
•Corso di Sicurezza su Reti
58
Crittografia Classica
59
•10
•Barbara Masucci
•17/03/2004
Il telegramma di
Zimmermann
Decifratura del telegramma
q Il telegramma fu intercettato dalla Gran Bretagna
e decifrato dai suoi crittoanalisti
– Non fu inviato subito agli americani
q 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
q 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
Crittografia Classica
60
Crittografia Classica
61
Cilindro di Thomas Jefferson
Cilindri cifranti
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
Crittografia Classica
62
Rotori
Crittografia Classica
63
Rotori
Costruiti a partire dal 1918
q Costruzione della prima macchina: E. H. Hebern [1918]
q 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]
q B. Hagelin, svedese, costrui:
testo in chiaro
A
B
C
D
...
A
B
C
D
testo cifrato
– 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
Crittografia Classica
•Corso di Sicurezza su Reti
– B-21 [1925], usata dall’esercito svedese
– B-211
– azienda svizzera dal 1948: C-52, CD-55, T-55, CD-57
64
Crittografia Classica
65
•11
•Barbara Masucci
•17/03/2004
Enigma
Enigma
Sviluppata da Arthur Scherbius [1918]
Usata nella II Guerra Mondiale
testo in chiaro
Crittografia Classica
66
Enigma
Crittografia Classica
involuzione
A
B
testo cifrato C
D
67
Enigma: odometro
testo in chiaro
A
B
testo cifrato C
D
ruota ad ogni carattere
ruota quando il primo rotore
passa una fissata posizione,
ruota quando il secondo rotore
passa una fissata posizione
rimane fermo una volta quando
passa per la posizione che fa
ruotare il terzo rotore
Ciclo: 26 ·25 ·26 = 16.900 caratteri!
Crittografia Classica
68
q Walzenlage scelta di 3 rotori tra 5 (Esercito e
Aviazione) oppure tra 8 (Marina)
Marina M4, quarto rotore, “greco” e sottile riflettore
verso la fine della guerra
q Umkehrwalze scelta del riflettore
q Ringstellung posizionamento ordinato dei rotori
q Steckers posizionamento di una tavola di connessioni
testo cifrato
A
B
C
D
Crittografia Classica
•Corso di Sicurezza su Reti
69
Le chiavi di Enigma
Enigma: inizializzazione
testo in chiaro
Crittografia Classica
q Rotori o scambiatori:
– 26x25x26 = 16.900 combinazioni possibili
q Unità cifrante:
– I tre rotori (1,2,3) potevano essere inseriti in 6
diverse posizioni: 123, 132, 213, 231, 312, 321
q Pannello a prese multiple:
– Gli abbinamenti di 6x2 lettere sono 12 su 26 cioè
100.391.791.500
Numero di chiavi totali: 10 milioni di miliardi…
70
Crittografia Classica
71
•12
•Barbara Masucci
•17/03/2004
Crittoanalisi in Polonia
Chiave giornaliera
1.
2.
3.
–
–
–
q
–
–
–
–
Assetto del pannello
Rejewski sfrutta la ripetizione della chiave di messaggio
per ricostruire l’assetto iniziale di Enigma
Es. A/L – P/R – T/D – B/W – K/F – O/Y
Disposizione dei rotori
– Studio delle concatenazioni
Orientamento dei rotori
– Scoperta dell’assetto dei rotori che ha generato le
concatenazioni osservate
• Il numero di collegamenti non dipende dal pannello a prese
multiple
1-3–2
Q– C–W
• 6 x 16.900 = 101.400…cento miliardi di volte più piccolo del
numero di chiavi possibili!
Per maggiore sicurezza si utilizza una chiave di
messaggio:
L OKRGM
MVTXZ E
J KTMPE
DVY PZX
Es. chiave giornaliera QCW
Chiave messaggio PGH, ripetuta PGHPGH
Cifratura di PGHPGH tramite QCW, à KIVBJE
Cifratura e trasmissione del messaggio tramite PGH
Crittografia Classica
72
Crittoanalisi in Polonia
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
Crittografia Classica
73
Crittoanalisi a Bletchley Park
q Compilazione del repertorio del numero di collegamenti e degli
assetti dei rotori (circa 1 anno di lavoro)
q Progettazione di “bombe” per la ricerca della chiave giornaliera
q Nel 1939 il materiale dei polacchi fu trasferito alla Government
Code and Cipher School di Bletchley Park, Inghilterra
q Nel 1938, modifiche ad Enigma
q Alcune debolezze di Enigma:
– Poiché i rotori potevano essere posti in sei posizioni diverse
occorrevano sei “bombe” che funzionavano in parallelo
– “bombe” forse a causa del ticchettio prodotto
– 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!
Crittografia Classica
74
Crittoanalisi a Bletchley Park
– Da 200 a 7.000 persone in 5 anni (matematici, scienziati, lingui sti,
maestri di scacchi)
– Nessuna lettera cifra sè stessa
– Una lettera non cifra lettere contigue
– Se LET1 cifra LET2
allora LET2 cifra LET1
– Utilizzo di cillies, chiavi semplici e non generate a caso (es. qweqwe)
Crittografia Classica
75
Crittoanalisi a Bletchley Park
q Il circuito è percorso dalla corrente solo quando tutte e 3 le macchine
sono nel giusto assetto
Il contributo più significativo fu dato da Alan Turing
– Individuazione di “crib”, frammenti di testo in chiaro che
possono essere dedotti dal testo cifrato
– Procedimento automatizzato, ma non semplificato (159 miliardi di miliardi
di combinazioni per ogni macchina)
• Esame dei bollettini metereologici, trasmessi periodicamente
• WETTER = tempo atmosferico, presente in posizioni fisse
– Progettazione di un circuito che collegava tre Enigma, con
assetti a, a+1, a+3
Crittografia Classica
•Corso di Sicurezza su Reti
76
Crittografia Classica
77
•13
•Barbara Masucci
•17/03/2004
Crittoanalisi a Bletchley Park
Idea: annullare gli effetti del pannello a prese multiple
– 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 comb inazioni,
necessari 60 gruppi di tre macchine che lavorano in parallelo
Crittoanalisi a Bletchley Park
q Nel 1940, costruzione di “Victory”, la prima “bomba di Turing”
– 10.000 sterline
– Dodici gruppi di rotori collegati elettricamente
– Lenta (7 giorni per scoprire una chiave giornaliera)
q Cinque mesi dopo, costruzione di “Agnus Dei”
– Veloce (un’ora per scoprire una chiave giornaliera)
– Necessitava di un crib di partenza
Solo 16.900 combinazioni
per ogni macchina!
Controllo degli assetti cento
milioni di volte più facile!
Crittografia Classica
q La Marina tedesca usava una versione più sofisticata di Enigma
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
– 50 navi colate a picco al mese
– 50.000 marinai alleati deceduti
q La risposta di Bletchley Park:
– 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
Crittografia Classica
testo cifrato
C = C0C1C2…Cn
(bit indipendenti e casuali)
100101110110
001110101010
101011011100
Crittografia Classica
•Corso di Sicurezza su Reti
79
Crittoanalisi a Bletchley Park
Impatto della decifrazione di Enigma secondo David Kahn:
I successi di Bletchley Park rimasero segreti, fino al 1974
Crittografia Classica
testo in chiaro
M = M0M1M2…M n
chiave K = K0K1K2…Kn
Esempio:
Crittografia Classica
81
One-time Pad
One-time pad, Gilbert Vernam, impiegato AT&T, 1917
M = M0M1M2…M n
w e t t e r nu l l s ec h s
I P R E N LW K M J J S X C P L E J W Q
80
Un cifrario perfetto
Ci ← Mi ⊕Ki
Testo chiaro ipotetico:
Porzione del crittogramma:
“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.”
q Conseguenze:
testo in chiaro
wet t e r n u l l s ech s
I PR E N L W K M J J S X C P L EJ W Q
78
Crittoanalisi a Bletchley Park
–
–
–
–
Testo chiaro ipotetico:
Porzione del crittogramma:
testo in chiaro
chiave
testo cifrato
82
Ci ← Mi ⊕Ki
testo cifrato
C = C0C1C2…Cn
chiave K = K0K1K2…Kn
(bit indipendenti e casuali)
cifrario perfetto: M e C sono indipendenti
Prob (M=M´) = Prob (M=M´ | C=C´)
lunghezza chiave = lunghezza testo in chiaro
Crittografia Classica
83
•14
•Barbara Masucci
•17/03/2004
One-time Pad
Cifrario di Che Guevara
Usato da:
– Spie russe
– Linea rossa Washington-Mosca
– Che Guevara per mandare messaggi a Fidel Castro
• Scoperto nel 1969
• Messaggi scritti in Spagnolo
• Relazione fissa tra lettere e numeri
Messaggio
diviso in gruppi
di 5 cifre
random pad
Somma senza riporto
One time pad su
alfabeto decimale
Crittografia Classica
84
Bibliografia
85
Bibliografia
David Kahn,
The codebreakers: the Story of Secret
Writing
Macmillan, New York 1967
Simon & Schuster Trade
1200 pp., October 1996
Crittografia Classica
Crittografia Classica
Simon Singh,
Codici & Segreti
Rizzoli ed., 1999
86
Educational Tools for
Cryptography
Crittografia Classica
87
ETC
q http://www.cs.newcastle.edu.au/Research/DSG/
q etc.zip, 270 KB, luglio 1999
q Autore: Andrew White
q Windows
q Cifrari a sostituzione, con shift, Vigenere,
analisi statistica
q Anche Crittografia Visuale
Crittografia Classica
•Corso di Sicurezza su Reti
88
Crittografia Classica
89
•15
•Barbara Masucci
•17/03/2004
Enigma
q Molti simulatori disponibili sul Web
q Enigma applet
– http://homepages.tesco.net /~andycarlson/enigma/enigma_j.html
– Versioni on-line e standalone, v2.3, 2001
Crittografia Classica
•Corso di Sicurezza su Reti
90
•16