Shamir’s Secret Sharing

Questo è il mio primo post sulla crittografia, richiede una conoscenza di matematica della terza media, se non vi interessa fermatevi qui. Tranquilli, domani tornerò ai soliti post…

Il Professor Adi Shamir

Adi Shamir è un israeliano di 56 anni e, non solo secondo la mia opinione, è il più grande crittografo della storia dell’uomo. Per capirci, ogni volta che comprate qualcosa su internet dovete ringraziare lui se i dati della vostra carta di credito non possono essere intercettati.

Tra i vari problemi che ha risolto, ha risolto anche il problema legato allo secret sharing, vale a dire il problema di distribuire un segreto tra un numero n di persone in modo tale che il segreto possa essere rivelato solo se si mettono daccordo un numero di persone k, dove ovviamente k < n. Esemplifico:

Il presidente di una azienda protegge con una password i documenti relativi ai piani strategici dell’azienda, ma nel caso fosse impossibilitato ad aprire questi documenti (perchè all’estero per lavoro, perchè malato, ecc.) vuole fare in modo che questi documenti possano essere letti se almeno 6 dei 10 dirigenti più importanti dell’azienda lo ritenessero necessario. Quindi deve distribuire il segreto tra i 10 dirigenti ma ce ne devono essere 6 per poter accedere ai documenti.

Shamir ha brillantemente risolto questo problema. Per un punto passano infinite rette, per due punti passa una sola retta e infinite parabole. Per trovare l’equazione di una parabola bisogna conoscere tre punti per i quali passa la parabola. La retta è un polinomio di primo grado, la parabola è un polinomio di secondo grado. Questo discorso è vero in generale, per definire un polinomio di grado m occorrono m+1 punti. Shamir ha usato questo semplicissimo concetto.

Usando la notazione di sopra, sarà sufficiente generare un polinomio a coefficienti casuali di grado k, imporre il termine noto uguale al segreto da distribuire, generare n punti e distribuire le coordinate di un punto ad ogni partecipante. Così facendo se k partecipanti si rivelano i propri punti possono usare una delle tecniche come l’interpolazione di Lagrange per trovare l’equazione del polinomio e quindi anche il termine noto, che è il segreto da ricostruire. Invece k-1 persone non sono in grado di ottenere nessuna informazione circa il segreto. Non solo… questo sistema permette anche di poter dare più poteri ad un gruppo di persone. Nell’esempio di prima si può volere che il presidente dell’azienda dia la possibilità all’amministratore delegato di poter aprire i documenti se con lui ci sono solo 2 dirigenti, basterebbe dargli 4 punti ricavati dal polinomio invece che 1, in modo che sommati ai due punti dei due dirigenti si raggiunga il numero k cioè 6.

E’ un metodo flessibile e funzionale, io l’ho usato per le mie ultime volontà perchè non voglio che siano pubbliche prima della mia morte. Quindi ho distribuito la password del documento che contiene le mie volontà ad amici, usando questo sistema. Se uno di loro fosse curioso e volesse leggerle prima del mio decesso dovrebbe convincerne altri 6 per poterlo fare. E non credo di avere amici così bastardi…

Per dettagli sullo Shamir’s Secret Sharing c’è wikipedia o un implementazione opensource per linux e per windows.