Схема Миньотта

Схема Миньотта — пороговая схема разделения секрета, построенная с использованием простых чисел. Позволяет разделить секрет (число) между <math>n</math> сторонами таким образом, что его смогут восстановить любые <math>k</math> участников, но <math>k-1</math> участников восстановить секрет уже не смогут. Схема основана на китайской теореме об остатках.

История

Впервые схема была предложена в 1982 году французским учёным Морисом Миньоттом в качестве одного из вариантов использования <math>(k,n)</math>-пороговой схемы, описанной Ади Шамиром. Сам Шамир предлагал решение с применением интерполяции полинома на конечном поле, где секретом являлся сам полином. Миньотт же смог предоставить более простое решение, заложив в основу модулярный подход - секретом является некоторое число, а частичным секретом - его вычет по некоторому модулю. Доработанной схемой Миньотта является схема Асмута-Блума. В обеих схемах для восстановления секрета используется китайская теорема об остатках, формулировка которой определяет единственное решение (секрет).

Схема разделения секрета

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

В основе схемы лежит использование китайской теоремы об остатках, которая позволяет пользователям, имеющим некоторую долю секрета, восстановить сам секрет, причём единственным образом. Существует несколько версий теоремы, назовём следующую общей: Пусть <math>k\geqslant 2, m_1,\dots,m_k\geqslant 2, b_1,\dots,b_k\in \mathbb{Z}</math>. Тогда система уравнений

<math>\begin{cases} x \equiv b_1\mod m_1\\ \vdots \\ x \equiv b_k\mod m_k \end{cases} </math> имеет решения в <math>\mathbb{Z}</math> тогда и только тогда, когда <math>b_i\equiv b_j\mod (m_i,m_j)\forall 1\leqslant i,j\leqslant k</math>. Более того, если приведенная система имеет решения в <math>\mathbb{Z}</math>, она имеет единственное решение в <math>\mathbb{Z}_{[m_1,\dots,m_k]}, [m_1,\dots,m_k]</math> определяет наименьшее общее кратное <math>m_1,\dots,m_k</math>. В случае, если <math>(m_i,m_j)=1\forall 1\leqslant i<j\leqslant k</math>, китайскую теорему об остатках называют стандартной.

Пороговые схемы разделения секрета

Допустим, имеется n пользователей, пронумерованных от <math>1</math> до <math>n</math>, и набор групп<math>\mathcal{A}\subseteq P({1,2,\dots,n})</math>, где <math>P({1,2,\dots,n})</math> - все подгруппы группы <math>\{1,2,\dots,n\}</math>. Фактически, <math>\mathcal{A} </math>-схема разделения секрета – это метод генерации секретов <math>(S,(I_1,\dots,I_n))</math> таких, что:

• (корректность) Для любого <math>A \in \mathcal{A}</math>, проблема нахождения <math>S</math> при наличии всех <math>I</math> «простая»
• (безопасность) Для любого <math>A \in P({1,2,\dots,n})\setminus \mathcal{A}</math>, проблема нахождения <math>S</math> является «труднообрабатываемой»

<math>\mathcal{A}</math> будем называть структурой доступа, <math>S</math> – секретом, а <math>I_1,\dots,I_n</math> – тенями <math>S</math>. Наборы элементов из<math>A</math>назовём группами авторизации. В идеальной схеме разделения секрета тени любой группы, не являющейся группой авторизации, не даёт информации (с точки зрения теории информации) о секрете. Доказано, что в любой идеальной схеме разделения секрета размер каждой из теней должен быть не меньше размера самого секрета. Естественным является условие о том, что структура доступа <math>\mathcal{A}</math> должна быть монотонной, то есть: <math>(\forall B\in P(\{1,2,\dots ,n\}))((\exists A\in \mathcal{A})(A\subseteq B)\Rightarrow B\in \mathcal{A})</math>. Любая структура доступа <math>\mathcal{A}</math> хорошо описывается с помощью минимального набора групп авторизации: <math>\mathcal{A}_{min}=\{A\in \mathcal{A} \mid (\forall B\in \mathcal{A} \setminus \{A\})(\neg B\subseteq A)\}</math>. Можно описать и структуру доступа, не обладающую свойствами авторизации: <math>\bar{\mathcal{A}}=P(\{1,2,\dots ,n\})\setminus \mathcal{A}</math>. Её хорошо описывает максимальный набор групп "неавторизации":<math>\bar{\mathcal{A}}_{max}=\{A\in \bar{\mathcal{A}} \mid (\forall B\in \bar{\mathcal{A}} \setminus \{A\})(\neg A\subseteq B)\}</math>

В первых схемах разделения секрета только количество участников являлось важным при восстановлении секрета. Такие схемы были названы пороговыми схемами разделения секрета. Пусть <math>n \geqslant 2, 2 \leqslant k \leqslant n</math>, тогда структура доступа <math>\mathcal{A} = \{A \in P({1,2,\dots ,n})\mid |A| \geqslant k\}</math> называется <math>(k,n)</math>-пороговой структурой доступа.

Стоит учесть также, что для <math>(k,n)</math>-пороговых структур доступа.:

<math>\bar{\mathcal{A}}=\{A\in P(\{1,2,\dots ,n\}) \mid |A|\leqslant k-1\}</math>

<math>\mathcal{A}_{min}=\{A\in P(\{1,2,\dots ,n\}) \mid |A|=k\}</math>

<math>\bar{\mathcal{A}}_{max}=\{A\in P(\{1,2,\dots ,n\}) \mid |A|=k-1\}</math>.

Все <math>A</math>-схемы разделения секрета также назовём <math>(k,n)</math>-пороговыми схемами разделения секрета.

Последовательность Миньотта

Пороговая схема разделения секрета Миньотта использует специальные последовательности чисел, названные последовательностями Миньотта. Пусть <math>n</math> – целое, <math>n \geqslant 2</math>, и <math>2 \geqslant k \geqslant n </math>. <math>(k,n)</math>-последовательность Миньотта – последовательность взаимно простых положительных <math>p_1 < p_2 <\dots < p_n</math> таких, что <math>\prod^{k-2}_{i=0}p_{n-i}<\prod^{k}_{i=1}p_i</math> Последнее утверждение также равносильно следующему: <math>\max _{1 \leqslant i_1<\dots <i_{k-1}\leqslant n}(p_{i_1}\dots p_{i_{k-1}})<\min _{1 \leqslant i_1<\dots <i_k\leqslant n}(p_{i_1}\dots p_{i_k})</math>

Алгоритм

Имея открытый ключ-последовательность Миньотта, схема работает так:

1. Секрет <math>S</math> выбирается, как случайное число такое, что <math>\beta < S < \alpha </math>, где <math>\alpha = \prod^{k}_{i=1}p_i , \beta = \prod^{k-2}_{i=0}p_{n-i}</math>. Другими словами, секрет должен находиться в промежутке между <math>p_1 * p_2 * \dots * p_k</math> и <math>p_{n-k+2} * \dots * p_n</math>
2. Доли вычисляются, как <math>I_i=S\mod p_i</math>, для всех <math>1 \leqslant i \leqslant n</math>
3. Имея <math>k</math> различных теней <math>I_{i_1},\dots ,I_{i_k}</math>, можно получить секрет <math>S</math>, используя стандартный вариант китайской теоремы об остатках – им будет единственное решение по модулю <math>p_{i_1}\dots p_{i_k}</math> системы:

<math>\begin{cases} x \equiv I_{i_1}\mod p_{i_1}\\ \vdots \\ x \equiv I_{i_k}\mod p_{i_k} \end{cases} </math> Секретом является решение приведенной выше системы, более того, <math>S</math> лежит в пределах <math>Z_{{p_{i_1}},\dots ,p_{i_k}}</math>, т.к. <math>S < \alpha </math>. С другой стороны, имея всего <math>k-1</math> различных теней <math>I_{i_1},\dots ,I_{i_{k-1}}</math>, можно сказать, что <math>S\equiv x_0 \mod p_{i_1}\dots p_{i_{k-1}}</math>, где <math>x_0</math> – единственное решение по модулю <math>p_{i_1}\dots p_{i_{k-1}}</math> исходной системы (в данном случае: <math>S>\beta \geqslant p_{i_1}\dots p_{i_{k-1}}>x_0</math>. Для того, чтобы получить приемлемый уровень безопасности, должны быть использованы <math>(k,n)</math> последовательности Миньотта с большим значением <math>\dfrac{\alpha -\beta }{\beta }</math> Очевидно, что схема Миньотта не обладает значительной криптографической стойкостью, однако может оказаться удобной в приложениях, где компактность теней является решающим фактором.

Пример

Допустим, необходимо разделить секрет между <math>n=6</math> пользователями так, чтобы любые <math>k=5</math> могли его восстановить.

• Выбираем последовательность Миньотта <math>p_1=5, p_2=7, p_3=11, p_4=13, p_5=17, p_6=19</math>.
• Вычисляем для данной последовательности <math>\alpha =p_1*p_2*p_3*p_4*p_5=85085</math>, <math>\beta =p_3*p_4*p_5*p_6=46189</math>.
• Выбираем <math>S</math> такое, что <math>\beta <S<\alpha </math>, например, <math>S=50000</math>.
• Вычисляем доли: <math>I_i=S\mod p_i</math>: <math>I_1=50000\mod 5=0,I_2=50000\mod 7=6,I_3=50000\mod 11=5,I_4=50000\mod 13=2,I_5=50000\mod 17=3,I_5=50000\mod 19=11</math>
• Для восстановления секрета решим систему уравнений для <math>k</math> теней (предположим, секрет восстанавливают участники 1-5):

<math>\begin{cases} x \equiv 0\mod 5\\ x \equiv 6\mod 7\\ x \equiv 5\mod 11\\ x \equiv 2\mod 13\\ x \equiv 2\mod 17 \end{cases} </math>.

Из формулировки китайской теоремы об остатках знаем, что решение будет единственным.

Модификации схемы Миньотта

Обобщённая последовательность Миньотта

Для данной пороговой схемы элементы последовательности не обязательно являются взаимно простыми. Пусть <math>n</math> – целое, <math>n \geqslant 2, 2 \leqslant k \leqslant n</math>. Обобщённой <math>(k,n)</math>-последовательностью Миньотта называют такую последовательность <math>p_1,\dots ,p_n</math> положительных целых чисел, что <math>\max _{1\leqslant i_1<\dots <i_{k-1}\leqslant n}([p_{i_1},\dots ,p_{i_{k-1}}])<\min _{1\leqslant i_1<\dots <i_k\leqslant n}([p_{i_1},\dots ,p_{i_k}])</math>. Нетрудно видеть, что любая <math>(k,n)</math>-последовательность Миньотта является обобщённой <math>(k,n)</math>-последовательностью Миньотта. Более того, если умножить каждый элемент обобщённой последовательности на фиксированный элемент <math>\delta \in Z, (\delta, p_1,\dots,p_n) = 1</math>, также получим обобщённую <math>(k,n)</math>-последовательность Миньотта. Расширенная схема Миньотта работает так же, как и обыкновенная для <math>\alpha =\min _{1\leqslant i_1<\dots <i_k\leqslant n}([p_{i_1},\dots ,p_{i_k}])</math> и <math>\beta =\max _{1\leqslant i_1<\dots <i_{k-1}\leqslant n}([p_{i_1},\dots ,p_{i_{k-1}}])</math>.В данном случае для нахождения секрета необходимо использовать обобщённый вариант китайской теоремы об остатках.

Взвешенное разделение секрета

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

Пусть <math>S(k,n,N,P)</math> - секрет, где <math>P=(p_1,\dots ,p_N)</math> - веса теней пользователей. Сгенерируем <math>(k,W)</math>-последовательность Миньотта, где <math>W=\sum_{i=1}^{n}p_i</math>. Тогда <math>P_i=[\{ P^{\prime }_{j}\mid j\in P_{a_j}\}] \forall 1 \leqslant i \leqslant N</math>, где <math>P_{a_1},\dots ,P_{a_N}</math> - произвольное разбиение множества <math>\{1,2,\dots ,W\}</math> такое, что <math>|P_{a_i}|=p_i \forall 1\leqslant i\leqslant N</math>

Можно заметить, что существует однозначное соответствие между размером и весом тени: например, бит — это тень весом 1, тень весом <math>p_i</math> будет весить <math>p_i*n</math> битов. Реализация схемы Миньотта со взвешенным разделением секрета не является целесообразной, так как генерация последовательности Миньотта и взвешенной пороговой структуры доступа является трудо- и ресурсоемкой задачей. Существуют более простые и эффективные схемы со взвешенным разделением секрета, в которых также устранена зависимость между весом и размером тени.

Аналогичные схемы

• Схема Асмута-Блума, также основанная на китайской теореме об остатках, была впервые представлена в 1983 году. Основное отличие состоит в том, что вместо последовательности Миньотта, требующей генерации, необходимо выбрать простое число, связанную с ним последовательность из <math>n</math> взаимно простых чисел, а также некоторое случайное число, с помощью которого шифруется секрет, и уже на основе зашифрованного секрета вычисляются тени. В схема Асмута-Блума отсутствуют некоторые недостатки, присущие схеме Миньотта:

1. Нет ограничения на область, в которой можно выбирать секрет
2. Набор из менее, чем <math>k</math> теней пользователей не даёт никакой информации о секрете

• Существует несколько схем с разделением взвешенного секрета, основанных на схеме Миньотта. В качестве примера приведём схему, опубликованную в совместной работе Индианского университета и университета Пердью

1. Предполагаем, что раскрытый вес равен <math>w</math>, а <math>n</math>-длина используемых чисел в битах. Также полагаем, что <math>w<n</math>. Стоит отметить, что в реальных схемах <math>w\ll n</math>.
2. Секрет <math>S</math> в таком случае выберем длиной <math>w*n</math> битов (если он меньше, дополним его, например, путём повторения битов секрета или добавления случайных битов).
3. Для пользователя <math>U_i</math>, обладающего весом его доли <math>p_i</math>, выберем простое число <math>P_i</math> длиной <math>p_i*n</math> битов и такое, что <math>p_i<w</math>. Простые числа выбраны в данном случае для упрощения работы алгоритма, для корректной работы схемы достаточно выбора попарно взаимно простых чисел.
4. Вычислим <math>r_i=S\mod P_i</math> и определим долю пользователя <math>U_i</math>, как <math>s_i=\{(r_i,p_i)\}</math>.
5. При восстановлении секрета любой коллектив пользователей <math>U_{i_1},U_{i_2},\dots ,U_{i_l}</math> такой, что <math>p_{i_1}+p_{i_2}+\dots +p_{i_l}>w</math> может составить систему уравнений:

<math>\begin{cases} S \equiv r_{i_1}\mod P_{i_1}\\ S \equiv r_{i_2}\mod P_{i_2}\\ \vdots \\ S \equiv r_{i_l}\mod P_{i_l}\\ \end{cases} </math> и вычислить S, применив китайскую теорему об остатках. Так как размер <math>S</math> составляет <math>w*n</math> битов, размер произведения модулей <math>\hat{P}=P_{i_1}*P_{i_2}*\dots *P_{i_n}</math> состоит из, по меньшей мере, <math>(p_{i_1}+p_{i_2}+\dots +p_{i_l})*n-l</math>, можно видеть, что <math>\hat{P}>S</math>, пока <math>w<n</math>. Именно это позволяет вычислить секрет <math>S</math> единственным образом. Можно ослабить условие на сумму весов долей до <math>p_{i_1}+p_{i_2}+\dots +p_{i_l}\geqslant w</math>, тогда в случае <math>p_{i_1}+p_{i_2}+\dots +p_{i_l}=w</math> длина <math>\hat{P}</math> составляет, как минимум, <math>w*n-w+1</math>, поэтому необходимо ограничить <math>S</math> до <math>w*n-w</math> битов. Если же это невозможно, можно сохранить работоспособность схемы, введя дополнительный элемент, модуль которого <math>H_P</math> - наименьшее простое число из <math>w</math> битов, доля элемента - <math>H_s=S\mod H_P</math>. Этот элемент можно использовать, как дополнительное уравнение в приведенной выше системе, в таком случае <math>P_{i_1}*P_{i_2}*\dots *P_{i_l}*H_P>S</math>, поэтому секрет можно будет восстановить единственным образом. В данной схеме устранён один из главных недостатков обыкновенной схемы с разделением взвешенного секрета - любую долю <math>s_i</math> можно описать точкой <math>(r_i,P_i)</math>, причём эта точка не обладает зависимостью между собственным весом и размером.

---

Данную схему можно также изменить для работы с несколькими секретами. Допустим, необходимо разделить секреты <math>S_1,\dots,S_k</math>, каждый секрет состоит из <math>n</math> битов. Сложим секреты вместе, получив один секрет длиной <math>k*n</math> битов. Необходимо рассмотреть три случая:

1. <math>k<w</math>: Добавим случайных битов, до размера <math>w*n</math>
2. <math>k=w</math>: Ничего не делаем
3. <math>k>w</math>: Введём дополнительный элемент с весом <math>(k-w)</math>

Производительность схемы

Значительную часть времени выполнения схемы отнимает генерация последовательностей Миньотта и взаимно простых модулей. Допустим, имеются доли <math>s_1,s_2,\dots ,s_N</math> с весами <math>p_1,p_2,\dots ,p_N</math> соответственно. Общий вес долей составит <math>p_1+p_2+\dots +p_N=W</math>, вес, необходимый для раскрытия секрета - <math>w</math>, размер числа - <math>n</math> битов.

• Генерация последовательности Миньотта состоит из нескольких этапов:

1. Генерация <math>W</math> попарно взаимно простых <math>P_1,\dots ,P_W</math>. Преобладающей операцией является нахождение НОК, сложность её составляет <math>O(n^2)</math>. Для каждого нового сгенерированного числа необходимо проверить, является ли оно попарно взаимно простым с каждый из предыдущих элементов, поэтому для генерации <math>W</math> попарно взаимно простых чисел сложность составляет <math>O(W^2n^2)</math>.
2. Их сортировка, её сложность составляет <math>O(Wlog(W)n)</math>.
3. Проверка условия <math>\prod ^{w-2}_{i=0}P_{W-i}<\prod ^w_{j=1}P_j</math>. Сложность перемножения двух чисел длиной <math>l</math> битов и <math>v</math> битов составляет <math>O(lv)</math>. Сложность проверки составит <math>O(w^2n^2)</math>.

Таким образом, общая сложность генерации последовательности Миньотта составляет <math>O(W^2n^2)</math>.

• Для генерации модуля пользователю с весом <math>p_i</math> необходимо перемножить <math>p_i</math> чисел размера <math>n</math>. Сложность генерации <math>N</math> модулей составит <math>O((p_1-2)n^2+(p_2-1)n^2+\dots +(p_N-1)n^2)=O((W-N)n^2)</math>. Таким образом, общая сложность генерации модулей также составляет <math>O(W^2n^2)</math>.

Схема не обладает хорошей производительностью, так как возможно модифицировать её и тем самым избавиться от необходимости генерации последовательностей Миньотта. На графиках приведены результаты анализа производительности схемы, основанной на схеме Миньотта со взвешенном разделением секрета и самой схемы. Для построения графика была выбрана <math>(4,15)</math>-пороговая схема с одним секретом, <math>p_i=1</math> и <math>\hat{p}=(1,2,3,\dots,1,2,3)</math> соответственно.

Недостатки схемы

• Не обладает криптографической стойкостью, так как даже неполное множество пользователей может предоставить некоторую информацию о секрет.
• Не является простой в принципиальном плане или при реализации. Генерация последовательностей Миньотта и пороговых структур доступа является трудным и ресурсоемким процессом.
• Существует ограничение на область значений, в которой можно выбирать секрет:<math>S</math> должен находится в промежутке между <math>p_1 * p_2 * \dots * p_k</math> и <math>p_{n-k+2} * \dots * p_n</math>. Знание этого факта также даёт дополнительную информацию злоумышленнику.
• Для обеспечение хорошей криптостойкости необходима генерация больших значений <math>\dfrac{\alpha -\beta }{\beta }</math>, что также является ресурсоемкой задачей.
• Злоумышленник может обмануть пользователей схемы, подменив секрет.

Схемы поведения злоумышленников

Можно выделить две схемы, описывающих поведение злоумышленников в пороговых схемах: модель CDV, в которой злоумышленники знают секрет и пытаются передать другим участникам ложные данные, и модель OKS, в которой злоумышленники не знают секрета заранее. В обыкновенной схеме Миньотта один злоумышленник всегда может обмануть <math>k-1</math> пользователей в модели CDV и с большой вероятностью - в модели OKS. Допустим, участники <math>i_1, i_2,\dots ,i_k</math> разделили секрет, и пользователь <math>i_1</math> решает сжульничать. Следовательно, он должен изменить свою тень <math>I_{i_1}</math> на <math>I^{\prime }_{i_1}</math> так, чтобы <math>S^\prime \neq S, S\in(\beta, \alpha )</math>. Пусть <math>l=p_{i_2}p_{i_3}\dots p_{i_k}, r=p_{i_1}p_{i_2}\dots p_{i_k}\Rightarrow S=pl+q, p\in \mathbf{Z}_{b_1}, q\in \mathbf{Z}_{I}</math>. Используя китайскую теорему об остатках, получим <math>S\mod l=S^\prime \mod l=q</math>, то есть, <math>S^\prime </math> представим в виде <math>p^\prime l+q</math>. Так как последовательность Миньотта <math>p_1,\dots ,p_k</math> известна, можно найти <math>l</math>. Можно выбрать <math>p^\prime =p\pm 1</math>, откуда <math>I^{\prime }_{i_1}=(I_{i_1}\pm l)\mod p_{i_1} \Rightarrow S^\prime =(p\pm 1)l+q=(S\pm l)\mod r</math>

В модели CDV злоумышленник знает секрет, поэтому используя выражение <math>S^\prime =(S\pm l)\mod r</math> он может удостовериться в том, что<math>S^\prime \in (\beta ,\alpha )</math> (рис.1), существование <math>S^\prime </math> гарантировано, если <math>k-1</math> участников не могут определить секрет. Следовательно, злоумышленник может обмануть участников схемы с вероятностью 1. Более того, в этой модели злоумышленник может контролировать значение <math>S^\prime </math>, вычисляя <math>q</math> напрямую из <math>S</math>: <math>I^{\prime }_{i_1}=S^\prime \mod p_{i_1}</math>, где <math>S^\prime = p^\prime l+q, p^\prime \in \mathbb{Z}_\beta :S^\prime \in (\beta ,\alpha )</math>

В модели OKS, так как злоумышленник не знает секрет, он не может проверить истинность неравенств <math>S-l<\beta </math> и <math>S+l>\alpha </math>. В таком случае он всегда может использовать <math>I^{\prime }_{i_1}=(I_{i_1}+l)\mod p_1</math>. Единственный вариант, при котором обман может быть раскрыт - <math>S+l>\alpha </math>, откуда <math>S^\prime =(S+l)\mod r<\beta </math>(рис.2) или <math>S^\prime =(S+l)\mod r>\alpha </math>(рис.3). Следовательно, вероятность успешного обмана составляет <math>1-\frac{1}{[\frac{\alpha -\beta }{l}]}</math>

Пример

Пусть <math>n=5,k=3,p_1=661,p_2=673,p_3=677,p_4=683,p_5=691\Rightarrow \alpha =301165481,\beta =471953</math>. Тогда для секрета <math>S=500000</math> будут сгенерированы тени <math>I_1=284,I_2=634,I_3=374,I_4=44,I_5=407</math>. Допустим, участники 1,2,3 объединили свои доли, и участник 1 хочет сжульничать. Тогда он вычисляет <math>p_2*p_3=455621</math> и изменяет свою долю так, что <math>I^{\prime }_1=(I_1+p_2p_3)\mod p_1=476</math>. В таком случае, после решения системы уравнений <math>\begin{cases} x \equiv 476\mod 661\\ x \equiv 634\mod 673\\ x \equiv 374\mod 677 \end{cases} </math> участники восстановят неверный секрет <math>S^\prime =(S+p_2p_3)\mod p_1p_2p_3=955621</math>, также находящийся между <math>\alpha </math>и <math>\beta </math>. При этом пользователь 1 может получить настоящий секрет: <math>S=(S^\prime -p_2p_3)\mod p_1p_2p_3=500000</math>

Модификация схемы

Для того, чтобы избежать подобных махинаций, можно сделать следующее:

• Вводится дилер, генерирующий <math>(k,n)</math>-последовательность Миньотта <math>p_1, p_2,\dots ,p_n</math>. Также дилер генерирует <math>n</math> различных простых <math>m_1,\dots ,m_n</math> таких, что:<math>\frac{\alpha -\beta }{\beta \max _{1\leqslant i_1<\dots <i_{k-1}\leqslant n}(m_{i_1}*\dots *m_{i_{k-1}})}</math> является достаточно большим. Секрет <math>S</math> выбирается так, что <math>\beta <S<\alpha </math>. Долями <math>I_i</math> являются <math>(S\mod p_i, S\mod m_ip_i, m_i)</math>. Процесс восстановления секрета проходит так же, как и в стандартной схеме Миньотта. После того, как секрет <math>S^\prime </math> восстановлен, любой участник <math>i</math> может определить обман путём сравнения <math>S^\prime \mod m_i</math> с данными, переданными дилером. Таким образом, злоумышленник может обмануть участника <math>j</math> с вероятностью <math>\frac{1}{m_j} </math>

Литература

• M. Mignotte [www.springerlink.com/content/ynbh0numuuaxcwgm/ How to Share a Secret] (англ.) // Lecture Notes in Computer Science. — 1983. — Vol. 149. — P. 371—375. — DOI:10.1007/3-540-39466-4_27.
• E. Kranakis [www.cs.yale.edu/publications/techreports/tr394.pdf Primality and Cryptography] (англ.) // Wiley-Teubner Series in Computer Science. — 1986. — Vol. 1. — P. 9.
• C. A. Asmuth and J. Bloom [ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=1056651&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F18%2F22731%2F01056651.pdf%3Farnumber%3D1056651 A modular approach to key safeguarding] (англ.) // IEEE Transactions on Information Theory. — 1986. — Vol. 2. — P. 208-210.

Ссылки

• [www.fatih.edu.tr/~tyanik/ceng542/General-Secret-Sharing-Based-on-CRT.pdf General Secret Sharing Based on the Chinese Remainder Theorem] (англ.). Electronic Notes in Theoretical Computer Science (2007). Проверено 12 декабря 2013.
• [cs.iupui.edu/~xkzou/Papers/ICCCN2011-SecretSharing.pdf A New Approach to Weighted Multi-Secret Sharing] (англ.). Electronic Notes in Theoretical Computer Science (2011). Проверено 12 декабря 2013.
• [eprint.iacr.org/2009/426.pdf Cheating Detection and Cheater Identification in CRT-based Secret Sharing Schemes] (англ.). “Al. I. Cuza” University Iasi, Romania (2009). Проверено 12 декабря 2013.
• [thor.info.uaic.ro/~siftene/Publications.html A generalization of Mignotte’s secret sharing scheme] (англ.). Proceedings of the 6th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (2004). Проверено 12 декабря 2013.

Отрывок, характеризующий Схема Миньотта

– Да, вот извольте их собрать! – отвечал другой офицер. – Их не соберешь; надо идти скорее, чтобы последние не ушли, вот и всё!
– Как же идти? там стали, сперлися на мосту и не двигаются. Или цепь поставить, чтобы последние не разбежались?
– Да подите же туда! Гони ж их вон! – крикнул старший офицер.
Офицер в шарфе слез с лошади, кликнул барабанщика и вошел с ним вместе под арки. Несколько солдат бросилось бежать толпой. Купец, с красными прыщами по щекам около носа, с спокойно непоколебимым выражением расчета на сытом лице, поспешно и щеголевато, размахивая руками, подошел к офицеру.
– Ваше благородие, – сказал он, – сделайте милость, защитите. Нам не расчет пустяк какой ни на есть, мы с нашим удовольствием! Пожалуйте, сукна сейчас вынесу, для благородного человека хоть два куска, с нашим удовольствием! Потому мы чувствуем, а это что ж, один разбой! Пожалуйте! Караул, что ли, бы приставили, хоть запереть дали бы…
Несколько купцов столпилось около офицера.
– Э! попусту брехать то! – сказал один из них, худощавый, с строгим лицом. – Снявши голову, по волосам не плачут. Бери, что кому любо! – И он энергическим жестом махнул рукой и боком повернулся к офицеру.
– Тебе, Иван Сидорыч, хорошо говорить, – сердито заговорил первый купец. – Вы пожалуйте, ваше благородие.
– Что говорить! – крикнул худощавый. – У меня тут в трех лавках на сто тысяч товару. Разве убережешь, когда войско ушло. Эх, народ, божью власть не руками скласть!
– Пожалуйте, ваше благородие, – говорил первый купец, кланяясь. Офицер стоял в недоумении, и на лице его видна была нерешительность.
– Да мне что за дело! – крикнул он вдруг и пошел быстрыми шагами вперед по ряду. В одной отпертой лавке слышались удары и ругательства, и в то время как офицер подходил к ней, из двери выскочил вытолкнутый человек в сером армяке и с бритой головой.
Человек этот, согнувшись, проскочил мимо купцов и офицера. Офицер напустился на солдат, бывших в лавке. Но в это время страшные крики огромной толпы послышались на Москворецком мосту, и офицер выбежал на площадь.
– Что такое? Что такое? – спрашивал он, но товарищ его уже скакал по направлению к крикам, мимо Василия Блаженного. Офицер сел верхом и поехал за ним. Когда он подъехал к мосту, он увидал снятые с передков две пушки, пехоту, идущую по мосту, несколько поваленных телег, несколько испуганных лиц и смеющиеся лица солдат. Подле пушек стояла одна повозка, запряженная парой. За повозкой сзади колес жались четыре борзые собаки в ошейниках. На повозке была гора вещей, и на самом верху, рядом с детским, кверху ножками перевернутым стульчиком сидела баба, пронзительно и отчаянно визжавшая. Товарищи рассказывали офицеру, что крик толпы и визги бабы произошли оттого, что наехавший на эту толпу генерал Ермолов, узнав, что солдаты разбредаются по лавкам, а толпы жителей запружают мост, приказал снять орудия с передков и сделать пример, что он будет стрелять по мосту. Толпа, валя повозки, давя друг друга, отчаянно кричала, теснясь, расчистила мост, и войска двинулись вперед.


В самом городе между тем было пусто. По улицам никого почти не было. Ворота и лавки все были заперты; кое где около кабаков слышались одинокие крики или пьяное пенье. Никто не ездил по улицам, и редко слышались шаги пешеходов. На Поварской было совершенно тихо и пустынно. На огромном дворе дома Ростовых валялись объедки сена, помет съехавшего обоза и не было видно ни одного человека. В оставшемся со всем своим добром доме Ростовых два человека были в большой гостиной. Это были дворник Игнат и казачок Мишка, внук Васильича, оставшийся в Москве с дедом. Мишка, открыв клавикорды, играл на них одним пальцем. Дворник, подбоченившись и радостно улыбаясь, стоял пред большим зеркалом.
– Вот ловко то! А? Дядюшка Игнат! – говорил мальчик, вдруг начиная хлопать обеими руками по клавишам.
– Ишь ты! – отвечал Игнат, дивуясь на то, как все более и более улыбалось его лицо в зеркале.
– Бессовестные! Право, бессовестные! – заговорил сзади их голос тихо вошедшей Мавры Кузминишны. – Эка, толсторожий, зубы то скалит. На это вас взять! Там все не прибрано, Васильич с ног сбился. Дай срок!
Игнат, поправляя поясок, перестав улыбаться и покорно опустив глаза, пошел вон из комнаты.
– Тетенька, я полегоньку, – сказал мальчик.
– Я те дам полегоньку. Постреленок! – крикнула Мавра Кузминишна, замахиваясь на него рукой. – Иди деду самовар ставь.
Мавра Кузминишна, смахнув пыль, закрыла клавикорды и, тяжело вздохнув, вышла из гостиной и заперла входную дверь.
Выйдя на двор, Мавра Кузминишна задумалась о том, куда ей идти теперь: пить ли чай к Васильичу во флигель или в кладовую прибрать то, что еще не было прибрано?
В тихой улице послышались быстрые шаги. Шаги остановились у калитки; щеколда стала стучать под рукой, старавшейся отпереть ее.
Мавра Кузминишна подошла к калитке.
– Кого надо?
– Графа, графа Илью Андреича Ростова.
– Да вы кто?
– Я офицер. Мне бы видеть нужно, – сказал русский приятный и барский голос.
Мавра Кузминишна отперла калитку. И на двор вошел лет восемнадцати круглолицый офицер, типом лица похожий на Ростовых.
– Уехали, батюшка. Вчерашнего числа в вечерни изволили уехать, – ласково сказала Мавра Кузмипишна.
Молодой офицер, стоя в калитке, как бы в нерешительности войти или не войти ему, пощелкал языком.
– Ах, какая досада!.. – проговорил он. – Мне бы вчера… Ах, как жалко!..
Мавра Кузминишна между тем внимательно и сочувственно разглядывала знакомые ей черты ростовской породы в лице молодого человека, и изорванную шинель, и стоптанные сапоги, которые были на нем.
– Вам зачем же графа надо было? – спросила она.
– Да уж… что делать! – с досадой проговорил офицер и взялся за калитку, как бы намереваясь уйти. Он опять остановился в нерешительности.
– Видите ли? – вдруг сказал он. – Я родственник графу, и он всегда очень добр был ко мне. Так вот, видите ли (он с доброй и веселой улыбкой посмотрел на свой плащ и сапоги), и обносился, и денег ничего нет; так я хотел попросить графа…
Мавра Кузминишна не дала договорить ему.
– Вы минуточку бы повременили, батюшка. Одною минуточку, – сказала она. И как только офицер отпустил руку от калитки, Мавра Кузминишна повернулась и быстрым старушечьим шагом пошла на задний двор к своему флигелю.
В то время как Мавра Кузминишна бегала к себе, офицер, опустив голову и глядя на свои прорванные сапоги, слегка улыбаясь, прохаживался по двору. «Как жалко, что я не застал дядюшку. А славная старушка! Куда она побежала? И как бы мне узнать, какими улицами мне ближе догнать полк, который теперь должен подходить к Рогожской?» – думал в это время молодой офицер. Мавра Кузминишна с испуганным и вместе решительным лицом, неся в руках свернутый клетчатый платочек, вышла из за угла. Не доходя несколько шагов, она, развернув платок, вынула из него белую двадцатипятирублевую ассигнацию и поспешно отдала ее офицеру.
– Были бы их сиятельства дома, известно бы, они бы, точно, по родственному, а вот может… теперича… – Мавра Кузминишна заробела и смешалась. Но офицер, не отказываясь и не торопясь, взял бумажку и поблагодарил Мавру Кузминишну. – Как бы граф дома были, – извиняясь, все говорила Мавра Кузминишна. – Христос с вами, батюшка! Спаси вас бог, – говорила Мавра Кузминишна, кланяясь и провожая его. Офицер, как бы смеясь над собою, улыбаясь и покачивая головой, почти рысью побежал по пустым улицам догонять свой полк к Яузскому мосту.
А Мавра Кузминишна еще долго с мокрыми глазами стояла перед затворенной калиткой, задумчиво покачивая головой и чувствуя неожиданный прилив материнской нежности и жалости к неизвестному ей офицерику.


В недостроенном доме на Варварке, внизу которого был питейный дом, слышались пьяные крики и песни. На лавках у столов в небольшой грязной комнате сидело человек десять фабричных. Все они, пьяные, потные, с мутными глазами, напруживаясь и широко разевая рты, пели какую то песню. Они пели врозь, с трудом, с усилием, очевидно, не для того, что им хотелось петь, но для того только, чтобы доказать, что они пьяны и гуляют. Один из них, высокий белокурый малый в чистой синей чуйке, стоял над ними. Лицо его с тонким прямым носом было бы красиво, ежели бы не тонкие, поджатые, беспрестанно двигающиеся губы и мутные и нахмуренные, неподвижные глаза. Он стоял над теми, которые пели, и, видимо воображая себе что то, торжественно и угловато размахивал над их головами засученной по локоть белой рукой, грязные пальцы которой он неестественно старался растопыривать. Рукав его чуйки беспрестанно спускался, и малый старательно левой рукой опять засучивал его, как будто что то было особенно важное в том, чтобы эта белая жилистая махавшая рука была непременно голая. В середине песни в сенях и на крыльце послышались крики драки и удары. Высокий малый махнул рукой.
– Шабаш! – крикнул он повелительно. – Драка, ребята! – И он, не переставая засучивать рукав, вышел на крыльцо.
Фабричные пошли за ним. Фабричные, пившие в кабаке в это утро под предводительством высокого малого, принесли целовальнику кожи с фабрики, и за это им было дано вино. Кузнецы из соседних кузень, услыхав гульбу в кабаке и полагая, что кабак разбит, силой хотели ворваться в него. На крыльце завязалась драка.
Целовальник в дверях дрался с кузнецом, и в то время как выходили фабричные, кузнец оторвался от целовальника и упал лицом на мостовую.
Другой кузнец рвался в дверь, грудью наваливаясь на целовальника.
Малый с засученным рукавом на ходу еще ударил в лицо рвавшегося в дверь кузнеца и дико закричал:
– Ребята! наших бьют!
В это время первый кузнец поднялся с земли и, расцарапывая кровь на разбитом лице, закричал плачущим голосом:
– Караул! Убили!.. Человека убили! Братцы!..
– Ой, батюшки, убили до смерти, убили человека! – завизжала баба, вышедшая из соседних ворот. Толпа народа собралась около окровавленного кузнеца.
– Мало ты народ то грабил, рубахи снимал, – сказал чей то голос, обращаясь к целовальнику, – что ж ты человека убил? Разбойник!
Высокий малый, стоя на крыльце, мутными глазами водил то на целовальника, то на кузнецов, как бы соображая, с кем теперь следует драться.
– Душегуб! – вдруг крикнул он на целовальника. – Вяжи его, ребята!
– Как же, связал одного такого то! – крикнул целовальник, отмахнувшись от набросившихся на него людей, и, сорвав с себя шапку, он бросил ее на землю. Как будто действие это имело какое то таинственно угрожающее значение, фабричные, обступившие целовальника, остановились в нерешительности.
– Порядок то я, брат, знаю очень прекрасно. Я до частного дойду. Ты думаешь, не дойду? Разбойничать то нонче никому не велят! – прокричал целовальник, поднимая шапку.
– И пойдем, ишь ты! И пойдем… ишь ты! – повторяли друг за другом целовальник и высокий малый, и оба вместе двинулись вперед по улице. Окровавленный кузнец шел рядом с ними. Фабричные и посторонний народ с говором и криком шли за ними.
У угла Маросейки, против большого с запертыми ставнями дома, на котором была вывеска сапожного мастера, стояли с унылыми лицами человек двадцать сапожников, худых, истомленных людей в халатах и оборванных чуйках.
– Он народ разочти как следует! – говорил худой мастеровой с жидкой бородйой и нахмуренными бровями. – А что ж, он нашу кровь сосал – да и квит. Он нас водил, водил – всю неделю. А теперь довел до последнего конца, а сам уехал.
Увидав народ и окровавленного человека, говоривший мастеровой замолчал, и все сапожники с поспешным любопытством присоединились к двигавшейся толпе.
– Куда идет народ то?
– Известно куда, к начальству идет.
– Что ж, али взаправду наша не взяла сила?
– А ты думал как! Гляди ко, что народ говорит.
Слышались вопросы и ответы. Целовальник, воспользовавшись увеличением толпы, отстал от народа и вернулся к своему кабаку.
Высокий малый, не замечая исчезновения своего врага целовальника, размахивая оголенной рукой, не переставал говорить, обращая тем на себя общее внимание. На него то преимущественно жался народ, предполагая от него получить разрешение занимавших всех вопросов.
– Он покажи порядок, закон покажи, на то начальство поставлено! Так ли я говорю, православные? – говорил высокий малый, чуть заметно улыбаясь.
– Он думает, и начальства нет? Разве без начальства можно? А то грабить то мало ли их.
– Что пустое говорить! – отзывалось в толпе. – Как же, так и бросят Москву то! Тебе на смех сказали, а ты и поверил. Мало ли войсков наших идет. Так его и пустили! На то начальство. Вон послушай, что народ то бает, – говорили, указывая на высокого малого.
У стены Китай города другая небольшая кучка людей окружала человека в фризовой шинели, держащего в руках бумагу.
– Указ, указ читают! Указ читают! – послышалось в толпе, и народ хлынул к чтецу.
Человек в фризовой шинели читал афишку от 31 го августа. Когда толпа окружила его, он как бы смутился, но на требование высокого малого, протеснившегося до него, он с легким дрожанием в голосе начал читать афишку сначала.
«Я завтра рано еду к светлейшему князю, – читал он (светлеющему! – торжественно, улыбаясь ртом и хмуря брови, повторил высокий малый), – чтобы с ним переговорить, действовать и помогать войскам истреблять злодеев; станем и мы из них дух… – продолжал чтец и остановился („Видал?“ – победоносно прокричал малый. – Он тебе всю дистанцию развяжет…»)… – искоренять и этих гостей к черту отправлять; я приеду назад к обеду, и примемся за дело, сделаем, доделаем и злодеев отделаем».
Последние слова были прочтены чтецом в совершенном молчании. Высокий малый грустно опустил голову. Очевидно было, что никто не понял этих последних слов. В особенности слова: «я приеду завтра к обеду», видимо, даже огорчили и чтеца и слушателей. Понимание народа было настроено на высокий лад, а это было слишком просто и ненужно понятно; это было то самое, что каждый из них мог бы сказать и что поэтому не мог говорить указ, исходящий от высшей власти.
Все стояли в унылом молчании. Высокий малый водил губами и пошатывался.
– У него спросить бы!.. Это сам и есть?.. Как же, успросил!.. А то что ж… Он укажет… – вдруг послышалось в задних рядах толпы, и общее внимание обратилось на выезжавшие на площадь дрожки полицеймейстера, сопутствуемого двумя конными драгунами.
Полицеймейстер, ездивший в это утро по приказанию графа сжигать барки и, по случаю этого поручения, выручивший большую сумму денег, находившуюся у него в эту минуту в кармане, увидав двинувшуюся к нему толпу людей, приказал кучеру остановиться.
– Что за народ? – крикнул он на людей, разрозненно и робко приближавшихся к дрожкам. – Что за народ? Я вас спрашиваю? – повторил полицеймейстер, не получавший ответа.
– Они, ваше благородие, – сказал приказный во фризовой шинели, – они, ваше высокородие, по объявлению сиятельнейшего графа, не щадя живота, желали послужить, а не то чтобы бунт какой, как сказано от сиятельнейшего графа…
– Граф не уехал, он здесь, и об вас распоряжение будет, – сказал полицеймейстер. – Пошел! – сказал он кучеру. Толпа остановилась, скучиваясь около тех, которые слышали то, что сказало начальство, и глядя на отъезжающие дрожки.
Полицеймейстер в это время испуганно оглянулся, что то сказал кучеру, и лошади его поехали быстрее.
– Обман, ребята! Веди к самому! – крикнул голос высокого малого. – Не пущай, ребята! Пущай отчет подаст! Держи! – закричали голоса, и народ бегом бросился за дрожками.
Толпа за полицеймейстером с шумным говором направилась на Лубянку.
– Что ж, господа да купцы повыехали, а мы за то и пропадаем? Что ж, мы собаки, что ль! – слышалось чаще в толпе.


Вечером 1 го сентября, после своего свидания с Кутузовым, граф Растопчин, огорченный и оскорбленный тем, что его не пригласили на военный совет, что Кутузов не обращал никакого внимания на его предложение принять участие в защите столицы, и удивленный новым открывшимся ему в лагере взглядом, при котором вопрос о спокойствии столицы и о патриотическом ее настроении оказывался не только второстепенным, но совершенно ненужным и ничтожным, – огорченный, оскорбленный и удивленный всем этим, граф Растопчин вернулся в Москву. Поужинав, граф, не раздеваясь, прилег на канапе и в первом часу был разбужен курьером, который привез ему письмо от Кутузова. В письме говорилось, что так как войска отступают на Рязанскую дорогу за Москву, то не угодно ли графу выслать полицейских чиновников, для проведения войск через город. Известие это не было новостью для Растопчина. Не только со вчерашнего свиданья с Кутузовым на Поклонной горе, но и с самого Бородинского сражения, когда все приезжавшие в Москву генералы в один голос говорили, что нельзя дать еще сражения, и когда с разрешения графа каждую ночь уже вывозили казенное имущество и жители до половины повыехали, – граф Растопчин знал, что Москва будет оставлена; но тем не менее известие это, сообщенное в форме простой записки с приказанием от Кутузова и полученное ночью, во время первого сна, удивило и раздражило графа.
Впоследствии, объясняя свою деятельность за это время, граф Растопчин в своих записках несколько раз писал, что у него тогда было две важные цели: De maintenir la tranquillite a Moscou et d'en faire partir les habitants. [Сохранить спокойствие в Москве и выпроводить из нее жителей.] Если допустить эту двоякую цель, всякое действие Растопчина оказывается безукоризненным. Для чего не вывезена московская святыня, оружие, патроны, порох, запасы хлеба, для чего тысячи жителей обмануты тем, что Москву не сдадут, и разорены? – Для того, чтобы соблюсти спокойствие в столице, отвечает объяснение графа Растопчина. Для чего вывозились кипы ненужных бумаг из присутственных мест и шар Леппиха и другие предметы? – Для того, чтобы оставить город пустым, отвечает объяснение графа Растопчина. Стоит только допустить, что что нибудь угрожало народному спокойствию, и всякое действие становится оправданным.
Все ужасы террора основывались только на заботе о народном спокойствии.
На чем же основывался страх графа Растопчина о народном спокойствии в Москве в 1812 году? Какая причина была предполагать в городе склонность к возмущению? Жители уезжали, войска, отступая, наполняли Москву. Почему должен был вследствие этого бунтовать народ?
Не только в Москве, но во всей России при вступлении неприятеля не произошло ничего похожего на возмущение. 1 го, 2 го сентября более десяти тысяч людей оставалось в Москве, и, кроме толпы, собравшейся на дворе главнокомандующего и привлеченной им самим, – ничего не было. Очевидно, что еще менее надо было ожидать волнения в народе, ежели бы после Бородинского сражения, когда оставление Москвы стало очевидно, или, по крайней мере, вероятно, – ежели бы тогда вместо того, чтобы волновать народ раздачей оружия и афишами, Растопчин принял меры к вывозу всей святыни, пороху, зарядов и денег и прямо объявил бы народу, что город оставляется.
Растопчин, пылкий, сангвинический человек, всегда вращавшийся в высших кругах администрации, хотя в с патриотическим чувством, не имел ни малейшего понятия о том народе, которым он думал управлять. С самого начала вступления неприятеля в Смоленск Растопчин в воображении своем составил для себя роль руководителя народного чувства – сердца России. Ему не только казалось (как это кажется каждому администратору), что он управлял внешними действиями жителей Москвы, но ему казалось, что он руководил их настроением посредством своих воззваний и афиш, писанных тем ёрническим языком, который в своей среде презирает народ и которого он не понимает, когда слышит его сверху. Красивая роль руководителя народного чувства так понравилась Растопчину, он так сжился с нею, что необходимость выйти из этой роли, необходимость оставления Москвы без всякого героического эффекта застала его врасплох, и он вдруг потерял из под ног почву, на которой стоял, в решительно не знал, что ему делать. Он хотя и знал, но не верил всею душою до последней минуты в оставление Москвы и ничего не делал с этой целью. Жители выезжали против его желания. Ежели вывозили присутственные места, то только по требованию чиновников, с которыми неохотно соглашался граф. Сам же он был занят только тою ролью, которую он для себя сделал. Как это часто бывает с людьми, одаренными пылким воображением, он знал уже давно, что Москву оставят, но знал только по рассуждению, но всей душой не верил в это, не перенесся воображением в это новое положение.