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

Поделись знанием:
(перенаправлено с «Схема Шамира»)
Перейти к: навигация, поиск

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





История

В 1979 году израильский криптоаналитик Ади Шамир предложил пороговую схему разделения секрета между <math>n</math> сторонами, которая позволяет проводить разделение таким образом, чтоОшибка Lua : attempt to index local 'entity' (a nil value).:

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

Идея

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

Основная идея данной схемы состоит в том, что интерполяция невозможна, если известно меньшее число точекОшибка Lua : attempt to index local 'entity' (a nil value)..

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

Описание

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

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

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

<math>F \left( x \right) = \left( a_{k-1}x^{k-1}+a_{k-2}x^{k-2}+\dots+a_1x + M \right) \mod p</math>

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

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

Теперь вычисляем «тени» — значения построенного выше многочлена, в <math>n</math> различных точках, причём <math>(x </math> ≠ <math>0) </math>[2]:

<math>\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}</math> Аргументы многочлена (номера секретов) не обязательно должны идти по порядку, главное — чтобы все они были различны по модулю <math>p</math>.

После этого каждой стороне, участвующей в разделении секрета, выдаётся доля секрета — тень <math>k_i </math> вместе с номером <math>i </math>. Помимо этого, всем сторонам сообщается степень многочлена <math>k - 1 </math> и размер поля <math>p </math>. Случайные коэффициенты <math>a_{k-1}, a_{k-2}, \dots, a_1</math> и сам секрет <math>M</math> «забываются»[2].

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

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

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

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

<math>\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}</math>

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

Свойства

К достоинствам данной схемы разделения секрета относятОшибка Lua : attempt to index local 'entity' (a nil value).:

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

Недостатки[3]:

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

Использование

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

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

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

Пример

Пусть нужно разделить секрет «11» между 5-ю сторонами. При этом любые 3 стороны должны иметь возможность восстановить этот секрет. То есть нужно реализовать <math>(3, 5)</math>-пороговую схему[2].

Возьмём простое число <math>p=13</math>. Построим многочлен степени <math>k-1=3-1=2</math>:

<math>F \left( x \right) = \left( 7x^2 + 8x + 11 \right) \mod 13</math>

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

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

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

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

<math>\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.</math> Очевидно, что с меньшим числом известных секретов получится меньше уравнений и систему решить будет нельзя (даже полным перебором решений).

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

<math>\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}</math>

<math>\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}</math> Получим исходный многочлен:

<math>\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}</math> Последний коэффициент многочлена — <math>M = 11</math> — и является секретом[2].

См. также

Напишите отзыв о статье "Схема разделения секрета Шамира"

Примечания

  1. 1 2 Чмора А.Л. Современная прикладная криптография. — 2-е изд., стер.. — М.: Гелиос АРВ, 2002. — С. 123—124. — 256 с. — ISBN 5-85438-046-3.
  2. 1 2 3 4 5 6 7 8 9 Шнайер Б. 23.2 Алгоритмы разделения секрета. Схема интерполяционных полиномов Лагранжа // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 588—589. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
  3. Dawson E., Donovan D. The breadth of Shamir's secret-sharing scheme (англ.) // Computers and Security : Journal. — 1994. — Vol. 13. — Fasc. 1. — P. 71. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=0167-4048&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0167-4048]. — DOI:10.1016/0167-4048(94)90097-3.
  4. P. Luo, A. Yu-Lun Lin, Z. Wang, M. Karpovsky. Hardware Implementation of Secure Shamir's Secret Sharing Scheme (англ.) // HASE '14 Proceedings of the 2014 IEEE 15th International Symposium on High-Assurance Systems Engineering : Proceeding. — Washington, DC, USA: IEEE Computer Society, 2014. — P. 193—200. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=978-1-4799-3466-9&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 978-1-4799-3466-9]. — DOI:10.1109/HASE.2014.34.
  5. Chia-Chun Wu , Shang-Juh Kao, Wen-Chung Kuo, Min-Shiang Hwang. Reversible Secret Image Sharing Based on Shamir's Scheme (англ.) // IIH-MSP '09 Proceedings of the 2009 Fifth International Conference on Intelligent Information Hiding and Multimedia Signal Processing : Proceeding. — Washington, DC, USA: IEEE Computer Society, 2009. — P. 1014—1017. — ISBN 978-0-7695-3762-7. — DOI:10.1109/IIH-MSP.2009.158.
  6. M. Ulutas, G. Ulutas, V. Nabiyev Medical image security and EPR hiding using Shamir's secret sharing scheme (англ.) // Journal of Systems and Software : Journal. — New York, NY, USA: Elsevier Science Inc., 2011. — Vol. 84, no. 3. — P. 341—353. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=0164-1212&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0164-1212]. — DOI:10.1016/j.jss.2010.11.928.
  7. S. Salim, S. Suresh, R. Gokul, Reshma S. Application of Shamir Secret Sharing Scheme for Secret Data Hiding and Authentication (англ.) // International Journal of Advanced Research in Computer Science & Technology : Journal. — 2014. — Vol. 2, no. 2. — P. 220—224. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=2347-8446&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 2347-8446].
  8. Che-Wei Lee, Wen-Hsiang Tsai. A data hiding method based on information sharing via PNG images for applications of color image authentication and metadata embedding (англ.) // Signal Processing : Journal. — Amsterdam, The Netherlands: Elsevier North-Holland, Inc., 2013. — Vol. 93, no. 7. — P. 2010—2025. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=0165-1684&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0165-1684]. — DOI:10.1016/j.sigpro.2013.01.009.
  9. Louis Goubin, Ange Martinelli. Protecting AES with Shamir's secret sharing scheme (англ.) // CHES'11 Proceedings of the 13th international conference on Cryptographic hardware and embedded systems : Proceeding. — Springer-Verlag Berlin, 2011. — P. 79—94. — ISBN 978-3-642-23950-2.
  10. Shangqin Xiao, Hefei Ling, Fuhao Zou, Zhengding Lu. Secret Sharing Based Video Watermark Algorithm for Multiuser (англ.) // Digital Watermarking : Book. — Springer-Verlag Berlin, 2009. — P. 303—312. — ISBN 978-3-642-04437-3. — DOI:10.1007/978-3-642-04438-0_26.
  11. A. Teoh, D. Ngo, A. Goh. Personalised cryptographic key generation based on FaceHashing (англ.) // Computers and Security : Journal. — Elsevier Advanced Technology Publications Oxford, 2004. — Vol. 23, no. 7. — P. 606—614. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=0167-4048&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0167-4048]. — DOI:10.1016/j.cose.2004.06.002.

Литература

  • Шнайер Б. 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. — Vol. 22, fasc. 11. — P. 612 — 613. — ISSN [www.sigla.ru/table.jsp?f=8&t=3&v0=0001-0782&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0001-0782]. — DOI:10.1145/359168.359176.
  • Чмора А.Л. Современная прикладная криптография. — 2-е изд., стер.. — М.: Гелиос АРВ, 2002. — С. 123—124. — 256 с. — ISBN 5-85438-046-3.
  • Под общ. ред. Ященко В.В. Введение в криптографию. — 2-е изд., испр.. — М.: МЦНМО: «ЧеРо», 1999. — С. 118—125. — 272 с. — ISBN 5-900916-40-5.

Отрывок, характеризующий Схема разделения секрета Шамира

– Да, – продолжал Пьер с улыбкой, – и этот молодой человек теперь себя так держит, что, где есть богатые невесты, – там и он. Я как по книге читаю в нем. Он теперь в нерешительности, кого ему атаковать: вас или mademoiselle Жюли Карагин. Il est tres assidu aupres d'elle. [Он очень к ней внимателен.]
– Он ездит к ним?
– Да, очень часто. И знаете вы новую манеру ухаживать? – с веселой улыбкой сказал Пьер, видимо находясь в том веселом духе добродушной насмешки, за который он так часто в дневнике упрекал себя.
– Нет, – сказала княжна Марья.
– Теперь чтобы понравиться московским девицам – il faut etre melancolique. Et il est tres melancolique aupres de m lle Карагин, [надо быть меланхоличным. И он очень меланхоличен с m elle Карагин,] – сказал Пьер.
– Vraiment? [Право?] – сказала княжна Марья, глядя в доброе лицо Пьера и не переставая думать о своем горе. – «Мне бы легче было, думала она, ежели бы я решилась поверить кому нибудь всё, что я чувствую. И я бы желала именно Пьеру сказать всё. Он так добр и благороден. Мне бы легче стало. Он мне подал бы совет!»
– Пошли бы вы за него замуж? – спросил Пьер.
– Ах, Боже мой, граф, есть такие минуты, что я пошла бы за всякого, – вдруг неожиданно для самой себя, со слезами в голосе, сказала княжна Марья. – Ах, как тяжело бывает любить человека близкого и чувствовать, что… ничего (продолжала она дрожащим голосом), не можешь для него сделать кроме горя, когда знаешь, что не можешь этого переменить. Тогда одно – уйти, а куда мне уйти?…
– Что вы, что с вами, княжна?
Но княжна, не договорив, заплакала.
– Я не знаю, что со мной нынче. Не слушайте меня, забудьте, что я вам сказала.
Вся веселость Пьера исчезла. Он озабоченно расспрашивал княжну, просил ее высказать всё, поверить ему свое горе; но она только повторила, что просит его забыть то, что она сказала, что она не помнит, что она сказала, и что у нее нет горя, кроме того, которое он знает – горя о том, что женитьба князя Андрея угрожает поссорить отца с сыном.
– Слышали ли вы про Ростовых? – спросила она, чтобы переменить разговор. – Мне говорили, что они скоро будут. Andre я тоже жду каждый день. Я бы желала, чтоб они увиделись здесь.
– А как он смотрит теперь на это дело? – спросил Пьер, под он разумея старого князя. Княжна Марья покачала головой.
– Но что же делать? До года остается только несколько месяцев. И это не может быть. Я бы только желала избавить брата от первых минут. Я желала бы, чтобы они скорее приехали. Я надеюсь сойтись с нею. Вы их давно знаете, – сказала княжна Марья, – скажите мне, положа руку на сердце, всю истинную правду, что это за девушка и как вы находите ее? Но всю правду; потому что, вы понимаете, Андрей так много рискует, делая это против воли отца, что я бы желала знать…
Неясный инстинкт сказал Пьеру, что в этих оговорках и повторяемых просьбах сказать всю правду, выражалось недоброжелательство княжны Марьи к своей будущей невестке, что ей хотелось, чтобы Пьер не одобрил выбора князя Андрея; но Пьер сказал то, что он скорее чувствовал, чем думал.
– Я не знаю, как отвечать на ваш вопрос, – сказал он, покраснев, сам не зная от чего. – Я решительно не знаю, что это за девушка; я никак не могу анализировать ее. Она обворожительна. А отчего, я не знаю: вот всё, что можно про нее сказать. – Княжна Марья вздохнула и выражение ее лица сказало: «Да, я этого ожидала и боялась».
– Умна она? – спросила княжна Марья. Пьер задумался.
– Я думаю нет, – сказал он, – а впрочем да. Она не удостоивает быть умной… Да нет, она обворожительна, и больше ничего. – Княжна Марья опять неодобрительно покачала головой.
– Ах, я так желаю любить ее! Вы ей это скажите, ежели увидите ее прежде меня.
– Я слышал, что они на днях будут, – сказал Пьер.
Княжна Марья сообщила Пьеру свой план о том, как она, только что приедут Ростовы, сблизится с будущей невесткой и постарается приучить к ней старого князя.


Женитьба на богатой невесте в Петербурге не удалась Борису и он с этой же целью приехал в Москву. В Москве Борис находился в нерешительности между двумя самыми богатыми невестами – Жюли и княжной Марьей. Хотя княжна Марья, несмотря на свою некрасивость, и казалась ему привлекательнее Жюли, ему почему то неловко было ухаживать за Болконской. В последнее свое свиданье с ней, в именины старого князя, на все его попытки заговорить с ней о чувствах, она отвечала ему невпопад и очевидно не слушала его.
Жюли, напротив, хотя и особенным, одной ей свойственным способом, но охотно принимала его ухаживанье.
Жюли было 27 лет. После смерти своих братьев, она стала очень богата. Она была теперь совершенно некрасива; но думала, что она не только так же хороша, но еще гораздо больше привлекательна, чем была прежде. В этом заблуждении поддерживало ее то, что во первых она стала очень богатой невестой, а во вторых то, что чем старее она становилась, тем она была безопаснее для мужчин, тем свободнее было мужчинам обращаться с нею и, не принимая на себя никаких обязательств, пользоваться ее ужинами, вечерами и оживленным обществом, собиравшимся у нее. Мужчина, который десять лет назад побоялся бы ездить каждый день в дом, где была 17 ти летняя барышня, чтобы не компрометировать ее и не связать себя, теперь ездил к ней смело каждый день и обращался с ней не как с барышней невестой, а как с знакомой, не имеющей пола.
Дом Карагиных был в эту зиму в Москве самым приятным и гостеприимным домом. Кроме званых вечеров и обедов, каждый день у Карагиных собиралось большое общество, в особенности мужчин, ужинающих в 12 м часу ночи и засиживающихся до 3 го часу. Не было бала, гулянья, театра, который бы пропускала Жюли. Туалеты ее были всегда самые модные. Но, несмотря на это, Жюли казалась разочарована во всем, говорила всякому, что она не верит ни в дружбу, ни в любовь, ни в какие радости жизни, и ожидает успокоения только там . Она усвоила себе тон девушки, понесшей великое разочарованье, девушки, как будто потерявшей любимого человека или жестоко обманутой им. Хотя ничего подобного с ней не случилось, на нее смотрели, как на такую, и сама она даже верила, что она много пострадала в жизни. Эта меланхолия, не мешавшая ей веселиться, не мешала бывавшим у нее молодым людям приятно проводить время. Каждый гость, приезжая к ним, отдавал свой долг меланхолическому настроению хозяйки и потом занимался и светскими разговорами, и танцами, и умственными играми, и турнирами буриме, которые были в моде у Карагиных. Только некоторые молодые люди, в числе которых был и Борис, более углублялись в меланхолическое настроение Жюли, и с этими молодыми людьми она имела более продолжительные и уединенные разговоры о тщете всего мирского, и им открывала свои альбомы, исписанные грустными изображениями, изречениями и стихами.
Жюли была особенно ласкова к Борису: жалела о его раннем разочаровании в жизни, предлагала ему те утешения дружбы, которые она могла предложить, сама так много пострадав в жизни, и открыла ему свой альбом. Борис нарисовал ей в альбом два дерева и написал: Arbres rustiques, vos sombres rameaux secouent sur moi les tenebres et la melancolie. [Сельские деревья, ваши темные сучья стряхивают на меня мрак и меланхолию.]
В другом месте он нарисовал гробницу и написал:
«La mort est secourable et la mort est tranquille
«Ah! contre les douleurs il n'y a pas d'autre asile».
[Смерть спасительна и смерть спокойна;
О! против страданий нет другого убежища.]
Жюли сказала, что это прелестно.
– II y a quelque chose de si ravissant dans le sourire de la melancolie, [Есть что то бесконечно обворожительное в улыбке меланхолии,] – сказала она Борису слово в слово выписанное это место из книги.
– C'est un rayon de lumiere dans l'ombre, une nuance entre la douleur et le desespoir, qui montre la consolation possible. [Это луч света в тени, оттенок между печалью и отчаянием, который указывает на возможность утешения.] – На это Борис написал ей стихи:
«Aliment de poison d'une ame trop sensible,
«Toi, sans qui le bonheur me serait impossible,
«Tendre melancolie, ah, viens me consoler,
«Viens calmer les tourments de ma sombre retraite
«Et mele une douceur secrete
«A ces pleurs, que je sens couler».
[Ядовитая пища слишком чувствительной души,
Ты, без которой счастье было бы для меня невозможно,
Нежная меланхолия, о, приди, меня утешить,
Приди, утиши муки моего мрачного уединения
И присоедини тайную сладость
К этим слезам, которых я чувствую течение.]
Жюли играла Борису нa арфе самые печальные ноктюрны. Борис читал ей вслух Бедную Лизу и не раз прерывал чтение от волнения, захватывающего его дыханье. Встречаясь в большом обществе, Жюли и Борис смотрели друг на друга как на единственных людей в мире равнодушных, понимавших один другого.
Анна Михайловна, часто ездившая к Карагиным, составляя партию матери, между тем наводила верные справки о том, что отдавалось за Жюли (отдавались оба пензенские именья и нижегородские леса). Анна Михайловна, с преданностью воле провидения и умилением, смотрела на утонченную печаль, которая связывала ее сына с богатой Жюли.
– Toujours charmante et melancolique, cette chere Julieie, [Она все так же прелестна и меланхолична, эта милая Жюли.] – говорила она дочери. – Борис говорит, что он отдыхает душой в вашем доме. Он так много понес разочарований и так чувствителен, – говорила она матери.
– Ах, мой друг, как я привязалась к Жюли последнее время, – говорила она сыну, – не могу тебе описать! Да и кто может не любить ее? Это такое неземное существо! Ах, Борис, Борис! – Она замолкала на минуту. – И как мне жалко ее maman, – продолжала она, – нынче она показывала мне отчеты и письма из Пензы (у них огромное имение) и она бедная всё сама одна: ее так обманывают!
Борис чуть заметно улыбался, слушая мать. Он кротко смеялся над ее простодушной хитростью, но выслушивал и иногда выспрашивал ее внимательно о пензенских и нижегородских имениях.
Жюли уже давно ожидала предложенья от своего меланхолического обожателя и готова была принять его; но какое то тайное чувство отвращения к ней, к ее страстному желанию выйти замуж, к ее ненатуральности, и чувство ужаса перед отречением от возможности настоящей любви еще останавливало Бориса. Срок его отпуска уже кончался. Целые дни и каждый божий день он проводил у Карагиных, и каждый день, рассуждая сам с собою, Борис говорил себе, что он завтра сделает предложение. Но в присутствии Жюли, глядя на ее красное лицо и подбородок, почти всегда осыпанный пудрой, на ее влажные глаза и на выражение лица, изъявлявшего всегдашнюю готовность из меланхолии тотчас же перейти к неестественному восторгу супружеского счастия, Борис не мог произнести решительного слова: несмотря на то, что он уже давно в воображении своем считал себя обладателем пензенских и нижегородских имений и распределял употребление с них доходов. Жюли видела нерешительность Бориса и иногда ей приходила мысль, что она противна ему; но тотчас же женское самообольщение представляло ей утешение, и она говорила себе, что он застенчив только от любви. Меланхолия ее однако начинала переходить в раздражительность, и не задолго перед отъездом Бориса, она предприняла решительный план. В то самое время как кончался срок отпуска Бориса, в Москве и, само собой разумеется, в гостиной Карагиных, появился Анатоль Курагин, и Жюли, неожиданно оставив меланхолию, стала очень весела и внимательна к Курагину.
– Mon cher, – сказала Анна Михайловна сыну, – je sais de bonne source que le Prince Basile envoie son fils a Moscou pour lui faire epouser Julieie. [Мой милый, я знаю из верных источников, что князь Василий присылает своего сына в Москву, для того чтобы женить его на Жюли.] Я так люблю Жюли, что мне жалко бы было ее. Как ты думаешь, мой друг? – сказала Анна Михайловна.
Мысль остаться в дураках и даром потерять весь этот месяц тяжелой меланхолической службы при Жюли и видеть все расписанные уже и употребленные как следует в его воображении доходы с пензенских имений в руках другого – в особенности в руках глупого Анатоля, оскорбляла Бориса. Он поехал к Карагиным с твердым намерением сделать предложение. Жюли встретила его с веселым и беззаботным видом, небрежно рассказывала о том, как ей весело было на вчерашнем бале, и спрашивала, когда он едет. Несмотря на то, что Борис приехал с намерением говорить о своей любви и потому намеревался быть нежным, он раздражительно начал говорить о женском непостоянстве: о том, как женщины легко могут переходить от грусти к радости и что у них расположение духа зависит только от того, кто за ними ухаживает. Жюли оскорбилась и сказала, что это правда, что для женщины нужно разнообразие, что всё одно и то же надоест каждому.