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



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

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
  • d1 < d2 < d3 < d4
    11 < 13 < 17 < 19
  • d_1 * d_2 * \dots d_m > p * d_{n-m+2} * d_{n-m+3} * \dots * d_n
    d1 * d2 * d3 > p * d3 * d4
    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\}. Составим систему уравнений:

12 = M' \mod 13
13 = M' \mod 17
 2 = M' \mod 19

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

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

M \equiv M' \mod p
M \equiv 155 \equiv 2 \mod 3


Просмотров: 844


<<< Векторная схема разделения секрета
Схема Блэкли >>>