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

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

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

Идея

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

Идея схемы заключается в том, что двух точек достаточно для задания прямой, трех точек — для задания параболы, четырех точек — для кубической параболы, и так далее. Чтобы задать многочлен степени $k$ требуется $k+1$ точек.

Если мы хотим разделить секрет таким образом, чтобы восстановить его могли только $k$ человек, мы «прячем» его в формулу $(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_1x + M \right) \mod p$

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

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

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

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

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

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

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

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

$\begin{align} F\left( x \right) &=& \sum\limits_i {l_i \left( x \right)y_i } &\mod p \\ l_i \left( x \right) &=& \prod\limits_{i \ne j} {\frac{{x - x_j }}{{x_i - x_j }}} &\mod p \\ \end{align}$

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

Пример

Пусть нужно разделить секрет «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{align} 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{align}$

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

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

$\left\{\begin{align} \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{align} \right.$

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

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

$\begin{align} F\left( x \right) &= \sum\limits_i {l_i \left( x \right)y_i } &\mod p \\ l_i \left( x \right) &= \prod\limits_{i \ne j} {\frac{{x - x_j }}{{x_i - x_j }}} &\mod p \\ \end{align}$

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

$\begin{align} 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) &= 7 x ^ 2 + 8 x + 11 \mod 13 \end{align}$

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

Литература

• Шнайер Б. 23.2 Алгоритмы разделения секрета. Схема интерполяционных полиномов Лагранжа // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 588—589. — 816 с. — 3000 экз. — ISBN 5-89392-055-4
• Adi Shamir How to share a secret (англ.) // Communications of the ACM. — New York, NY, USA: ACM, 1979. — В. 11. — Т. 22. — С. 612 — 613. — ISSN 0001-0782. — DOI:10.1145/359168.359176