Datemi una chiave e… anzi due!

Orologi asimmetrici

La ricerca di Diffie, Hellman e Merkle si concentrò su quelle che sono denominate funzioni asimmetriche.
Una funzione è asimmetrica se non permette, o lo permette con grande difficoltà, di risalire ai dati di origine una volta noto il risultato. Nel caso simmetrico cui siamo normalmente abituati, se per esempio si conosce l’esito di una moltiplicazione si possono usare delle divisioni per risalire ai termini del calcolo originario o si possono usare i logaritmi per risalire all’originale elevamento a potenza.
Vi è però una branca della matematica detta aritmetica modulare in cui abbondano le funzioni asimmetriche e per illustrarne il funzionamento possiamo ricorrere ad un semplice esempio che coinvolge un orologio.
Supponiamo che alle 10 del mattino incontriate un vostro amico e che questi vi dica di avere un impegno e di essere disponibile solo dopo 6 ore. Non è un problema per voi capire che un appuntamento col vostro amico non possa essere fissato prima delle 4 di pomeriggio. Quello che avete fatto inconsapevolmente (a meno che non siate dei matematici) è di effettuare una somma in modulo 12!
Cioè avete sommato 10 + 6 = 16, ne avete effettuato la divisione per 12 e avete preso come dato di uscita il resto di questa divisione che è appunto 4.
La peculiarità di questa operazione è che ci sono un numero enorme di combinazioni di orari e intervalli di tempo la cui somma può dare come risultato 4 e questo introduce nel calcolo l’asimmetria cercata in quanto, mentre è facile trovare il risultato partendo dagli addendi iniziali, il contrario può essere particolarmente difficile.
Dopo due anni di lavoro su questo tipo di funzioni, Diffie, Hellman e Merkle diedero una dimostrazione dei risultati trovati nel giugno del 1976 di fronte all’attonita platea di crittografi specialisti alla National Computer Conference.
Vediamone un esempio con dei numeri sufficientemente piccoli e maneggevoli.

La funzione unidirezionale individuata dai nostri è la Y ^x(mod P).

Quindi i soliti Alice e Bob che volessero scambiarsi dei messaggi segreti, per utilizzare questa funzione, devono dapprima accordarsi sui due numeri Y e P. La particolarità dell’algoritmo, come vedremo, è che questa scelta può avvenire tranquillamente per mezzo di una telefonata non protetta in quanto anche venendo a conoscenza dei due valori, la curiosa Eva non ne trarrebbe alcuna utilità.

Supponiamo che Alice e Bob si mettano d’accordo per usare Y=7 e P=13 (l’algoritmo richiede che P sia un numero primo e Y sia minore di P).
A questo punto Alice e Bob sceglieranno ciascuno un numero, che rimarrà segreto, che nel nostro esempio sarà A=3 per Alice e B=10 per Bob.
Entrambi applicheranno la funzione unidirezionale al loro numero segreto usando i parametri concordati. Avremo quindi

7³(mod 13)=5 che chiameremo Alfa

per Alice e

7¹⁰(mod 13)=4 che chiameremo Beta

per Bob.
I due numeri Alfa e Beta così trovati possono essere trasmessi rispettivamente verso Bob e verso Alice per mezzo di una trasmissione non protetta.
Quando Alice riceverà il numero Beta di Bob effettuerà l’operazione:

Beta^A(mod P) → 4³(mod 13)=12

e Bob effettuerà l’operazione:

Alfa^B(mod P) → 5¹⁰(mod 13)=12

Entrambi saranno pervenuti alla stessa soluzione che in questo caso è 12 e questa sarà la loro chiave da utilizzare per crittografare i loro messaggi.

Notiamo che, per il calcolo della chiave, sia Alice che Bob hanno usato una informazione, i numeri A e B rispettivamente, che non sono mai stati comunicati a nessuno e, a causa dell’asimmetria della funzione esponenziale modulare, anche venendo a conoscenza dei numeri Alfa e Beta, che invece sono stati comunicati, l’ipotetica Eva non riuscirebbe a risalire ai valori A e B che li hanno originati. Ovviamente nei casi reali si utilizzano numeri molto grandi per rendere effettivamente inattuabile la ricerca per tentativi di A e B a ritroso.