Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
В нашем примере 38 = 7-5 + 3, поэтому в заполненной таблице имеется 3 длинных и 4 коротких столбца. Согласно числовому ключу, начальные буквы криптограммы берутся из второго (по счету слева) столбца, он — длинный (так как первые три столбца — длинные), поэтому первые шесть букв образуют второй столбец. Следующие пять букв образуют пятый столбец (он — короткий). И так далее.
Более сложные маршрутные перестановки могут использовать другие геометрические фигуры и более “хитрые” маршруты, как, например, при обходе шахматной доски “ходом коня”, пути в некотором лабиринте и т.п. Возможные варианты зависят от фантазии составителя системы и, конечно, естественного требования простоты ее использования.
97
fлава 4
§ 4.2. Элементы криптоанализа шифров перестановки
Укажем сначала основные идеи, используемые при вскрытии вертикальных перестановок.
Заметим прежде всего, что буквы каждого столбца заполненного прямоугольника выписываются в криптограмму подряд, то есть криптограмма разбивается на отрезки, являющиеся столбцами таблицы. Поэтому при дешифровании следует попытаться соединить две группы последовательных букв криптограммы так, чтобы они образовывали хорошие (“читаемые”) с точки зрения обычного текста комбинации. Для этого естественно использовать наиболее частые биграммы открытого текста, которые можно составить из букв рассматриваемого шифрованного текста. Если для первой пробы выбрано, скажем, сочетание CT (самая частая биграмма русского языка), то мы можем по очереди приписывать к каждой букве С криптограммы каждую букву T из нее. При этом несколько букв, стоящих до и после данной буквы С, и несколько букв, стоящих до и после данной буквы Т, соединяются в пары, то есть получаются два столбца букв, записанные рядом:
I П
Конечно, мы не знаем длины столбцов, но некоторые ограничения на них можно получить, используя положение конкретных букв. Так, столбцы должны иметь одинаковые длины или первый столбец может быть длиннее второго на одну букву, и тогда эта буква — последняя буква сообщения:
98
Шифры перестановки
С T
А Б
M <—
последняя буква сообщения
Если приписываемые друг к другу буквы разделены, скажем, только двумя буквами, то, как легко видеть, мы можем составить в соседних столбцах не более трех пар, и длина каждого столбца не превышает четырех. Кроме того, ограничением может послужить появление запретной биграммы (например, гласная — мягкий знак):
А Ь
запретная биграмма
Для выбранного сочетания CT получается по одной паре столбцов для каждого конкретного выбора букв С и T из криптограммы, и из них целесообразно отобрать ту пару, которая содержит наиболее частые биграммы.
Заметим, что при автоматизации этого процесса можно приписать каждой биграмме вес, равный частоте ее появления в открытом тексте. Тогда целесообразно отобрать ту пару столбцов, которая имеет наибольший вес. Кстати, появление одной биграммы с низкой частотой может указать на то, что длину столбца надо ограничить.
Выбрав пару столбцов, мы аналогичным образом можем подобрать к ним третий (справа или слева) и т. д. Описанная процедура значительно упрощается при использовании вероятных слов, то есть слов, которые могут встретиться в тексте с большой вероятностью.
Рассмотрим также метод, применимый к любым шифрам перестановки. Допустим, что к двум или более сообщениям (или
99
Г лава 4
отрезкам сообщений) одинаковой длины применяется один и тот же шифр перестановки. Тогда очевидно, что буквы, которые находились на одинаковых местах в открытых текстах, окажутся на одинаковых местах и в шифрованных текстах.
Выпишем зашифрованные сообщения одно под другим так, что первые буквы всех сообщений оказываются в первом столбце, вторые — во втором и т. д. Если предположить, что две конкретные буквы в одном из сообщений идут одна за другой в открытом тексте, то буквы, стоящие на тех же местах в каждом из остальных сообщений, соединяются подобным же образом. Значит, они могут служить проверкой правильности первого предположения, подобно тому как комбинации, которые дают два столбца в системе вертикальной перестановки, позволяют проверить, являются ли соседними две конкретные буквы из этих столбцов. К каждому из указанных двухбуквенных сочетаний можно добавить третью букву для образования триграммы и т. д. Если располагать не менее чем четырьмя сообщениями одинаковой длины, то можно с уверенностью гарантировать их вскрытие подобным образом.
Контрольные вопросы
1. Приведите пример шифра перестановки, который может рассматриваться и как блочный шифр замены.
2. Как определить по криптограмме, полученной с помощью шифра вертикальной перестановки, число коротких столбцов заполненного открытым текстом основного прямоугольника?
3. Какие свойства открытого текста используются при вскрытии шифра вертикальной перестановки?
4. Сколько ключей имеет шифр поворотной решетки (см. главу I). На основе прямоугольника размером т х п?
5. Каким образом можно использовать вероятные слова для вскрытия ряда криптограмм, полученных на одном ключе шифра перестановки?
