Blog divulgativo sulla matematica applicata

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.

alice-et-bob1

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

curva

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.

Untitled Diagram (1)

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 .

Untitled Diagram (3)

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.

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

Similar posts

3 commenti

  1. maggio 10, 2018    

    Articolo molto interessante, posso chiederti se c'è qualche libro dove approfondire l'argomento?

  2. maggio 11, 2018    

    Grazie 10^3 Alessandro, vedrò di leggermi attentamente il primo articolo, il pairing era proprio l'argomento che volevo approfondire, e cerco se quel libro è consultabile su Safari Books Online.

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Partecipa all’indagine “Io e la Matematica”

Clicca sull'immagine sottostante per rispondere al breve e anonimo questionario:

MIA15 - Nomination

Conviditi con i tuoi contatti questo link!

Canale Telegram dedicato alla Matematica

Iscriviti sul nostro canale Telegram

MIA15 - Nomination

Rimani aggiornato sui più interessanti articoli di divulgazione matematica e non solo!

Iscriviti alla nostra newsletter

Resta aggiornato sui nostri post e su quello che facciamo.

Seguici su Twitter

Tag Cloud

Grazie per il sostegno ai #MIA2015

Grazie a tutti per averci votato ai "Macchia Nera Awards 2015" nella categoria "Miglior Sito Tecnico-Divulgativo".

Siamo arrivati in finale grazie al vostro sostegno!

MIA15 - Nomination