Оценка эффективности схем разделения секрета28.12.2023 18:45

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

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

Предметная область исследования

Разберем на примере принцип работы схем разделения секрета. У нас есть информация, некий пароль: Ch8a_hf90n — секрет. Мы разделим его между 3 людьми: первый знает символы »Ch8» и позицию 1, второй »90n», позиция 3, третий »a_hf», позиция 2. Восстановить исходный пароль носители секрета смогут, только собравшись вместе. Данный подход является самым базовым и неприменим в реальной жизни по ряду причин, которые сводятся к низкому уровню безопасности.[2]

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

совершенность (обеспечивает конфиденциальность)
идеальность (обеспечивает конфиденциальность)
ресурсоемкость (эффективность по памяти)
сложность алгоритма (эффективность по мощности)

Дадим определения данным критериям.

Схема разделения секрета является совершенной, если любое количество нелегитимных пользователей не может извлечь никакой информации о секрете [3].
Схема разделения секрета называется идеальной, если размер доли секрета равен размеру самого секрета [4].
Ресурсоемкость означает затраты ресурсов памяти при вычислении этапа разделения и восстановления секрета.
Сложность алгоритма — это оценка по О-нотации сложности алгоритма вычисления этапов разделения и восстановления секрета. В качестве элементарной операции рассматривается эквивалентные для всех схем действия, которые выполняются за , это может быть в одном случае умножение чисел, в другом векторов, но все равно операция выполняется как элементарная. В итоге сложность зависит от количества легитимных абонентов и долей, на которые делится секрет .

В данной работе мы оценим и сравним эффективность самых распространенных схем разделения секрета (СРС), алгоритмы которых основаны на различных принципах:

СРС Блэкли
СРС Шамира
СРС Карнина — Грина — Хеллмана
СРС, основанная на эллиптической кривой
СРС Асмута — Блума

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

Эту СРС также называют пороговой, она основана на концепции полиномиальной интерполяции [5]. Пусть — минимальное число легитимных абонентов, необходимых для восстановления секрета; — число долей, на которые делится секрет. Секрет необходимо разделить так, чтобы его могли восстановить не менее абонентов — для этого используется многочлен степени k-1 , он восстанавливается однозначно не менее чем по точкам [6].

Приведем алгоритм разделения секрета:

Выбирается случайное простое число . Проверка простоты числа является ресурсоемкой и сложность зависит от алгоритма, лучшие результаты способен показать ряд алгоритмов, например Тест Бейли-Померанца-Селфриджа-Уогстаффа, оценка сложности проверки простоты числа составляет [7]. Не будем учитывать этот этап в наших оценках, так как он обязателен для всех расматриваемых схем.
Требуется построить полином степени в поле простого модуля кольца целых чисел . Сложность составляет .
Части секрета для каждого из абонентов вычисляются как значение построенного полинома в одной из точек. Получаем вложенный цикл из итераций в каждом из подходов. После разделения секрета каждый пользователь получит четыре значения: номер частичного секрета , его значение , размерность поля , степень многочлена . Сложность данного шага $O(k\cdot n)$ .
Осталось раздать участникам их доли секрета — это займет .

Общая сложность вычислений составляет $O(k\cdot n)$ .

Для восстановления секрета строится интерполяционный полином Лагранжа, сложность O(k^2) . Общая оценка сложности составляет $O(k\cdot n)+O(k^2)$ .

Оценим ресурсоемкость вычислений. Пусть — длина секрета в байтах, long double занимает 8 байт. Значение доли секрета k_i имеет тот же размер, что и секрет. Тогда для обработки и хранения долей секрета понадобится оперативная память в размере $k\cdot M$ . Для хранения коэффициентов полинома требуется столько же памяти, потому что используется один тип данных. Следовательно, при k=32=n , M=8 потребуется $328\cdot 2=512$ байт памяти. Оперативную память, затраченную на сам цикл не будем учитывать, так как ее размер зависит от компилятора и одинаков для всех схем разделения секрета.

Осталось рассмотреть совершенность и идеальность схемы Шамира.

Размер секрета равен размеру доли: для хранения секрета требуется определенный тип данных, вещественные числа, для хранения доли секрета необходим тот же тип данных. Из этого следует идеальность СРС. Процесс восстановления секрета можно приблизить решением системы из уравнений с неизвестными, если количество легитимных абонентов будет меньше , то система будет иметь бесконечное число решений и ни одно из них нельзя будет отвергнуть как невозможное [8]. Схема Шамира совершенна.

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

Данная схема также называется векторной СРС, она работает на использовании точек многомерного пространства [9]. Рассмотрим любые две (или больше) некомпланарных плоскостей, они пересекаются в пространстве и секретом является одна из координат точки пересечения. Мы берем именно одну координату для кодирования секрета, иначе по двум можно будет построить гиперплоскость и получить некоторое представление о целом секрете. Долями секрета будут являться плоскости, пересекающиеся в искомой точке.

Разделение секрета:

Первым шагом является проверка случайного числа p на простоту, сложность [2]. Данный шаг выполняется в каждом алгоритме, при равных и используются простые числа одного порядка, поэтому мы можем исключить этот шаг из сравнения, оценив сложность таким способом.
Подобно схеме Шамира, выбираем чисел, сложность .
Требуется раздать каждому из участников плоскость в пространстве размерности (на сколько частей делим секрет), потребуется чисел для задания каждой плоскости. Следовательно, сложность $O(k\cdot n)$ .
За доли секрета раздаются участникам.

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

Для получения исходного секрета требуется решить систему уравнений, например методом Крамера, так как секретом является первая координата точки, полученной в результате решения. [10] Требуется вычислить два определителя матриц размерности $k\times k$ по методу Гаусса сложность составит O(k^3) .

Общая сложность вычислений составляет $O(n\cdot k)+O(k^3)$ .

Ресурсоемкость вычислений:

Уравнение плоскости задается с помощью коэффициентов. Следовательно, $k\cdot n$ для уравнений плоскостей. При восстановлении потребуется вычислить определитель матрицы размером $k \times k$ , и при n=k получим то же число. Тогда для разделения/восстановления потребуется $k\cdot k \cdot M$ оперативной памяти, где M=8 байт. При n=k=32 потребуется Кбайт памяти.

Размер каждой доли секрета превышает размер секрета в раз, значит схема не идеальна. Но она является совершенной, потому что при решении системы из n-1 уравнений будет получена гиперплоскость, которая дает бесконечное количество вариантов значений секрета

Схема разделения секрета, основанная на эллиптической кривой

Рассмотрим алгоритм разделения секрета из [8] и оценим его сложность:

Выбирается эллиптическая кривая с количеством точек не менее . Каждому из участников СРС, ставится в соответствие точка на эллиптической кривой, включая бесконечно удаленную.
Через точки задается многочлен степени на этой кривой вида: $S=P_0+tP_1+t^2P_2+...+t^{k-1}P_{k-1}$
Некоторое значение на эллиптической кривой известно всем.
подставляется в многочлен — вычисляется значение секрета.
Чтобы раздать каждому участнику свою долю секрета, подставляются номера участников как в многочлен, получается доля секрета для каждого. В результате каждый участник имеет точку на эллиптической кривой и свою долю секрета .

Общая сложность разделения оценивается как $O(k\cdot n)$ .

Оценка процесса восстановления секрета:

Требуется восстановить коэффициенты выбранного многочлена, для восстановления секрета необходимо человек. Каждый из них знает некоторый коэффициент многочлена и его значение для своего порядкового номера. Для восстановления секрета необходимо провести рекуррентный итерационный процесс, его сложность оценивается как O(k^2) .

Ресурсоемкость вычислений:

Для хранения точек потребуется $2\cdot 8 байт \cdot n = 512$ байт ( n=32 ). При разделении и восстановлении секрета потребуется $n\cdot M=256$ байт. Суммарно получим 768 байт. Но алгоритм восстановления является рекурсивным, это означает, что потребуютcя большие затраты памяти на создание фреймов при работе функции. Точную оценку провести невозможно без конкретного компилятора и реализованного алгоритма, но это значение обычно измеряется в Мб, запишем для нашего сравнения Мб.

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

Схема разделения секрета Карнина — Грина — Хеллмана

Для разделения секрета между различными сторонами так, чтобы минимум сторон могли его восстановить, выбирается n+1 векторов $\vec{vt}$ размерности , так чтобы ранг любой матрицы, составленной из данных векторов, был равен [8]. Вектор $\vec{v_0}$ известен всем участникам. Секретом является скалярное произведение $(\vec{u},\vec{v_0})$ , долями — скалярные произведения $(\vec{u},\vec{v_i})$ , и векторы $\vec{v_i}$ . Сложность этапа разделения оценивается как O(n) .

Для восстановления секрета по известным долям (и набору векторов)
решается система из уравнений для нахождения вектора $\vec{u}$ .
Сложность оценивается как O(k^3) (аналогично методу Крамера).

Оценим ресурсоемкость. Секрет представляется в виде произведения двух векторов, объем оперативной памяти для хранения координат векторов равен $k\cdot (k+1) \cdot M=32\cdot 33\cdot 8 = 8,3$ Кбайта. При n=32 для хранения скалярных произведений потребуется еще $32\cdot 8 = 256$ байт. Для восстановления требуется решить систему линейных уравнений методом Крамера, считается k+1 определителей матриц $k \times k$ . Будет затрачено $32\cdot 32 \cdot (32+1) \cdot 8 = 8,3$ Кбайта. Суммарно оценим как Кбайт.

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

Схема разделения секрета Асмута — Блума

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

Анализ сложности вычислений:

Выбирается простое число .
Выбирается взаимно простых чисел , больших , и удовлетворяющих условиям Асмута–Блума.
Выбирается случайное число , такое, что
$\sqrt[k]{M`} < d_i << \sqrt[k-1]{M`}, i = \overline{1..n}$ , где .
Вычисляются доли и раздаются участникам.

Сложность оценивается как O(n).

Восстановление секрета происходит при помощи китайской теоремы об остатках, сложность составляет O(k^2) .

Ресурсоемкость вычислений начинаем оценивать с того, что простое число занимает в памяти байт, общий объем $n\cdot 8 = 256$ байт. Для проверки условий Асмута–Блума требуется $2\cdot k \cdot d_i$ памяти, примерно 12,8 Кбайт. Это довольно много и общая оценка ресурсоемкости составит Кбайт.

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

Обсуждение результатов и выводы

В исследовании были рассмотрены 5 пороговых схем разделения секрета, оценены такие параметры, как сложность алгоритма разделения и восстановления, ресурсоемкость и безопасность, как совершенность и идеальность схемы.

Представим полученные результаты в виде таблицы и сравним схемы:

По ресурсоемкости выигрывают схемы Шамира и Карнина — Грина — Хеллмана, а по сложности алгоритма наиболее быстрой является схема Асмута — Блума, также она обладает идеальностью. Еще схема Шамира идеальна, при этом ее сложность ненамного отстает от Асмута — Блума: при $n \sim k$ они обе оцениваются как O(n^2) , но схема Шамира выигрывает по ресурсоемкости.

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

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

Список источников

Positive Research. Актуальные киберугрозы: II квартал 2018 года // Positive Research Center. — 10.09.2018.
Анализ криптографических схем разделения секрета для резервного хранения ключевой информации / З.А. Носиров, О.В. Щербинина // Прикаспийский журнал: управление и высокие технологии, 2019
Парватов Н.Г. Совершенные схемы разделения секрета / Н.Г. Парватов // Прикладная дискретная математика. — 2008. — № 2 (2). — C. 41–47.
Шенец Н.Н. Об идеальных модулярных схемах разделения секрета в кольцах многочленов от нескольких переменных / Н.Н. Шенец. — 2011
Червяков Н.И. Новый метод порогового разделения секрета, основанный на системе остаточных классов / Н.И. Червяков, М.А. Дерябин // Информационные технологии. — 2016. — Т. 22, № 3. — С. 211–219.
Алексейчук А.Н. Совершенные схемы разделения секрета и конечные универсальные алгебры / А.Н. Алексейчук // Анализ и обработка данных. — 2005.
Мельман В.С. Методы анализа тестов простоты числа / В.С. Мельман, Ю.В. Шабля, Д.В. Кручинин // Электронные средства и системы управления. — 2016. — № 1–2. — С. 54–55.
Лавриненко А.Н. Некоторые элементы концепции активной безопасности в современной криптографии / А.Н. Лавриненко, Н.И. Червяков // Научные ведомости Белгородского государственного университета. Серия: Экономика. Информатика. — 2014. — Т. 30, № 8–1 (179)
Blakley G.R. Safeguarding cryptographic keys / G.R. Blakley // Proceedings of the national computer conference. — 1979. — Vol. 48. — P. 313–317
Пьянов С.М. Сравнительный анализ стойкости некоторых классов схем разделения секрета / С.М. Пьянов // Магистерская диссертация по программе «Математическое и программное обеспечение защиты информации». — Москва : МГУ им. Ломоносова, 2013. — 67 с
Виноградова А.А. Системы разделения секрета. // Выпускная квалификационная работа по направлению «Математическое обеспечение и администрирование информационных систем», Санкт-Петербургский государственный университет, 2017, — 13 с