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

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

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

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

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

Пусть имеется группа из ${\displaystyle t}$ человек и сообщение ${\displaystyle s}$ длины ${\displaystyle n}$ , состоящее из двоичных символов. Если подобрать случайным образом такие двоичные сообщения ${\displaystyle s_{1},\ldots ,s_{t}}$ , что в сумме они будут равняться ${\displaystyle s}$ , и распределить эти сообщения между всеми членами группы, получится, что прочесть сообщение будет возможно только в случае, если все члены группы соберутся вместе .

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

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

В отличие от процедуры разбиения секрета, где ${\displaystyle t=n}$ , в процедуре разделения секрета количество долей, которые нужны для восстановления секрета, может отличаться от того, на сколько долей секрет разделён. Такая схема носит названия пороговой схемы ${\displaystyle \left(t,n\right)}$ , где ${\displaystyle n}$ — количество долей, на которые был разделён секрет, а ${\displaystyle t}$ — количество долей, которые нужны для восстановления секрета. Идеи схем ${\displaystyle t\neq n}$ были независимо предложены в 1979 году Ади Шамиром и Джорджем Блэкли . Кроме этого, подобные процедуры исследовались Гусом Симмонсом .

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

Схема Шамира

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

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

Кратко данный алгоритм можно описать следующим образом. Пусть дано конечное поле ${\displaystyle G}$ . Зафиксируем ${\displaystyle n}$ различных ненулевых несекретных элементов данного поля. Каждый из этих элементов приписывается определённому члену группы. Далее выбирается произвольный набор из ${\displaystyle t}$ элементов поля ${\displaystyle G}$ , из которых составляется многочлен ${\displaystyle f(x)}$ над полем ${\displaystyle G}$ степени ${\displaystyle t-1,1<t\leq n}$ . После получения многочлена вычисляем его значение в несекретных точках и сообщаем полученные результаты соответствующим членам группы .

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

Важным достоинством схемы Шамира является то, что она легко масштабируема . Чтобы увеличить число пользователей в группе, необходимо лишь добавить соответствующее число несекретных элементов к уже существующим, при этом должно выполняться условие ${\displaystyle r_{i}\neq r_{j}}$ при ${\displaystyle i\neq j}$ . В то же время, компрометация одной части секрета переводит схему из ${\displaystyle (n,t)}$ -пороговой в ${\displaystyle (n-1,t-1)}$ -пороговую.

Схема Блэкли

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

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

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

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

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

Пусть количество пользователей в группе равно ${\displaystyle n}$ . В схеме Миньотта выбирается некоторое множество попарно взаимно простых чисел ${\displaystyle \{m_{1},m_{2},...,m_{n}\}}$ таких, что произведение ${\displaystyle k-1}$ наибольших чисел меньше, чем произведение ${\displaystyle k}$ наименьших из этих чисел. Пусть эти произведения равны ${\displaystyle M}$ и ${\displaystyle N}$ , соответственно. Число ${\displaystyle k}$ называется порогом для конструируемой схемы по множеству ${\displaystyle \{m_{1},m_{2},...,m_{n}\}}$ . В качестве секрета выбирается число ${\displaystyle S}$ такое, для которого выполняется соотношение ${\displaystyle M<S<N}$ . Части секрета распределяются между участниками группы следующим образом: каждому участнику выдается пара чисел ${\displaystyle (r_{i},m_{i})}$ , где ${\displaystyle r_{i}\equiv S{\pmod {m_{i}}}}$ .

Чтобы восстановить секрет, необходимо объединить ${\displaystyle t\geq k}$ фрагментов. В этом случае получим систему сравнений вида ${\displaystyle x\equiv r_{i}{\pmod {m_{i}}}}$ , множество решений которой можно найти, используя китайскую теорему об остатках . Секретное число ${\displaystyle S}$ принадлежит этому множеству и удовлетворяет условию ${\displaystyle S<m_{1}\cdot m_{2}\cdot ...\cdot m_{t}}$ . Также несложно показать, что если число фрагментов меньше ${\displaystyle k}$ , то, чтобы найти секрет ${\displaystyle S}$ , необходимо перебрать порядка ${\displaystyle {\frac {N}{M}}}$ целых чисел. При правильном выборе чисел ${\displaystyle m_{i}}$ такой перебор практически невозможно реализовать. К примеру, если разрядность ${\displaystyle m_{i}}$ будет от 129 до 130 бит, а ${\displaystyle k<15}$ , то соотношение ${\displaystyle {\frac {N}{M}}}$ будет иметь порядок ${\displaystyle 2^{100}}$ .

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

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

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

В рамках данной схемы выбираются ${\displaystyle n+1}$ ${\displaystyle m}$ -мерных векторов ${\displaystyle V_{0},V_{1},...,V_{n}}$ так, чтобы любая матрица размером ${\displaystyle m\times m}$ , составленная из этих векторов, имела ранг ${\displaystyle m}$ . Пусть вектор ${\displaystyle U}$ имеет размерность ${\displaystyle m}$ .

Секретом в схеме является матричное произведение ${\displaystyle U^{T}V_{0}}$ . Долями секрета являются произведения ${\displaystyle U^{T}V_{i},1\leq i\leq n}$ .

Имея любые ${\displaystyle m}$ долей, можно составить систему линейных уравнений размерности ${\displaystyle m\times m}$ , неизвестными в которой являются коэффициенты ${\displaystyle U}$ . Решив данную систему, можно найти ${\displaystyle U}$ , а имея ${\displaystyle U}$ , можно найти секрет. При этом система уравнений не имеет решения в случае, если долей меньше, чем ${\displaystyle m}$ .

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

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

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

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

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

См. также

• Проверяемое разделение секрета
• Схемы разделения секрета для произвольных структур доступа

Примечания

Литература

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

• Blakley G. R. (англ.) // — Montvale: , 1979. — P. 313—317. —
• Shamir A. (англ.) // Communications of the ACM — New York City: Association for Computing Machinery , 1979. — Vol. 22, Iss. 11. — P. 612—613. — ISSN —
• (англ.) // : Proceedings of the Workshop on Cryptography Burg Feuerstein, Germany, March 29–April 2, 1982 / — Berlin, Heidelberg, New York City, London: , 1983. — P. 371—375. — ( ; Vol. 149) — ISBN 978-3-540-11993-7 — ISSN ; —
• , (англ.) // / — IEEE , 1983. — Vol. 29, Iss. 2. — P. 208—210. — ISSN ; —
• , , Hellman M. E. (англ.) // / — IEEE , 1983. — Vol. 29, Iss. 1. — P. 35—41. — ISSN ; —
• Блэкли Д. , // — 1997. — Т. 33, вып. 3. — С. 102—110.
• (англ.) // : 19th Annual International Cryptology Conference Santa Barbara, California, USA, August 15–19, 1999 Proceedings / — , 1999. — P. 148—164. — ISBN 978-3-540-66347-8 —
• , , , : Учебное пособие — 2-е изд., испр. и доп. — М. : , 2002. — ISBN 978-5-85438-137-6
• , — СПб. : , 2005. — 288 с. — ( учебное пособие ) — ISBN 978-5-94157-563-3
• , , (англ.) // — 2010. — Vol. 9, Iss. 2. — P. 107—117. — ISSN ;
• // : материалы международного научного конгресса 31 окт. — Минск: БГУ , 2011. — Т. 1. Статьи факультета прикладной математики и информатики. — С. 169—173. — ISBN 978-985-518-563-6