Передача секрета с использованием китайской теоремы об остатках

Совместное использование секрета заключается в восстановлении секрета $S$ из набора общих ресурсов, каждый из которых содержит частичную информацию о секрете. Китайская теорема об остатках (CRT) утверждает, что для данной системы одновременных уравнений сравнения решение единственно в некотором $Z / n Z$ , при этом $n > 0$ при некоторых подходящих условиях на сравнения. Таким образом, при совместном использовании секрета можно использовать CRT для получения долей, представленных в уравнениях сравнения, а секрет можно восстановить, решив систему сравнений, чтобы получить уникальное решение, которое и будет секретом для восстановления.

Схемы обмена секретами: несколько типов

Существует несколько типов схем обмена секретами . Самыми основными типами являются так называемые пороговые схемы, где имеет значение только мощность набора долей. Другими словами, при наличии секрета $S$ и $n$ долей любой набор из $t$ долей представляет собой набор с наименьшей мощностью , из которого секрет может быть восстановлен, в том смысле, что любого набора из $t - 1$ долей недостаточно, чтобы дать $S$ . Это известно как структура порогового доступа . Мы называем такие схемы $(t, n)$ пороговыми схемами разделения секрета или $t$ -out- $n$ схемой .

Схемы порогового разделения секрета отличаются друг от друга методом генерации долей, начиная с определенного секрета. Первые из них — это пороговая схема разделения секрета Шамира , которая основана на полиномиальной интерполяции с целью найти $S$ из заданного набора долей, и геометрическая схема разделения секрета Джорджа Блейкли секрета $S.$ , которая использует геометрические методы для восстановления порогового Схемы разделения секрета , основанные на CRT, созданы Миньоттом и Асмутом-Блумом. Они используют специальные последовательности целых чисел вместе с CRT.

Китайская теорема об остатках

Позволять $k\geqslant 2,m_{1},...,m_{k}\geqslant 2$ , и $b_{1},...,b_{k}\in \mathbf {Z}$ . Система сравнений

{\begin{cases}x\equiv &b_{1}\ {\bmod {\ }}m_{1}\\&\vdots \\x\equiv &b_{k}\ {\bmod {\ }}m_{k}\\\end{cases}}

имеет решения в $Z$ тогда и только тогда, когда $b_{i}\equiv b_{j}{\bmod {(}}m_{i},m_{j})$ для всех $1\leqslant i,j\leqslant k$ , где $(m_{i},m_{j})$ обозначает наибольший общий делитель (НОД) чисел $m i$ и $m j$ . Более того, в этих условиях система имеет единственное решение в $Z / n Z$ , где $n=[m_{1},...,m_{k}]$ , что обозначает наименьшее общее кратное (НОК) чисел $m_{1},...,m_{k}$ .

Передача секрета с помощью CRT

Поскольку китайская теорема об остатках дает нам метод однозначного определения числа S по модулю k - множества относительно простых целых чисел $m_{1},m_{2},...,m_{k}$ , при условии ${\textstyle S<\prod _{i=1}^{k}m_{i}}$ , то идея состоит в том, чтобы построить схему, которая будет определять секрет $S$ по любым $k$ долей (в данном случае остатку $S$ по модулю каждого из чисел $m i$ ), но не будет раскрывать секрет, если известно меньше $k$ таких чисел. акции.

В конечном итоге мы выбираем $n$ относительно простых целых чисел $m_{1}<m_{2}<...<m_{n}$ такой, что $S$ меньше произведения любого выбора $k$ этих целых чисел, но в то же время больше, чем любой выбор $k - 1$ из них. Тогда акции $s_{1},s_{2},...,s_{n}$ определяются $s_{i}=S{\bmod {\ }}m_{i}$ для $i=1,2,...,n$ . Таким образом, благодаря CRT, мы можем однозначно определить $S$ из любого набора из $k$ или более долей, но не менее чем из $k$ . Это обеспечивает так называемую пороговую структуру доступа .

Это условие на $S$ можно также рассматривать как

\prod _{i=n-k+2}^{n}m_{i}<S<\prod _{i=1}^{k}m_{i}.

Поскольку $S$ меньше наименьшего произведения $k$ целых чисел, оно будет меньше произведения любого $k$ из них. Кроме того, поскольку оно больше произведения наибольшего $k - 1$ целого числа, оно будет больше произведения любого $k - 1$ из них.

Существуют две схемы обмена секретами , которые по существу используют эту идею: схемы Миньотта и Асмута-Блума, которые объясняются ниже.

Схема разделения секрета с порогом Миньотта

Миньотта с порогом Как было сказано ранее, схема совместного использования секрета использует, наряду с CRT, специальные последовательности целых чисел, называемые $(k, n)$ -последовательностями Миньотта, которые состоят из $n$ целых чисел, попарно взаимно простых , таких, что произведение наименьшего $k$ из них больше произведения $k - 1$ самых больших из них. Это условие имеет решающее значение, поскольку схема построена на выборе секрета как целого числа между двумя продуктами, и это условие гарантирует, что $не менее k$ для полного восстановления секрета потребуется долей, независимо от того, как они выбраны.

Формально, пусть $2 \leq k \leq n$ — целые числа. A $(k, n)$ -последовательность Миньотта — это строго возрастающая последовательность натуральных чисел. $m_{1}<\cdots <m_{n}$ , с $(m_{i},m_{j})=1$ для всех $1 ⩽ i < j ⩽ n$ , таких что $m_{n-k+2}\cdots m_{n}<m_{1}\cdots m_{k}$ . Позволять $\alpha =m_{n-k+2}\cdots m_{n}$ и $\beta =m_{1}\cdots m_{k}$ ; мы называем целые числа, лежащие строго между $\alpha$ и $\beta$ разрешенный диапазон. Мы строим $(k, n)$ - пороговую схему разделения секрета следующим образом: мы выбираем секрет $S$ как случайное целое число. $\alpha <S<\beta$ в разрешенном диапазоне. Мы вычисляем для каждого $1 \leq i \leq n$ сокращение по модулю $i S$ m $,$ которое мы называем $s i$ , это доли. Теперь для любых $k$ различных акций $s_{i_{1}},\ldots ,s_{i_{k}}$ , рассмотрим систему сравнений:

{\begin{cases}x\equiv &s_{i_{1}}\ {\bmod {\ }}m_{i_{1}}\\&\vdots \\x\equiv &s_{i_{k}}\ {\bmod {\ }}m_{i_{k}}\\\end{cases}}

По китайской теореме об остатках , поскольку $m_{i_{1}},\ldots ,m_{i_{k}}$ попарно взаимно просты , система имеет единственное решение по модулю $m_{i_{1}}\cdots m_{i_{k}}$ . По конструкции наших акций, это решение — не что иное, как секрет $S$ , который нужно восстановить.

Схема разделения секрета с порогом Асмута – Блума

В этой схеме также используются специальные последовательности целых чисел. Пусть $2 \leq k \leq n$ — целые числа. Рассмотрим последовательность попарно взаимно простых натуральных чисел $m_{0}<...<m_{n}$ такой, что $m_{0}\cdot m_{n-k+2}\cdots m_{n}<m_{1}\cdots m_{k}$ . Для данной последовательности мы выбираем секрет S как случайное целое число из $Z / m 0 Z.$ множества

Затем мы выбираем случайное целое число $α$ такое, что $S+\alpha \cdot m_{0}<m_{1}\cdots m_{k}$ . Мы вычисляем сокращение по $m i$ модулю $S+\alpha \cdot m_{0}$ , для всех $1 \leq i \leq n$ это доли $I_{i}=(s_{i},m_{i})$ . Теперь для любых $k$ различных акций $I_{i_{1}},...,I_{i_{k}}$ , рассмотрим систему сравнений:

{\begin{cases}x\equiv &s_{i_{1}}\ {\bmod {\ }}m_{i_{1}}\\&\vdots \\x\equiv &s_{i_{k}}\ {\bmod {\ }}m_{i_{k}}\\\end{cases}}

По китайской теореме об остатках , поскольку $m_{i_{1}},...,m_{i_{k}}$ попарно взаимно просты , система имеет единственное решение $S 0$ по модулю $m_{i_{1}}\cdots m_{i_{k}}$ . По построению наших долей, секрет S заключается в уменьшении по $m 0$ S $модулю 0$ .

Важно отметить, что $Миньотта (k, n)$ с порогом схема разделения секрета не идеальна в том смысле, что набор из менее чем $k$ долей содержит некоторую информацию о секрете. Схема Асмута–Блума совершенна: $α$ не зависит от секрета $S$ и

\left.{\begin{array}{r}\prod _{i=n-k+2}^{n}m_{i}\\\alpha \end{array}}\right\}<{\frac {\prod _{i=1}^{k}m_{i}}{m_{0}}}

Следовательно, $α$ может быть любым целым числом по модулю

\prod _{i=n-k+2}^{n}m_{i}.

Это произведение $k 1$ модулей является наибольшим из любого из $n$ возможных $k эквивалентностей$ произведений, поэтому любое подмножество $- - 1$ может быть любым целым числом по модулю его произведения, и никакая информация из $S$ не утекает.

Пример

Ниже приводится пример схемы Асмута – Блума. В практических целях мы выбираем небольшие значения для всех параметров. Мы выбираем $k = 3$ и $n = 4$ . Наши попарно взаимно простые целые числа $m_{0}=3,m_{1}=11,m_{2}=13,m_{3}=17$ и $m_{4}=19$ . Они удовлетворяют требуемой последовательности Асмута–Блума, поскольку $3\cdot 17\cdot 19<11\cdot 13\cdot 17$ .

Скажем, наш секрет $S$ равен 2. Выберите $\alpha =51$ , удовлетворяющее требуемому условию схемы Асмута–Блума. Затем $2+51\cdot 3=155$ и мы вычисляем доли для каждого из целых чисел 11, 13, 17 и 19. Это соответственно 1, 12, 2 и 3. Мы рассматриваем один возможный набор из 3 долей: среди 4 возможных наборов по 3 доли мы берем набор {1, 12, 2} и покажите, что он восстанавливает секрет $S = 2$ . Рассмотрим следующую систему сравнений:

{\begin{cases}x\equiv &1\ {\bmod {\ }}11\\x\equiv &12\ {\bmod {\ }}13\\x\equiv &2\ {\bmod {\ }}17\\\end{cases}}

Для решения системы пусть $M=11\cdot 13\cdot 17$ . Из конструктивного алгоритма решения такой системы мы знаем, что решение системы есть $x_{0}=1\cdot e_{1}+12\cdot e_{2}+2\cdot e_{3}$ , где каждый $e i$ находится следующим образом:

По тождеству Безу , поскольку $(m_{i},M/m_{i})=1$ , существуют положительные целые числа $r i$ и $s i$ , которые можно найти с помощью расширенного алгоритма Евклида , такие, что $r_{i}.m_{i}+s_{i}.M/m_{i}=1$ . Набор $e_{i}=s_{i}\cdot M/m_{i}$ .

Из тождеств $1=1\cdot 221-20\cdot 11=(-5)\cdot 187+72\cdot 13=5\cdot 143+(-42)\cdot 17$ , мы поняли это $e_{1}=221,e_{2}=-935,e_{3}=715$ , и единственное решение по модулю $11\cdot 13\cdot 17$ равно 155. Наконец, $S=155\equiv 2\mod 3$ .

См. также

Ссылки

Одед Голдрейх , Дана Рон и Мадху Судан , Китайский остаток с ошибками, Транзакции IEEE по теории информации, Том. 46, № 4, июль 2000 г., страницы 1330–1338.
Миньотт М. (1983) Как поделиться секретом. В: Бет Т. (ред.) Криптография. EUROCRYPT 1982. Конспекты лекций по информатике, том 149. Springer, Берлин, Гейдельберг.
К. А. Асмут и Дж. Блум. Модульный подход к защите ключей. Транзакции IEEE по теории информации, IT-29(2):208-210, 1983.
Сорин Ифтене. Общий обмен секретами на основе китайской теоремы об остатке с применением в электронном голосовании. Электронные заметки по теоретической информатике (ENTCS). Том 186 (июль 2007 г.). Страницы 67–84. Год издания: 2007. ISSN 1571-0661 .
Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы, второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 31.5: Китайская теорема об остатках, страницы 873–876.
Рональд Крамер . Базовый обмен секретами (лекции 1–2), заметки для занятий. Октябрь 2008 г., версия 1.1.

Внешние ссылки

https://web.archive.org/web/20091209071915/http://www.cryptolounge.org/wiki/Ronald_Cramer