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

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

ИсторияПравить

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

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

ИдеяПравить

 

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

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

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

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

ОписаниеПравить

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

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

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

$F\left(x\right)=\left(a_{k-<!--\; -\; -->1}{x}^{k-<!--\; -\; -->1}+a_{k-<!--\; -\; -->2}{x}^{k-<!--\; -\; -->2}+\cdots <!--\; \cdots \; -->+a_{1}x+M\right)\mathrm{mod}p$$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$$M$  — это разделяемый секрет, а остальные коэффициенты $a_{k-<!--\; -\; -->1},a_{k-<!--\; -\; -->2},\dots <!--\; \dots \; -->,a_1$$a_{k-1},a_{k-2},\dots ,a_{1}$  — некоторые случайные числа, которые нужно будет «забыть» после того, как процедура разделения секрета будет завершена.

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

Теперь вычисляем «доли» — значения построенного выше многочлена, в $n$$n$  различных точках, причём $(x$$(x$  ≠ $0)$$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$$k$  в точке $S$$S$  (секрет). Каждая доля — точка на прямой. Секрет может быть восстановлен по двум произвольным теням. Однако, в случае задания лишь одной тени в качестве искомого секрета может быть выбрана любая точка на оси $k$$k$ , так как через одну точку можно провести множество различных прямых, пересекающихся с осью $k$$k$  в произвольных точках

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

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

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

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

Особенностью схемы является то, что вероятность раскрытия секрета в случае произвольных $k-<!--\; -\; -->1$$k-1$  долей оценивается как $p^{-<!--\; -\; -->1}$$p^{-1}$  . То есть в результате интерполяции по $k-<!--\; -\; -->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 _{i\neq j}{\frac {x-x_{j}}{x_{i}-x_{j}}}&\mod p\\\end{aligned}}$ 

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

СвойстваПравить

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

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

Недостатки:

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

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

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

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

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

ПримерПравить

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

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

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

В этом многочлене $11$$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$$p=13$  и степенью многочлена $k-<!--\; -\; -->1=2$$k-1=2$ ) раздаются сторонам. Случайные коэффициенты $7,8$$7,8$  и сам секрет $M=11$$M=11$  «забываются».

Теперь любые 3 участника смогут восстановить многочлен и все его коэффициенты, включая последний из них — разделённый секрет. Например, чтобы восстановить многочлен по трём долям $k_2,k_3,k_5$$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 _{i\neq j}{\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$$M=11$  — и является секретом.

См. такжеПравить

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

ЛитератураПравить

• Shamir A. How to share a secret (англ.) // Commun. ACM — [New York]: 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: реализация схемы разделения секретов Шамира с интерактивной демонстрацией.