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

Каждая доля секрета — это плоскость, а секрет представляет собой точку пересечения трёх плоскостей. Две доли секрета позволяют получить линию, на которой лежит секретная точка

Разделение секрета (англ. secret sharing) — термин в криптографии, под которым понимают любой из способов распределения секрета среди группы участников, каждому из которых достаётся «персональная доля». Секрет может воссоздать только коалиция участников из первоначальной группы, причём входить в эту коалицию должно не менее некоторого изначально известного числа (порогового значения) участников.

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

Существующие схемы имеют две составляющие: разделение и восстановление секрета. К разделению относится формирование частей секрета и распределение их между членами группы, что позволяет разделить ответственность за секрет между её участниками. Обратная схема должна обеспечить его восстановление при условии доступности его хранителей в некотором необходимом количестве[1].

Пример использования: протокол тайного голосования на основе разделения секрета[2].

Простейший пример схемы разделения секрета

Пусть имеется группа из человек и сообщение длины , состоящее из двоичных символов. Если подобрать случайным образом такие двоичные сообщения , что в сумме они будут равняться , и распределить эти сообщения между всеми членами группы, получится, что прочесть сообщение будет возможно только в случае, если все члены группы соберутся вместе[1].

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

Пороговая схема

В отличие от процедуры разбиения секрета, где , в процедуре разделения секрета количество долей, которые нужны для восстановления секрета, может отличаться от того, на сколько долей секрет разделён. Такая схема носит название пороговой схемы , где  — количество долей, на которые был разделён секрет, а  — количество долей, которые нужны для восстановления секрета. Идеи схем были независимо предложены в 1979 году Ади Шамиром и Джорджем Блэкли. Кроме этого, подобные процедуры исследовались Гусом Симмонсом[3][4][5].

Если коалиция участников такова, что они имеют достаточное количество долей для восстановления секрета, то коалиция называется разрешённой. Схемы разделения секрета, в которых разрешённые коалиции участников могут однозначно восстановить секрет, а неразрешённые не получают никакой апостериорной информации о возможном значении секрета, называются совершенными[6].

Схема Шамира

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

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

Для того, чтобы после разделения секрет могли восстановить только участников, его «прячут» в формулу многочлена степени над конечным полем . Для однозначного восстановления этого многочлена необходимо знать его значения в точках, причем, используя меньшее число точек, однозначно восстановить исходный многочлен не получится. Количество же различных точек многочлена не ограничено (на практике оно ограничивается размером числового поля , в котором ведутся расчёты).

Кратко данный алгоритм можно описать следующим образом. Пусть дано конечное поле . Зафиксируем различных ненулевых известных элементов данного поля. Каждый из этих элементов приписывается определённому члену группы. Далее выбирается произвольный набор из элементов поля , из которых составляется многочлен над полем степени . После получения многочлена вычисляем его значение в несекретных точках и сообщаем полученные результаты соответствующим членам группы[1].

Чтобы восстановить секрет, можно воспользоваться интерполяционной формулой, например формулой Лагранжа.

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

Схема Блэкли

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

Одна доля Две доли — пересекаются вдоль плоскости Три доли — пересекаются в точке
Схема Блэкли в трёх измерениях: каждая доля секрета — это плоскость, а секрет — это одна из координат точки пересечения плоскостей. Двух плоскостей недостаточно для определения точки пересечения, но достаточно для получения дополнительной информации об этой точке.

С помощью схемы Блэкли[4] можно создать (t, n)-схему разделения секрета для любых t и n: для этого надо использовать размерность пространства, равную t, и каждому из n игроков дать одну гиперплоскость, проходящую через секретную точку. Тогда любые t из n гиперплоскостей будут однозначно пересекаться в секретной точке.

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

Схемы, основанные на китайской теореме об остатках

В 1983 году Морис Миньотт[англ.], Асмут и Блум предложили две схемы разделения секрета, основанные на китайской теореме об остатках. Для некоторого числа (в схеме Миньотта это сам секрет, в схеме Асмута — Блума — некоторое производное число) вычисляются остатки от деления на последовательность чисел, которые раздаются сторонам. Благодаря ограничениям на последовательность чисел, восстановить секрет может только определённое число сторон[7][8].

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

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

Схема Асмута — Блума является доработанной схемой Миньотта. В отличие от схемы Миньотта, её можно построить в таком виде, чтобы она была совершенной[10].

Схемы, основанные на решении систем уравнений

В 1983 году Карнин, Грин и Хеллман предложили свою схему разделения секрета, которая основывалась на невозможности решить систему с неизвестными, имея менее уравнений[11].

В рамках данной схемы выбираются -мерных векторов так, чтобы любая матрица размером , составленная из этих векторов, имела ранг . Пусть вектор имеет размерность .

Секретом в схеме является матричное произведение . Долями секрета являются произведения .

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

Способы обмана пороговой схемы

Существуют несколько способов нарушить протокол работы пороговой схемы:

  • владелец одной из долей может помешать восстановлению общего секрета, отдав в нужный момент неверную (случайную) долю[13].
  • злоумышленник, не имея доли, может присутствовать при восстановлении секрета. Дождавшись оглашения нужного (порогового) числа долей, он быстро восстанавливает секрет самостоятельно и генерирует ещё одну долю, после чего предъявляет её остальным участникам. В результате он получает доступ к секрету и остаётся непойманным[14]. Имея секрет в моменте, злоумышленник может распорядиться им сразу, либо подождать достаточное для отвода подозрений количество времени и использовать секрет позднее.

Также существуют другие возможные нарушения работы, не связанные с особенностями реализации схемы:

  • злоумышленник может сымитировать ситуацию, при которой необходимо раскрытие секрета, тем самым выведав доли всех участников или их части[14].

См. также

Примечания

  1. 1 2 3 Алферов, Зубов, Кузьмин и др., 2002, с. 401.
  2. Schoenmakers, 1999.
  3. C. J. Simmons. An introduction to shared secret and/or shared control schemes and their application (англ.) // Contemporary Cryptology. — IEEE Press, 1991. — P. 441—497.
  4. 1 2 Blakley, 1979.
  5. 1 2 Shamir, 1979.
  6. Блэкли, Кабатянский, 1997.
  7. Mignotte, 1982.
  8. Asmuth, Bloom, 1983.
  9. Молдовян, Молдовян, 2005, с. 225.
  10. Шенец, 2011.
  11. Karnin, Greene, Hellman, 1983.
  12. Шнайер Б. Прикладная криптография. — 2-е изд. — Триумф, 2002. — С. 590. — 816 с. — ISBN 5-89392-055-4.
  13. Pasailă, Alexa, Iftene, 2010.
  14. 1 2 Шнайер, 2002, с. 69.

Литература

  • Шнайер Б. 3.7. Разделение секрета // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 93—96. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
  • Шнайер Б. 23.2 Алгоритмы разделения секрета // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 588—591. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.