Compartiendo un secreto

El intercambio de secretos es un término en criptografía , que se entiende como cualquiera de los métodos de distribución de un secreto entre un grupo de participantes, cada uno de los cuales obtiene su propia parte determinada. El secreto solo puede ser recreado por una coalición de participantes del grupo original, y al menos un número inicialmente conocido de ellos debe estar incluido en la coalición.

Los esquemas de intercambio de secretos se utilizan en casos en los que existe una probabilidad significativa de compromiso de uno o más guardianes de secretos, pero la probabilidad de colusión desleal por parte de una parte significativa de los participantes se considera insignificante.

Los esquemas existentes tienen dos componentes: intercambio de secretos y recuperación de secretos. Compartir se refiere a la formación de partes del secreto y su distribución entre los miembros del grupo, lo que permite compartir la responsabilidad del secreto entre sus miembros. El esquema inverso debe asegurar su restauración, sujeto a la disponibilidad de sus poseedores en un cierto número requerido [1] .

Caso de uso: Protocolo de votación secreta basado en intercambio secreto [2] .

El ejemplo más simple de un esquema de intercambio secreto

Que haya un grupo de personas y un mensaje de longitud , compuesto por caracteres binarios. Si selecciona al azar mensajes binarios que en total serán iguales y distribuye estos mensajes entre todos los miembros del grupo, resulta que será posible leer el mensaje solo si todos los miembros del grupo se juntan [1] . $t$ $s$ $norte$ ${\displaystyle s_{1},\ldots,s_{t))$ $s$

Hay un problema importante en tal esquema: en caso de pérdida de al menos uno de los miembros del grupo, el secreto se perderá irremediablemente para todo el grupo.

Esquema de umbral

A diferencia del procedimiento de división del secreto, en el que , en el procedimiento de división del secreto, la cantidad de acciones que se necesitan para restaurar el secreto puede diferir de la cantidad de acciones en las que se divide el secreto. Tal esquema se denomina esquema de umbral , donde es el número de acciones en las que se dividió el secreto y es el número de acciones que se necesitan para restaurar el secreto. Las ideas de circuitos fueron propuestas de forma independiente en 1979 por Adi Shamir y George Blakley . Además, Gus Simmons [3] [4] [5] estudió procedimientos similares . $t=n$ $\izquierda(t, n\derecha)$ $norte$ $t$ $t \ neq n$

Si la coalición de participantes es tal que tienen suficientes acciones para restaurar el secreto, entonces la coalición se considera permitida. Los esquemas de intercambio de secretos en los que las coaliciones permitidas de participantes pueden recuperar el secreto de forma única, y los no resueltos no reciben ninguna información a posteriori sobre el posible valor del secreto, se denominan perfectos [6] .

Esquema de Shamir

La idea del diagrama es que dos puntos son suficientes para definir una línea recta , tres puntos son suficientes para definir una parábola , cuatro puntos son suficientes para definir una parábola cúbica , y así sucesivamente. Para especificar un polinomio de grado , se requieren puntos . $k$ $k+1$

Para que el secreto sea restaurado solo por los participantes después de la separación, está "oculto" en la fórmula de un polinomio de grado sobre un campo finito . Para restaurar de forma única este polinomio, es necesario conocer sus valores en los puntos, y utilizando un número menor de puntos, no será posible restaurar de forma única el polinomio original. El número de puntos diferentes del polinomio no está limitado (en la práctica, está limitado por el tamaño del campo numérico en el que se realizan los cálculos). $k$ $(k-1)$ $GRAMO$ $k$ $GRAMO$

Brevemente, este algoritmo se puede describir de la siguiente manera. Sea dado un campo finito . Arreglamos varios elementos no secretos distintos de cero de este campo. Cada uno de estos elementos se atribuye a un miembro específico del grupo. A continuación, se selecciona un conjunto arbitrario de elementos del campo , a partir del cual se compone un polinomio sobre un campo de grado . Después de obtener el polinomio, calculamos su valor en puntos no secretos e informamos los resultados a los miembros correspondientes del grupo [1] . $GRAMO$ $norte$ $t$ $GRAMO$ $f(x)$ $GRAMO$ $t-1,1<t\leq n$

Para recuperar el secreto, puedes usar una fórmula de interpolación , como la fórmula de Lagrange .

Una ventaja importante del esquema de Shamir es que es fácilmente escalable [5] . Para aumentar el número de usuarios en un grupo, solo es necesario agregar el número correspondiente de elementos no secretos a los existentes, y se debe cumplir la condición para . Al mismo tiempo, el compromiso de una parte del secreto cambia el esquema de -umbral a -umbral. ${\displaystyle r_{i}\neq r_{j))$ $yo\neq j$ ${\ estilo de visualización (n, t)}$ ${\ estilo de visualización (n-1, t-1)}$

El esquema de Blackley

Dos rectas no paralelas en un plano se cortan en un punto. Cualquier dos planos no coplanares se intersecan en una línea recta, y tres planos no coplanares en el espacio también se intersecan en un punto. En general , los hiperplanos de n n dimensiones siempre se intersecan en un punto. Una de las coordenadas de este punto será un secreto. Si el secreto está codificado como varias coordenadas de un punto, entonces ya desde una parte del secreto (un hiperplano) será posible obtener alguna información sobre el secreto, es decir, sobre la interdependencia de las coordenadas del punto de intersección.


El esquema de Blackley en tres dimensiones: cada parte del secreto es un plano , y el secreto es una de las coordenadas del punto de intersección de los planos. Dos planos no son suficientes para determinar el punto de intersección.

Con la ayuda del esquema de Blackley [4] , se puede crear un esquema de intercambio de secretos (t, n) para cualquier t y n : para hacer esto, se debe usar la dimensión espacial igual a t , y dar a cada uno de los n jugadores un hiperplano que pasa por el punto secreto. Entonces cualquier t de n hiperplanos se intersecará únicamente en un punto secreto.

El esquema de Blackley es menos eficiente que el esquema de Shamir: en el esquema de Shamir cada acción es del mismo tamaño que el secreto, mientras que en el esquema de Blackley cada acción es t veces mayor. Hay mejoras en el esquema de Blakely para mejorar su eficiencia.

Esquemas basados en el teorema del resto chino

En 1983, Maurice Mignotte , Asmuth y Bloom propusieron dos esquemas secretos para compartir basados en el teorema chino del resto . Para un número determinado (en el esquema de Mignotte este es el secreto en sí mismo, en el esquema de Asmuth-Bloom es un número derivado), los restos se calculan después de dividir por una secuencia de números, que se distribuyen a las partes. Debido a restricciones en la secuencia de números, solo un cierto número de partes puede recuperar el secreto [7] [8] .

Deje que el número de usuarios en el grupo sea . En el esquema de Mignotte, se elige un cierto conjunto de números coprimos por pares de modo que el producto de los números más grandes sea menor que el producto del más pequeño de estos números. Sean estos productos iguales y , respectivamente. El número se denomina umbral del esquema construido sobre el conjunto . Como secreto, se elige un número tal que se cumpla la relación . Las partes del secreto se distribuyen entre los miembros del grupo de la siguiente manera: a cada miembro se le asigna un par de números , donde . $norte$ ${\ estilo de visualización \ {m_ {1}, m_ {2},..., m_ {n} \))$ $k-1$ $k$ $METRO$ $norte$ $k$ ${\ estilo de visualización \ {m_ {1}, m_ {2},..., m_ {n} \))$ $S$ ${\ estilo de visualización M<S<N}$ ${\ estilo de visualización (r_ {i}, m_ {i})}$ ${\displaystyle r_{i}\equiv S{\pmod {m_{i))))$

Para recuperar el secreto, debe fusionar los fragmentos. En este caso, obtenemos un sistema de comparaciones de la forma , cuyo conjunto de soluciones se puede encontrar utilizando el teorema chino del resto . El número secreto pertenece a este conjunto y cumple la condición . También es fácil demostrar que si el número de fragmentos es menor que , entonces para encontrar el secreto , es necesario clasificar el orden de los números enteros. Con la elección correcta de números, tal búsqueda es casi imposible de implementar. Por ejemplo, si la profundidad de bits es de 129 a 130 bits, y entonces la relación será del orden [9] . ${\ Displaystyle t \ geq k}$ ${\displaystyle x\equiv r_{i}{\pmod {m_{i))))$ $S$ ${\displaystyle S<m_{1}\cdot m_{2}\cdot ...\cdot m_{t))$ $k$ $S$ ${\ fracción {N}{M}}$ $mi$ $mi$ ${\ estilo de visualización k <15}$ ${\ fracción {N}{M}}$ $2^{100}$

El esquema Asmuth-Bloom es un esquema Mignott modificado. A diferencia del esquema de Mignotte, se puede construir de tal manera que sea perfecto [10] .

Esquemas basados en la resolución de sistemas de ecuaciones

En 1983, Karnin, Green y Hellman propusieron su esquema de intercambio secreto , que se basaba en la imposibilidad de resolver un sistema con incógnitas con menos ecuaciones [11] . $metro$ $metro$

En el marco de este esquema, se eligen vectores bidimensionales de modo que cualquier matriz de tamaño compuesta por estos vectores tenga rango . Deje que el vector tenga dimensión . $n+1$ $metro$ ${\displaystyle V_{0},V_{1},...,V_{n))$ ${\ estilo de visualización m \ veces m}$ $metro$ $tu$ $metro$

El secreto del circuito es el producto de matriz . Las acciones del secreto son obras . $U^{T}V_{0}$ $U^{T}V_{i},1\leq i\leq n$

Teniendo algunas acciones, es posible componer un sistema de ecuaciones lineales de dimensión , en el que los coeficientes son desconocidos . Resolviendo este sistema, puedes encontrar , y teniendo , puedes encontrar el secreto. En este caso, el sistema de ecuaciones no tiene solución si las acciones son menores que [12] . $metro$ ${\ estilo de visualización m \ veces m}$ $tu$ $tu$ $tu$ $metro$

Maneras de engañar al esquema de umbral

Hay varias formas de romper el protocolo del circuito de umbral:

el propietario de una de las acciones puede interferir con la restauración del secreto compartido regalando la acción incorrecta (aleatoria) en el momento adecuado [13] .
un atacante, al no tener una parte, puede estar presente en la recuperación del secreto. Después de esperar el anuncio del número requerido de acciones, rápidamente restaura el secreto por su cuenta y genera otra acción, luego de lo cual la presenta al resto de los participantes. Como resultado, obtiene acceso al secreto y permanece libre [14] .

También existen otras posibilidades de interrupción que no están relacionadas con la implementación del esquema:

un atacante puede simular una situación en la que es necesaria la revelación de un secreto, averiguando así las acciones de los participantes [14] .

Véase también

Notas

↑ 1 2 3 Alferov, Zubov, Kuzmin et al., 2002 , pág. 401.
↑ Schönmakers, 1999 .
↑ CJ Simmons. Una introducción a los esquemas de secreto compartido y/o control compartido y su aplicación // Criptología Contemporánea. - IEEE Press, 1991. - P. 441-497 .
↑ 12 Blakley , 1979 .
↑ 12 Shamir , 1979 .
↑ Blackley, Kabatiansky, 1997 .
↑ Mignotte, 1982 .
↑ Asmut, Bloom, 1983 .
↑ moldoviano, moldoviano, 2005 , p. 225.
↑ Shenets, 2011 .
↑ Karnin, Greene, Hellman, 1983 .
↑ Schneier B. Criptografía aplicada. - 2ª ed. - Triunfo, 2002. - S. 590. - 816 p. - ISBN 5-89392-055-4 .
↑ Pasaila, Alexa, Iftene, 2010 .
↑ 1 2 Schneier, 2002 , pág. 69.

Literatura

Schneier B. 3.7. Intercambio de secretos // Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - M. : Triumph, 2002. - S. 93-96. — 816 pág. - 3000 copias. - ISBN 5-89392-055-4 .
Schneier B. 23.2 Algoritmos de intercambio de secretos // Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - M. : Triumf, 2002. - S. 588-591. — 816 pág. - 3000 copias. - ISBN 5-89392-055-4 .

Blakley G. R. Protección de claves criptográficas (inglés) // Actas de la Conferencia Nacional de Informática de AFIPS de 1979 - Montvale : AFIPS Press , 1979. - P. 313-317. doi : 10.1109/AFIPS.1979.98
Shamir A. Cómo compartir un secreto // Commun . ACM - [Nueva York] : Asociación de Maquinaria de Computación , 1979. - Vol. 22, edición. 11.- Pág. 612-613. — ISSN 0001-0782 — doi:10.1145/359168.359176
Mignotte M. Cómo compartir un secreto (inglés) // Criptografía : actas del taller sobre criptografía Burg Feuerstein, Alemania, 29 de marzo–2 de abril de 1982 / T. Beth — Berlín , Heidelberg , Nueva York, NY , Londres [etc. .] : Springer Berlín Heidelberg , 1983. - P. 371-375. - ( Lecture Notes in Computer Science ; Vol. 149) - ISBN 978-3-540-11993-7 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-39466-4_27
Asmuth C. , Bloom J. Un enfoque modular para la protección de claves // IEEE Trans . inf. Teoría / F. Kschischang - IEEE , 1983. - Vol. 29, edición. 2.- Pág. 208-210. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1983.1056651
Karnin E. D. , Greene J. W. , Hellman M. E. Sobre sistemas de intercambio secreto // IEEE Trans . inf. Teoría / F. Kschischang - IEEE , 1983. - Vol. 29, edición. 1.- Págs. 35-41. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1983.1056621
Blackley D. , Kabatyansky G. A. Esquemas ideales generalizados que comparten un secreto y matroides // Probl. transmisión de información - 1997. - T. 33, núm. 3.- S. 102-110.
Schoenmakers B. Un esquema simple de intercambio de secretos verificable públicamente y su aplicación a la votación electrónica // Avances en criptología — CRYPTO' 99 :19.ª Conferencia anual internacional de criptología Santa Bárbara, California, EE. UU., 15 al 19 de agosto de 1999 Actas / M. Wiener - Springer Berlín Heidelberg , 1999. - P. 148-164. — ISBN 978-3-540-66347-8 — doi:10.1007/3-540-48405-1_10
Alferov A. P. , Zubov A. Yu. , Kuzmin A. S. , Cheremushkin A. V. Fundamentos de criptografía : Libro de texto - 2ª ed., Rev. y adicional - M .: Helios ARV , 2002. - ISBN 978-5-85438-137-6
Moldovyan N. A. , Moldovyan A. A. Introducción a los criptosistemas de clave pública - San Petersburgo. : BHV-Petersburgo , 2005. - 288 p. - ( Tutorial ) - ISBN 978-5-94157-563-3
Pasailă D. , Alexa V. , Iftene S. Detección de trampas e identificación de tramposos en esquemas de intercambio de secretos basados en CRT (inglés) // International Journal of Computing - 2010. - vol. 9, edición. 2.- Pág. 107-117. — ISSN 2312-5381 ; 1727-6209
Shenets N. N. Sobre esquemas modulares ideales para compartir secretos en anillos polinómicos en varias variables // Congreso Internacional de Informática: Sistemas y Tecnologías de la Información : materiales del Congreso Científico Internacional 31 de octubre. - Minsk : BGU , 2011. - V. 1. Artículos de la Facultad de Matemática Aplicada e Informática. - S. 169-173. — ISBN 978-985-518-563-6