Considere un escenario en el que necesita proteger la bóveda de un banco. Se considera absolutamente inexpugnable sin la llave que se le entrega el primer día de trabajo. Su objetivo es almacenar la clave de forma segura.

Supongamos que decide conservar la clave con usted en todo momento y brindar acceso al almacenamiento según sea necesario. Pero rápidamente se dará cuenta de que una solución de este tipo no se adapta bien en la práctica, porque se requiere su presencia física cada vez que abre el almacenamiento. ¿Qué pasa con las vacaciones que te prometieron? Además, la pregunta es aún más aterradora: ¿y si perdieras tu única llave?

Pensando en tus vacaciones, decides hacer una copia de la llave y confiársela a otro empleado. Sin embargo, comprende que esto tampoco es lo ideal. Al duplicar el número de llaves, también se duplican las posibilidades de robo de llaves.

Desesperado, destruyes el duplicado y decides dividir la clave original por la mitad. Ahora bien, se podría pensar que dos personas de confianza con fragmentos de clave tendrían que estar físicamente presentes para recoger la clave y abrir la bóveda. Esto significa que un ladrón necesita robar dos piezas, lo que es el doble de difícil que robar una llave. Sin embargo, pronto te darás cuenta de que este esquema no es mucho mejor que solo una clave, porque si alguien pierde media clave, no se puede recuperar la clave completa.

El problema se puede resolver con una serie de llaves y cerraduras adicionales, pero este enfoque requerirá rápidamente много llaves y cerraduras. Decide que el diseño ideal sería compartir la clave para que la seguridad no dependa exclusivamente de una sola persona. También concluye que debe haber algún umbral para la cantidad de fragmentos de modo que si se pierde un fragmento (o si una persona se va de vacaciones), toda la clave siga funcionando.

como compartir un secreto

Este tipo de esquema de gestión de claves fue pensado por Adi Shamir en 1979 cuando publicó su trabajo. "Como compartir un secreto". El artículo explica brevemente el llamado esquema de umbral para dividir eficientemente un valor secreto (como una clave criptográfica) en partes. Entonces, cuando y sólo cuando al menos de Las piezas están ensambladas, puedes restaurar fácilmente el secreto. .

Desde el punto de vista de la seguridad, una propiedad importante de este esquema es que el atacante no debe saber absolutamente nada a menos que tenga al menos partes. Incluso la presencia Las piezas no deben proporcionar ninguna información. A esta propiedad la llamamos seguridad semántica.

Interpolación polinomial

Esquema de umbral de Shamir construido alrededor del concepto interpolación polinomial. Si no estás familiarizado con este concepto, en realidad es bastante simple. De hecho, si alguna vez dibujaste puntos en un gráfico y luego los conectaste con líneas o curvas, ¡ya lo has usado!

A través de dos puntos puedes dibujar un número ilimitado de polinomios de grado 2. Para elegir el único entre ellos, necesitas un tercer punto. Ilustración: Wikipedia

Considere un polinomio de grado uno, . Si quieres trazar esta función en una gráfica, ¿cuántos puntos necesitas? Bueno, sabemos que esta es una función lineal que forma una línea y por eso necesita al menos dos puntos. A continuación, considere una función polinómica de grado dos, . Esta es una función cuadrática, por lo que se requieren al menos tres puntos para trazar la gráfica. ¿Qué tal un polinomio de grado tres? Al menos cuatro puntos. Y así sucesivamente y así sucesivamente.

Lo realmente interesante de esta propiedad es que, dado el grado de la función polinómica y al menos puntos, podemos derivar puntos adicionales para esta función polinómica. A la extrapolación de estos puntos adicionales la llamamos interpolación polinomial.

inventando un secreto

Quizás ya te hayas dado cuenta de que aquí es donde entra en juego el inteligente plan de Shamir. digamos nuestro secreto - es . podemos girar a un punto en el gráfico y obtener una función polinómica con grado , lo que satisface este punto. Te recordamos que será nuestro umbral de fragmentos requeridos, por lo que si establecemos el umbral en tres fragmentos, debemos elegir una función polinómica de grado dos.

Nuestro polinomio tendrá la forma Donde и — números enteros positivos seleccionados aleatoriamente. Simplemente estamos construyendo un polinomio con grado. , donde el coeficiente libre  - Este es nuestro secreto , y para cada uno de los siguientes términos hay un coeficiente positivo seleccionado aleatoriamente. Si volvemos al ejemplo original y asumimos que , entonces obtenemos la función .

En este punto podemos generar fragmentos conectando enteros únicos en Donde (porque es nuestro secreto). En este ejemplo, queremos distribuir cuatro fragmentos con un umbral de tres, por lo que generamos puntos aleatoriamente. y enviar un punto a cada una de las cuatro personas de confianza, los custodios de la clave. También le hacemos saber a la gente que , ya que se considera información pública y es necesaria para la recuperación .

Recuperando el secreto

Ya hemos discutido el concepto de interpolación polinomial y cómo subyace al esquema de umbral de Shamir. . Cuando tres de los cuatro fideicomisarios quieran restaurar , sólo necesitan interpolar con sus propios puntos únicos. Para ello, pueden determinar sus puntos. y calcule el polinomio de interpolación de Lagrange usando la siguiente fórmula. Si la programación le resulta más clara que las matemáticas, entonces pi es esencialmente un operador for, que multiplica todos los resultados, y sigma es for, que suma todo.

en podemos resolverlo así y devolver nuestra función polinómica original:

porque sabemos que , recuperación hecho simplemente:

Usar aritmética de enteros insegura

Aunque hemos aplicado con éxito la idea básica de Shamir , nos quedamos con un problema que hasta ahora habíamos ignorado. Nuestra función polinómica utiliza aritmética de enteros insegura. Tenga en cuenta que por cada punto adicional que obtiene un atacante en la gráfica de nuestra función, hay menos posibilidades para otros puntos. Puedes ver esto con tus propios ojos cuando trazas un número creciente 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 debería saber absolutamente nada hasta que tenga al menos fragmentos.

Para demostrar cuán débil es el circuito aritmético de enteros, considere un escenario en el que un atacante obtuvo dos puntos y conoce información pública que . De esta información puede deducir , igual a dos, e inserte los valores conocidos en la fórmula и .

El atacante puede entonces encontrar , contando :

Ya que hemos definido como enteros positivos seleccionados aleatoriamente, hay un número limitado de posibles . Usando esta información, un atacante puede deducir , ya que cualquier valor mayor que 5 servirá negativo. Esto resulta ser cierto ya que hemos determinado

El atacante puede entonces calcular los valores posibles. reemplazando в :

Con opciones limitadas para queda claro lo fácil que es seleccionar y comprobar los valores . Aquí sólo hay cinco opciones.

Resolver el problema con la aritmética de enteros insegura

Para eliminar esta vulnerabilidad, Shamir sugiere utilizar aritmética modular, reemplazando en Donde и — el conjunto de todos los números primos.

Recordemos rápidamente cómo funciona la aritmética modular. Un reloj con manecillas es un concepto familiar. Ella usa un reloj que es . Tan pronto como la manecilla de las horas pasa de 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 dado la manecilla de las horas. Sin embargo, si sabemos que la manecilla de las horas ha pasado cuatro veces por 12, podemos determinar completamente el número de horas que han pasado usando una fórmula sencilla. Donde  es nuestro divisor (aquí ),  es el coeficiente (cuántas veces el divisor entra en el número original sin resto, aquí ), y  es el resto, que generalmente devuelve una llamada al operador de módulo (aquí ). Conocer todos estos valores nos permite resolver la ecuación para , pero si omitimos el coeficiente, nunca podremos restaurar el valor original.

Podemos demostrar cómo esto mejora la seguridad de nuestro esquema aplicando el esquema a nuestro ejemplo anterior y usando . Nuestra nueva función polinómica , y los nuevos puntos . Ahora los encargados de las claves pueden volver a utilizar la interpolación polinomial para reconstruir nuestra función, sólo que esta vez las operaciones de suma y multiplicación deben ir acompañadas de una reducción de módulo. (p.ej ).

Usando este nuevo ejemplo, supongamos que el atacante aprendió dos de estos nuevos puntos, e información pública . Esta vez, el atacante, basándose en toda la información que tiene, genera las siguientes funciones, donde  es el conjunto de todos los números enteros positivos, y representa el coeficiente del módulo .

Ahora nuestro atacante vuelve a encontrar , calculando :

Luego lo intenta de nuevo reemplazando в :

Esta vez tiene un problema grave. Valores faltantes de fórmula , и . Como hay un número infinito de combinaciones de estas variables, no puede obtener ninguna información adicional.

Consideraciones de Seguridad

El plan secreto para compartir de Shamir sugiere Seguridad desde el punto de vista de la teoría de la información.. Esto significa que las matemáticas son resistentes incluso a un atacante con una potencia informática ilimitada. Sin embargo, el circuito todavía contiene varios problemas conocidos.

Por ejemplo, el plan de Shamir no crea fragmentos a comprobar, es decir, las personas pueden presentar libremente fragmentos falsos e interferir con la recuperación del secreto correcto. Un guardián de fragmentos hostil con suficiente información podría incluso producir otro fragmento cambiando a su propia discreción. Este problema se resuelve usando esquemas de intercambio de secretos verificables, como el esquema de Feldman.

Otro problema es que la longitud de cualquier fragmento es igual a la longitud del secreto correspondiente, por lo que la longitud del secreto es fácil de determinar. Este problema se puede resolver mediante trivialidades. relleno secreto con números arbitrarios hasta una longitud fija.

Finalmente, es importante señalar que nuestras preocupaciones de seguridad pueden extenderse más allá del diseño mismo. Para las aplicaciones criptográficas del mundo real, a menudo existe la amenaza de ataques de canal lateral en los que 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, durante el desarrollo se debe considerar cuidadosamente el uso de medidas de protección, como funciones y búsquedas de tiempo constante, evitar que la memoria se guarde en el disco y una serie de otras consideraciones que están fuera del alcance de este artículo.

Manifestación

En En esta página Hay una demostración interactiva del plan secreto para compartir de Shamir. Demostración basada en la biblioteca. ssss-js, que a su vez es una adaptación de JavaScript del popular programa ssss. Tenga en cuenta que calcular valores grandes , и puede tardar un poco.

Fuente: habr.com