CTX - 09 - Cifrari a Chiave Pubblica II

1 Informazioni Lezione

Data: [2018-04-04 mer]

In questa lezione abbiamo introdotto e descritto il funzionamento del sistema RSA, analizzando come può essere attaccato e descrivendo anche come può essere utilizzato per risolvere il problema della firma digitale.

2 Sistema RSA

Consideriamo $N$ utenti. Indichiamo con $i \in \{1, ..., N\}$ , l'$i$ -esimo utente. Per poter utilizzare il sistema $i$ deve fare i seguenti passi, nell'ordine in cui vengono menzionati

$(i)$ sceglie due numeri primi molto grandi e con lo stesso ordine di grandezza

\[p_i \cdot q_i = n_i\]

$(i)$ sceglie $e_i$ primo con

\[\varphi(n_i) = \varphi(p_iq_i) = (p_i - 1)(q_i - 1)\]

$(i)$ calcola

\[d_i \equiv e_i^{-1} \mod \varphi(n_i)\]

Gli interi $e_i$ e $n_i$ formano la chiave pubblica dell'utente $(i)$, $K_{c, i} := (n_i, e_i)$, mentre gli interi $d_i$ e $n_i$ invece formano la chiave privata dell'utente $(i)$ $K_{d, i} := (n_i, d_i)$. La chiave pubblica può e deve essere distribuita pubblicamente, mentre quella privata deve assolutamente rimanere privata (duh!).

Quando un altro utente, diciamo l'utente $(j)$, vuole inviare in modo sicuro un messaggio $P$ (che nuovamente consideriamo essere un intero) all'utente $(i)$, l'utente $(j)$ calcola il seguente valore e lo invia ad $(i)$

\[C \equiv P^{e_i} \mod n_i\]

Per decifrare i messaggi che riceve, l'utente $(i)$ poi si calcola il seguente valore

\[P \equiv C^{d_i} \mod n_i\]

3 Correttezza RSA

Poniamo ora il problema di analizzare la correttezza del sistema RSA. In altre parole siamo interessati a sapere se l'utente $(i)$ sia effettivamente in grado di decifrare messaggi cifrati con la sua chiave pubblica.

Iniziando notando che per costruzione

\[d_i \equiv e^{-1} \mod \varphi(n_i) \iff d_ie_i = 1 + \varphi(n_i)h\]

ma allora, dal teorema di Eulero otteniamo che, se $MCD(P, n_i) = 1$,

\[\begin{split} C^{d_i} &\equiv (P^{e_i})^{d_i} \mod n_i \\ &\equiv P^{e_id_i} \mod n_i \\ &\equiv P^{1 + \varphi(n_i)h} \mod n_i \\ &\equiv (P^{\varphi(n_i)})^hP \mod n_i \\ &\equiv P \mod n_i \end{split}\]

In realtà questo vale anche nel caso in cui $MCD(P, n_i) \neq 1$. Vale infatti il seguente risultato

Lemma: Sia $n \in \mathbb{N}$ libero da quadrati (o square free), ovvero $n = p_1p_2...p_k$ con $p_1, p_2, ..., p_k$ primi distinti. Allora

\[\begin{split} de\equiv 1 \mod \varphi(n_i) &\implies \forall p \,\,|\,\, n : \,\,\,\,\, p - 1 \,\,|\,\, de - 1 \\ &\implies a^{de} \equiv a \mod n \end{split}\]

Dimostrazione: Se $n$ è primo allora questo equivale al teorema di Eulero. Supponiamo $n = p_1p_2...p_k$ square free. Dalle ipotesi so che

\[\forall p \,\,|\,\, n : \,\,\,\, p - 1 \,\,|\,\, de - 1 \iff \forall p \,\,| \,\,n : \exists h : de = 1 + (p-1)h\]

ma allora, dal teorema di fermat, so che, per ogni $i = 1, ..., k$, dato $a \not \equiv 0 \mod n$,

\[\begin{split} a^{de} &\equiv a^{(p-1)h + 1} \mod p_i \\ &\equiv (a^{p-1})^ha \mod p_i \\ &\equiv a \mod p_i \end{split}\]

Il che equivale a

\[\forall i = 1, ..., k : \,\,\,\,p_i \,\,|\,\, a^{de} - a\]

Ma dato che i $p_i$ sono primi distinti, questo vuol dire che $a^{da} - a$ contiene ciascun $p_i$ tra i suoi fattori, e quindi contiene anche $n = p_1...p_k$, ovvero

\[n \,\,|\,\, a^{de} - a \iff a^{de} \equiv a \mod n\]

Infine se $a \equiv 0 \mod n$, allora chiaramente $a^{de} \equiv 0 \equiv a \mod n$.

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

4 Sicurezza RSA

Rompere il sistema, nel caso RSA, significa ricostruire la chiave privata $d_i$ dell'utente $(i)$. Cosi facendo si è infatti in grado di leggere tutti i messaggi inviati a lui, distruggendo la protezione desiderata. Ora, per conoscere $d_i$ un crittoanalista si potrebbe muovere in varie strade. La strada più ovvia e intutiva è quella di passare tramite $\varphi(n_i)$. Infatti, se conosco $\varphi(n_i)$, posso facilmente calcolarmi $d_i$. Così facendo il problema si è spostato dal cercare di ricostruire $d_i$ al cercare di calcolare $\varphi(n_i)$.

Calcolare $\varphi(n_i)$ però, equivale, in un senso che renderemo preciso tra poco, a conoscere la fattorizzazione di $n_i$, ovvero conoscere gli interi $p_i$, $q_i$. Ricordiamo a questo punto che anche se l'intero $n_i$ viene reso pubblico, la sua fattorizzazione non viene resa pubblica. Abbiamo ridotto nuovamente il problema: adesso dobbiamo calcolare la fattorizzazione di $n$. Sarà possibile farlo?

A quanto pare no, non è possibile. Da quanto è stato scoperto fino adesso sembra proprio che il problema della fattorizzazione faccia parte di quella classe di problemi che sembrano essere "praticamente impossibili" da risolvere in tempo polinomiale. Avendo preso $p_i$ e $q_i$ dello stesso ordine di grandezza, l'unica cosa che possiamo fare è procedere con il crivello di eratostene, il che richiede tanto tempo e risorse computazionali, rendendo il tutto impraticabile da eseguire.

Ricapitolando, la sicurezza del sistema RSA è basata sul fatto che fattorizzare i numeri è un problema di cui ancora non si conosce una soluzione polinomiale, e che molto probabilmente tale soluzione non esiste.

4.1 Conoscere $\varphi(n_i) \implies$ Fattorizzare $n_i$

Per concludere andiamo a formalizzare meglio il concetto che calcolare $\varphi(n_i)$ equivale a conoscere la fattorizzazione di $n_i$. In particolare vale la seguente proposizione

Proposizione: Sia $n = pq$, cn $p, q$ primi distinti (supponiamo > 2). Allora

\[\text{conoscere } p, q \iff \text{conoscere } \varphi(n)\]

Dimostrazione:

$(\Rightarrow)$: Questo lato è banale, in quanto

\[\varphi(n) = (p-1)(q-1) = n -q -p + 1\]

dunque se conosco $p$ e $q$ mi calcolo facilmente $\varphi(n)$.
$(\Leftarrow)$: Supponiamo adesso di conoscere $\varphi(n) = n - q - p + 1$. Dal fatto che $p$ e $q$ sono entrambi primi segue che $p + q$ è un numero pari, ovvero che esiste un $b \in \mathbb{N}$ tale che

\[p + q = n + 1 - \varphi(n) = 2b \iff p + q -2b = 0\]

Definiamo adesso la seguente equazione

\[x^2 - 2b \cdot x + n\]

notiamo che $p$ e $q$ sono le due radici di questa equazione, infatti

\[p^2 -2b \cdot p + pq = p(p + q - 2b) = p \cdot 0 = 0\]

utilizzando la solita formula di risoluzione per le equazioni di secondo grado otteniamo

\[x = b \pm \sqrt{b^2 - n}\]

notando poi che $b = \frac{n + 1 -\varphi(n)}{2}$, la formula diventa

\[x = \frac{n + 1 - \varphi(n)}{2} \pm \sqrt{\Big(\frac{n + 1 - \varphi(n)}{2}\Big)^2 - n}\]

Dato che nella precedente lezione avevamo dimostrato che il calcolo della radice quadrata può essere effettuato in tempo polinomiale, ciò significa che dalla conoscenza di $n$ e $\varphi(n)$ siamo anche in grado di conoscere i fattori di $n$.

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

4.2 È possibile calcolare $d$ senza $\varphi(n_i)$?

Arrivati a questo punto può sorgere una domanda alquanto naturale. Esiste un modo per calcolare la chiave privata $d$ di un utente del sistema RSA, senza però doversi calcolare $\varphi(n_i)$, ovvero senza fattorizzare $n$? Da un punto di vista teorico, anche se la conoscenza di $\varphi(n_i)$ implica computazionalmente la conoscenza di $d$, non vale il viceversa, ovvero non è vero che, se conosco $d$, allora devo necessariamente conoscere $\varphi(n_i)$.

Detto questo, esiste un algoritmo probabilistico, che, utilizzando la conoscenza della chiave privata $d$, è in grado di calcolare il valore $\varphi(n_i)$, e quindi di fattorizzare $n$. Dato che l'algoritmo lavora con alta probabilità, questo significa che la conoscenza di $d$ e quella di $\varphi(n_i)$ sono strettamente correlate da un punto di vista pratico, seppur non sono equivalenti da un punto di vista teorico.

Osservazione: Ricordiamo che dire "con alta probabilità" significa dire che possiamo aumentare la probabilità di successo di quanto vogliamo. In particolare un evento $A_n$ succede con alta probabilità se e solo se esiste una costante $\alpha$ tale che

\[P(A_n) \geq 1 - \frac{1}{k^{\alpha}}\]

4.2.1 Algoritmi Deterministici e Algoritmi Probabilistici

Prima di vedere questo algoritmo probabilistico però andiamo a definire, seppur approssimatamente, qualche termine di interesse.

Algoritmo deterministico: Tutti gli algoritmi visti fino ad ora vengono chiamati deterministici. Con il termine deterministico si indica il fatto che le azioni compiute dall'algoritmo sono sempre le stesse, e variano solamente in base ai dati. Se diamo in input gli stessi dati ad un algoritmo deterministico e lo facciamo girare per un determinato numero di volte, allora ogni volta l'algoritmo si comporta nello stesso modo, e in particolare quindi ci da la stessa identica risposta.
Algoritmo probabilistico: Quando invece si parla di algoritmi probabilistici si sta facendo riferimento al fatto che nella serie di istruzioni che definisco l'algoritmo, sono presenti istruzioni che utilizzano delle variabili aleatorie, ovvero degli oggetti che cambiano valore di volta in volta e che seguono una determinata distribuzione di probabilità.

A differenza di un algoritmo deterministico quindi, se eseguiamo più volte un algoritmo probabilistico con lo stesso input, ogni volta otteniamo delle esecuzioni diverse, dettate in parte dal valore assunto dalle variabili aleatorie utilizzate dall'algoritmo. In particolare quindi un algoritmo probabilistico non ci darà mai sempre la risposta corretta al nostro problema, bensì ci darà la risposta corretta con una certa probabilità, che può variare in base all'input.

Siamo ora in grado di descrivere l'algoritmo probabilistico che calcola $\varphi(n_i)$ dato $d$.

4.2.2 Algoritmo probabilistico che calcola $\varphi(n)$ dato $d$

Supponiamo di conoscere la chiave privata $d$ di un utente. Denotiamo con $(e, n)$ la chiave pubblica dello stesso utente e denotiamo con $p, q$ i fattori di $n = p \cdot q$. Iniziamo notando che per ogni $a \in \mathbb{N}$, dire che $MCD(a, n) = 1$ significa dire che

\[a^{de} \equiv a \mod n \iff a^{de - 1} \equiv 1 \mod n\]

Non solo, se $a$ è coprimo con $n$, allora $a$ è anche coprimo sia con $p$ che con $q$. In altre parole $MCD(a, p) = MCD(a, q) = 1$. Ma allora,

\[\begin{cases} a^{de} \equiv a \mod p \iff a^{de - 1} \equiv 1 \mod p\\ a^{de} \equiv a \mod q \iff a^{de - 1} \equiv 1 \mod q \end{cases}\]

Conoscere $d$ equivale quindi a conoscere $m := de - 1$ tale che

\[\forall a \in \mathbb{N}: MCD(a, n) = 1 \implies a^{m} \equiv 1 \mod n\]

Facciamo ora un po' di osservazioni:

Notiamo che $m$ è necessariamente pari. Infatti, ponendo $a = -1$, abbiamo $MCD(a, n) = 1$, e quindi per quanto detto prima

\[(-1)^m \equiv_n a^m \equiv_n 1\]

il che è vero se e solo se $m$ è pari.

Se vale

\[\forall a \in \mathbb{N}: MCD(a, n) = 1 \implies a^{\frac{m}{2}} \equiv 1 \mod n\]

allora possiamo spostare la nostra attenzione da $m$ a $\frac{m}{2}$, in quanto quest'ultimo soddisfa tutte le proprietà di interesse che soddisfava $m$.

Possiamo quindi assumere che ad un certo punto arriviamo ad un $m$ tale che

\[\exists a \in \mathbb{Z}^*_n: a^{\frac{m}{2}} \not \equiv 1 \mod n\]

Andiamo adesso a dimostrare che in questo caso avrò che almeno il $50\%$ degli $a$ soddisfa la seguente congruenza

\[a^{\frac{m}{2}} \equiv -1 \mod n\]

Infatti, sia $a \in \mathbb{Z}^*_n$ l'elemento $a$ tale che $a^{\frac{m}{2}} \not \equiv 1 \mod n$. Notiamo che

\[(a^{\frac{m}{2}})^2 \equiv_n a^m \equiv_n 1 \iff \begin{cases} (a^{\frac{m}{2}})^2 \equiv 1 \mod p \\ (a^{\frac{m}{2}})^2 \equiv 1 \mod q \end{cases}\]

Utilizzando poi il fatto che l'equazione $x^2 \equiv 1 \mod p$ con $p$ primo ha solamente le soluzioni banali $x^2 \equiv \pm 1 \mod p$, concludiamo, escludendo la soluzione banale $1$, che

\[\begin{cases} a^{\frac{m}{2}} \equiv -1 \mod p \\ a^{\frac{m}{2}} \equiv -1 \mod q \\ \end{cases} \iff a^{\frac{m}{2}} \equiv -1 \mod n\]

Riassumendo, abbiamo mostrato che $a^{\frac{m}{2}}$, o è congruo ad 1, oppure è congruo a -1 modulo $n$. L'unica cosa che ci resta da dimostrare è il fatto che il numero di $a$ tali che $a^{\frac{m}{2}} \equiv -1 \mod n$ è almeno la metà degli elementi. A tale fine definiamo i seguenti insiemi

\[\begin{split} A &:= \{ a \in \mathbb{Z}_n^*: a^{\frac{m}{2}} \equiv -1 \mod n \} \\ B &:= \{ a \in \mathbb{Z}_n^*: a^{\frac{m}{2}} \equiv 1 \mod n \} \end{split}\]

Sia $a \in A$. Allora, per ogni $b \in B$, l'elemento $ab$ è nuovamente in $A$, infatti

\[(ab)^{\frac{m}{2}} \equiv_n a^{\frac{m}{2}}b^{\frac{m}{2}} \equiv_n -1 \cdot 1 \equiv_n -1\]

Ma allora $|A| \geq |B|$. Utilizzando poi il fatto che $A \cup B = \mathbb{Z}^*_n$, concludiamo che

\[\phantom{} | \mathbb{Z}^*_n | = | A | + | B | \leq | A | + | A | = 2 | A | \iff | A | \geq \frac{|\mathbb{Z}_n^*|}{2} \]

Continuando l'analisi, che ci porterà poi alla definizione di un algoritmo probabilistico, sia $m$ l'intero tale che

\[\exists a \in \mathbb{Z}_n^*: a^{\frac{m}{2}} \equiv -1 \mod n\]

Questo vuol dire che $\frac{m}{2}$ non divide $\varphi(n) = (p-1)(q-1)$. Qui possono succedere varie cose, che andiamo ad analizzare separatamente:

Se $\frac{m}{2}$ divide $(p-1)$ ma non $(q-1)$ (o viceversa), allora sicuramente

\[a^{\frac{m}{2}} \equiv 1 \mod p\]

Per quanto riguarda il modulo $q$, abbiamo invece i seguenti sottocasi

\[\begin{cases} a^{\frac{m}{2}} &\equiv &1 &\mod q \quad &\leq 50\% \text{ delle volte} \\ a^{\frac{m}{2}} &\equiv -&1 &\mod q \quad &\geq 50\% \text{ delle volte} \end{cases}\]
Se $\frac{m}{2}$ non divide né $(p-1)$ né $(q-1)$. In questo caso caso abbiamo molti più sottocasi, che sono
- $\leq 25\% \text{ delle volte}$
  
  \[\begin{cases} a^{\frac{m}{2}} \equiv 1 \mod q \\ a^{\frac{m}{2}} \equiv 1 \mod q \end{cases}\]
- $\geq 25\% \text{ delle volte}$
  
  \[\begin{cases} a^{\frac{m}{2}} \equiv -1 \mod q \\ a^{\frac{m}{2}} \equiv -1 \mod q \end{cases}\]
- Questo e il caso analogo coprono la differenza, che approssimatamente è $\geq 50\% \text{ delle volte}$
  
  \[\begin{cases} a^{\frac{m}{2}} \equiv 1 \mod q \\ a^{\frac{m}{2}} \equiv -1 \mod q \end{cases}\]

Ora, scegliendo un $a \in \mathbb{Z}_n^*$ in modo uniforme ho una probabilità abbastanza elevata che vale

\[\begin{cases} a^{\frac{m}{2}} \equiv 1 \mod p \\ a^{\frac{m}{2}} \equiv -1 \mod q \end{cases}\]

o viceversa scambiando $p$ e $q$. Quando trovo un $a$ del genere so che $a^{\frac{m}{2}}$ o è un multiplo di $p$ e non di $q$, oppure è un multiplo di $q$ e non di $p$. Ma allora, se mi calcolo

\[d = MCD(a^{\frac{m}{2}} - 1, n)\]

ho che $d = p$, se $a^{\frac{m}{2}}$ è un multiplo di $p$ e non di $q$, e $d = q$ nell'altro caso. In poche parole, se riesco a trovare un $a$ del genere (e questo è un evento probabilistico), sono in grado di trovare i fattori di $n$, e conseguentemente di calcolarmi $\varphi(n)$.

5 Firma Digitale con RSA

Nel mondo del Web poter certificare la provenienza di un documento è un qualcosa di estremamente importante. Tale problema è anche noto come problema della firma digitale e può essere riformulato nel seguente modo: supponiamo che Beatrice riceve un messaggio firmato da Arianna. Come fa Beatrice ad essere sicura che è stata effettivamente Arianna, e non un terzo che fingeva di essere Arianna, ad inviare il messaggio?

Sorprendentemente (o forse no), il sistema RSA può anche essere utilizzato per certificare la provenienza e l'autenticità di un documento firmato. Questa caratteristica è un'ulteriore punto di forza del sistema. Andiamo adesso a vedere il perché questo è possibile.

Supponiamo che $F_A$ sia la firma di Arianna, e supponiamo che Arianna vuole inviare un messaggio $P$ a Beatrice in modo tale da certificarne la provenienza. Indichiamo con $(e_A, n_A)$ e $(e_B, n_B)$ rispettivamente la chiave pubblica di Arianna e Beatrice nel sistema RSA. Infine, indichiamo con $d_A$, $d_B$ le rispettive chiavi private di Arianna e Beatrice. RSA risolve il problema della firma digitale nel seguente modo:

Arianna cifra il messaggio $P$ con la chiave pubblica di Beatrice seguendo il protocollo RSA per ottenere

\[C_1 \equiv P^{e_B} \mod n_B\]

Prima di inviare il messaggio però, allega a $C$ un secondo messaggio, che rappresenta la propria firma digitale.

Per calcolare la firma digitale, Arianna prende la sua firma $F_A$ e la cifra utilizzando la propria chiave privata, ovvero si calcola

\[C_F \equiv F^{d_A} \mod n_A\]

Successivamente prende $C_F$ e lo cifra utilizzando la chiave pubblica di Beatrice, ottenendo

\[C_2 = C_F^{e_B} \mod n_B\]

Il messaggio inviato da Arianna a Beatrice è quindi la concatenazione tra $C_1$ e $C_2$.

Quando Beatrice riceve il messaggio $C_1$ con la firma $C_2$, utilizzando la propria chiave privata è in grado di decifrare $C_1$ e leggere il messaggio $P$. Se poi vuole essere sicura che $P$ sia stato effettivamente inviato da Arianna, allora utilizza nuovamente la propria chiave privata per decifrare il messaggio $C_2$, e ottenere $C_F$. A questo punto decifra $C_F$ applicando la chiave pubblica di Arianna e, se ottiene $F_A$, ovvero la firma di Arianna, allora il messaggio è stato effettivamente inviato da Arianna.

5.1 Funziona?

Si, il metodo appena descritto funziona.

Infatti quando Beatrice decifra quella che pensa sia la firma $F_A$ di Arianna, la decifra utilizzando la chiave pubblica di Arianna, e quindi ottiene $F_A$ se e solo se $F_A$ era stato cifrato con la chiave privata di Arianna, che possiamo assumere conosce solamente Arianna. In altre parole,

\[C_F^{e_A} \equiv F \mod n_A \iff C_F \equiv F^{d_A} \mod n_A\]

Osservazione: Notiamo che tutto questo però assume che Beatrice sia in grado di conoscere quale sia la chiave pubblica di Arianna. Nel mondo reale la realizzazione effettiva di questa ipotesi non è per niente scontata. A tale fine infatti esistono delle architetture basate su delle certificate authorities il cui compito è proprio garantire l'associazione tra chiave pubblica e identità.