L’algoritmo di crittografia Diffie-Hellman

di Fabrizio Sinopoli

scritto il

In questo articolo presenteremo l’implementazione originale e la più semplice dell’algoritmo di crittografia a chiave pubblica Diffie-Hellman, che porta proprio il nome dei “padri” della crittografia asimmetrica.

Nel 1976 Diffie ed Hellman hanno descritto un protocollo per lo scambio di una chiave segreta sopra un canale insicuro; tale meccanismo era stato inteso essenzialmente per risolvere il problema dell’avvio di un normale sistema di cifratura a chiavi simmetriche, quale il DES, ma in realtà ha posto le basi della crittografia a chiavi pubbliche.

Il protocollo, utilizzato da due interlocutori Alice e Bob, può essere descritto come segue:

  • Alice e Bob scelgono pubblicamente un insieme di interi G = [0,N – 1] ed un suo elemento s.
  • Alice sceglie in modo casuale un elemento a di G, calcola A = sa mod N ossia (s elevato a) modulo N e lo invia a Bob.
  • Bob sceglie in modo casuale un elemento b di G, calcola B= sb mod N ossia (s elevato b) mod N e lo invia ad Alice.
  • Alice, ricevuto B , calcola K = (B elevato a) modulo N
  • Bob, ricevuto A, calcola K = (s elevato a)(elevato b) modulo N

Nota: le formule matematiche sono espresse in modo esteso.

In questo modo entrambi gli interlocutori possiedono la chiave K ma sopra il canale insicuro sono stati trasferiti solo N, s, A e B che non consentono di ricostruire K.

In realtà la determinazione di a, noti s ed A, richiede la soluzione del problema del logaritmo discreto che consiste nella determinazione dell’intero che corrisponde al logaritmo in una base intera di un intero di cui è noto solo resto della divisione rispetto al modulo N. Tale problema è computazionalmente difficile.

Il brevetto originale, ora scaduto, è disponibile a questa pagina.

I Video di PMI

Video su Facebook: impariamo dai più bravi