Come abbiamo spiegato, l'idea iniziale di Hellman per la generazione delle chiavi si basava sulle cosiddette funzioni unidirezionali: funzioni matematiche semplici da calcolare, ma difficili da invertire.
Consideriamo per prima cosa un esempio di funzione bidirezionale, cioè una normale funzione facile da invertire: la funzione 3x (tre elevato a x). Essa ricava da x un altro numero (il valore della funzione) moltiplicando 3 (la base) tante volte quanto è il valore dell'esponente x; così per esempio, se x = 2, la funzione assume il valore 3×3 = 9, cioè calcola 9 a partire da x=2.
Notiamo che al crescere di x, cresce anche il valore dell'elevamento a potenza: perciò è relativamente facile, conoscendo quest’ultimo, risalire al numero di partenza. Per esempio, se il valore della funzione è 81 è chiaro che x, cioè il numero di partenza, è 4, perché 34 dà 81. Anche se per errore supponessimo che x sia 5, la scoperta e la correzione dell’errore non presenterebbero difficoltà. Un semplice calcolo rivela infatti che 35 dà 243: quindi è stato scelto un numero di partenza troppo alto. Attribuiremo quindi a x il valore 4, che è esatto. In breve, nell’aritmetica normale invertire una funzione non è difficile, perché qualche tentativo e un po’ di buon senso permettono, noto il calcolo della funzione, di scoprire il numero x di partenza.
Tutto questo non è possibile (o è molto difficile) con le funzioni unidirezionali. L’aritmetica dei moduli, per esempio è un campo della matematica ricco di funzioni unidirezionali. L'aritmetica dei moduli è chiamata a volte anche aritmetica dell’orologio dagli studiosi, perché si applica alle somme di ore sul quadrante di un orologio. Per esempio sommando 4 ore alle 11, non si ottiene 15 ma 3. Il valore 3 è il resto (modulo) della divisione fra 15 e 12.
In pratica la funzione modulo (indicata nel seguito con mod) calcola il resto della divisione fra due interi: così per esempio 13 mod 5 = 3, in quanto 12/5 fa 2 con il resto di 3. Supponiamo che qualcuno ci abbia detto che 3x mod 7 = 1 e ci abbia invitato a scoprire il valore di x. L’intuito non ci aiuta, perché l’aritmetica dei moduli non è di uso comune. Tirando a indovinare, potremmo partire dall’ipotesi che x sia 5, e calcolare 35 mod 7. Il risultato è 5 (35 = 243 e il resto della divisione per 7 vale 5). Questo valore è troppo grande, visto che il numero cercato deve far sì che la funzione assuma il valore 1. Potremmo esser tentati di ridurre il valore di x e riprovare. In realtà, in tal modo andremmo nella direzione sbagliata, perché la risposta giusta è 6.
Il fatto è che il modulo non cresce al crescere di x e dunque (a differenza dell'elevamento a potenza) è una funzione molto difficile da invertire (si tratta appunto di una funzione unidirezionale).
L’idea di Hellman si basava appunto su una funzione unidirezionale della forma Yx mod P. All’inizio, Alice e Bob devono accordarsi sui valori di Y e P. Quasi tutti i valori sono accettabili, fatta eccezione per un paio di limitazioni: P dev’essere numero primo, e Y dev’essere minore di P. Non è necessario che i valori in questione siano segreti; perciò Alice può telefonare a Bob e suggerire Y = 7 e P = 11. Come si vedrà, l’eventualità che la linea telefonica non sia sicura ed Eva abbia ascoltato la conversazione è irrilevante per la sicurezza del sistema crittografico. Dunque, Alice e Bob hanno concordato la funzione unidirezionale 7x (mod 11). A questo punto possono avviare il procedimento che permetterà loro di stabilire una chiave segreta senza incontrarsi. Ecco nel dettaglio come avviene lo scambio:
Passo | Alice | Bob |
1 | Sceglie un numero A (per esempio A = 3) e lo tiene segreto. | Sceglie un numero B (per esempio B = 6) e lo tiene segreto |
2 | Inserisce il numero segreto A come x
nella funzione unidirezionale e calcola: Yx mod P = 73 mod 11 = 343 mod 11 = 2 |
Inserisce il numero segreto B come x
nella funzione unidirezionale e calcola: Yx mod P = 76 mod 11 = 117649 mod 11 = 4 |
3 | Chiama α il risultato e lo comunica a Bob | Chiama β il risultato e lo comunica a Alice |
4 | Si serve del
risultato β di
Bob e del suo numero segreto A per
calcolare: βA mod P = 43 mod 11 = 64 mod 11 = 9 |
Si serve del
risultato α di
Alice e del suo numero segreto B per
calcolare: αB mod P = 26 mod 11 = 64 mod 11 = 9 |
Ora che Alice e Bob hanno concordato la chiave (senza incontrarsi e usando linee telefoniche pubbliche), possono usarla per cifrare il messaggio. Per esempio, potrebbero usare il numero 9 per effettuare una cifratura DES (in realtà il DES usa come chiavi numeri molto più grandi, ma in realtà questo vale anche per il procedimento appena descritto).
Bob e Alice si erano scambiati solo le informazioni indispensabili a stabilire la chiave, ma le medesime informazioni erano insufficienti per Eva. Il metodo Diffie-Hellman-Merkle di scambio delle chiavi, come è chiamato, permette ad Alice e Bob di condividere un segreto per mezzo di un pubblico scambio di informazioni. In effetti, si tratta di una delle scoperte più controintuitive della storia della scienza; essa ha costretto la crittografia ufficiale a riscrivere le regole della messa in codice.
Sito realizzato in base al emplate offerto da
http://www.graphixmania.it