Пороговая схема разделения секрета

Цель протокола разделения секрета (secret sharing) — обеспечить восстановление секретного значения S ÎК только разрешенной коалицией участни­ков, каждый из которых обладает значением, называемым долей (share) или тенью (shadow) секрета s _i ÎТ.

Предполагается, что схема разделения секрета включает п участ­ни­ков и управляется авторизованным дилером. Основная функция дилера - разделение секрета на п компонентов («теней») и распределе­ние их среди участников так, что любые т (и более) участников, собравшись вместе и предъявив тени, могут восстановить секретный ключ. Причем любые (т -1) и менее участников не могут этого сделать.

Криптографические схемы разделения секрета известны также под названием m -из- n -схем или (т,п)-пороговых схем.

Определение. Множество { s ₁, …, s_n }, удовлетворяющее следующим двум условиям, называется (т,п)- пороговой схемой разделения секрета.

1. Секрет S легко может быть вычислен по любым m значениям s _i.

2. Знание любых (m -1) значений s _i не позволяет определить секрет S.

Компромисс меж­ду криптостойкостью и гибкостью схемы регулируется выбором параметров т и п.

Протокол состоит из двух фаз.

На фазе разделения секрета дилер, знающий некоторый секрет S, генерирует п долей секрета s ₁,..., s_n и посылает s_i процессору A _i по защищенному каналу связи.

На фазе восстановления секрета любое подмножество из не менее чем m процессоров однозначно восстанавливает секрет, обмениваясь сообщениями по защищенным каналам связи. А любое подмножество из не более чем (т- 1) процессоров не может восстановить секрет.

Определение. Схемой разделения секрета с множеством секретов К и множеством долей Т называвется пара алгоритмов (D,R), таких, что

- D(S) – вероятностный полиномиальный алгоритм раздачи, который исходя из секрета sÎК вычисляет набор долей участников s _i ÎТ.

- R(I, x ₁, …, x _½I½) – детерминированнный полиномиальный алгоритм восстановления секрета такой, что

D(S)= (s ₁, …, s _n)   Þ S = R(I, x₁, …, x _½I½).

Для каждой разрешенной коалиции I алгоритм задает функцию

j_I(x ₁, …, x _½I½)= R(I, x ₁, …, x _½I½),

для каждой неразрешенной коалиции I все возможные значения S равновероятны: " IÏU, " x_i ÎТ,   P (s=x ½" i ÎI, s _i = x_i)= P (s=x).

Определение. Схема разделения секрета называется совершенной, если произвольная коалиция либо полностью раскрывает секрет, либо в резуль­тате не получает о нем никакой апостериорной информации.

Схема вычисления ключа доступа

1. Схема вычисления ключа доступа при разделении секрета между двумя участниками.

 Рассмотрим простейший вариант совершенной схемы. Пусть имеется первичный секретный ключ и два участника, образующих легальную коалицию для получения доступа к секрет­ной информации. Ни один из участ­ников не знает первичного секретного ключа, и только объединение теней, которыми располагают участники, позволяет восстановить первичный ключ и выполнить дешифрование.

Практическая реализация идеи основана на свойствах арифметики по модулю 2. Рассмотрим первичный ключ S как последовательность двоичных символов (бит) длины п.

Тогда тень первого участника s₁ вычисляется путем побитного суммирования первичного ключа и шумовой (случайной) последовательности s₂ двоичных символов длины п.

Та же шумовая последовательность s₂ используется в качестве тени другого участника. Следовательно, первичный ключ S может быть вычислен суммированием по модулю 2 теней участников:

S = s₁+ s₂.

Оценка трудоемкос­ти раскрытия первичного ключа для каждого из участников, так же как и для нелегального злоумышленника, составляет 2 ^п попыток дешифрова­ния в худшем случае и 2 ^{п- 1} в среднем.

Схема Шамира

Схема разделения секрета, предложенная Шамиром [7], построена по принципу полиномиальной интерполяции. Пусть задан многочлен степени (т- 1) над конечным полем Галуа GF(q)из q элементов (GF(q)=Z_q, где - q простое).

Секретный ключ задается свободным членом а₀, все остальные коэф­фициенты многочлена — случайные элементы поля. Поле GF(q)извес­тно всем участникам. Каждая из n теней представля­ет собой точку (x_i,у_i) кривой, описываемой многочленом Р (x), x_i¹ 0.

Воспользовавшись интерполяционной формулой Лагран­жа, приведен­ной ниже, можно восстановить исход­ный многочлен (и, следова­тель­но, секрет а_о) по любым m точкам (теням).

При этом вероятность раскрытия секрета в случае произволь­ных (т- 1) теней оценивается как q^-1, то есть в результате интер­поля­ции по (т- 1) точке секретом может быть любой элемент поля с равн­ой вероятностью. Следовательно, схема Шамира является совершен­ной.

 

На рисунке 7.1 представлен специальный случай; т =2 (для восстановле­ния секрета необходимо две тени). Таким образом, двучлен описыва­ет некоторую прямую, пересекающуюся с осью у в точке s (секрет). Каждая тень - точка на прямой. Следовательно, секрет может быть восстановлен по двум произвольным теням, так как для однозначного опре­деления прямой достаточно двух произвольных точек.

В случае зада­ния одной тени в качестве искомого секрета может быть выбрана лю­бая точка на оси у, так как через одну точку можно провести множест­во различных прямых, пересекающихся с осью у в произвольных точках.

Схема Блэкли

Схема разделения секрета Блэкли имеет геометрическую природу. Секрет представляет собой точку в m -мерном пространстве. Отметим, что для случая m >2 все геометричес­кие построения выполняются над конеч­ным полем GF(q). Каждая из n теней задается как ги­перплоскость в m -мерном пространстве. Опре­деление секрета сводится к нахо­ждению точки пересечения m гиперплос­костей.

На рисунке 7.2 представлен специаль­ный слу­чай схемы Блэкли. Каждая тень — прямая, про­ходя­щая через эту точку. Для восста­нов­ления секрета S (точки на плос­кости) необходимо иметь по крайней мере две тени.