Esquema de Shamir

El sistema de compartición de secretos de Shamir es un algoritmo criptográfico. Es una forma de compartición de secretos donde un secreto se divide en partes y se da a cada participante una sola: todas o parte de ellas son necesarias para reconstruir el secreto.

Adi Shamir, desarrollador del sistema de compartición de secretos que lleva su nombre.

El algoritmo basa su funcionamiento en una propiedad de los polinomios interpoladores^[1] y fue desarrollado por el criptógrafo israelí Adi Shamir, que lo presentó en 1979.^[2]

Definición matemática

Formalmente, nuestro objetivo es dividir un conjunto de datos ${\displaystyle D\,\!}$ (por ejemplo, una clave) en ${\displaystyle n\,\!}$ partes ${\displaystyle D_{1},\cdots ,D_{n}\,\!}$ de manera que:

1. El conocimiento de ${\displaystyle k\,\!}$ o más ${\displaystyle D_{i}\,\!}$ partes hace que ${\displaystyle D\,\!}$ sea fácilmente computable.^[3]
2. El conocimiento de ${\displaystyle k-1\,\!}$ o menos ${\displaystyle D_{i}\,\!}$ partes hace que ${\displaystyle D\,\!}$ esté indeterminado, en el sentido de que todos sus valores posibles tienen la misma probabilidad de ser verdaderos.

Esta combinación se denomina combinación o esquema de umbral ${\displaystyle \left(k,n\right)\,\!}$.^[2] Si ${\displaystyle k=n\,\!}$ se requiere la concurrencia de todos los participantes para reconstruir el secreto.

Sistema de compartición de secretos de Shamir

Se pueden dibujar infinitos polinomios de grado 2 que pasen por 2 puntos. Se necesitan 3 puntos para definir un polinomio único de grado 2. Esta imagen sólo tiene fines ilustrativos - El esquema de Shamir utiliza polinómios en un conjunto finito, no representable en un plano bidimensional.

La idea esencial de la combinación de umbral de Shamir es que dos puntos son suficientes para definir una línea recta, tres puntos lo son para definir una parábola, cuatro para definir una curva cúbica y así sucesivamente. Es decir, son necesarios ${\displaystyle n+1\,\!}$ puntos para definir un polinomio de grado ${\displaystyle n\,\!}$.

Supongamos que queremos trabajar con un umbral de ${\displaystyle \left(k,n\right)\,\!}$ para compartir un secreto ${\displaystyle S\,\!}$ (cualquier número, sin pérdida de generalidad) siendo ${\displaystyle k<n\,\!}$. La elección de los valores de ${\displaystyle k\,\!}$ y ${\displaystyle n\,\!}$ determina la fortaleza del sistema.

Eligiendo al azar ${\displaystyle \left(k-1\right)\,\!}$ coeficientes ${\displaystyle a_{1},\cdots ,a_{k-1}\,\!}$, y siendo ${\displaystyle a_{0}=S\,\!}$, se construye el polinomio ${\displaystyle f\left(x\right)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{k-1}x^{k-1}\,\!}$. Calculamos cualesquiera ${\displaystyle n\,\!}$ puntos a partir del mismo, por ejemplo determinamos que ${\displaystyle i=1,\cdots ,n\,\!}$ de lo que se deriva ${\displaystyle \left(i,f\left(i\right)\right)\,\!}$. A todo participante en el secreto se le da un punto (un par de valores, el de entrada y el de salida para el polinomio)

Dado cualquier subconjunto de ${\displaystyle k\,\!}$ entre estos pares, podemos calcular los coeficientes del polinomio mediante interpolación y luego despejar ${\displaystyle a_{0}\,\!}$, que es el secreto.

Ejemplo de uso

Preparación

Supongamos que el secreto es el número de una tarjeta de crédito: 1234 ${\displaystyle (S=1234)\,\!}$.

Queremos dividir el secreto en seis partes ${\displaystyle (n=6)\,\!}$, de forma que cualquier subconjunto ${\displaystyle (k=3)\,\!}$ sea suficiente para reconstruir el secreto. Al azar obtenemos ${\displaystyle k-1}$ números: por ejemplo, 166 y 94.

${\displaystyle (a_{1}=166;a_{2}=94)\,\!}$

El polinomio con el que operaremos será por lo tanto:

${\displaystyle f\left(x\right)=1234+166x+94x^{2}\,\!}$

Calculamos seis puntos a partir del polinomio:

${\displaystyle \left(1,1494\right);\left(2,1942\right);\left(3,2578\right);\left(4,3402\right);\left(5,4414\right);\left(6,5614\right)\,\!}$

Damos a cada partícipe un único punto, que comprende el valor ${\displaystyle x\,\!}$ y ${\displaystyle f\left(x\right)\,\!}$).

Reconstrucción

Para reconstruir el secreto bastará con tres puntos.

Considérese

${\displaystyle \left(x_{0},y_{0}\right)=\left(2,1942\right);\left(x_{1},y_{1}\right)=\left(4,3402\right);\left(x_{2},y_{2}\right)=\left(5,4414\right)\,\!}$.

Usamos la interpolación polinómica de Lagrange:

${\displaystyle \ell _{0}={\frac {x-x_{1}}{x_{0}-x_{1}}}\cdot {\frac {x-x_{2}}{x_{0}-x_{2}}}={\frac {x-4}{2-4}}\cdot {\frac {x-5}{2-5}}={\frac {1}{6}}x^{2}-{\frac {3}{2}}x+{\frac {10}{3}}\,\!}$

${\displaystyle \ell _{1}={\frac {x-x_{0}}{x_{1}-x_{0}}}\cdot {\frac {x-x_{2}}{x_{1}-x_{2}}}={\frac {x-2}{4-2}}\cdot {\frac {x-5}{4-5}}=-{\frac {1}{2}}x^{2}+{\frac {7}{2}}x-5\,\!}$

${\displaystyle \ell _{2}={\frac {x-x_{0}}{x_{2}-x_{0}}}\cdot {\frac {x-x_{1}}{x_{2}-x_{1}}}={\frac {x-2}{5-2}}\cdot {\frac {x-4}{5-4}}={\frac {1}{3}}x^{2}-2x+{\frac {8}{3}}\,\!}$

Por lo tanto,

${\displaystyle f(x)=\sum _{j=0}^{2}y_{j}\cdot \ell _{j}(x)\,\!}$

${\displaystyle =1942\cdot \left({\frac {1}{6}}x^{2}-{\frac {3}{2}}x+{\frac {10}{3}}\right)+3402\cdot \left(-{\frac {1}{2}}x^{2}+{\frac {7}{2}}x-5\right)+4414\cdot \left({\frac {1}{3}}x^{2}-2x+{\frac {8}{3}}\right)\,\!}$

${\displaystyle =1234+166x+94x^{2}\,\!}$

Teniendo en cuenta que el secreto es el coeficiente de ${\displaystyle x^{0}\,\!}$, el secreto original es ${\displaystyle S=1234\,\!}$.