Цель протокола разделения секрета (secret sharing) — обеспечить восстановление секретного значения S ÎК только разрешенной коалицией участников, каждый из которых обладает значением, называемым долей (share) или тенью (shadow) секрета s i ÎТ.
Предполагается, что схема разделения секрета включает п участников и управляется авторизованным дилером. Основная функция дилера - разделение секрета на п компонентов («теней») и распределение их среди участников так, что любые т (и более) участников, собравшись вместе и предъявив тени, могут восстановить секретный ключ. Причем любые (т -1) и менее участников не могут этого сделать.
Криптографические схемы разделения секрета известны также под названием m -из- n -схем или (т,п)-пороговых схем.
Определение. Множество { s 1, …, sn }, удовлетворяющее следующим двум условиям, называется (т,п)- пороговой схемой разделения секрета.
1. Секрет S легко может быть вычислен по любым m значениям s i.
2. Знание любых (m -1) значений s i не позволяет определить секрет S.
|
|
Компромисс между криптостойкостью и гибкостью схемы регулируется выбором параметров т и п.
Протокол состоит из двух фаз.
На фазе разделения секрета дилер, знающий некоторый секрет S, генерирует п долей секрета s 1,..., sn и посылает si процессору A i по защищенному каналу связи.
На фазе восстановления секрета любое подмножество из не менее чем m процессоров однозначно восстанавливает секрет, обмениваясь сообщениями по защищенным каналам связи. А любое подмножество из не более чем (т- 1) процессоров не может восстановить секрет.
Определение. Схемой разделения секрета с множеством секретов К и множеством долей Т называвется пара алгоритмов (D,R), таких, что
- D(S) – вероятностный полиномиальный алгоритм раздачи, который исходя из секрета sÎК вычисляет набор долей участников s i ÎТ.
- R(I, x 1, …, x ½I½) – детерминированнный полиномиальный алгоритм восстановления секрета такой, что
D(S)= (s 1, …, s n) Þ S = R(I, x1, …, x ½I½).
Для каждой разрешенной коалиции I алгоритм задает функцию
jI(x 1, …, x ½I½)= R(I, x 1, …, x ½I½),
для каждой неразрешенной коалиции I все возможные значения S равновероятны: " IÏU, " xi ÎТ, P (s=x ½" i ÎI, s i = xi)= P (s=x).
Определение. Схема разделения секрета называется совершенной, если произвольная коалиция либо полностью раскрывает секрет, либо в результате не получает о нем никакой апостериорной информации.
Схема вычисления ключа доступа
1. Схема вычисления ключа доступа при разделении секрета между двумя участниками.
Рассмотрим простейший вариант совершенной схемы. Пусть имеется первичный секретный ключ и два участника, образующих легальную коалицию для получения доступа к секретной информации. Ни один из участников не знает первичного секретного ключа, и только объединение теней, которыми располагают участники, позволяет восстановить первичный ключ и выполнить дешифрование.
|
|
Практическая реализация идеи основана на свойствах арифметики по модулю 2. Рассмотрим первичный ключ S как последовательность двоичных символов (бит) длины п.
Тогда тень первого участника s1 вычисляется путем побитного суммирования первичного ключа и шумовой (случайной) последовательности s2 двоичных символов длины п.
Та же шумовая последовательность s2 используется в качестве тени другого участника. Следовательно, первичный ключ S может быть вычислен суммированием по модулю 2 теней участников:
S = s1+ s2.
Оценка трудоемкости раскрытия первичного ключа для каждого из участников, так же как и для нелегального злоумышленника, составляет 2 п попыток дешифрования в худшем случае и 2 п- 1 в среднем.
Схема Шамира
Схема разделения секрета, предложенная Шамиром [7], построена по принципу полиномиальной интерполяции. Пусть задан многочлен степени (т- 1) над конечным полем Галуа GF(q)из q элементов (GF(q)=Zq, где - q простое).
Секретный ключ задается свободным членом а0, все остальные коэффициенты многочлена — случайные элементы поля. Поле GF(q)известно всем участникам. Каждая из n теней представляет собой точку (xi,уi) кривой, описываемой многочленом Р (x), xi¹ 0.
Воспользовавшись интерполяционной формулой Лагранжа, приведенной ниже, можно восстановить исходный многочлен (и, следовательно, секрет ао) по любым m точкам (теням).
При этом вероятность раскрытия секрета в случае произвольных (т- 1) теней оценивается как q-1, то есть в результате интерполяции по (т- 1) точке секретом может быть любой элемент поля с равной вероятностью. Следовательно, схема Шамира является совершенной.
На рисунке 7.1 представлен специальный случай; т =2 (для восстановления секрета необходимо две тени). Таким образом, двучлен описывает некоторую прямую, пересекающуюся с осью у в точке s (секрет). Каждая тень - точка на прямой. Следовательно, секрет может быть восстановлен по двум произвольным теням, так как для однозначного определения прямой достаточно двух произвольных точек.
В случае задания одной тени в качестве искомого секрета может быть выбрана любая точка на оси у, так как через одну точку можно провести множество различных прямых, пересекающихся с осью у в произвольных точках.
Схема Блэкли
Схема разделения секрета Блэкли имеет геометрическую природу. Секрет представляет собой точку в m -мерном пространстве. Отметим, что для случая m >2 все геометрические построения выполняются над конечным полем GF(q). Каждая из n теней задается как гиперплоскость в m -мерном пространстве. Определение секрета сводится к нахождению точки пересечения m гиперплоскостей.
На рисунке 7.2 представлен специальный случай схемы Блэкли. Каждая тень — прямая, проходящая через эту точку. Для восстановления секрета S (точки на плоскости) необходимо иметь по крайней мере две тени.