Составители:
Рубрика:
43
(26, 0, 13, 11, 23, 25)
(2, 7, 15, 12, 27, 6)
(1, 3 , 24, 6, 0, 16)
(12, 2, 7, 0, 7, 0)
Для последнего, пятого сотрудника вычисленный фрагмент имеет
вид:
(14, 1, 20, 8, 1, 0).
Легко проверяется, что сложение всех фрагментов (каждый элемент
складывается по модулю 29) дает полный секретный ключ (26, 13, 21, 8,
0, 18)
Следует заметить, что сложность подбора секретного ключа в рас-
смотренном случае зависит только от значения модуля p и числа эле-
ментов k и практически не зависит от количества сотрудников n.
Рассмотрим случай, когда h < n. Имеется несколько вариантов ре-
шения такой пороговой задачи.Приведем алгоритм, описанный в [2].
Он основан на модульной арифметике и китайской теореме об остатках.
Имеется n участников A
1
, A
2
, A
3
, …, A
n
. Пусть m
i
, i = 1, 2, …n, целые
числа, большие 1, такие, что (m
i
, m
j
) = 1 при i ≠j. Обозначим М – произ-
ведение всех чисел m
i
, т. е. М = m
1
m
2
m
3
…, m
i
, …m
n
.
Обозначим также M
i
– произведение всех m
j
(j = 1, 2, …, i–1, i+1, …, n),
кроме m
i
, т. е. M
i
= M / m
i
. Вычислим значения N
i
из условия: M
i
N
i
≡
≡1 mod m
i
. Поскольку (M
i
, m
i
) = 1, то решение всегда существует и все
N
i
будут найдены.
Если имеется n сравнений вида: x ≡ a
i
mod m
i
, i = 1, 2, …, n, a
i
–
целые, то общее решение этих сравнений имеет вид:
1
.
n
iii
i
xaMN
=
=
∑
Кроме того, это решение единственное, т. е. любое другое решение
y удовлетворяет сравнению: y ≡ x mod M.
Пусть теперь h фиксированный порог, 1 < h ≤ n. Обозначим через
min(h) – наименьшее из h произведений m
i
, а max(h–1) – наибольшее из
h–1 произведений m
i
. Если выполнены условия:
min(h) – max(h–1) ≥ 3 max(h–1) ( ∗ )
и max(h–1) < c < min(h) (∗∗)
то множество {a
1
, a
2
, …, a
t
}, где a
i
≡ c mod m
i
, образует (h, n) пороговую
схему для с [ 2 ]. Это означает, что если c – некоторый секретный ключ,
Страницы
- « первая
- ‹ предыдущая
- …
- 41
- 42
- 43
- 44
- 45
- …
- следующая ›
- последняя »
