Схема разделения секрета Шамира: порог k из n

Иногда секрет нельзя доверить одному человеку, но и потеря его недопустима: мастер-ключ к хранилищу, корневой сертификат, код запуска. Схема разделения секрета Шамира решает задачу так, что секрет «размазывается» на $n$ долей, и любые $k$ из них восстанавливают его точно, а любые $k-1$ не дают о нём вообще никакой информации. В основе лежит школьная идея: через $k$ точек проходит ровно один полином степени $k-1$. Ниже разберём математику схемы, восстановление по Лагранжу и типовые ошибки. А чтобы быстро посчитать доли или восстановление под свои числа, соберите условие в форме ниже.

Идея: один полином через k точек

Возьмём многочлен степени $k-1$ со случайными коэффициентами, а свободным членом сделаем сам секрет $S$:

$$f(x) = S + a_1 x + a_2 x^2 + \dots + a_{k-1} x^{k-1}.$$

Доли - это значения полинома в разных ненулевых точках: участник с номером $i$ получает пару $(x_i, f(x_i))$. Сам секрет «спрятан» в точке $x = 0$, ведь $f(0) = S$.

Ключевое свойство интерполяции: полином степени $k-1$ однозначно определяется любыми $k$ точками. Значит, собрав $k$ долей, мы восстановим весь полином - а вместе с ним и $f(0) = S$. Имея же только $k-1$ точку, мы не можем зафиксировать полином: через них проходит бесконечно много кривых нужной степени, и для каждого кандидата на секрет найдётся подходящая. Поэтому неполная группа не получает ни бита информации.

Рассчитать для своей задачи

Почему нужно конечное поле

Если считать в обычных вещественных числах, доли «протекают»: по наклону кривой и порядку величин противник способен оценить $S$ приближённо. Поэтому Шамир предложил работать в конечном поле - обычно $\mathbb{Z}_p$, целые числа по модулю простого $p$, большего и секрета, и числа участников.

В таком поле все арифметические операции замкнуты, а главное - деление: для каждого ненулевого элемента есть обратный по модулю. Это и нужно для восстановления (там придётся делить). Случайные коэффициенты $a_1, \dots, a_{k-1}$ берут равномерно из $\{0, 1, \dots, p-1\}$. Тогда распределение любых $k-1$ долей не зависит от секрета - это и есть свойство совершенной (информационно-теоретической) стойкости.

Раздача долей: схема k из n

Параметры схемы - пара $(k, n)$, её называют пороговой $(k, n)$-схемой:

• $n$ - сколько всего долей выдаётся;
• $k$ - порог: минимальное число долей для восстановления.

Алгоритм раздачи компактен:

1. Выбрать простое $p > \max(S, n)$.
2. Сгенерировать случайные коэффициенты $a_1, \dots, a_{k-1}$ из $\mathbb{Z}_p$.
3. Для $i = 1, \dots, n$ вычислить долю $(i, f(i) \bmod p)$ и выдать участнику $i$.

Точки $x_i$ публичны (это просто номера), секретны лишь значения $f(x_i)$. Точку $x = 0$ не раздают никогда - в ней лежит сам секрет.

Рассчитать для своей задачи

Восстановление: интерполяция Лагранжа

Собрав любые $k$ долей $(x_1, y_1), \dots, (x_k, y_k)$, восстанавливаем секрет по формуле интерполяции Лагранжа, вычисленной в точке $x = 0$:

$$S = f(0) = \sum_{j=1}^{k} y_j \prod_{\substack{m=1 \\ m \neq j}}^{k} \frac{x_m}{x_m - x_j} \pmod p.$$

Внутреннее произведение - это базисные множители Лагранжа $\ell_j(0)$. Все деления выполняются по модулю $p$: вместо «разделить на $d$» умножают на обратный элемент $d^{-1} \bmod p$, который находят расширенным алгоритмом Евклида или через малую теорему Ферма ($d^{-1} \equiv d^{p-2}$).

Поскольку полный полином восстанавливать не обязательно (нужен лишь его свободный член), удобно сразу подставить $x = 0$ - формула выше делает именно это. Если же требуется проверить целостность долей, можно собрать весь $f(x)$ и убедиться, что все $n$ точек на нём лежат.

Маленький пример руками

Пусть $S = 5$, схема $(2, 4)$, поле $p = 7$. Возьмём случайный коэффициент $a_1 = 3$, тогда $f(x) = 5 + 3x$.

Доли: $f(1) = 8 \equiv 1$, $f(2) = 11 \equiv 4$, $f(3) = 14 \equiv 0$, $f(4) = 17 \equiv 3 \pmod 7$. Раздаём $(1,1), (2,4), (3,0), (4,3)$.

Восстановим по долям $(1,1)$ и $(2,4)$:

$$S = 1 \cdot \frac{2}{2-1} + 4 \cdot \frac{1}{1-2} = 1 \cdot 2 + 4 \cdot (-1) = 2 - 4 = -2 \equiv 5 \pmod 7.$$

Получили исходный секрет. Любая другая пара долей дала бы тот же результат - в этом и смысл порога $k = 2$. Та же логика однозначного восстановления по точкам лежит и в основе интерполяционной формулы Лагранжа, только там без поля и без секретности.

Свойства и достоинства

Схема Шамира ценится за набор свойств, редких в одном решении:

• Совершенная стойкость. $k-1$ долей не сужают множество возможных секретов - это доказуемо, а не «вычислительно трудно».
• Минимальность. Размер каждой доли равен размеру секрета; меньше теоретически невозможно для пороговой схемы.
• Гибкость. Можно выдать новому участнику ещё долю $(n+1, f(n+1))$, не трогая остальных, пока точек хватает в поле.
• Обновляемость. Сменив все коэффициенты, кроме свободного члена (так называемый proactive secret sharing), раздают новые доли при том же секрете - старые перехваченные доли обесцениваются.

Где применяют

Пороговая криптография на основе схемы Шамира встречается шире, чем кажется:

• Управление ключами. Мастер-ключ хранилища или HSM делят между несколькими офицерами безопасности; запуск требует кворума.
• Кошельки и блокчейн. Мультиподпись и threshold-signature-схемы делят приватный ключ, чтобы транзакцию подписывал кворум, а не один узел.
• Резервирование секретов. Сид-фразу криптокошелька дробят на доли и раскладывают по разным местам - потеря одной не фатальна.
• Безопасные вычисления. Схема - кирпич протоколов multi-party computation, где стороны считают функцию, не раскрывая входов.

Частые ошибки

• Раздать точку $x = 0$. В ней лежит сам секрет - любой обладатель этой доли знает $S$ целиком. Номера участников начинают с $1$.
• Считать в целых без модуля. Без конечного поля схема теряет совершенную стойкость и протекает по величине значений. Поле обязательно.
• Взять слишком маленькое $p$. Если $p \le S$, секрет не помещается в поле и восстановится с потерей. Нужно $p > \max(S, n)$.
• Путать $k$ и $n$. Восстанавливают $k$ долей, а не $n$. Схема $(3,5)$ требует любых трёх из пяти, а не всех пяти.
• Повторять точки $x_i$. Две доли с одинаковым $x$ ломают интерполяцию (деление на ноль в множителе Лагранжа). Точки должны быть различны.

FAQ

Чем схема Шамира лежит от простого деления секрета пополам? При «разрезании» строки на куски каждый кусок раскрывает часть секрета, и нужны все куски сразу. У Шамира любая неполная группа не знает ничего, а порог $k$ можно задать меньше $n$ - терпимость к потере долей.

Можно ли восстановить секрет, если часть долей подменена? Базовая схема не обнаруживает подлог: подставив фальшивую долю, можно получить неверный $S$ без сигнала об ошибке. Для защиты используют верифицируемое разделение секрета (схема Фельдмана или Педерсена) с криптографическими обязательствами на коэффициенты.

Насколько большим должно быть простое $p$? Достаточно, чтобы поле вмещало секрет и все номера участников. На практике берут $p$ под разрядность секрета: для 128-битного ключа - простое около $2^{128}$ либо поле $\mathrm{GF}(2^n)$ подходящего размера.

Коротко

Схема разделения секрета Шамира - пороговая $(k, n)$-схема: секрет прячут в свободный член случайного полинома степени $k-1$ над конечным полем $\mathbb{Z}_p$, а доли - это значения полинома в точках $1, \dots, n$. Любые $k$ долей восстанавливают секрет интерполяцией Лагранжа в точке $x = 0$; любые $k-1$ не дают о нём ни бита (совершенная стойкость). Доли минимального размера, схему легко расширять и обновлять. Главные ошибки - раздать точку $x = 0$, считать без модуля и взять слишком малое $p$. Применяется в управлении ключами, threshold-подписях и multi-party computation.