Problema del Logaritmo Discreto

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)
\begin{align} b = \alpha^{i} \end{align}

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)
\begin{align} \alpha^x\:mod\:p = b \end{align}

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)
\begin{align} \alpha^x = b \end{align}

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)
\begin{align} DHP \leq_p DLP \end{align}

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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License