•Barbara Masucci
•12/03/2003
Crittografia
Crittografia
Classica
Dall’antichità fino a pochi anni fa:
– Essenzialmente comunicazioni private
– Usi Militari e Diplomatici
χρυπτοσ
Barbara Masucci
Dipartimento di Informatica ed Applicazioni
Università di Salerno
γραφια
λογοσ
Oggi: studio di tecniche ed applicazioni che
dipendono dall’esistenza di problemi difficili
[email protected]
http://www.dia.unisa.it/masucci.dir
Crittografia Classica
Scritture segrete
Scritture segrete
trasformazione
+
segretezza
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
Altre trasformazioni, scopo:
Crittografia
Cryptos = segreto
– mistero
– senso dell’arcano
– conferire potere magico alle parole
Crittografia Classica
1
2
Crittografia e civiltà antiche
‰ Cina: nessuna forma di crittografia pur
essendo la scrittura antichissima
Grafien = scrittura
Crittografia Classica
3
Crittografia e civiltà antiche
– Artha-Sastra servizi di spionaggio
‰ Mesopotamia: Assiri e Babilonesi
(scritture cuneiformi) parti terminali delle
parole sostituite con forme stereotipate
(colofoni)
– Latila-Vistara esalta Budda, scritture perpendicolari,
disordinate
‰Iraq: periodo terminale delle scritture cuneiformi
‰ India: crittografia sviluppata e praticata
– Kama-Sutra tra le 64 arti (yoga), la 45-esima
mlecchita-vikalpa che le donne debbono conoscere …
Crittografia Classica
•Corso di Sicurezza su Reti
4
Nomi vengono sostituiti da numeri
Crittografia Classica
5
•1
•Barbara Masucci
•12/03/2003
Scritture segrete e Civiltà
‰ Yezidis: popolazione di circa 25.000 abitanti
scritture segrete per proteggere i testi sacri
dai musulmani
‰ Tibetani: scrittura segreta per la
corrispondenza ufficiale
‰ Nsibidi: scrittura di tipo pittorico per
esprimere concetti d’amore … tanto
crittografica quanto pornografica
La crittografia nasce
spontaneamente
non appena una
società raggiunge
un determinato
livello di sviluppo
Crittografia Classica
6
Scritture segrete e Civiltà
‰ Thailandia: diverse tecniche di cifratura
– sostituzione
– divisione delle lettere dell’alfabeto in gruppi
Ogni lettera è indicata dal numero di gruppo e
dalla posizione nel gruppo
‰ Maldive: due forme di scrittura segreta
‰ Persia: primo uso delle scritture segrete per
documenti politici e di natura fiscale (600 d.C.)
Crittografia Classica
Scritture segrete e Civiltà
Crittografia Classica
7
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
8
Crittografia Classica
Daniele
9
Gorgo
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…
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
•Corso di Sicurezza su Reti
10
Crittografia Classica
11
•2
•Barbara Masucci
•12/03/2003
Cifrario di Cesare
Alcuni metodi antichi di cifratura
100100-44 a.C.
‰Erodoto
‰Scytala spartana, 500 a.C. (Plutarco in Vite parallele)
‰Polibio
1 2 3 4 5
1
2
3
4
5
A
F
L
Q
V
B
G
M
R
W
C
H
N
S
X
D
IJ
O
T
Y
E
K
P
U
Z
testo in chiaro:
testo cifrato:
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
12
Crittografia Classica
Cifrari a sostituzione
13
Frequenze occorrenze lettere
chiave:
14
12
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
10
testo in chiaro:
C
A
S
A
8
testo cifrato:
T
O
P
O
6
4
Cifrari con shift
2
Chiave K
0
X ← M+K mod 26
K∈{0,1,…,25}
Crittografia Classica
A
italiano
10,3
inglese
7,3
francese 8,3
B
0,9
1,3
1,3
C
4,3
3,5
3,3
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
14
•Corso di Sicurezza su Reti
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
15
– in posizioni da non alterare il significato
(scelti a caso!)
‰Si abbassano le frequenze dei simboli del
testo cifrato
12.6 per E
3.15 per Õ Ñ ®
Crittografia Classica
N
6,6
7,8
7,2
‰Aggiungere simboli meno frequenti
E
ÕÑ®
M
2,6
2,8
3,2
Nulle
‰ Molti simboli per cifrare singoli caratteri
frequenti
testo cifrato:
L
6,6
3,7
5,8
Crittografia Classica
Omofoni
testo in chiaro:
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
testo in chiaro: QUELQRAMODELQLAGO...
testo cifrato:
…
‰Aumento frequenze dei corrispondenti simboli
16
Crittografia Classica
17
•3
•Barbara Masucci
•12/03/2003
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
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
• 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
‰ 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
‰ Sir Francis Walsingham, segretario di
stato, provò che Maria aveva preso parte
alla congiura
Crittografia Classica
18
Crittografia Classica
19
Disco di Alberti
Crittoanalisi
Leon Battista Alberti,
architetto italiano, XV secolo
Edgar Allan Poe, “Lo scarabeo d'oro” (1843)
messaggio scritto dal pirata Capitano Kidd, dice dove è nascosto il tesoro
testo in chiaro
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
; 48 I8E60 ) ) 85 ; II ( ; : I *8 I 83(88 ) 5* I
THE DEVIL`S SEAT FORTY-ONE DEGREES AND
DI S CO
U B X MG
testo cifrato con
rotazione “AL”
Crittografia Classica
20
Cifrario di Porta
Giovanni Battista Porta,
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
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
Crittografia Classica
21
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
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
Crittografia Classica
•Corso di Sicurezza su Reti
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
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
22
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
Crittografia Classica
23
•4
•Barbara Masucci
•12/03/2003
Cifrario di Porta
Cifrario di Playfair
Progettato da Charles Wheatstone buon amico
del Barone Lyon Playfair, XIX secolo
M
H
K
V
Q
Crittografia Classica
T
A
F
W
O
Z
U
G
X
S
C
IJ
N
B
Y
24
T
A
F
W
O
Z
U
G
X
S
C
IJ
N
B
Y
Girolamo Cardano, XVI secolo
L
E
R
D
P
N
Z
L
I
O
L
O
A
D
T
M
D
M
I
R
•Corso di Sicurezza su Reti
M
D
M
I
R
E
E
M
N
A
Crittografia Classica
27
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
E
E
M
N
A
Crittografia Classica
L
O
A
D
T
Griglie con rotazioni
Girolamo Cardano, XVI secolo
E
Z
C
N
S
E
Z
C
N
S
26
Griglie
N
Z
L
I
O
25
Griglie
testo in chiaro: DO MA NI
testo cifrato: WP TH BN
Crittografia Classica
Anche rettangoli 4x7, 4x8,…
Crittografia Classica
Cifrario di Playfair
M
H
K
V
Q
L
E
R
D
P
Cifrario usato dai britannici.
Anche dall’Australia durante
la II guerra mondiale.
5
9
8
7
6
5
28
6
2
4
3
2
9
7
3
1
1
4
8
8
4
1
1
3
7
9
2
3
4
2
6
5
6
7
8
9
5
Crittografia Classica
29
•5
•Barbara Masucci
•12/03/2003
Griglie con rotazioni
griglia
griglia ruotata
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
di 180°
di 270°
5
6
7
8
9
5
Griglie con rotazioni
A
T
D
C
C
G
A
M
O
O
M
I
A
E
A
Z
H
I
R
N
M
N
A
I
M
T
A
Z
N
O
30
Cifrario di Vigenère [1586] (Blaise de Vigenère, 1523-1596)
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
32
Cifrari a sostituzione polialfabetica
M = M0M1M2…Mn
di 180°
griglia ruotata
di 270°
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
Crittoanalisi: possibile romperlo usando indice di
coincidenza ed indice mutuo di coincidenza
Crittografia Classica
•Corso di Sicurezza su Reti
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
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 NOP Q
M NOP Q R
N OPQR S
O P QR S T
P QRS 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 BC 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
31
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
S T U V
T U VW
U V W X
V W X Y
W X Y Z
X Y ZA
Y Z A B
Z A B C
A B CD
B C D E
C D E F
D E F G
E F G H
F G HI
G H I J
H I J K
I J K L
J K L M
K L M N
L M NO
M N OP
N O P Q
O P QR
P QR S
QR S T
V
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
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
Crittografia Classica
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
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
33
I crittogrammi Beale
‰ La vicenda inizia nel 1822 a Lynchburg, Virginia
‰ Protagonisti:
Cifrario di Vigenère [1586] (Blaise de Vigenère, 1523-1596)
testo in chiaro
di 90°
griglia ruotata
Crittografia Classica
Cifrari a sostituzione polialfabetica
M = M0M1M2…Mn
griglia ruotata
testo cifrato: AAARMOTMENTODOAMACCOZNZOCMHANIGIIIOL
testo in chiaro: ATTACCHIAMODOMANIAMEZZOGIORNOCONMIL
Crittografia Classica
testo in chiaro
griglia
O
O
C
O
I
L
34
–
–
–
–
–
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
Crittografia Classica
35
•6
•Barbara Masucci
•12/03/2003
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
Crittografia Classica
36
I crittogrammi Beale
Crittografia Classica
37
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
Crittografia Classica
38
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
40
Un crittogramma
Crittografia Classica
39
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) …
Crittografia Classica
41
•7
•Barbara Masucci
•12/03/2003
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
42
Il telegramma di
Zimmermann
– 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
Crittografia Classica
43
– 1198 vittime, tra cui 128 civili americani
‰ 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
44
Crittografia Classica
45
Il telegramma di
Zimmermann
‰ 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
– Non fu inviato subito agli americani
‰ 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
•Corso di Sicurezza su Reti
‰ E il tesoro?
‰ Nel 1915 un U-boot tedesco in immersione affondò il
transatlantico Lusitania
Il telegramma di
Zimmermann
Crittografia Classica
– I crittogrammi potrebbero essere stati alterati
dall’autore dell’opuscolo per impedirne la decifratura
Il telegramma di
Zimmermann
‰ 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à
Crittografia Classica
I crittogrammi Beale
‰ Il primo e il terzo crittogramma di Beale sono
inviolati da più di un secolo
‰ 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
46
Crittografia Classica
47
•8
•Barbara Masucci
•12/03/2003
Decifratura del telegramma
Cilindri cifranti
Prime descrizioni: Francis Bacon, 1605
Crittografia Classica
48
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
Crittografia Classica
49
Rotori
Costruiti a partire dal 1918
testo in chiaro
A
B
C
D
Numero possibili ordinamenti dei dischi = 36! ≈ 3.72 ·1041
Crittografia Classica
50
Rotori
...
A
B
C
D
testo cifrato
Per alcuni movimento come odometro
Crittografia Classica
51
Enigma
‰ Costruzione della prima macchina: E. H. Hebern [1918]
‰ Primo brevetto [1921], Hebern Electric Code, Inc. prima
azienda crittografica americana, bancarotta [1926]
Sviluppata da Arthur Scherbius [1918]
Usata nella II Guerra Mondiale
– U. S. Navy, usa macchine a 5 rotori della Hebern [1929-1930]
‰ B. Hagelin, svedese, costrui:
– B-21 [1925], usata dall’esercito svedese
– 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
– azienda svizzera dal 1948: C-52 CD-55, T-55, CD-57
Crittografia Classica
•Corso di Sicurezza su Reti
52
Crittografia Classica
53
•9
•Barbara Masucci
•12/03/2003
Enigma
Enigma
testo in chiaro
involuzione
A
B
testo cifrato C
D
Crittografia Classica
54
Enigma: odometro
Crittografia Classica
55
Enigma: inizializzazione
‰ Walzenlage scelta di 3 rotori tra 5 (Esercito e
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
Aviazione) oppure tra 8 (Marina)
Marina M4, quarto rotore, “greco” e sottile riflettore
verso la fine della guerra
‰ Umkehrwalze scelta del riflettore
‰ Ringstellung posizionamento ordinato dei rotori
‰ Steckers posizionamento di una tavola di connessioni
testo in chiaro
rimane fermo una volta quando
passa per la posizione che fa
ruotare il terzo rotore
testo cifrato
Ciclo: 26 ·25 ·26 = 16.900 caratteri!
Crittografia Classica
56
Enigma: crittoanalisi
‰ Prima in Polonia
‰ Poi Government Code and Cipher School a Bletchley Park
‰ Alcune debolezze:
Crittografia Classica
Un cifrario perfetto
testo in chiaro
M = M0M1M2…Mn
Ci ← Mi ⊕Ki
testo cifrato
C = C0C1C2…Cn
chiave K = K0K1K2…Kn
(bit indipendenti e casuali)
Esempio:
Alan Turing
•Corso di Sicurezza su Reti
57
One-time pad, Gilbert Vernam, impiegato AT&T, 1917
– Nessuna lettera cifra se stessa
– Se LET1 cifra LET2
allora LET2 cifra LET1
– Invio della posizione iniziale rotori
Crittografia Classica
A
B
C
D
58
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
Crittografia Classica
59
•10
•Barbara Masucci
•12/03/2003
One-time Pad
OneOne-time Pad
testo in chiaro
M = M0M1M2…Mn
Ci ← Mi ⊕Ki
Usato da:
testo cifrato
C = C0C1C2…Cn
– 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
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
60
Cifrario di Che Guevara
Messaggio
diviso in gruppi
di 5 cifre
Crittografia Classica
61
Bibliografia
David Kahn,
The codebreakers: the Story of Secret
Writing
‰ Macmillan, New York 1967
‰ Simon & Schuster Trade
1200 pp., October 1996
random pad
Somma senza riporto
One time pad su
alfabeto decimale
Crittografia Classica
62
Crittografia Classica
63
Educational Tools for
Cryptography
Bibliografia
Simon Singh,
Codici & Segreti
Rizzoli ed., 1999
‰ http://www.cs.newcastle.edu.au/Research/DSG/
‰ etc.zip, 270 KB, luglio 1999
‰Autore: Andrew White
‰Windows
‰Cifrari a sostituzione, con shift, Vigenere,
analisi statistica
‰Anche Crittografia Visuale
Crittografia Classica
•Corso di Sicurezza su Reti
64
Crittografia Classica
65
•11
•Barbara Masucci
•12/03/2003
ETC
Enigma
‰ Molti simulatori disponibili sul Web
‰ 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
66
Crittografia Classica
67
•12