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

Векторная схема разделения секрета, или схема Блэкли (Шаблон:Lang-en), — схема разделения секрета между сторонами, основанная на использовании точек многомерного пространства. Предложена Джорджем Блэкли в 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{array}{cc}{d}_1& =-(a_{11}\cdot M+a_{21}\cdot b_2+\dots +a_{k1}\cdot b_k)modp,\\ d_2& =-(a_{12}\cdot M+a_{22}\cdot b_2+\dots +a_{k2}\cdot b_k)modp,\\ & ⋮\\ d_i& =-(a_{1i}\cdot M+a_{2i}\cdot b_2+\dots +a_{ki}\cdot b_k)modp,\\ & ⋮\\ d_n& =-(a_{1n}\cdot M+a_{2n}\cdot b_2+\dots +a_{kn}\cdot b_k)modp.\\ \end{array}$

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

Восстановление секрета

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

$\{\begin{array}{cc}(a_{11}\cdot x_1+a_{21}\cdot x_2+\dots +a_{k1}\cdot x_k+d_1)modp& =0,\\ (a_{12}\cdot x_1+a_{22}\cdot x_2+\dots +a_{k2}\cdot x_k+d_2)modp& =0,\\ & ⋮\\ (a_{1k}\cdot x_1+a_{2k}\cdot x_2+\dots +a_{kk}\cdot x_k+d_k)modp& =0.\\ \end{array}$

Решение системы даёт точку в $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{array}{cc}{d}_1& =-(4\cdot 6+8\cdot 4+2\cdot 2)mod11=6,\\ d_2& =-(2\cdot 6+6\cdot 4+8\cdot 2)mod11=3,\\ d_3& =-(6\cdot 6+8\cdot 4+4\cdot 2)mod11=1,\\ d_4& =-(3\cdot 6+10\cdot 4+1\cdot 2)mod11=6.\\ \end{array}$

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

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

$\{\begin{array}{c}(4\cdot x_1+8\cdot x_2+2\cdot x_3+6)mod11=0,\\ (2\cdot x_1+6\cdot x_2+8\cdot x_3+3)mod11=0,\\ (6\cdot x_1+8\cdot x_2+4\cdot x_3+1)mod11=0.\\ \end{array}$

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

Литература

• Шаблон:Книга:Прикладная криптография
• Шаблон:Source