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

UptoLike

ВУЗ: 

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

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

Рубрика: 

23
то получим значение k.
Если каждую букву английского алфавита закодировать двоичным
пятиразрядным кодом и разбить передаваемое сообщение на пары букв,
то каждая пара будет кодироваться 10 двоичными символами. Будем
умножать вектор-строку A на векторы-столбцы кодов пар букв, при этом
будем получать шифрованное сообщение k
1
k
2
k
3
... Шифрование осу-
ществляется очень просто, а вот для расшифровки полученного сооб-
щения потребуется решать задачу о рюкзаке: по значению k находить
двоичный 10-разрядный вектор-столбец, при умножении на который век-
тора-строки A будет получено данное k. Эта задача явно односторон-
няя: легкое шифрование и очень трудное расшифрование. В принципе,
можно ее решать с помощью полного перебора (2
10
вариантов). Однако
трудности расшифрования будут одинаковыми как для криптоаналити-
ка, так и для легального получателя, что, безусловно, нежелательно.
Для того чтобы облегчить легальному получателю расшифровку сооб-
щения, нужно предложить ему “лазейку”. В данном случае “лазейка”
может быть устроена следующим образом. Рассмотрим сверхрасту-
щие векторы A = (a
1
a
2
a
3
...a
i
... a
n
), в которых a
i
>
1
1
i
l
l
a
−
=
∑
, т. е. каждый
элемент вектора A больше суммы всех предыдущих элементов. На-
пример, A = (25 27 56 112 231 452 916 1803). Нахождение элементов
вектора A, сумма которых дает заданное число k, элементарно (если
такое решение имеется). Действительно, пусть k = 1449. Поскольку
1449<1803, то последний элемент вектора не входит в решение. Далее,
так как 1449>916, то 916 обязательно входит в решение, так как сумма
всех предыдущих элементов меньше 916. Рассуждая аналогично, полу-
чаем код позиций выбираемых элементов: (1 0 1 0 0 1 1 0). Однако если
опубликовать этот сверхрастущий вектор, то и для криптоаналитика
задача расшифрования сообщений станет элементарной. Тогда мы пре-
образуем сверхрастущий вектор A в вектор B по следующему правилу:
выберем некоторый модуль m, больший суммы всех элементов A,
возьмем некоторое t, такое, что (t, m) = 1 и каждый элемент вектора B
будем вычислять по правилу: b
i
≡ a
i
⋅t mod m. Вектор B уже не будет
казаться сверхрастущим, и он может быть опубликован в качестве от-
крытого ключа. А в качестве “лазейки” для легального пользователя
сообщим ему значения t и m.

Страницы