EssayAI
Блог
Блог
Математика и алгоритмы

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

19 июня 2026Время чтения: 7 минут
#схема Шамира#разделение секрета#пороговая схема#интерполяция Лагранжа#конечное поле
Схема разделения секрета Шамира: порог k из n

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

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

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

f(x)=S+a1x+a2x2+⋯+ak−1xk−1.f(x) = S + a_1 x + a_2 x^2 + \dots + a_{k-1} x^{k-1}.

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

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

Полином степени k минус один через k точек, секрет в точке x равно ноль
Полином степени k минус один через k точек, секрет в точке x равно ноль

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

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

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

Простое число $p$ должно быть больше и секрета $S$, и числа участников $n$. Стандартный выбор для байтовых секретов - поле $\mathrm{GF}(2^8)$, в котором работает, например, утилита ssss.

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

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

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

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

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

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

Секрет делится на n долей, любые k восстанавливают, k минус один бессильны
Секрет делится на n долей, любые k восстанавливают, k минус один бессильны

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

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

S=f(0)=∑j=1kyj∏m=1m≠jkxmxm−xj(modp).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.

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

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

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

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

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

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

S=1⋅22−1+4⋅11−2=1⋅2+4⋅(−1)=2−4=−2≡5(mod7).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=2k = 2. Та же логика однозначного восстановления по точкам лежит и в основе интерполяционной формулы Лагранжа, только там без поля и без секретности.

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

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

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

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

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

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

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

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

FAQ

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

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

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

Коротко

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

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Эллиптические кривые в криптографии: точки и ключи

Эллиптические кривые в криптографии: точки и ключи

Как эллиптические кривые применяют для обмена ключами и цифровых подписей: сложение точек над конечным полем, учебный расчёт, ECDH и границы стойкости ECC.

8 ноября 20268 минут
Неприводимый многочлен над полем: определение и примеры

Неприводимый многочлен над полем: определение и примеры

Что такое неприводимый многочлен над полем, как проверить его для степеней два и три и почему ответ зависит от поля. Примеры над Q, R и конечными полями.

8 ноября 20269 минут
Примитивный многочлен над конечным полем

Примитивный многочлен над конечным полем

Примитивный многочлен над конечным полем: как проверить неприводимость и порядок корня, найти период и отличить это понятие от примитивности над целыми числами.

8 ноября 20268 минут
Абсолютная и относительная погрешность числа

Абсолютная и относительная погрешность числа

Абсолютная и относительная погрешность приближённого числа: формулы, расчёт в процентах, оценка при округлении и подробные примеры сравнения точности.

8 ноября 20268 минут
Абсолютная пропускная способность СМО: формула

Абсолютная пропускная способность СМО: формула

Как найти абсолютную пропускную способность СМО через интенсивность потока и вероятность отказа: формула, пример расчёта и отличие от относительной способности.

8 ноября 20268 минут
Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

Алгоритм Флойда-Уоршелла на примере: как получить матрицу кратчайших путей для всех пар вершин, восстановить маршрут и вовремя обнаружить отрицательный цикл.

8 ноября 20268 минут