Il Problema del Logaritmo Discreto si basa sulla difficoltà del calcolo di un logaritmo discreto su gruppi ciclici.
Introduzione
Gruppi Ciclici
Un gruppo ciclico è costituito dagli insiemi dei numeri interi modulo n. In questo insieme tutte le operazioni sono effettuate con il modulo.
Esempio: considerando l'insieme degli interi modulo 31, indicato con Z31, alcune operazioni sono:
15 + 24 = 8 perché 15 + 24 = 39 mod 31 = 8
5 * 10 = 19 perché 5 * 10 = 50 mod 31 = 19
72 = 18 perché 72 = 49 mod 31 = 18
Viene scelto un valore di n tale che sia un numero primo sufficientemente elevato. Questo insieme di numeri, che varia da 1 a (n-1), ha la caratteristica di possedere un numero generatore tale che ogni numero può essere generato tramite l'elevazione a potenza del generatore.
In altre parole, se $\alpha$ è un generatore di un gruppo G, allora $\forall b \in G$,
(1)dove $i \in G$
Problema del Logaritmo Discreto
Il problema del Logaritmo Discreto (Discrete Logarithm Problem - DLP) è definito come segue: dato un numero primo p, un generatore $\alpha$ di e un elemento $b \in Z_p$ trovare un numero intero x, con $0 \leq x \leq p-2$ tale che
(2)Il Problema del Logaritmo Discreto Generalizzato (Generalized Discrete Logarithm Problem - GDLP) è il seguente: dato un gruppo ciclico G di ordine n, un generatore $\alpha$ e un elemento $b \in G$, calcolare quel numero $x \in G$ tale che
(3)Problema di Diffie-Hellman
Un problema strettamente correlato a quello del logaritmo discreto è il Problema di Diffie-Hellman (Diffie-Hellman Problem - DHP) seguente: dato un numero primo p, un generatore $\alpha$ di Z*p e gli elementi $\alpha^a mod\:p$ e $\alpha^b mod\:p$, trovare $\alpha^{ab} mod\:p$.
Nel 1976, Whitfield Diffie e Martin Hellman applicarono il problema che porta il loro nome definendo un protocollo per scambiare una chiave attraverso un canale non sicuro. Tramite questo protocollo, è possibile utilizzare un algoritmo simmetrico e riuscire a concordare tra le due parti che si scambiano messaggi una chiave in modo sicuro.
Questo protocollo riuscì quindi a superare uno dei problemi più seri che affliggono la crittografia simmetrica, ovvero lo scambio della chiave.
Si può dimostrare che
(4)ovvero, il problema di Diffie-Hellman può essere riducibile in tempo polinomiale al problema del Logaritmo Discreto: il problema di Diffie-Hellman non può essere più difficile del problema del logaritmo discreto. Infatti, potendo risolvere quest'ultimo con un algoritmo efficiente, è possibile risolvere efficientemente anche quello di Diffie-Hellman.
