Crittografia - Passato, presente, futuro

Crittografia

, ,

Passato presente futuro

ITIS Antonio Meucci, Firenze

Bruni Valentino 5

B ins

A.s. 2008/2009

1

Crittografia

, ,

Passato presente futuro

Indice

I ..................................................................................................................................................... 3

Indice

1 - Premesse .......................................................................................................................................... 7

Premesse

1.1 - Introduzione..................................................................................................................................................... 7

1.2 - Steganografia................................................................................................................................................... 7

1.3 - Crittografia ...................................................................................................................................................... 8

1.4 - Terminologia.................................................................................................................................................... 9

1.5 - Sicurezza .........................................................................................................................................................10

Passato.................................................................................................................................11

2 - Crittografia antica ..................................................................................................................... 13

Crittografia antica

2.1 - Scitala ............................................................................................................................................................13

2.2 - Atbash, Albam e Atbah ..................................................................................................................................13

2.2.1 - Atbash ............................................................................................................................ 14

2.2.1 - Albam............................................................................................................................. 14

2.2.1 - Atbah.............................................................................................................................. 14

2.3 - Cifrario di Cesare..........................................................................................................................................14

2.4 - Cifrature monoalfabetiche.............................................................................................................................15

2.4.1 - Analisi delle frequenze ................................................................................................... 16

3 - Crittografia medioevale ............................................................................................................ 17

Crittografia medioevale

3.1 - Cifrature polialfabetiche ...............................................................................................................................17

3.1.1 - Cifrario di Vigènere........................................................................................................ 17

3.1.2 - Test di Kasiski................................................................................................................ 20

3.1.3 - Ricerca per profilo.......................................................................................................... 20

3.1.4 - Indice di mutua coincidenza ........................................................................................... 21

Presente..............................................................................................................................23

4 - Prima guerra mondiale ................................................................................................................ 25

Prima guerra mondiale

4.1 - Introduzione...................................................................................................................................................25

4.2 - Il telegramma di Zimmermann ......................................................................................................................25

4.3 - La cifratura adfgvx ........................................................................................................................................28

5 - Cifratura a blocco monouso ...................................................................................................... 31

Cifratura a blocco monouso

5.1 - One Time Pad ...............................................................................................................................................31

5.1.1 - Cifrario di Vernam ......................................................................................................... 32

5.1.2 - Sicurezza ........................................................................................................................ 33

5.1.3 - Chiavi casuali ................................................................................................................. 33

5.1.4 - Scambio di chiavi ........................................................................................................... 34

6 - Enigma ............................................................................................................................................ 35

Enigma

6.1 – Struttura, funzionamento, utilizzo.................................................................................................................35

6.2 - Attacco ad Enigma.........................................................................................................................................41

6.2.1 - Crittoanalisti polacchi..................................................................................................... 41

6.2.2 - Crittoanalisti britannici................................................................................................... 48

6.3 - Enigma navale ...............................................................................................................................................53

7 - “Code Talkers”............................................................................................................................. 55

Code Talkers

8 - La fine del secondo conflitto .................................................................................................... 59

La fine del secondo conflitto

9 - Crittografia e informatica ......................................................................................................... 61

Crittografia e informatica

10 - Distribuzione delle chiavi ........................................................................................................ 65

Distribuzione delle chiavi

11 - Crittografia a chiave pubblica ................................................................................................ 69

Crittografia a chiave pubblica

11.1 - RSA...............................................................................................................................................................69

11.1.1 - Sicurezza ...................................................................................................................... 71

11.1.2 - Considerazioni.............................................................................................................. 72

12 - La crittografia al servizio di tutti ......................................................................................... 73

La crittografia al servizio di tutti

Futuro ..................................................................................................................................75

13 - Fisica quantistica ....................................................................................................................... 77

Fisica quantistica

14 - Crittografia quantistica ............................................................................................................ 79

Crittografia quantistica

15 - Algoritmo BB84 ......................................................................................................................... 83

Algoritmo

16 - Conclusioni ................................................................................................................................. 87

Conclusioni

A ............................................................................................................................................. 89

Appendici

A - Tavola delle frequenze ................................................................................................. 91

Tavola delle frequenze

B - Prime macchine cifranti .................................................................................................. 93

Prime macchine cifranti

C - Indici di mutua coincidenza ............................................................................................ 97

Indici di mutua coincidenza

D - Codice alfabetico Navajo .............................................................................................. 99

Codice alfabetico Navajo

E - Cifratura a blocchi ....................................................................................................... 101

Cifratura a blocchi

F - Aritmetica modulare .................................................................................................... 105

Aritmetica modulare

G - Algoritmo di Euclide .................................................................................................... 107

Algoritmo di Euclide

H - Algoritmo BB84 ............................................................................................................ 109

Algoritmo

..................................................................................................................................... 111

Bibliografia

1 - Premesse

Premesse

1.1 - Introduzione

Per migliaia di anni il problema di celare e trasmettere informazioni era reso urgente per questioni di ordine pubblico e militare, oggi non se ne può fare a meno: il pagamento elettronico, l’accesso ad un terminale e l’acquisto on-line sono alcuni aspetti che rendono indispensabile la segretezza nei dati trasmessi. È necessario preservare informazioni che per motivi di varia natura siano trasmesse attraverso canali di comunicazione non sicuri se non, addirittura, pubblici.

Le tecniche usate si distinguono in due grandi gruppi: la steganografia e la crittografia. Il suffisso dei due termini è lo stesso, grafia (dal greco γ ρ α φ ω), scrivere; la scrittura è quindi il contesto operativo, oggi si va oltre il problema di scrivere abbracciando campi più vasti.

1.2 - Steganografia

Steganografia

La steganografia (dal greco σ τ ε γ α ν ο σ, steganos: coperto) ha il compito di salvaguardare l'informazione contenuta in un messaggio, nascondendone non tanto il significato ma l'esistenza stessa.

Erodoto (v secolo a.C.) racconta una bizzarra tecnica steganografica persiana: i messaggi non urgenti venivano tatuati sulle teste rasate di schiavi, una volta ricresciuti i capelli, lo schiavo veniva inviato al destinatario che provvedeva a rasarlo e a leggere il testo.

[1]

Altri metodi sfruttavano le tavolette usate per la scrittura: grattata via la cera il messaggio veniva inciso sul supporto di legno e riversata nuova cera per riportare la tavoletta nelle condizioni iniziali senza dar adito ad alcun sospetto.

Metodo utilizzato ad Demarato per avvertire gli ateniesi dell’attacco persiano ad opera di Serse, il Re dei re, il 23 settembre 480 a.C. - Erodoto, “Storie”. 7

1

Il destinatario, per leggere il messaggio, doveva solamente eliminare la cera grattandola via.

In Cina si scriveva su striscioline di seta che venivano appallottolate e coperte di cera, quindi inghiottite dal messaggero.

In Italia, nel XVI secolo, lo scienziato Giovanni Battista della Porta creò un inchiostro a base di allume e aceto con il quale poter scrivere sul guscio di un uovo sodo. L'inchiostro penetra il guscio, senza lasciare traccia, e va a tingere l'albume solidificato.

[2]

Tecniche di steganografia più recenti risalgono alla Seconda guerra mondiale con il microdot, cioè la riduzione di uno scritto alle dimensioni di un punto che veniva nascosto in un innocuo testo (per esempio nel puntino di una ‘i’).

La stenografia è una tecnica molto longeva che dimostra una certa sicurezza; tale sicurezza, e di conseguenza segretezza, è perduta nel momento stesso dell'intercettazione in quanto ad un'attenta perquisizione si può scoprire il messaggio.

1.3 - Crittografia

Crittografia

La crittografia (dal greco krypto, κ ρ υ π τ ο: nascondo) ha il compito di rendere inintellegibile il testo cioè incomprensibile. Si prenda l'esempio di un anagramma: le lettere che compongono il messaggio vengono mescolate ottenendo nuove parole (di senso compiuto o non) che non hanno alcun legame con il messaggio originale.

La crittografia altera il contenuto del messaggio tramite un procedimento concordato tra mittente e destinatario; quest’ultimo, ricevuto il messaggio, dovrà ‘invertire’ il procedimento per ricavare il messaggio originale.

Giovanni Battista della Porta, “Magiæ naturalis sive de miraculis rerum naturalium”, Napoli 1589, libro IV. Tradotto da Demetra Giunti Editore 8

2

Gli anagrammi sono metodi di cifratura fragili perché, con l'aiuto di un dizionario o di un software, è rapido individuare le parole che compongono il messaggio.

1.4 - Terminologia

Terminologia

Prima di esporre i principali metodi di cifratura è necessario definire la terminologia usata: il messaggio originale viene chiamato testo in chiaro o plaintext e verrà indicato con P; quello che si ottiene dopo la cifratura viene chiamato testo cifrato o cyphertext e verrà indicato con C. Inoltre si definisce chiave, k, il parametro utilizzato per svolgere le operazioni di codifica e decodifica.

È necessario che il processo di cifratura/decifratura sia una funzione iniettiva cioè che un plaintext, cifrato con una chiave, generi uno e un solo cyphertext; inoltre, tale cyphertext, una volta decifrato, riporti al plaintext di partenza in modo da garantire una comunicazione senza ambiguità. Una funzione da A a B (f: A → B) è iniettiva se f(x1) = f(x2) implica x1 = x2. Formalmente: siano P l’insieme di tutti i possibili plaintext e C l’insieme di tutti i possibili cyphertext si definisce funzione cifrante da P in C ogni funzione iniettiva e funzione decifrante d: C → P di ogni funzione e: P → C tale che d(e(p)) = p ∀ p ∈ P. Il tutto deve essere valido per ogni chiave del sistema.

In crittografia vige l’uso di scrivere l’alfabeto in chiaro con lettere minuscole, quello cifrante con lettere maiuscole. Analogamente il testo, in chiaro è scritto in caratteri minuscoli, quello cifrato in caratteri maiuscoli. Nella trattazione è rispettata questa convenzione, inoltre la chiave verrà indicata in caratteri minuscoli corsivi.

Altro concetto fondamentale è il concetto di sicurezza, secondo cui un sistema è tanto più sicuro quanto è più improbabile che un’eventuale terza persona entrata in possesso del cyphertext riesca a ricostruire correttamente il plaintext corrispondente senza conoscere la chiave; questa terza persona dovrà quindi provare tutte le possibili chiavi prima di riuscire a leggere il messaggio. Tale tipo di attacco viene indicato come attacco a forza bruta, e per resistergli sarà sufficiente far sì che il sistema abbia così tante chiavi da rendere impossibile il provarle tutte (ciò non è sempre vero, vedi il caso delle cifrature monoalfabetiche).

1.5 - Sicurezza

Sicurezza

Un sistema è sicuro se è improbabile che un’eventuale terza persona, in possesso del cyphertext, riesca a ricostruire il corrispondente plaintext. È possibile classificare tre diversi criteri di per descrivere la sicurezza.

Sicurezza computazionale: un sistema possiede questo tipo di sicurezza se il miglior algoritmo in grado di infrangerlo richiede un numero di operazioni superiore ad N.

Sicurezza dimostrabile: un sistema possiede questo tipo di sicurezza se è possibile dimostrare che romperlo equivale a risolvere problemi di tipo non polinomiale, o meglio, si crede che risolvere il problema ad esso legato sia infattibile.

Sicurezza incondizionata: un sistema possiede questo tipo di sicurezza se è impossibile romperlo anche ammettendo una capacità di calcolo infinita (ad oggi non raggiunta).

Nel 1949, l’ingegnere e matematico statunitense Claude Elwood Shannon, definito il “padre della teoria dell’informazione”, afferma: «Un crittosistema ha sicurezza perfetta se la probabilità di scoprire il plaintext corrispondente ad un cyphertext è la stessa che si ha di indovinare P C, senza sapere nient’altro»; inoltre ricordiamo le parole di Gilles Dubertret «Non abbiate mai una fiducia cieca in un sistema di crittografia».

[3]

C. E. Shannon, “Communication Theory of Secrecy Systems”, Bell Sys Technical Journal, 1949.

3

G. Dubertret, “Initiation à la cryptographie”, Broché, 1999.

4 10

Passato

2 - Crittografia antica

Crittografia antica

2.1 - Scitala

Scitala

Il sistema più antico di crittografia per trasposizione è la scitala dal greco σκυτάλη, bastone. Di questo metodo parla Plutarco che lo data intorno al IX sec a.C. e che venne usato successivamente nelle guerre del Peloponneso (400 a.C.) dallo spartano Lisandro.

La scitala era un bastoncino attorno al quale veniva avvolta una striscia di pelle su cui veniva inciso il messaggio; una volta srotolata la striscia, quest'ultima, veniva inviata al destinatario che, per leggere il messaggio, doveva possedere una scitala dello stesso diametro di quella di partenza, altrimenti le lettere sarebbero risultate sfalsate e il messaggio incomprensibile.

S [5]

Scitala

2.2 - Atbash, Albam e Atbah

Atbash, Albam e Atbah

Nei testi sacri, in particolare nel Vecchio Testamento si trovano descritte tre principali scritture criptate: