Esquema de Shamir

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Adi Shamir, desarrollador del sistema de compartición de secretos que lleva su nombre.

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]

Definición matemática[editar]

Formalmente, nuestro objetivo es dividir un conjunto de datos D\,\! (por ejemplo, una clave) en n\,\! partes D_1,\cdots,D_n\,\! de manera que:

  1. El conocimiento de k\,\! o más D_i\,\! partes hace que D\,\! sea fácilmente computable.[3]
  2. El conocimiento de k-1\,\! o menos D_i\,\! partes hace que 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 \left(k,n\right)\,\!.[2] Si k=n\,\! se requiere la concurrencia de todos los participantes para reconstruir el secreto.

Sistema de compartición de secretos de Shamir[editar]

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 n+1\,\! puntos para definir un polinomio de grado n\,\!.

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

Eligiendo al azar \left(k-1\right)\,\! coeficientes a_1,\cdots,a_{k-1}\,\!, y siendo a_0=S\,\!, se construye el polinomio f\left(x\right)=a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_{k-1}x^{k-1}\,\!. Calculamos cualesquiera n\,\! puntos a partir del mismo, por ejemplo determinamos que i=1,\cdots,n\,\! de lo que se deriva \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 k\,\! entre estos pares, podemos calcular los coeficientes del polinomio mediante interpolación y luego despejar a_0\,\!, que es el secreto.

Ejemplo de uso[editar]

Preparación[editar]

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

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

(a_1=166;a_2=94)\,\!

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

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

Calculamos seis puntos a partir del polinomio:

\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 x\,\! y f\left(x\right)\,\!).

Reconstrucción[editar]

Para reconstruir el secreto bastará con tres puntos.

Considérese

\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:

\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}\,\!

\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\,\!

\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,

f(x)=\sum_{j=0}^2 y_j\cdot\ell_j(x)\,\!

=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)\,\!

=1234+166x+94x^2\,\!

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

Referencias[editar]

  1. What is Shamir's Secret Sharing Scheme? en X5 Networks
  2. a b Morillo, Paz (mayo-agosto de 2006). «Las matemáticas en la criptología». Encuentros multidisciplinares. Universidad Politécnica de Catalunya (23). http://www.encuentros-multidisciplinares.org/Revistan%C2%BA23/Paz%20Morillo%20Bosch.pdf. 
  3. Carracedo Gallardo, Justo (2004). «Servicios de anonimato para la Sociedad de la Información». Seguridad en redes telemáticas. Editorial McGraw-Hill. ISBN 84-481-4157-1. , p. 470