Алгоритмы разделения секрета

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

Алгоритм разделения секрета, реализованный в PGP, называется полиномиальной интерполяцией ЛаГранжа (еще известный как схема Блейкли-Шамира) и действует побайтно. Он рассматривает каждый байт в конечном поле F₂₅₆. Для каждого байта y₀, разделяемого между участниками от 1 до n, он формирует полиномиальное P, проходящее через точки (x₀, y₀), (1, y₁), (2, y₂), ... , (n, y_n). Пусть m будет числом людей, которые могут восстановить секрет. Случайным образом выбираются y₁, ..., y_m, а остальные y исходят из того, что P должно быть полиномиальным степени m. Предельным количеством долей в этом случае является 255, но этого должно быть достаточно.

Проблемы

В описанном алгоритме нет ничего дурного. Если генератор случайных чисел надежен, алгоритм дает свойство совершенной секретности (perfect secrecy): без нужного количества долей невозможно сказать ничего определенного о содержании секрета, он может принимать любое значение в зависимости от отсутствующих долей. Возможно, по этой причине в PGP реализован только один такой алгоритм.

Единственная проблема с разделением секрета подобного типа в том, что [в PGP] он применяется для разделения закрытых ключей. Разделенный таким методом ключ перед использование требуется восстановить: если хранители хотят что-то подписать, они должны собраться вместе и загрузить в один компьютер все свои доли и парольные фразы. Это создает серьезный риск безопасности: по завершении всей операции они должны убедиться, что вся информация тщательно уничтожена. Если они решат реконструировать ключ на компьютере одного из хранителей, он сможет с легкостью модифицировать свою версию PGP, чтобы скрытно сохранить все доли и введенные парольные фразы.

Существуют более удачные схемы, где ключ можно разделить на части и применять без необходимости реконструировать его. Для RSA и m=n простой метод состоит в нахождении долей S₁, S₂, ..., S_n по S₁ + S₂ + ... + S_n = e mod φ(n). Чтобы рассчитать X = M^e mod φ(n), все участники вычисляют X_i = M^S_i mod φ(n) и совместно восстанавливают X = X₁ ∗ X₂ ∗ ... ∗ X_n mod φ(n).

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

Назад | Дальше