Книга шифров. Тайная история шифров и их расшифровки
Шрифт:
(5) Длина ключа составляется 10 букв, и он повторяется 2 раза.
(6) Длина ключа составляется 20 букв, и он повторяется 1 раз.
Первая возможность может быть исключена, так как ключ, длина которого составляет всего 1 букву, сразу же приводит к одноалфавитному шифру; для шифрования всего текста будет использоваться только одна строка квадрата Виженера, и шифралфавит не будет меняться. Крайне маловероятно, чтобы криптограф так поступил. Чтобы показать все другие возможности, в соответствующей колонке таблицы 8 поставлен символ . Каждый символ указывает возможную длину ключа.
Чтобы определить, какова длина ключа, то есть будет ли она составлять 2,4, 5,10 или 20 букв, нам понадобится рассмотреть множители и всех остальных интервалов между повторениями. Поскольку, по всей видимости, длина ключевого слова составляет 20 букв или меньше, в таблице 8 для всех этих интервалов указаны те множители, которые не превышают 20. Здесь явно прослеживается тенденция делимости интервалов на 5. Фактически на 5 делятся все интервалы. Первая повторяющаяся последовательность, Е-F-I-Q, может
Третья повторяющаяся последовательность, W-С-Х-Y-М, может быть объяснена тем, что ключевое слово длиной 5 букв между первой и второй последовательностями повторилось четыре раза. Четвертая повторяющаяся последовательность, Е-Т-R-L, может быть объяснена тем, что ключевое слово длиной 5 букв между первой и второй последовательностями повторилось двадцать четыре раза. Короче говоря, все указывает на наличие пятибуквенного ключевого слова.
Предположим, что длина ключевого слова действительно составляет 5 букв; тогда следующий этап будет заключаться в том, чтобы найти эти буквы. Пока обозначим ключевое слово в виде L1– L2– L3– L4– L5, где L1будет первой буквой ключевого слова, L2 — второй, и так далее. Тогда процесс шифрования начнется с зашифровывания первой буквы открытого текста в соответствии с первой буквой ключевого слова Буква определяет строку квадрата Виженера и, тем самым, задает одноалфавитный шифр замены для первой буквы открытого текста. Однако когда наступает время для зашифровывания второй буквы открытого текста, криптограф должен использовать L2, чтобы определить другую строку квадрата Виженера, задавая тем самым уже иной одноалфавитный шифр замены. Третья буква открытого текста будет зашифровываться в соответствии с L3, четвертая — в соответствии с L4, а пятая — в соответствии с L5. Каждая буква ключевого слова задает для шифрования свой отличающийся шифралфавит. Но затем шестая буква открытого текста будет опять зашифровываться в соответствии с L1, седьмая буква — в соответствии с L2, и далее цикл повторяется. Другими словами, в нашем случае многоалфавитный шифр состоит из пяти одноалфавитных шифров, причем каждый одноалфавитный шифр отвечает за шифрование 1/5 части всего сообщения. Но самое главное состоит в том, что нам уже известно, как проводить криптоанализ одноалфавитных шифров.
Таблица 8 Повторяющиеся последовательности и интервалы между ними в шифртексте.
Поступим следующим образом. Мы знаем, что одна из строк квадрата Виженера, определяемая буквой задает шифралфавит, которым зашифрованы 1-я, 6-я, 11-я, 16-я… буквы сообщения. Поэтому если возьмем 1-ю, 6-ю, 11-ю, 16-ю… буквы шифртекста, то мы сможем применить добрый, старый частотный анализ для определения данного шифралфавита. На рисунке 14 показано частотное распределение букв, которые стоят на 1-м, 6-м, 11-м, 16-м… местах шифртекста; это буквы W, I, R, Е… Здесь следует напомнить, что каждый шифралфавит в квадрате Виженера — это просто обычный алфавит, сдвинутый на 1… 26 позиций. Поэтому частотное распределение на рисунке 14 должно иметь те же особенности, что и частотное распределение стандартного алфавита, за исключением того, что оно будет сдвинуто на некоторое расстояние. Сравнивая распределение L1 со стандартным распределением, можно определить величину сдвига. На рисунке 15 показано стандартное частотное распределение для отрывка английского открытого текста.
В стандартном распределении имеются пики, плато и впадины, и, чтобы сравнить его с распределением шифра L1 поищем наиболее заметные особенности и их комбинации. Так, весьма характерную особенность в стандартном распределении (рис. 15) составляют три пика у R-S-Т и длинная ложбина справа от них, которая захватывает шесть букв от U до Z включительно. В распределении (рис. 14) есть только один похожий участок с тремя пиками у V-W-Х и последующей впадиной, простирающейся вдоль шести букв от Y до D. А это означает, что все буквы, зашифрованные в соответствии с L1 были сдвинуты на четыре позиции, и L1 определяет шифралфавит, который начинается с Е, F, G, Н…, то есть первая буква ключевого слова, L1 это, по всей видимости, Е. Данное предположение может быть проверено путем сдвига распределения на четыре буквы назад и сравнения его со стандартным распределением. На рисунке 16 даны для сравнения оба распределения. Совпадение между основными пиками очень хорошее, так что нет никаких сомнений, что ключевое слово действительно начинается с буквы Е.
Рис. 14 Частотное распределение букв в зашифрованном с помощью шифралфавита L1 тексте (число появлений букв).
Рис. 15 Стандартное частотное распределение букв (число появлений букв на основе отрывка открытого текста, содержащего то же самое количество букв, что и в шифртексте).
Подведем итоги. Поиск повторений в шифртексте позволил нам определить длину ключевого слова, которое, как оказалось, состоит из пяти букв. Это позволило нам разделить шифртекст на пять частей, где каждая часть зашифрована с помощью шифра одноалфавитной замены, который определяется одной буквой ключевого слова. При анализе той части шифртекста, которая была зашифрована в соответствии с первой буквой ключевого слова, мы смогли показать, что эта буква, L1, является, по-видимому, буквой Е. Этот же прием применяется и для поиска второй буквы ключевого слова. Выясняется распределение частот появления 2-й, 7-й, 12-й, 17-й… букв в шифртексте, и получившееся распределение, приведенное на рисунке 17, снова сравнивается со стандартным распределением, после чего находится величина сдвига.
Это распределение анализировать сложнее. Явных кандидатов для трех соседствующих пиков, которые соответствуют буквам R-S-T, не находится. Однако отчетливо видна ложбина, которая тянется от G до L и которая, видимо, соответствует ложбине, идущей от U до Z в стандартном распределении. Если это так, то можно ожидать, что пики, соответствующие R-S-T, появятся у букв D, Е и F, однако пика у буквы Е не наблюдается.
Рис. 16 Распределение L1 сдвинутое на четыре буквы назад (вверху), в сравнении со стандартным частотным распределением (внизу). Совпадают все основные пики и впадины.
Рис. 17 Частотное распределение букв в зашифрованном с помощью шифралфавита L2 тексте (число появлений букв).
Забудем пока об отсутствующем пике, посчитав его статистическим выбросом, и продолжим наш анализ, предполагая, что ложбина от G до L как раз и является той самой отличительной особенностью. Отсюда следует, что все буквы, зашифрованные в соответствии с L2, были сдвинуты на двенадцать позиций, и L2 определяет шифралфавит, который начинается с М, N, О, Р…, то есть второй буквой ключевого слова, L2, является М. Данное предположение вновь может быть проверено путем сдвига распределения L2 на двенадцать букв назад и сравнения его со стандартным распределением.
На рисунке 18 даны для сравнения оба распределения. Совпадение между основными пиками очень хорошее, так что нет никаких сомнений, что второй буквой ключевого слова действительно является м.
Я не буду продолжать дальнейшее рассмотрение; достаточно сказать, что при анализе 3-й, 8-й, 13-й… букв третьей буквой ключевого слова будет буква I, при анализе 4-й, 9-й, 14-й… букв четвертой буквой ключевого слова будет L, а при анализе 5-й, 10-й, 15-й… букв пятой буквой ключевого слова будет Y. Ключевым словом является EMILY. Теперь можно завершить криптоанализ. Первая буква шифртекста — W, и она была зашифрована в соответствии с первой буквой ключевого слова Е. Будем действовать в обратном порядке:
Рис. 18 Распределение L2, сдвинутое назад на двенадцать букв (вверху), в сравнении со стандартным частотным распределением (внизу). Совпадают все основные пики и впадины
возьмем квадрат Виженера и поищем W в ряду, начинающемся с буквы Е, а затем посмотрим, какая буква находится вверху этого столбца. Этой буквой будет буква в, которая и будет первой буквой открытого текста. Повторяя эту операцию шаг за шагом, мы получим открытый текст, который начинается следующим образом: sittheedow-nandhavenoshamecheekbyjol… Вставив в соответствующих местах пробелы между словами и знаки пунктуации, приведем открытый текст к окончательному виду: