Condivisione dei segreti di Shamir: matematica dei polinomi

Shamir's Secret Sharing (1979) codifica il segreto come intercetta sull'asse y (f(0)) di un polinomio casuale di grado (k-1) su un campo finito. Qualsiasi k punti determina univocamente il polinomio (interpolazione di Lagrange); meno di k punti non rivelano nulla.

Per condividere il segreto S con soglia k tra n parti: scegliere un primo p > S e n. Scegliere coefficienti casuali a_1, ..., a_{k-1}. Definire f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p). La parte i riceve la quota (i, f(i)).

Secret S=7, p=17, k=2 (polinomio lineare). Scegliere a_1=3. f(x)=7+3x mod 17. Quote: (1,10), (2,13), (3,16). Due punti qualsiasi determinano la retta. f(0)=7. Un solo punto: infinite rette possibili, nessuna informazione su S.

Dati k punti (x_1,y_1),...,(x_k,y_k), ricostruire f(0) usando Lagrange: S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p. Tutte le operazioni sono modulari. Nessun calcolo in virgola mobile: ricostruzione esatta sul campo finito.

from functools import reduce def lagrange(shares, p): xs = [s[0] for s in shares] ys = [s[1] for s in shares] result = 0 for i, (xi, yi) in enumerate(shares): num = reduce(lambda a,b: a*b%p, [(-xj)%p for j,xj in enumerate(xs) if j!=i], 1) den = reduce(lambda a,b: a*b%p, [(xi-xj)%p for j,xj in enumerate(xs) if j!=i], 1) result = (result + yi * num * pow(den, p-2, p)) % p return result

Per k-1 condivisioni, per ogni possibile valore del segreto S esiste esattamente un polinomio di grado k-1 che passa per quei k-1 punti. Pertanto, conoscendo k-1 condivisioni, ogni valore di S nell'intervallo [0, p-1] è equiprobabile: non viene rivelata alcuna informazione.

p deve essere maggiore del segreto e di n. Una scelta comune è p = 2^127-1 (primo di Mersenne) per segreti di 128 bit. In questo modo tutte le condivisioni possono essere rappresentate in 128 bit e i calcoli sono efficienti. In alternativa, si può usare p = 2^521-1 per segreti di 512 bit.

La SSS di base non garantisce l'integrità delle condivisioni: un partecipante malevolo può fornire una condivisione falsa, causando una ricostruzione errata del segreto. Feldman VSS (condivisione verificabile del segreto) pubblica i commitment g^{a_i} mod p, consentendo di verificare le condivisioni senza rivelare il polinomio.

Le condivisioni possono essere aggiornate periodicamente: si genera un nuovo polinomio con lo stesso segreto S e si distribuiscono nuove condivisioni; quelle vecchie non sono più valide. Un attaccante che compromette un partecipante dopo l'aggiornamento ottiene una vecchia condivisione inutile. Questa tecnica viene usata nei sistemi di gestione delle chiavi a lunga durata.

ssss (riga di comando Linux), python-secret-sharing, hashicorp/vault utilizza la SSS per il meccanismo di sigillatura, mentre il portafoglio hardware Trezor usa la SSS per il backup del seed del portafoglio (SLIP-39). Tutte operano su campi primi di grandi dimensioni.

La SSS richiede un dealer fidato che generi e distribuisca le condivisioni (il dealer conosce il segreto). In assenza di un dealer è necessaria la DKG (generazione distribuita delle chiavi). La ricostruzione rivela il segreto a chiunque disponga di k condivisioni; questo problema viene eliminato dalla MPC e dalle firme a soglia.

Nella condivisione del segreto (3,5) di Shamir, qual è il numero minimo di condivisioni necessarie per ricostruire il segreto?

La SSS di Shamir codifica i segreti come intercette sull'asse y dei polinomi. L'interpolazione di Lagrange recupera il segreto da k condivisioni. Offre una sicurezza perfetta e informazionalmente teorica con meno di k condivisioni. Prossimo argomento: condivisione visiva e additiva del segreto.