Схема разделения секрета Шамира: Математика доверия и полиномы
Как передать ядерный код запуска так, чтобы ни один генерал в одиночку не смог развязать войну, но любые три из пяти генералов, собравшись вместе, смогли бы восстановить пароль? В классической криптографии можно просто разрезать пароль на части, но потеря одной части сделает пароль невосстановимым. Изящное математическое решение этой проблемы предложил Ади Шамир в 1979 году, создав криптографическую схему разделения секрета на основе свойств полиномов.
Схема Шамира — это пороговая схема (k, n). Секрет делится на n долей, которые раздаются участникам. Секрет можно восстановить только в том случае, если вместе соберутся как минимум k участников со своими долями (где k ≤ n). При этом любые k-1 участников не получают абсолютно никакой информации о секрете: для них исходный пароль выглядит как белый шум.
Математический аппарат схемы опирается на фундаментальную теорему алгебры: через k точек на плоскости (с разными x-координатами) можно провести ровно один полином (многочлен) степени k-1. Например: через 2 точки можно провести ровно одну прямую; через 3 точки — ровно одну параболу.
Алгоритм генерации долей выглядит так:
- Главный секрет (S), который нужно скрыть, принимается за свободный член полинома (значение при x = 0).
- Для схемы с порогом k случайным образом генерируется многочлен степени k-1:
f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1}. Коэффициенты a_i — это случайные числа. - Каждому из n участников выдается одна точка на графике этого многочлена. Участнику №1 дается (1, f(1)), участнику №2 — (2, f(2)) и так далее.
Чтобы восстановить секрет, любые k участников приносят свои точки. Используя математическую процедуру, называемую Интерполяцией Лагранжа, они восстанавливают изначальную формулу полинома. Вычислив значение восстановленной формулы в точке x=0, они мгновенно получают секрет S.
В реальной ИТ-индустрии эта алгебраическая геометрия переносится в конечные поля Галуа (чтобы избежать работы с бесконечными дробными числами и не дать взломщикам информацию по приблизительному наклону кривой). Схема Шамира является краеугольным камнем современных технологий распределенного хранения ключей (Multi-Party Computation). Она используется для хранения главных ключей шифрования (Master Keys) в корпоративных менеджерах паролей (HashiCorp Vault), управления резервными фондами криптовалютных бирж и создания защищенных сетей, где доверие математически распределено по всему кластеру.
