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




Главная
Новости
Статьи
Строительство
Ремонт
Дизайн и интерьер
Строительная теплофизика
Прочность сплавов
Основания и фундаменты
Осадочные породы
Прочность дорог
Минералогия глин
Краны башенные
Справочник токаря
Цементный бетон




23.06.2021


22.06.2021


20.06.2021


20.06.2021


20.06.2021


20.06.2021


19.06.2021





Яндекс.Метрика

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

24.05.2021


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

История

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

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

Идея

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

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

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

Описание

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

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

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

F ( x ) = ( a k − 1 x k − 1 + a k − 2 x k − 2 + ⋯ + a 1 x + M ) mod p {displaystyle Fleft(x ight)=left(a_{k-1}x^{k-1}+a_{k-2}x^{k-2}+dots +a_{1}x+M ight)mod p}

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

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

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

k 1 = F ( 1 ) = ( a k − 1 ⋅ 1 k − 1 + a k − 2 ⋅ 1 k − 2 + ⋯ + a 1 ⋅ 1 + M ) mod p k 2 = F ( 2 ) = ( a k − 1 ⋅ 2 k − 1 + a k − 2 ⋅ 2 k − 2 + ⋯ + a 1 ⋅ 2 + M ) mod p … k i = F ( i ) = ( a k − 1 ⋅ i k − 1 + a k − 2 ⋅ i k − 2 + ⋯ + a 1 ⋅ i + M ) mod p … k n = F ( n ) = ( a k − 1 ⋅ n k − 1 + a k − 2 ⋅ n k − 2 + ⋯ + a 1 ⋅ n + M ) mod p {displaystyle {egin{aligned}k_{1}&=&Fleft(1 ight)&=&left(a_{k-1}cdot 1^{k-1}+a_{k-2}cdot 1^{k-2}+dots +a_{1}cdot 1+M ight)&mod pk_{2}&=&Fleft(2 ight)&=&left(a_{k-1}cdot 2^{k-1}+a_{k-2}cdot 2^{k-2}+dots +a_{1}cdot 2+M ight)&mod p&&dots k_{i}&=&Fleft(i ight)&=&left(a_{k-1}cdot i^{k-1}+a_{k-2}cdot i^{k-2}+dots +a_{1}cdot i+M ight)&mod p&&dots k_{n}&=&Fleft(n ight)&=&left(a_{k-1}cdot n^{k-1}+a_{k-2}cdot n^{k-2}+dots +a_{1}cdot n+M ight)&mod pend{aligned}}}

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

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

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

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

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

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

F ( x ) = ∑ i l i ( x ) y i mod p l i ( x ) = ∏ i ≠ j x − x j x i − x j mod p {displaystyle {egin{aligned}Fleft(x ight)&=&sum limits _{i}{l_{i}left(x ight)y_{i}}&mod pl_{i}left(x ight)&=&prod limits _{i eq j}{frac {x-x_{j}}{x_{i}-x_{j}}}&mod pend{aligned}}}

где ( x i , y i ) {displaystyle left(x_{i},y_{i} ight)} — координаты точек многочлена. Все операции выполняются также в конечном поле p {displaystyle p} .

Свойства

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

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

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

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

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

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

    Пример

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

    Возьмём простое число p = 13 {displaystyle p=13} . Построим многочлен степени k − 1 = 3 − 1 = 2 {displaystyle k-1=3-1=2} :

    F ( x ) = ( 7 x 2 + 8 x + 11 ) mod 13 {displaystyle Fleft(x ight)=left(7x^{2}+8x+11 ight)mod 13}

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

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

    k 1 = F ( 1 ) = ( 7 ⋅ 1 2 + 8 ⋅ 1 + 11 ) mod 13 = 0 k 2 = F ( 2 ) = ( 7 ⋅ 2 2 + 8 ⋅ 2 + 11 ) mod 13 = 3 k 3 = F ( 3 ) = ( 7 ⋅ 3 2 + 8 ⋅ 3 + 11 ) mod 13 = 7 k 4 = F ( 4 ) = ( 7 ⋅ 4 2 + 8 ⋅ 4 + 11 ) mod 13 = 12 k 5 = F ( 5 ) = ( 7 ⋅ 5 2 + 8 ⋅ 5 + 11 ) mod 13 = 5 {displaystyle {egin{aligned}k_{1}&=Fleft(1 ight)&=left(7cdot 1^{2}+8cdot 1+11 ight)mod 13&=0k_{2}&=Fleft(2 ight)&=left(7cdot 2^{2}+8cdot 2+11 ight)mod 13&=3k_{3}&=Fleft(3 ight)&=left(7cdot 3^{2}+8cdot 3+11 ight)mod 13&=7k_{4}&=Fleft(4 ight)&=left(7cdot 4^{2}+8cdot 4+11 ight)mod 13&=12k_{5}&=Fleft(5 ight)&=left(7cdot 5^{2}+8cdot 5+11 ight)mod 13&=5end{aligned}}}

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

    Теперь любые 3 участника смогут восстановить многочлен и все его коэффициенты, включая последний из них — разделённый секрет. Например, чтобы восстановить многочлен по трём долям k 2 , k 3 , k 5 {displaystyle k_{2},k_{3},k_{5}} им нужно будет решить систему:

    { ( a 2 ⋅ 2 2 + a 1 ⋅ 2 + M ) mod 13 = 3 ( a 2 ⋅ 3 2 + a 1 ⋅ 3 + M ) mod 13 = 7 ( a 2 ⋅ 5 2 + a 1 ⋅ 5 + M ) mod 13 = 5 {displaystyle left{{egin{aligned}left(a_{2}cdot 2^{2}+a_{1}cdot 2+M ight)&mod 13&=3left(a_{2}cdot 3^{2}+a_{1}cdot 3+M ight)&mod 13&=7left(a_{2}cdot 5^{2}+a_{1}cdot 5+M ight)&mod 13&=5end{aligned}} ight.}

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

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

    F ( x ) = ∑ i l i ( x ) y i mod p l i ( x ) = ∏ i ≠ j x − x j x i − x j mod p {displaystyle {egin{aligned}Fleft(x ight)&=sum limits _{i}{l_{i}left(x ight)y_{i}}&mod pl_{i}left(x ight)&=prod limits _{i eq j}{frac {x-x_{j}}{x_{i}-x_{j}}}&mod pend{aligned}}}
    l 1 ( x ) = x − x 2 x 1 − x 2 ⋅ x − x 3 x 1 − x 3 = x − 3 2 − 3 ⋅ x − 5 2 − 5 = 1 3 ( x 2 − 8 x + 15 ) = 9 ( x 2 + 5 x + 2 ) = 9 x 2 + 6 x + 5 mod 13 l 2 ( x ) = x − x 1 x 2 − x 1 ⋅ x − x 3 x 2 − x 3 = x − 2 3 − 2 ⋅ x − 5 3 − 5 = 1 11 ( x 2 − 7 x + 10 ) = 6 ( x 2 + 6 x + 10 ) = 6 x 2 + 10 x + 8 mod 13 l 3 ( x ) = x − x 1 x 3 − x 1 ⋅ x − x 2 x 3 − x 2 = x − 2 5 − 2 ⋅ x − 3 5 − 3 = 1 6 ( x 2 − 5 x + 6 ) = 11 ( x 2 + 8 x + 6 ) = 11 x 2 + 10 x + 1 mod 13 {displaystyle {egin{aligned}l_{1}left(x ight)&={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} ight)=9left({x^{2}+5x+2} ight)=9x^{2}+6x+5mod 13l_{2}left(x ight)&={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} ight)=6left({x^{2}+6x+10} ight)=6x^{2}+10x+8mod 13l_{3}left(x ight)&={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} ight)=11left({x^{2}+8x+6} ight)=11x^{2}+10x+1mod 13end{aligned}}}

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

    F ( x ) = 3 ⋅ l 1 ( x ) + 7 ⋅ l 2 ( x ) + 5 ⋅ l 3 ( x ) mod p a 2 = 9 ⋅ 3 + 6 ⋅ 7 + 11 ⋅ 5 = 7 mod 13 a 1 = 6 ⋅ 3 + 10 ⋅ 7 + 10 ⋅ 5 = 8 mod 13 M = 5 ⋅ 3 + 8 ⋅ 7 + 1 ⋅ 5 = 11 mod 13 F ( x ) = 7 x 2 + 8 x + 11 mod 13 {displaystyle {egin{aligned}Fleft(x ight)&=3cdot l_{1}left(x ight)+7cdot l_{2}left(x ight)+5cdot l_{3}left(x ight)mod pa_{2}&=9cdot 3+6cdot 7+11cdot 5=7mod 13a_{1}&=6cdot 3+10cdot 7+10cdot 5=8mod 13M&=5cdot 3+8cdot 7+1cdot 5=11mod 13Fleft(x ight)&=7x^{2}+8x+11mod 13end{aligned}}}

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