CTX - 10 - Cifrari a Chiave Pubblica III

1 Lecture Info

Data: [2018-04-05 gio]

In questa lezione introduciamo un cifrario a chiave pubblica che utilizza, per essere sicuro, la complessità computazione del problema dello zaino. Infine, per terminare la discussione sui cifrari a chiave pubblica discutiamo brevemente del concetto di O-knowledge proof.

2 Problema dello Zaino (Knapsack)

Andiamo adesso a vedere un ulteriore sistema di cifratura a chiave pubblica. Questa volta, al posto della fattorizzazione (RSA), come funzione trappola si utilizza la complessità del problema dello zaino, che riportiamo di seguito.

Knapsack Problem: Dati $a_1$, $a_2$, ..., $a_n$ $\in \mathbb{N}$, $m \in \mathbb{N}$, vogliamo stabilire, ed eventualmente calcolare, se esistono degli $x_i \in \{0, 1\}, i = 1, ..., n$, tali che

\[m = \sum_{i = 1}^n x_ia_i\]

Una possibile interpretazione di questo problema, da cui tra l'altro ne deriva anche il nome, è la seguente: stiamo per partire per una bellissima vacanza. Abbiamo già prenotato il volo e l'albergo; l'unica cosa che ci resta da fare sono le valigie, che per nostra fortuna sono composte da un singolo zaino. Lo zaino però, purtroppo, ha una capacità finita, che noi conosciamo fin troppo bene. Abbiamo una serie di oggetti, tutti molto cari a noi, e che vogliamo quindi portarli in vacanza. Per ciascun oggetto sappiamo quanto spazio occupa nello zaino. Volendo essere efficienti e non sprecare spazio vogliamo cercare un insieme di oggetti che, messi tutti insieme nello zaino, lo occupano completamente, senza lasciare nessun spazio sprecato.

Generalmente la soluzione a questo problema potrebbe esistere ed essere unica, non esistere, oppure esistere e non essere unica.

2.1 Esempi

Riportiamo a seguire qualche istanza del problema knapsack.

Sia $(a_1, a_2, ..., a_n) = (2, 7, 8, 11, 12)$. Se $m = 1$, non abbiamo soluzione, invece, se $m = 21$, abbiamo più soluzioni, in quanto $21 = 2 + 8 + 11 = 2 + 7 + 12$.

Sia $a_i = 2^{i-1}, i = 1, ..., n$. Se $m \leq 2^n - 1$ allora e una soluzione unica data dalla scrittura in base $2$ di $m$.

2.2 Digressione: $\mathbb{P}$ vs $\mathbb{NP}$

Entrando nel campo della teoria della complessità, notiamo l'esistenza delle seguenti classi di complessità, che partizionano i vari problemi a seconda di quanto velocemente possono essere risolti

$\mathbb{P} :=$ problemi per cui esiste un algoritmo polinomiale per la loro soluzione.

$\mathbb{NP} :=$ problemi per cui esiste un algoritmo per la loro soluzione, ed esiste un algoritmo polinomiale per verificare se, un particolare dato, è soluzione del problema.

Banalmente si ha $\mathbb{P} \subseteq \mathbb{NP}$, in quanto se so risolvere un problema, allora so anche stabilire se un dato è soluzione del problema (risolvo il problema e confronto il dato). Una delle congetture più importanti dell'informatica, e anche della matematica è la seguente, che viene chiamata la congettura centrale della complessità computazionale, afferma che

\[\mathbb{P} \subset \mathbb{NP}\]

Ovvero che, esistono problemi in $\mathbb{NP}$ che non possono essere risolti in modo efficiente.

Per riuscire a dimostrare una congettura del genere, nel corso dello sviluppo della teoria della complessità si è cercato di scovare, tra tutti i problemi in $\mathbb{NP}$, quelli che erano i più difficili da risolvere. In particolare è stata scoperta una classe di problemi, i problemi detti $\mathbb{NP}$ -completi tali che, se si riuscisse a risolvere in modo efficente un solo problema $\mathbb{NP}$ -completo, allora tutti i problemi in $\mathbb{NP}$ potrebbero essere risolti in modo efficiente e $\mathbb{P} = \mathbb{NP}$.

La fattorizzazione, la cui difficolta computazionale è la base della sicurezza del sistema $\text{RSA}$ discusso nella precedente lezione è chiaramente un problema in $\mathbb{NP}$: se mi dai un intero $p$ io riesco subito a vedere se questo è un fattore di $n$; inoltre so fattorizzare $n$, anche se ci metto tanto tempo. Anche se sembra difficile, non si è ancora riusciti a dimostrare che il problema di fattorizzare un numero sia $\mathbb{NP}$ -completo, e quindi potrebbe darsi che in realtà questo problema si trovi in $\mathbb{P}$.

Il problema dello zaino, invece, è un problema $\mathbb{NP}$ completo. Trovare una soluzione efficiente a questo problema porterebbe quindi a negare una delle congetture più famosi della teoria della complessità, il che è altamente improbabile. Detto questo, per alcune tipologie di successioni la soluzione esiste e la si può ricavare facilmente. Un caso del genere lo abbiamo con le successioni supercrescenti.

2.3 Istanze particolari: successioni supercrescenti

Una successione $a_1, a_2, ..., a_n$ è detta supercrescente se valgono le seguenti disuguaglianze:

\[\begin{split} a_1 < a_2 \\ a_1 + a_2 < a_3 \\ a_1 + a_2 + a_3 < a_4 \\ . \\ . \\ a_1 + a_2 + ... + a_{n-1} < a_n \end{split}\]

Sia $a_1, a_2, ..., a_n$, $m$ una istanza del problema dello zaino in cui la successione $a_1, a_2, ..., a_n$ è una successione supercrescente. Allora, se esiste, la soluzione può essere calcolata facilmente. Infatti, se $m \geq a_n$, allora sicuramente $x_n = 1$, in quanto se $x_n = 0$, anche prendendo tutti i restanti termini, sicuramente non saremmo in grado di ottenere $m$. Continuando così, se $m - a_nx_n \geq a_{n-1}$ allora sicuramente $x_{n-1} = 1$ sempre per lo stesso motivo. Generalizzando,

\[\begin{split} x_i &= \begin{cases} 1 \,\,\,\,,\,\,\,\,\text{ se $m - \sum_{j = i+1}^n x_ja_j\geq a_i$} \\ 0 \,\,\,\,,\,\,\,\,\text{ altrimenti } \end{cases}\\ \end{split}\]

Dunque, per successioni supercrescenti, il problema dello zaino è risolvibile in tempo polinomiale.

3 Cifrario di Merkle-Hellman

Questo cifrario utilizza il fatto che il problema dello zaino è facilmente risolvibile per successioni supercrescenti ed è difficile da risolvere per successioni generali.

Supponiamo di essere un utente del sistema. Per iscriverci al sistema dobbiamo ottenere una successione supercrescente $a_1, a_2, ..., a_N$, la cui lunghezza $N$ è già stata stabilita. Scegliamo poi due interi, un $m \in \mathbb{N}$ e un $w \in \mathbb{N}$ tali che $MCD(w, m) = 1$. Vogliamo inoltre che $m < 2a_N$. Fatto tutto questo ci calcoliamo la sequenza $b_1, b_2, ... , b_N$ il cui $i$ esimo termine, per $i = 1, ..., N$ è dato da

\[b_i \equiv w \cdot a_i \mod m\]

La coppia chiave pubblica e chiave privata è quindi così formata:

La chiave pubblica è rappresentata dalla successione $(b_1, b_2, ..., b_N)$.
La chiave privata invece è rappresentata dalla successione supercrescente $(a_1, a_2, ..., a_N)$ e dagli interi $w, m$

Possiamo pensare ai messaggi che vengono scambiati in questo sistema come a delle stringhe numerie scritte in base 2. Un messaggio avrà quindi la forma $(x_1, x_2, ..., x_N)$, con $x_i \in \{0, 1\}$. Le operazioni di cifratura e decifratura sono così descritte:

Cifratura: Quando un utente ci vuole inviare un messaggio $(x_1, x_2, ..., x_N)$ in modo tale che solo noi saremo in grado di decifrarlo, utilizzando la nostra chiave privata si calcola il valore $C$ e ce lo invia.

\[C = x_1b_1 + x_2b_2 + ... + x_Nb_N\]
Decifratura: Viceversa, quando riceviamo un messaggio $C$ cifrato con la nostra chiave pubblica, per poterlo decifrare ci dobbiamo prima ricavare $w^{-1} \mod m$, che sappiamo esistere in quanto $MCD(w, m) = 1$. Una volta calcolato $w^{-1} \mod m$ lo moltiplichiamo per $C$, trovando

\[\begin{split} w^{-1}C &\equiv w^{-1}(x_1b_1 + x_2b_2 + ... + x_Nb_N) \mod m \\ &\equiv x_1a_1(w^{-1}w) + x_2a_2(w^{-1}w) + ... + x_Na_N(w^{-1}w) \mod m \\ &\equiv x_1a_1 + x_2a_2 + ... + x_Na_N \mod m \end{split}\]

Notiamo infine che, dato che $m > 2a_N$, ed essendo $a_i$ una successione supercrescente, otteniamo

\[x_1a_1 + x_2a_2 + ... + x_Na_N < (a_1 + ... + a_{n-1}) + a_n < a_n + a_n = 2a_n < m\]

Ma allora, una volta che riceviamo il messaggio cifrato $C$, moltiplicandolo per $w^{-1}$ e riducendolo modulo $m$ otteniamo proprio il numero $P = x_1a_1 + x_2a_2 + ... + x_Na_N$. Avendo a disposizione $P$, e dato che $a_1, ..., a_N$ è supercrescente, possiamo poi risolvere il problema dello zaino con $m := P$, la cui soluzione, per costruzione, è proprio il messaggio in chiaro $x_1, x_2, ..., x_N$.

3.1 Il sistema è sicuro?

Il sistema descritto può essere considerato sicuro?

A priva vista sembrerebbe di si. Un attaccante, infatti, non conosce $w$ e $m$ con cui trasformare la successione pubblica $(b_1, b_2, ..., b_N)$ nella successione supercrescente $(a_1, a_2, ..., a_N)$. L'unico modo a sua disposizione per ottenere il messaggio in chiaro è quindi quella di risolvere l'istanza del problema dello zaino con $b_1, b_2, ..., b_N$ come successione e $m := b_1x_1 + b_2x_2 + ... b_Nx_N$. Sapendo poi che il problema dello zaino è un problema $\mathbb{NP}$ completo, sembrerebbe che non esiste un algoritmo efficiente per ricostruire il messaggio.

In realtà questo non è propriamente vero. A prova di tutto ciò nel 1982 Shamir è riuscito trovare un algoritmo polinomiale che risolve in modo efficiente le istanze del problema dello zaino con successioni della forma $(b_1, b_2, ..., b_N)$. L'osservazione fatta da Shamir fu la seguente: la successione $(b_1, b_2, ..., b_N)$, pur non essendo supercrescente, (e scegliendo opportuni $w$ e $m$ la si può rendere non supercrescente), è stata comunque ottenuta tramite semplici trasformazioni partendo dalla successione $(a_1, a_2, ..., a_N)$, che è una successione supercrescente.

Quindi no, il sistema, per come è stato descritto, non può essere considerato sicuro. Nel corso degli anni sono state però sviluppate variazioni del sistema, alcune delle quali hanno resistito a vari attacchi da parte dei crittoanalisi nel corso degli ultimi decenni.

4 0-Knowledge Proofs

Il concetto fondamentale che sta dietro alle 0-knowledge proofs è quello di convincere qualcuno che noi conosciamo qualcosa (ad esempio particolari ricette o procedure industriali), senza però mostrarle direttamente. Il concetto di 0-knowledge proof fu inizialmente concepito nel 1985. Tra gli ideatori di questa nuova teoria matematica troviamo anche Silvio Micali, un italiano nato a Parlemo! Per questa idea Micali e altri ricercatori furono premiati con il primo Godel prize, nel 1993.

Andiamo a vedere un esempio di 0-knowledge proof.

4.1 Esempio: Logaritmo discreto

Sia $G$ un gruppo finito di $N$ elementi, e siano $b, y \in G$. Supponiamo che sia riuscito a calcolare $x \in \mathbb{N}$ tale che $y = b^x$, ovvero

\[x = \log_b y\]

Adesso voglio convincere un terzo individuo, chiamiamolo Ivar, che io conosco $x$. Lo voglio fare però senza rivelarglielo direttamente. La procedura da utilizzare è la seguente:

Genero $e \in \mathbb{N}$ tale che $e < N$ e spedisco ad Ivar $b' := b^e \in G$.
Ivar lancia una moneta.
- Esce Testa: Se esce testa gli rivelo il numero $e$ che avevo generato prima. A questo punto se Ivar vuole controllare se sto rispettando il controllo o meno, basta che calcola $b^e$ e verifichi che $b' = b^e$.
- Esce Croce: Se esce croce gli rivelo il numero $c = e + x \mod N$. Nuovamente, se Ivar vuole controllare se ho effettivamente calcolato $x$ può calcolarsi $b^{c}$ e vedere se $b^c \equiv b'y \mod N$.

Ora, funziona tutto ciò, oppure esistono modi per barare? Supponiamo di voler mentire. Supponiamo quindi di non conoscere $x$ tale che $y = b^x$, ma semplicemente di fare finta di conoscerlo. Un modo per aggirare il sistema in questo caso potrebbe essere quello di generare $e \in \mathbb{N}$, ma al posto di inviare $b^e$, inviamo $b' = \frac{b^e}{y}$. In questo modo, quando esce croce, possiamo semplicemente rivelare $c = e$, e quando lui controlla ottiene banalmente

\[b^c \equiv b^e \equiv \frac{b^e}{y} \cdot y \equiv b'y \mod N\]

in questo caso però, se esce testa, siamo costretti a rivelare $e - x$, in quanto

\[b^{e-x} = b' = \frac{b^e}{y}\]

se non riveliamo $e - x$ ma inviamo un certo $e'$, Ivar si accorgerebbe subito che $b^{e'} \neq b'$, e quindi capirebbe che stiamo mentendo. In questo caso quindi possiamo rispondere correttamente solamente quando esce croce.

Se vogliamo rispondere bene al primo lancio di moneta però, dobbiamo necessariamente inviargli $b' = b^e$. Ma allora per rispondere correttamente al secondo lancio di moneta dovremmo inviargli $c = e + x \mod N$, che non possiamo calcolare se non conosciamo $x$. Quindi se rispondiamo bene al caso testa, non sappiamo rispondere bene al caso croce.

Da tutte le osservazioni fatte concludiamo che, se non conosciamo $x$, allora possiamo rispondere correttamente solamente ad uno dei due casi possibli (testa o croce).