Схема Асмута

Схема Асмута — Блума — пороговая схема разделения секрета, построенная с использованием простых чисел. Позволяет разделить секрет (число) между $n$ сторонами таким образом, что его смогут восстановить любые $m$ участников.

Описание

Пусть $M$ - некоторый секрет, который требуется разделить. Выбирается простое число $p$, большее $M$. Выбирается $n$ взаимно простых друг с другом чисел $d_1, d_2, \dots, d_n$, таких что:

• $\forall i:d_i > p$
• $\forall i:d_i < d_{i+1}$
• $d_1 * d_2 * \dots d_m > p * d_{n-m+2} * d_{n-m+3} * \dots * d_n$

Выбирается случайное число $r$ и вычисляется

$M' = M + r p$

Вычисляются доли:

$k_i = M' \mod d_i$

Участникам раздаются $\left\{p, d_i, k_i\right\}$

Теперь, используя китайскую теорему об остатках можно восстановить секрет $M$ имея $m$ и более долей.

Пример

Предположим нам нужно разделить секрет $M=2$ между 4-мя участниками таким образом, чтобы любые 3 из них могли этот секрет восстановить (а два участника — не могли бы). То есть нужно реализовать (3,4)-пороговую схему.

В качестве простого числа выберем $p=3$, в качестве взаимно простых - $11, 13, 17, 19$. Проверяем, что:

• $\forall i:d_i > p$

  $\forall i: i \in \{11, 13, 17, 19\}, i > p = 3$

• $d_1 < d_2 < d_3 < d_4$

  $11 < 13 < 17 < 19$

• $d_1 * d_2 * \dots d_m > p * d_{n-m+2} * d_{n-m+3} * \dots * d_n$

  $d_1 * d_2 * d_3 > p * d_3 * d_4$

  $11 * 13 * 17 > 3 * 17 * 19$

Выбираем случайное число $r = 51$ и вычисляем:

$M' = M + r p = 2 + 51 * 3 = 155$

Вычисляем доли:

$k_i = M' \mod d_i$

$k_1 = 155 \mod 11 = 1$

$k_2 = 155 \mod 13 = 12$

$k_3 = 155 \mod 17 = 2$

$k_4 = 155 \mod 19 = 3$

Теперь попробуем восстановить исходный секрет, имея на руках доли $\left\{3, 11, 1\right\}$, $\left\{3, 13, 12\right\}$, $\left\{3, 17, 2\right\}$. Составим систему уравнений:

$12 = M' \mod 13$

$13 = M' \mod 17$

$2 = M' \mod 19$

Мы можем восстановить $M'$, используя китайскую теорему об остатках.

Зная $M'$ мы восстанавливаем секрет.

$M \equiv M' \mod p$

$M \equiv 155 \mod 3 \equiv 2$

В данном примере, т.к. 155<17*19, то 2 участника спокойно восстановят секрет:) M' должно быть больше произведения долей неавторизованных участников.

Литература

• Шнайер Б. Схема Асмута-Блума // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 589—590. — 816 с. — 3000 экз. — ISBN 5-89392-055-4
• C. Asmuth, J. Bloom A modular approach to key safeguarding // Information Theory, IEEE Transactions on. — 1983. — В. 2. — Т. 29. — ISSN 0018-9448.