m1rko Nov 28 2018 at 17:20

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

7 min

52K

Algorithms*Information Security*Cryptography*Mathematics*

Translation

Рассмотрим сценарий, когда необходимо обеспечить безопасность банковского хранилища. Оно считается абсолютно неприступным без ключа, который вам выдают в первый же день работы. Ваша цель — надёжно сохранить ключ.

Предположим, вы решили всё время хранить ключ при себе, предоставляя доступ к хранилищу по мере необходимости. Но вы быстро поймёте, что такое решение на практике нормально не масштабируется, потому что всякий раз для открытия хранилища требуется ваше физическое присутствие. А как насчёт отпуска, которые вам обещали? Кроме того ещё более пугает вопрос: а что если вы потеряли единственный ключ?

С мыслью об отпуске вы решили сделать копию ключа и доверить её другому сотруднику. Однако вы понимаете, что это тоже не идеально. Удваивая количество ключей, вы также удвоили возможности кражи ключа.

Отчаявшись, вы уничтожаете дубликат и решаете разделить исходный ключ пополам. Теперь, вы думаете, два доверенных человека с фрагментами ключей должны физически присутствовать, чтобы собрать ключ и открыть хранилище. Это означает, что вору необходимо украсть два фрагмента, что вдвое труднее кражи одного ключа. Однако вскоре вы понимаете, что эта схема ненамного лучше, чем просто один ключ, потому что если кто-то потеряет половину ключа, полный ключ нельзя восстановить.

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

Как разделить секрет

О таком типе схемы управления ключами думал Ади Шамир в 1979 году, когда опубликовал свою работу «Как разделить секрет». В статье кратко объясняется так называемая $inline$ пороговая схема для эффективного разделения секретного значения (например, криптографического ключа) на $inline$ частей. Затем, когда и только когда хотя бы $inline$ из $inline$ частей собраны, можно легко восстановить секрет $inline$ .

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

Полиномиальная интерполяция

Пороговая схема Шамира $inline$ построена вокруг концепции полиномиальной интерполяции. Если вы не знакомы с этой концепцией, она на самом деле довольно простая. Вообще, если вы когда-нибудь рисовали точки на графике, а затем соединяли их линиями или кривыми, то уже использовали её!

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

Рассмотрим полином со степенью один, $inline$ . Если вы хотите построить эту функцию на графике, сколько точек вам нужно? Ну, мы знаем, что это линейная функция, которая образует линию и поэтому нужно по крайней мере две точки. Далее рассмотрим полиномиальную функцию со степенью два, $inline$ . Это квадратичная функция, поэтому для построения графика требуется не менее трёх точек. Как насчёт многочлена со степенью три? По крайней мере, четыре точки. И так далее и тому подобное.

Действительно классная вещь в этом свойстве заключается в том, что, учитывая степень полиномиальной функции и, по крайней мере, $inline$ точек, мы можем вывести дополнительные точки для этой полиномиальной функции. Экстраполяцию этих дополнительных точек мы называем полиномиальной интерполяцией.

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

Возможно, вы уже поняли, что здесь вступает в игру умная схема Шамира. Предположим, что наш секрет $inline$ — это $inline$ . Мы можем превратить $inline$ в точку на графике $inline$ и придумать полиномиальную функцию со степенью $inline$ , которая удовлетворяет этой точке. Напомним, что $inline$ будет нашим порогом требуемых фрагментов, поэтому если мы установить порог в три фрагмента, то должны выбрать полиномиальную функцию со степенью два.

Наш полином будет иметь форму $f(x) = a_0+a_1x+a_2x^2+a_3x^3+…+a_{k-1}x^{k-1}$ , где $inline$ и $a_1,…,a_{k-1}$ — случайным образом выбранные положительные целые числа. Мы всего лишь строим полином со степенью $inline$ , где свободный коэффициент $inline$ — это наш секрет $inline$ , а у каждого из последующих $inline$ членов есть случайным образом выбранный положительный коэффициент. Если вернуться к первоначальному примеру и предположить, что $S = 42, k = 3, a_1,…,a_{k-1} = [3,5]$ , то тогда мы получим функцию $inline$ .

На этом этапе мы можем генерировать фрагменты, подключив $inline$ уникальных целых чисел в $inline$ , где $x \neq 0$ (потому что это наш секрет). В данном примере мы хотим раздать четыре фрагмента с порогом три, поэтому случайным образом генерируем точки $inline$ и отправляем по одной точке каждому из четырёх доверенных человек, хранителей ключа. Мы также сообщаем людям, что $inline$ , так как это считается публичной информацией и необходимо для восстановления $inline$ .

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

Мы уже обсуждали концепцию полиномиальной интерполяции и то, что она лежит в основе пороговой схемы Шамира $inline$ . Когда любые три из четырёх доверенных лиц хотят восстановить $inline$ , им нужно только интерполировать $inline$ со своими уникальными точками. Для этого они могут определить свои точки $inline$ и рассчитать интерполяционный полином Лагранжа, используя следующую формулу. Если программирование вам понятнее, чем математика, то пи — это по сути оператор for, который умножает все результаты, а сигма — это for, который всё складывает.

$P(x) = \sum_{j=1}^{k} p_j(x)$

$P_j(x) = y_j \prod_{\scriptstyle m=1\atop\scriptstyle m\neq j}^{k}\frac{x-x_m}{x_j-x_m}$

При $inline$ мы можем это решить следующим образом и вернуть нашу исходную полиномиальную функцию:

$\begin{aligned} P(x) &= {y_1}\left({x-x_2 \over x_1-x_2}\cdot{x-x_3 \over x_1-x_3}\right) + {y_2}\left({x-x_1 \over x_2-x_1}\cdot{x-\_3 \over x_2-x_3}\right) + {y_3}\left({x-x_1 \over x_3-x_1}\cdot{x-x_2 \over x_3-x_2}\right) \\ P(x) &= {1716}\left({x-27 \over 18-27}\cdot{x-31 \over 18-31}\right) + {3768}\left({x-18 \over 27-18}\cdot{x-31 \over 27-31}\right) + {4940}\left({x-18 \over 31-18}\cdot{x-27 \over 31-27}\right) \\ P(x) &= 42 + 3x + 5x^2 \end{aligned}$

Поскольку мы знаем, что $inline$ , восстановление $inline$ осуществляется просто:

$\begin{aligned} P(0) &= 42 + 3(0) + 5(0)^2 \\ P(0) &= 42 \end{aligned}$

Использование небезопасной целочисленной арифметики

Хотя мы успешно применили основную идею Шамира $inline$ , у нас остаётся проблема, которую мы игнорировали до настоящего момента. Наша полиномиальная функция использует небезопасную целочисленную арифметику. Учтите, что для каждой дополнительной точки, которую атакующий получает на графике нашей функции, остаётся меньшее количество возможностей для других точек. Вы можете увидеть это своими глазами, когда строите график с увеличением количества точек для полиномиальной функции с использованием целочисленной арифметики. Это контрпродуктивно для нашей заявленной цели безопасности, потому что злоумышленник не должен абсолютно ничего узнать, пока у них не будет хотя бы $inline$ фрагментов.

Чтобы продемонстрировать, насколько слаба схема с целочисленной арифметикой, рассмотрим сценарий, в котором злоумышленник получил две точки $inline$ и знает публичную информацию, что $inline$ . Из этой информации он может вывести $inline$ , равный двум, и подключить в формулу известные значения $inline$ и $inline$ .

$\begin{aligned}f(x) &= a_0 + a_1x + a_2x^2 + a_3x^3 + … + a_{k-1}x^{k-1} \\ f(x) &= S + a_1x + a_2x^2 \\ f(18) \equiv 1716 &= S + a_118 + a_218^2 \\ f(27) \equiv 3768 &= S + a_127 + a_227^2\end{aligned}$

Затем злоумышленник может найти $inline$ , посчитав $inline$ :

$\begin{aligned}3768 - 1716 &= (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) \\ 2052 &= 9a_1 + 405a_2 \\ 9a_1 &= 2052 - 405a_2 \\ a_1 &= \frac{2052 - 405a_2}{9} \\ a_1 &= 228 - 45a_2\end{aligned}$

Поскольку мы определили $a_1,…,a_{k-1}$ как случайно выбранные целые положительные числа, есть ограниченное число возможных $inline$ . С помощью этой информации злоумышленник может вывести $a_2 \in [1,2,3,4,5]$ , поскольку всё, что больше 5, сделает $inline$ отрицательным. Это оказывается правдой, поскольку мы определили $inline$

Затем злоумышленник может рассчитать возможные значения $inline$ , заменив $inline$ в $inline$ :

$\begin{aligned}1716 &= S + a_118 + a_218^2 \\ 1716 &= S + 18\left(228 - 45a_2\right) + a_218^2 \\ 1716 - S &= 18\left(228 - 45a_2\right) + a_218^2 \\ -S &= 18\left(228 - 45a_2\right) + a_218^2 - 1716 \\ -S &= 4104 - 810a_2 + a_218^2 - 1716 \\ S &= -4104 + 810a_2 - a_218^2 + 1716 \\ S &= 810a_2 - 324a_2 -2388 \\ S &= 486a_2 - 2388\end{aligned}$

С ограниченным набором вариантов для $inline$ становится понятно, насколько легко подобрать и проверить значения $inline$ . Здесь всего пять вариантов.

Решение проблемы с небезопасной целочисленной арифметикой

Чтобы устранить эту уязвимость, Шамир предлагает использовать модульную арифметику, заменив $inline$ на $f(x) \mod p$ , где $p \in \mathbb{P} : p > S, p > n$ и $\mathbb{P}$ — множество всех простых чисел.

Быстро вспомним, как работает модульная арифметика. Часы со стрелками — уже знакомая концепция. Она использует часы, которые являются $\mod 12$ . Как только часовая стрелка проходит мимо двенадцати, она возвращается к одному. Интересным свойством этой системы является то, что просто посмотрев на часы, мы не можем вывести, сколько оборотов сделала часовая стрелка. Однако если мы знаем, что часовая стрелка четыре раза миновала 12, можно полностью определить количество прошедших часов с помощью простой формулы $inline$ , где $inline$ — это наш делитель (здесь $inline$ ), $inline$ — это коэффициент (сколько раз делитель без остатка переходит в исходное число, здесь $inline$ ), а $inline$ — это остаток, который обычно и возвращает вызов оператора по модулю (здесь $inline$ ). Знание всех этих значений позволяет нам решить уравнение для $inline$ , но если мы пропустим коэффициент, то никогда не сможем восстановить исходное значение.

Можно продемонстрировать, как это улучшает безопасность нашей схемы, применив схему к нашему предыдущему примеру и используя $inline$ . Наша новая полиномиальная функция $f’(x) = 42 + 3x + 5x^2 \mod 73$ , а новые точки $inline$ . Теперь хранители ключа могут ещё раз использовать полиномиальную интерполяцию для восстановления нашей функции, только на этот раз операции сложения и умножения должны сопровождаться сокращением по модулю $inline$ (e.g. $48 + 93 \mod 73 = 68$ ).

Используя этот новый пример, предположим, что злоумышленник узнал две из этих новых точек, $inline$ , а публичная информация $inline$ . На этот раз атакующий на основе всей имеющейся у него информации выводит следующие функции, где $\mathbb{N}$ — набор всех положительных целых чисел, а $inline$ представляет коэффициент модуля $inline$ .

$\begin{aligned} f’(x) &= S + a_1x + a_2x^2 \mod 73 \\ f’(x) &= S + a_1x + a_2x^2 - 73q_x : q_x \in \mathbb{N} \\ f’(18) \equiv 37 &= S + a_118 + a_218^2 - 73q_{18} \\ f’(27) \equiv 45 &= S + a_127 + a_227^2 - 73q_{27}\end{aligned}$

Теперь наш злоумышленник снова находит $inline$ , вычислив $inline$ :

$\begin{aligned}45 - 37 &= (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) + (-73q_{27} - (-73q_{18})) \\ 8 &= 9a_1 + 405a_2 + 73(q_{18} - q_{27}) \\ -9a_1 &= -8 + 405a_2 + 73(q_{18} - q_{27}) \\ 9a_1 &= 8 - 405a_2 - 73(q_{18} - q_{27}) \\ a_1 &= \frac{8 - 405a_2 - 73(q_{18} - q_{27})}{9} \\ a_1 &= \frac{8}{9} - 45a_2 - \frac{73}{9} (q_{18} - q_{27}) \end{aligned}$

Затем он снова пытается вывести $inline$ , заменив $inline$ в $inline$ :

$\begin{aligned}37 &= S + 18\left(\frac{8}{9} - 45a_2 - \frac{73}{9} (q_{18} - q_{27})\right) + a_218^2 - 73q_{18} \\ -S &= 18\left(\frac{8}{9} - 45a_2 - \frac{73}{9} (q_{18} - q_{27})\right) + a_218^2 - 73q_{18} - 37 \\ S &= -18\left(\frac{8}{9} - 45a_2 - \frac{73}{9} (q_{18} - q_{27})\right) - 324a_2 + 73q_{18} + 37 \\ S &= 486a_2 + 21 + 219q_{18} - 146q_{27}\end{aligned}$

На этот раз у него серьёзная проблема. В формуле отсутствуют значения $inline$ , $q_{18}$ и $q_{27}$ . Поскольку существует бесконечное количество комбинаций этих переменных, он не может получить никакой дополнительной информации.

Соображения безопасности

Схема разделения секрета Шамира предлагает безопасность с точки зрения теории информации. Это значит, что математика является стойкой даже против злоумышленника с неограниченной вычислительной мощностью. Однако схема по-прежнему содержит несколько известных проблем.

Например, схема Шамира не создаёт проверяемых фрагментов, то есть люди могут свободно предъявлять поддельные фрагменты и мешать восстановлению правильного секрета. Враждебный хранитель фрагментов с достаточной информацией может даже произвести другой фрагмент, изменив $inline$ на своё усмотрение. Эта проблема решается с помощью проверяемых схем разделения секрета, таких как схема Фельдмана.

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

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

Демо

На этой странице есть интерактивная демонстрация cхема разделения секрета Шамира. Демонстрация сделана на базе библиотеки ssss-js, которая сама по себе является JavaScript-портом популярной программы ssss. Обратите внимание, что вычисление больших значений $inline$ , $inline$ и $inline$ может занять некоторое время.

Tags:

Hubs: