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

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

Идея

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

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

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

Описание

Генерация точки

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

Раздача секрета

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

<math>\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}</math> При этом необходимо следить, чтобы любые <math>k</math> уравнений были линейно независимы. В качестве долей секрета сторонам раздают набор коэффициентов, задающих уравнение гиперплоскости.

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

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

<math>\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.</math> Решение системы дает точку в <math>k</math>-мерном пространстве, первая координата которой и есть разделяемый секрет. Систему можно решать любым известным способом, например, методом Гаусса, но при этом необходимо проводить вычисления в поле <math>GF(p)</math>.

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

Свойства

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

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

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

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

Пример

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

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

Каждой стороне необходимо дать уравнение плоскости, проходящей через заданную точку. В 3-мерном пространстве уравнение плоскости задается с помощью 4-ех параметров: <math> a_1\cdot x_1 + a_2\cdot x_2 + a_3\cdot x_3 + d = 0</math>, где <math>x_1, x_2, x_3</math> - координаты, а <math>(a_1, a_2, a_3, d)</math> - параметры, раздаваемые сторонам. Для выбора параметров, можно поступить следующим образом: величины <math>(a_1, a_2, a_3)</math> выбрать случайным образом (при этом необходимо, чтобы полученные плоскости не оказались компланарными), а свободный коэффициент для каждой стороны вычислять по заданной точке и выбранным коэффициентам.

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

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

2-я сторона - <math>(2, 6, 8, d_2)</math>

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

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

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

<math>\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}</math>

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

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

<math>\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.</math>

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

Литература

• Шнайер Б. 23.2 Алгоритмы разделения секрета. Векторная схема // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 589. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.

Отрывок, характеризующий Векторная схема разделения секрета

В медленно расходившемся пороховом дыме по всему тому пространству, по которому ехал Наполеон, – в лужах крови лежали лошади и люди, поодиночке и кучами. Подобного ужаса, такого количества убитых на таком малом пространстве никогда не видал еще и Наполеон, и никто из его генералов. Гул орудий, не перестававший десять часов сряду и измучивший ухо, придавал особенную значительность зрелищу (как музыка при живых картинах). Наполеон выехал на высоту Семеновского и сквозь дым увидал ряды людей в мундирах цветов, непривычных для его глаз. Это были русские.
Русские плотными рядами стояли позади Семеновского и кургана, и их орудия не переставая гудели и дымили по их линии. Сражения уже не было. Было продолжавшееся убийство, которое ни к чему не могло повести ни русских, ни французов. Наполеон остановил лошадь и впал опять в ту задумчивость, из которой вывел его Бертье; он не мог остановить того дела, которое делалось перед ним и вокруг него и которое считалось руководимым им и зависящим от него, и дело это ему в первый раз, вследствие неуспеха, представлялось ненужным и ужасным.
Один из генералов, подъехавших к Наполеону, позволил себе предложить ему ввести в дело старую гвардию. Ней и Бертье, стоявшие подле Наполеона, переглянулись между собой и презрительно улыбнулись на бессмысленное предложение этого генерала.
Наполеон опустил голову и долго молчал.
– A huit cent lieux de France je ne ferai pas demolir ma garde, [За три тысячи двести верст от Франции я не могу дать разгромить свою гвардию.] – сказал он и, повернув лошадь, поехал назад, к Шевардину.


Кутузов сидел, понурив седую голову и опустившись тяжелым телом, на покрытой ковром лавке, на том самом месте, на котором утром его видел Пьер. Он не делал никаких распоряжении, а только соглашался или не соглашался на то, что предлагали ему.
«Да, да, сделайте это, – отвечал он на различные предложения. – Да, да, съезди, голубчик, посмотри, – обращался он то к тому, то к другому из приближенных; или: – Нет, не надо, лучше подождем», – говорил он. Он выслушивал привозимые ему донесения, отдавал приказания, когда это требовалось подчиненным; но, выслушивая донесения, он, казалось, не интересовался смыслом слов того, что ему говорили, а что то другое в выражении лиц, в тоне речи доносивших интересовало его. Долголетним военным опытом он знал и старческим умом понимал, что руководить сотнями тысяч человек, борющихся с смертью, нельзя одному человеку, и знал, что решают участь сраженья не распоряжения главнокомандующего, не место, на котором стоят войска, не количество пушек и убитых людей, а та неуловимая сила, называемая духом войска, и он следил за этой силой и руководил ею, насколько это было в его власти.
Общее выражение лица Кутузова было сосредоточенное, спокойное внимание и напряжение, едва превозмогавшее усталость слабого и старого тела.
В одиннадцать часов утра ему привезли известие о том, что занятые французами флеши были опять отбиты, но что князь Багратион ранен. Кутузов ахнул и покачал головой.
– Поезжай к князю Петру Ивановичу и подробно узнай, что и как, – сказал он одному из адъютантов и вслед за тем обратился к принцу Виртембергскому, стоявшему позади него:
– Не угодно ли будет вашему высочеству принять командование первой армией.
Вскоре после отъезда принца, так скоро, что он еще не мог доехать до Семеновского, адъютант принца вернулся от него и доложил светлейшему, что принц просит войск.
Кутузов поморщился и послал Дохтурову приказание принять командование первой армией, а принца, без которого, как он сказал, он не может обойтись в эти важные минуты, просил вернуться к себе. Когда привезено было известие о взятии в плен Мюрата и штабные поздравляли Кутузова, он улыбнулся.
– Подождите, господа, – сказал он. – Сражение выиграно, и в пленении Мюрата нет ничего необыкновенного. Но лучше подождать радоваться. – Однако он послал адъютанта проехать по войскам с этим известием.
Когда с левого фланга прискакал Щербинин с донесением о занятии французами флешей и Семеновского, Кутузов, по звукам поля сражения и по лицу Щербинина угадав, что известия были нехорошие, встал, как бы разминая ноги, и, взяв под руку Щербинина, отвел его в сторону.
– Съезди, голубчик, – сказал он Ермолову, – посмотри, нельзя ли что сделать.
Кутузов был в Горках, в центре позиции русского войска. Направленная Наполеоном атака на наш левый фланг была несколько раз отбиваема. В центре французы не подвинулись далее Бородина. С левого фланга кавалерия Уварова заставила бежать французов.
В третьем часу атаки французов прекратились. На всех лицах, приезжавших с поля сражения, и на тех, которые стояли вокруг него, Кутузов читал выражение напряженности, дошедшей до высшей степени. Кутузов был доволен успехом дня сверх ожидания. Но физические силы оставляли старика. Несколько раз голова его низко опускалась, как бы падая, и он задремывал. Ему подали обедать.
Флигель адъютант Вольцоген, тот самый, который, проезжая мимо князя Андрея, говорил, что войну надо im Raum verlegon [перенести в пространство (нем.) ], и которого так ненавидел Багратион, во время обеда подъехал к Кутузову. Вольцоген приехал от Барклая с донесением о ходе дел на левом фланге. Благоразумный Барклай де Толли, видя толпы отбегающих раненых и расстроенные зады армии, взвесив все обстоятельства дела, решил, что сражение было проиграно, и с этим известием прислал к главнокомандующему своего любимца.
Кутузов с трудом жевал жареную курицу и сузившимися, повеселевшими глазами взглянул на Вольцогена.
Вольцоген, небрежно разминая ноги, с полупрезрительной улыбкой на губах, подошел к Кутузову, слегка дотронувшись до козырька рукою.
Вольцоген обращался с светлейшим с некоторой аффектированной небрежностью, имеющей целью показать, что он, как высокообразованный военный, предоставляет русским делать кумира из этого старого, бесполезного человека, а сам знает, с кем он имеет дело. «Der alte Herr (как называли Кутузова в своем кругу немцы) macht sich ganz bequem, [Старый господин покойно устроился (нем.) ] – подумал Вольцоген и, строго взглянув на тарелки, стоявшие перед Кутузовым, начал докладывать старому господину положение дел на левом фланге так, как приказал ему Барклай и как он сам его видел и понял.
– Все пункты нашей позиции в руках неприятеля и отбить нечем, потому что войск нет; они бегут, и нет возможности остановить их, – докладывал он.
Кутузов, остановившись жевать, удивленно, как будто не понимая того, что ему говорили, уставился на Вольцогена. Вольцоген, заметив волнение des alten Herrn, [старого господина (нем.) ] с улыбкой сказал: