Condividi I Tuoi Segreti Con Shamir

Lo scorso articolo, avevo parlato di due belle cosette: aritmetica modulare e campi di Galois. E li avevo introdotti in previsione di questo giorno. Sí, perché oggi parlerò di un algoritmo di crittografia. Algoritmo non solo veramente figo, ma che ha anche un valore affettivo in quanto conosciuto tempo fa discutendo con un collega che saluto (ciao Dylan) e che ora non c'é piú. Tranquilli non é morto ha "solo", con mio sommo malessere, cambiato azienda. L'algoritmo di cui discuterò è lo Shamir's Secret Sharing (abbreviato SSS, fortuna che ce ne sono 3 altrimenti vallo a spiegare ai lettori), ideato da Adi Shamir che è un guru della crittografia (a lui si deve la S nell'algoritmo RSA). Prima di iniziare vi consiglio fortemente, se non lo avete ancora fatto, di leggere qui, l'articolo sui campi finiti.

In Aggiunta

L'aritmetica modulare e i campi di Galois li ho spiegati, quindi sono con l'anima in pace su questo fronte. Manca peró un ultimo strumento per poter spiegare l'algoritmo SSS e dato che sono un perfezionista, lungi dal volervi privare di tutto quello di cui avete bisogno. Quello che ci serve ora è l'interpolazione lineare di Lagrange. Due punti su questo:

1. Portano il suo nome ma non ha ideato lui il metodo.
2. E' un grandissimo matematico ITALIANO e non francese.

Riprendiamo. Só che non è il vostro primo problema al mattino, ma cosa fareste se voleste determinare un polinomio di grado \(n\) che passa su \(n+1\) punti dati:

Il problema sembra di chissà quale complessità, ma in realtà non è nulla di astruso. Andiamo a vedere un primo metodo risolutivo.

L'Aggiunta "Naive"

Non voglio partire subito a raffica quindi prima riscaldiamoci se no ci si fà male, e andiamo a vedere un metodo semplice. Lo scopo del problema è quello di trovare un polinomio di grado \(n\), no? Per cui iniziamo prendendone uno generico:

Formula 1. Generico Polinomio

Dove \(x\) e \(y\) sono generiche coordinate, e \(a_i\) è un generico coefficiente. Cosa vogliamo da questo polinomio!? Che passi per \(n+1\) punti. Iniziamo dal primo punto:

• \((x_0, \, y_0)\): Da questo punto sappiamo i valori di \(x\) e \(y\) che sono appunto \(x_0\) e \(y_0\). Andiamoli a mettere nella nostra formula.

  $$ y_0 = a_0 + a_1x_0 + a_2x_0^2 + \dots + a_nx_0^n $$

  Quello che vogliamo fare è calcolare i coefficienti \(a_i\), e ci basta questa formula a risolvere il problema? No. Perché le \(a_i\) da cercare sono \(n+1\) e noi qui abbiamo solo una formula. Se c'è una cosa che alle medie abbiamo imparato risolvendo i sistemi, è che se abbiamo \(m\) incognite, abbiamo bisogno di \(m\) equazioni per scoprirle tutte. Noi abbiamo \(n+1\) \(a\), ma abbiamo anche \(n+1\) punti no? Quindi possiamo scrivere una seconda uguaglianza...

• \((x_1, \, y_1)\): Da questo punto sappiamo i valori di \(x\) e \(y\) che sono appunto \(x_1\) e \(y_1\). Andiamoli a mettere nella nostra formula.

  $$ y_1 = a_0 + a_1x_1 + a_2x_1^2 + \dots + a_nx_1^n $$

  Direi che l'antifona è abbastanza chiara. Quindi skippiamo fino all'ultimo punto.

• \(...\)

• \((x_n, \, y_n)\): Da questo punto sappiamo i valori di \(x\) e \(y\) che sono appunto \(x_n\) e \(y_n\). Al solito, andiamoli a mettere nella nostra formula.

  $$ y_n = a_0 + a_1x_n + a_2x_n^2 + \dots + a_nx_n^n $$

  Arrivati a questo punto è chiaro che abbiamo \(n+1\) equazioni e quindi siano contenti, dato che ora possiamo calcolare le \(n+1\) incognite \(a\).

Quello che abbiamo ottenuto è un sistema di equazioni, cioè quell'insieme di equazioni le quali una volta sostituiti i valori incognita, rispettano tutte le condizioni di uguaglianza date. Scriviamolo in una forma piú matematica:

a questo punto due sono le strade, o lo facciamo a manella, o ci facciamo furbi e scriviamo il sistema lineare in forma matriciale:

dove:

• \(V\) è una matrice chiamata matrice di Vandermonde, ed è definita cosí:

  $$ V = \begin{bmatrix} 1 & x_0 & x_0^2 & \dots & x_0^n \\ 1 & x_1 & x_1^2 & \dots & x_1^n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^n \end{bmatrix} $$

  Vi ricordo che noi abbiamo tutti gli elementi di questa matrice, sono le coordinate \(x\) (e le loro potenze) per i quali vogliamo far passare il polinomio.

• \(\vec{a}\) è il vettore delle incognite, cioè dei coefficienti del polinomio che stiamo cercando.

  $$ \vec{a} = \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_n \end{bmatrix} $$

• \(\vec{y}\) è il vettore dei termini noti, anche questi li conosciamo in quanto dalle coordinate \(y\) per le quali vogliamo far passare il polinomio.

  $$ \vec{y} = \begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_n \end{bmatrix} $$

Riscrivendo per intero il sistema abbiamo:

Formula 2. Forma Matriciale Dell'Interpolazione

Bene a questo punto per risolvere il problema ci sono due modi.

1. Quello che fa incazzare la mia professoressa di calcolo numerico e analisi complessa, e che prevede di invertire la \(V\):

   $$ \vec{a} = V^{-1} \cdot \vec{b} $$

2. Un metodo piú intelligente che puó essere il metodo di Gauss, la fattorizzazione LU e chi piú ne ha piú ne metta.

Ora noi non vedremo nessuno dei due, perché vorrebbe dire spiegarvi cosa é un determinante, cosa é l'inversa di una matrice e cosa succede quando non é invertibile (per farla brevissima o non esistono soluzioni oppure ce ne sono infinite), perché non conviene invertire una matrice e fare invece la decomposizione. Quindi poi dovrei spiegare pure le decomposizioni. Ciao, troppa roba. Consideriamo un esempio piccolo da risolvere a mano giusto per farvi capire cosa otteniamo.

Esempio

Supponiamo di volere calcolare un polinomio di grado \(2\) passante per i punti:

Il polinomio avrà forma:

Andiamo a scrivere il nostro sistema di tre equazioni, semplicemente sostituendo i punti come mostrato in precedenza:

da cui:

Abbiamo trovato tutti i coefficienti \(a_0, \, a_1, \, a_2\), possiamo quindi scrivere il nostro polinomio che sarà:

Vediamone l'andamento grafico:

Figura 1. Plot Del Polinomio \(y = 1 + x^2\)

Guardate attentamente il grafico per vedere dove sono poste le croci rosse. Passa esattamente per i punti richiesti.

L'Aggiunta Lagrange

Ora che sapete cosa si sta cercando di fare, buttate via tutto il metodo precedente. E' sicuramente stato utile perché abbiamo capito, in maniera abbastanza intuitiva, quale era il senso. Ma dato c'é un altro modo per farlo, e dato che morite dalla voglia di conoscerlo, chi sono io per privarvene? E' arrivato il momento dell'interpolazione di Lagrange, per cui iniziamo definendo il nostro polinomio \(y\). Questa volta lo definiamo tramite sommatoria, in questo modo:

Formula 3. Interpolazione Di Lagrange

dove il generico \(L_i(x)\) é una produttoria cosí definita:

Andando a sviluppare per esteso abbiamo che un generico polinomio ha forma:

Anche qui, sembra chissà che cosa complessa, ma in realtà è molto semplice. Vediamo con un esempio.

Esempio

Consideriamo lo stesso esempio di prima, e cerchiamo il polinomio passante per i punti:

Calcoliamo le \(L_i\) richieste:

• \(L_0\) usa il punto \((x_0, \, y_0) = (0, \, 1)\):

  $$ \begin{aligned} L_0(x) &= \frac{x - x_1}{x_0 - x_1} \cdot \frac{x - x_2}{x_0 - x_2} \\ &= \frac{x - 1}{0 - 1} \cdot \frac{x - 2}{0 - 2} \\ &= \frac{x - 1}{-1} \cdot \frac{x - 2}{-2} \\[6pt] &= \frac{(x - 1)(x - 2)}{2} \end{aligned} $$

• \(L_1\) usa il punto \((x_1, \, y_1) = (1, \, 2)\):

  $$ \begin{aligned} L_1(x) &= \frac{x - x_0}{x_1 - x_0} \cdot \frac{x - x_2}{x_1 - x_2} \\ &= \frac{x - 0}{1 - 0} \cdot \frac{x - 2}{1 - 2} \\ &= x \cdot \frac{x - 2}{-1} \\[6pt] &= -x(x - 2) \end{aligned} $$

• \(L_2\) usa il punto \((x_2, \, y_2) = (2, \, 5)\):

  $$ \begin{aligned} L_2(x) &= \frac{x - x_0}{x_2 - x_0} \cdot \frac{x - x_1}{x_2 - x_1}\\ &= \frac{x - 0}{2 - 0} \cdot \frac{x - 1}{2 - 1}\\ &= \frac{x}{2}(x - 1)\\[6pt] &= \frac{x(x - 1)}{2} \end{aligned} $$

Da notare che non stiamo ancora usando le \(y\). Quelle intervengono precisamente qui:

Sviluppando quest'ultima cosa otteniamo:

e guarda caso, è lo stesso risultato ottenuto in precedenza. Per concludere questo paragrafo, perché preferire questo metodo? Non tanto per questioni di performance ma perché, per l'uso che ne faremo, si presta meglio a risolvere il problema.

E' Tempo Di Condivisione

Ora che abbiamo tutti gli strumenti necessari, possiamo finalmente arrivare al cuore dell’algoritmo di oggi. L’idea alla base di SSS è tanto semplice quanto elegante: prendere un segreto, nasconderlo nel termine noto di un polinomio scelto ad hoc e distribuire ai partecipanti dei punti appartenenti a quel polinomio. Presi singolarmente, quei punti non rivelano nulla ma messi insieme in numero sufficiente permettono di ricostruire esattamente il polinomio originale tramite l’interpolazione di Lagrange, e quindi recuperare il termine noto ossia il segreto. In altre parole, la matematica diventa il meccanismo di fiducia distribuita: ogni partecipante possiede un frammento dell’informazione e solo se c'è un gruppo abbastanza numeroso, si è in grado di svelare il segreto.

I passi sono semplici. Si inizia scegliendo due parametri:

1. Il numero di partecipanti \(s\) rappresentante il numero di punti del polinomio che vogliamo generare e distribuire.
2. La soglia minima \(t\), rappresentante il numero di partecipanti necessario per ricostruire il segreto. Questo valore determina che utilizzeremo un polinomio di grado \(t-1\).

Il legame tra queste due variabili è che deve essere rispettato il vincolo:

cioè il numero di punti distribuiti deve essere (ovviamente), maggiore del numero di partecipanti necessari a ricostruire il messaggio, e non puó essere maggiore della cardinalità del campo finito da cui si prendono gli elementi (come mostreró piú avanti) escludendo l'elemento nullo. Quindi supponendo di avere \(s=3\) e \(t=2\) stiamo dicendo che creiamo e distribuiamo \(s=3\) punti, e per ricostruire il messaggio è necessario che almeno \(t=2\) partecipanti siano d'accordo. Il contrario anche intuitivamente non ha senso, come si fa a creare e distribuire \(s=2\) ma avere l'accordo di \(t=3\) persone? Oppure, come facciamo a distribuire piú elementi di quelli che si hanno a disposizione nel campo? Ovviamente non si puó, non è mica il debito pubblico italiano. Questa è matematica.

Una volta stabiliti i valori di \(s\) e \(t\) costruiamo il nostro polinomio:

Formula 4. Polinomio Di Condivisione

Questo polinomio è molto simile a quello definito qui ma ci sono due piccole differenze:

• \(S\) è il segreto da nascondere nel polinomio
• gli \(a_i\) sono coefficienti presi dal campo di Galois

Il polinomio così costruito non deve mai essere rivelato per intero, ogni partecipante riceve soltanto una coppia \((x_i, \, f(x_i))\), cioè la valutazione del polinomio in un punto. Preso singolarmente, questo valore non contiene alcuna informazione sul segreto, né sugli altri coefficienti del polinomio. La ricostruzione del segreto avviene unicamente quando almeno \(t\) partecipanti mettono insieme i loro punti. Per ricostruire la \(S\), basta valutare il polinomio \(f\) nel punto \(0\), calcolando appunto \(f(0)\). Infatti, proprio per via di come è costruito il polinomio \(f(x)\), ponendo \(x=0\) tutti i termini (ad eccezione di \(S\)) si annullano. Quindi quello che sappiamo é:

• Il segreto é nel punto \(0\) del polinomio \(f(x)\).
• Non abbiamo accesso al polinomio \(f(x)\).

In questo contesto interviene l'interpolazione di Lagrange. Ci permette di estrapolare \(S\) (cioè il polinomio valutato in \(0\)), senza conoscere il polinomio stesso, ma solo i punti che gli appartengono. In particolare, quello che si fa è calcolare:

Formula 5. Formule Di Decifratura

Con \(I\) insieme degli shares (e dopo vedremo cosa sono). Arrivati fin qui è tutto, e se ci pensate non è chissà che cosa complicata. Ma il bello della crittografia è questo. Usare strumenti semplici, ma terribilmente potenti.

Ma ciancio alle bande, vediamo un esempio.

Esempio Di Cifratura

Potrei utilizzare un campo di Galois semplice come \(\mathbb{F}_{11}\). Essendo composto da soli numeri, dato che \(p\) è un primo ed ha potenza \(1\), fare operazioni di somma e moltiplicazione è semplice. Fin troppo. Per cui perché non complicarsi la vita? Perché non usare un campo \(\mathbb{F}_{2^3}\) dove i coefficienti sono polinomi? E sopratutto, che ci sto a fare io altrimenti? Andiamo a vedere...

Supponiamo di avere un dealer, cioè un distributore di chiavi, che usa il campo \(\mathbb{F}_{2^3}\) con polinomio irriducibile \(\alpha^3 + \alpha^2 + 1\). Con questo campo possiamo nascondere al più 3 bit di informazione. Se avete qualcosa di più ingombrante da nascondere, o usate campi più grandi o dividete l'informazione in batch. Io vi spiego solo come fare. In ogni caso, come sappiamo da qui, gli elementi del campo in questione sono:

Supponiamo inoltre che per chissà quale motivo il dealer voglia nascondere il numero di blasfemie che genero nel giro di 1 minuto, ossia 6. Sapendo che la \(S\) e i coefficienti \(a_i\) devono appartenere al campo, la prima cosa che il dealer fà è convertire \(6\) in un valore del campo (da notare che ho scelto il numero 6 perché pienamente rappresentabile con 3 bit). Per cui abbiamo:

Se siete curiosi di sapere come ho fatto, leggete qui.

Ora il dealer deve scegliere quante chiavi (o share, che abbiamo nominato in precedenza), creare. Supponiamo che ne voglia generare \(s=4\), e che scelga soglia minima per ricostruire l'informazione \(t=3\) (da notare che il campo \(\mathbb{F}_{2^3}\) ha \(8\) elementi e noi ne distribuiamo \(4\) quindi tutto lecito). Il polinomio di condivisione avrà la forma:

dove \(S\) è l'informazione da nascondere, ossia

e \(a_1\) e \(a_2\) sono coefficienti del campo scelti casualmente. Supponiamo:

e quindi il polinomio è:

dove:

• \(\alpha\) è il simbolo usato per rappresentare gli elementi del campo \(\mathbb{F}_{2^3}\).
• \(x\) è la variabile del polinomio di condivisione su cui verrà effettuata la valutazione.

Ora che abbiamo fissato il polinomio di condivisione, il dealer deve generare i quattro share. Quello che fà quindi, è scegliere quattro distinte \(x\) e valutare la funzione \(f(x)\) nei punti scelti. Vi ricordate che in questa sezione venivano imposti dei punti nel piano nei quali far passare il polinomio? Qui è la stessa identica cosa, ma il dominio è il campo di Galois ad esclusione del punto \(0\) (perchè è quello che nasconde l'informazione). Dato che sono pigro come un bradipo, e per chi mi conosce sà che non sto esagerando dato che spesso non provvedo ai miei bisogni primari (ma poi vado in palestra, guarda tu la vita...), scegliamo dei punti che non ci rendono i calcoli (troppo) complicati:

e iniziamo a creare gli shares da distribuire:

• Share 1:

• Share 2:

• Share 3:

• Share 4:

Nello sviluppo dei polinomi, si è applicata la proprietà di ciclicità delle potenze. Se volete saperne di piú, vi basta guardare qui. Torniamo a noi. A questo punto il dealer ha finito. Ha scelto quello che doveva scegliere e ha generato quello che doveva generare. Conserva gelosamente il polinomio di condivisione, e distribuisce gli shares (ogni persona riceve uno ed un solo share) e il campo utilizzato. Supponiamo che il dealer distribuisce gli shares a Pico, Pluto, Paperino e Topolino asserendo che l'informazione top-secret è il codice per accedere ai files di Duckstein (e chissà perché la password é il mio numero di blasfemie al minuto) e scoprire la verità sui rapporti tra il signor T. (presidente di Paperopoli) e il signor B. (ogni riferimento a fatti e/o persone è puramente casuale). Il dealer dice loro che nessuno, da solo, puó accedere ai files. Serve che almeno \(3\) persone siano d'accordo.

Esempio Di Decifratura

Dato che non si vuole minare la democrazia, l'informazione non viene utilizzata, in fondo manca poco alla fine del mandato. Poi peró, T. organizza l'assalto al municipio di Paperopoli per rimanere in carica e si sá, chi di spada ferisce di spada perisce. I quattro iniziano a discutere tra di loro e Pluto, che é un cane, é un fervente sostenitore del movimento 'Return Paperopoli to Greatness' e non vuole rivelare nulla. Per fortuna Pico Paperino e Topolino, che non vivono dell'ignoranza altrui, sono d'accordo nello svelare i segreti che apriranno gli occhi sugli abitanti di Paperopoli e che, si spera, cacceranno T. a pedate. Per cui procedono cosí. Supponiamo che in tre abbiano gli shares \((x_1, \, f(x_1))\), \((x_2, \, f(x_2))\) e \((x_4, \, f(x_4))\). Inoltre conoscono il campo finito utilizzato:

Dalle formule di decifatura, sappiamo che dobbiamo calcolare

e quindi, dati gli shares:

• \(L_1(0)\):

  $$ \begin{aligned} L_1(0) &= \frac{0 - x_2}{x_1 - x_2} \cdot \frac{0 - x_4}{x_1 - x_4}\\ &= \frac{0 - \alpha}{1 - \alpha} \cdot \frac{0 - (1 + \alpha)}{1 - (1 + \alpha)}\\[6pt] &= 1 \end{aligned} $$

• \(L_2(0)\):

  $$ \begin{aligned} L_2(0) &= \frac{0 - x_1}{x_2 - x_1} \cdot \frac{0 - x_4}{x_2 - x_4}\\ &= \frac{0 - 1}{\alpha - 1} \cdot \frac{0 - (1 + \alpha)}{\alpha - (1 + \alpha)}\\[6pt] &= 1 \end{aligned} $$

• \(L_4(0)\):

  $$ \begin{aligned} L_4(0) &= \frac{0 - x_1}{x_4 - x_1} \cdot \frac{0 - x_2}{x_4 - x_2}\\ &= \frac{0 - 1}{(1 + \alpha) - 1} \cdot \frac{0 - \alpha}{(1 + \alpha) - \alpha}\\[6pt] &= 1 \end{aligned} $$

Vorrei far notare che i valori delle \(L_i\) sono sempre \(1\) perché ho preso un campo estremamente piccolo. In ogni caso ora possiamo calcolare la nostra \(S\). Infatti, date le \(y_i\) che altro non sono che le \(f(x_i)\) degli shares, applichiamo ancora la formuletta di decifratura:

Quindi il segreto è \(S=\alpha^2 + \alpha\) e sapendo di essere nel campo \(\mathbb{F}_{2^3} \pmod{\alpha^3 + \alpha^2 + 1}\), ne prendiamo il valore intero utilizzando l'ormai abusata tabellina:

Quindi ora Pico, Paperino e Topolino insieme, e solo insieme, non solo sanno il mio rate bestemmie per minuto ma possono accedere ai files di Duckstein e riportare Paperopoli al raziocinio.

Provare per credere, utilizzate un qualsiasi sottoinsieme di 3 elementi e vedrete che funziona. Non uno di piú (nel senso che non è necessario uno in piú) non uno di meno (nel senso che ve ne basta solo uno in meno, che non riuscite a ricostruire correttamente il segreto). Questo grazie alla proprietà dell'interpolazione che dice che per definire, in maniera univoca, un polinomio di grado \(k\) sono necessari \(k + 1\) punti distinti sulle ascisse.

Considerazioni

L'esempio che tra satira politica, matematica e licenza poetica, ho portato, è molto semplice. Per risalire al secret basterebbe una banalissima forza bruta dato che ogni generico \(L_i\) è all'interno del campo \(\mathbb{F}_{2^3}\) contenente 8 elementi. Dato che per impostazione sono necessari tre shares, abbiamo che il numero di tentativi da fare è pari a tutte le possibili triplette differenti in un insieme di 8 elementi. Usando la formula del coefficiente binomiale abbiamo che:

abbiamo 56 possibili triplette. Fattibilissimo. Ma guardiamo il caso generico:

Da qui possiamo procedere in due modi. O usiamo l'approssimazione di Stirling o andiamo di semplificazioni brutali. Dato che siamo tutti stanchi procediamo per quest'ultima via.

Il fattoriale per definizione è:

applicando ricorsivamente la definizione, possiamo scrivere che:

da cui

Usandolo nella formula iniziale abbiamo

Raggruppando per \(n\) è facile ottenere:

Se consideriamo \(n \to \infty\) quello che rimane è \(\frac{n^k}{k!}\) e quindi, essendo \(k\) trascurabile se lo consideriamo finito, abbiamo che la complessità computazionale del testare tutti i possibili valori è:

dove \(n\) è la cardinalità del campo finito e \(k\) è la soglia minima per ricostruire l'informazione, e questa è una complessità mostruosa. Ora considerate che i campi usati sono del tipo \(\mathbb{F}_{2^{256}}\) che contengono \(\sim 10^{77}\) elementi. Secondo stime scientifiche il numero di atomi dell'universo è dell'ordine di \(\sim 10^{80}\).

Conclusioni

Premettendo che mi sono piaciuti tutti gli articoli che ho scritto (altrimenti semplicemente non ne avrei scritto ovvio), ma tra tutti questo è stato il piú divertente da scrivere. Sia per il valore affettivo della sua scoperta, sia perché dai, é una gran ficata. Mi é piaciuto talmente tanto che ne ho scritto anche un repo. Potete trovarlo qui. Mi perdonerete se non ho implementato raw i campi di Galois, so tanto belli e tanto cari ma implementare da zero la riduzione a polinomio, ciaone proprio. Per fortuna che c'è una libreria (galois, tu guarda la fantasia) che ha implementato molto del lavoro sporco. In ogni caso voglio concludere l'articolo invitandovi a leggere l'articolo originale di Shamir perché é molto interessante. Detto questo vado a condividere (a pezzetti ora che posso) i miei segreti con qualcuno.

Alla Prossima.