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

Схема интерполяционных полиномов Лагранжа (схема разделения секрета Шамира или схема Шамира) — схема разделения секрета, широко используемая в криптографии. Схема Шамира позволяет реализовать $(k,n)$ — пороговое разделение секретного сообщения (секрета) между $n$ сторонами так, чтобы только любые $k$ и более сторон ($k$ ≤ $n$) могли восстановить секрет. При этом любые $k-1$ и менее сторон не смогут восстановить секрет.

История

В 1979 году израильский криптоаналитик Ади Шамир предложил пороговую схему разделения секрета между $n$ сторонами, которая позволяет проводить разделение таким образом, что:

• Для восстановления секрета достаточно $k$ и больше сторон.
• Никакие $(k-1)$ и меньше сторон не смогут получить никакой информации о секрете.

Идея

Через две точки можно провести неограниченное число полиномов степени 2. Чтобы выбрать из них единственный — нужна третья точка. Данные графики приведены только для иллюстрации идеи — в схеме Шамира используется конечное поле, полиномы над которым сложно представить на графике

Для интерполяции многочлена степени $k-1$ требуется $k$ точек. К примеру, для задания прямой достаточно двух точек, для задания параболы — трех точек, и так далее.

Основная идея данной схемы состоит в том, что интерполяция невозможна, если известно меньшее число точек.

Если мы хотим разделить секрет между $n$ людьми таким образом, чтобы восстановить его могли только $k$ человек ($k$ ≤ $n$), мы «прячем» его в формулу многочлена степени $k-1$. Восстановить этот многочлен и исходный секрет можно только по $k$ точкам. Количество же различных точек многочлена не ограничено (на практике оно ограничивается размером числового поля, в котором ведутся расчёты).

Описание

Подготовительная фаза

Пусть нужно разделить секрет $M$ между $n$ сторонами таким образом, чтобы любые $k$ участников могли бы восстановить секрет (то есть нужно реализовать $(k,n)$-пороговую схему).

Выберем некоторое простое число $p>M$. Это число можно открыто сообщать всем участникам. Оно задаёт конечное поле размера $p$. Над этим полем построим многочлен степени $k-1$ (то есть случайно выберем все коэффициенты многочлена, кроме $M$):

$F\left(x\right)=\left(a_{k-1}x^{k-1}+a_{k-2}x^{k-2}+\dots +a_{1}x+M\right)\mod p$

В этом многочлене $M$ — это разделяемый секрет, а остальные коэффициенты $a_{k-1},a_{k-2},\dots ,a_{1}$ — некоторые случайные числа, которые нужно будет «забыть» после того, как процедура разделения секрета будет завершена.

Генерация долей секрета

Теперь вычисляем «доли» — значения построенного выше многочлена, в $n$ различных точках, причём $(x$ ≠ $0)$:

${\begin{aligned}k_{1}&=&F\left(1\right)&=&\left(a_{k-1}\cdot 1^{k-1}+a_{k-2}\cdot 1^{k-2}+\dots +a_{1}\cdot 1+M\right)&\mod p\\k_{2}&=&F\left(2\right)&=&\left(a_{k-1}\cdot 2^{k-1}+a_{k-2}\cdot 2^{k-2}+\dots +a_{1}\cdot 2+M\right)&\mod p\\&&\dots \\k_{i}&=&F\left(i\right)&=&\left(a_{k-1}\cdot i^{k-1}+a_{k-2}\cdot i^{k-2}+\dots +a_{1}\cdot i+M\right)&\mod p\\&&\dots \\k_{n}&=&F\left(n\right)&=&\left(a_{k-1}\cdot n^{k-1}+a_{k-2}\cdot n^{k-2}+\dots +a_{1}\cdot n+M\right)&\mod p\\\end{aligned}}$

Рассмотрим простой случай, когда для восстановления секрета необходимо две тени. Многочлен, в этом случае, будет задавать прямую, пересекающуюся с осью $k$ в точке $S$ (секрет). Каждая доля — точка на прямой. Секрет может быть восстановлен по двум произвольным теням. Однако, в случае задания лишь одной тени в качестве искомого секрета может быть выбрана любая точка на оси $k$, так как через одну точку можно провести множество различных прямых, пересекающихся с осью $k$ в произвольных точках

Аргументы многочлена (номера секретов) не обязательно должны идти по порядку, главное — чтобы все они были различны по модулю $p$.

После этого каждой стороне, участвующей в разделении секрета, выдаётся доля секрета $k_{i}$ вместе с номером $i$. Помимо этого, всем сторонам сообщается степень многочлена $k-1$ и размер поля $p$. Случайные коэффициенты $a_{k-1},a_{k-2},\dots ,a_{1}$ и сам секрет $M$ «забываются».

Восстановление секрета

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

Особенностью схемы является то, что вероятность раскрытия секрета в случае произвольных $k-1$ долей оценивается как $p^{-1}$ . То есть в результате интерполяции по $k-1$ точке секретом может быть любой элемент поля с равной вероятностью. При этом попытка полного перебора всех возможных теней не позволит злоумышленникам получить дополнительную информацию о секрете.

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

${\begin{aligned}F\left(x\right)&=&\sum \limits _{i}{l_{i}\left(x\right)y_{i}}&\mod p\\l_{i}\left(x\right)&=&\prod \limits _{j\neq i}{\frac {x-x_{j}}{x_{i}-x_{j}}}&\mod p\\\end{aligned}}$

где $\left(x_{i},y_{i}\right)$ — координаты точек многочлена. Все операции выполняются также в конечном поле $p$.

Свойства

К достоинствам данной схемы разделения секрета относят:

1. Идеальность: отсутствует избыточность — размер каждой из долей секрета равен размеру секрета.
2. Масштабируемость: в условиях схемы $(k,n)$ число владельцев долей секрета $n$ может дополнительно увеличиться вплоть до $p$, где $p$ — размер поля, в котором ведутся вычисления. При этом количество долей $k$, необходимых для получения секрета, останется неизменным.
3. Динамичность: можно периодически менять используемый многочлен и пересчитывать тени, сохраняя секрет (свободный член) неизменным. При этом вероятность нарушения защиты путем утечки теней уменьшится, так как для получения секрета нужно $k$ теней, полученных на одной версии многочлена.
4. Гибкость: в тех случаях, когда стороны не являются равными между собой, схема позволяет это учесть путём выдачи сразу нескольких теней одной стороне. Например, пусковой код баллистической ракеты может быть разделён по схеме $(3,5)$ так, чтобы ракету могли запустить лишь три генерала, которые соберутся вместе, либо любой из генералов и президент, которому при разделении секрета было выдано сразу две тени.

Недостатки:

1. Ненадёжность дилера: по умолчанию в схеме предполагается, что тот, кто генерирует и раздаёт тени, надёжен, что не всегда верно.
2. Нет проверки корректности теней сторон: участвующая в разделении сторона не может с уверенностью сказать, что её тень подлинна — при подстановке в исходный многочлен получается верное равенство.

Использование

Данная схема нашла применение в аппаратных криптографических модулях, где она используется для многопользовательской авторизации в инфраструктуре открытых ключей.

Также схема используется в цифровой стеганографии для скрытой передачи информации в цифровых изображениях, для противодействия атакам по сторонним каналам при реализации алгоритма AES.

Помимо этого, с помощью схемы Шамира может осуществляться нанесение цифрового водяного знака при передаче цифрового видео и генерация персонального криптографического ключа, используемого в биометрических системах аутентификации.

Пример

Пусть нужно разделить секрет «11» между 5 сторонами. При этом любые 3 стороны должны иметь возможность восстановить этот секрет. То есть нужно реализовать $(3,5)$-пороговую схему.

Возьмём простое число $p=13$. Построим многочлен степени $k-1=3-1=2$:

$F\left(x\right)=\left(7x^{2}+8x+11\right)\mod 13$

В этом многочлене $11$ — это разделяемый секрет, а остальные коэффициенты 7 и 8 — некоторые случайные числа, которые нужно будет «забыть» после того, как процедура разделения секрета будет завершена.

Теперь вычисляем координаты 5 различных точек:

${\begin{aligned}k_{1}&=F\left(1\right)&=\left(7\cdot 1^{2}+8\cdot 1+11\right)\mod 13&=0\\k_{2}&=F\left(2\right)&=\left(7\cdot 2^{2}+8\cdot 2+11\right)\mod 13&=3\\k_{3}&=F\left(3\right)&=\left(7\cdot 3^{2}+8\cdot 3+11\right)\mod 13&=7\\k_{4}&=F\left(4\right)&=\left(7\cdot 4^{2}+8\cdot 4+11\right)\mod 13&=12\\k_{5}&=F\left(5\right)&=\left(7\cdot 5^{2}+8\cdot 5+11\right)\mod 13&=5\\\end{aligned}}$

После этого ключи (вместе с их номером, числом $p=13$ и степенью многочлена $k-1=2$) раздаются сторонам. Случайные коэффициенты $7,8$ и сам секрет $M=11$ «забываются».

Теперь любые 3 участника смогут восстановить многочлен и все его коэффициенты, включая последний из них — разделённый секрет. Например, чтобы восстановить многочлен по трём долям $k_{2},k_{3},k_{5}$ им нужно будет решить систему:

$\left\{{\begin{aligned}\left(a_{2}\cdot 2^{2}+a_{1}\cdot 2+M\right)&\mod 13&=3\\\left(a_{2}\cdot 3^{2}+a_{1}\cdot 3+M\right)&\mod 13&=7\\\left(a_{2}\cdot 5^{2}+a_{1}\cdot 5+M\right)&\mod 13&=5\\\end{aligned}}\right.$

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

Построим интерполяционный многочлен Лагранжа:

${\begin{aligned}F\left(x\right)&=\sum \limits _{i}{l_{i}\left(x\right)y_{i}}&\mod p\\l_{i}\left(x\right)&=\prod \limits _{j\neq i}{\frac {x-x_{j}}{x_{i}-x_{j}}}&\mod p\\\end{aligned}}$

${\begin{aligned}l_{1}\left(x\right)&={\frac {x-x_{2}}{x_{1}-x_{2}}}\cdot {\frac {x-x_{3}}{x_{1}-x_{3}}}={\frac {x-3}{2-3}}\cdot {\frac {x-5}{2-5}}={\frac {1}{3}}\left({x^{2}-8x+15}\right)=9\left({x^{2}+5x+2}\right)=9x^{2}+6x+5\mod 13\\l_{2}\left(x\right)&={\frac {x-x_{1}}{x_{2}-x_{1}}}\cdot {\frac {x-x_{3}}{x_{2}-x_{3}}}={\frac {x-2}{3-2}}\cdot {\frac {x-5}{3-5}}={\frac {1}{11}}\left({x^{2}-7x+10}\right)=6\left({x^{2}+6x+10}\right)=6x^{2}+10x+8\mod 13\\l_{3}\left(x\right)&={\frac {x-x_{1}}{x_{3}-x_{1}}}\cdot {\frac {x-x_{2}}{x_{3}-x_{2}}}={\frac {x-2}{5-2}}\cdot {\frac {x-3}{5-3}}={\frac {1}{6}}\left({x^{2}-5x+6}\right)=11\left({x^{2}+8x+6}\right)=11x^{2}+10x+1\mod 13\end{aligned}}$

Получим исходный многочлен:

${\begin{aligned}F\left(x\right)&=3\cdot l_{1}\left(x\right)+7\cdot l_{2}\left(x\right)+5\cdot l_{3}\left(x\right)\mod p\\a_{2}&=9\cdot 3+6\cdot 7+11\cdot 5=7\mod 13\\a_{1}&=6\cdot 3+10\cdot 7+10\cdot 5=8\mod 13\\M&=5\cdot 3+8\cdot 7+1\cdot 5=11\mod 13\\F\left(x\right)&=7x^{2}+8x+11\mod 13\end{aligned}}$

Последний коэффициент многочлена — $M=11$ — и является секретом.

См. также

• Схема Блэкли
• Схема Карнина — Грина — Хеллмана

Литература

• Shamir A. How to share a secret (англ.) // Communications of the ACM — New York City: Association for Computing Machinery, 1979. — Vol. 22, Iss. 11. — P. 612—613. — ISSN 0001-0782 — doi:10.1145/359168.359176
• Шнайер Б. 23.2 Алгоритмы разделения секрета. Схема интерполяционных полиномов Лагранжа // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 588—589. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
• Чмора А.Л. Современная прикладная криптография. — 2-е изд., стер.. — М.: Гелиос АРВ, 2002. — С. 123—124. — 256 с. — ISBN 5-85438-046-3.
• Под общ. ред. Ященко В.В. Введение в криптографию. — 2-е изд., испр.. — М.: МЦНМО: «ЧеРо», 1999. — С. 118—125. — 272 с. — ISBN 5-900916-40-5.

Ссылки

ssss: реализация схемы разделения секретов Шамира с интерактивной демонстрацией.