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

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

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

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

В отличие от процедуры разбиения секрета, в процедуре разделения секрета количество долей, которые нужны для восстановления секрета, может отличаться от того, на сколько долей мы разделили секрет. Такая схема носит названия пороговой схемы $\left( t, n \right)$, где $n$ — количество долей, на которые был разделён секрет, а $t$ — количество долей, которые нужны для восстановления секрета.

В тривиальном случае $t=n$ мы получаем схему разбиения секрета.

Идеи схем $t \neq n$ были независимо предложены в 1979 году Ади Шамиром^[1] и Джорджем Блэкли (англ. George Robert (Bob) Blakley Jr.)^[2]. Кроме этого подобные процедуры исследовались Гусом Симмонсом.^[3]

Схема Шамира

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

Основная статья: Схема разделения секрета Шамира

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

Если мы хотим разделить секрет таким образом, чтобы восстановить его могли только $k$ человек, мы «прячем» его в формулу $(k-1)$-мерного многочлена. Восстановить этот многочлен можно по $k$ точкам. Количество же различных точек многочлена не ограничено (на практике оно ограничивается размером числового поля, в котором ведутся расчёты).

Схема Блэкли

Основная статья: Векторная схема разделения секрета

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

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

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

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

Основные статьи: Схема Миньотта, Схема Асмута — Блума

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

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

Основная статья: Схема Карнина — Грина — Хеллмана

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

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

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

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

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

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

Примечания

1. ↑ Adi Shamir How to share a secret (англ.) // Communications of the ACM. — New York, NY, USA: ACM, 1979. — В. 11. — Т. 22. — С. 612 — 613. — ISSN 0001-0782. — DOI:10.1145/359168.359176
2. ↑ G. R. Blakley Safeguarding cryptographic keys (англ.) // Proceedings of the 1979 AFIPS National Computer Conference. — Monval, NJ, USA: AFIPS Press, 1979. — С. 313—317. — DOI:10.1109/AFIPS.1979.98
3. ↑ C. J. Simmons An introduction to shared secret and/or shared control schemes and their application (англ.) // Contemporary Cryptology. — IEEE Press, 1991. — С. 441—497.
4. ↑ M. Mignotte How to Share a Secret (англ.) // Lecture Notes in Computer Science. — 1983. — Т. 149. — С. 371—375. — DOI:10.1007/3-540-39466-4_27
5. ↑ C. Asmuth, J. Bloom A modular approach to key safeguarding // Information Theory, IEEE Transactions on. — 1983. — В. 2. — Т. 29. — ISSN 0018-9448.
6. ↑ Karnin, E., Greene, J., Hellman, M. On secret sharing systems (англ.) // Information Theory, IEEE Transactions on. — 1983. — В. 1. — Т. 29. — С. 35—41. — ISSN 0018-9448. — DOI:10.1109/TIT.1983.1056621

Литература

• Шнайер Б. 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