Cifrari a chiave pubblica
L'algoritmo DH (Diffie-Hellman)
Il cifrario RSA

L'algoritmo Diffie-Hellman risale al 1976 ed è quindi uno dei più antichi algoritmi a chiave pubblica; gli autori furono anche i primi a proporre l'idea dei cifrari a chiave pubblica.

L'algoritmo è particolarmente adatto alla generazione di una chiave segreta tra due corrispondenti che comunicano attraverso un canale non sicuro (pubblico). La sua sicurezza si basa sulla complessità computazionale del calcolo del logaritmo discreto.

Supponiamo di avere i soliti Aldo e Bruno che vogliono scambiarsi una chiave segreta in modo sicuro.

  1. Aldo genera e comunica pubblicamente un numero primo $N$ molto elevato (p.es. 1024 bit, circa 300 cifre decimali) e un generatore g (che esiste sicuramente essendo N primo); si potrebbero anche usare due numeri $N, g$ pubblicati da un qualche ente pubblico.
  2. Aldo genera un numero casuale $a <N $ e calcola $A = g^a \mod N$, ed invia $A$ a Bruno. A questo punto $N, g, A$ sono pubblici, $a$ è noto solo ad Aldo.
  3. Bruno genera un numero casuale $b <N $ e calcola $B = g^b \mod N$, ed invia $B$ ad Aldo. A questo punto $N, g, A, B$ sono pubblici, $a$ è noto solo ad Aldo, $b$ solo a Bruno.
  4. Aldo calcola $k = B^a \mod N$.
  5. Aldo calcola $k = A^b \mod N$.

Inutile aggiungere che i due numeri $k$ sono uguali! Infatti entrambe valgono $g^{ab} \mod N$.

A questo punto Aldo e Bruno possono usare $k$ come chiave per comunicare con un cifrario simmetrico p.es. DES.

Esempio

  1. Aldo sceglie $N = 17, g = 3$ (3 è generatore di 17).
  2. Aldo sceglie $a = 6$ e quindi $A = 3^6 \mod 17 = 15$.
  3. Bruno sceglie $b = 11$ e quindi $B = 3^{11} \mod 17 = 7$.
  4. Aldo calcola $k = 7^6 \mod 17 = 9$.
  5. Bruno calcola $k = 15^{11} \mod 17 = 9$.

La chiave segreta è quindi $9$.

Sicurezza

La cosa importante per la sicurezza è che un terzo che intercettasse i quattro numeri $N, g, A, B$ non sarebbe in grado di ottenere $k = g^{ab} \mod N$ non conoscendo né $a$ né $b$. In realtà basterebbe calcolarli $a = \log_g{A} \quad e \quad b = \log_g{B}$ ma il calcolo del logaritmo discreto è computazionalmente proibitivo per numeri molto grandi (1024 bit e oltre).

Come altri sistemi a chiave pubblica anche DH è però esposto all'attacco del terzo uomo interposto. Nel nostro esempio immaginiamo che Carlo intercetti il numero A che Aldo invia a Bruno e, fingendo di essere Bruno, generi un suo numero B e lo invii ad Aldo. A questo punto Aldo e Carlo generano la chiave segreta k e comunicano via DES; e Carlo può tranquillamente leggere tutti i messaggi che Aldo crede di inviare a Bruno! Peggio ancora: Carlo può ripetere il gioco anche con Bruno fingendosi Aldo e di qui in avanti, intercettare e leggere tutta la corrispondenza tra gli inconsapevoli Aldo e Bruno.

Per prevenire simili attacchi la soluzione è anche qui quella di usare un ente certificatore che garantisca l'identità dei corrispondenti. Aldo e Bruno potranno p.es. identificarsi con un meccanismo di firma digitale, utilizzando le chiavi pubbliche fornite dall'ente certificatore.

Di questo tipo è il protocollo Diffie-Hellman autenticato proposto da Diffie, van Oorschot, e Wiener nel 1992 (DVW92).



Fonti bibliografiche e collegamenti

Valido HTML 4.01!