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

Интернет магазин китайских планшетных компьютеров

Компьютеры - Схема разделения секрета Шамира - Описание

23 января 2011

Оглавление:
1. Схема разделения секрета Шамира
2. Описание
3. Пример

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

Выберем некоторое простое число p > M. Это число можно открыто сказать всем участникам. Оно задаёт конечное поле размера p. Над этим полем построим многочлен степени k − 1:

$F \left = \left \mod p$

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

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

$\begin{align} k_1 &=& F \left &=& \left &\mod p \\ k_2 &=& F \left &=& \left &\mod p \\ && \dots \\ k_i &=& F \left &=& \left &\mod p \\ && \dots \\ k_n &=& F \left &=& \left &\mod p \\ \end{align}$

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

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

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

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

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

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

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

<<< NESSIE

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие