SOK: la crittografia incontra la magia

E se vi dicessi che è possibile scambiarsi un’informazione senza però incontrarsi o mandarsi alcun messaggio? Telepatia? Magia? No, Matematica!

Supponiamo che Alice (nome fittizio n.1) voglia inviare un messaggio segreto a Bob (nome fittizio n.2), e che ci sia una certa Eve (nome fittizio n.3) intenzionata ad intercettare e leggere il messaggio. Come può Alice proteggere il proprio messaggio? Con la crittografia (per una chiara e e semplice introduzione date un’occhiata al nostro articolo Introduzione alla Crittografia)!

Alice cifra il proprio messaggio utilizzando una chiave, Bob sarà poi in grado di decifrarlo mediante la stessa chiave. In altre parole, immaginate che Alice scriva il proprio messaggio in un foglio, lo chiuda a chiave dentro una cassaforte molto difficile da forzare, e la spedisca a Bob. Chiunque intercetti la cassaforte in viaggio non è in grado di forzarne l’apertura, e quindi di leggere il messaggio. Solo Bob, che possiede una copia della chiave di Alice, è in grado di aprirla e quindi di rivelarne il contenuto.

Quanto descritto sopra prende il nome tecnico di crittografia simmetrica, ossia quando il mittente ed il destinatario utilizzano la stessa chiave per cifrare e decifrare. Il problema che sicuramente vi state chiedendo è: come ci si scambia la chiave in maniera sicura?

Una prima soluzione potrebbe essere quella di mettere la chiave in un camion blindato, caricarlo di militari armati fino ai denti, ed affidare a loro il compito di portare la chiave a Bob. Questa soluzione ovviamente è molto costosa e neanche tanto sicura: basterebbe infatti corrompere uno dei militari oppure intercettare il camion per compromettere l’operazione. Per fortuna esiste uno strumento molto più economico, efficace e sicuro per scambiarsi una chiave crittografica: la matematica!

Al giorno d’oggi lo scambio di chiavi simmetriche avviene principalmente in due modi: utilizzando un algoritmo di crittografia asimmetrica, come per esempio RSA (ne avevamo già parlato qui: RSA alla corte di Re Artù/), oppure utilizzando un algoritmo di scambio chiavi, come per esempio EC-DH, giusto per citare il più utilizzato. Entrambe le soluzioni permettono ad Alice e Bob, attraverso lo scambio di alcuni messaggi insignificanti per chiunque li intercetti, di accordarsi in maniera sicura sull’utilizzo di una chiave. Questo è possibile solo perché vi sono dei problemi matematici molto difficili da risolvere alla base di codesti algoritmi. Qualora essi venissero risolti, la sicurezza degli algoritmi crittografici che si basano su di essi andrebbe a mancare.

In questo articolo andremo a parlare di un algoritmo di scambio chiavi che, quasi come fosse telepatia, permette ad Alice e Bob di scambiarsi una chiave senza però scambiarsi nessun messaggio! Prima però abbiamo bisogno di alcuni piccoli prerequisiti di matematica.

Curve ellittiche, logaritmi discreti e pairings

Avevamo già parlato di crittografia a curve ellittiche (Crittografia Ellittica), di seguito ricapitoliamo velocemente l’argomento.

Una curva ellittica è una cura algebrica rappresentata da un’equazione del tipo

\( y^2 = x^3 +ax +b \)

L’insieme dei punti di una curva ellittica congiuntamente ad un’operazione di somma “+” propriamente definita su di esso, formano quello che in matematica viene chiamato un gruppo. Non andremo ad approfondire questo seppur semplice concetto. E’ sufficiente per il momento sapere che, dati due punti \(A\) e \(B\) di una curva ellittica, la loro somma \(C = A+B\) è anch’esso un punto della curva.

Definiamo ora un’altra operazione: la moltiplicazione scalare. Dato un numero intero positivo \(n\) definiamo la moltiplicazione di un punto \(A\) della curva per \(n\) come la somma di \(A\) con se stesso per \(n\) volte, ossia

\(nA = A+A+…+A \quad n-volte\)

Definiamo adesso un concetto fondamentale per l’argomento. Supponiamo di conoscere due punti \(A\) e \(C\) di una curva ellittica tale che

\(C = nA\)

Il problema del logaritmo discreto consiste nel trovare \(n\), conoscendo solamente \(A\) e \(C\). In generale questo è un problema difficile da risolvere e proprio per questo è la base di numerosi protocolli crittografici. Vediamo adesso un’altro concetto matematico essenziale per i nostri scopi.

Il pairing è una funzione bilineare e (supponiamo per semplicità) simmetrica. In altre parole, è una funzione che prende due punti di una curva ellittica e ci restituisce un numero, e rispetta alcune interessanti proprietà. Ne elenchiamo due che ci interessano in particolare. Dati tre punti \(A\) e \(B\) di una curva ellittica, un numero intero n ed una funzione pairing \( e(.,.) \) si ha che

– \( e(A,B) = e(B,A) \)

– \( e(nA, B) = e(A,nB) \)

Detto ciò, finalmente abbiamo ora gli strumenti per introdurre il magico algoritmo di scambio chiavi SOK (dagli autori Sakari, Ohgishi e Kasahara) menzionato all’inizio di questo articolo.

SOK: scambio non interattivo di chiavi

Al fine di evidenziare alcune interessanti caratteristiche di questo protocollo, complichiamo leggermente le cose. Supponiamo che anzichè due partecipanti ve ne siano tre: Alice, Bob e Carl (in realtà può essere generalizzato per qualsiasi numero di partecipanti!).

Alice, Bob e Carl vogliono comunicare in maniera sicura tra di loro nel senso che, Alice non è in grado di leggere i messaggi che Bob e Carl si scambiano, Bob non è in grado di leggere i messaggi tra Alice e Carl ed, allo stesso modo, Carl non è in grado di leggere i messaggi tra Alice e Bob.

Data una curva ellittica (che sia adatta per questo genere di applicazioni), per ognuno dei tre partecipanti viene determinato un punto su di essa. Siano dunque \( A \), \( B \) e \( C \) i punti associati rispettivamente ad Alice, Bob e Carl. Tali punti sono determinati a partire dalle identità, rappresentate per esempio dagli indirizzi email, dei tre partecipanti. Quindi, per esempio, è sufficiente conoscere la mail di Alice alice\(@\)mail.com per determinare il punto \(A\) sulla curva associato a lei.

Una autorità di terze parti, chiamata spesso Trusted Authority (ossia autorità di fiducia) calcola \(s\), un numero random che manterrà segreto ed i punti sulla curva ellittica \(sA\), \(sB\) e \(sC\), che distribuirà attraverso un canale sicuro rispettivamente ad Alice, Bob e Carl.

Ricordiamo che, come spiegato sopra, \(sA\) sta a significare il punto sulla curva che si ottiene sommando il punto \(A\) con se stesso \(s\) volte.

Dunque, ricapitolando, siamo in una situazione in cui le identità dei comunicanti, rappresentate da tre punti sulla curva \(A\), \(B\) e \(C\), sono ricavabili semplicemente conoscendo il loro indirizzo email e quindi sono pubblicamente note. Inoltre Alice possiede un punto personale e segreto \(sA\), Bob possiede il punto \(sB\) e Carl il punto \(sC\). In altre parole, ogni coppia di partecipanti deve accordarsi nell’utilizzo di una chiave diversa rispetto a quella delle altre coppie.

Ora supponiamo che Alice e Bob vogliano scambiarsi una chiave privata per comunicare poi in maniera sicura. E’ in questo momento che si rivela la caratteristica sorprendente di questo protocollo: senza scambiarsi alcun messaggio, Alice e Bob sono in grado di scambiarsi una chiave. Infatti Alice calcola il seguente valore

\(e(sA,B)\)

e Bob calcola

\(e(sB,A).\)

Grazie alle proprietà della funzione pairing viste nella sezione precedente si ha che

\( e(sA,B) = e(sB,A) = k_{AB} \)

Dunque, senza comunicare, Alice e Bob si sono accordati nell’utilizzo di una chiave privata \(k_{AB}\). Carl, non è in grado di calcolare \(k_{AB}\) in quanto egli non è a conoscenza ne di \( sA \) e ne di \( sB \).

Alice e Bob sono dunque in grado di poter cifare messaggi con la chiave \(k_{AB}\) e scambiarseli in maniera sicura senza che nessuno che li intercetti sia in grado di decifrarli.

In questo modo, ogni coppia di comunicanti, senza effettivamente scambiarsi nessun messaggio, può accordarsi sull’utilizzo di una chiave privata. Bob e Carl useranno la chiave

\( e(sB,C) = e(sC,B) = k_{BC}, \)

mentre Alice e Carl useranno la chiave

\( e(sA,C) = e(sC,A) = k_{AC}. \)

Ogni chiave è diversa, il che significa che ogni coppia può avere una conversazione privata al sicuro da tutti gli altri.

Qualche osservazione

– Un vantaggio immediato di SOK è che, a differenza di tutti gli altri protocolli di scambio chiave, un malintenzionato che vuole scoprire una chiave privata tra due comunicanti, non ha messaggi da intercettare. Tuttavia, è importante che, quando la Trusted Authority distribuisce i punti della curva segreti ai partecipanti ( \(sA, sB, sC\) nell’esempio di sopra con Alice, Bob e Carl ), questi viaggino attraverso un canale sicuro, e quindi che non vengano intercettati a loro volta.

– La Trusted Authority, conoscendo il segreto \(s\), è in grado di calcolare le chiavi di tutti i partecipanti. In pratica questo può essere evitato avendo più di una Trusted Authority. Supponiamo per esempio che ce ne siano due: una in Cina, che chiameremo TA1, ed una negli Stati Uniti, che chiameremo TA2. Alice riceve da TA1 il segreto \(s_1A\) e da TA2 il segreto \(s_2A\), poi calcola il suo segreto completo semplicemente facendo la somma

\(s_1A+s_2A = (s_1+s_2)A =sA\)

La cosa avviene in maniera analoga per Bob e Carl. TA1 conosce solo parte del segreto e, non essendo a conoscenza di \(s_2\), non è in grado di ricavare il segreto completo. Inoltre, se per esempio il governo di un paese provasse a forzare le Trusted Authority a rivelare i segreti, questo sarebbe difficile in quanto le due TA risiedono in due diversi paesi, con diverse leggi sulla privacy.

– Supponiamo che Eve, un malintenzionato, riesca in qualche modo a scoprire la chiave privata tra Alice e Bob. Le conversazioni tra Bob e Carl e tra Alice e Carl non sono compromesse in quanto conoscere \(k_{AB}\) non da nessuna informazione riguardo la chiave privata di Bob e Carl \(k_{BC}\) e la chiave tra Alice e Carl \(k_{AC}\).

– La sicurezza di questo protocollo si basa sul fatto che il logaritmo discreto sia difficile da risolvere. Supponiamo infatti che Carl sia in grado di risolvere il logaritmo discreto su curve ellittiche. Egli è in grado quindi di ricavare, a partire da \(sC\) e \(C\), il numero segreto \(s\). Questo gli permette di calcolare il segreto di Alice \(sA\), e quindi la chiave privata tra Alice e Bob \(k_{AB} = e(sA,B)\).

– E’ giusto specificare che questa veloce introduzione al protocollo SOK presenta numerose semplificazioni che nel mondo della crittografia non possono essere ignorate. Al fine di trasmettere l’idea matematica che si cela dietro questo protocollo, ho deciso di omettere diversi dettagli.

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.