Shamir's Secret Sharing , formulado por Adi Shamir , es uno de los primeros esquemas de intercambio secreto en criptografía . Se basa en la interpolación polinomial sobre campos finitos .
Explicación de alto nivel
El uso compartido de secretos de Shamir (SSS) se utiliza para proteger un secreto de forma distribuida, la mayoría de las veces para proteger otras claves de cifrado. El secreto se divide en varias partes, llamadas acciones . Estas acciones se utilizan para reconstruir el secreto original.
Para desbloquear el secreto a través del intercambio secreto de Shamir, necesita un número mínimo de acciones. Esto se denomina umbral y se utiliza para indicar el número mínimo de recursos compartidos necesarios para desbloquear el secreto. Veamos un ejemplo:
Problema: la empresa XYZ necesita proteger el código de acceso de su bóveda. Podrían usar algo estándar, como AES, pero ¿qué pasa si el titular de la clave no está disponible o muere? ¿Qué pasa si la clave se ve comprometida a través de un pirata informático malintencionado o el titular de la clave se vuelve deshonesto y usa su poder sobre la bóveda en su beneficio?
Aquí es donde entra en juego SSS. Se puede utilizar para cifrar el código de acceso de la bóveda y generar una cierta cantidad de acciones, donde se puede asignar una cierta cantidad de acciones a cada ejecutivo dentro de la Compañía XYZ. Ahora, solo si juntan sus acciones pueden desbloquear la bóveda. El umbral se puede establecer adecuadamente para el número de ejecutivos, por lo que las personas autorizadas siempre pueden acceder a la bóveda. Si una acción o dos cayeran en las manos equivocadas, no podrían abrir el código de acceso a menos que los otros ejecutivos cooperaran.
Formulación matemática
Shamir's Secret Sharing es ideal y perfecto -esquema de umbral . En tal esquema, el objetivo es dividir un secreto(por ejemplo, la combinación de una caja fuerte ) en piezas de datos (conocido como acciones ) de tal manera que:
- Conocimiento de cualquier o más piezas hacen fácilmente computable. Es decir, el secreto completo se puede reconstruir a partir de cualquier combinación de piezas de datos.
- Conocimiento de cualquier o menos pedazos de hojas completamente indeterminado, en el sentido de que los posibles valores para parece tan probable como con el conocimiento de piezas. Es decir, el secreto no se puede reconstruir con menos de piezas.
Si , luego cada pieza del secreto original se requiere para reconstruir el secreto.
La idea esencial del esquema se basa en el teorema de interpolación de Lagrange , específicamente quepuntos es suficiente para determinar unívocamente un polinomio de grado menor o igual a. Por ejemplo, 2 puntos son suficientes para definir una línea , 3 puntos son suficientes para definir una parábola , 4 puntos para definir una curva cúbica, etc. Asumimos nuestro secreto se puede representar como un elemento de un campo finito . Elegimos al azar elementos, , de y construye el polinomio . Construyamos cualquier señala, por ejemplo, establecer para recuperar . A cada participante se le asigna un punto (una entrada de número entero distinto de cero al polinomio y la salida de número entero correspondiente). Dado cualquier subconjunto de de estos pares, podemos encontrar obtener utilizando interpolación , con una posible formulación como se muestra a continuación:
.
Uso
Ejemplo
El siguiente ejemplo ilustra la idea básica. Sin embargo, tenga en cuenta que los cálculos del ejemplo se realizan utilizando aritmética de enteros en lugar de utilizar aritmética de campos finitos . Por lo tanto, el siguiente ejemplo no proporciona un secreto perfecto y no es un verdadero ejemplo del plan de Shamir . Entonces, explicaremos este problema y mostraremos la forma correcta de implementarlo (usando aritmética de campos finitos).
Preparación
Supongamos que nuestro secreto es 1234 .
Deseamos dividir el secreto en 6 partes , donde cualquier subconjunto de 3 partes es suficiente para reconstruir el secreto. Al azar obtenemos números: 166 y 94.
- dónde es secreto
Nuestro polinomio para producir acciones secretas (puntos) es por lo tanto:
Construimos seis puntos del polinomio:
Damos a cada participante un único punto diferente (ambos y ). Porque usamos en vez de los puntos comienzan desde y no . Esto es necesario porque es el secreto.
Reconstrucción
Para reconstruir el secreto serán suficientes 3 puntos.
Considerar .
Calcularemos polinomios de base de Lagrange :
Por lo tanto
Recuerde que el secreto es el coeficiente libre, lo que significa que y hemos terminado.
Enfoque computacionalmente eficiente
Considerando que el objetivo de utilizar la interpolación polinomial es encontrar una constante en un polinomio fuente usar polinomios de Lagrange "tal cual" no es eficiente, ya que se calculan las constantes no utilizadas.
Un enfoque optimizado para usar polinomios de Lagrange para encontrar se define de la siguiente manera:
Problema
Aunque la versión simplificada del método demostrado anteriormente, que utiliza aritmética de enteros en lugar de aritmética de campos finitos, funciona bien, existe un problema de seguridad: Eve obtiene mucha información sobre con todo que ella encuentra.
Suponga que encuentra los 2 puntos y ella todavía no tiene puntos, por lo que en teoría no debería haber obtenido más información sobre . Pero ella combina la información de los 2 puntos con la información pública: y ella :
- llena el -fórmula con y el valor de
- llena (i) con los valores de 's y
- llena (i) con los valores de 's y
- hace (iii) - (ii): y reescribe esto como
- saber eso entonces ella comienza a reemplazar en (iv) con 0, 1, 2, 3, ... para encontrar todos los valores posibles para:
- reemplaza por (iv) en (ii):
- reemplaza en (vi) por los valores encontrados en (v) por lo que obtiene lo que la lleva a la información:
- Ahora solo tiene 150 números para adivinar en lugar de un número infinito de números naturales.
Solución
Geométricamente, este ataque aprovecha el hecho de que conocemos el orden del polinomio y, por lo tanto, conocemos las rutas que puede tomar entre puntos conocidos. Esto reduce los posibles valores de los puntos desconocidos, ya que debe estar en una curva suave.
Este problema se puede solucionar utilizando aritmética de campos finitos. Un campo de tamañose utiliza. El gráfico muestra una curva polinomial sobre un campo finito, en contraste con la curva suave habitual, parece muy desorganizada e inconexa.
En la práctica, esto es solo un pequeño cambio, solo significa que debemos elegir un primo que es mayor que el número de participantes y cada (incluso ) y tenemos que calcular los puntos como en vez de .
Dado que todo el que recibe un punto también debe conocer el valor de , puede considerarse de conocimiento público. Por lo tanto, se debe seleccionar un valor para eso no es demasiado bajo.
Para este ejemplo elegimos , por lo que nuestro polinomio se convierte en que da los puntos:
Esta vez Eve no gana ninguna información cuando encuentra un (hasta que ella tenga puntos).
Supongamos de nuevo que Eva encuentra y , esta vez la información pública es: así que ella:
- llena el -fórmula con y el valor de y :
- llena (i) con los valores de 's y
- llena (i) con los valores de 's y
- hace (iii) - (ii): y reescribe esto como
- saber eso entonces ella comienza a reemplazar en (iv) con 0, 1, 2, 3, ... para encontrar todos los valores posibles para:
Esta vez ella no puede parar porque podría ser cualquier número entero (incluso negativo si ) por lo que hay una cantidad infinita de valores posibles para . Ella sabe eso siempre disminuye en 3 así que si era divisible por ella podría concluir pero debido a que es primordial, ella no puede concluir ni siquiera eso y por eso no obtuvo ninguna información.
Ejemplo de Python
"" " La siguiente implementación de Python de Shamir's Secret Sharing se publica en el dominio público bajo los términos de CC0 y OWFa: https://creativecommons.org/publicdomain/zero/1.0/ http://www.openwebfoundation.org/legal / the-owf-1-0-acuerdos / owfa-1-0Consulte las últimas líneas para conocer su uso. Probado en Python 2 y 3. "" "de __future__ importar división de __future__ import print_functionimportar al azar de importación functools# 12th Mersenne Prime # (para esta aplicación queremos un número primo conocido lo más cercano posible a nuestro nivel de seguridad; por ejemplo, el nivel de seguridad deseado de 128 # bits - demasiado grande y todo el texto cifrado es demasiado grande; demasiado pequeño y # la seguridad es comprometido) _PRIME = 2 ** 127 - 1 # 13 Mersenne Prime es 2 ** 521 - 1_RINT = funciones . parcial ( aleatorio . SystemRandom () . randint , 0 )def _eval_at ( poli , x , prime ): "" "Evalúa polinomio (coeficiente de tupla) en x, que se utiliza para generar una piscina shamir en make_random_shares abajo. """ acum = 0 para Coef en invertido ( poli ): acum * = x acum + = coeficiente acum % = primer retorno acumdef make_random_shares ( secreto , mínimo , acciones , prime = _PRIME ): "" " Genera una piscina Shamir al azar para un secreto dado, vuelve comparten puntos. ''" Si mínima > acciones : aumento ValueError ( 'secreto piscina sería irrecuperable.' ) poli = [ secreto ] + [ _RINT ( principal - 1 ) para i en el rango ( mínimo - 1 )] puntos = [( i , _eval_at ( poli , i , principal )) para i en el rango ( 1 , comparte + 1 ) ] puntos de retorno def _extended_gcd ( a , b ): "" "La división en números enteros módulo p significa encontrar el inverso del denominador módulo p y luego multiplicar el numerador por este inverso (Nota: el inverso de A es B tal que A * B% p == 1) esto se puede calcular a través del algoritmo euclidiano extendido http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation "" " x = 0 last_x = 1 y = 1 last_y = 0 mientras que b ! = 0 : quot = a / / b a , b = b , a % b x , last_x = last_x - quot * x , x y , last_y = last_y - quot * y , y devuelve last_x , last_ydef _divmod ( num , den , p ): "" "Calcular num / den módulo prime p Para explicar lo que esto significa, el valor de retorno será tal que lo siguiente sea verdadero: den * _divmod (num, den, p)% p == num "" " inv , _ = _extended_gcd ( den , p ) return num * invdef _lagrange_interpolate ( x , x_s , y_s , p ): "" " Encuentra el valor y para la x dada, dados n (x, y) puntos; k puntos definirán un polinomio de hasta k-ésimo orden. " "" k = len ( x_s ) assert k == len ( set ( x_s )), "los puntos deben ser distintos" def PI ( vals ): # PI en mayúsculas - producto de las entradas acumuladas = 1 para v en vals : acumuladas * = v volver acum nums = [] # evitar inexacta división dens = [] para i en rango ( k ): otros = lista ( X_S ) cur = otros . pop ( i ) números . append ( PI ( x - o para o en otros )) dens . append ( PI ( cur - o para o en otros )) den = PI ( dens ) num = sum ([ _divmod ( nums [ i ] * den * y_s [ i ] % p , dens [ i ], p ) para i en rango ( k )]) return ( _divmod ( num , den , p ) + p ) % pdef recuperar_secreto ( acciones , prima = _PRIME ): "" " Recuperar el secreto de los puntos compartidos ( puntos x, y en el polinomio). " "" si len ( acciones ) < 2 : aumentar ValueError ( "necesita al menos dos acciones" ) x_s , y_s = zip ( * acciones ) return _lagrange_interpolate ( 0 , x_s , y_s , prime )def main (): "" "Función principal" "" secreto = 1234 acciones = make_random_shares ( secreto , mínimo = 3 , acciones = 6 ) print ( 'Secreto:' , secreto ) print ( 'Acciones:' ) si acciones : para compartir en acciones : imprimir ( '' , compartir ) print ( 'Secreto recuperado de un subconjunto mínimo de recursos compartidos:' , recovery_secret ( participaciones [: 3 ])) print ( 'Secreto recuperado de un subconjunto mínimo de recursos compartidos:' , recovery_secret ( participaciones [ - 3 :]))if __name__ == '__main__' : main ()
Propiedades
Algunas de las propiedades útiles de Shamir's esquema de umbral son:
- Seguro : seguridad teórica de la información .
- Mínimo : El tamaño de cada pieza no excede el tamaño de los datos originales.
- Extensible : cuando se mantiene fijo, las piezas se pueden agregar o eliminar dinámicamente sin afectar a las otras piezas.
- Dinámico : la seguridad se puede mejorar fácilmente sin cambiar el secreto, pero cambiando el polinomio ocasionalmente (manteniendo el mismo término libre) y creando nuevas acciones para los participantes.
- Flexible : En organizaciones donde la jerarquía es importante, podemos suministrar a cada participante diferente número de piezas según su importancia dentro de la organización. Por ejemplo, el presidente puede abrir la caja fuerte solo, mientras que se requieren 3 secretarias juntas para abrirla.
Un problema conocido en el esquema de intercambio secreto de Shamir es la verificación de la corrección de los recursos compartidos recuperados durante el proceso de reconstrucción, que se conoce como intercambio secreto verificable . El intercambio secreto verificable tiene como objetivo verificar que los accionistas sean honestos y no presenten acciones falsas.
Ver también
- Compartir secreto
- Polinomio de Lagrange
- Uso compartido de secretos homomórficos : un protocolo de votación descentralizado simplista.
- Regla de dos hombres
- Contraseña parcial
Referencias
- Shamir, Adi (1979), "Cómo compartir un secreto", Comunicaciones de la ACM , 22 (11): 612–613, doi : 10.1145 / 359168.359176 , S2CID 16321225.
- Liu, CL (1968), Introducción a las matemáticas combinatorias , Nueva York: McGraw-Hill.
- Dawson, E .; Donovan, D. (1994), "La amplitud del esquema de intercambio de secretos de Shamir", Computers & Security , 13 : 69–78, doi : 10.1016 / 0167-4048 (94) 90097-3.
- Knuth, DE (1997), El arte de la programación informática , II: Algoritmos seminuméricos (3ª ed.), Addison-Wesley, p. 505.
- Benzekki, K. (2017), "A Verifiable Secret Sharing Approach for Secure MultiCloud Storage", In Ubiquitous Networking , Lecture Notes in Computer Science, Casablanca: Springer, 10542 : 225-234, doi : 10.1007 / 978-3-319- 68179-5_20 , ISBN 978-3-319-68178-8.
enlaces externos
- Compartir el secreto de Shamir en la biblioteca Crypto ++
- Esquema de intercambio secreto de Shamir (ssss) : una implementación de GNU GPL
- sharedsecret - implementación en Go
- s4 - la herramienta de intercambio de secretos de shamir en línea que utiliza el algoritmo de intercambio de secretos de hashi corps shamir