CTX - 04 - Congruenze

Innanzitutto mostriamo che \(MCD(a, n) \,\, | \,\, b\) è una condizione necessaria all'esistenza di una soluzione. Infatti, se \(x\) è una soluzione della nostra equazione, allora abbiamo che

\[\exists \alpha \in Z: ax - b = \alpha n \iff b = ax + (- \alpha)n\]

Ma quindi, visto che \(d\, |\, a\) e \(d\, |\, n\), abbiamo che \(d\, |\, b\).

Vediamo ora che \(MCD(a, n) \,\, | \,\, b\) è anche una condizione sufficiente a garantire l'esistenza di almeno una soluzione.

A tale fine supponiamo che \(d = MCD(a, n) | b\). Allora \(b = d \alpha\), con \(\alpha \in \mathbb{Z}\). Potendo dividere per \(d\) sia \(a\) che \(b\) che \(n\), possiamo ricondurre ogni soluzione della nostra equazione alla soluzione della seguente equazione congruenziale

\[\frac{a}{d}x \equiv \frac{b}{d} \quad \mod{\frac{n}{d}}\]

Infatti, se \(x\) è una soluzione di \(ax \equiv b \quad \mod{n}\), abbiamo che

\[\begin{split} ax - b = \alpha n &\iff \frac{a}{d}x - \frac{b}{d} = \alpha \frac{n}{d} \\ &\iff \frac{a}{d}x \equiv \frac{b}{d} \quad \mod{\frac{n}{d}} \\ \end{split}\]

notando poi che \(MCD(\frac{a}{d}, \frac{n}{d}) = 1\) abbiamo che la seconda equazione presa in considerazione ha una e una sola soluzione. Tale soluzione, chiamiamola \(x^*\), sarà quindi, per quello che abbiamo appena mostrato, anche una soluzione della prima equazione presa in considerazione. Detto altrimenti, se \(MCD(a, n)\, |\, b\), allora abbiamo almeno una soluzione.

Se la nostra equazione ammette una soluzione, generalmente ne ammette più di una. Per calcolarci tutte le soluzioni della nostra equazione possiamo utilizzare la seguente applicazione tra anelli \(f: \mathbb{Z}_n \to \mathbb{Z}_{\frac{n}{d}}\), definita come segue

\[\forall a \in \mathbb{Z}_n: \,\,\,\, f(a) := a \mod{\frac{n}{d}}\]

ed eseguire i seguenti step

• In \(\mathbb{Z}_{\frac{n}{d}}\) ci calcoliamo l'unica soluzione \(x^*\) dell'equazione

  \[\frac{a}{d}x \equiv \frac{b}{d} \quad \mod{\frac{n}{d}}\]

• Partendo da \(x^*\), prendiamo la controimmagine di \(x^*\) tramite \(f\), ovvero calcoliamo l'insieme

  \[f^{-1}(x^*) = \{ x \in \mathbb{Z}_n : f(x) = x^*\}\]

Notando che ogni \(x \in Z_{\frac{n}{d}}\) ha una controimmagine tramite \(f\) di \(d\) elementi, che sono in particolare:

\[f(x) = x, \,\, f\Big(x + \frac{n}{d}\Big) = x, \,\, f\Big(x + 2\frac{n}{d}\Big) = x, \,\, ..., \,\, f\Big(x + (d-1)\frac{n}{d}\Big) = x\]

anche \(x^*\) avrà una controimmagine di \(d\) elementi, e da questo segue che l'equazione a cui siamo interessati ha esattamente \(d\) soluzioni in \(\mathbb{Z}_n\), che sono date da

\[x^* + i \cdot \frac{n}{d}, \,\,\,\, i \in \{0, 1, ..., d-1\}\]

Dimostrazione: Iniziamo mostrando che \((2) \implies (1)\).

Sia \(a \in \mathbb{Z}_p\), e supponiamo che a1 \quad \mod p. Se \(p \,\not|\, a\) otteniamo \(a^p \equiv a (\mod p)\). Altrimenti \(p\, |\, a\) e quindi \(a^p \equiv 0 \equiv a (\mod p)\).

Andiamo adesso a dimostrare il punto \((2)\). A tale fine supponiamo che \(p \, \not |\, a\), e quindi \(a \in \mathbb{Z}_p^*\). Utilizzando il concetto di ordine di un elemento, ripreso dalla teoria dei gruppi, notiamo che \(p-1\) è l'ordine di \(\mathbb{Z}_p^*\), e quindi

\[a^{p-1} = 1 \in \mathbb{Z}_p^*\]

Notando infine che \(\mathbb{Z}_p^* \subseteq \mathbb{Z}_p\), otteniamo che \(a^{p-1} = 1\) in \(\mathbb{Z}_p\), il che vuol dire che

\[a^{p-1} \equiv 1 \mod p\]

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

Volendo dimostrare il punto \((2)\) senza utilizzare risultati ripresi dalla teoria dei gruppi, consideriamo il seguente insieme di elementi

\[\{1 \cdot a, 2 \cdot a, ..., (p-1) \cdot a\} \subseteq Z_p\]

Notiamo che tutti gli elementi della forma \(i \cdot a\) con \(i \in \{1, .., p-1\}\) sono invertibili, in quanto sia \(i\) che \(a\) sono invertibili. Questi elementi risultano anche essere distinti: se esistono \(i, j \in \{1, ..., p-1\}\), tali che \(i \cdot a \equiv j \cdot a \mod p\), allora, divendo per \(a\) (e lo posso fare in quanto \(a\) è coprimo con \(p\)) ottengo \(i \equiv j \mod p\), ovvero \(i = j\). Abbiamo quindi \(p-1\) elementi distinti e invertibili presi da \(\mathbb{Z}_p\). Segue necessariamente che

\[\big\{1 \cdot a, 2 \cdot a, ..., (p-1) \cdot a\big\} = Z_p^*\]

Ma allora andando a moltiplicare tutti gli elementi di \(Z_p^*\) in entrambe le rappresentazioni, dobbiamo ottenere necessariamente lo stesso valore. In formula,

\[1 \cdot 2 \cdot \,\, \ldots \,\, \cdot (p-1) \equiv (1 \cdot a) \cdot (2 \cdot a) \cdot \,\, \ldots \,\, \cdot ((p-1) \cdot a) \mod p \]

il che equivale a dire che

\[(p-1)! \equiv (p-1)! \cdot a^{p-1} \mod p\]

Infine, dato che \((p-1)!\) è invertibile, in quanto \(MCD((p-1)!\,\,,\,\, p) = 1\), possiamo dividere ambo i lati per \((p-1)!\) per ottenere

\[a^{p-1} \equiv 1 \mod p\]

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

Il seguente corollario può essere utilizzato per semplificare il calcolo delle potenze in \(\mathbb{Z}_p\).

Corollario: Sia \(p\) primo e \(a\) un intero tale che \(p \,\, \not |\,\, a\), allora

\[n \equiv m \quad \mod{p-1} \implies a^n \equiv a^m \quad \mod{p}\]

Dimostrazione: Iniziamo notando le seguenti equivalenze

\[\begin{split} n \equiv m \mod{p-1} &\iff \,\, \exists \alpha \in \mathbb{Z}: \,\, n - m = \alpha (p-1) \\ &\iff \,\, \exists \alpha \in \mathbb{Z}: \,\, n = m + \alpha (p-1) \end{split}\]

Ma quindi,

\[\begin{split} a^n &\equiv a^{m + \alpha (p-1)} &\mod p \\ &\equiv a^ma^{\alpha (p-1)} &\mod p\\ &\equiv a^m(a^{p-1})^{\alpha} &\mod p \\ &\equiv a^m 1^{\alpha} &\mod p \\ &\equiv a^m &\mod p \end{split}\]

Osserviamo che il viceversa non è sempre vero: se \(p \not | a\), e \(a^m \equiv a^n (\mod p)\), non sempre è vero che \(n \equiv m \mod p-1\). Infatti il corollario ci dice semplicemente che l'ordine di \(a\) è un divisore di \(p-1\), ma non ci dice la sua grandezza. Per fare un controesempio, consideriamo \(p = 7\). Notiamo che l'ordine di \(2\) in \(\mathbb{Z}_7\) è \(3\), infatti

\[\begin{split} 2^1 \equiv 2 \mod 7 \\ 2^2 \equiv 4 \mod 7 \\ 2^3 \equiv 1 \mod 7 \\ \end{split}\]

troviamo quindi che \(2^3 \equiv 2^6 \mod 7\), ma \(3 \not \equiv 6 \mod 6\).

Sia \(n >> 0\) la chiave e \(r\) il numero di persone a cui vogliamo dare un indizio. Scegliamo \(r\) primi distinti, \(p_1, p_2, ..., p_r\) , uno per ogni persona, con la proprietà che:

\[\sqrt[3]{n} < p_i < \sqrt{n} \,\,\,\,, \,\,\,\, \forall i = 1,...,r\]

A ciascuna persona \(i\) assegnamo, come "indizio" il resto della divisione di \(n\) per \(p_i\). Ovvero, alla \(i\) -esima persona diamo il valore \(r_i(n)\) tale che

\[r_i(n) \equiv n \mod p_i\]

Andiamo adesso a verificare che il nostro sistema rispetti che le due proprietà, che riportiamo per completezza:

1. Se un numero di persone \(\geq 3\) si mettono d'accordo e condividono i loro indizi, sono in grado di ricostruire la chiave \(n\).

2. Se un numero di persone \(< 3\) si mettono d'accordo e condividono i loro indizi, non sono in grado di ricostruire la chiave \(n\).

Per quanto riguarda riguarda la prima condizione, notiamo che se \(3\) persone si mettono d'accordo, supponiamo la prima la seconda e la terza persona, allora per ricostruire \(n\) possono semplicemente risolvere il seguente sistema di congruenze lineare.

\[\begin{cases} x \equiv r_1(n) \mod p_1 \\ x \equiv r_2(n) \mod p_2 \\ x \equiv r_3(n) \mod p_3 \\ \end{cases}\]

Ora, tramite il Teorema Cinese dei Resti (abbreviato TCDR), sappiamo che esiste una soluzione \(x^*\), e che tale soluzione è unica modulo \(p_1p_2p_3\). L'osservazione fondamentale è che, per come sono stati scelti i numeri primi, si ha

\[p_1 \cdot p_2 \cdot p_3 > \sqrt[3]{n}^3 = n\]

In altri termini abbiamo che la soluzione del sistema è unica con un modulo più grande di \(n\). Dato che \(n\) sicuramente è una soluzione del sistema, proprio per come abbiamo ottenuto i vari \(r_i(n)\), concludiamo che \(n\) è la soluzione del sistema compresa da 0 e \(p_1p_2p_3\). In poche parole, per trovare \(n\), alle \(3\) persone basta risolvere il sistema, trovare una qualsiasi soluzione \(x^*\) e infine ridurre la soluzione trovata modulo \(p_1p_2p_3\). Così facendo ottengono sicuramente \(n\).

Se al posto di 3 persone si mettono d'accordo un numero maggiore di 3, allora il modulo sarà ancora più grande di \(n\), e quindi si procede nello stesso modo esposto prima.

Analizziamo adesso il caso in cui il numero di persone che si mettono d'accordo è \(\leq 2\). In questo caso le due persone possono nuovamente risolvere il sistema.

\[\begin{cases} x \equiv r_1(n) \mod p_1 \\ x \equiv r_2(n) \mod p_2 \\ \end{cases}\]

Tramite il TCDR sappiamo che esiste una soluzione \(x^*\) a tale sistema, e che tale soluzione è unica modulo \(p_1p_2\). Per come sono stati scelti i primi però osserviamo che

\[p_1 \cdot p_2 < n\]

Questa volta, a differenza di prima, la soluzione è unica con un modulo più piccolo di \(n\). Questo vuol dire che \(n\) non è più la più piccola soluzione intera positiva del sistema. In questo scenario l'unica informazione conosciuta sulla chiave \(n\) è che \(x^* \equiv n \mod p_1p_2\). Ci sono però infiniti valori per cui questo è vero. Concludiamo che ricostruire la chiave \(n\) in questo scenario risulta impossibile.

Osservazione: Per chiudere la trattazione di questo metodo, notiamo che, dato che la chiave è abbastanza grande, anche i primi \(p_i\) sono abbastanza grandi. Possiamo quindi iniziare a vedere come un metodo efficiente per trovare numeri primi di grandi dimensioni possa essere estremamente utile nella crittografia moderna.

Sia \(k >> 0\) la chiave, \(r\) il numero di persone totali e \(s\) il numero minimo di persone che devono essere d'accordo al fine di ricostruire la chiave. Sia inoltre \(P\) un numero primo tale che \(P > k\). Il numero \(P\) scelto rappresenta la chiave pubblica e viene quindi reso pubblico a tutti. La chiave \(k\) invece rappresenta la chiave privata. Scegliamo poi \(r\) interi tali che

\[m_1 < m_2 < ...< m_{i-1}< m_i < m_{i+1} < ... < m_r\]

uno per ogni utente, che siano a due a due primi tra loro e che non siano divisibili per \(P\). Voglio inoltre che gli interi scelti rispettano la seguente disuguaglianza:

\[M := m_1m_2...m_s > P \cdot m_rm_{r-1}...m_{r-s+2}\]

Questa scelta, che può sembrare abbastanza arbitraria, viene effettuata per assicurarmi che comunque prendo \(s-1\) interi tra \(m_1...m_r\), ho che \(\frac{M}{P}\) è maggiore del loro prodotto, ovvero che

\[\frac{M}{P} > m_{j_1}m_{j_2}...m_{j_{s-1}}, \quad \forall 1 \leq j_1 \leq j_2 \leq ... \leq j_{s-1} \leq r\]

Si sceglie poi \(t\) tale che \(t + 1 < \frac{M}{P}\) e si considera \(k_0\) dato da

\[k_0 := k + tP < k + \Big(\frac{M}{P} - 1\Big)P < M\]

Infine, si assegna all'\(i\) esimo utente il resto della divisione di \(k_0\) per \(m_i\). Ovvero si da come indizio all'\(i\) -esimo utente il valore \(k_i\) tale che

\[k_i \equiv k_0 \mod m_i\]

Come prima cosa analizziamo il caso in cui un gruppi composto da \(s\) persone si riunisce. Siano quindi \(j_1, j_2, ..., j_s\), \(s\) persone distinte che vogliono ricostruire la chiave. Come prima cosa devono necessariamente risolvere il seguente sistema lineare

\[\begin{cases} x \equiv k_{j_1} \mod m_{j_1} \\ x \equiv k_{j_2} \mod m_{j_2} \\ . \\ . \\ x \equiv k_{j_s} \mod m_{j_s} \\ \end{cases}\]

Sempre per il TCDR sono in grado di trovare una soluzione \(x^*\). Tale soluzione è unica modulo \(m_{j_1}m_{j_2}...m_{j_s}\). Per costruzione poi si ha che

\[m_{j_1}m_{j_2}...m_{j_2} > m_1m_2...m_s = M\]

La soluzione trovata è unica con un modulo più grande di M. Nuovamente, dato che \(k_0\) per costruzione è una soluzione del nostro sistema, e dato che \(k_0 < M\), abbiamo che \(k_0\) è la più piccola soluzione positiva del sistema. Questo vuol dire che qualunque sia la soluzione che gli \(s\) utenti calcolano, possono semplicemente ridurla modulo \(M\) per trovare \(k_0\). Una volta trovato \(k_0\) poi possono nuovamente ridurlo, questa volta modulo \(P\), per trovare \(k\). Infatti \(k\) è proprio il resto nella divisione di \(k_0\) per \(P\).

Analizziamo invece il caso in cui a riunirsi sono \(s-1\) utenti \(j_1, j_2, ..., j_{s-1}\). Nuovamente, per ricostruire la chiave possono risolvere il solito sistema lineare, trovando, sempre grazie al TCDR, una soluzione \(x^*\). Questa volta però la soluzione è unica modulo \(M_j := m_{j_1}m_{j_2}...m_{j_{s-1}}\). Ora, dato che \(k_0\) è un'altra soluzione del sistema, la relazione che collega \(k_0\) e \(x^*\) è la seguente:

\[k_0 \equiv x^* \mod M_j\]

ovvero esiste un certo \(y \in Z\), tale che \(k_0 = x^* + y \cdot M_j\). Osserviamo poi che \(y < \frac{M}{M_j}\), infatti

\[y \cdot M_j \leq k_0 = x^* + y \cdot M_j < M \implies y < \frac{M}{M_j}\]

D'altra parte, \(\frac{M}{M_j} > P\), infatti per costruzione avevamo che

\[\frac{M}{P} > m_{j_1}...m_{j_{s-1}} = M_j\]

Per trovare \(k_0\), e quindi la chiave \(k\), si potrebbe quindi procedere a tentativi: prendo tutti gli \(y < \frac{M}{M_j}\) e per ciascuno mi calcolo il relativo \(k_0\) e poi la relativa chiave \(k\). Certo, non vado a colpo sicuro e fallirò molte volte, ma il numero di tentativi è limitato da \(\frac{M}{M_j}\), che comunque è un valore finito. Il problema in questo approccio brute force è il seguente: dato che \(\frac{M}{M_j} > P\), quando provo tutti gli \(y < \frac{M}{M_j}\), sto anche provando tutti gli \(y < P\). In altre parole, \(y\) viaggia in tutte le classi di resto modulo \(P\). Ma se \(y\) viaggia in tutte le classi di resto modulo \(P\), anche \(k_0\) viaggia in tutte le classi di resto modulo \(P\), e quindi nuovamente non sono in grado di stabilire qual'è la chiave \(k\) in quanto esistono una infinità di valori con lo stesso resto modulo \(P\).