Разделение секрета с использованием СОК

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

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

Можно выделить множество путей обеспечения конфиденциальности помимо схем разделения секрета, например, шифрование данных. Однако стандарты асинхронного шифрования сегодня требуют больших вычислительных ресурсов. Так требуемый размер модулей для поддержки высокого уровня безопасности схемы шифрования RSA равен 4096 бит. СРС в свою очередь могут быть адаптированы для решения задач различного спектра задач, таких как безопасное хранение данных, безопасная передача в компьютерных сетях и так далее. А в случае использования Системы остаточных классов в качестве основы для построения СРС можно добиться высокой вычислительной эффективности, как было показано в предыдущих статьях.

Что такое СРС лучше всего разобрать на конкретных примерах. Наиболее известными являются схемы Шамира и Блэкли, которые в 1979 году одновременно предложили концепцию пороговых схем разделения секрета. Хорошим инструментом для реализации СРС является система остаточных классов, разряды в которой могут быть расценены как доли секрета благодаря своей непозиционности. К таким СРС относятся классические схемы Асмута-Блума и Миньотта. Далее рассмотрим некоторые конкретные схемы разделения секрета.

Схема Шамира

Данная схема [1] основывается на использовании интерполяционных многочленов Лагранжа и является самой используемой схемой разделения секрета в криптографии. Основная ее идея заключается в использовании алгебраических свойств интерполяционных многочленов для разделения и восстановления секрета. Под интерполяцией понимается приближение некоторой функции другой на основе данных лишь о ее значениях в некоторых заданных точках. Если мы пытаемся приблизить некоторый многочлен степени t-1 другим многочленом (классическим способом для достижения этого является метод Лагранжа), то для точного восстановления степень, выбираемая для интерполяционного многочлена, должна равняться исходной степени t-1. Иными словами, невозможно точно восстановить многочлен степени t-1 используя методы интерполяции, если известно меньше чем t точек.

Итак, в соответствии с введенной Шамиром терминологией, пороговой схемой разделения секрета (t,n) с порогом t называется такой метод распределения секрета на доли (shares) между n "участниками", при котором восстановить секрета можно объединив как минимум t произвольных его долей. Под участниками здесь можно понимать различные объекты от реальных людей до различных облачных хранилищ и тому подобного. В такой интерпретации необходим так называемый "дилер" - сторона, которая считается в криптографической терминологии абсолютно "честной" и которой доверена организация процесса разделения секрета на части между участниками.

Пусть необходимо разделить секрет S с использованием (t,n)-пороговой схемы Шамира. Первым шагом выбирается некоторое простое число p>S, которое задает конечное поле, над которым будут происходить вычисления. Над этим полем строится многочлен степени t-1:

P(x)=(a_{t-1}x^{t-1}+a_{t-2}x^{t-2}+ ... +a_{1}x+S)\mod{p},

в котором S - это разделяемый секрет, коэффициенты a_{1},a_{2},...,a_{t-1} - случайные числа. Для генерации доли участника с номером i рассчитывается значение многочлена в точке i (или в любой другой ассоциированной с ним точке, принадлежащей конечному полю, определяемому числом p, и уникальным образом его идентифицирующей). Иными словами, каждому участнику раздается значение k_{i}=P(i) для i=1,2,...,n. После чего построенный многочлен "забывается".

Секрет таким образом оказывается "спрятанным" среди коэффициентов многочлена P(x) над полем, определяемым числом p. Чтобы восстановить значение секрета необходимо собрать вместе ровно t долей секрета и воспользоваться одним из методов интерполяции (в поле целых чисел для этого хорошо годиться метод Лагранжа). Узнав, как выглядит многочлен, мы можем вычислить секрет S=P(0).

Схемы на СОК

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

В свою очередь, безопасные схемы разделения секрета с использованием СОК строить достаточно непросто. В первую очередь необходимо обеспечить криптографическую безопасность. Рассмотрим в качестве примера известную схему Асмута-Блума [2], основанную на СОК. Для начала необходимо особым образом построить систему оснований m_0, m_1, m_2, ..., m_t, m_{t+1}, ..., m_n. Она должна удовлетворять следующим условиям:

  • m_{i+1} > m_iдля любого 0\le i \le n
  • \prod_{i=1}^{t} m_i > m_0 \prod_{i=0}^{t-2} m_{n-i}

Пусть, как и ранее, S есть некоторый секрет. В схеме Асмута-Блума секрет выбирается из \mathbb{Z}_{m_0}, а это значит, что 0\leqslant S < m_0. По условиям схемы, генерируется некоторое число r, такое, что

S' = S + rm_0 < \prod_{i=1}^{t} m_i

Далее каждому участнику схемы с номером i=1,2,...,n раздается значение k_{i}=S'\mod{m_{i}}. При этом для восстановления секрета достаточно объединить вместе t его частей: согласно построенной схеме, собранные данные будут представлять собой число в СОК, восстановление которого было обговорено ранее.

Еще проще схема Миньотта. Пусть у нас есть СОК с основаниями m_1 < m_2 < ... < m_n и выполняется условие:

 \alpha =\prod_{i=1}^{t} m_i > \prod_{i=0}^{k-2} m_i = \beta

Секрет S выбирается из промежутка \left ( \alpha, \beta \right ). Каждому участнику раздаются доли k_i=S \mod{m_i}. Восстановление происходит таким же образом, как и для предыдущей СРС.

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

Сравнение различных подходов

 

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

Если говорить о втором направлении, то здесь все достаточно прозрачно. В теории СРС можно выделить три основных процесса - генерация параметров схемы, разделение секрета и его восстановление. Чем проще алгоритмы, реализующие эти процессы, чем они быстродейственнее, тем лучше. Естественно в современных условиях необходимо учитывать и параллелизм операций. Поэтому схемы разделения секрета на СОК - серьезный конкурент классическим схемам.

При рассмотрении первого направления необходимо ответить на вопрос: насколько сложно восстановить секрет, не имея достаточного количества его частей. Предположим, что мы объединили произвольную неразрешенную коалицию участников. Если вероятность восстановить секрет в таком случае будет всегда равна вероятности восстановить секрет при полном отсутствии долей секрета, то данная схема считается совершенной. Схема Шамира совершенна, а схема Асмута-Блума в свою очередь нет. Как показали недавние исследования [3], о схемах на СОК в принципе нельзя говорить в терминах абсолютной совершенности. Было введено новое понятие для СРС - асимптотическая совершенность, которое в полной мере отражает свойства схем на СОК. Пространства, в которых определяется секрет и его части, неоднородны и имеют различные размеры. Столь же неоднородны и вероятности восстановления в разных случаях. Поэтому, как доказано в [3], асимптотически совершенная СРС Асмута-Блума вполне безопасна для практического использования. В свою очередь, СРС Миньотта таким свойством не обладает.

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

Литература

  1. A. Shamir. How to share a secret // Communications of the ACM. New York, NY, USA: ACM, 1979. В. 11. Т. 22. P. 612-613.
  2. C. A. Asmuth and J. Bloom. A Modular Approach to Key Safeguarding. IEEE Transactions on Information Theory, 29(2):208–210, Mar. 1983.
  3. M. Quisquater, B. Preneel, and J. Vandewalle. On the Security of the Threshold Scheme Based on the Chinese Remainder Theorem. In D. Naccache and P. Paillier, editors, Public Key Cryptography, volume 2274 of Lecture Notes in Computer Science, pages 199–210. Springer, 2002.

Leave a Reply