Схемы разделения секрета

Схема разделения секрета представляет собой схему предварительного распределения ключей между уполномоченными группами пользователей, в которой ключ заранее определен и одинаков для каждой уполномоченной группы. При этом каждый пользователь получает свою долю или "часть секрета". Схема включает два протокола: протокол формирования долей (разделения секрета) и распределения их между пользователями и протокол восстановления секрета группой пользователей. Схема должна позволять восстанавливать ключ только тем группам пользователей, которые имеют на это полномочия, и никакая другая группа не должна иметь возможности для восстановления ключа или получения о нем какой-либо информации.

Основное назначение схемы разделения секрета — защита ключа от потери. Обычно для защиты от потери делают несколько копий ключа. С возрастанием числа копий ключа возрастает вероятность его компрометации. Если число копий мало, то велик риск потери ключа. Поэтому лучше "разделить" ключ между несколькими лицами так, чтобы допускалась возможность восстановления ключа при различных обстоятельствах несколькими уполномоченными группами с заранее оговоренным составом участников. Тем самым исключается риск безвозвратной потери ключа.

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

В простейшем случае, когда имеется только одна группа, состоящая из t пользователей, уполномоченная формировать ключ, схему разделения секрета можно построить следующим образом. Предположим, к примеру, что ключ представляет собой двоичный вектор s длины т. Выберем случайным образом t векторов s₁, ...,s_t так, чтобы их сумма совпадала с вектором s, и распределим их между пользователями. Теперь, собравшись вместе, они могут легко восстановить значение ключа s, в то время как никакая группа, состоящая из меньшего числа пользователей, не сможет этого сделать. Действительно, в данном случае отсутствие хотя бы одной доли приводит к полной неопределенности относительно значения секрета, поскольку для каждого значения искомого секрета найдется возможный вариант значения отсутствующей доли.

Заметим, что если бы мы в предыдущем примере просто разбили вектор на t частей, то такая схема не могла быть схемой разделения секрета, так как знание любой доли давало бы частичную информацию о секрете s.

Другой пример схемы разделения секрета дает пороговая схема Шамира. Пусть 1 < t ≤ п. Схема разделения секрета между п пользователями называется (n,t)-пороговой, если любая группа из t пользователей может восстановить секрет, в то время как никакая группа из меньшего числа пользователей не может получить никакой информации о секрете.

Для построения (n,t)-пороговой схемы А. Шамир предложил использовать многочлен степени t – 1над конечным полем с достаточно большим числом элементов. Многочлен степени t - 1 можно однозначно восстановить по его значениям в t различных точках, но при этом меньшее число точек использовать для интерполяции нельзя.

Выберем поле F и зафиксируем п различных несекретных элементов r₁,...,r_nÎF, отличных от нуля. Каждый элемент r_i, приписан i-му абоненту сети, . Выберем также t случайных элементов а₀,...,а_i-1 поля F и составим из них многочлен f(х) над полем F степени t - 1, 1< t ≤ n ,

Положим s = f(0) = а₀. Вычислим теперь значения

s₁ = f(r₁),…, s_n = f(r_n)

и распределим в качестве долей между участниками наборы

Для восстановления секрета S можно воспользоваться интерполяционной формулой Лагранжа. Путь имеются t пар (х_i, у_i), где y_i = f(x_i). Тогда формула Лагранжа имеет вид

Так как s = f(0), то из формулы Лагранжа получаем равенства

причем коэффициенты с, не зависят от коэффициентов многочлена f(x) и могут быть вычислены заранее.

С помощью полученной формулы любая группа из t пользователей может легко восстановить секрет. В то же время можно показать, что никакая группа из меньшего числа пользователей не может получить никакой информации о секрете (докажите это самостоятельно).

Схема Шамира удобна тем, что она позволяет легко увеличивать число пользователей. Для этого не нужно ничего менять, кроме множества {r₁,..., r_п}, к которому следует добавить новые элементы r_n+1,..., r_{n+ w}. Компрометация одной доли делает из (n,t)-пороговой схемы (п -1, t -1)-пороговую схему.