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.

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]​

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:

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

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 ight),!}$ 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 ight),!}$ coeficientes ${displaystyle a_{1},cdots ,a_{k-1},!}$, y siendo ${displaystyle a_{0}=S,!}$, se construye el polinomio ${displaystyle fleft(x ight)=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,fleft(i ight) ight),!}$. 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.

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 fleft(x ight)=1234+166x+94x^{2},!}$

Calculamos seis puntos a partir del polinomio:

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

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

Para reconstruir el secreto bastará con tres puntos.

Considérese

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

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 =1942cdot left({frac {1}{6}}x^{2}-{frac {3}{2}}x+{frac {10}{3}} ight)+3402cdot left(-{frac {1}{2}}x^{2}+{frac {7}{2}}x-5 ight)+4414cdot left({frac {1}{3}}x^{2}-2x+{frac {8}{3}} ight),!}$

${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,!}$.