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.
