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

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

История

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

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

Идея

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

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

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

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

Описание

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

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

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

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

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

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

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

$\begin{array}{cccccc}{k}_1& =& F\left(1\right)& =& (a_{k-1}\cdot 1^{k-1}+a_{k-2}\cdot 1^{k-2}+\dots +a_1\cdot 1+M)& modp\\ k_2& =& F\left(2\right)& =& (a_{k-1}\cdot 2^{k-1}+a_{k-2}\cdot 2^{k-2}+\dots +a_1\cdot 2+M)& modp\\ & & \dots \\ k_i& =& F\left(i\right)& =& (a_{k-1}\cdot i^{k-1}+a_{k-2}\cdot i^{k-2}+\dots +a_1\cdot i+M)& modp\\ & & \dots \\ k_n& =& F\left(n\right)& =& (a_{k-1}\cdot n^{k-1}+a_{k-2}\cdot n^{k-2}+\dots +a_1\cdot n+M)& modp\\ \end{array}$

Рассмотрим простой случай, когда для восстановления секрета необходимо две тени. Многочлен, в этом случае, будет задавать прямую, пересекающуюся с осью $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{array}{cccc}F\left(x\right)& =& \sum _i{l}_i\left(x\right)y_i& modp\\ l_i\left(x\right)& =& \prod _{j\ne i}\frac{x-x_j}{x_i-x_j}& modp\\ \end{array}$

где $(x_i,y_i)$ — координаты точек многочлена. Все операции выполняются также в конечном поле $p$.

Свойства

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

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)=(7x^2+8x+11)mod13$

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

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

$\begin{array}{cccc}{k}_1& =F\left(1\right)& =(7\cdot 1^2+8\cdot 1+11)mod13& =0\\ k_2& =F\left(2\right)& =(7\cdot 2^2+8\cdot 2+11)mod13& =3\\ k_3& =F\left(3\right)& =(7\cdot 3^2+8\cdot 3+11)mod13& =7\\ k_4& =F\left(4\right)& =(7\cdot 4^2+8\cdot 4+11)mod13& =12\\ k_5& =F\left(5\right)& =(7\cdot 5^2+8\cdot 5+11)mod13& =5\\ \end{array}$

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

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

$\{\begin{array}{ccc}(a_2\cdot 2^2+a_1\cdot 2+M)& mod13& =3\\ (a_2\cdot 3^2+a_1\cdot 3+M)& mod13& =7\\ (a_2\cdot 5^2+a_1\cdot 5+M)& mod13& =5\\ \end{array}$

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

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

$\begin{array}{ccc}F\left(x\right)& =\sum _i{l}_i\left(x\right)y_i& modp\\ l_i\left(x\right)& =\prod _{j\ne i}\frac{x-x_j}{x_i-x_j}& modp\\ \end{array}$

$\begin{array}{cc}{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+5mod13\\ 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+8mod13\\ 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+1mod13\end{array}$

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

$\begin{array}{cc}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)modp\\ a_2& =9\cdot 3+6\cdot 7+11\cdot 5=7mod13\\ a_1& =6\cdot 3+10\cdot 7+10\cdot 5=8mod13\\ M& =5\cdot 3+8\cdot 7+1\cdot 5=11mod13\\ F\left(x\right)& =7x^2+8x+11mod13\end{array}$

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

См. также

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

Литература

• Шаблон:Source
• Шаблон:Книга:Прикладная криптография
• Шаблон:Книга
• Шаблон:Книга

Ссылки

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