Esquema de Shamir

Esquema de Shamir

Esquema de Shamir

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]

Contenido

Definición matemática

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

La idea esencial de la combinación de umbral de Shamir es que dos puntos son suficientes para definir una línea, 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

Preparación

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

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-1\frac{1}{2}x+3\frac{1}{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+3\frac{1}{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+2\frac{2}{3}\,\!

Por lo tanto,

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

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

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

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

Referencias

  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. n.º 23.
  3. ↑ Carracedo Gallardo, Justo (2004). «Servicios de anonimato para la Sociedad de la Información», Seguridad en redes telemáticas. Editorial McGraw-Hill. ISBN 8448141571., p. 470
  • Shamir, Adi (noviembre de 1979). «How to share a secret» Communications of the ACM. Vol. 22. n.º 11. ISSN 0001-0782., pp. 612-613
Obtenido de "Esquema de Shamir"

Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Adi Shamir — Adi Shamir, 2009. Nombre …   Wikipedia Español

  • Interpolación polinómica — En análisis numérico, la interpolación polinómica es una técnica de interpolación de un conjunto de datos o de una función por un polinomio. Es decir, dado cierto número de puntos obtenidos por muestreo o a partir de un experimento se pretende… …   Wikipedia Español

  • RSA — En criptografía, RSA (Rivest, Shamir y Adleman) es un sistema criptográfico de clave pública desarrollado en 1977. Es el primer y más utilizado algoritmo de este tipo y es válido tanto para cifrar como para firmar digitalmente. La seguridad de… …   Wikipedia Español

  • Uriel Feige — Residencia  Israel Nacionalidad Israelí Campo Ciencias de la computación Criptogr …   Wikipedia Español

  • Data Encryption Standard — (DES) es un algoritmo de cifrado, es decir, un método para cifrar información, escogido por FIPS en los Estados Unidos en 1976, y cuyo uso se ha propagado ampliamente por todo el mundo. El algoritmo fue controvertido al principio, con algunos… …   Wikipedia Español

  • A5/1 — es un algoritmo cifrador de flujo usado para proporcionar privacidad en la comunicación al aire libre en el estándar GSM, es decir, el algoritmo que cifra la conversación entre 2 terminales GSM cuando el mensaje viaja por el aire. Inicialmente… …   Wikipedia Español

  • Advanced Encryption Standard — (AES), también conocido como Rijndael (pronunciado Rain Doll en inglés), es un esquema de cifrado por bloques adoptado como un estándar de cifrado por el gobierno de los Estados Unidos. El AES fue anunciado por el Instituto Nacional de Estándares …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”