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

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

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

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

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

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

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


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

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

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


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


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

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

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

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


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

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

На этом этапе мы можем генерировать фрагменты, подключив $n$ уникальных целых чисел в $f(x) = 42 + 3x + 5x^2$, где $x \neq 0$ (потому что это наш секрет). В данном примере мы хотим раздать четыре фрагмента с порогом три, поэтому случайным образом генерируем точки $(18, 1716), (27, 3768), (31, 4940), (35, 6272)$ и отправляем по одной точке каждому из четырёх доверенных человек, хранителей ключа. Мы также сообщаем людям, что $k = 3$, так как это считается публичной информацией и необходимо для восстановления $S$.

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


Мы уже обсуждали концепцию полиномиальной интерполяции и то, что она лежит в основе пороговой схемы Шамира $(k,n)$. Когда любые три из четырёх доверенных лиц хотят восстановить $S$, им нужно только интерполировать $f(0)$ со своими уникальными точками. Для этого они могут определить свои точки $(x_1,y_1),…,(x_k,y_k) = (18, 1716), (27, 3768), (31, 4940)$ и рассчитать интерполяционный полином Лагранжа, используя следующую формулу. Если программирование вам понятнее, чем математика, то пи — это по сути оператор 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}$


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

$\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}$


Поскольку мы знаем, что $S = P(0)$, восстановление $S$ осуществляется просто:

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


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


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

Чтобы продемонстрировать, насколько слаба схема с целочисленной арифметикой, рассмотрим сценарий, в котором злоумышленник получил две точки $(18, 1716), (27,3768)$ и знает публичную информацию, что $k = 3$. Из этой информации он может вывести $f(x)$, равный двум, и подключить в формулу известные значения $x$ и $f(x)$.

$\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}$


Затем злоумышленник может найти $a_1$, посчитав $f(27) - f(18)$:

$\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}$ как случайно выбранные целые положительные числа, есть ограниченное число возможных $a_2$. С помощью этой информации злоумышленник может вывести $a_2 \in [1,2,3,4,5]$, поскольку всё, что больше 5, сделает $a_1$ отрицательным. Это оказывается правдой, поскольку мы определили $a_2 = 5$

Затем злоумышленник может рассчитать возможные значения $S$, заменив $a_1$ в $f(18)$:

$\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}$


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

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


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

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

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

Используя этот новый пример, предположим, что злоумышленник узнал две из этих новых точек, $(18, 37), (27, 45)$, а публичная информация $k = 3, p = 73$. На этот раз атакующий на основе всей имеющейся у него информации выводит следующие функции, где $\mathbb{N}$ — набор всех положительных целых чисел, а $q_x$ представляет коэффициент модуля $f’(x)$.

$\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}$


Теперь наш злоумышленник снова находит $a_1$, вычислив $f’(27) - f’(18)$:

$\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}$


Затем он снова пытается вывести $S$, заменив $a_1$ в $f’(18)$:

$\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}$


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

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


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

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

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

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

Демо


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

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 24

    +10
    Огромное спасибо за статью, я врубился:) Пишите еще на тему криптографии, очень интересно. Именно то, какие возможности в принципе предоставляет современная криптография, какие задачи решает а какие нет.
      +16

      Можно добавить только, что Ади Шамир — S из RSA.

        +2
        А в каких библиотеках есть реализация?
          +1

          Про 42 отсылка понятна. А вот откуда взялось 73?

            0
            случайное простое число?
              +1
              Любимое число Шелдона Купера.
                0

                Спасибо, не знал.

              0
              А нам точно нужно морочиться с полиномами и тд? есть же RAID 5 (к=n-1), масштабируемый до RAID 6 (к=n-2) и большего числа теряемых блоков на контроле четности. Берем полный секретный ключ длины M, «пишем» его в нужное количество блоков длины M/k*n и раздаём каждому по кусочку. Насколько я понимаю, до сбора порогового числа блоков «рейдовая» схема не даёт никакой информации о оставшихся блоках.
                +5

                Вы не поверите, но RAID5/6 — это частный случай erasure coding, для произвольных порогов существуют схемы типа кодов Рида-Соломона-Коши, и сводятся они к составлению и решению системы линейных уравнений в конечных полях, т.е. в сущности то же решение, только чуть по другому сформулированное

                  0
                  Да я помню про Рида-Соломона, но как-то отложилось, что там биты контрольные должны в нужных местах стоять. Ну и рассыпаны они там по всему сообщению, а в рейде как раз на куски равного размера нарезка. Ровно то, что нужно в исходной задаче.

                  Просто, согласно вике, код Рида — Соломона был изобретён в 1960 году. Зачем после этого схема Шамира в 1979 — не ясно.
                  (ладно еще законы Бойля — Мариотта, Шарля и Гей-Люссака — общее уравнение вывели последним. Но тут частный случай описанный позже имеет фамилию)
                  Рейды ладно, позже похоже появились. Хотя я думал что они ровесники магнитным накопителям, но похоже ошибся.
                    +4
                    В схеме Шамира знание N-1 частей никак не облегчит подбор секрета (при условии что для восстановления секрета нужно N частей), и это строго доказано. А вот для кодов Рида-Соломона, насколько я знаю, таких гарантий нет.
                      +3

                      Если верить этой статье, то схема Шамира на самом деле и есть частный случай кодов Рида-Соломона, так что вполне возможно, что Шамир просто разработал свою схему независимо. Правда, как написал выше mrsantak он еще и строго доказал, что в его схеме знание N-1 из N частей не облегчает подбор секрета, а Рид и Соломон вроде не заморачивались на эту тему, так что научная новизна в его работе точно есть. Кстати, в той же статье есть и идеи как сделать схему Шамира более устойчивой к ситуациям когда кто-то подсовывает заведомо неверные куски, либо уменьшить амплификацию данных при разделении секрета ценой уменьшения секьюрности. Более подробно это разжевано здесь (там как раз вопрос был чем же отличаются коды Рида-Соломона от схемы Шамира с точки зрения безопасности)

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

                  С тех пор что-то поменялось?
                    +1
                    Ничего не поменялось. В этом случае вам нужно зашифровать приватный ключ с помощью симметричного шифрования (например AES-256-CTR) и уже симметричный ключ делить.
                      0
                      А ещё лучше просто использовать PKCS#8 и разделить пароль от ключа
                        0
                        А, вот на это меня не хватило.

                        А в чём проблема использовать Шамира для больших данных? Например, секрет размером в 1Мб, чанк в 128кб. Я не думаю, что современные компьютеры взорвутся от решения уравнений с 128кб числами.
                          +1
                          Тем, что это непрактично и небыстро. Всегда найдётся какой-то секрет, который будет длиннее имеющихся возможностей по подсчёту. Раздувая числа, которыми придётся оперировать, ёмкость растёт незначительно по меркам возможных потребностей, а затраты линейно.

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

                          Поэтому блочные шифры каскадируются разными режимами, типа CBC, CTR и так далее; криптоподпись оперирует хэшом от изначального сообщения, а шифрование зашифровывает симметричный ключ, либо подписывает параметры DH.
                            0
                            И всё-таки я не понимаю. Ну вот у нас «цифры» по 1Мб каждая. В чём проблемы работать с числами такого размера?

                            В вот только что сделал число в питоне в 1454113 знаков (десятчных). Я его поделил на 17, это заняло примерно пол-секунды (без привлечения numpy). Если программа будет 30-40с тупить над решением уравнений никого это не смутит. Мне кажется, ограничения в этом месте весьма искуственные и не cpu/memory bound.
                              +1
                              Проблемы нет. Но и нужды нет.
                              Если программа будет 30-40с тупить над решением уравнений никого это не смутит. Мне кажется, ограничения в этом месте весьма искуственные и не cpu/memory bound.
                              Это «никого» — очень смелое обобщение. Если для обработки всего полутора мегабайт секретных данных нужны десятки секунд, то как раз этот предел по CPU уже осязаем.

                              Вообще этот вопрос аналогичен вопросу: «почему бы не использовать RSA с огромными ключами для прямого шифрования сообщения целиком?». Как и тут — можно, но не нужно.
                                0
                                Технически, есть смысл использовать RSA напрямую как one time pad, лишь с тем уточнением, что лично я не знаю никого, кто бы всерьёз использовал его так. Теоретически, такое использование улучшает достаточно устойчивую шифросистему до абсолютно устойчивой. Ценой производительности, конечно. к тому же есть сомнения насчёт устойчивости источника случайных простых чисел.
                                  0
                                  Она не будет абсолютно устойчивой, так как здесь наиболее сомнительное звено это RSA. Да и для одноразовых шифроблокнотов RSA здесь абсолютно лишний.
                                    0
                                    Да, очевидно RSA здесь слабое звено. Вместо RSA можно использовать куда более устойчивые декодирования общих линейных кодов (МакЭлис).

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

                                    И да, эта криптосистема не является абсолютно юзабельной.

                    Only users with full accounts can post comments. Log in, please.