CTX - 01 - Introduzione

1 Informazioni Lezione

Data: [2018-03-07 mer]

In questa lezione sono stati introdotti i concetti fondamentali studiati dalla crittografia, andando a far vedere i primi esempi di cifrari che sono stati utilizzati nel corso della storia. La lezione si è chiusa discutendo le problematiche dei cifrari classici, e di come la crittografia utilizza nel mondo moderno, la crittografia a chiave pubblica, ha permesso una diffusione mai vista prima di metodi per proteggere le informazioni.

2 Cosa Studia la Crittografia?

La crittografia studia una serie di tecniche e metodologie che permettono lo scambio sicuro di messaggi tra un mittente e un destinatario. Questo scambio di messaggi deve essere "sicuro" nel senso che deve garantire determinate caratteristiche. Tra queste caratteristiche troviamo il fatto che, nel caso in cui il messaggio inviato si perde e finisce in mani ignote, nessun individuo oltre al destinatario ed eventualmente colui che l'ha inviato, è in grado di leggere il messaggio. In altre parole, a meno di non conoscere il metodo utilizzato per rendere sicuro il messaggio cifrandolo, estrarre il significato da un messaggio cifrato deve essere un'operazione talmente difficile e costosa che risulta praticamente impossibile da effettuare.

Il bisogno di progettere le informazioni è sempre stato vivo e attivo fin da quando abbiamo inventato la scrittura. Documenti storici ci permettono di stabilire che tecniche per proteggere le informazioni contenute nei messaggi furono utilizzate anche nelle Guerre Greco-persiane, intorno al 500 BCE. Erodio infatti ci racconta di come determinati schiavi venivano rasati a zero per poter scrivere segreti nella loro teste; una volta ricresciuti i capelli venivano poi utilizzati come mezzi di trasporto per spedire i segreti ai destinatari.

Inizialmente i metodi più utilizzati per proteggere le informazioni tentavano di nascondere le informazioni, piuttosto che modificarle per renderle inaccessibili agli estranei. L'area di studi che si occupa di tecniche per nascondere i messaggi in modo che non vengano scoperti prende il nome di stenografia. La stenografia è parallela alla crittografia, e anche se entrambe le discipline possono essere utilizzare per aumentare il livello di sicurezza, esse rimangono comunque indipendenti tra loro.

Parallelamente ai metodi per proteggere i segreti durante lo scambio di messaggi, che vengono studiati dalla crittografia, troviamo anche i metodi inversi, cioé quei metodi e tecniche che cercano di estrapolare, in qualsiasi modo possibile, il segreto dal messagio. Lo studio di questi metodi prende il nome di crittoanalisi.

3 Cifrario di Cesare

Un primo esempio di schema di cifratura di un messagio è il famoso cifrario di Cesare. Il cifrario di Cesare si basa sul concetto di permutare le lettere dell'alfabeto.

Supponiamo di avere due persone, $A$ e $B$. $A$ vuole inviare un messagio a $B$ e vuole proteggere il significato del messagio, magari perché contiene informazioni militari altamente importanti. Il messagio da inviare è composto da una serie di simboli presi da un particolare alfabeto $\Sigma$. Per la seguente discussione assumiamo che $\Sigma$ sia il comune alfabeto inglese $\Sigma = \{a, b, c, d, ..., w, x, y, z\}$. Notiamo a questo punto che a noi non interessano i particolari simboli utilizzati. L'unica cosa che ci interessa è che abbiamo un certo numero di simboli diversi. Possiamo quindi assegnare ad ogni simbolo un numero in modo tale che a simboli diversi corrispondano numeri diversi. Una volta stabilita questa associazione tra numeri e caratteri possiamo scartare l'alfabeto $\Sigma$ e utilizzare solamente un appropriato insieme di numeri.

Un modo banale e intuitivo per ottenere questa associazione tra caratteri e numeri è il seguente: alla $a$ assegno lo $0$, a $b$ assegno $1$, etc..., continuando fino a $z$ a cui viene assegnato il numero $25$. Il nostro nuovo alfabeto è quindi il famoso insieme quoziente modulo 26, $\mathbb{Z}_{26} = \{0, 1, ..., 25\}$. A seguire quindi consideriamo $a$, $0$ e tutte le altre lettere con i rispettivi numeri come la stessa cosa.

In questo schema, la chiave di cifratura dello schema crittografico, ovvero l'oggetto che ci permette di passare dal segreto al messagio cifrato da inviare, è una determinata permutazione $\sigma$ di $\mathbb{Z}_{26}$. L'idea alla base è infatti abbastanza naturale: devo nascondere il significato di un messagio? Bene, quello che posso fare è assegnare ad ogni simbolo distinto del messagio da inviare (il segreto, la cosa da proteggere), un altro simbolo. Posso quindi trasformare tutte le $a$ in $d$ e tutte le $f$ in $h$, oppure tutte le $a$ in $z$ e tutte le $f$ in $q$. Insomma, ci sono tanti modi e ciascuno di essi ci permette di passare da un qualsiasi messagio ad un messagio diverso.

Andiamo adesso ad analizzare generalmente come vengono effettuate le due operazioni fondamentali di codifica e decodifica in questi schemi di cifratura a permutazione.

3.1 Cifratura a Permutazione

Lo schema appena discusso può essere modellato matematicamente come segue:

La parola da cifrare è rappresentata come una sequenza di valori

\[x_1, ..., x_n \in \{0, 1, ..., 25\} = \mathbb{Z}_{26}\]
La chiave di cifratura è una permutazione di $\mathbb{Z}_{26}$

\[\sigma: \mathbb{Z}_{26} \to \mathbb{Z}_{26}\]
L'operazione di cifratura della parola $p = x_1, ..., x_n$ è effettuata come segue

\[\text{Cifra}(p) = \sigma(x_1), ..., \sigma(x_n)\]
L'operazione di decifrazione della parola cifrata $p = y_1, ..., y_n$ è effettuata come segue

\[\text{Decifra}(p) = \sigma^{-1}(y_1), ..., \sigma^{-1}(y_n)\]

Notiamo quindi che per cifrare utilizzo la permutazione $\sigma$, mentre per decifrare sono costretto a calcolarmi l'inversa $\sigma^{-1}$ (esiste sempre in quanto $\sigma$ è una biiezione).

Una condizione importante che voglio avere nel contesto di un sistema di cifratura è la seguente: voglio un sistema in cui la procedura di cifratura, ovvero la trasformazione di un segreto in un messagio cifrato, sia facile da eseguire, mentre la procedura inversa, quella che mi permette di ottenere il segreto partendo dal messagio cifrato, assumendo di non possedere la chiave, sia estremamente difficile. Questa condizione è fondamentale, in quanto è proprio ciò che mi permette di stare tranquillo nel caso in cui un agente esterno dovesse accidentalmente (o, più probabilmente, intenzionalmente) ottenere un messagio destinato a me, oppure inviato da me: essendo appunto un agente esterno, possiamo supporre che non possiede la chiave che ho utilizzato per la cifratura del messagio, e quindi, se è davvero difficile decifrare il messagio quando non si ha la chiave, allora non sarà possibile per questo agente esterno decifrare il messagio e scoprire il segreto che volevo inviare.

L'approccio utilizzato dallo schema di cifratura utilizzato da cesare per rendere facile la cifratura e difficile la decifrazione è il seguente:

La chiave è rappresentata da un certo intero $c \in \mathbb{Z}_{26}$.

La permutazione utilizzata per cifrare è definita come segue

\[ \sigma(x) := (x + c) \mod 26 \,\,\,\,,\,\,\, \forall x \in \mathbb{Z}_{26} \]
La permutazione inversa, quella utilizzata per decifrare, è definita come segue

\[ \sigma^{-1}(x) := (x - c) \mod 26 \,\,\,\,,\,\,\, \forall x \in \mathbb{Z}_{26} \]

Se $c = 5$, abbiamo che $\sigma(0) = 5$, e quindi il simbolo $a$ viene sostituito con il simbolo $f$. Notiamo che questo sistema non è "difficile" da rompere, in quanto abbiamo solamente 26 possibili chiavi, e quindi ci basterebbe provarle tutte per scoprire quella giusta.

3.2 Possibili Raffinazioni

Una possibiel raffinazione al cifrario di Cesare utilizza il fatto che in $\mathbb{Z}_{26}$ non solo possiamo sommare i numeri, ma li possiamo anche moltiplicare tra loro. In particolare quindi lo schema viene trasformato come segue

La chiave adesso è rappresentata da due interi $h, c \in \mathbb{Z}_{26}$.

La permutazione utilizzata per cifrare è definita come segue

\[\sigma(x) := (h \cdot x + c) \mod 26 \,\,\,\,,\,\,\, \forall x \in \mathbb{Z}_{26}\]
La permutazione inversa, quella utilizzata per decifrare, è definita come segue

\[\sigma^{-1}(x) := (x - c) \cdot h^{-1} \mod 26 \,\,\,\,,\,\,\, \forall x \in \mathbb{Z}_{26}\]

Bisogna osservare che, in questo caso, non è detto che $h^{-1}$ esiste in $\mathbb{Z}_{26}$. Infatti è possibile dimostrare la seguente proposizione

Proposizione: L'inverso di $a \in \mathbb{Z}_{n}$ esiste se e solo se $gcd(a, n) = 1$

Dimostrazione: Supponiamo che $b \in \mathbb{Z}_{n}$ sia l'inverso di $a$. Dalla definizione di inverso abbiamo che $a \cdot b = 1 \mod 26$. Ora, se se indichiamo con $gcd(a, b)$ il massimo comun divisore tra $a$ e $b$, abbiamo che, fissato un certo $h \in \mathbb{Z}_{n}$

\[\forall x \in \mathbb{Z}_{n}: gcd(h, n) \mid h \cdot x \mod n\]

Questo segue dal semplice fatto che $h \cdot x \mod n$ può essere scritto nella forma $h \cdot x + n \cdot k$. Ma quindi, se dovessimo avere che, per qualche $y \in \mathbb{Z}_{26}$, $h \cdot y = 1 \mod n$, allora avremmo anche che $gcd(h, n) \mid 1$, e quindi $gcd(h, n) = 1$.

D'altra parte, se $gcd(a, n) = 1$, allora mi posso scrivere, per qualche $x, y \in \mathbb{Z}_{n}$, $gcd(a, n) = a \cdot x + n \cdot y = 1$, e quindi $a \cdot x = 1 \mod n$, ovvero $x$ è l'inverso di $a$.

\[\tag*{$\blacksquare$}\]

Altre possibili raffinazioni agli schemi di cifrazione basati sulla permutazione dei simboli sono state apportate nelle seguenti date.

Leon Battista Alberti (1400 CE)
Vigenère (fine 1500, inizio 1600 CE)
Macchina enigma (Seconda Guerra Mondiale - 1939-1945 CE)

Per finire l'introduzione di questa tipologia di schemi di cifratura, è importante notare che una debolezza fondamentale di questi sistemi è il fatto che si basano sui simboli utilizzati nei linguaggi naturali. È oramai risaputo che le lettere dei nostri linguaggi naturali non hanno la stessa frequenza di utilizzo (vedi Legge di Zipfs): alcune lettere sono più frequenti di altre. Questa caratteristicha, inevitabilmente, introduce informazioni cruciali che i crittoanalisti più furbi e geniali possono utilizzare per rompere lo schema.

3.2.1 Cifrario di Vernam

Il cifrario di Vernam è sempre un cifrario basato sul concetto di permutazione dell'insieme delle lettere (o numeri che codificano lettere). A differenza di tutti gli altri però, per il cifrario di Vernam esiste una dimostrazione matematica della sua sicurezza teorica.

Il cifrario di Vernam si basa sulla scelta di una chiave lunga quanto il testo da cifrare e inoltre impone che la chiave venga utilizzata una volta sola: per ogni messagio diverso dobbiamo quindi accordarci con il destinatario sulla chiave utilizzata. Per questa ragione il cifrario di Vernam, anche se teoricamente perfetto, è praticamente inutile.

4 Crittografia Moderna

Lo scenario di utilizzo della crittografia è sempre stato o militare, o scientifico/industriale. Questo almeno fino all'avvento dei calcolatori. Dal 1950 in poi la crittografia è stata sempre più utilizzata, e continua a esserlo, per scopi "quotidiani", intendendo con ciò tutto quello che potrebbe fare un cittadino comune tramite il Web: comprare online un libro, un gioco, gestire il conto bancario online, e via dicendo.

Subendo questo importante cambiamento di contesto, la crittografia si è dovuta adeguare a nuovi scenari, scenari in cui un tipo di crittografia come quella utilizzata da Cesare è praticamente inutile. La crittografia moderna infatti ha a che fare con il mondo del Web. Il compito fondamentale non è più quello di proteggere un numero abbastanza limitato di messagi, bensì quello di dare sicurezza ai milioni di scambi di informazione che avvengono ogni minuto tra svariati utenti. Non solo è aumentato il carico di lavoro da gestire, ma anche il modo in cui questi messagi vengono inviati e ricevuti è diverso: gli utenti che partecipano allo scambio dei messagi non è detto che si conoscano, anzi, il più delle volte queste transazioni avvengono tra utenti ignari di tutto ciò.

Da questo bisogno nasce la crittografia a chiave pubblica. In questa nuova forma di crittografia, la chiave non è unica, ma viene spezzata in due: una serve per cifrare il messagio, e prende il nome di chiave pubblica; l'altra serve per decifrare il messagio cifrato, e prende il nome di chiave privata. Nella crittografia a chiave pubblica, la chiave pubblica è appunto, pubblica, e ognuno può, e anzi deve, accedere alla chiave pubblica degli altri utenti. Quello che resta privato è solamente la chiave privata, che è la chiave utilizzata nella decifrazione dei messagi.

4.1 Funzione Trappola

La crittografia a chiave pubblica si basa sul concetto di funzione trappola. Brevemente, una funzione trappola è una biiezione da un insieme $X$ a se stesso, con la proprietà che è "facile" da calcolare, ma tale che è "difficile" calcolarne l'inversa.

Ad esempio, se $X = \mathbb{Z}_{p}$, con $p$ primo abbastanza grande per codificare tutti i simboli del nostro alfabeto, una funzione trappola è data da un polinomio $P(x) \in \mathbb{Z}_{p}[x]$.

5 Complessità di un Algoritmo

Ogni volta che facciamo riferimento a determinate proprietà di funzioni, come ad esempio quella di essere "facilmente" calcolabile, o, andando nella direzione opposta, di essere "difficile" da calcolare, ci stiamo riferendo al numero di operazioni elementari che quella funzione richiede per poter essere calcolata.

Osserviamo che ogni funzione, per poter essere effettivamente calcolata, necessità di un modello di calcolo, ovvero di un ambiente di lavoro, fisico o teorico, che specifichi quali sono le operazioni "elementari" che possono essere eseguite immediatamente, senza necessitare di altri passi. Avendo un modello di calcolo a disposizione, e sapendo quindi quali sono le operazioni elementari, possiamo quindi definire i concetti di complessità di un algoritmo e di tempo di attuazione di un algoritmo.

Definizione: La complessità di un algoritmo è intesa come il numero di operazioni elementari previste dall'algoritmo.

Definizione: Il tempo di attuazione di un algoritmo è definito come il periodo di tempo fisico necessario alla macchina, da quando viene messa in azione, per terminare.

Notiamo che la complessità di un algoritmo non dipende dalla particolaretecnologia utilizzata per implementare la macchina su cui l'algoritmo viene eseguito, ma è una proprietà inerente l'algoritmo. Il tempo di esecuzione, invece, dipende dalla complessità dell'algoritmo e anche dalla tecnologia utilizzata per implementare il calcolatore su cui si vuole eseguire l'algoritmo.

Sia $ALG$ un algoritmo qualunque, abbiamo la seguente relazione tra la complessità dell'algoritmo e il suo tempo di esecuzione:

\[\text{Tempo}(ALG) = c \cdot \text{Complessità}(ALG)\]

Quando diciamo "facile da calcolare", stiamo quindi intendendo che la complessità deve essere "bassa". Se invece parliamo di "difficile da calcolare", vogliamo avere una complessità molto alta.

Il modello di calcolo per antonomasia è la Macchina di Turing, introdotta dal matematico inglese Alan Turing nel 1936 per risolvere il problema della decisione (che all'epoca veniva chiamato col suo nome tedesco: Entscheidungsproblem). Tale macchina è essenzialmente sequenziale, ovvero esegue una operazione elementare alla volta. Conseguentemente, tutti i metodi di crittografia moderni, sono basati sul fatto che le macchine moderne, essendo implementazioni fisiche di macchine di Turing, sono anch'esse sequenziali.

Un modello di calcolo altamente diverso invece è costituito dal computer quantistico. Il computer quantistico, come suggerisce il nome, utilizza i principi fondamentali della meccanica quantistica per riuscire ad eseguire più operazioni elementari nello stesso momento, andando quindi ad eseguire una computazione parallela, che permette di ottenere un forte beneficio temporale rispetto a quello che potrebbe fare una macchina di Turing. Se questi computer dovessero diventare commerciali--e questo non si sa effettivamente se succederà, anche se si stanno facendo degli sforzi, sia teorici che pratici, verso quella direzioni--tutti i protocolli crittografici utilizzati nella società moderna dovranno essere ripensati, in quanto diventerebbero immediatamente inutili. Detto questo, si è già sviluppata una branca della crittografia che prende il nome di crittografia quantistica, e che ha già scoperto un metodo per utilizzare le proprietà quantistiche al fine di effettuare lo scambio di chiavi di Vernam in modo sicuro. In ogni caso, i computer quantistici hanno ancora oggi molte problematiche, tra cui il fatto che sono molto suscettibili a interazioni esterne con l'ambiente. Queste interazioni provocano gravi errori e perdita di precisione nella memoria della macchina, e quindi pongono un grave problema ad una potenziale implementazione.