147

использования, являются подспорьем для криптоаналитика.

Выравнивание цепочек

В результате анализа, который показывает, что цепочки равной длины появляются в парах, также становится ясно, как использовать эту особенность для идентификации колеса R1 и его угловой установки. Для этого нам необходимо выровнять друг относительно друга пары цепочек одинаковой длины, при этом одна из цепочек такой пары должна быть выписана в обратном порядке. При этом нам придется опробовать все возможные варианты выравнивания букв. Так, для двух полученных выше 10-значных цепочек существует 20 возможных взаимных расположений, в зависимости от того, какая из двух цепочек выписывается в обратном порядке, а также от того, какая буква стоит первой. Вот одно из возможных взаимных расположений:

ABQNUMLPIR

CHGYVTJSKD

Кроме него, имеются еще 19 других, например:

CDKSJTVYGH

IPLMUNQBAR.

Если две взаимосвязанные цепочки выровнены правильно, то вертикальные пары букв при зашифровании с помощью правильного колеса R1 в его первом угловом положении дают пары составного отражателя, а пары, расположенные вдоль диагонали (из левого верхнего в правый нижний угол) при зашифровании колесом R1 в его втором угловом положении должны дать те же самые пары составного отражателя. При неправильном выборе колеса или его угловой установки получаются противоречия. Эта чрезвычайно важная особенность, являющаяся следствием порядка действий, который был предписан при работе с "Энигмой", была обнаружена польскими криптоаналитиками в 1932 году (доказательство приводится в [9.1]). В приведенном примере рассмотрены несколько коротких цепочек и, поскольку возможных вариантов выравнивания здесь меньше, с них, возможно, и следовало бы начать.

148

Идентификация колеса R1 и его угловой установки

Чтобы разобрать здесь пример идентификации колеса R1 и его угловой установки на полномасштабной "Энигме" с известными колесами, но с неизвестным коммутатором, потребовалось бы большое количество данных и многостраничный анализ. Тем не менее, криптоаналитики были вынуждены ежедневно решать именно эту задачу. Этот метод можно проиллюстрировать с помощью данных из вышеприведенного примера с 12-буквенной "мини-Энигмой". Предположим, что коммутатор известен, и что необходимо выяснить, может ли являться колесом R1 какое-нибудь из известных колес в одном из 12 возможных начальных угловых положений. Поскольку существует много неверных вариантов, мы рассмотрим только два случая: один неправильный, другой правильный.

Пример 9.3.

Допустим, что приведенные выше пары одинаковых букв в 12-буквенной "мини-Энигме" зашифрованы в последовательных угловых положениях колеса при одинаковых базовых угловых установках, причем таблица зашифрования для колеса R1 приведена в таблице 9.2.

Таблица 9.2.

Показать, что выравнивание цепочек в виде

D AICJK

HBLFGE

(1)приводит к противоречиям, если предположить, что колесо R1 первоначально находится в 1-м угловом положении, но

(2)приводит к решению, если предположить, что колесо R1 первоначально находится во 2-м угловом положении.

149

Решение

(1) Начнем с зашифрования вертикальных пар из цепочек в 1-м угловом положении, и диагональных пар (левый верхний - правый нижний угол)- во 2-м угловом положении. 12 пар, которые мы получим, не должны противоречить друг другу; из них должны получиться 6 пар составного отражателя (см. таблицу 9.3).

Таблица 9.3.

Получается несколько противоречий: например, 1-е угловое положение дает нам пару (A,G) составного отражателя, в то время, как 2-е угловое положение указывает на то, что (A,F) также образуют пару. Поэтому колесо R1 не может находиться в 1-м угловом положении.

(2) Повторим процедуру , но на этот раз зашифруем пары во 2-м и 3-м угловом положениях (см. таблицу 9.4)

Таблица 9.4.

Оба множества полностью согласуются друг с другом. Таким образом, мы установили вид колеса R1 и то, что перед началом зашифрования оно находилось во 2-м угловом положении. Кроме того, нам теперь известно, каким образом сгруппированы попарно 12 букв составного отражателя:

(A,L), (B,F), (C,D), (E,I), (G,K) и (H,J).

Поскольку колесо R1 и неподвижный отражатель (U) криптоаналитику известны, теперь он может попытаться найти, с помощью каких комбинаций отражателя U с двумя другими колесами можно получить эти пары. Первая

150

модель "Энигмы" имела в комплекте только три колеса, и поскольку колесо R1 уже установлено, остается перебрать "всего лишь" 2 26 26=1352 варианта. Это число может показаться большим, однако в сравнении с перебором 105456 вариантов, с которыми криптоаналитик имел дело в начале работы, оно совсем небольшое. На этой стадии можно попробовать и другие подходы, например, перебор вероятных начал открытых текстов некоторых сообщений.

Разумеется, следует помнить, что данный пример дает лишь условное представление о способе дешифрования сообщений для первой модели "Энигмы", в комплекте которой было только три колеса и отсутствовал коммутатор. В последующие годы, и особенно с 1938 по 1945, конструкция "Энигмы" и установленный порядок шифрования подверглись значительным изменениям. Например:

(1)благодаря введению букв-"пустышек" и использованию таблицы замены диграфов изменился повторяющийся трехбуквенный индикатор;

(2)от использования общей базовой угловой установки отказались; операторы теперь выбирали свою собственную базовую угловую установку, которую они в незашифрованном виде передавали перед шифрованным текстом;

(3)у всех пользователей число колес увеличилось с трех до пяти, а в военно-морском флоте, позднее, и до восьми; там же, начиная с 1942 года, использовалась еще и четырехколесная модель "Энигмы" с новой конструкцией отражателя.

Все эти изменения поставили перед криптоаналитиками из Блетчли целый ряд серьезных задач, которые были ими решены - в некоторых случаях довольно быстро; однако дешифрование четырехколесной шифрмашины потребовало очень больших усилий.

Более подробно об этом можно прочитать в [9.2] и [9.3].

Если читатель захочет смоделировать "Энигму" на персональном компьютере и вслед за польскими криптоаналитиками повторить все шаги по ее вскрытию, то он найдет работу [9.4] весьма интересной.

Для тех, кто хотел бы попробовать определить угловую установку колеса "мини-Энигмы", предлагаем следующую задачу:

Задача 9.1 Рассмотрим "мини-Энигму" с алфавитом из 10 знаков, на которой

шифруются сообщения в цифровом алфавите (от 0 до 9). Получены следующие индикаторы (их порядок неизвестен)

(0,2), (1,6), (2,3), (3,9), (4,8), (5,5), (6,4), (7,7), (8,1) и (9,0),

которые представляют собой результаты зашифрования пар 00,11,..,99 при