Secret Sharing de Shamir: matemáticas polinómicas

La compartición de secretos de Shamir (1979) codifica el secreto como la intersección con el eje y (f(0)) de un polinomio aleatorio de grado (k-1) sobre un campo finito. Cualquier k puntos determina unívocamente el polinomio (interpolación de Lagrange); menos de k puntos no revelan nada.

Para compartir el secreto S con un umbral k entre n partes: elija un primo p > S y n. Escoja coeficientes aleatorios a_1, ..., a_{k-1}. Defina f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p). La parte i recibe la participación (i, f(i)).

Secreto S=7, p=17, k=2 (polinomio lineal). Elija a_1=3. f(x)=7+3x mod 17. Partes: (1,10), (2,13), (3,16). Cualquier dos puntos determina la recta. f(0)=7. Un solo punto: infinitas rectas posibles, cero información sobre S.

Dado k puntos (x_1,y_1),...,(x_k,y_k), reconstruya f(0) mediante Lagrange: S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p. Toda la aritmética es modular. No se utilizan números de coma flotante: la reconstrucción exacta se realiza sobre el 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

Para k-1 partes, existe exactamente un polinomio de grado k-1 que pasa por esos k-1 puntos para cada valor posible del secreto S. Por lo tanto, al conocer k-1 partes, todos los valores de S en [0, p-1] son igual de probables: no se revela ninguna información.

p debe ser mayor que el secreto y que n. Una elección habitual es p = 2^127-1 (primo de Mersenne) para secretos de 128 bits. Esto garantiza que todas las partes quepan en 128 bits y que la aritmética sea eficiente. Como alternativa, puede utilizarse p=2^521-1 para secretos de 512 bits.

El SSS básico no ofrece integridad de las partes: un participante malicioso puede enviar una parte falsa y provocar una reconstrucción incorrecta del secreto. Feldman VSS (Verifiable Secret Sharing) publica compromisos g^{a_i} mod p, lo que permite verificar las partes sin revelar el polinomio.

Las partes pueden renovarse periódicamente: se genera un polinomio nuevo con el mismo secreto S y se distribuyen nuevas partes; las partes antiguas dejan de ser válidas. Un atacante que comprometa a un participante después de la renovación obtiene una parte antigua que ya no sirve. Este mecanismo se utiliza en sistemas de gestión de claves de larga duración.

ssss (línea de comandos de Linux), python-secret-sharing, hashicorp/vault utiliza SSS para su mecanismo de sellado y la billetera de hardware Trezor utiliza SSS para la copia de seguridad de la semilla de la billetera (SLIP-39). Todas operan sobre cuerpos finitos de gran tamaño.

SSS requiere un distribuidor de confianza que genere y distribuya las partes; el distribuidor conoce el secreto. Un escenario sin distribuidor requiere DKG (Distributed Key Generation). La reconstrucción revela el secreto a quien posea k partes; MPC y las firmas de umbral eliminan este problema.

El SSS de Shamir codifica los secretos como interceptos con el eje y de un polinomio. La interpolación de Lagrange recupera el secreto a partir de k partes. Ofrece seguridad perfecta e incondicional para menos de k partes. A continuación: compartición visual y aditiva de secretos.