Crittografia quantistica

La crittografia quantistica

Gastaldello Nicolò

Liceo Scientifico G.B. Quadri

CST

Classe 5

Anno scolastico 2010-2011

Indice

1 Crittografia 2

1.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.1.1 Vocabolario della crittografia . . . . . . . . . . . . . . . . . 3

1.2 La storia della crittografia . . . . . . . . . . . . . . . . . . . . . 4

1.2.1 Dall'antichità al 1800 . . . . . . . . . . . . . . . . . . . . . . 4

1.2.2 Un attacco crittoanalitico: l'analisi delle frequenze . . 8

1.2.3 Crittografia nella Seconda guerra mondiale . . . . . . . 10

1.3 One Time Pad: il cifrario perfetto . . . . . . . . . . . . . . . . . 13

1.4 La crittografia asimmetrica . . . . . . . . . . . . . . . . . . . . . 16

1.5 Il futuro della crittografia . . . . . . . . . . . . . . . . . . . . . 19

2 Meccanica quantistica 20

2.1 La polarizzazione della luce . . . . . . . . . . . . . . . . . . . . . 20

2.2 La dualità onda-particella . . . . . . . . . . . . . . . . . . . . . . . 23

2.3 Indeterminazione e No Cloning Theorem . . . . . . . . . . . . . . 26

3 Crittografia quantistica 27

3.1 L'algoritmo BB84 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.1.1 Efficienza di BB84 . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.2 Applicazioni tecnologiche . . . . . . . . . . . . . . . . . . . . . . 32

4 Conclusione 33

Bibliografia 34

1

1 Crittografia

1.1 Introduzione

Da sempre, nella storia dell'umanità, è stata l'esigenza di comunicare messaggi segreti, per motivi politici, commerciali o di qualsiasi genere. La segretezza di un messaggio, cioè dell'informazione che si vuole inviare, è quindi un concetto storicamente molto antico.

Si narra che nell'antica Grecia un certo Istieo voleva spingere Aristagora di Mileto a ribellarsi alla dominazione persiana. Non disponendo di un sistema sicuro per comunicargli l'ordine di insorgere, rasò il capo a un servo, vi tatuò dei segni, attese che ricrescessero i capelli e, appena furono ricresciuti, lo mandò ad Aristagora con il solo incarico di invitarlo a radere i capelli al servo e dare un'occhiata alla sua testa. Tale episodio, narrato da Erodoto nelle sue Storie, è il primo esempio storicamente attestato di steganografia, dal greco στεγανός (coperto) e γράφειν (scrivere).

La steganografia si occupa di nascondere sicuramente il messaggio che si vuole inviare, senza però alterarne la forma; l'obiettivo è quindi mantenere nascosta l'esistenza di dati a chi non conosce il modo per estrarli.

Oltre alla steganografia, si sviluppa un'altra tecnica, che avrà molta più fortuna e rilevanza nei secoli futuri fino a divenire una vera e propria scienza con moltissime implicazioni teoriche e pratiche. Tale scienza è la crittografia, termine greco che deriva da κρυπτός (nascosto) e γράφειν (scrivere).

La crittografia è la scienza che si occupa di trasformare un messaggio, fargli assumere un'altra forma, per evitare che chiunque entri in possesso del messaggio, tranne il legittimo destinatario, possa comprenderne il contenuto. L'obiettivo della crittografia è quindi non rendere accessibili i dati nascosti a chi non conosce il modo per ottenerli.

Si presuppone quindi che sia possibile, da parte di un intercettatore comunque non desiderato, entrare in possesso del messaggio. Tale intercettatore, desideroso di ottenere il contenuto del messaggio in una forma a lui comprensibile, deve elaborare tecniche per poter ritrasformare il messaggio di cui è entrato in possesso in quello originale.

Parallelamente alla crittografia si sviluppa quindi la crittoanalisi, cioè lo studio dei metodi necessari per ottenere il messaggio originale in assenza dell'informazione segreta di solito necessaria per fare ciò. La crittografia e la crittoanalisi insieme costituiscono la crittologia, generalmente definita come la scienza delle scritture nascoste.

Si può quindi immaginare come, nel corso della storia, la crittografia e la crittoanalisi si siano evolute l'una insieme all'altra, in quanto nel momento in cui la prima escogitava un metodo per alterare un messaggio la seconda ne individuava uno per riportarlo al contenuto originale. L'ambito strettamente collegato alla loro evoluzione è quello della guerra: è essenziale poter trasmettere messaggi segreti per dare ordini di attacchi, comunicare strategie o stipulare alleanze.

Ai tempi d'oggi la crittografia è essenziale per moltissime applicazioni: commercio elettronico e transazioni bancarie sono i due campi in cui sono maggiormente usati protocolli di cifratura per nascondere dati sensibili, come numeri di carte di credito.

1.1.1 Vocabolario della crittografia

È opportuno introdurre alcuni termini tecnici della crittografia. Osservando la Figura 1 si può vedere uno schema di una comunicazione di un messaggio cifrato tra due utenti.

Figura 1: Schema di una comunicazione cifrata

L'elenco seguente di termini può aiutare a comprendere la Figura 1.

• Mittente: colui che invia il messaggio.
• Destinatario: colui al quale è destinato il messaggio.
• Testo in chiaro: il messaggio originale da inviare, in una forma leggibile a chiunque.
• Cifratura: è l'operazione che trasforma il testo in chiaro in una forma alterata.
• Cifrario: è il complesso di regole e dei documenti necessari per cifrare e decifrare, cioè il metodo con cui viene fatta la cifratura e l'algoritmo usato.
• Chiave: è una stringa di caratteri, lettere o numeri, che consente di passare dal testo in chiaro al testo cifrato e viceversa.
• Testo cifrato: è il testo trasformato, cioè ottenuto dalla cifratura del testo in chiaro.
• Decifratura: è l'operazione che trasforma il testo cifrato nel testo in chiaro.
• Decrittazione: è il procedimento di trasformazione del testo cifrato nel testo in chiaro da parte di una persona non autorizzata, che non conosce quindi la chiave.
• Canale di comunicazione: è il mezzo attraverso il quale viene inviato il messaggio, per esempio cavo di rame, bra o ottica. Si considera generalmente non sicuro.

Nella crittografia esistono sostanzialmente due grandi categorie di metodi di cifratura:

• Crittografia simmetrica o a chiave privata: in questa tecnica la chiave di cifratura coincide con la chiave di decifratura. Tale chiave deve quindi essere in possesso sia del mittente che del destinatario e deve essere segreta.
• Crittografia asimmetrica o a chiave pubblica: in questa tecnica la chiave di cifratura, chiave pubblica, è diversa dalla chiave di decifratura, chiave privata; esiste ovviamente un certo legame tra le due.

1.2 La storia della crittografia

Osservando la distinzione riportata alla fine della sezione precedente, si può osservare che la tecnica maggiormente usata, parlando in senso temporale, è quella della crittografia simmetrica, con moltissimi diversi metodi. La crittografia asimmetrica è infatti una scoperta molto recente se confrontata con quella simmetrica: la prima risale agli anni ’70 del XX secolo mentre la seconda ha origini antichissime, cioè molti secoli avanti Cristo.

1.2.1 Dall'antichità al 1800

La crittografia simmetrica, in generale la crittografia, trova origine nell'antica Grecia, in particolare nella città di Sparta. Come riporta lo storico Tucidide nella sua Guerra del Peloponneso, gli spartani avevano inventato un sistema passato alla storia come scitala.

Figura 2: Scitala spartana

Come si può vedere dalla Figura 2, la scitala era un bastone di un certo diametro attorno al quale veniva avvolto un pezzo di stoffa su cui veniva scritto il messaggio da inviare. In questo modo, una volta srotolato il pezzo di stoffa, il messaggio risultava incomprensibile in quanto la lettura avverrebbe verticalmente e non orizzontalmente, cosa possibile solo quando il pezzo di stoffa viene arrotolato attorno a un bastone.

Ovviamente, affinché il messaggio si ricomponga in modo esatto, è necessario un bastone dello stesso diametro di quello su cui è stato scritto; se no non ci sarebbe la giusta sequenza di lettere.

La scitala è il più antico metodo di cifratura conosciuto.

La cifratura per trasposizione è un metodo nel quale sostanzialmente viene fatto un anagramma del messaggio da inviare secondo uno schema prestabilito. Il testo cifrato è quindi una permutazione del testo in chiaro.

Considerando quindi un messaggio lungo n caratteri, il numero di permutazioni possibili è uguale a n!. Si può quindi intuire come, all'aumentare della lunghezza del messaggio, aumenti in modo vertiginoso il numero di anagrammi possibili.

Esempio. Per n = 4, 4! = 24; per n = 20, 20! ≈ 10¹⁸.

Lo schema di cifratura deve essere condiviso sia dal mittente sia dal destinatario, affinché quest'ultimo possa trasformare il cifrato nel testo in chiaro. Deve essere tenuto nascosto in quanto la conoscenza delle regole di cifratura permetterebbe subito ad un intercettatore di decrittare il messaggio.

Due esempi di cifrari a trasposizione sono la Scacchiera di Polibio, risalente al III secolo a.C., e il cifrario di Playfair, del 1854 e ispirato al primo. Tali sistemi sono più complessi di una trasposizione semplice; utilizzano infatti una tabella in cui viene inserita una parola chiave secondo la quale verrà cifrato il messaggio.

L'altro metodo principale di cifratura in uso nell'antichità era quello della sostituzione monoalfabetica. Esistono due tipi di sostituzione, quella monoalfabetica e quella polialfabetica.

La sostituzione monoalfabetica consiste nel sostituire ad ogni simbolo del messaggio originale un diverso simbolo, in modo che a simboli differenti corrispondano simboli differenti. Il nome deriva dal fatto che per cifrare viene usato un solo alfabeto cifrante, cioè una chiave che è una permutazione dell'alfabeto del messaggio originale.

Sono quindi possibili, considerando l'alfabeto italiano di 21 lettere, 21! chiavi diverse, circa 10¹⁹.

Tale numero è enorme ma, come si vedrà, non è assolutamente garante di segretezza del messaggio.

Uno dei cifrari a sostituzione semplice più famosi è il codice Cesare. Come dice il nome, tale codice fu inventato da Giulio Cesare per le proprie corrispondenze; tale sistema fu usato, con opportuni miglioramenti, per tutto il millennio successivo.

Tale codice consiste nel mutare ogni lettera del messaggio originale con la terza lettera ad essa successiva nell'alfabeto, per esempio la a con la d e così via, come riportato nello schema sottostante:

a b d e f g h i l m n o p q r s t u v z

D E F G H I L M N O P Q R S T U V Z A B C

In questo modo, il messaggio CODICE SEGRETO diventa FRGNFH VHLUHZR. Venendo a conoscenza dell'alfabeto cifrante, la decifratura è immediata: basta sostituire a ogni lettera la lettera che la precede di 3 posizioni nell'alfabeto.

Il metodo della sostituzione polialfabetica è una variante di quello appena descritto. In questo metodo si sostituisce sempre una lettera con un'altra, ma alla singola lettera del testo chiaro non corrisponde sempre la stessa lettera nel cifrato, in quanto l'alfabeto cifrante viene cambiato di volta in volta, secondo una qualche regola convenuta.

In questo modo ad una singola lettera nel testo in chiaro ne corrispondono più di una in quello cifrato e una stessa lettera del cifrato corrisponde a diverse lettere originali. Due dei sistemi più famosi di sostituzione polialfabetica sono il disco cifrante di Leon Battista Alberti e la tavola di Vigenère.

Il primo, inventato tra il 1460 e il 1470, è composto da una coppia di cerchi concentrici imperniati in modo tale che il cerchio interno possa ruotare mentre quello esterno sia fermo. Sul cerchio esterno sono presenti le lettere dell'alfabeto. Il cerchio interno è la chiave di cifratura; ruotandolo, la si può quindi cambiare ogni volta che si desidera.

Per ottenere la lettera cifrata si ruota di un certo grado il disco interno e si osserva la lettera sul cerchio interno che viene a trovarsi in corrispondenza della lettera da cifrare posta sul cerchio esterno, come nella Figura 3.

Figura 3: Disco cifrante di Leon Battista Alberti

La tavola di Vigenère fu proposta nel 1586 da Blaise de Vigenère; tale sistema fu utilizzato, con alcune varianti, fino alla fine della Prima guerra mondiale. Essa deriva dalla Tabula recta di Trithemius, un abate tedesco del 1400.

Figura 4: Tavola di Vigenère

Come si può osservare dalla Figura 4, la tavola è costituita da una tabella di dimensioni n × n, dove n è la lunghezza dell'alfabeto. Le lettere che stanno nella prima riga in alto sono quelle del messaggio originale, mentre quelle nella prima colonna a sinistra sono quelle che individuano ognuna una diversa chiave.

Ogni volta che si deve cifrare una lettera, si sceglie quale chiave usare e per ottenere la lettera cifrata si va nella colonna corrispondente alla lettera in chiaro e nella riga corrispondente alla chiave scelta.

Per la sua apparente indecifrabilità essa si guadagnò il nome di chiffre indéchiffrable. Il metodo per violare tale cifrario fu scoperto nel 1863 dal maggiore prussiano Friedrich Kasiski.

Il disco cifrante di Alberti e la tavola di Vigenère sono due metodi che hanno sicuramente una sicurezza più elevata rispetto a quelli precedentemente usati, cioè trasposizione e sostituzione monoalfabetica, per i motivi elencati nel prossimo paragrafo.

1.2.2 Un attacco crittoanalitico: l'analisi delle frequenze

I metodi della trasposizione e della sostituzione semplice, monoalfabetica, descritti nella sezione precedente, nonostante possano sembrare garantire una buona segretezza, hanno in realtà entrambi un grosso punto debole, che permette ad un eventuale intercettatore di decrittare il messaggio cifrato con estrema facilità, anche se questo non è in possesso della chiave di cifratura.

Il metodo più semplice, solamente dal punto di vista logico, per decrittare un messaggio cifrato con un metodo a trasposizione o sostituzione semplice, è tentare tutte le soluzioni possibili, cioè gli anagrammi del messaggio cifrato, fino a quando non si ottiene il messaggio corretto.

Tale metodo prende il nome di attacco a forza bruta o ricerca esaustiva della soluzione. Teoricamente permette sempre di trovare la soluzione, ma sostanzialmente è di difficile utilizzo in quanto presenta gravi difetti: è lento e dispendioso.

Infatti, come si è visto precedentemente, il numero di permutazioni possibili per un messaggio di n caratteri è uguale a n!. Cercare tutte le soluzioni equivale quindi a provare un numero enorme di combinazioni possibili, cosa molto faticosa e assolutamente lenta.

In passato, quando non c'erano né dispositivi elettromeccanici né elaboratori elettronici che potessero trovare tutte le permutazioni grazie a degli algoritmi, l'unico procedimento era quello di cercare le combinazioni a mano; per questo tale metodo non è utilizzabile.

È dal mondo arabo che proviene la soluzione per decrittare i messaggi cifrati; lo scienziato e teologo Al-Kindi, dopo essersi occupato per anni di studi coranici relativi alle strutture fonetico-linguistiche delle parole di Maometto, pubblicò nel IX secolo un trattato, il Manoscritto sulla decifrazione dei messaggi crittati.

In esso è inclusa la descrizione del metodo più utilizzato per decrittare tale tipo di messaggi in codice: il metodo dell'analisi delle frequenze. Esso si basa sulla considerazione che, in qualsiasi lingua, le lettere sono presenti con una certa frequenza piuttosto determinata e diversa tra le varie lettere, come nella Figura 5.

Figura 5: Frequenza delle lettere nella lingua italiana

Per esempio, nella lingua italiana le lettere a, e ed i sono sicuramente più frequenti di b, q e z. In un testo sufficientemente lungo, la frequenza delle lettere presenti tende a quella definita; in un testo breve le frequenze sono invece un po' più diverse da quelle previste.

Con questo metodo, come si può intuire, risulta abbastanza facile e in alcuni casi immediato rompere tali cifrature. Infatti, se il testo da decrittare non è troppo corto e si conosce la lingua originale, è sufficiente calcolare le frequenze con cui compaiono i vari simboli per associarli alle occorrenze delle lettere dell'alfabeto della lingua di provenienza.

Per esempio, si potrebbe ottenere tale distribuzione delle frequenze in un testo cifrato:

Figura 6: Frequenza delle lettere nel messaggio cifrato

Si può quindi supporre che le lettere d e l nel testo cifrato corrispondano alle lettere e ed u del testo in chiaro. Per trovare la giusta corrispondenza si procede per tentativi.

Si nota che tale metodo è di più difficile applicazione in testi cifrati con sostituzioni polialfabetiche: in questo caso infatti la frequenza delle lettere risulta appiattita perché non c'è una corrispondenza biunivoca tra le lettere del cifrato e le lettere del chiaro, ma ad ogni lettera ne corrisponde più di una. Per rompere tali cifrari servono quindi metodi più complessi.

1.2.3 Crittografia nella Seconda guerra mondiale