Вскрытие установок "Хагелина" по отрезку гаммы

Как показано далее, если мы имеем 131 или более подряд стоящих знаков гаммы, задача восстановления установок барабана и штифтов для шифрмашины "Хагелин" без перекрытий решается в лоб. Может возникнуть вопрос: "А как же нам получить 131 знак гаммы подряд?" Ответ на это таков: "Для этого нужно получить открытый текст сообщения длиной 131 знак или более". Это можно сделать несколькими способами, в том числе:

1. обнаружив, что то же самое сообщение отправлено с использованием другого шифра, который мы умеем читать;

2. обнаружив, что два или более сообщения, зашифрованные с помощью "Хагелина", являются одноключевыми; тогда их можно прочесть методом протяжки шаблонов, как описано в главе 7;

3. если шифровальщик сделал ошибку и вынужден повторить переданное сообщение, слегка изменив установки шифрмашины;

4. с помощью агентурных методов, то есть если агент добудет открытый текст сообщения.

Для иллюстрации метода дешифрования по достаточно длинному отрезку гаммы, рассмотрим гамму, выработанную "мини-Хагелином", состоящим всего из трех колес. Чтобы вскрыть подобным образом полноразмерный "Хагелин", без сомнения, потребуется выполнить больший объем работы, однако метод дешифрования остается тем же самым. Он основан на том, что гамма является суммой (по модулю 26) последовательностей, снимаемых с шести регулярно движущихся колес. Поэтому, вычитая последовательность знаков гаммы из самой себя с необходимым сдвигом, можно исключить вклад любой пятерки из этих шести колес и вычислить, таким образом, "зацепление" оставшегося колеса. Подобным образом можно, например, построить гамму, сложив между собой последовательности, снимаемые с двух мини-колес. Пусть одно из них имеет 7 штифтов и "зацепление", равное 5, а другое - 9 штифтов и "зацепление", равное 3. Получаем:

7-штифтовое колесо 5 0 5 5 0 0 5 5 0 5 5 0 0 5 5 0 5 5 0 0 5 5 . . .

9-штифтовое колесо 0 3 3 3 0 0 3 0 3 0 3 3 3 0 0 3 0 3 0 3 3 3 . . .

Сумма 5 3 8 8 0 0 8 5 3 5 8 3 3 5 5 3 5 8 0 3 8 8

Скопируем последовательность знаков гаммы, сдвинем ее на 7 позиций вправо (т.е. на размер одного из колес) и вычтем из несдвинутой последовательности знаков гаммы:

5 3 8 8 0 0 8 5 3  5 8 3 3  5 5 3 5 8  0 3 8 8

 5 3  8 8 0 0  8 5 3 5 8  3 3 5 5

Разностная последовательность  0 0 -3 0 3 3 -3 0 0 0 0 -3 0 3 3

Заметим, что

1. все элементы разностной последовательности кратны 3, значению "зацепления" 9-штифтового колеса

2. разностная последовательность повторяется через 9 шагов, то есть ее период равен числу штифтов оставшегося колеса.

Описанная здесь операция называется "нахождением разности на расстоянии 7" и обычно в математике обозначается с помощью греческой буквы  (заглавная "дельта", которая соответствует букве D латинского алфавита) с индексом, который обозначает размер интервала (в данном случае 7). Таким образом, вычисленная нами разность обозначается символом

₇

Иногда вычисление разности называют также "нахождением дельты".

Вовсе не обязательно было начинать с нахождения разности именно на расстоянии 7. Мы, конечно же, могли найти разностную последовательность и на расстоянии 9. В этом случае получаем:

Сумма 5 3 8 8 0 0 8 5 3  5 8  3  3  5 5  3 5 8   0  3 8 8

Сдвиг на 9 позиций 5 3  8  8  0 0  8 5 3   5  8 3 3

Разность 0 5 -5  -5  5 5 -5 0 5  -5 -5 5 5

Полученная последовательность повторяется через 7 шагов, и к тому же очевидно, что "зацепление" 7-штифтового колеса равно 5.

Итак, "зацепления" колес мы установили. А что можно сказать о штифтовых установках колес? При известных "зацеплениях" колес они получаются из числовых значений разностных последовательностей. В "реальной" шифрмашине "Хагелин" в этом есть одна сложность, но мы ее пока не будем учитывать: значение гаммы, равное 0 или 1, может фактически означать 26 или 27. А пока метод восстановления штифтовых установок можно проиллюстрировать примером еще одного "мини-Хагелина".

Пример 10.4

С помощью "мини-Хагелина", состоящего из трех колес длин 5, 8 и 9, получена следующая последовательность знаков гаммы:

6 4 3 6 8 6 4 5 1 8 4 1 8 6 8 1 6 3 9 0 4 6 8 6 0.

Требуется найти "зацепления" и штифтовые установки колес.

Решение

Операцию взятия разности можно применять в любом порядке. Если сначала найти разность на расстоянии 5, а затем к полученной последовательности применить операцию взятия разности на расстоянии 8, то мы исключим влияние 5- и 8-штифтовых колес. В результате должна получиться последовательность чисел (среди них могут быть положительные, отрицательные и нулевые), каждое из которых кратно значению "зацепления" 9-штифтового колеса. Итак:

Гамма 6 4 3 6 8 6 4 5  1 8  4  1 8 6 8  1  6  3  9  0 4  6 8  6  0

Сдвиг на 5 6 4 3  6 8  6  4 5 1 8  4  1  8  6  8 1  6 3  9  0

₅ 0 0 2 -5 0 -2 -3 3 5 0 -3  5 -5  3 -8 3  0 5 -3  0

Сдвиг на 8  0 0  2 -5  0 -2 -3 3  5 0 -3  5

₈₅  5 0 -5 10 -5  5 -5 0 -5 5  0 -5

Очевидно, "зацепление" 9-штифтового колеса равно 5. Заметим, что полученная разностная последовательность повторяется через 9 шагов. Также в ней присутствует ровно одно значение, равное удвоенному значению "зацепления". Это - частный случай следующего утверждения:

"При N-кратном применении операции взятия разности к последовательности знаков гаммы результирующая разностная последовательность может содержать значения, кратные размеру "зацепления" с множителем до 2^(N-1) включительно." (Доказательство см. в приложении M19).

Теперь найдем зацепление 8-штифтового колеса. Для этого нужно взять разность на расстоянии 5, а затем на расстоянии 9 (в любом порядке). Так как разность на расстоянии 5 мы уже вычислили (см. полученную выше последовательность ₅), нужно только выполнить операцию взятия разности на расстоянии 9:

₅ 0 0 2 -5 0 -2 -3 3 5 0 -3 5 -5 3 -8  3  0 5 -3  0

Сдвиг на 9   0  0 2 -5 0 -2 -3  3 5  0 -3

₉₅   0 -3 3  0 3 -6  6 -3 0 -3  3

Полученная последовательность повторяется через 8 шагов (как и должно быть), и очевидно, что зацепление 8-штифтового колеса равно 3.

Аналогично, вычисляя разности исходной последовательности знаков гаммы на расстоянии 8, а затем на расстоянии 9, получаем:

₉₈ 0  1 -2  1  0  0  1 -2

Последовательность повторяется через 5 шагов, и зацепление 5‑штифтового колеса равно 1.

Теперь необходимо найти штифтовые установки этих трех колес. Для этого рассмотрим последовательность знаков гаммы и проанализируем, каким образом можно получить ее элементы в виде комбинации "зацеплений" (1, 3 и 5) колес. Сделать это очень просто. Для полноразмерного "Хагелина" с шестью колесами задача будет посложнее, но нам очень помогает тот факт, что вклад каждого колеса в суммарную последовательность знаков гаммы повторяется с периодом, равным размеру колеса. В случае с нашим "мини-Хагелином" все восемь вариантов можно перечислить. Все возможные варианты построения гаммы показаны в таблице 10.4. (X обозначает активный штифт, O - неактивный).

Таблица 10.4

Теперь выпишем последовательность знаков гаммы и штифтовые установки, которые получаются для каждого колеса:

Штифтовые последовательности всех колес повторяются через правильное число шагов, поэтому можно заключить, что штифтовые установки выглядят так:

Штифтовая установка колеса размера 5 X X O X O

Штифтовая установка колеса размера 8 O X X O X O X O

Штифтовая установка колеса размера 9 X O O X X X O X O

Для полноразмерной шифрмашины "Хагелин", конечно, понадобится отрезок гаммы большей длины. При каждом взятии разности последовательности знаков гаммы ее длина сокращается на столько элементов, каков размер исключаемого колеса. Так, в вышеприведенном примере при взятии разности на расстоянии 5 исходные 25 знаков гаммы сократились до 20, а после взятия второй разности на расстоянии 8 осталось только 12 значений. Для полноразмерного "Хагелина" понадобится не менее 131 знаков гаммы, так как сумма размеров всех шести колес равна 131. Желательно иметь их немного больше, чем 131: дополнительные знаки гаммы нужны, чтобы проверить, что финальная последовательность (полученная 5-кратным взятием разностей) повторяется через правильное число шагов. В реальности 150 знаков гаммы оказывается достаточно. К тому же, как уже упоминалось ранее, полноразмерный "Хагелин" имеет дополнительные возможности, значительно усложняющие задачу дешифрования. В этом мы сейчас убедимся.