Разделение секрета. 
Криптографические методы защиты информации

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

Простейший пример схемы разделения секрета между группой из t пользователей состоит в следующем. Пусть ключ s есть некоторый элемент аддитивной абелевой группы G. Возьмем t элементов 5ь <72, •. , 9t группы G_y для которых справедливо равенство.

и распределим их между t пользователями.

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

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

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

Пусть р — простое число и q = р^т, те N. Рассмотрим далее (п, ?)-пороговую схему на основе многочлена степени t — 1 над конечным полем F_q, предложенную² Ади Шамиром (Adi Shamir).

Пусть заданы п различных ненулевых элементов п, Г2, …, r_n е F_q. Каждый элемент rj соответствует j-му абоненту сети. Пусть также имеется многочлен степени t — 1 над нолем F_q

Положим секрет $ равным s = /(0) = ао. Вычислим значения ^sj = f (rj)y j = 1,…, n и распределим среди участников в качестве долей секрета наборы (г, Sj), j = 1,2,…, n.

Для восстановления секрета s по любым t парам {rj, Sj) можно воспользоваться интерполяционной формулой Лагранжа:

²См. Shamir A. How to share a secret//Communication ACM. — 1979. — V. 22. — No. 11. — pp. 612−613.

Учитывая, что s = /(()), отсюда получаем.

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

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

Данная схема разделения секрета позволяет легко увеличивать число пользователей. Для этого достаточно к множеству {r*i, г^-2,…, г_п} просто добавить новые элементы r_n+i,…, r_n+w.

Отметим, что компрометация одной пары (г, s,;) делает из (n, t) — пороговой схемы (га — l, t — 1)-пороговую схему.