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.
![](http://up.wiki.x.io/wikipedia/commons/thumb/0/06/Adi_Shamir_2009_crop.jpg/230px-Adi_Shamir_2009_crop.jpg)
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
editarFormalmente, nuestro objetivo es dividir un conjunto de datos (por ejemplo, una clave) en partes de manera que:
- El conocimiento de o más partes hace que sea fácilmente computable.[3]
- El conocimiento de o menos partes hace que 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 .[2] Si se requiere la concurrencia de todos los participantes para reconstruir el secreto.
Sistema de compartición de secretos de Shamir
editarLa 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 puntos para definir un polinomio de grado .
Supongamos que queremos trabajar con un umbral de para compartir un secreto (cualquier número, sin pérdida de generalidad) siendo . La elección de los valores de y determina la fortaleza del sistema.
Eligiendo al azar coeficientes , y siendo , se construye el polinomio . Calculamos cualesquiera puntos a partir del mismo, por ejemplo determinamos que de lo que se deriva . 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 entre estos pares, podemos calcular los coeficientes del polinomio mediante interpolación y luego despejar , que es el secreto.
Ejemplo de uso
editarPreparación
editarSupongamos que el secreto es el número de una tarjeta de crédito: 1234 .
Queremos dividir el secreto en seis partes , de forma que cualquier subconjunto sea suficiente para reconstruir el secreto. Al azar obtenemos números: por ejemplo, 166 y 94.
El polinomio con el que operaremos será por lo tanto:
Calculamos seis puntos a partir del polinomio:
Damos a cada partícipe un único punto, que comprende el valor y ).
Reconstrucción
editarPara reconstruir el secreto bastará con tres puntos.
Considérese
.
Usamos la interpolación polinómica de Lagrange:
Por lo tanto,
Teniendo en cuenta que el secreto es el coeficiente de , el secreto original es .
Referencias
editar- ↑ What is Shamir's Secret Sharing Scheme? en X5 Networks
- ↑ a b Morillo, Paz (mayo-agosto de 2006). «Las matemáticas en la criptología». Encuentros multidisciplinares. Universidad Politécnica de Catalunya (23).
- ↑ 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
- Shamir, Adi (noviembre de 1979). «How to share a secret». Communications of the ACM 22 (11). ISSN 0001-0782., pp. 612-613