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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поскольку мы знаем, что Схема разделения секрета Шамира, восстановление Схема разделения секрета Шамира осуществляется просто:

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

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

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

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

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

Затем злоумышленник может найти Схема разделения секрета Шамира, посчитав Схема разделения секрета Шамира:

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

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

Затем злоумышленник может рассчитать возможные значения Схема разделения секрета Шамира, заменив Схема разделения секрета Шамира в Схема разделения секрета Шамира:

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

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

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

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

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

Можно продемонстрировать, как это улучшает безопасность нашей схемы, применив схему к нашему предыдущему примеру и используя Схема разделения секрета Шамира. Наша новая полиномиальная функция Схема разделения секрета Шамира, а новые точки Схема разделения секрета Шамира. Теперь хранители ключа могут ещё раз использовать полиномиальную интерполяцию для восстановления нашей функции, только на этот раз операции сложения и умножения должны сопровождаться сокращением по модулю Схема разделения секрета Шамира (e.g. Схема разделения секрета Шамира).

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

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

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

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

Затем он снова пытается вывести Схема разделения секрета Шамира, заменив Схема разделения секрета Шамира в Схема разделения секрета Шамира:

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

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

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

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

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

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

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

Демо

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

Источник: habr.com

Добавить комментарий