Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Однако благодаря своей простоте подобные подстановочные шифры нашли широкое применение в современных алгоритмах шифрования с секретным ключом. Далее будет показано, что простые подстановочные ключи играют основную роль в стандартах DES (раздел 7.6) и AES (раздел 7.7). Общепризнанно, что комбинация простых подстановочных шифров образует алгоритм шифрования, имеющий повышенную стойкость. По этой причине простые шифры широко используются и по сей день. Кроме того, простые подстановочные шифры часто применяются в криптографических протоколах. Демонстрация этого факта содержится в разделе 7.5 и во многих других частях книги.
?fc(m) <— тп + fc(modiV), Щс) <- с - fc(mod N),
(7.3.1)
(7.3.2)
^k(fn) <— k\rn + /^(modiV), Т>к{с) *- fef^c- fc2)(modiV).
(7.3.3)
254
Часть III. Основные методы криптографии
7.3.2 Полиалфавитные шифры
Подстановочный шифр называется полиалфавитным (polyalphabetic cipher), если элемент исходного сообщения в пространстве V можно заменить несколькими элементами пространства зашифрованных сообщений С.
Наиболее известным из полиалфавитных шифров является шифр Виженера (Vigenere cipher). Этот шифр основан для подстановке строк: ключ представляет собой строку, состоящую из большого количества символов. Пусть т — длин на ключа. Тогда строка исходного текста разбивается на фрагменты, состоящие из т символов, причем последний фрагмент может содержать меньшее количество символов. Алгоритм шифрования поочередно применяет сдвиговый шифр к строке ключа и каждой строке исходного текста, при необходимости повторяя применение ключа снова. Расшифровка выполняется аналогично.
Пример 7.2 (Шифр Виженера). Пусть ключевой строкой является слово gold. Используя правило шифрования А = О, В = 1,..., Z = 25, преобразуем ключевое слово в кортеж (6,14,11,3). Применение шифра Виженера к строке исходного! текста
proceed meeting as agreed сводится к выполнению посимвольного сложения по модулю 26.
15 17 14 2 4 4 3 12 4 4 19 6 14 11 3 6 14 11 3 6 14 11 ~21 5 25 5 10 18 14 15 10 18 4~
8 13 6 0 18 0 6 17 4 4 3 3 6 14 11 3 6 14 11 3 6 14 11 19 20 11 21 6 20 2 7 10 17
Следовательно, зашифрованная строка будет выглядеть так.
vfzfkso pkseltu lv guchkr D
Другими примерами известных полиалфавитных шифров является книжный шифр (book cipher), называемый также шифром Биле (Beale cipher), в котором ключевой строкой является условленная строка книги, и шифр Хилла (Hill cipher). Подробное описание этих подстановочных шифров содержится в книгах [93] и [284].
Глава 7. Шифрование — симметричные методы
255
7.3.3 Шифр Вернама и одноразовый блокнот
Шифр Вернама (Veraam cipher) — одна из простейших криптосистем. Предположим, что сообщение и ключ представляют собой строки из п двоичных разрядов:
т = Ь1Ь2...Ьпе{0,1}п, к = к!к2...кпе и{0,1}п.
(Обратите внимание на символ €{/: число к извлекается из равномерно распределенной генеральной совокупности.) Шифрование выполняется бит за битом, а зашифрованная строка с = С1С2... сп образуется путем применения побитовой операции XOR ("исключительное или") к каждому биту сообщения и соответствующему биту ключа:
С% = Ъ% ф ki,
где 1 ^ г ^ п, а операция $ определена следующим образом:
е 0 1
0 0 1
1 1 0
Расшифровка выполняется аналогично шифрованию, поскольку операция © является сложением по модулю 2, а значит, вычитание идентично сложению.
Если АЛ = С = /С = {0,1}*, шифр Вернама представляет собой частный случай подстановочных шифров. Если ключевая строка используется только один раз, шифр Вернама удовлетворяет двум требованиям повышенной стойкости, предъявляемым к подстановочным шифрам. В разделе 7.5 мы покажем, что секретность, обеспечиваемая однократным применением шифра Вернама, является секретностью в теоретико-информационном смысле, т.е. безусловной. Для того чтобы убедиться в этом, достаточно проверить, что строка зашифрованного текста с не предоставляет перехватчику никакой информации о строке исходного сообщения т, поскольку если ключ к равен с © т, то строка с может порождаться любой строкой т (бит за битом).
Одноразовый шифр Вернама называется также шифром одноразового блокнота (one-time pad cipher). В принципе, если некий шифр удовлетворяет двум требованиям повышенной стойкости, предъявляемым к подстановочным шифрам (см. раздел 7.5), то любой подстановочный шифр является шифром одноразового блокнота. Однако шифрами одноразового блокнота принято называть только шифры, использующие побитовую операцию XOR.
В сравнении с другими подстановочными шифрами (например, сдвиговым шифром, использующим сложение по модулю 26), побитовую операцию XOR
256
Часть III. Основные методы криптографии!
(т.е. сложение по модулю 2) можно легко реализовать с помощью электроннгД схемы. По этой причине побитовая операция XOR широко используется при раз] работке современных алгоритмов шифрования с секретным ключом. Кроме того, она применяется в двух важных современных шифрах: DES (раздел 7.6) и AES (раздел 7.7).
