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

Схема разделения секрета Шамира — это криптографический алгоритм, созданный для распределённого хранения секретной информации. Метод позволяет разделить секрет (например, ключ шифрования, пароль или код доступа) на _n_ частей (долей, теней), которые распространяются между участниками. Для восстановления исходного секрета необходимо собрать не менее _k_ долей (пороговое значение). При этом любое количество долей меньше _k_ не даёт никакой информации о секрете. Схема была предложена израильским математиком Ади Шамиром в 1979 году и является одним из фундаментальных протоколов пороговой криптографии.

История

Идея порогового разделения секрета возникла из практической потребности: если хранить ключ или пароль у одного человека, он становится уязвимым (потеря, шантаж, смерть). Если хранить несколько копий у разных людей, возрастает риск утечки или кражи. Необходимо было найти компромисс между безопасностью и надёжностью.

В 1979 году Ади Шамир, а также независимо от него советский и израильский учёный Густав Симмонс предложили математические схемы разделения секрета. Схема Шамира основана на свойствах многочленов над конечными полями. Она получила широкое распространение благодаря простоте, доказуемой стойкости и возможности точной настройки параметров (_n_ и _k_).

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

Описание алгоритма

Математическая основа

Схема Шамира базируется на следующем наблюдении: для однозначного задания многочлена степени _k-1_ необходимо знать _k_ различных точек, лежащих на его графике. Если дано меньше _k_ точек, через них можно провести бесконечно много многочленов степени _k-1_. Перехватчик, обладающий менее чем _k_ долями, не может определить, какой из этих многочленов был исходным, и, следовательно, не может восстановить секрет (константу многочлена).

Процедура разделения (delaering)

Пусть S — секрет (число), который необходимо разделить. Работа ведётся в конечном поле F_p, где _p_ — простое число, большее, чем S и число участников _n_. Алгоритм:

1. Выбор параметров: определяются _n_ (общее количество долей) и _k_ (пороговое значение).
2. Создание многочлена: строится многочлен _f(x)_ степени _k-1_ над полем F_p:

_f(x) = S + a₁ x + a₂ x² + ... + a_k-1 x^k-1 (mod p)_, где _a₁, a₂, ..., a_k-1_ — случайные числа из F_p. Свободный член многочлена S — это секрет.

1. Вычисление долей: для каждого участника _i_ (где _i_ принимает значения от 1 до _n_) вычисляется значение _y_i = f(i) mod p_.
2. Распределение: каждая пара _(i, y_i)_ передаётся соответствующему участнику. Число _p_ (модуль) и _k_ (порог) могут быть известны всем участникам или храниться отдельно.

Процедура восстановления (reconstruction)

Для восстановления секрета необходимо собрать любые _k_ долей _(x₁, y₁), (x₂, y₂), ..., (x_k, y_k)_. Восстановление происходит с помощью интерполяции по Лагранжу. Формула для вычисления секрета S:

S = Σ_j=1^k y_j · Π_i≠j (–x_i / (x_j – x_i))  (mod p)

Эта формула позволяет вычислить _f(0)_ = S без восстановления всего многочлена. Любая комбинация из (k-1) долей даёт лишь случайное значение, не связанное с исходным секретом.

Пример

Пусть S = 1234, _n_ = 5, _k_ = 3. Выбираем простое _p_ = 1999. Выбираем случайные коэффициенты _a₁ = 166, a₂ = 94_. Многочлен:

_f(x) = 1234 + 166x + 94x² (mod 1999)_

Вычисляем доли для _x = 1, 2, 3, 4, 5_:

• (1, 1494)
• (2, 1942)
• (3, 2506 = 507 mod 1999 → (3, 507))
• (4, 3210 = 1211 mod 1999 → (4, 1211))
• (5, 4102 = 104 mod 1999 → (5, 104))

Для восстановления секрета можно взять любые 3 доли, например (1,1494), (3,507), (5,104). Интерполяция по Лагранжу даст S = 1234.

Классификация схем разделения секрета

Схема Шамира относится к идеальным и пороговым схемам.

• Идеальная схема: размер каждой доли не превосходит размера секрета. В схеме Шамира доля — это пара чисел (x, y), что примерно в два раза больше размера секрета, однако за счёт использования конечного поля и выбора _x_ как последовательного номера (1, 2, ...) можно считать долю равной одному элементу поля. На практике доли чуть больше секрета, но в пределах O(1).
• Пороговая схема (k, n): для восстановления нужно ровно _k_ долей, а _k-1_ доля не даёт никакой информации. Это свойство называется _безусловной стойкостью_: даже при неограниченной вычислительной мощности противник не сможет восстановить секрет, имея _k-1_ долю (при условии, что модуль _p_ известен и многочлен построен над достаточно большим полем).

Существуют также другие схемы:

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

Применение

Криптография и защита данных

• Хранение мастер-ключей: корневой ключ шифрования делится на доли, хранящиеся у разных администраторов. Для расшифровки требуется консенсус (например, 3 из 5).
• Менеджеры паролей: сервисы вроде LastPass, 1Password и Bitwarden используют варианты схемы для защиты мастер-пароля пользователя или его долей на своих серверах.
• Облачные системы: разделение ключей для доступа к шифрованным данным в облаке (например, Google, Amazon).

Блокчейн и криптовалюты

• Управление кошельками: приватные ключи криптовалютных кошельков делятся на доли между доверенными лицами. Никто не может потратить средства в одиночку.
• Протоколы управления (multisig): в некоторых блокчейнах (например, Ethereum) реализована поддержка мультиподписи, аналогом которой является разделение секрета.

Военная и государственная сфера

• Ядерное оружие: система запуска ракет может требовать одновременной авторизации нескольких офицеров, каждый из которых вводит свою часть кода (например, два из трёх).
• Системы управления чрезвычайными ситуациями: доступ к хранилищам с аварийными планами.

Прочие области

• Резервное копирование: создание надёжных копий паролей от шифрованных дисков.
• Цифровое наследование: разделение секретных данных между наследниками.

Интересные факты

• Ади Шамир — признанный криптограф, соавтор алгоритма RSA, получивший за развитие криптографии с открытым ключом премию Тьюринга в 2002 году.
• Схема Шамира может быть расширена для работы с большими объёмами данных: секрет разбивается на блоки, каждый блок делится независимо.
• Для повышения эффективности часто используется модификация с использованием массива долей — схема не требует, чтобы доли вычислялись для _x = 1,2,...,n_. Можно брать любые _n_ различных значений _x_.
• Алгоритм не является защищённым от квантового взлома (так как основан на конечных полях и полиномиальной интерполяции), но в текущих условиях квантовая атака на схему считается маловероятной из-за огромного размера пространства поиска.

Критика и ограничения

Несмотря на теоретическую безусловную стойкость, на практике существуют уязвимости:

• Атака по сторонним каналам: при реализации алгоритма на реальном оборудовании (смарткарты, серверы) возможна утечка временны́х задержек, потребляемой мощности или электромагнитного излучения, что позволяет восстановить доли.
• Проблема с модулем: если модуль _p_ мал и известен, уменьшается энтропия. При больших секретах необходимо разбивать их на блоки и делить каждый.
• Необходимость доверенного дилера: дилер, который создаёт многочлен и распределяет доли, знает секрет. Если дилер ненадёжен, секрет может быть скомпрометирован. Для решения используются протоколы с совместным вычислением (без единого дилера).
• Хрупкость при утере долей: если потеряно более (n-k) долей, восстановление становится невозможным. Для смягчения используют протоколы перераспределения и восстановления долей (proactive secret sharing).
• Ограничение по размеру секрета: схема Шамира наиболее эффективна для небольших объёмов (ключи, пароли), а не для больших файлов.

Источники

• Ади Шамир. «How to Share a Secret». Communications of the ACM, 1979.
• Дуглас Р. Стинсон. «Криптография. Теория и практика», 3-е издание, 2005.
• Алфред Дж. Менезес, Пол К. ван Орсхот, Скотт А. Ванстон. «Handbook of Applied Cryptography», 1996.
• Голдрич О., Калии Ю. «Cryptography: Theory and Practice», 2016.