Схема Асмута Блума

Интернет магазин китайских планшетных компьютеров

Компьютеры - Схема Асмута Блума

23 января 2011

Схема Асмута — Блума — пороговая схема разделения секрета, построенная с использованием простых чисел. Позволяет разделить секрет между 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 + rp

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

$k_i = M' \mod d_i$

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

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

Пример

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

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

$\forall i:d_i > p$

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

d₁ < d₂ < d₃ < d₄

11 < 13 < 17 < 19

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

d₁ * d₂ * d₃ > p * d₃ * d₄

11 * 13 * 17 > 3 * 17 * 19

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

M' = M + rp = 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\}$ . Составим систему уравнений: