(Classe 5a) - Sistemi e Reti

L’algoritmo DH, pubblicato nel 1976, permette a due interlocutori di generare una stessa chiave simmetrica (PSK-Pre Shared Key), usata per la cifratura rapida di messaggi anche di grandi dimensioni; utilizza la stessa teoria matematica che è alla base della generazione delle chiavi asimmetriche RSA, già illustrate.

Siccome il risultato dell’uso di DH è l’ottenimento della stessa chiave simmetrica presso i due partner, l’algoritmo viene spesso detto impropriamente “di scambio chiavi”; ma la chiave PSK in realtà non viene mai scambiata: essa è generata localmente, in base ad altri elementi scambiati, che sono però insufficienti a un terzo per generare la stessa PSK.

L’algoritmo, come vediamo brevemente nel seguito, è resistente all’intercettazione o eavesdropping (origliare) dei messaggi scambiati, ma non all’attacco Man-In-The-Middle (MITM), ossia alla modifica dei messaggi scambiati, se i due partner non si sono previamente autenticati con certezza. Ognuno crederebbe di parlare con l’altro, mentre sta parlando con l’hacker. Per questo occorre che i messaggi scambiati siano firmati dal mittente con qualche forma di certificato digitale, di solito garantito da una Certification Authority della PKI-Public Key Infrastructure.

La robustezza del sistema si basa sulla difficoltà computazionale del calcolo del “logaritmo discreto” di un numero, che non ha per ora trovato (per fortuna) una soluzione efficiente.

L’implementazione più semplice di DH prevede i seguenti passi:

• Alice sceglie un piccolo numero generatore g (di solito 2 o 5), un grande numero primo p e un suo numero segreto a, grande anch’esso, ma non come p
• Alice calcola A = g^a mod p, e invia in chiaro a Bob g, p ed A

• Bob sceglie un suo numero segreto b grande, calcola B = g^b mod p, e lo invia ad Alice
• Alice calcola PSK = B^a mod p, e Bob calcola PSK = A^b mod p
• Le due PSK calcolate da Alice e da Bob sono la stessa chiave simmetrica, legata a g^ab = g^ba.

Un terzo che ascolti gli scambi tra Alice e Bob, ma non conosca a e b, non può ricostruire la PSK.

Esempio numerico con numeri piccoli:

• Alice sceglie g=2, p=23 e a=6 (segreto)
• Alice calcola A = 2⁶ mod 23 = 64 mod 23 = 18 e lo invia a Bob
• Bob sceglie b=15 (segreto), calcola B = 2¹⁵ mod 23 = 32768 mod 23 = 16 e lo invia ad Alice
• Alice calcola la PSK = 16⁶ mod 23 = 4
• Bob calcola la PSK = 18¹⁵ mod 23 = 4, identica a quella di Alice.

Conoscendo solo g, p, A e B, ma non a e b, non si può risalire alla PSK=4 generata da Alice e Bob.