Algoritmo di Diffie-Hellman: panoramica e implementazione in C

L'algoritmo Diffie-Hellman viene utilizzato per stabilire un segreto condiviso tra due parti che può essere utilizzato per la comunicazione segreta per lo scambio di dati su una rete pubblica.

Spiegazione pittorica:

Il processo inizia facendo in modo che le due parti, Alice e Bob, si accordino su un colore di partenza arbitrario che non deve essere tenuto segreto (ma dovrebbe essere ogni volta diverso); in questo esempio, il colore è giallo. Ognuno di loro seleziona un colore segreto, rispettivamente rosso e acqua, che tiene per sé. La parte cruciale del processo è che Alice e Bob ora mescolano il loro colore segreto con il loro colore reciprocamente condiviso, risultando rispettivamente in miscele arancione e blu, quindi scambiano pubblicamente i due colori misti. Infine, ciascuno dei due mescola il colore ricevuto dal partner con il proprio colore privato. Il risultato è una miscela di colori finale (marrone) identica alla miscela di colori del partner.

Diffie-Hellman_Key_Exchange

Sarebbe impossibile per la spia Eve determinare il colore segreto comune.

Spiegazione crittografica:

L'algoritmo in sé è molto semplice. Supponiamo che Alice voglia stabilire un segreto condiviso con Bob. Ecco un esempio del protocollo con valori segreti in red.

Alice e Bob accettano di usare un numero primo p = 23 e base g = 5. (Questi due valori vengono scelti in questo modo per garantire che il segreto condiviso risultante possa assumere qualsiasi valore da 1 a p–1).
Alice sceglie un numero intero segreto un = 6, quindi invia Bob UN = g^un mod p (UN = 5⁶ mod 23 = 8)
Bob sceglie un numero intero segreto b = 15, quindi invia Alice B = g^b mod p (B = 5¹⁵ mod 23 = 19)
Alice calcola S = B^un mod p (S = 19⁶ mod 23 = 2)
Bob calcola S = UN^b mod p (S = 8¹⁵ mod 23 = 2)
Alice e Bob ora condividono un segreto (il numero 2).

Il numero che Alice ottiene al punto 4 è lo stesso che Bob ha ottenuto al punto 5

Bob calcola

A^b mod p = (g^a mod p)^b mod p = g^ab mod p

Alice calcola

B^a mod p = (g^b mod p)^a mod p = g^ba mod p

L'algoritmo Diffie-Hellman viene utilizzato principalmente per scambiare chiavi di crittografia da utilizzare in algoritmi di crittografia simmetrica come AES. Si prega di notare che le informazioni non vengono condivise durante lo scambio delle chiavi. Qui le due parti stanno creando una chiave insieme.

Implementazione:

C

#include <stdio.h>

// Funzione per calcolare `a^m mod n`

int compute(int a, int m, int n)

{

int r;

int y = 1;

while (m > 0)

{

r = m % 2;

// esposizione veloce

if (r == 1) {

y = (y*a) % n;

}

a = a*a % n;

m = m / 2;

}

return y;

}

// Programma C per dimostrare l'algoritmo Diffie-Hellman

int main()

{

int p = 23; // modulo

int g = 5; // base

int a, b; // `a` – La chiave segreta di Alice, `b` – La chiave segreta di Bob.

int A, B; // `A` – La chiave pubblica di Alice, `B` – La chiave pubblica di Bob

// scegli un numero intero segreto per la chiave privata di Alice (conosciuta solo da Alice)

a = 6; // oppure, usa `rand()`

// Calcola la chiave pubblica di Alice (Alice invierà `A` a Bob)

A = compute(g, a, p);

// scegli un numero intero segreto per la chiave privata di Bob (conosciuta solo da Bob)

b = 15; // oppure, usa `rand()`

// Calcola la chiave pubblica di Bob (Bob invierà `B` ad Alice)

B = compute(g, b, p);

// Alice e Bob scambiano le loro chiavi pubbliche `A` e `B` tra loro

// Trova la chiave segreta

int keyA = compute(B, a, p);

int keyB = compute(A, b, p);

printf("Alice's secret key is %d\nBob's secret key is %d", keyA, keyB);

return 0;

}

Scaricare Esegui codice

Risultato:

Alice’s secret key is 2
Bob’s secret key is 2

Questo è tutto sull'algoritmo Diffie-Hellman.

Riferimento: https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange