In un articolo precedente abbiamo studiato l’algoritmo RSA utilizzato per la crittografia a chiave pubblica. La sicurezza di questo algoritmo si basa sulla complessità computazionale di un problema fondamentale della teoria dei numeri: determinare i fattori primi di un numero intero con un grande numero di cifre (ad esempio un numero con \(200\) cifre decimali). La difficoltà di questo problema rende il protocollo RSA abbastanza sicuro, anche se i progressi matematici e la disponibilità di computer con maggiore potenza costringeranno ad aumentare il numero delle cifre.
In questo articolo studieremo un altro problema della teoria dei numeri che ha una elevata complessità computazionale: il problema del logaritmo discreto. Data la difficoltà computazionale di questo problema, il logaritmo discreto è alla base di alcuni algoritmi crittografici importanti. In particolare analizzeremo gli algoritmi di EIGamal per la crittografia a chiave pubblica e la firma digitale, e l’algoritmo Diffie-Hellman per lo scambio in sicurezza di chiavi segrete.
1) Richiami di algebra e teoria dei numeri
La teoria dei numeri ha un ruolo fondamentale nel disegno dei moderni algoritmi utilizzati nella crittografia e quindi nella sicurezza della trasmissione di dati e informazioni sulle reti di computer. L’algoritmo RSA è stato il primo esempio di applicazione della teoria dei numeri alla crittografia asimmetrica a chiave pubblica.
Per comprendere il problema del logaritmo discreto e le sue applicazioni è necessario introdurre alcuni concetti di algebra e teoria dei numeri.
Per le definizioni delle strutture algebriche di gruppo e anello vedere articolo su questo sito relativo alla crittografia simmetrica.
1.1) L’aritmetica modulare di Gauss e l’anello delle classi residuo
Dato un intero positivo \(n\), si dice che due interi \(a,b\) sono congruenti modulo \(n\) se danno lo stesso resto nella divisione per \(n\). La relazione di congruenza viene rappresentata mediante la notazione di Gauss:
\[ a \equiv b \pmod{n} \]Ad esempio \(100\equiv 1 \pmod {33}\).
Vale la seguente proprietà:
Teorema 1.1
Sia fissato un intero non negativo \(n \in \mathbb{Z}^{+}\). Allora per ogni \(a \in \mathbb{Z}\), esiste un unico intero non negativo \(r\) tale che \(a \equiv r \pmod {n}\) con \(0 ≤ r < n\).
Si può dimostrare facilmente che la relazione di congruenza \(\pmod n\) è una relazione di equivalenza (simmetrica, riflessiva e transitiva) e quindi induce una partizione dell’insieme degli interi \(\mathbb{Z}\) in \(n\) classi di equivalenza distinte. Indichiamo con \(\mathbb{Z}_{n}\) l’insieme delle classi di equivalenza modulo \(n\).
Un sistema completo di residui \(\pmod {n}\) è un insieme di \(n\) numeri distinti, ognuno preso da una delle \(n\) classi di equivalenza. La rappresentazione standard per le classi della congruenza modulo \(n\) è formata prendendo come rappresentanti gli elementi dell’insieme \(\{0,1,\cdots, n-1\}\). Quindi possiamo scrivere
Per ogni intero \(a\), la classe \(\overline{a}\) contiene tutti gli interi che danno lo stesso resto di \(a\) nella divisione per \(n\). Ad esempio la classe \(\overline{0}\) contiene lo zero e tutti i multipli positivi e negativi di \(n\).
Sull’insieme delle \(n\) classi definiamo due operazioni binarie di addizione e moltiplicazione:
Si può dimostrare che le due operazioni sono ben definite, cioè il risultato non dipende dall’elemento che si prende come rappresentante di una data classe.
Esercizio 1.1 – L’anello delle classi di congruenza
Dimostrare che l’insieme \(\mathbb{Z}_{n}\) con le operazioni di somma e prodotto definite in precedenza è un anello commutativo con unità moltiplicativa. L’unità è la classe \(\overline{1}\).
L’anello delle classi di congruenza modulo \(n\) viene indicato anche con il simbolo \(\mathbb{Z}/n\mathbb{Z}\).
Esercizio 1.2
Dimostrare che in generale l’anello \(\mathbb{Z}_{n}\) non è un dominio di integrità. Cioè possono esistere due classi non nulle \(\overline{a},\overline{b}\) tali che \(\overline{a} \cdot \overline{b}=\overline{0}\).
Suggerimento
Considerare ad esempio le due classi \(\overline{2}\) e \(\overline{3}\) nell’anello \(\mathbb{Z}_{6}\).
Ricordiamo che un intero \(a\) si dice una unità modulo \(n\) se esiste il suo inverso moltiplicativo, cioè esiste un intero \(b\) tale che \(ab \equiv 1 \pmod{n}\). L’esistenza dell’inverso moltiplicativo di una classe è determinata dal seguente teorema:
Teorema 1.2
Un elemento \(a\) ha un inverso moltiplicativo \(b\), cioè \(ab \equiv 1 \pmod{n}\), se e solo se \((a,n)=1\).
1.2) La funzione aritmetica di Eulero
La funzione aritmetica di Eulero, indicata con \(\varphi(n)\), conta il numero degli interi positivi compresi fra \(1\) e \(n\) che sono primi con \(n\) stesso. In simboli:
\[ \varphi (n) = |\{x\in \mathbb{N} \mid 1\leq x\leq n,\ (x,n)=1\}| \]dove il simbolo \(|A|\) indica il numero degli elementi (o cardinalità) dell’insieme \(A\).
Siano ora \(a,n\) due interi primi fra loro, cioè \((a,n)=1\), con \( n \ge 1\). Il teorema di Eulero afferma che
Tuttavia potrebbe esistere un intero \( t \lt \varphi(n)\) tale che \(a^{t} \equiv 1 \pmod{n}\). Il più piccolo intero \(t\) che verifica questa proprietà si chiama ordine di \(a\) modulo \(n\) e indica con \(ord_{n}(a)\).
Ricordiamo che nel caso di modulo primo il teorema di Eulero diventa il teorema di Fermat:
Esercizio 1.3
Dimostrare che \(ord_{n}(a) | \varphi(n)\).
1.3) Il campo \(\mathbb{Z}_{p}\) e le radici primitive di un intero positivo
Ricordiamo che un campo è un insieme \(F\) sul quale sono definite due operazioni binarie \(+,\cdot\), chiamate in genere somma e prodotto, tali che:
- \(F(+)\) è un gruppo abeliano additivo. L’elemento neutro viene indicato con \(0\) e l’inverso additivo di \(a\) con \(-a\);
- \(F \setminus \{0\}(\cdot)\) è un gruppo abeliano moltiplicativo. L’elemento neutro viene indicato con \(1\) e l’inverso moltiplicativo di \(a\) con \(a^{-1}\);
- vale la legge di distribuzione: \(a\cdot(b+c)=a \cdot b + a \cdot c\).
Un campo può essere finito o infinito. Nel caso finito un campo di ordine \(n\) viene in genere indicato con \(F_{n}\), oppure con \(GF(n)\), in onore del matematico francese Galois.
Teorema 1.3 – Il campo \(\mathbb{Z}_{p}=GF(p)\)
Sia \(p\) un numero primo. Allora l’anello \(\mathbb{Z}_{p}\) è un campo di ordine \(p\).
Dimostrazione
Chiaramente \(\mathbb{Z}_{p}\) è un anello commutativo con unità. Si deve solo dimostrare che ogni elemento non nullo ha un inverso moltiplicativo. Ma questo segue subito dal teorema di Fermat:
Definizione 1.1 – Radice primitiva di un intero positivo
Un intero \(a\) si dice radice primitiva modulo \(n\) se risulta
Ad esempio \(ord_{7}(2)=3\), mentre \(\varphi(7)=6\), e quindi \(2\) non è una radice primitiva di \(7\).
Esercizio 1.4
Dimostrare che \(2\) e \(3\) sono entrambi radici primitive di \(5\).
Teorema 1.4
Per ogni numero primo \(p\) esiste almeno una radice primitiva modulo \(p\). Più precisamente se \(p\) è un numero primo, allora esistono \(\varphi(p-1)\) radici primitive distinte modulo \(p\).
Per una dimostrazione vedi il testo [1].
Nella seguente tabella per ogni numero primo \(p\) è mostrata la più piccola radice primitiva, indicata con \(\mu(p)\):
\[ \begin{array}{|c|c|c|c|} \hline \text{p} & \mu(p) & \text{p} & \mu(p) \\ \hline 2 & 1 & 61 & 2 \\ \hline 3 & 2 & 71 & 7 \\ \hline 5 & 2 & 79 & 3 \\ \hline 7 & 3 & 89 & 3 \\ \hline 11 & 2 & 101 & 2 \\ \hline 19 & 2 & 113 & 3 \\ \hline 31 & 3 & 139 & 2 \\ \hline \end{array} \]Esercizio 1.5
Dimostrare che se \((a,n)=1\) e \(t=ord_{n}(a)\) allora i numeri
sono incongruenti fra loro modulo \(n\).
Più in generale vale il seguente teorema:
Teorema 1.5
Sia \((a,n)=1\). Allora \(a\) è una radice primitiva modulo \(n\) se e solo se i seguenti numeri
formano un sistema di residui ridotto modulo \(n\), cioè se sono incongruenti fra loro e primi con \(n\).
Se un numero \(n\) ha una radice primitiva, allora ogni sistema di residui ridotto modulo \(n\) può essere espresso mediante una successione di potenze (progressione geometrica). In altri termini il gruppo moltiplicativo delle classi residuo è un gruppo ciclico, generato dalla radice primitiva.
Indichiamo con \((\mathbb{Z}/p\mathbb{Z})^{*}=Z_{p}^{*}\) il gruppo moltiplicativo del campo \(\mathbb{Z}/p\mathbb{Z}\). Il gruppo contiene gli elementi \(1,2,\cdots,p-1\) e \(g\) è una radice primitiva di \(p\) se genera questo gruppo.
Il gruppo \(Z_{p}^{*}\) è un gruppo ciclico, cioè ogni elemento \(h\) del gruppo può essere scritto nella forma \(h=g^{t}\), dove \(t\) è un intero.
Non tutti i numeri hanno radici primitive. Vale questo teorema fondamentale:
Teorema 1.6
I numeri aventi radici primitive sono
con \(n\) intero positivo e \(p\) è un primo dispari.
Per la dimostrazione vedere ad esempio [2].
Esercizio 1.6
Siano \(a,n\) interi positivi. Dimostrare che
Suggerimento
Utilizzare la seguente proprietà:
2) Il problema del logaritmo discreto
La soluzione di problemi matematici tramite algoritmi non sempre è possibile, anche con i moderni computer. Possiamo distinguere due categorie di problemi:
- problemi trattabili, che hanno un costo polinomiale;
- problemi non trattabili, che hanno un costo esponenziale.
In entrambi i casi al crescere della dimensione del problema aumenta il tempo necessario per la loro risoluzione. Tuttavia, mentre nel caso polinomiale la crescita è lenta e in generale gestibile, nel caso dei problemi con complessità esponenziale il tempo impiegato cresce molto velocemente, diventando di fatto intrattabili. Per questi concetti vedere ad esempio su questo sito l’articolo dedicato al problema della primalità.
Un esempio di problema con complessità esponenziale è il problema del logaritmo discreto, che analizziamo in questo paragrafo.
2.1) Il logaritmo ordinario
Ricordiamo alcune proprietà del logaritmo ordinario. Data un numero reale positivo \(b \neq 1\) e un numero reale \(x\), il problema consiste nel trovare il numero reale \(y\) tale che
\[ b^{y}=x \]In tal caso si scrive \(y= \log_{b}x\), cioè \(y\) è il logaritmo in base \(b\) di \(x\). Le basi più utilizzate sono \(10,2,e\), dove \(e \approx 2,7182\) è la costante di Eulero. Se \(b=e\) si usa la notazione \(\ln x\) al posto di \(\log_{e}x\).
Esempio 2.1
\[ \begin{array}{l} \log_{10} 1000 = 3 \\ \log_{2} 64 = 6 \\ \ln 100 \approx 4,605 \end{array} \]Esercizio 2.1
Dimostrare le seguenti proprietà della funzione logaritmo:
Esercizio 2.2 – Cambiamento di base
Dimostrare la seguente formula:
2.2) Il logaritmo discreto
Sia \(p\) un numero primo e indichiamo con \(F_{p}\) un campo finito di ordine \(p\). Il campo \(F_{p}\) è di fatto equivalente al campo degli interi modulo \(p\), cioè \(\mathbb{Z}/p\mathbb{Z}\).
Sia \(g\) una radice primitiva di \(p\) e sia \(y\) un elemento non nullo di \(F_{p}\), cioè \(y \in F_{p}^{*}\). Come abbiano visto nel paragrafo precedente, ogni elemento di \(F_{p}^{*}\) è uguale a qualche potenza di \(g\). In particolare \(g^{p-1} =1\), per il teorema di Fermat. Quindi la seguente lista di elementi:
\[ 1,g,g^{2}, \cdots, g^{p-2} \]è un elenco completo degli elementi del campo \(F_{p}\).
Il Problema del Logaritmo Discreto (DLP) consiste nel trovare un elemento \(x\) tale che
\[ g^{x} \equiv y \pmod{p} \]Il numero intero \(x\) viene chiamato il logaritmo discreto in base \(g\) del numero intero \(y\) e si scrive \(x=\log_{g}y\).
Nella teoria dei numeri il logaritmo discreto viene chiamato indice di \(y\) in base \(g\) e indicato con il simbolo \(\text{ind}_{g}(y)\).
Esercizio 2.3
Consideriamo il campo finito \(F_{5}\). Il numero \(2 \in F_{5}^{*}\) è un elemento primitivo di \(F_{5}\). Verificare i seguenti valori del logaritmo discreto:
Esercizio 2.4
Sia \(g\) una radice primitiva nel campo \(F_{p}\). Supponiamo che la congruenza \(g^{x} \equiv y \pmod{p}\) abbia due soluzioni intere \(x=a\) e \(x=b\).
Dimostrare che
Quindi il logaritmo discreto è definito modulo \(p-1\).
Esercizio 2.5
Dimostrare che, se \(x\) è una soluzione di \(g^{x}=y\), allora esistono infinite soluzioni.
Soluzione
Applicando il teorema di Fermat abbiamo:
Esercizio 2.6
\[ \begin{array}{l} \log_{g}(xy) = \log_{g}x + \log_{g}y \ ,\quad x,y \in F_{p}^{*} \\ \log_{g}x^{k} = k \log_{g}x \ ,\quad x \in F_{p}^{*} \end{array} \]Esercizio 2.7.
Supponiamo \(p=23\) e \(g=5\). Trovare il logaritmo discreto in base \(5\) di \(11\) modulo \(23\).
Soluzione: \([x=9]\)
Esercizio 2.8
Verificare le seguenti formule:
Nota
Vogliamo sottolineare la differenza fra il logaritmo ordinario e il logaritmo discreto. Nel caso ordinario, dati due interi \(a,n\) se conosciamo \(a\) e \(a^{n}\) allora possiamo calcolare \(n\) tramite la formula \(n = \log_{a}a^{n}\). Anche senza utilizzare la funzione logaritmo, si può calcolare \(n\) mediante delle approssimazioni successive. Si ipotizza un valore \(x\) e si calcola \(a^{x}\). Se \(a^{x} \lt a^{n}\) si prova con un valore maggiore, altrimenti con uno minore. Dopo un certo numero di tentativi ci si avvicina al valore cercato.
Nel caso del logaritmo discreto questa procedura non è possibile non essendo il campo finito \(F_{p}\) un campo ordinato.
Nella definizione abbiamo utilizzato il gruppo moltiplicativo del campo \(F_{p}\), che come è noto ha \(p-1\) elementi. La definizione può essere estesa a gruppi finiti più generali, come il gruppo dei punti di una curva ellittica. Per approfondire vedere [3].
3) Calcolo del logaritmo discreto
Anche se non esiste una dimostrazione matematica rigorosa, l’esperienza pratica mostra che il calcolo del logaritmo discreto per un campo \(F_{p}\) ha una complessità paragonabile a quella del problema della fattorizzazione di un intero delle dimensioni di \(p\).
Vediamo ora alcuni metodi di calcolo.
3.1) Il calcolo elementare – Ricerca esaustiva
Dati due elementi \(g,h\) di un gruppo finito \(F_{p}\), il problema di calcolare il logaritmo discreto \(\log_{g}h\) consiste nel determinare un elemento \(x\) tale che \(g^{x}=h\).
Un procedimento elementare consiste nell’effettuare il calcolo di tutte le potenze della base \(g,g^{2},g^{3},\cdots\) fino a che troviamo un valore uguale ad \(h\). Se \(g\) è una radice primitiva allora al massimo servono \(p-1\) passi. Infatti essendo \(g^{a+1}=g\cdot g^{a}\) , bastano \(p-1\) operazioni.
Esercizio 3.1
Dimostrare mediante la ricerca esaustiva i seguenti risultati:
La complessità di questo algoritmo è dell’ordine \(O(p)\), supponendo \(O(1)\), cioè costante, la complessità dell’operazione di test dell’uguaglianza dei due valori. Si tratta di un metodo non utile nelle applicazioni reali, in cui si hanno gruppi molto grandi, ad esempio con un numero di elementi \(n \gt 2^{100}\).
3.2) Metodo di calcolo dell’indice (Index Calculus)
Il metodo del calcolo dell’indice (Index calculus) è in grado di risolvere il problema del logaritmo discreto nel gruppo moltiplicativo \(F_{p}^{*}=\mathbb{Z}_{p}^{*}\) del campo \(F_{p}=\mathbb{Z}/p\mathbb{Z}\).
Il metodo di calcolo dell’indice si basa sull’idea di calcolare il logaritmo discreto per diversi numeri primi, e quindi utilizzare queste informazioni per calcolare il logaritmo discreto di un elemento arbitrario \(h\).
Vediamo in dettaglio l’algoritmo. Il problema consiste nel calcolare il logaritmo discreto di \(y\) in base \(g\), cioè \(x = \log_{g}y\), dove \(g\) è una radice primitiva modulo \(p\). Supponiamo di conoscere la fattorizzazione dell’intero \(y\):
\[ y = \prod\limits_{k=1}^{r}p_{k}^{a_{k}} \]Allora possiamo trovare il logaritmo discreto \(x\) con la seguente formula:
\[ x = \sum\limits_{k=1}^{r}a_{k}\log_{g}p_{k} \]Questo metodo presenta due vantaggi principali. In primo luogo per ognuno dei fattori primi \(p_{k}\) abbiamo \(p_{k} \le y\), quindi il calcolo dei logaritmi discreti \(\log_{g}p_{k}\) coinvolge numeri più piccoli rispetto a \(\log_{g}y\).
Inoltre, utilizzando la formula per il cambiamento di base, i logaritmi calcolati per i numeri primi, possono essere riutilizzati anche per calcolare il logaritmo discreto di altri numeri, se questi hanno uno stesso numero primo nella loro fattorizzazione.
Definizione 3.1
Sia \(B \ge 2\) un intero fissato. Un numero intero positivo si dice B-smooth se tutti i suoi fattori primi sono minori od uguali a \(B\). Si definisce la base di fattori F(B) come segue:
Algoritmo Index Calculus
L’algoritmo del metodo di calcolo dell’indice è composto dai seguenti passi:
A1) Scegliamo un valore \(B\) e risolviamo il problema del logaritmo discreto per tutti i numeri primi \(q \le B\):
A2) Calcoliamo le seguenti quantità:
\[ y \cdot g^{-k} \pmod{p} \ ,\quad k=1,2,3,\cdots \]fino a che troviamo un valore \(k\) tale che \(y \cdot g^{-k} \pmod{p}\) è un numero \(B\)-smooth. Quindi per questo numero abbiamo
\[ y \cdot g^{-k} \equiv \prod\limits_{q \le B}q^{a_{q}} \pmod{p} \]Questa espressione può essere scritta nel seguente modo:
\[ \log_{g}y \equiv k + \sum\limits_{q \le B}a_{q}\log_{g}q \pmod{p-1} \]Se abbiamo già calcolato i logaritmi discreti per tutti i numeri primi \(q \le B\), allora possiamo calcolare anche il valore \(\log_{g}y\).
Calcolo logaritmo discreto per numeri primi piccoli
Naturalmente per poter utilizzare l’algoritmo è necessario prima calcolare il logaritmo discreto per i numeri primi che sono \(\le B\). Un metodo semplice consiste nello scegliere in modo casuale un esponente \(k\) e calcolare
Se il numero \(z_{k}\) non è \(B\)-smooth lo scartiamo, se invece è \(B\)-smooth lo possiamo fattorizzare utilizzando i numeri primi della base dei fattori:
\[ z_{k} = \prod\limits_{q \le B}q^{b_{q}(k)} \]Dalla formula precedente abbiamo
\[ \log_{g}z_{k} \equiv k \equiv \sum\limits_{q \le B}{}b_{q}(k) \cdot \log_{g}q \pmod{p-1} \]Si tratta di una equazione nelle incognite \(\log_{g}q\). Se scriviamo un numero di equazioni maggiore di \(\pi(B)\) allora possiamo risolvere il sistema mediante gli algoritmi dell’algebra lineare e calcolare quindi le incognite.
Ricordiamo che la funzione \(\pi(x)\) conta i numeri primi minori o uguali a \(x\).
Esempio 3.1
Supponiamo \(g=3,\ p=101,\ x=94\). Dobbiamo trovare \(y=\log_{3}94\), cioè l’esponente \(y\) tale che \(3^{y} \equiv 94 \pmod{101}\).
Scegliamo come base di fattori \(F(B)= \{2,3,5,7\}\). Calcoliamo il logaritmo discreto dei fattori primi modulo \(101\):
Scegliamo un intero \(k\) in modo casuale, ad esempio \(k=8\). Quindi calcoliamo \(z \equiv 94 \cdot 3^{-8} \pmod{101}\).
Osserviamo in primo luogo che \(3^{-1} \equiv 34 \pmod {101}\). Quindi \(3^{-8} \equiv 34^{8} \equiv 25 \pmod{101}\).
Osservando che \(z \equiv 94*25 \equiv 27 \pmod{101}\) abbiamo infine
Infatti abbiamo \(3^{11} \equiv 94 \pmod{101}\).
Esercizio 3.1
Supponiamo \(p=19\). Dimostrare che \(\log_{2}6 \equiv 14 \pmod{18}\).
Suggerimento
Prendere come base di fattori \(F(B)=\{2,3\}\).
Complessità dell’algoritmo Index Calculus
L’algoritmo Index Calculus utilizzato per risolvere il problema del logaritmo discreto nel campo \(F_{p}\) ha una complessità sub-esponenziale. La complessità sub-esponenziale cresce in modo più veloce di quella polinomiale ma più lentamente di quella esponenziale.
Precisamente la complessità temporale per il problema DLP modulo \(p\) è \(O\left(\exp(\sqrt{2 \ln p \ln \ln p})\right)\).
Per approfondire vedere il testo [5].
3.3) Altri algoritmi
Esistono altri algoritmi sofisticati per trattare il problema del logaritmo discreto. Tra questi ricordiamo:
- Algoritmo Baby-step, Giant-step
- Algoritmi \(\rho\) e \(\lambda\) di Pollard
- Algoritmo Pohlig-Hellman
Per questi e altri algoritmi vedere i testi indicati nella bibliografia finale.
4) L’algoritmo Diffie-Hellman per lo scambio di chiavi nella crittografia simmetrica
La crittografia è la disciplina matematica che si occupa della trasmissione sicura dei messaggi anche su canali non sicuri, come la rete Internet. Un sistema crittografico deve garantire tre obiettivi fondamentali (triade CIA):
- Confidenzialità (Confidentiality): garantire che solo i soggetti autorizzati possano accedere alle informazioni;
- Integrità (Integrity): impedire che i dati vengano modificati o cancellati nei dispositivi di memoria, nella trasmissione sulle reti o nelle fasi di elaborazione;
- Disponibilità (Availability): garantire che le informazioni siano disponibili per le persone autorizzate nei tempi e modi richiesti.
I sistemi crittografici si dividono in due categorie fondamentali:
- sistemi a chiave pubblica (crittografia asimmetrica)
- sistemi a chiave privata (crittografia simmetrica)
Nella crittografia a chiave pubblica ogni utente possiede una coppia di chiavi, una pubblica e una privata. La chiave pubblica è accessibile da parte degli altri utenti, mentre la chiave privata è nota solo al soggetto proprietario. Il sistema a chiave pubblica attualmente più diffuso utilizza l’algoritmo RSA (Rivest-Shamir-Adleman). Altri algoritmi efficienti a chiave pubblica attualmente in uso sono basati sulle proprietà delle curve ellittiche.
Nella crittografia simmetrica viene utilizzata la stessa chiave sia nella fase di cifratura, sia nella fase di decifratura del messaggio. Un problema nella crittografia simmetrica è rappresentato dalla necessità di concordare e quindi scambiare la chiave fra il mittente e il destinatario. Chiaramente la chiave non deve essere trasferita insieme ai dati, soprattutto se il canale di trasmissione non risulta sicuro al 100%.
Quando si utilizza la crittografia simmetrica è fondamentale quindi utilizzare due canali di trasmissione diversi: un canale per lo scambio della chiave segreta e un altro per la trasmissione dei dati crittografati.
4.1) Lo schema di scambio Diffie-Hellman
Supponiamo che Alice e Bob debbano scambiare la chiave segreta da utilizzare successivamente per lo scambio dei messaggi. La procedura ideale da un lato deve essere abbastanza semplice, dall’altro deve impedire ad un eventuale terzo soggetto di intercettare la chiave scambiata.
Descriviamo l’algoritmo di Diffie-Hellman. Due soggetti Alice e Bob si accordano su un campo finito \(F_{p}\), con \(p\) numero primo molto grande, e scelgono un generatore \(g\) del campo. Inoltre Alice sceglie un intero \(a\) che tiene segreto, e allo stesso modo Bob sceglie un intero \(b\). I valori \(a,b\) servono ad Alice e Bob per generare separatamente due numeri \(A,B\) con le seguenti formule:
A questo punto Alice invia il valore \(A\) a Bob, il quale invia il valore \(B\) ad Alice. I valori \(A,B\) servono ad Alice e Bob per calcolare la chiave che potrà essere utilizzata per crittografare i dati che verranno trasmessi. Precisamente Alice calcola \(A_{1}\) e Bob calcola \(B_{1}\) nel seguente modo:
\[ \begin{array}{l} A_{1} \equiv B^{a} \pmod {p} \\ B_{1} \equiv A^{b} \pmod {p} \\ \end{array} \]In realtà i due valori calcolati da Alice e Bob, \(A_{1},B_{1}\) sono uguali, in quanto
\[ \begin{array}{l} B^{a} \equiv (g^{b})^{a} \equiv g^{ab} \equiv (g^{a})^{b} \equiv A^{b} \pmod{p} \end{array} \]La chiave segreta di \(A\) e \(B\) è quindi il valore comune \(A_{1}=B_{1}\).
Osserviamo che lo scambio dei dati avviene su un canale non sicuro, e un terzo soggetto potrebbe intercettare i valori \(A,B\) trasmessi. Quindi un terzo soggetto che intercetta la comunicazione potrebbe conoscere \(p,g^{a},g^{b}\). Tuttavia per conoscere la chiave scambiata dovrebbe riuscire a calcolare il valore comune \(g^{ab}\). Ad esempio dovrebbe calcolare \(a = \log_{g}g^{a}\), cioè risolvere un problema di logaritmo discreto, che tuttavia sappiamo essere molto difficile.
Si definisce problema di Diffie-Hellman (DHP) il problema di calcolare il valore \(g^{ab} \pmod p\) a partire dai valori di \(g^{a},g^{b} \pmod p\). Chiaramente se si è in grado di calcolare il logaritmo discreto allora è possibile calcolare la chiave comune \(g^{ab}\). Non è dimostrato se vale anche l’inverso, cioè se esiste un algoritmo efficiente per risolvere il problema DHP allora è possibile trovare un algoritmo efficiente anche per il problema del logaritmo discreto.
Esempio 4.1
Scegliamo \(p=11,\ g=2\). Alice sceglie \(a=4\) e Bob \(b=6\), che tengono segreti. Quindi calcolano i seguenti valori:
A questo punto Alice e Bob calcolano la chiave segreta:
\[ \begin{array}{l} A_{1} \equiv 9^{4} \equiv 5 \pmod {11} \\ B_{1} \equiv 5^{6} \equiv 5 \pmod {11} \end{array} \]Quindi la chiave segrete condivisa è uguale a \(5\).
4.2) Attacco all’algoritmo di Diffie-Hellman
L’algoritmo Diffiel-Hellman sembra sicuro dal punto di vista matematico, data la difficoltà di risolvere il problema del logaritmo discreto. Tuttavia ha un punto debole nel tipo di protocollo utilizzato per lo scambio dei dati fra Alice e Bob. E’ infatti vulnerabile all’attacco MITM (man in the middle, o uomo nel mezzo).
Un attacco MITM è un tipo di attacco informatico durante il quale un terzo soggetto riesce ad intercettare una conversazione tra altri due soggetti, senza che i due si accorgano della sua presenza. Ci sono vari tipi di attacchi MITM; in genere lo scopo dell’attacco è quello di conoscere dati sensibili come nomi utente, password, numeri di carte di credito, indirizzi email e altre informazioni utili per eseguire operazioni fraudolente.
Un attacco MITM comprende due fasi note come intercettazione e decrittazione.
Intercettazione
In questa fase il terzo soggetto cerca di intercettare le comunicazioni. In genere gli hacker riescono ad inserirsi in una rette Wi-Fi pubblica o a creare dei finti hotspot Wi-Fi. Questo permette di leggere i dati che si scambiano gli utenti che si collegano alla rete.
Decrittazione
In genere i dati che viaggiano sulle rete sono crittografati. Quindi gli hacker devono essere in grado di decifrare i messaggi scambiati. Per questo hanno a disposizione varie tecniche e algoritmi.
Vediamo come, mediante un attacco MITM, un terzo soggetto può riuscire a intercettare e decrittare una comunicazione che avviene tra Alice e Bob, i quali stanno comunicando fra loro per concordare la chiave segreta comune.
In primo luogo l’hacker intercetta il messaggio pubblico \(A\) che Alice invia a Bob. Quindi calcola il suo valore \(C_{1}\) e lo rimanda ad Alice. La stessa procedura viene fatta con Bob.
Il risultato finale è che Alice e l’hacker hanno una chiave segreta, e Bob e l’hacker ne hanno un’altra, mentre Alice e Bob credono di avere tra loro una chiave segreta comune. In questo modo l’hacker può leggere ogni messaggio, crittografarlo e reinviarlo.
Per contrastare l’attacco MITM esistono diversi strumenti, come l’utilizzo di firme digitali o certificati, che permettono di verificare l’identità di ogni soggetto collegato alla rete. Un esempio è dato dal protocollo STS (Station-To-Station protocol).
5) La crittografia a chiave pubblica di ElGamal
Un vantaggio fondamentale della crittografia asimmetrica è che non è necessario effettuare lo scambio della chiave segreta tra due soggetti che vogliono comunicare. Un altro vantaggio è la possibilità di effettuare la firma digitale, come vedremo nel paragrafo successivo.
L’algoritmo ElGamal è stato presentato nel \(1985\) e costituisce un’alternativa al più famoso e diffuso algoritmo RSA. La robustezza dell’algoritmo RSA si basa sulla difficoltà di fattorizzare i numeri interi molto grandi, ad esempio con \(200\) cifre decimali.
L’algoritmo Elgamal dipende invece dalla difficoltà di risolvere il problema del logaritmo discreto sul campo \(F_{p}\), dove \(p\) è un numero primo molto grande.
Esaminamo l’algoritmo diElGamal. Supponiamo che Alice e Bob vogliano scambiare in sicurezza dei messaggi. Distinguiamo due fasi principali:
Fase 1) Preparazione delle due chiavi di Alice
Per prima cosa Alice genera le sue chiavi privata e pubblica.
Alice sceglie un numero primo \(p\) molto grande in modo da rendere difficile il problema del logaritmo discreto, e sceglie anche un generatore \(g\) modulo \(p\) del gruppo moltiplicativo \(F_{p}^{*}\). Quindi sceglie un numero intero casuale \( 0 \lt a \lt p-1\) che sarà la sua chiave privata e calcola il seguente numero:
Quindi Alice pubblica la terna \((A,g,p)\) che costituisce la sua chiave pubblica, mentre tiene segreto il valore di \(a\), che è la sua chiave privata.
Fase 2) Invio di un messaggio da Bob ad Alice
Supponiamo ora che Bob debba inviare un messaggio \(m\) ad Alice. Il messaggio viene codificato come un elemento del gruppo \(F_{p}^{*}\), cioè come un intero \(2 \le m \lt p\). Mediante un generatore di numeri casuali Bob sceglie un numero casuale \(t\) modulo \(p\). Quindi prepara il suo messaggio cifrato mediante le seguenti formule:
Nella preparazione del messaggio cifrato Bob utilizza la chiave pubblica \(A\) di Alice.
Bob quindi trasmette ad Alice la coppia \((c_{1},c_{2})\), che costituisce la cifratura del messaggio \(m\).
Per decifrare il messaggio Alice, conoscendo la sua chiave privata \(a\) e \(c_{1}\), per prima cosa calcola la seguente quantità:
Quindi decritta il messaggio mediante il prodotto \(x \cdot c_{2}\):
\[ \begin{array}{l} x \cdot c_{2} \equiv (c_{1}^{a})^{-1} \cdot c_{2} \equiv (g^{at})^{-1} \cdot (mA^{t}) \equiv \\ (g^{at})^{-1} \cdot (m(g^{at})) \equiv m \pmod{p}\\ \end{array} \]Il calcolo delle potenze può essere effettuato mediante l’algoritmo di esponenziazione veloce descritto su questo sito nel seguente articolo. Per il calcolo dell’inverso moltiplicativo si può usare l’algoritmo esteso di Bezout-Euclide.
Osservazioni
Come nella procedura per lo scandio della chiave segreta, la sicurezza dell’algoritmo per la crittografia ElGamal si basa sull’ipotesi che, anche conoscendo \(g,g^{a}\), non si riesce a calcolare la chiave segreta \(a\). Questa si chiama anche ipotesi di Diffie-Hellman.
Un vantaggio dell’algoritmo di ElGamal è che lo stesso testo in chiaro ripetuto più volte dà sempre un testo cifrato diverso.
Uno svantaggio è che il messaggio codificato che viene trasmesso ha lunghezza doppia del messaggio in chiaro. Infatti il testo cifrato è costituito da una coppia di interi di \(\mathbb{Z_{p}}\), mentre il testo in chiaro è un solo intero.
Esempio 5.1
Scegliamo il numero primo \(p=2357\). Quindi scegliamo il generatore \(2\) del gruppo moltiplicativo \(\mathbb{Z}_{2357}^{*}= \{1,2,3,\cdots, 2356\}\). Scegliamo come nostra chiave privata \(a=1317\). Calcoliamo quindi la nostra chiave pubblica
La nostra chiave pubblica completa è quindi \(\{2357,2,1529\}\).
6) La firma digitale di ElGamal
Oltre a garantire l’integrità e la segretezza dei messaggi, un buon sistema crittografico deve anche essere in grado di dimostrare l’autenticità della sorgente che invia il messaggio. La firma digitale è l’equivalente informatico della tradizionale firma apposta su un documento cartaceo.
Un sistema di firma digitale ha i seguenti obiettivi:
- autenticità: garantire l’identità del soggetto che ha firmato digitalmente il documento;
- integrità: garantire che il documento non è stato modificato dopo essere stato firmato;
- non ripudiabilità: il mittente non può ripudiare la sua firma e quindi il contenuto del documento;
- non riusabilità: la firma è strettamente collegata al documento, e non può essere utilizzata in un altro documento.
6.1) La funzione hash
Una caratteristica importante per realizzare una firma digitale efficiente è data dalla possibilità di utilizzare solo una piccola parte dei dati del documento da firmare, altrimenti la procedura sarebbe lenta e la firma sarebbe grande quasi come il documento. La soluzione più diffusa è utilizzare una funzione hash crittografica.
Definizione 6.1 – Funzione di hash
Una funzione di hash è una funzione facile da calcolare, ma molto difficile da invertire. Precisamente una \(F: A \to B\) è una funzione di hash se sono verificate queste due condizioni:
In altre parole il problema di calcolare l’inverso della funzione è intrattabile, cioè non esiste un algoritmo efficiente per calcolare il valore inverso della funzione.
Nel caso della firma digitale una funzione di hash, indicata con il simbolo \(H\), prende in input una stringa di lunghezza variabile \(m\), anche di milioni di bit, e produce in output una stringa di lunghezza fissa \(n\), chiamata message digest. In simboli
Proprietà di una funzione di hash
- Dato un messaggio \(m\), deve essere possibile calcolare rapidamente il message digest \(H(m)\).
- Deve essere computazionalmente intrattabile il problema inverso, cioè dato un valore \(y\) trovare un \(m\) tale che \(H(m)=y\).
- Deve essere pressoché nulla la probabilità di trovare due messaggi diversi \(m_{1},m_{2}\), che abbiano lo stesso risultato, cioè \(H(m_{1})= H(m_{2})\). Questa proprietà viene chiamata resistenza alle collisioni.
Tra gli algoritmi di hashing più utilizzati ricordiamo MD5, sviluppato da Rivest, che produce un output di \(128\) bit, e l’algoritmo Secure Hash Algorithm che produce un output di 160 bit.
Di seguito sono presentati alcuni semplici esempi di funzioni di hash.
Metodo della divisione e del resto
In questo metodo si divide il valore del messaggio per la dimensione di una tabella di hash di dimensione \(m\), e si prende il resto come valore della funzione. Il metodo della divisione consiste nell’associare ad una chiave \(k\) il resto della divisione per \(m\):
Ad esempio se \(m=14\) e \(k=100\) allora \(H(k)=2\).
Il procedimento è semplice e veloce, tuttavia è importante la scelta del modulo \(m\). Ad esempio \(m\) non dovrebbe essere una potenza di \(2\). Infatti se \(m=2^{t}\), allora il valore \(H(k)\) coincide con i \(t\) bit meno significativi del numero \(k\). Una buona scelta è un numero primo non troppo vicino ad una potenza di due.
Metodo del quadrato centrale
Consideriamo una tabella con \(d=2^{m}\) posizioni disponibili e sia \(k\) la stringa binaria di una chiave. Il metodo consiste nel calcolare \(k^{2}\) ed estrarre \(m\) bit al centro del risultato. Il valore risultante è inferiore a \(d\) e viene utilizzato per indirizzare la tabella di hashing.
Un aspetto importante di questo algoritmo è che tutti i bit del numero contribuiscono al risultato finale del valore di hash.
Esempio 6.1
Consideriamo un numero di \(4\) cifre, ad esempio \(x=1234\). Per avere numeri casuali con distribution uniforme possiamo dividere per \(10000\). Effettuiamo alcuni calcoli a partire da \(x_{0}=0,1234\). Abbiamo
Il problema delle collisioni
Si ha una collisione se, dati due valori distinti delle variabili di input, la funzione di hash produce lo stesso valore in output. Quindi due messaggi diversi producono lo stesso message digest. E’ molto importante scegliere un algoritmo che ha una forte resistenza alle collisioni, poiché altrimenti un soggetto esterno potrebbe sostituire un messaggio con un altro senza alterare il valore di hash, potendo compromettere l’integrità dei dati e l’autenticità del mittente.
6.2) L’algoritmo ElGamal per la firma digitale
Nella crittografia asimmetrica le procedure per la firma digitale utilizzano entrambe le chiavi, quella pubblica e quella privata, con modalità simili alle procedure per la cifratura e decifratura dei messaggi. Con l’algoritmo RSA è abbastanza facile implementare la forma digitale di un documento. Per i dettagli vedi ad esempio l’articolo su questo sito.
La procedura per la gestione della firma digitale comprende tre passi principali: generazione della chiave, firma e verifica delle firma. Lo schema seguente illustra i passi principali del metodo di ElGamal, presentato nel 1984.
Lo schema precedente per semplicità prevede la trasmissione del messaggio in chiaro. Naturalmente, se il messaggio deve essere riservato, allora bisogna prevedere la cifratura del messaggio mediante la chiave privata del mittente e la decifratura da parte del destinatario mediante la chiave pubblica del mittente.
Descriviamo ora in dettaglio i passi del metodo di ElGamal.
Supponiamo che Alice voglia inviare un messaggio \(m\) con la sua firma digitale.
In primo luogo Alice sceglie un numero primo \(p\) molto grande e una radice primitiva \(g\) modulo \(p\). Sceglie anche una funzione di hash \(H\), resistente alle collisioni.
Generazione della chiave
Alice sceglie un numero intero \(a\) che tiene segreto e calcola il seguente valore:
La quantità \(a\) è la chiave segreta, mentre sono pubblici i valori \(A,p,g\).
Firma digitale
Supponiamo ora che Alice voglia firmare un messaggio \(m\), rappresentato in forma binaria con un numero \(1 \lt m \lt p\). Alice sceglie un numero casuale \(1 \lt k \lt p\) che soddisfa la relazione \((k,\ p-1)=1\). Calcola \(H(m)\) mediante la funzione di hash e quindi calcola i seguenti valori:
La firma digitale di Alice sul documento \(m\) è costituita dalla coppia \(B_{1},B_{2}\).
Verifica della chiave
Bob riceve il messaggio \(m\) insieme alla firma digitale. Ricalcola il valore \(H(m)\) e verifica la firma di Alice mediante il seguente calcolo:
Se i valori sono uguali, allora la firma è verificata.
Chiaramente, se un terzo soggetto che intercetta la trasmissione fosse in grado di risolvere il problema del logaritmo discreto, allora potrebbe risolvere l’equazione \(A \equiv g^{a} \pmod{p}\) e quindi conoscere il valore segreto \(a\) di Alice.
L’algoritmo DSA
Nel 1991 l’istituto americano per gli standard (NIST) ha proposto l’algoritmo DSA (Digital Signature Algorithm) che è una variante dell’algoritmo di ElGamal.
Conclusione
La teoria dei numeri è stata per un lungo periodo una branca puramente teorica della matematica, con poche applicazioni pratiche. Ricordiamo l’affermazione di Gauss: “La matematica è la regina delle scienze – e la teoria dei numeri è la regina della matematica“.
Nel corso degli ultimi anni la situazione è cambiata in modo significativo. Sono state implementate molte applicazioni pratiche della teoria dei numeri in vari settori, in particolare nel campo della crittografia.
Il problema del logaritmo discreto è un esempio importante di problema prettamente teorico della teoria dei numeri, la cui soluzione ha anche una grande importanza pratica. Lo stesso vale per il problema della fattorizzazione degli interi, che è alla base dell’algoritmo RSA.
La teoria dei numeri e più in generale la matematica discreta stanno avendo applicazioni sempre più importanti in molti settori della scienza e della tecnologia, ad esempio nel campo dell’informatica e anche nella fisica quantistica.
Bibliografia
[1]Niven, Zuckerman, Montgomery – An introduction to the Theory of Numbers (Wiley)
[2]W. LeVecque – Fundamentals of Number Theory (Addison-Wesley)
[3]Neal Koblitz – A Course in Number Theory and Cryptography (Springer)
[4]J. Kraft, L. Washington – An Introduction to Number Theory with Cryptography (Chapman and Hall, 2018)
[5]Crandall, Pomerance – Prime numbers: A Computational Perspective (Springer)
0 commenti