Scambio di chiavi Diffie-Hellman

Da Wikipedia, l'enciclopedia libera.

Questa voce riguardante un argomento di informatica non è ancora stata tradotta completamente dalla lingua inglese. Se sei in grado, potresti terminarla tu.
Il testo da tradurre potrebbe essere nascosto: clicca su modifica per visualizzarlo. Non usare programmi di traduzione automatica.

Lo Scambio di chiavi Diffie-Hellman (Diffie-Hellman key exchange) è un protocollo crittografico che consente a due entità di stabilire una chiave condivisa e segreta utilizzando un canale di comunicazione insicuro (pubblico) senza la necessità che le due parti si siano scambiate informazioni o si siano incontrate in precedenza. La chiave ottenuta mediante questo protocollo può essere successivamente impiegata per criptare le comunicazioni successive tramite uno schema di crittografia simmetrica.

Sebbene l'algoritmo in sé sia anonimo (cioè non autenticato) è alla base di numerosi protocolli autenticati ed è usato anche in alcune modalità di funzionamento del protocollo TLS.

[modifica] Storia del protocollo

Lo schema del protocollo Diffie-Hellman fu pubblicato per la prima volta nel 1976 nell'ambito di una collaborazione tra Whitfield Diffie e Martin Hellman e fu il primo metodo pratico per due interlocutori di accordarsi su un segreto condiviso (la chiave) utilizzando un canale di comunicazione non protetto. Il lavoro di Ralph Merkle sulla distribuzione delle chiavi pubbliche (i Puzzle di Merkle) ed il suggerimento da parte di John Gill di utilizzare il problema dei logaritmi discreti come base per la creazione di funzioni unidirezionali servirono da linee guida per lo sviluppo dell'algoritmo. Alla medesima idea erano giunti tuttavia anche alcuni ricercatori (Malcolm J. Williamson, James H. Ellis, Clifford C. Cocks) del GCHQ alcuni anni prima (1973) delle pubblicazioni di Diffie-Hellman e di quelle, risalenti al 1977, ad opera di Ron Rivest, Adi Shamir e Leonard Adleman del MIT che descrivono il noto algoritmo di crittografia asimmetrica conosciuto come RSA, ma i documenti riguardanti l'invenzione, all'epoca giudicata tecnologicamente impraticabile, sono stati segretati fino al 1997.

Nel 2002, Hellman scrisse:

(EN)

« The system...has since become known as 'Diffie-Hellman key exchange'. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called 'Diffie-Hellman-Merkle key exchange' if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle's equal contribution to the invention of public key cryptography »

(IT)

« Il sistema[..]è sempre stato conosciuto con il nome di 'Diffie-Hellman key exchange'. Sebbene questo sistema fu descritto per la prima volta in una pubbicazione firmata da me e Diffie, esso è un sistema a distribuzione di chiave pubblica, un concetto sviluppato da Merkle, e quindi, se dovessimo associare dei nomi all'algoritmo, questo dovrebbe chiamarsi 'Diffie-Hellman-Merkle key exchange'. Spero che questo piccolo intervento possa aiutare l'intento di dare il giusto riconoscimento al contributo di Merkle all'invenzione della crittografia a chiave pubblica. »

(Martin Hellman, [1] )

Il brevetto U.S. Patent 4,200,770, ora scaduto, descrive l'algoritmo e riporta Hellman, Diffie e Merkle come inventori.

[modifica] Descrizione

Diffie-Hellman key exchange

Nell'implementazione originale (e più semplice) del protocollo si considera inizialmente un numero g, generatore del gruppo moltiplicativo degli interi modulo p, dove p è un numero primo. Uno dei due interlocutori, ad esempio Alice, sceglie un numero casuale a e calcola il valore A = g ^amod p (dove mod indica l'operazione modulo, ovvero il resto della divisione intera) e lo invia attraverso il canale pubblico a Bob (l'altro interlocutore), assieme ai valori g e p. Bob da parte sua sceglie un numero casuale b, calcola B = g ^b mod p e lo invia ad Alice. A questo punto Alice calcola K_A = B ^a mod p, mentre Bob calcola K_B = A ^b mod p. ... A questo punto i due interlocutori sono entrambi in possesso della chiave segreta e possono cominciare ad usarla per crittare le comunicazioni successive.

L'implementazione più semplice del protocollo, quella originale, usa il gruppo moltiplicativo degli interi modulo p, dove p è un numero primo e g è generatore mod p.

Un' esempio del funzionamento del protocollo è il seguente:

Alice
Sec		Calc
	p, g
a
		g^a mod p
	…
	(g^b mod p)^a mod p

$\rightarrow$

$\leftarrow$

Bob
Calc		Sec
	p, g
		b
	…
g^b mod p
	(g^a mod p)^b mod p

Alice e Bob si accordano di usare un numero primi p=23 e la base g=5.
Alice sceglie in numero segreto a=6 e manda a Bob (g^a mod p)
- 5⁶ mod 23 = 8
Bob sceglie il intero segreto b=15 e manda ad Alice (g^b mod p)
- 5¹⁵ mod 23 = 19.
Alice calcola (g^b mod p)^a mod p
- 19⁶ mod 23 = 2.
Bob calcola (g^a mod p)^b mod p
- 8¹⁵ mod 23 = 2.

Alice e Bob trovano lo stesso risultato perché g^ab e g^ba sono uguali. Si noti come solo a, b e g^ab = g^ba sono segreti. Tutti gli altri numeri sono mandati in chiaro, ossia pubblici. Una volta che Alice e Bob calcolano la chiave segreta, essa può esser usata come chiave di criptazione, conosciuta solo a loro, per mandare messaggi tramite il canale di comunicazione in chiaro.

Chiaramente i valori di a, b e p devono esser molto maggiori di quelli usati nell'esempio siccome è facile provare tutti i possibili valori di g^ab mod 23 ( vi sono in ogni caso al massimo 22 valori anche se a e b sono grandi). Se p è un primo di almeno 300 cifre e a e b sono almeno di 100 cifre, il miglior algoritmo conosciuto oggigiorno non può trovare a dati g, p e g^a mod p usando tutta la potenza computazionale della terra. Questo è il problema del logaritmo discreto. Si noti come g non debba esser grande, infatti nella pratica è spesso 2 o 5.