Составители:
Рубрика:
24
2.3. Пример использования рюкзачных систем
для криптографии с открытым распределением ключей
Пусть A – сверхрастущая последовательность чисел: (1 2 4 8 16).
Легко видеть, что a
i
>
1
1
i
l
l
a
−
=
∑
, т. е. суммы всех предыдущих значений.
Передаваемые сообщения пусть представляют собой следующие
пятиразрядные двоичные коды:
w
1
= (1 0 1 1 0); w
2
= ( 0 1 1 0 1); w
3
= ( 1 0 0 0 1).
Выполним сильное модульное преобразование вектора A. Для этого
выберем значение модуля m так, чтобы он был больше суммы всех a
i
.
Одновременно нужно выбрать t так, чтобы (t, m) = 1.
При этом желательно, чтобы даже первые значения a
i
t были бы боль-
ше модуля m (чтобы и по ним нельзя было бы сразу определить t). Вы-
бираем t = 40 и m = 37.
Элементы вектора B получаются следующим образом: b
i
≡ a
i
t mod m.
Сам вектор B = (3 6 12 24 11). Он уже не является сверхрастущим век-
тором, поэтому криптоанализ будет затруднен. Умножая вектор B на
матрицу, составленную из двоичных векторов w
i
, получаем зашифро-
ванный текст:
B⋅W = (3 6 12 24 11) ⋅
101
010
110
100
011
= (39 29 14) = X,
где X – вектор шифрованного сообщения.
Именно этот шифрованный текст передается по каналу связи и мо-
жет быть перехвачен криптоаналитиком. Кроме того, считается, что
ключ (вектор B) также открыто сообщается всем (как получателю со-
общения, так и может быть перехвачен любым пользователем сети).
Значения t и m являются “лазейкой” для легального получателя сооб-
щений. Он находит значение u такое, что t⋅u ≡ 1 mod m. В нашем случае
легко находится u = 25, так как 40⋅25 ≡ 1 mod 37.
Страницы
- « первая
- ‹ предыдущая
- …
- 22
- 23
- 24
- 25
- 26
- …
- следующая ›
- последняя »
