Il logaritmo discreto

Vediamo di parlare del logaritmo discreto e della difficoltà a cui si va incontro dal punto di vista matematico. Abbiamo visto nei sistemi RSA e Diffie Hellman che è un protocollo crittografico che consente a due soggetti di stabilire una chiave condivisa e segreta utilizzando un canale di comunicazione insicuro (publico) seza che si siano incontrati prima.

Definiamo il logaritmo discreto. Consideriamo un gruppo ciclico G di ordine n con operazione di gruppo * e sia g un suo generatore. Allora si definirà l’esponenziale discreto comedove x è un intero non negativo. Il problema del logaritmo discreto ( problema DL) consiste nel calcolare x una volta assegnati G, g ed y come precedentemente indicato. I dati g ed y prenderanno rispettivamente il nome di base ed argomento del logaritmo discreto. Se vale la 1.1 si ha che

dove log_g y è appunto il logaritmo discreto di y in base g.

Soluzioni del problema logaritmo discreto

Se G è un gruppo ciclico generato da g, allora la sua soluzione al problema del logaritmo discreto in generale non è unica. Infatti se l’ordine di G è n, si ha g^x+kn = g^x  (gⁿ)^k = g^x = y per ogni k appartenente agli interi relativi

Possiamo dimostrare il seguente teorema.

Teorema. Sia g generatore del gruppo ciclico G di ordine n. Allora

Dimostrazione. Supponiamo x z mod n. Allora, per definizione di congruenza, nɪ (x- z) quindi esiste k appartente a interi relativi tale che x – z = kn. Ne segue che g ^x-z = g^kn = 1 ovvero g^x = g^z. Viceversa, sia per ipotesi g^x = g^z. Se, per assurdo, x e z non fossero cogrui modulo n, allora n non dividerebbe x – z quindi g ^x-z ≠ 1, contro l’ipotesi. Quindi x e z devono essere congrui modulo n.

Dal teorema precedente segue che, se il problema del logaritmo discreto ha soluzione, allora questa sarà unica modulo l’ordine del gruppo.

Osservazione 1.

Osserviamo che g^x non dipende da x ma dalla sua classe d’equivalenza modulo n che denotiamo con [x]n. Perciò ha senso definire g^[x]n = g^x.

Osservazione 2

Sarebbe possibile definire in modo analogo a quanto fatto prima il logaritmo discreto su un gruppo generico G non ciclico o con una base che non sia un generatore. In questi casi non sarebbe però garantita l’esistenza della soluzione del problema. In queste situazioni è comunque possibile restringersi al sottogruppo ciclico generato dalla base del logaritmo per poter risolvere il problema per ogni elemento di quel sottogruppo. In generale, se non diversamente specificato, nei discorsi considereremo gruppi ciclici.

Difficoltà del problema

Ci sono diversi parametri che infuenzano la difficoltà del problema. Uno di questi è l’ordine del gruppo ciclico nel quale si sta lavorando; un ordine grande aumenta ovviamente i possibili elementi e quindi il numero di operazioni che l’algoritmo deve eseguire. Vedremo che non solo la grandezza dell’ordine è importante ma anche la sua fattorizzazione in primi. Vediamo ora che la difficoltà dipende anche dal gruppo scelto.

Conclusioni

La trattazione continua e si capisce che sono problemi matematici abbastanza complessi, si voleva qui solo dare un idea di cosa si sta parlando.