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

Разделение секрета (англ. 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. Алферов, Зубов, Кузьмин и др., 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. Blakley, 1979.
  5. 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. Шнайер, 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.