Considere el escenario cuando sea necesario garantizar la seguridad de la bóveda del banco. Se considera absolutamente inexpugnable sin una clave, que se le entrega el primer día de trabajo. Su objetivo es guardar la clave de forma segura.

Supongamos que decide mantener la llave con usted todo el tiempo, proporcionando acceso a la tienda según sea necesario. Pero rápidamente se dará cuenta de que tal solución en la práctica no se escala normalmente, porque cada vez que necesita su presencia física para abrir el repositorio. ¿Qué pasa con las vacaciones que te prometieron? Además, la pregunta es aún más aterradora: ¿qué pasa si pierde una sola clave?

Con la idea de las vacaciones, decidió hacer una copia de la clave y confiarla a otro empleado. Sin embargo, usted comprende que esto tampoco es ideal. Al duplicar el número de claves, también duplicó las posibilidades de robo de claves.

Desesperado, destruyes el duplicado y decides dividir la clave original por la mitad. Ahora, usted piensa, dos personas de confianza con fragmentos de clave deben estar físicamente presentes para recoger la clave y abrir la tienda. Esto significa que el ladrón necesita robar dos fragmentos, lo cual es el doble de difícil que robar una llave. Sin embargo, pronto se dará cuenta de que este esquema no es mucho mejor que una sola clave, porque si alguien pierde la mitad de la clave, la clave completa no se puede restaurar.

El problema se puede resolver con una serie de llaves y cerraduras adicionales, pero con este enfoque necesitará rápidamente muchas llaves y cerraduras. Decide que, en un esquema ideal, necesita dividir la clave para que la seguridad no dependa completamente de una persona. También concluye que debe haber un cierto umbral para la cantidad de fragmentos, de modo que si se pierde un fragmento (o si una persona se va de vacaciones), la clave completa permanece funcional.

Como compartir un secreto

Este tipo de esquema de gestión clave fue pensado por Adi Shamir en 1979 cuando publicó su trabajo Cómo compartir un secreto . El artículo explica brevemente los llamados $$$(k, n)$esquema de umbral para dividir efectivamente un valor secreto (por ejemplo, una clave criptográfica) en $$$n$partes Entonces, cuando y solo cuando al menos $$$k$de $$$n$partes ensambladas, puede restaurar fácilmente el secreto $$$S$.

Desde el punto de vista de la seguridad, una propiedad importante de este esquema es que el atacante no debe saber absolutamente nada si no tiene al menos $$$k$partes Incluso disponibilidad $$$k - 1$las partes no deben dar ninguna información. Llamamos a esta propiedad seguridad semántica .

Interpolación polinómica

Esquema de umbral de Shamir $$$(k, n)$construido alrededor del concepto de interpolación polinómica . Si no está familiarizado con este concepto, en realidad es bastante simple. En general, si alguna vez dibujó puntos en un gráfico y luego los conectó con líneas o curvas, ¡ya lo usó!


Se puede dibujar un número ilimitado de polinomios de grado 2 a través de dos puntos. Para elegir el único, necesita un tercer punto. Ilustración: Wikipedia

Considere un polinomio con grado uno, $$$f (x) = x + 2$. Si desea trazar esta función en un gráfico, ¿cuántos puntos necesita? Bueno, sabemos que esta es una función lineal que forma una línea y, por lo tanto, se necesitan al menos dos puntos. A continuación, considere una función polinómica con grado dos, $$$f (x) = x ^ 2 + 2x + 1$. Esta es una función cuadrática, por lo que se requieren al menos tres puntos para construir un gráfico. ¿Qué pasa con un polinomio con grado tres? Al menos cuatro puntos. Y así sucesivamente.

Lo realmente genial de esta propiedad es que, dado el grado de la función polinómica, y al menos $$$grado + 1$puntos, podemos derivar puntos adicionales para esta función polinómica. La extrapolación de estos puntos adicionales se llama interpolación polinómica .

Haciendo un secreto

Es posible que ya se haya dado cuenta de que el esquema inteligente de Shamir entra en juego aquí. Supongamos nuestro secreto $$$S$Es eso $$$42$. Podemos girar $$$S$hasta un punto en la tabla $$$(0.42)$y llegar a una función polinómica con grado $$$k-1$que satisface este punto Recordemos que $$$k$será nuestro umbral para los fragmentos requeridos, por lo que si establecemos el umbral en tres fragmentos, debemos elegir una función polinómica con grado dos.

Nuestro polinomio tomará la forma $$$f (x) = a_0 + a_1x + a_2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1}$donde $$$a_0 = S$y $$$a_1, ..., a_ {k-1}$- enteros positivos seleccionados al azar. Solo estamos construyendo un polinomio con un grado $$$k-1$donde es el coeficiente libre $$$a_0$Es nuestro secreto $$$S$y cada uno de los siguientes $$$k-1$Los miembros tienen un coeficiente positivo seleccionado al azar. Si vuelve al ejemplo original y asume que $$$S = 42, k = 3, a_1, ..., a_ {k-1} = [3,5]$entonces obtenemos la función $$$f (x) = 42 + 3x + 5x ^ 2$.

En esta etapa, podemos generar fragmentos conectando $$$n$enteros únicos en $$$f (x) = 42 + 3x + 5x ^ 2$donde $$$x \ neq 0$(porque este es nuestro secreto). En este ejemplo, queremos distribuir cuatro fragmentos con un umbral de tres, por lo que generamos puntos al azar $$$(18, 1716), (27, 3768), (31, 4940), (35, 6272)$y envíe un punto a cada una de las cuatro personas de confianza, encargados de llaves. También le decimos a la gente que $$$k = 3$, ya que se considera información pública y es necesaria para la recuperación $$$S$.

Recuperación secreta

Ya hemos discutido el concepto de interpolación polinómica y el hecho de que subyace en el esquema del umbral de Shamir $$$(k, n)$. Cuando tres de los cuatro representantes quieren recuperarse $$$S$solo necesitan interpolar $$$f (0)$con sus propios puntos únicos. Para hacer esto, pueden determinar sus puntos $$$(x_1, y_1), ..., (x_k, y_k) = (18, 1716), (27, 3768), (31, 4940)$y calcule el polinomio de interpolación de Lagrange utilizando la siguiente fórmula. Si la programación es más comprensible para usted que las matemáticas, entonces pi es esencialmente una declaración for que multiplica todos los resultados, y sigma es una declaración for que suma todo.

$$

$$P (x) = \ sum_ {j = 1} ^ {k} p_j (x)$$

$$

$$P_j (x) = y_j \ prod _ {\ scriptstyle m = 1 \ atop \ scriptstyle m \ neq j} ^ {k} \ frac {x-x_m} {x_j-x_m}$$

En $$$k = 3$podemos resolver esto de la siguiente manera y devolver nuestra función polinómica original:

$$

$$\ begin {alineado} P (x) & = {y_1} \ left ({x-x_2 \ over x_1-x_2} \ cdot {x-x_3 \ over x_1-x_3} \ right) + {y_2} \ left ( {x-x_1 \ over x_2-x_1} \ cdot {x - \ _ 3 \ over x_2-x_3} \ right) + {y_3} \ left ({x-x_1 \ over x_3-x_1} \ cdot {x-x_2 \ sobre x_3-x_2} \ right) \\ P (x) & = {1716} \ left ({x-27 \ over 18-27} \ cdot {x-31 \ over 18-31} \ right) + {3768 } \ left ({x-18 \ over 27-18} \ cdot {x-31 \ over 27-31} \ right) + {4940} \ left ({x-18 \ over 31-18} \ cdot {x -27 \ over 31-27} \ right) \\ P (x) & = 42 + 3x + 5x ^ 2 \ end {alineado}$$

Porque sabemos que $$$S = P (0)$recuperacion $$$S$llevado a cabo simplemente:

$$

$$\ begin {alineado} P (0) & = 42 + 3 (0) + 5 (0) ^ 2 \\ P (0) & = 42 \ end {alineado}$$

Usar aritmética de enteros inseguros

Aunque hemos aplicado con éxito la idea básica de Shamir $$$(k, n)$, todavía tenemos un problema que hemos ignorado hasta ahora. Nuestra función polinómica utiliza aritmética de enteros inseguros. Tenga en cuenta que por cada punto adicional que recibe el atacante en el gráfico de nuestra función, hay menos opciones para otros puntos. Puede verlo con sus propios ojos cuando construye un gráfico con un aumento en el número de puntos para una función polinómica usando aritmética de enteros. Esto es contraproducente para nuestro objetivo de seguridad declarado, porque el atacante no tiene que aprender absolutamente nada hasta que tenga al menos $$$k$fragmentos

Para demostrar cuán débil es el esquema con la aritmética de enteros, considere un escenario en el que un atacante obtuvo dos puntos $$$(18, 1716), (27,3768)$y conoce información pública que $$$k = 3$. De esta información puede deducir $$$f (x)$igual a dos y conecta los valores conocidos en la fórmula $$$x$y $$$f (x)$.

$$

$$\ begin {alineado} f (x) & = a_0 + a_1x + a_2x ^ 2 + a_3x ^ 3 + ... + a_ {k-1} x ^ {k-1} \\ f (x) & = S + a_1x + a_2x ^ 2 \\ f (18) \ equiv 1716 & = S + a_118 + a_218 ^ 2 \\ f (27) \ equiv 3768 & = S + a_127 + a_227 ^ 2 \ end {alineado}$$

Entonces el atacante puede encontrar $$$a_1$contando $$$f (27) - f (18)$:

$$

$$\ begin {alineado} 3768-1716 & = (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) \\ 2052 & = 9a_1 + 405a_2 \\ 9a_1 & = 2052 - 405a_2 \\ a_1 & = \ frac {2052 - 405a_2} {9} \\ a_1 & = 228 - 45a_2 \ end {alineado}$$

Como hemos identificado $$$a_1, ..., a_ {k-1}$como enteros positivos seleccionados al azar, hay un número limitado de posibles $$$a_2$. Usando esta información, un atacante puede inferir $$$a_2 \ in [1,2,3,4,5]$, ya que todo lo que sea más de 5 servirá $$$a_1$negativo Esto resulta ser cierto, como determinamos $$$a_2 = 5$

Entonces el atacante puede calcular los posibles valores $$$S$reemplazando $$$a_1$en $$$f (18)$:

$$

$$\ begin {alineado} 1716 & = S + a_118 + a_218 ^ 2 \\ 1716 & = S + 18 \ left (228 - 45a_2 \ right) + a_218 ^ 2 \\ 1716 - S & = 18 \ left (228 - 45a_2 \ right) + a_218 ^ 2 \\ -S & = 18 \ left (228 - 45a_2 \ right) + a_218 ^ 2 - 1716 \\ -S & = 4104 - 810a_2 + a_218 ^ 2 - 1716 \\ S & = -4104 + 810a_2 - a_218 ^ 2 + 1716 \\ S & = 810a_2 - 324a_2 -2388 \\ S & = 486a_2 - 2388 \ end {alineado}$$

Con una selección limitada de opciones para $$$a_2$queda claro lo fácil que es elegir y verificar los valores $$$S$. Solo hay cinco opciones.

Resolver el problema con aritmética de enteros inseguros

Para eliminar esta vulnerabilidad, Shamir sugiere usar aritmética modular, reemplazando $$$f (x)$en $$$f (x) \ mod p$donde $$$p \ in \ mathbb {P}: p> S, p> n$y $$$\ mathbb {P}$- el conjunto de todos los primos.

Recuerde rápidamente cómo funciona la aritmética modular. Un reloj con flechas ya es un concepto familiar. Ella usa relojes que son $$$\ mod 12$. Tan pronto como la manecilla de las horas pasa a las doce, vuelve a la una. Una propiedad interesante de este sistema es que simplemente mirando el reloj, no podemos deducir cuántas revoluciones ha hecho la manecilla de la hora. Sin embargo, si sabemos que la manecilla de la hora ha pasado 12 veces cuatro veces, podemos determinar completamente el número de horas transcurridas utilizando una fórmula simple $$$a = mq + r$donde $$$m$Es nuestro divisor (aquí $$$m = 12$), $$$q$Es el coeficiente (cuántas veces el divisor sin residuo va al número original, aquí $$$q = 4$) y $$$r$Es el resto, que generalmente devuelve el módulo de llamada del operador (aquí $$$r = 1.5$) Conocer todos estos valores nos permite resolver la ecuación para $$$a = 49.5$pero si omitimos el coeficiente, nunca podremos restaurar el valor original.

Puede demostrar cómo esto mejora la seguridad de nuestro circuito aplicando el circuito a nuestro ejemplo anterior y utilizando $$$p = 73$. Nuestra nueva función polinómica $$$f ’(x) = 42 + 3x + 5x ^ 2 \ mod 73$y nuevos puntos $$$(18, 37), (27, 45), (31, 49), (35, 67)$. Ahora, los encargados de teclas pueden usar una vez más la interpolación polinómica para restaurar nuestra función, solo que esta vez las operaciones de suma y multiplicación deben ir acompañadas de una reducción de módulo $$$p$(p. ej. $$$48 + 93 \ mod 73 = 68$)

Usando este nuevo ejemplo, supongamos que el atacante reconoce dos de estos nuevos puntos, $$$(18, 37), (27, 45)$e información pública $$$k = 3, p = 73$. Esta vez, el atacante, basado en toda la información que tiene, muestra las siguientes funciones, donde $$$\ mathbb {N}$Es el conjunto de todos los enteros positivos, y $$$q_x$representa el coeficiente del módulo $$$f ’(x)$.

$$

$$\ begin {alineado} f '(x) & = S + a_1x + a_2x ^ 2 \ mod 73 \\ f' (x) & = S + a_1x + a_2x ^ 2 - 73q_x: q_x \ in \ mathbb {N} \\ f '(18) \ equiv 37 & = S + a_118 + a_218 ^ 2 - 73q_ {18} \\ f' (27) \ equiv 45 & = S + a_127 + a_227 ^ 2 - 73q_ {27} \ end {alineado}$$

Ahora nuestro atacante encuentra de nuevo $$$a_1$por computación $$$f ’(27) - f’ (18)$:

$$

$$\ begin {alineado} 45 - 37 & = (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) + (-73q_ {27} - (-73q_ {18})) \\ 8 & = 9a_1 + 405a_2 + 73 (q_ {18} - q_ {27}) \\ -9a_1 & = -8 + 405a_2 + 73 (q_ {18} - q_ {27}) \\ 9a_1 & = 8 - 405a_2 - 73 (q_ {18} - q_ {27}) \\ a_1 & = \ frac {8 - 405a_2 - 73 (q_ {18} - q_ {27})} {9} \\ a_1 & = \ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ end {alineado}$$

Luego intenta nuevamente retirarse $$$S$reemplazando $$$a_1$en $$$f ’(18)$:

$$

$$\ begin {alineado} 37 & = S + 18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ right) + a_218 ^ 2 - 73q_ {18} \\ -S & = 18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27}) \ right) + a_218 ^ 2 - 73q_ {18} - 37 \\ S & = -18 \ left (\ frac {8} {9} - 45a_2 - \ frac {73} {9} (q_ {18} - q_ {27} ) \ right) - 324a_2 + 73q_ {18} + 37 \\ S & = 486a_2 + 21 + 219q_ {18} - 146q_ {27} \ end {alineado}$$

Esta vez tiene un problema grave. No hay valores en la fórmula. $$$a_2$, $$$q_ {18}$y $$$q_ {27}$. Como hay un número infinito de combinaciones de estas variables, no puede recibir ninguna información adicional.

Consideraciones de seguridad

El esquema de intercambio secreto de Shamir ofrece seguridad en términos de teoría de la información . Esto significa que las matemáticas son resistentes incluso contra un atacante con potencia informática ilimitada. Sin embargo, el circuito aún contiene varios problemas conocidos.

Por ejemplo, el esquema de Shamir no crea fragmentos de prueba , es decir, las personas pueden presentar libremente fragmentos falsos e interferir con la restauración del secreto correcto. Un guardián de fragmentos hostil con suficiente información puede incluso producir otro fragmento cambiando $$$S$a su discreción Este problema se resuelve mediante el uso de esquemas compartidos secretos verificados , como el esquema Feldman.

Otro problema es que la longitud de cualquier fragmento es igual a la longitud del secreto correspondiente, de modo que la longitud del secreto es fácil de determinar. Este problema se resuelve rellenando trivialmente el secreto con números arbitrarios de hasta una longitud fija.

Finalmente, es importante tener en cuenta que nuestras preocupaciones de seguridad pueden ir más allá del alcance del esquema en sí. Para las aplicaciones criptográficas del mundo real, a menudo existe una amenaza de ataques en canales de terceros, cuando un atacante intenta extraer información útil del tiempo de ejecución de la aplicación, el almacenamiento en caché, los bloqueos, etc. Si esto le preocupa, debe considerar cuidadosamente el uso de salvaguardas durante el desarrollo, como las funciones y la búsqueda con un tiempo de ejecución constante, evitar el almacenamiento de memoria en el disco y considerar una serie de otras cosas que están más allá del alcance de este artículo.

Demo

Esta página tiene una demostración interactiva del esquema de intercambio secreto de Shamir. La demostración se realizó sobre la base de la biblioteca ssss-js , que en sí misma es el puerto JavaScript del popular programa ssss . Tenga en cuenta que calcular valores grandes $$$k$, $$$n$y $$$S$Puede tomar algo de tiempo.