shamirs_secret_sharing.tex

\subsection[$(n,N)$-схема Шамира]{$(n,N)$-схема Шамира распределения \protect\\ секрета}
\selectlanguage{russian}


\subsubsection{Необходимые сведения из линейной алгебры}

Рассмотрим матрицу Вандермонда $V$ размера $(n \times n)$, где
\[
    V = \left(\begin{array}{cccc}
        {1} & {1} & { \ldots } & {1} \\
        {x_{1} } & {x_{2} } & { \ldots } & {x_{n} } \\
        {\begin{array}{l} {} \\ {x_{1}^{2} } \end{array}} &
            {\begin{array}{l} {} \\ {x_{2}^{2} } \end{array}} &
            {\begin{array}{l} {} \\ { \ldots } \end{array}} &
            {\begin{array}{l} {} \\ {x_{n}^{2} } \end{array}} \\
        {\begin{array}{l} { \ldots } \\ {x_{1}^{n-1} } \end{array}} &
            {\begin{array}{l} { \ldots } \\ {x_{2}^{n-1} } \end{array}} &
            {\begin{array}{l} { \ldots } \\ { \ldots } \end{array}} &
            {\begin{array}{l} { \ldots } \\ {x_{n}^{n-1} } \end{array}}
    \end{array}\right),
\]
где $x_{i}$ -- элемент поля $\Z_{p}$, $x_{i} \ne x_{j}$, $p$ -- большое простое число.

Определитель матрицы Вандермонда равен
    \[ \det V = \prod_{1\le i < j\le n} \left(x_j - x_i \right) \mod p. \]
В частности, при $n=2$ определитель
    \[ \det V = x_2 - x_1, \]
при $n=3$ определитель равен
    \[ \det V = (x_3 - x_2) (x_3 - x_1) (x_2 - x_1). \]

Если все элементы $x_{i}$ имеют различные значения, то $\det V \ne 0$, и матрица Вандермонда является невырожденной. Это значит, что существует обратная матрица.

Определим вектор-строку
    \[ \left(K_{0}, K_{1},  \ldots,  K_{n-1}\right), ~ K_{i} \in \Z_{p}. \]
как решение уравнения
%Ставим задачу решить уравнение
    \[ (K_{0} ,K_{1} ,  \ldots, K{}_{n-1} )V=(y_{1} ,  \ldots, y_{n} ), \]
или, что эквивалентно, решение системы уравнений
\[ \begin{array}{l}
    y_1 = K_0 + K_1 x_1 + K_2 x_1^2 + \dots + K_{n-1} x_1^{n-1}, \\
    y_2 = K_0 + K_1 x_2 + K_2 x_2^2 + \dots + K_{n-1} x_2^{n-1}, \\
    \dots \\
\end{array} \]

Используя методы линейной алгебры, получим решение в виде
    \[ (K_{0} ,K_{1} ,  \ldots,  K_{n-1} )=(y_{1} ,  \ldots,  y_{n} )V^{-1}, \]
где $V^{-1}$ -- обратная матрица.

Однако прямого вычисления обратной матрицы здесь можно избежать.  Введем для этого многочлены
\[ \begin{array}{c}
    K(x)= K_{0} +K_{1} x+ \ldots +K_{n-1} x^{n-1}, \\
    y_{i} =K(x_{i}). \\
\end{array} \]
Теперь решение этой задачи можно задать интерполяционной формулой Лагранжа:
\[
    K(x) = y_1 \frac{(x - x_2)(x - x_3) \dots (x - x_n)} {(x_1-x_2)(x_1-x_3) \dots (x_1-x_n)} +
\] \[
    + y_2 \frac{(x-x_1)(x-x_3) \dots (x-x_n)} {(x_2-x_1)(x_2-x_3) \dots (x_2-x_n)} + \dots +
\] \[
    + y_n \frac{(x-x_1)(x-x_2) \dots (x-x_{n-1})} {(x_n-x_1)(x_n-x_2) \dots (x_n-x_{n-1})}.
\]

Первое слагаемое равно нулю в точках $x_2, x_3, \dots, x_n$,   равно $y_1$ в точке $x_1$. Знаменатель не обращается в нуль, так как все $x_1, \dots, x_n$ имеют различные значения. Второе слагаемое равно $y_2$ в точке $x_2$, а при всех других значениях $x_i$ обращается в нуль. Аналогично обстоят дела с остальными слагаемыми.

Из всех коэффициентов $K_0, K_1, \dots, K_{n-1}$ нас интересует только $K_0$.
Положив $x=0$, получаем выражение  для $K_{0} $ в виде
\[
    K(x) = (-1)^{n-1} y_1 \frac{x_2 x_3 \dots x_n} {(x_1-x_2) \dots (x_1-x_n)} +
\] \[
    + (-1)^{n-1} y_2 \frac{x_1 x_3 \dots x_n} {(x_2-x_1) \dots (x_2-x_n)} + \dots +
\] \[
    + (-1)^{n-1} y_n \frac{x_1 x_2 \dots x_{n-1}} {(x_n-x_1) \dots (x_n-x_{n-1})}.
\]

Интерполяционный многочлен Лагранжа принимает заданные значения в заданных точках. В нашей задаче $K(x)=K_{0}$ при $x=0$.


\subsubsection{Описание $(n, N)$-схемы Шамира}

В пороговой \textbf{схеме Шамира}\index{распределение секрета!Шамира} распределения секретов доверенная сторона предварительно производит следующие действия.
\begin{itemize}
    \item Выбирает большое простое число $p: ~ p \sim 2^{512} \dots 2^{1024}$.
    \item Выбирает $N$ различных чисел $x_1, x_2, \dots, x_N$, каждое из которых меньше $p$.
    \item Выбирает прямоугольную матрицу Вандермонда:
        \[
            V_{n \times N} = \left( \begin{array}{cccc}
                {1} & {1} & { \ldots } & {1} \\
                {x_{1} } & {x_{2} } & { \ldots } & {x_{N} } \\
                { \ldots } & { \ldots } & { \ldots } & { \ldots } \\
                {x_{1}^{n-1} } & {x_{2}^{n-1} } & { \ldots } & {x_{N}^{n-1} }
            \end{array} \right) \mod p.
        \]
    \item Выбирает секрет $K_0$, а также выбирает случайные числа $K_1, K_2, \dots, K_{n-1}$.
    \item Вычисляет частичные секреты -- числа $y_1, y_2, \dots, y_N$:
        \[ (y_1, y_2, \dots, y_N) = (K_0, K_1, \dots, K_{n-1}) V. \]
\end{itemize}

Распределение секрета $K_0$ между $N$ сторонами состоит в том, что доверенная сторона выдает легальному пользователю $i$  открытый ключ $\PK_i$, который известен всем, и секретный ключ $\SK_i$ (секрет только $i$-го пользователя):
\[ \begin{array}{ll}
    \PK_1 = x_1, & \SK_1 = y_1, \\
    \PK_2 = x_2, & \SK_2 = y_2, \\
    \cdots & \\
    \PK_N = x_N, & \SK_N = y_N. \\
\end{array} \]

Покажем, что такое распределение удовлетворяет поставленным требованиям.

Пусть собрались любые $n$ из общего числа $N$ пользователей, имеющих значения $(x_i, y_i)$. Каждому из них можно поставить в соответствие один столбец матрицы Вандермонда: $y_i = K(x_i)$. Как показано в предыдущем параграфе, это позволяет найти  значение $K_0$.

Предположим, что собралось $m$, $m<n$, пользователей. Заметим, что число неизвестных $K_0, K_1, \dots, K_{n-1}$ в системе уравнений осталось неизменным и равным $n$, а число уравнений меньше, так как $m<n$. В этом случае решение существует, но не является единственным. Если коэффициенты многочленов взяты из поля $\Z_p$, то число решений является конечным.

Например, если $m = n - 1$, тогда
    \[ K_0 + K_1 x_j + K_2 x_j^2 + \dots + K_{n-1} x_j^{n-1} = y_j, \]
и $K_0$ может принимать $p$ значений. Найти все решения перебором -- вычислительно трудная задача.

Если $m = n - 2$, то число различных решений равно $p^2$. Это число экспоненциально  возрастает по мере уменьшения числа собравшихся вместе получателей секрета.

Таким образом, схема Шамира распределения секрета удовлетворяет предъявленным требованиям.


\subsubsection{Пример схемы Шамира}

Метод Шамира, называемый также схемой интерполяционных полиномов Лагранжа\index{многочлен!интерполяционный Лагранжа}, основывается на том, что для восстановления многочлена $f(x)$ степени $k-1$ необходимо и достаточно знать значения многочлена в любых $k$ разных точках.

Для секрета $M$ формируется многочлен
    \[ f(x) = \sum\limits_{i=1}^{k-1} a_i x^i + M, \]
где коэффициенты $a_i$ выбираются случайно. Вычисляются значения $y_i = f(x_i)$ в $n$ различных точках. Пользователю $i$ выдается тень $(x_i, y_i)$.

Для восстановления секрета по любым $k$ точкам $(x_i, y_i)$ используется интерполяционный многочлен Лагранжа:
    \[ f(x) = \sum\limits_{i=0}^{k-1} y_i \cdot l_i(x), ~~ l_i(x) = \prod\limits_{j=0, j \neq i}^{k-1} \frac{x - x_j}{x_i - x_j}. \]
Общий секрет $M$ является свободным коэффициентом $f(x)$.
    \[ M = \sum\limits_{i=0}^{k-1} y_i \prod\limits_{j=0, j \neq i}^{k-1} \frac{x_j}{x_j - x_i}. \]

\example
Приведем схему Шамира в поле $\GF{p}$. Для разделения секрета $M$ в $(3,n)$ схеме используется
    \[ f(x) = a x^2 + b x + M \mod p, \]
где $p$ -- простое число. Пусть $p=23$. Восстановим секрет $M$ по \emph{теням}
    \[ (1,14), (4,21), (15,6). \]

Последовательно вычисляем

    \[ M = \sum\limits_{i=0}^{k-1} y_i \prod\limits_{j=0, j \neq i}^{k-1} \frac{x_j}{x_j - x_i} \mod p = \]
    \[= 14 \cdot \frac{4}{4-1} \cdot \frac{15}{15-1} + 21 \cdot \frac{1}{1-4} \cdot \frac{15}{15-4} + 6 \cdot \frac{1}{1-15} \cdot \frac{4}{4-15} \mod 23 = \]
    \[ =14 \cdot \frac{4}{3} \cdot \frac{15}{14} + 21 \cdot \frac{1}{-3} \cdot \frac{15}{11} + 6 \cdot \frac{1}{-14} \cdot \frac{4}{-11} \mod 23 = \]
    \[= 20 - 7 \cdot 15 \cdot 11^{-1} + 12 \cdot 7^{-1} \cdot 11^{-1} \mod 23 = \]
    \[ = 13 \mod 23.\]
\exampleend