CTX - 08 - Cifrari a Chiave Pubblica I

1 Informazioni Lezione

Data: [2018-03-29 gio]

Nella lezione scorsa abbiamo visto alcuni dei più famosi cifrati classici, basati principalmente sulla permutazione dei simboli di un alfabeto. Più volte abbiamo menzionato il fatto che questi cifrari sono vulnerabili all'analisi delle frequenze. Questa vulnerabilità rende i cifrari classici inutilizzabili al fine di proteggere le comunicazioni moderne. Questa lezione sarà quindi concentrata su una diversa tipologia di cifrari, i cosiddetti cifrari a chiave pubblica.

2 Funzioni Trappola

I cifrari a chiave pubblica si differenziano dai cifrari classici per il fatto che sono basati sul concetto di funzione trappola. Intuitivamente una funzione trappola è una funzione definita su insiemi numerici, che è "facile" da calcolare ma "difficile" da invertire, dove i termini "facile" e "difficile" fanno riferimento alle risorse computazionali richieste.

Proviamo adesso a rendere più concreto e formale questo concetto di funzione trappola. Sia $f:A \to B$ una funzione biettiva tra due insiemi numerici $A$ e $B$. Diciamo che $f$ è una funzione trappola se e solo se valgono le seguenti cose:

$\forall a \in A$ esiste un algoritmo polinomiale che calcola $f(a)$.
Conoscendo $b \in B$ non esiste un algoritmo polinomiale che, utilizzando solamente $b$ sia in grado di calcolare $f^{-1}(b)$. Il calcolo di $f^{-1}(b)$ può essere effettuato velocemente solamente utilizzando qualche informazione extra, che tipicamente viene mantenuta segreta.

Osserviamo che una funzione trappola deve comunquere essere invertibile. Quello che richiediamo è che il calcolo della funzione inversa necessita di una qualche informazione extra, informazione che generalmente verrà mantenuta segreta, e verrà utilizzata solamente quando si è interessati a decifrari i messaggi.

Se invece rilassiamo la seconda richiesta, ovvero se non chiediamo che la funzione inversa possa essere calcolata conoscendo informazioni extra, allora otteniamo una funzione univoca. Una funzione univoca è quindi facile da calcolare, ma praticamente impossibile da invertire, indipendentemente da quante informazioni abbiamo. Un esempio di funzione univoca è la funzione SHA-256.

Osservazione: tutta la letteratura della crittografia moderna è invasa di frasi della forma: "è praticamente impossibile fare una cosa x". Cosa intendiamo con "praticamente"? Essenzialmente stiamo intendendo che, fino a questo momento, nessuno è riuscito a trovare un modo efficente (polinomiale) per fare quella determinata cosa, e inoltre che nessuno è stato in grado di dimostrare che non esiste un modo efficente per fare quella determinata cosa. Questo essenzialmente significa che la sicurezza della maggior parte dei sistemi crittograficitali sistemi è basata principalmente sulla nostra ignoranza, piuttosto che a qualche risultato teorico.

Le funzioni univoche a noi non interessanto tanto, in quanto siamo interessati a calcolare l'inversa $f^{-1}$ in un tempo decente. In ogni caso, andiamo a vedere un esempio di funzione univoca.

2.1 Esempio di Funzione Univoca

Poniamo $P := 2^{64} - 59$ e notiamo che $P$ è un numero primo. Consideriamo poi la seguente funzione $f: \mathbb{Z}_p \to \mathbb{Z}_p$ definita da

\[f(x) := x^{2^{24} + 17} + a_1x^{2^{24} + 3} + a_2x^3 + a_3x^2 + a_4x + a_5\]

con $a_1, a_2, a_3, a_4, a_5$ numeri arbitrari con almeno $19$ cifre decimali.

Come possiamo vedere, $f$ permuta gli elementi di $\mathbb{Z}_p$ in un modo molto strano. È stato dimostrato che $f$ è una funzione univoca, ovvero fino ad adesso non sono stati trovati algoritmi che siano in grado di calcolare $f^{-1}(x)$ in tempo polinomiale.

3 Cifrari Esponenziali

I cifrari esponenziale sono basati, come indica il nome, sulla esponenziaione modulare, e consistono nel seguende modello matematico:

$P$ è un numero primo molto grande, $P >> 0$.
$e \in \mathbb{Z}_p$ tale che $MCD(e, P-1) = 1$ è la nostra chiave per cifrare.
$d \in \mathbb{Z}_p$ tale che $d \equiv e^{-1} \mod P-1$ è la nostra chiave per decifrare.

In questo schema consideriamo messaggi come stringhe numeriche, che possiamo quindi interpretare come dei numeri. I messaggi d'ora in avanti verrano quindi trattati come interi. Il processo di codifica e decodifica tra messaggi e numeri non ci interessa tanto, ci basta solo sapere che l'intero $P$ sia più grande del massimo numero associato ai messaggi.

Per codificare un messaggio $p$ (un intero) e ottenere il messagio cifrato $c$ (nuovamente un intero), eseguiamo la seguente operazione

\[c \equiv p^e \mod P\]

Viceversa, per decifrare il messaggio cifrato $c$ e riottenere il messaggio originario $p$, ci calcoliamo

\[p \equiv c^d \mod P\]

3.1 Correttezza

La prima cosa da domandarci ora è: questo sistema, funzione correttamente? Ovveriamo siamo in grado di invertire il processo? La risposta, per fortuna, è affermativa. Infatti, sapendo che

\[d \equiv e^{-1} \mod P-1 \iff de = 1 + (P-1)h\]

e applicando il piccolo teorema di fermat, otteniamo

\[\begin{split} c^d &\equiv (p^e)^d \mod P \\ &\equiv p^{ed} \mod P \\ &\equiv p^{1 + (P-1)h} \mod P \\ &\equiv (p^{P-1})^hp \mod P \\ &\equiv 1 \cdot p \mod P \\ &\equiv p \mod P \end{split}\]

Partendo da un testo cifrato siamo quindi in grado, conoscendo $d$, di riottenere il testo in chiaro da cui siamo partiti. Notiamo poi che entrambe le operazioni, crittaggio e decrittaggio, vengono effettuate tramite un esponenziale modulare, che, come abbiamo visto due lezioni fa, sappiamo essere facile da calcolare.

3.2 Sicurezza

Adesso sappiamo che il sistema funziona correttamente e che è effettivamente possibile implementarlo in un calcolatore. La prossima domanda da farci è: il sistema risulta essere sicuro?

Una particolare vulnerabilità dei cifrari classici era il fatto che, congetturando delle corrispondenze tra testo cifrato e testo in chiaro, si era poi in grado di ricostruire la chiave utilizzata nella cifratura, che a sua volta ci permetteva di ricostruire la chiave per decifrare, rompendo essenzialmente l'intero sistema. Per quanto riguarda i cifrari esponenziale, un crittoanalista, anche se riesce a mappare del testo cifrato a dal testo in chiaro, ovvero ad ottenere una relazione del tipo

\[c \equiv p^e \mod P\]

per riuscire a ricostruire la chiave utilizzata, deve trovare l'esponente $e$ tale che $p^e \equiv c \mod P$. Tale problem prende il nome di logaritmo discreto.

3.2.1 Logaritmo Discreto

Sia $G$ un gruppo, e siano $x, y$ elementi di $G$. Supponiamo che vale la seguente relazione

\[y = x^n\]

Allora poniamo $n := \log_x y$.

Se $G$ è il gruppo dei reali, $n$ viene chiamato il logaritmo di y in base x. Se $G$ è un gruppo finito, $n$ viene chiamato il logaritmo discreto di y in base x. Il problema del logaritmo discreto è proprio quello di, dati $x, y \in G$, calcolare $n$ tale che $y = x^n$.

Notiamo che in un gruppo finito, il logaritmo discreto di y in base x, non è univocamente definito, vale infatti la seguente cosa

\[x^n = x^{n + ord(x) \cdot k}, \, \, k \in \mathbb{N}\]

Il che vuol dire che $\log_x y$ è univocamente definito a meno di multipli di ord(x).

Fino a questo momento nessuno è stato in grado di trovare un algoritmo polinomiale che risolve il problema del logaritmo discreto. In altre parole, il logaritmo discreto sembra essere uno dei problemi "praticamente impossibili" da risolvere. Questo significa che l'operazione di esponenziazione modulare risulta essere una ottima canditata per considerata una funzione trappola.

Andiamo adesso ad analizzare un algoritmo standard non polinomiale per il calcolo del logaritmo discreto.

3.2.2 Baby Steps, Giant Steps

Siano $g, y \in \mathbb{Z}_p^*$. Vogliamo calcolare $x \in \mathbb{N}$ tale che $x = \log_g y$, ovvero tale che $y = g^x$. A tale fine consideriamo $n = \lceil \sqrt{p} \rceil$, e procediamo nel seguente modo

(Baby steps): Inizialmente mi calcolo

\[g^0, g^1, g^2, \ldots, g^{n-1}\]

(Giant steps): Continuando mi calcolo

\[y \cdot g^{-n}, y \cdot g^{-2n}, \ldots, y \cdot g^{-n^2}\]

Alla fine confronto ogni coppia $(g^i, g^{-jn})$ e mi fermo alla prima coppia tale che

\[g^i = y \cdot g^{-jn}\]

dove $i = 0, ..., n-1$, e $j = 1, ..., n$.

Notiamo che nel caso in cui l'algoritmo ritorna la coppia $(i, j)$, allora sicuramente $jn +i$ è la il valore ricercato, infatti

\[g^i = y \cdot g^{-jn} \iff y = g^{jn + i} \iff \log_g y = jn + 1\]

Inoltre, se $\log_g y$ esiste, allora il nostro algoritmo sicuramente lo trova. Infatti, ponendo $x = \log_g y$, possiamo dividere $x$ per $n$, ottenendo

\[x = jn + i \quad, \quad 0 \leq i < n\]

Continuando, possiamo assumere senza perdita di generalità che $x < p$. Infatti, le potenze distinte di $g$ sono al più $p$, e quindi, anche se è vero che $\log_g y$ non è univoco, possiamo considerare che $x$ sia il più piccolo intero positivo tale che $y = g^x$. Essendo il più piccolo, questo è sicuramente compreso tra $0$ e $p$, in quanto andando oltre $p$ ci fa semplicemente tornare in una potenza già vista. Se $x < p$, allora $j \leq n$, in quanto altrimenti, se $j > n$, allora

\[x = jn + i > n^2 + i > p + i > p\]

Ma allora questo valore $x$ verrà sicuramente beccato dall'algoritmo, che è proprio quello che volevamo dimostrare.

Infine, per quanto riguarda la complessità, notiamo che l'algoritmo risulta comunque esponenziale, in quanto sia per i baby steps che per i giant steps dobbiamo effettuare $O(n \log n)$ operazioni, mentre per il confronto le operazioni sono $(n^2\log n)$, il che chiaramente è esponenziale.

4 Diffi-Hellman Key Exchange

Questa procedura permette di condividere una chiave segreta tra due persone, e si basa sulla difficoltà del calcolo del logaritmo discreto.

Sia $P$ un numero primo molto grande, $P >> 0$. Questo numero primo viene reso pubblico. Siano $k_1, ..., k_r$, $r$ chiavi private, una per ogni utente del sistema, tale che $MCD(k_i, P) = 1$. Infine, sia $a$ un intero tale che $MCD(a, P) = 1$.

Supponiamo che gli utenti $A$ e $B$ vogliono condividere una chiave segreta, che possono poi utilizzare come parametro in ulteriori schemi di cifratura. Gli steps da eseguire per ottenere questa chiave privata sono i seguenti:

L'utente $A$ si calcola

\[y_1 \equiv a^{k_1} \mod P \,\,\,\,,\,\,\,\, 0 < y_1 < P\]

e lo invia all'utente $B$.
L'utente $B$ si calcola

\[y_2 \equiv a^{k_2} \mod P \,\,\,\,,\,\,\,\, 0 < y_2 < P\]

e lo invia all'utente $A$.
L'utente $A$ si calcola

\[y_2^{k_1} \mod P\]
L'utente $B$ si calcola

\[y_1^{k_2} \mod P\]

Il segreto condiviso tra $A$ e $B$ è $a^{k_1k_2} \mod P$. Infatti,

\[\begin{split} y_2^{k_1} \equiv {a^{k_2}}^{k_1} \equiv a^{k_1k_2} \mod P \\ y_1^{k_2} \equiv {a^{k_1}}^{k_2} \equiv a^{k_1k_2} \mod P \\ \end{split}\]

La sicurezza di questo sistema di condivisione deriva dal fatto che, nel caso in cui un attaccante riesce ad intercettare i valori inviati nella rete, ovvero $y_1$ e $y_2$, per calcolare la chiave comune $k$ deve ottenere almeno una delle due chiavi private $k_1 = \log_a y_1$ e $k_2 = \log_a y_2$. Per fare questo deve necessariamente risolvere il problema del logaritmo discreto. Qui entra in gioco l'ipotesi di Diffie-Hellman, che afferma che il calcolo di $\log_a y$, con $a$ fissato, non è più facile del calcolo del logaritmo discreto in generale.

5 Crittografia a Chiave Pubblica

La crittografia a chiave pubblica si basa sul separare il ruolo delle chiavi, ed è per questo che molto spesso questo tipo di cifratura prende il nome di cifratura asimmetrica. Nella cifratura a chiave pubblica (o asimmetria), si hanno due chiavi: una chiave, detta pubblica, che può essere ottenuta da chiunque, e una chiave, detta privata, che deve essere mantenuta segreta. L'idea di base è che tutto ciò che è cifrato con la chiave pubblica può essere decifrato solamente con la chiave privata associata, e viceversa, tutto ciò che è cifrato con la chiave privata può essere decifrato solamente con la chiave pubblicata associata.

Nella crittografia a chiave pubblica cambia anche la natura delle comunicazioni. Generalmente i cifrari sono sempre stati utilizzati per proteggere comunicazioni che avvenivano tra un numero di persone ristretto, persone che si conoscevano a vicenda e che dovevano comunicare per questioni importanti. Nella crittografia a chiave pubblica moderna abbiamo invece tantissime persone che vogliono comunicare in modo sicuro tra loro, e questa comunicazione deve avvenire anche con persone che non necessariamente si conoscono, e che molto si possono mettere d'accordo per condividere una chiave privata.

Supponiamo di voler inviare un messaggio a $x$. Utilizzando un crittosistema a chiave pubblica, la prima cosa che devo fare è cifrare il messagio utilizzando la chiave pubblica di $x$. Così facendo mi sto assicurando che l'unica persona in grado di decifrare il messaggio è la persona che possiede la chiave privata associata alla chiave pubblica di $x$, che idealmente sarà solo $x$.

L'idea generale di questo tipo di cifrazione è stata concepita da Diffie e Hellman negli anni 80. Il primo sistema ad implementarla viene chiamato RSA, ripreso dai nomi dei ricecartori che lo hanno sviluppato: Rivest, Adelman e Shaniz. Tale sistema sarà analizzato nella prossima lezione.

Per chiudere questa lezione invece andiamo ad analizzare il problema del calcolo della radice quadrata, che ci tornerà utile per analizzare la sicurezza del sistema RSA.

6 Calcolo Radice Quadrata

Sia $n$ a $k$ -bit

\[n = \big(n_{k-1}, n_{k-2}, ..., n_1, n_0\big)_2\]

e assumiamo senza perdità di generalità che $k$ sia un numero dispari, ovvero $k = 2h + 1$, con $h \in \mathbb{N}$. Definiamo $m := \lceil \sqrt{n} \rceil$ come la sua radice quadrata. Notiamo che $m$ sarà un numero della forma

\[m = \big(m_{h}, m_{h-1}, ..., m_{1}, m_0\big)_2\]

in quanto se $m$ avesse più di $h+1$ cifre, allora $m^2$ avrebbe più di $k$ cifre. Andiamo adesso a descrivere una procedura che ci permette di calcolare le varie cifre $m_i$ di $m$:

Iniziamo ponendo

\[m_0 := \big(1, \underbrace{0, ..., 0}_{\text{$h - 1$}}\big)_2\]

Notiamo che $m_0^2 \leq n$. Ora, se $m_0^2 = n$, allora ho fatto e $m = m_0$, altrimenti continuo al passo $(2)$
Sia

\[m_1 = \big(1, 1, \underbrace{0, ..., 0}_{\text{$h-2$}}\big)_2\]

Se $m_1^2 > n$, allora tolgo l'ultima cifra aggiunta e continuo al passo $(3)$. Se $m_1^2 < n$, allora continuo direttamente al passo $(3)$. Infine, se $m_1^2 = n$, allora ho fatto e $m = m_1$.
Continua....

Continuando così sono in grado di stabilire ogni cifra $m_i$ di $m$. Infatti eseguo al più $h$ iterazioni, ciascuna delle quali, tramite un confronto che richiede $O(h^2)$, mi permette di stabilire una cifra di $m$. Il costo totale per il calcolo della radice quadrata risulta quindi essere

\[O(h^3) = O(\log{n}^3)\]