# Cryptocaffè: Diffie-Hellman

Scritto da il

Supponete di conoscere una persona per corrispondenza, senza averla mai incontrata. E di dover comunicare qualcosa si segreto a questa persona senza che nessuno sappia cosa vi state dicendo. Per farlo, anche per motivi di efficienza, l’idea migliore è utilizzare la crittografia simmetrica, ovvero quella tecnica per cui si utilizza la stessa chiave, nota ad entrambe le parti, per cifrare e decifrare un messaggio (un esempio è AES)

Perfetto. Ma come scambiarsi la chiave o accordarsi su di essa se il canale di comunicazione è insicuro? Non puoi certamente inviarla in chiaro, chiunque potrebbe leggerla. Serve quindi un algoritmo in grado di generare in modo sicuro una chiave unica per entrambi. Qui viene in aiuto Diffie-Hellman

Aritmetica modulare

Alla base dell’algoritmo di scambio delle chiavi c’è quella che si chiama aritmetica modulare, che a discapito del nome apparentemente complesso fa parte della nostra vita tutti i giorni.

Si tratta di un modo di contare per cui gli interi “ruotano” intorno ad un numero n detto modulo. Ed è la logica che quotidianamente applichiamo alle ore dell’orologio. Nello specifico modulo24 (o 12, se ragioniamo in AM/PM).

Se infatti alle 23 vi dicessi “vediamoci tra 6 ore” sapreste tutti che ci dovremmo vedere alle 5 . Ovvero 29 mod(24) . In forma “matematica” diciamo che 29 e 5 sono congruenti modulo 24

Mod

Diffie-Hellman si basa sullo stesso principio di base, utilizzando però un numero primo come modulo e aggiungendo l’elevamento a potenza

L’algoritmo (semplificato)

Prendete sempre l’esempio precedente dell’orologio: se vi dicessi che sono alle ore 14, e che sono partito dalle ore 9, sapreste dirmi con certezza con quale numero ci sono arrivato? La risposta è no, infatti partendo dalle 9 posso arrivare alle 14 sommando 5, ma anche 29 infatti

Derivante dal fatto che 38 - 24 = 14 che è pertanto raggiungibile in diversi modi.

Per concordare un’ora con un amico senza che nessuno la scopra si può adottare un algoritmo come quello seguente

  • Decise a priori ora di partenza o (nell’esempio 17) e modulo p (nel caso delle ore 24), che possono essere pubblici

  • Io, Alice, scelgo un numero < 24 ( supponiamo 9 ) **che rimarrà segreto **e lo sommo ad o modulo 24

  • Bob fa altrettanto, supponiamo scelga 10

  • Ci scambiamo i risultati ottenuti, 3 e 2 e sommiamo a questi il nostro valore segreto

Come si può vedere sono giunti alla stessa ora (chiave) senza scambiarsi dati segreti . Come abbiamo visto infatti è difficile risalire al valore segreto conoscendo il risultato della somma delle ore in modulo

L’algoritmo effettivo

L’algoritmo effettivo funziona sullo stesso principio di base, ma con costrutti matematici più complessi. Parte infatti da un modulo p che deve essere un numero primo. Utilizza le potenze al posto delle somme e “la partenza” è un numero detto generatore, g

Il nome è dovuto al fatto che elevando g ad una potenza x, al variare di x tra 1 e p-1 , è possibile generare tutti i numeri compresi tra 1 e p, in modulo

Ad esempio se prendiamo p=5 2 è un generatore infatti

e come si può vedere abbiamo “generato” tutti gli interi tra 1 e 4

L’algoritmo procede come descritto per l’orologio. Ipotizziamo in questo caso p = 7 e g= 3

  • Alice sceglie un numero segreto a< 7 , ipotizziamo 4, e calcola la potenza modulo

  • Bob fa lo stesso, supponiamo b = 2 e calcola

  • Si scambiano i risultati e applicano il loro esponente segreto ad essi

NOTA: il fatto che b sia uguale al risultato ottenuto è assolutamente un caso

Come si vede entrambi ottengono lo stesso valore, 2, che possono utilizzare come chiave per scambiarsi messaggi

Perché funziona

Nell’algoritmo reale si utilizzano numeri estremamente più grandi, ma la difficoltà sta nel fatto che si ritiene essere difficile per un computer calcolare il logaritmo discreto di un numero in modulo.

Dove per logaritmo discreto si intende

Similmente al discorso del risalire al punto di partenza sull’orologio.

Conclusioni

In conclusione questa era una presentazione (molto) semplificata di quel che sta alla base dello scambio di chiavi Diffie-Hellman.
La teoria matematica alla base è estremamente affascinante (l’aritmetica modulare, i gruppi moltiplicativi, la scelta dei parametri, le curve ellittiche che si usano ultimamente e molto altro). Se siete curiosi potete contattarci al nostro gruppo telegram

history_edu Revisioni