Дискретная математика. Математические вопросы криптографии. Ерош И.Л. - 44 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

44
а a
i
– фрагменты ключа, розданные n участникам, то любые h из участ-
ников смогут восстановить значение c по его фрагментам, а любые
h–1 участников сделать это не смогут (без перебора вариантов). При
этом чем больше в (∗) разность, тем труднее h–1 участникам подо-
брать секретный ключ по своим фрагментам.
Пример.
Пусть n = 5 и m
1
= 97; m
2
= 98, m
3
= 99, m
4
= 101, m
5
= 103.
Возьмем h = 3 и вычислим min(3) = (97 ⋅ 98 ⋅ 99) = 941094; max(2) =
=(101 ⋅ 103) = 10403. Неравенство (∗) примет вид:
941094 – 10403 = 930691 > 3 ⋅ 10403 = 31209.
Секретное число с должно лежать в пределах (∗∗). Пусть оно изве-
стно некоторому сотруднику, разделяющему секрет, который вычислил
значения a
i
(i = 1, 2, …, 5) из условий a
i
≡ c mod m
i
и раздал фрагменты
секрета пяти участникам: a
1
= 62, a
2
= 4, a
3
= 50, a
4
= 50, a
5
= 38.
Пусть теперь трое из пяти участников, например, A
2
, A
3
и A
4
пытают-
ся восстановить секретный ключ c по своим фрагментам. Поскольку
каждый участник знает только свое значение m
i
, то они вычисляют:
M
2
’ = m
3
⋅ m
4
= 9999; M
3
’ = m
2
⋅ m
4
= 9898; M
4
’ = m
2
⋅ m
3
= 9702,
а затем соответствующие значения N
i
: N
2
= 33, N
3
= 49, N
4
= 17. После
чего находят значение y = 4 ⋅ 9999 ⋅ 33 + 50 ⋅ 9898 ⋅ 49 + 50 ⋅ 9702 ⋅ 17 =
=33816668. Секретный ключ вычисляется из сравнения: c ≡ y mod (m
2
⋅ m
3
⋅ m
4
).
Таким образом,
c ≡ 33816668 mod (98 ⋅ 99 ⋅ 101) ≡ 500000 mod 979902.
Если взять любую другую тройку клиентов, например, A
1
, A
4
, A
5
, то
они вычислят тот же секретный ключ с = 500000.
Пусть теперь двое клиентов, например, A
2
и A
5
пытаются найти сек-
ретный ключ с. Они вычисляют значения y = 4 ⋅ 103 ⋅ 59 + 38 ⋅ 98 ⋅ 41 =
≡176992 ≡ 5394 ≡ с mod 10094. Они понимают, что истинный секретный
ключ находится из условий: 5394 + i ⋅ 10094, но значения i не знают.
Количество значений i определяется как целая часть дроби:
() ( )
()
min max 1 1
.
max 1
hh
h
−−−
−
Для рассматриваемого примера целая часть дроби равна 89, т. е. двум
участникам потребуется перебрать 89 вариантов ключа. В реальных усло-
виях количество вариантов может быть сделано существенно большим.

Страницы