Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Увеличение значности шифробозначений делает шифр неэкономным, поэтому получили распространение шифры, использующие одно- и двузначные шифробозначения, подобные рассмотренному выше в примере цифровому шифру. Понятно, что для таких шифров наибольшую повторяемость в шифртексте имеют цифры, с которых начинаются двузначные шифробозначения. Выдвигая гипотезы о таких цифрах и отмечая в шифртексте соответствующие двузначные шифробозначения, можно восстановить и однозначные шифробозначения, оказавшиеся в шифртексте между некоторыми двузначными шифробозначениями. Дальнейшая работа по вскрытию открытого текста для разнозначного шифра ничем не отличается от уже знакомой нам работы для однобуквенной простой замены.
112
Шифры замены
§ 5.3. Блочные шифры простой замены
Как мы убедились, задача вскрытия простой однобуквенной замены является не слишком сложной. Основная слабость такого шифра состоит в том, что избыточность открытого текста, полностью проникающая в шифртекст, делает (за счет малого числа шифрвеличин, которыми являются буквы алфавита) очень рельефной диаграмму повторяемости знаков криптограммы. Это побудило в свое время криптографов к устранению этой слабости за счет увеличения числа шифрвеличин. Интуитивно понятно, что чем больше разница между числом шифрвеличин и числом букв алфавита, тем более равномерной должна стать диаграмма повторяемости знаков шифртекста. Первым естественным шагом в этом направлении стало увеличение значности шифрвеличин, то есть использование блочных шифров простой замены.
Простейший блочный шифр оперирует с биграммными шифрвеличинами. Одними из первых таких шифров были биграммные шифры Порта и Плейфера (см. гл. 1). Приведем описание шифра Плейфера, нашедшего широкое применение в начале нашего века.
Основой шифра Плейфера является прямоугольная таблица, в которую записан систематически перемешанный алфавит (для удобства запоминания). Правило зашифрования состоит в следующем.
Буквы биграммы (/, /), / Ф j (являющейся шифрвеличи-ной) находятся в данной таблице. При зашифровании биграмма (/,У) заменяется биграммой (&,/), где к и / определяются в соответствии с правилами 1-3.
1. Если / и j не лежат в одной строке или одном столбце, то их позиции образуют противоположные вершины прямоугольника. Тогда к и I — другая пара вершин, причем к — вершина, лежащая в той же строке, что и /.
2. Если і и j лежат в одной строке, то к и / — буквы той же строки, расположенные непосредственно справа от / и j
113
І лава b
соответственно. При этом если одна из букв — последняя в строке, то считается, что ее “правым соседом” является первая буква той же строки.
3. Аналогично, если / и j лежат в одном столбце, то они заменяются их “соседями снизу”.
Наглядно правило зашифрования можно проиллюстрировать следующим образом.
В случае 1:
В случае 2:
і к . • j і
В случае 3:
При зашифровании открытый текст представляется в виде последовательности биграмм. Если текст имеет нечетную
114
Шифры замены
длину или содержит биграмму, состоящую из одинаковых букв, то в него добавляются “пустышки” следующим образом. “Пустышкой” является некоторая редкая для данного типа текста буква (или знак), которая вставляется между одинаковыми буквами биграммы или добавляется в текст для того, чтобы его длина стала четной. Такие изменения открытого текста, как правило, не мешают при расшифровании. Проиллюстрируем сказанное следующим примером.
Пример (шифра Плейфера)
Пусть шифр использует прямоугольник размером 5 х 6, в который записан систематически перемешанный русский 30-буквенный алфавит на основе ключевого слова командир:
к О M а H д
и P б в г е
ж 3 л п с T
У ф X ц ч ш
щ ь ы э ю я
Зашифруем фразу “автором метода является Уитстон”. В качестве “пустышки” будем использовать редкую букву ф. Представим фразу в виде последовательности биграмм:
AB ТО PO MO ME ТО ДА ЯВ ЛЯ ET ТЯ УИ TC ТО HO
(Нам пришлось дважды вставить “пустышку”.)
В соответствии со сформулированными правилами получаем шифртекст:
ВП ЗД ЗР OX ДБ ЗД KH ЭЕ ТЫ ТШ ШД ЩЖ ЖТ ЗД 04
или без пробелов
впздзрохдбздкнэетытшшдщжжтздоч
115
І лава 5
Криптоанализ шифра Плейфера опирается на частотный анализ биграмм, триграмм и четырехграмм шифртекста и особенности замены шифрвеличин на шифробозначения, связанные с расположением алфавита в прямоугольнике. При этом существенную информацию о заменах дает знание того, что используется систематически перемешанный алфавит. Замечательный пример вскрытия криптограммы, полученной применением шифра Плейфера, приведен в [Sal96].
Шифрвеличинами для другого широко известного блочного шифра — шифра Хилла (названного по имени Лестора Хилла) — являются п -граммы открытого текста (п> 2 ), представленного некоторым числовым кодом (так что алфавитом открытого текста служит кольцо вычетов по модулю мощности алфавита Zm ).
Правило зашифрования представляет собой линейное преобразование кольца Zm: если х = (хХ9...,хп) —«-грамма
открытого текста, к = (ktJ) — некоторая обратимая матрица
