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

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

История

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

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

Идея

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

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

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

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

Описание

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

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

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

${\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}}$ — некоторые случайные числа, которые нужно будет «забыть» после того, как процедура разделения секрета будет завершена^[3].

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

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

${\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 k}$ в точке ${\displaystyle S}$ (секрет). Каждая доля — точка на прямой. Секрет может быть восстановлен по двум произвольным теням. Однако, в случае задания лишь одной тени в качестве искомого секрета может быть выбрана любая точка на оси ${\displaystyle k}$, так как через одну точку можно провести множество различных прямых, пересекающихся с осью ${\displaystyle k}$ в произвольных точках

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

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

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

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

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

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

${\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 _{j\neq i}{\frac {x-x_{j}}{x_{i}-x_{j}}}&\mod p\\\end{aligned}}}$

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

Свойства

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

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

Недостатки^[4]:

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

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

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

Также схема используется в цифровой стеганографии для скрытой передачи информации в цифровых изображениях^[6][7][8][9], для противодействия атакам по сторонним каналам при реализации алгоритма AES^[10].

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

Пример

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

Возьмём простое число ${\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 _{j\neq i}{\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}$ — и является секретом^[3].

См. также

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