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

История

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

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

Идея

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

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

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

Описание

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

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

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

${\displaystyle 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}$

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

Свойства

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

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

Недостатки :

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

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

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

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

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

Пример

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

${\displaystyle \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.}$

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

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

${\displaystyle {\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}}}$

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

См. также

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

Примечания

Литература

• Shamir A. (англ.) // Communications of the ACM — New York City: Association for Computing Machinery , 1979. — Vol. 22, Iss. 11. — P. 612—613. — ISSN —
• Шнайер Б. 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 .

Ссылки