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

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

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

Свойства[править | править вики-текст]

Несовершенная схема : Количество участника увеличит, номер возможностей для секретной точкой снизит.Например , для t-1 участников  знают линии, в которой лежит секретная точка.

Отсек схемы : Участники  делятся на подгруппы называемых  отсеков . Чтобы получить секрет, кворум отсеков  требуется , но для отсек  участвовать в кворуме, другой кворум акций  требуется.

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

Некоторые участники  не могут получить секрет .

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

Пусть нужно разделить секрет «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» и есть разделяемый секрет.

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