Esquema de vector de intercambio secreto

Un esquema de intercambio de secretos vectoriales , o esquema de Blakley , es un esquema de intercambio de secretos entre partes basado en el uso de puntos en un espacio multidimensional. Propuesto por George Blackley en 1979 . El esquema de Blakely le permite crear un umbral secreto compartido ( t , n ) para cualquier t , n .

Idea

El secreto compartido en el esquema de Blackley es una de las coordenadas del punto en el espacio bidimensional. Las partes del secreto dadas a las partes son las ecuaciones de los hiperplanos -dimensionales . Para restaurar un punto, es necesario conocer las ecuaciones de los hiperplanos. Menos de dos lados no pueden recuperar el secreto, ya que el conjunto de intersección de los planos es una línea y el secreto no se puede recuperar. $metro$ $(m-1)$ $metro$ $metro$ $m-1$


Un ejemplo del 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.

Cabe señalar que la descripción geométrica y las ilustraciones se dan para comprender la idea principal del esquema. Sin embargo, el proceso de compartir secretos en sí tiene lugar en campos finitos utilizando un aparato matemático similar pero diferente.

Descripción

Generación de puntos

Que sea necesario implementar un esquema de umbral, es decir, dividir el secreto entre las partes para que cualquiera de ellas pueda restaurar el secreto. Para ello, se elige un número primo grande , módulo con el que se construirá el campo . Distribuidor aleatorio $(k, n)$ $METRO$ $norte$ $k$ $p>M$ $FG(p)$ [ quien? ] selecciona números . Esto establece un punto en el espacio bidimensional, cuya primera coordenada es un secreto. $b_{2},\puntos,b_{k}\en GF(p)$ $(M,b_{2},\puntos,b_{k})$ $k$

Compartiendo un secreto

Para cada lado , los coeficientes seleccionados al azar se distribuyen uniformemente en el campo . Como la ecuación del plano tiene la forma , para cada lado es necesario calcular los coeficientes : $P_{i},i=(1,\dots,n)$ $a_{{1i}},a_{{2i}},\puntos,a_{{ki}}$ $FG(p)$ $a_{1i}\cdot x_{1}+a_{2i}\cdot x_{2}+\dots +a_{ki}\cdot x_{k}+d_{i}=0$ $d_{i}$

{\begin{alineado}d_{1}&=-(a_{11}\cdot M+a_{21}\cdot b_{2}+\dots +a_{k1}\cdot b_{k}) {\bmod {p)),\\d_{2}&=-(a_{12}\cdot M+a_{22}\cdot b_{2}+\dots +a_{k2}\cdot b_{k} ){\bmod {p)),\\&~\vdots \\d_{i}&=-(a_{1i}\cdot M+a_{2i}\cdot b_{2}+\dots +a_{ki }\cdot b_{k}){\bmod {p)),\\&~\vdots \\d_{n}&=-(a_{1n}\cdot M+a_{2n}\cdot b_{2} +\puntos +a_{kn}\cdot b_{k}){\bmod {p}}.\\\end{alineado}}

En este caso, es necesario asegurarse de que las ecuaciones sean linealmente independientes. Como partes del secreto, las partes reciben un conjunto de coeficientes que definen la ecuación del hiperplano. $k$

Restaurando el secreto

Para restaurar el secreto, las partes deben reunirse y usar las partes disponibles del secreto para hacer ecuaciones para encontrar el punto de intersección de los hiperplanos: $k$

\left\{{\begin{alineado}(a_{11}\cdot x_{1}+a_{21}\cdot x_{2}+\dots +a_{k1}\cdot x_{k}+ d_{1}){\bmod {p}}&=0,\\(a_{12}\cdot x_{1}+a_{22}\cdot x_{2}+\dots +a_{k2}\cdot x_{k}+d_{2}){\bmod {p}}&=0,\\&\vdots \\(a_{1k}\cdot x_{1}+a_{2k}\cdot x_{2} +\puntos +a_{kk}\cdot x_{k}+d_{k}){\bmod {p}}&=0.\\\end{alineado}}\right.

La solución del sistema da un punto en el espacio bidimensional, cuya primera coordenada es el secreto compartido. El sistema se puede resolver por cualquier método conocido, por ejemplo, por el método de Gauss , pero es necesario realizar cálculos en campo . $k$ $FG(p)$

Si el número de participantes de la reunión es menor que , por ejemplo, entonces el resultado de resolver el sistema de ecuaciones, compuesto por el conjunto de coeficientes disponible, será una línea recta en el espacio bidimensional. Así, el conjunto de valores secretos permitidos que satisfacen el sistema resultante coincide exactamente con el número total de elementos del campo , y el secreto puede tomar cualquier valor de este campo con igual probabilidad. Por lo tanto, los participantes, una vez reunidos, no recibirán ninguna información nueva sobre el secreto compartido. $k$ $k-1$ $k$ $FG(p)$

Propiedades

Esquema imperfecto : El número de participantes aumentará, el número de posibilidades para el punto secreto disminuirá. Por ejemplo, para t − 1 los participantes conocen la línea que contiene el punto secreto.

Circuito Compartimental : Los participantes se dividen en subgrupos llamados compartimentos. Para recibir un secreto se requiere un quórum de franjas horarias, pero para que una franja participe de un quórum se requiere otro quórum de cuotas.

Esquemas escalonados : los participantes se dividen en dos niveles ordenados. Para restaurar un secreto, se requiere menos quórum en un nivel superior. Además, cada miembro de nivel superior puede reemplazar a los miembros de nivel inferior.

Algunos participantes no pueden obtener el secreto.

Ejemplo

Deje que sea necesario compartir el secreto "6" entre 4 partes, mientras que 3 deberían poder restaurarlo. En otras palabras, es necesario implementar el uso compartido de secretos de umbral. $(3.4)$

Para hacer esto, establezcamos un punto en el espacio tridimensional, por ejemplo, . La primera coordenada del punto es el secreto compartido, 4 y 2 son algunos números aleatorios. En este caso, trabajaremos en el campo , es decir, todos los números se calcularán como el resto de la división por . $(6,4,2)$ $novia(11)$ $pag=11$

A cada lado se le debe dar una ecuación para un plano que pasa por un punto dado. En el espacio tridimensional, la ecuación de un plano se especifica usando 4 parámetros: , donde son las coordenadas, y son los parámetros distribuidos a los lados. Para seleccionar los parámetros, puede proceder de la siguiente manera: seleccione los valores al azar (en este caso, es necesario que los planos resultantes no resulten coplanares ), y calcule el coeficiente libre para cada lado usando un punto dado y los coeficientes seleccionados. $a_{1}\cdot x_{1}+a_{2}\cdot x_{2}+a_{3}\cdot x_{3}+d=0$ $x_{1},x_{2},x_{3}$ $(a_{1},a_{2},a_{3},d)$ $(a_{1},a_{2},a_{3})$

Por ejemplo, elijamos los parámetros de la siguiente manera:

1er lado: ,

(4,8,2,d_{1})

2do lado: ,

(2,6,8,d_{2})

3er lado: ,

(6,8,4,d_{3})

4to lado: .

(3,10,1,d_{4})

Para calcular los parámetros desconocidos, usamos los valores de las coordenadas del punto seleccionado: $d$

{\begin{alineado}d_{1}&=-(4\cdot 6+8\cdot 4+2\cdot 2){\bmod {1}}1=6,\\d_{2}& =-(2\cdot 6+6\cdot 4+8\cdot 2){\bmod {1}}1=3,\\d_{3}&=-(6\cdot 6+8\cdot 4+4 \cdot 2){\bmod {1}}1=1,\\d_{4}&=-(3\cdot 6+10\cdot 4+1\cdot 2){\bmod {1}}1=6 .\\\end{alineado}}

Después de eso, las partes del secreto, junto con el número , se distribuyen a las partes. $pag=11$

Para restaurar el secreto, tres participantes deben encontrar el punto de intersección de los planos cuyas ecuaciones se les dieron. Por ejemplo, las tres primeras partes en recuperar el secreto deberán resolver el sistema de ecuaciones.

\left\{{\begin{alineado}(4\cdot x_{1}+8\cdot x_{2}+2\cdot x_{3}+6){\bmod {1}}1=0 ,\\(2\cdot x_{1}+6\cdot x_{2}+8\cdot x_{3}+3){\bmod {1}}1=0,\\(6\cdot x_{1 }+8\cdot x_{2}+4\cdot x_{3}+1){\bmod {1}}1=0.\\\end{alineado}}\right.

El sistema se puede resolver de cualquier forma, sin olvidar que los cálculos se realizan en campo . Es fácil asegurarse de que el punto es la solución del sistema, su primera coordenada "6" es el secreto compartido. $novia(11)$ $(6,4,2)$

Literatura

Schneier B. 23.2 Algoritmos para compartir un secreto. Esquema vectorial // 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. 589. - 816 p. - 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