Векторная схема разделения секрета

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Векторная схема разделения секрета или же схема Блэкли (англ. Blakley's scheme) — схема разделения секрета между сторонами, основанная на использовании точек многомерного пространства. Предложена Джорджем Блэкли (англ. George Robert (Bob) Blakley Jr.) в 1979 году. Схема Блэкли позволяет создать (t, n)-пороговое разделение секрета для любых t, n.


Идея[править | править вики-текст]

Разделяемым секретом в схеме Блэкли является одна из координат точки в m-мерном пространстве. Долями секрета, раздаваемые сторонам, являются уравнения (m-1)-мерных гиперплоскостей. Для восстановления точки необходимо знать m уравнений гиперплоскостей. Менее, чем m сторон не смогут восстановить секрет, так как множеством пересечения m-1 плоскостей является прямая, и секрет не может быть восстановлен.

Одна доля Две доли - пересекаются вдоль плоскости Три доли - пересекаются в точке
Пример схемы Блэкли в трех измерениях: каждая доля секрета — это плоскость, а секрет — это одна из координат точки пересечения плоскостей. Двух плоскостей недостаточно для определения точки пересечения.

Нужно отметить, что геометрическое описание и иллюстрации приведены для понимания главной идеи схемы. Однако сам процесс разделения секрета происходит в конечных полях с использованием аналогичного, но иного математического аппарата.


Описание[править | править вики-текст]

Генерация точки[править | править вики-текст]

Пусть нужно реализовать (k, n)-пороговую схему, то есть секрет M разделить между n сторонами так, чтобы любые k из них могли восстановить секрет. Для этого выбирается большое простое число p>M, по модулю которого будет строиться поле GF(p). Случайным образом дилер выбирает числа b_2, \dots , b_k \in GF(p). Тем самым задается точка (M, b_2, \dots, b_k) в k-мерном пространстве, первая координата которой является секретом.

Раздача секрета[править | править вики-текст]

Для каждой стороны P_i, i = (1,\dots, n) случайным образом выбираются коэффициенты a_{1i}, a_{2i}, \dots, a_{ki}, равномерно распределенные в поле GF(p). Так как уравнение плоскости имеет вид a_{1i}\cdot x_1 + a_{2i}\cdot x_2 + \dots + a_{ki}\cdot x_k + d_i = 0, для каждой стороны необходимо вычислить коэффициенты d_i:

\begin{align}
 d_1 &=& -\left( a_{11}\cdot M + a_{21}\cdot b_2 + \dots + a_{k1}\cdot b_k \right) &\mod p \\
 d_2 &=& -\left( a_{12}\cdot M + a_{22}\cdot b_2 + \dots + a_{k2}\cdot b_k \right) &\mod p \\
 & \dots \\
 d_i &=& -\left( a_{1i}\cdot M + a_{2i}\cdot b_2 + \dots + a_{ki}\cdot b_k \right) &\mod p \\
 & \dots \\
 d_n &=& -\left( a_{1n}\cdot M + a_{2n}\cdot b_2 + \dots + a_{kn}\cdot b_k \right) &\mod p \\
\end{align}

При этом необходимо необходимо следить, чтобы любые k уравнений были линейно независимы. В качестве долей секрета сторонам раздают набор коэффициентов, задающих уравнение гиперплоскости.

Восстановление секрета[править | править вики-текст]

Для восстановления секрета любым k сторонам необходимо собраться вместе и из имеющихся долей секрета составить уравнения для отыскания точки пересечения гиперплоскостей:

\left\{\begin{align}
   \left( a_{11}\cdot x_1 + a_{21}\cdot x_2 + \dots + a_{k1}\cdot x_k + d_1 \right) &\mod p &= 0  \\
   \left( a_{12}\cdot x_1 + a_{22}\cdot x_2 + \dots + a_{k2}\cdot x_k + d_2 \right) &\mod p &= 0  \\
    \dots \\
   \left( a_{1k}\cdot x_1 + a_{2k}\cdot x_2 + \dots + a_{kk}\cdot x_k + d_k \right) &\mod p &= 0  \\
\end{align} \right.

Решение системы дает точку в k-мерном пространстве, первая координата которой и есть разделяемый секрет. Систему можно решать любым известным способом, например, методом Гаусса, но при этом необходимо проводить вычисления в поле GF(p).

Если число участников встречи будет меньше, чем k, например, k-1, то результатом решения системы уравнений, составленной из имеющегося набора коэффициентов, будет прямая в k-мерном пространстве. Тем самым множество допустимых значений секрета, удовлетворяющих полученной системе, в точности совпадает с полным числом элементов поля GF(p), и секрет равновероятно может принимать любое значение из этого поля. Таким образом, участники, собравшись вместе, не получат никакой новой информации о разделенном секрете.

Пример[править | править вики-текст]

Пусть нужно разделить секрет «6» между 4-я сторонами, при этом любые 3 должны иметь возможность восстановить его. Иными словами, необходимо реализовать (3, 4)-пороговое разделение секрета.

Для этого зададим точку в 3-мерном пространстве, например, (6, 4, 2). Первая координата точки и есть разделяемый секрет, 4 и 2 - некоторые случайные числа. При этом будем работать в поле GF(11), то есть все числа будут вычисляться, как остатки от деления на p = 11.

Каждой стороне необходимо дать уравнение плоскости, проходящей через заданную точку. В 3-мерном пространстве уравнение плоскости задается с помощью 4-ех параметров:  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) выбрать случайным образом (при этом необходимо, чтобы полученные плоскости не оказались компланарными), а свободный коэффициент для каждой стороны вычислять по заданной точке и выбранным коэффициентам.

Например, выберем параметры следующим образом:

1-ая сторона - (4, 8, 2, d_1)

2-ая сторона - (2, 6, 8, d_2)

3-я сторона - (6, 8, 4, d_3)

4-ая сторона - (3, 10, 1, d_4)

Для вычисления неизвестных параметров d воспользуемся значениями координат выбранной точки:

\begin{align}
d_1 &= -\left( 4\cdot 6 + 8\cdot 4 + 2\cdot 2 \right) \mod 11 &= 6 \\
d_2 &= -\left( 2\cdot 6 + 6\cdot 4 + 8\cdot 2 \right) \mod 11 &= 3 \\
d_3 &= -\left( 6\cdot 6 + 8\cdot 4 + 4\cdot 2 \right) \mod 11 &= 1 \\
d_4 &= -\left( 3\cdot 6 + 10\cdot 4 + 1\cdot 2 \right) \mod 11 &= 6 \\
\end{align}

После этого доли секрета вместе с числом p = 11 раздаются сторонам.

Для восстановления секрета любым трем участникам необходимо найти точку пересечения плоскостей, уравнения которых им были заданы. Например, первым трем сторонам для восстановления секрета необходимо будет решить систему уравнений:

\left\{\begin{align}
   \left( 4\cdot x_1 + 8\cdot x_2 + 2\cdot x_3 + 6 \right) &\mod 11 &= 0  \\
   \left( 2\cdot x_1 + 6\cdot x_2 + 8\cdot x_3 + 3 \right) &\mod 11 &= 0  \\
   \left( 6\cdot x_1 + 8\cdot x_2 + 4\cdot x_3 + 1 \right) &\mod 11 &= 0  \\
\end{align} \right.

Систему можно решать любым способом, не забывая при этом, что вычисления ведутся в поле GF(11). Несложно убедиться, что точка (6, 4, 2) является решением системы, ее первая координата «6» и есть разделяемый секрет.


Литература[править | править вики-текст]