Как математика делит секрет на бесполезные части
Представьте, что важный ключ хранится в одном сейфе. Единственную копию можно потерять, но простое размножение ключа тоже не решает задачу, потому что каждая новая копия становится ещё одной точкой компрометации. Нужен другой принцип: распределить данные между несколькими хранителями так, чтобы заранее заданное число участников могло восстановить секрет, а меньшая группа не получала о нём полезной информации. Именно такую пороговую конструкцию Ади Шамир описал в 1979 году.
Две страницы, которые изменили управление ключами
Статья «How to Share a Secret» заняла страницы 612 и 613 ноябрьского выпуска Communications of the ACM. Шамир предложил представить секрет числом и записать его как свободный член случайного многочлена степени не выше K−1. Затем многочлен вычисляется в N различных ненулевых точках, и каждая пара из номера точки и полученного значения становится отдельной долей.
Любые K точек однозначно определяют многочлен степени не выше K−1, поэтому по ним можно вычислить его значение в нуле и вернуть секрет. Если известны только K−1 точек, одного уравнения не хватает. Для каждого возможного значения секрета в поле существует совместимый набор коэффициентов, причём при равномерном выборе случайных коэффициентов все эти варианты одинаково вероятны. В этом точном вероятностном смысле классическая схема обеспечивает совершенную секретность ниже порога, а не просто делает перебор вычислительно дорогим.
В исходной работе вычисления выполняются по простому модулю p, который выбирается больше секрета и количества долей. Это конечное поле: сложение, умножение и деление дают точные результаты без округления, а размер каждой доли остаётся сопоставимым с размером исходного секрета.
Как это устроено простыми словами
Возьмём учебный пример с секретом 42 и схемой (3, 5), где создаются пять долей, а для восстановления нужны любые три. В привычной геометрической аналогии число 42 становится пересечением параболы с осью Y, два остальных коэффициента выбираются случайно, а пять точек на параболе раздаются участникам.
Три точки определяют единственную параболу, поэтому позволяют найти её значение при x = 0. Через две точки на обычной вещественной плоскости можно провести бесконечно много парабол с разными пересечениями оси Y. Это удобная картинка для понимания порога, но реальный алгоритм работает не с гладкой кривой и вещественными координатами, а с конечным набором значений поля. Там вариантов конечное число, и точная гарантия состоит в том, что каждый возможный секрет остаётся одинаково вероятным.
Текст сначала кодируется последовательностью байтов. Для каждого байта независимо строится свой многочлен с отдельными случайными коэффициентами, после чего все многочлены вычисляются при одном и том же номере доли x. В результате участник получает номер точки и последовательность значений, по одному для каждого байта исходного текста.
Формула: как секрет собирается обратно
Браузерный инструмент использует поле GF(256), поэтому один элемент поля точно соответствует одному байту. Для байта b строится многочлен:
f(x) = b ⊕ a₁·x ⊕ a₂·x² ⊕ … ⊕ a_(K−1)·x^(K−1)
Здесь b = f(0), а остальные коэффициенты получают из криптографического генератора браузера. Знак ⊕ обозначает сложение в GF(256), которое совпадает с побитовым XOR; умножение и возведение в степень также выполняются по правилам поля, а не как обычные операции над целыми числами. Доли вычисляются в точках x = 1, 2, …, N, поскольку точка x = 0 сразу раскрыла бы свободный член.
При восстановлении интерполяцию Лагранжа не обязательно выполнять для всего многочлена. Достаточно сразу вычислить его значение в нуле:
b = ⊕ᵢ f(xᵢ)·Lᵢ(0),
где Lᵢ(0) = ∏_(j≠i) xⱼ / (xᵢ ⊕ xⱼ)
В поле характеристики 2 вычитание совпадает со сложением, поэтому разность xᵢ − xⱼ записывается как XOR. У различных ненулевых номеров долей знаменатель не обращается в ноль, а каждый ненулевой элемент поля имеет единственную обратную величину.
В реализации используется тот же способ представления GF(256), который определён для AES в FIPS 197: произведение двоичных многочленов сокращается по неприводимому полиному x⁸ + x⁴ + x³ + x + 1, записываемому как 0x11b. Таблицы умножения и деления строятся с примитивным элементом 3. Это не означает, что инструмент шифрует данные с помощью AES; две конструкции лишь используют одно и то же конечное поле.
Где это используется сегодня
Один из хорошо документированных примеров даёт HashiCorp Vault. В конфигурации Shamir seal система делит unseal key на доли и требует заданный порог для разблокировки хранилища. При этом распределяется не вся база секретов, а сравнительно короткий ключ, который защищает следующий уровень ключей шифрования.
В экосистеме криптокошельков существует SLIP-0039, отдельный стандарт мнемонических долей для резервного копирования мастер-секрета. Он не равен обычной BIP-39 seed-фразе, разрезанной на слова, и не совместим автоматически с любым инструментом, который реализует полиномиальное разделение. Перед созданием реальной резервной копии нужно проверить стандарт, формат и возможность восстановления в другом совместимом приложении.
Пороговые подписи, multisig и церемонии ключей преследуют похожую организационную цель, но их нельзя автоматически называть схемой Шамира. Политика IANA для корневого DNSSEC требует трёх из семи учётных данных Crypto Officers для активации HSM, а все криптографические операции с закрытым KSK должны выполняться внутри проверенного устройства. Та же политика отдельно предусматривает пороговое разделение 5 из 7 для Storage Master Key или Domain Key, но не называет применённый алгоритм схемой Шамира. Поэтому пороговую церемонию нельзя считать доказательством того, что сам ключ подписи разделён полиномом Шамира.
Что умеет наш инструмент
Shamir's Secret Sharing кодирует введённый текст в UTF-8 и делит каждый его байт над GF(256). Можно создать от 2 до 255 долей, выбрать порог от 2 до N, скопировать Base64-представление, сохранить отдельные QR-коды в PNG или SVG либо выгрузить ZIP с QR-кодами, текстовым списком и метаданными. При восстановлении инструмент принимает строки и изображения с QR-кодами, удаляет дубликаты номеров и проверяет, что набран заявленный порог.
В каждой доле записаны версия формата, порог K, случайный восьмибайтовый идентификатор набора, номер x, CRC32 исходного текста и полиномиальные значения. Идентификатор помогает заметить случайное смешивание разных комплектов, а CRC32 обнаруживает многие повреждения после восстановления. Однако это не цифровая подпись и не код аутентификации: человек, способный изменить долю, может также пересчитать неключевой checksum.
Формат имеет ещё два важных ограничения. Длина доли раскрывает длину секрета, а записанный в каждой доле CRC32 позволяет проверять догадки о коротком или предсказуемом тексте. Кроме того, код принудительно выбирает ненулевой старший коэффициент, чтобы каждый байтовый многочлен имел ровно степень K−1; из-за этого при K−1 долях один вариант байта исключается, и классическое доказательство нулевой утечки уже не применяется буквально. Сам полиномиальный payload восстанавливается корректно, но эту реализацию нельзя представлять как строгую и независимо проверенную систему perfect secret sharing.
Все вычисления происходят в открытой вкладке с использованием crypto.getRandomValues, и сам инструмент не отправляет секрет на сервер. Тем не менее загруженная веб-страница исполняет код в обычном браузере, поэтому для долгоживущих мастер-ключей и реальных seed-секретов безопаснее выбрать аудированную реализацию признанного формата, запустить её на изолированном устройстве и заранее проверить процедуру восстановления. Каждую долю всё равно нужно защищать: достижение порога раскрывает весь исходный секрет.
Похожие инструменты
Частые вопросы
Что такое схема разделения секрета Шамира?
Это пороговая криптографическая схема, которая делит секрет на N долей. Любые K корректных долей позволяют восстановить секрет, а в классической конструкции с равномерно выбранными коэффициентами набор из K−1 долей статистически не зависит от него. Ади Шамир описал схему в статье «How to Share a Secret» в 1979 году.
Как работает пороговая схема (K, N)?
Секрет записывают как свободный член случайного многочлена степени не выше K−1, а долями становятся его значения в N различных ненулевых точках. По любым K точкам интерполяция Лагранжа восстанавливает значение многочлена в нуле, то есть секрет.
Где применяется разделение секрета?
Его применяют для распределённого хранения ключей и восстановления доступа. Например, HashiCorp Vault может делить unseal key на доли, а SLIP-0039 определяет совместимый формат мнемонических долей для резервного копирования мастер-секрета криптокошелька. Multisig, threshold signatures и пороговый доступ к HSM решают похожую организационную задачу, но не обязательно используют схему Шамира.
Можно ли использовать этот браузерный инструмент для важных ключей?
Инструмент работает локально и подходит для изучения механизма, но его формат не является SLIP-0039 и не проходил независимый аудит. Кроме того, каждая доля содержит CRC32 исходного секрета, а старший коэффициент выбирается только из ненулевых значений, поэтому строгая гарантия нулевой утечки для K−1 долей к этой реализации неприменима. Для критичных ключей лучше использовать проверенный специализированный продукт и изолированное устройство.
Автор
Alex RelFullstack Engineer
В коммерческой разработке с 2011 года — больше 15 лет. Автор двух SaaS-продуктов: TeleGo.io и LingvoHabit.com. Статьи здесь выросли из реальной клиентской и продуктовой работы.
