Как работает шифровальная машина Lorenz SZ 42 (для телетайпа)

В прошлом году я написал пост про известную шифровальную машину нацистов Как работает машина Enigma M3 (для флота) / Хабр .

Enigma широко использовалась в немецких вооружённых силах, включая армию и флот.

Но куда менее известной является машина Lorenz SZ 42, хотя она была не менее важна.

Из этой статьи вы сможете узнать, как шифровали сверхсекретную связь высшего немецкого командования, как ошибка оператора в 1941 году помогла раскрыть устройство Lorenz и почему в 1944-м для чтения таких сообщений появился электронный Colossus.

Сразу скажу, что написать эту статью было куда сложнее, чем статью про Enigma, так как материалов про это сильно меньше, особенно научно-популярных и особенно на русском языке. Но это того стоило! Получилась еще одна увлекательная глава из истории техники, криптографии и Второй мировой войны.

Кроме того, в процессе работы над материалом было найдено довольно много первоисточников, которые неплохо сохранить внутри такой статьи. В самом низу есть cайты, архивы, интерактивные модели и первоисточники, в статье много кода на Python.

1. «Новая музыка» в эфире

В 1940 году британские перехватчики услышали в эфире непривычные телетайпные сигналы — механические трели вместо знакомой азбуки Морзе. Такие немецкие шифрованные телетайпные системы объединяли названием Fish («Рыба»). Разбор сообщений Lorenz между Веной и Афинами начался летом 1941 года; название Tunny («Тунец») появилось в 1942-м. Ранние перехваты описаны в отчёте 1945 года. Немецкое название семейства — Schlüsselzusatz, «шифровальная приставка»: сначала SZ 40, затем SZ 42 и его модификации.

https://www.gchq.gov.uk/news/secret-sites-revealed — статья про перехватную станцию Knockholt в Кенте, опубликованная в ноябре 2019-го года. В ней впервые была раскрыта информация о разведывательной деятельности на 5 очень важных секретных объектах Великобритании.

2. Зачем Lorenz, если была Enigma

Enigma была портативной, но шифрование и передача оставались отдельными операциями: буквы набирали на машине, записывали результат и затем отправляли его по каналу связи, например азбукой Морзе. Верховному командованию вермахта нужна была прямая телетайпная связь между штабами. Lorenz SZ 40/42 включалась между телетайпом и линией: поток пятибитных знаков шифровался автоматически.

Оператор мог подготовить сообщение на перфоленте и передать его с помощью считывателя. На другом конце согласованная по ключу приставка восстанавливала текст, который печатал телетайп. Lorenz была именно шифровальной приставкой, а не самостоятельным телетайпом.

Фото и образцы немецкой машины выложены в британском национальном музее вычислений, сайт https://www.tnmoc.org/news-releases/2017/5/15/virtual-lorenz

Известны четыре более или менее полных сохранившихся экземпляра. Один находится в TNMOC, серийный № 1137.

В музее Блетчли Парка находится еще один, серийный №1077.

Образец с серийным № 1116 находится в национальном криптографическом музее США.

Четвертый находится в немецком музее https://digital.deutsches-museum.de/de/digital-catalogue/collection-object/81019/ Он присутствует в официальном цифровом каталоге музея как “Chiffrierfernschreibmaschine Lorenz SZ 42”, инвентарный объект 81019.

Серийный номер немецкого экземпляра по приведённой музейной карточке установить не удалось. Номера 1077, 1116 и 1137 для трёх других машин приведены в техническом отчёте реставратора Крейга Сойерса.

3. Код Бодо: от букв к битам

Lorenz работает с пятибитным кодом ITA2 (International Telegraph Alphabet No. 2), развитием кода Бодо. Пять бит дают 32 комбинации. В буквенном режиме 26 соответствуют буквам; остальные служат для пробела, возврата каретки, перевода строки, пустой группы и переключений FIGS/LTRS. FIGS включает цифры и знаки, LTRS возвращает буквы. Поэтому одна и та же комбинация может печатать разные символы в зависимости от регистра.

В Википедии эта таблица изложена компактнее Код Бодо — Википедия

Запрограммируем ITA2. Группы храним как числа 0…31; первый передаваемый импульс b1 — младший бит. Например, C = 14, LTRS = 31, FIGS = 27. Раскладки знаков различались по странам: здесь используется международный набор с явно обозначенными резервными позициями. Неподдерживаемый символ вызывает ошибку, а не исчезает из сообщения.

NUL, LF, SPACE, CR, FIGS, LTRS = 0, 2, 4, 8, 27, 31
LETTERS = (
    "", "E", "n", "A", " ", "S", "I", "U",
    "r", "D", "R", "J", "N", "F", "C", "K",
    "T", "Z", "L", "W", "H", "Y", "P", "Q",
    "O", "B", "G", None, "M", "X", "V", None,
)
# Международная раскладка: None — переключение/спецфункция/резерв.
FIGURES = (
    "", "3", "n", "-", " ", "'", "8", "7",
    "r", None, "4", "a", ",", None, ":", "(",
    "5", "+", ")", "2", None, "6", "0", "1",
    "9", "?", None, None, ".", "/", "=", None,
)


def check_codes(codes):
    values = list(codes)
    if any(type(v) is not int or not 0 <= v < 32 for v in values):
        raise ValueError("Каждая группа должна быть целым числом 0..31")
    return values


def encode_ita2(text):
    tables = [LETTERS, FIGURES]
    inverse = [{c: i for i, c in enumerate(t) if c is not None}
               for t in tables]
    mode, out = 0, [LTRS]  # явно задаём начальный регистр
    for c in text.upper():
        if c not in inverse[mode]:
            other = 1 - mode
            if c not in inverse[other]:
                raise ValueError(f"Символ {c!r} отсутствует в этой ITA2")
            mode = other
            out.append(LTRS if mode == 0 else FIGS)
        out.append(inverse[mode][c])
    return out


def decode_ita2(codes):
    mode, out = 0, []
    for v in check_codes(codes):
        if v in (LTRS, FIGS):
            mode = int(v == FIGS)
        elif v != NUL:  # NUL ничего не печатает
            c = (LETTERS, FIGURES)[mode][v]
            if c is None:
                raise ValueError(f"Неподдержанная спецфункция ITA2: {v}")
            out.append(c)
    return "".join(out)


def to_bits(value):
    check_codes([value])
    return [(value >> i) & 1 for i in range(5)]


def from_bits(bits):
    if len(bits) != 5 or any(type(b) is not int or b not in (0, 1) for b in bits):
        raise ValueError("Нужны ровно пять битов")
    return sum(b << i for i, b in enumerate(bits))


def text_to_baudot(text):
    return [to_bits(v) for v in encode_ita2(text)]


def baudot_to_text(bits_list):
    return decode_ita2(from_bits(b) for b in bits_list)

4. Общий принцип: потоковый шифр Вернама

Lorenz реализует классический шифр Вернама. Открытый текст (P) складывается по модулю 2 (XOR) с ключевым потоком (K) — получается шифротекст (C).

На приёмном конце тот же ключ складывается с C — получается P: (P ⊕ K) ⊕ K = P. При секретном, равномерно случайном ключе той же длины, независимом от сообщения и использованном только один раз, получается одноразовый блокнот с совершенной секретностью. Lorenz же создаёт поток механически, из повторяющихся узоров и правил движения. Их зависимости и становятся предметом криптоанализа.

def xor_codes(a, b):
    a, b = check_codes(a), check_codes(b)
    if len(a) != len(b):
        raise ValueError("Длины текста и ключа должны совпадать")
    return [x ^ y for x, y in zip(a, b)]


def xor_bits(a, b):
    return to_bits(from_bits(a) ^ from_bits(b))


def vernam_cipher(plaintext_bits, keystream):
    if len(plaintext_bits) != len(keystream):
        raise ValueError("Длины текста и ключа должны совпадать")
    return [xor_bits(p, k) for p, k in zip(plaintext_bits, keystream)]

5. Двенадцать колёс: χ, ψ и μ

Если снять крышку Lorenz, внутри окажется ряд из двенадцати колёс. Однако работают они по-разному. Британские криптоаналитики назвали три группы греческими буквами: χ (хи), ψ (пси) и μ (мю). В документах встречаются и обозначения X, S и M.

Каждое колесо χ и ψ выдаёт один бит. Для первого импульса ITA2 складываются χ1 и ψ1, для второго — χ2 и ψ2, и так далее. Получаются пять битов ключа: Kᵢ = χᵢ ⊕ ψᵢ.

Моторные колёса непосредственно в этот XOR не входят: они определяют, когда изменится ψ. Всего на двенадцати колёсах 501 двоичный штифт.

Длины и механика описаны в техническом разделе Virtual Lorenz.

Собственная схема: как двенадцать колёс создают пятибитный ключ. Моторная логика показана для базового SZ 40.

Попарно взаимно простые длины колёс увеличивают время до повторения их положений. Большое число состояний ещё не доказывает стойкость шифра: криптоаналитик может искать части ключа по отдельности. Тогда полный перебор машины ему не понадобится.

6. Почему ψ «заикается» и как это важно для взлома

В базовой схеме μ61 после каждого знака продвигается на одну позицию. Если его текущий штифт активен, разрешён следующий шаг μ37. Текущий штифт μ37, в свою очередь, разрешает шаг сразу всем пяти ψ. Если разрешения нет, они остаются на месте, и их пятибитная добавка повторяется.

GIF-анимация. Числа — позиции контактов в учебной модели, с нумерацией от нуля; «ШАГ/СТОП» относится к переходу к следующему знаку. После 24-го кадра повторяется показанный фрагмент: возврат к первому кадру не изображает период машины.

Криптоаналитикам помогло сравнение соседних знаков. Определим ΔCₜ = Cₜ ⊕ Cₜ₊₁. Такая «разность» тоже считается через XOR. Тогда:

ΔC = ΔP ⊕ Δχ ⊕ Δψ.

Если между двумя знаками ψ не сдвинулись, то ψₜ = ψₜ₊₁, следовательно, Δψ = 00000. Одна из двух маскирующих добавок исчезает. Из этого не получается готовый открытый текст: χ всё ещё мешают чтению. Зато на длинном сообщении можно заметить статистическую неравномерность языка. Это основной смысл атаки через разности, описанной Тони Сейлом.

Для заданного кандидата χ вычисляют ΔD = ΔC ⊕ Δχ. При правильном кандидате в ΔD остаются разности языка и ψ, при неправильном к ним добавляется чужой узор χ. Например, можно считать нули в ΔD₁ ⊕ ΔD₂ и сравнивать результаты для разных начальных позиций.

При этом остановки ψ не обязаны занимать ровно половину конкретного сообщения. Это зависит от узоров и начальных положений. Слова «около половины» относятся к типичному поведению базовой схемы, а не к гарантированному расписанию.

7. Устройство колеса: штифты, ролики, блокировка

Колесо Lorenz похоже на небольшой барабан с переставляемыми кулачками по ободу. У каждого кулачка два положения. Для криптоаналитика это 0 и 1, или точка и крестик. Для механика — два профиля поверхности, которые по-разному воздействуют на считывающий рычаг с подпружиненным роликом.

Когда барабан поворачивается, ролик следует по ободу и считывает очередную настройку. На моторных колёсах это движение связано с блокирующими рычагами: одни положения разрешают продвижение следующей группы, другие задерживают его.

Посмотреть оригинальные чертежи и инструкции можно в CryptoCellar — архиве документов SZ 42. Для понимания движения удобно открыть трёхмерную модель Virtual Lorenz.

Сравним это с Enigma. Её ротор содержит проводку, которая переставляет буквы алфавита, а колесо Lorenz хранит последовательность двоичных состояний. Чтобы описать его логическую работу, нам достаточно массива битов и номера текущей позиции.

Ключевой поток зависит и от узоров штифтов, и от движения колёс. При другом старте тот же узор даёт другой поток; остановки ψ растягивают последовательности их битов. Чтобы воспроизвести работу Lorenz, придётся повторить и настройки колёс, и механизм их продвижения.

8. Полный цикл шифрования: от текста до ленты

Проследим путь одного символа. Оператор нажал букву C. Телетайп превратил её в пять импульсов 0 1 1 1 0 в порядке b1…b5. Lorenz считал текущие контакты χ и ψ и получил пятибитный ключ. В нашем примере это 0 0 1 1 1, то есть группа M.

Теперь складываем соответствующие импульсы: получается 0 1 0 0 1, группа L. На другом конце линии такая же приставка складывает L с тем же ключом M и восстанавливает C. После обработки знака колёса переходят в состояние для следующей кодовой группы.

Собственная GIF-анимация одного знака. P — открытая группа, C — шифрованная; названия букв относятся к режиму LTRS.

Шифр обрабатывает и управляющие группы: пробел, возврат каретки, перевод строки, LTRS и FIGS. У шифротекста комбинация 31 уже не означает, что надо переключить открытый текст на буквы. Её сначала необходимо расшифровать. Поэтому произвольный шифротекст нельзя корректно показать обычным вызовом нашего текстового декодера: часть групп будет воспринята как управление.

Собственная схема ленты, построенная по фактическому результату Python-примера. Маленькие отверстия между дорожками — транспортные.

На линии связи пять информационных импульсов передаются последовательно, в рамке со стартовым и стоповым сигналами. В коде промоделировано шифрование пяти информационных битов, без электрического интерфейса, радиомодуляции и транспортных отверстий. Такой путь сигнала описан в материалах Lorenz Cipher Event.

9. Ключ машины

У Lorenz было два уровня настройки: узоры штифтов на всех колёсах и стартовые положения для конкретного сообщения. Передатчик и приёмник должны согласовать оба.

Если зафиксировать узор, то число возможных комбинаций двенадцати стартов равно:

41 × 31 × 29 × 26 × 23 × 43 × 47 × 51 × 53 × 59 × 61 × 37 ≈ 1,60 × 10¹⁹.

Для первых двух χ остаётся всего 41 × 31 = 1271 комбинация, а для всех пяти χ — 22 041 682. Эти части ключа можно искать отдельно, используя статистические методы.

Узоры меняли по расписанию, которое усложнялось по ходу войны. Кроме того, группы колёс могли перенастраиваться с разной частотой. Первоначально стартовые положения передавались через двенадцатибуквенный индикатор и таблицы. Позже использовались книги QEP с согласованными наборами позиций. Сами ключевые документы и страницы книг QEP сохранились, а общие уязвимости этой процедуры отлично разобраны у Тони Сейла.

В SZ 42A/B появилась ещё одна сложность: ограничения движения. На решение о шаге ψ могли влиять предыдущие значения χ2, в варианте B — также ψ1; существовала и опция с пятым импульсом открытого текста двумя знаками раньше.

С помощью этих ограничений, таким образом, менялось само правило работы прежних двенадцати колес. Поэтому базовый алгоритм SZ 40 и полный эмулятор позднего SZ 42B — совершенно разные задачи по сложности. Описание вариантов можно найти по этой ссылке Virtual Lorenz.

10. Ключевая ошибка оператора 30 августа 1941 года

30 августа 1941 года британцы перехватили две длинные передачи между Веной и Афинами с одним индикатором HQIBPEXEZMUG. Отправитель повторно набрал практически то же сообщение с теми же начальными настройками. Но версии различались пробелами, опечатками, исправлениями и сокращениями. Короткая содержала 3976 шифрованных групп. Это зафиксировано и описано тут General Report on Tunny.

Пара сообщений на одном ключевом потоке называется depth. Для неё выполняется:

C₁ ⊕ C₂ = (P₁ ⊕ K) ⊕ (P₂ ⊕ K) = P₁ ⊕ P₂.

Ключ сократился, и осталось побитовое наложение двух открытых телеграмм. Их ещё нужно разделить. Чтобы разделить его, нужны предположения о языке, типовых началах сообщений и местах, где повторный набор ушёл вперёд или отстал.

Когда удаётся угадать фрагмент P₁, вычисляется соответствующий фрагмент P₂; осмысленность результата помогает проверить догадку.

Джон Тилтман примерно за десять дней восстановил длинный участок открытых текстов и 3976 последовательных групп ключа. Он описал эту работу в своей научной статье The “Tunny” Machine and Its Solution. Именно ключ, очищенный от языка сообщения, стал важнейшим материалом для дальнейшего исследования внутренней структуры аппарата.

Дословный повтор с тем же ключом дал бы одинаковый шифротекст и сам по себе не раскрыл бы эту длинную последовательность. Здесь помогло именно то, что на повторном ключе передали изменившийся текст. Далее предстояло разработать методы анализа машины.

11. Тур де форс Татта: реверс-инжиниринг без чертежей

Ключ попал к Уильяму, или Биллу, Татту. В Блетчли-Парк он пришёл в мае 1941 года после учёбы в Кембридже, причём его первое образование было химическим. Позднее он стал известен как математик. В тот момент его задача начиналась с потока точек и крестиков от неизвестной машины. Биографию и значение его работы можно посмотреть тут GCHQ.

Татт исследовал пять импульсных последовательностей по отдельности. В первой удалось выделить регулярную составляющую с периодом 41. Полный ключ при этом не повторялся каждые 41 знак: регулярный узор был скрыт второй, нерегулярной составляющей. Отсюда возникла модель χ1 ⊕ ψ1, затем аналогичные пары для остальных импульсов и механизм, объясняющий общие остановки ψ.

К началу 1942 года Татт и его коллеги восстановили логическую структуру двенадцатиколёсной машины. Как выглядели корпус и редуктор, где стояли винты, из радиограммы узнать было нельзя.

Но для воспроизведения ключевого потока хватило восстановленной логики: своё устройство британцы построили ещё до знакомства с немецким аппаратом.

Теперь нужно было находить меняющиеся узоры и старты. Алан Тьюринг разработал для этой задачи метод Turingery. Работы распределились так: Тилтман восстановил ключ, Татт с коллегами диагностировал машину, Тьюринг развивал методы получения её настроек. Об этой последовательности описано в исследовании Джека Коупленда.

Попробуем представить такую задачу сегодня. У нас есть выходные данные устройства, но нет ни самого устройства, ни схем, ни исходников. По этим данным нужно восстановить модель, которая объяснит наблюдения и позволит предсказывать следующие результаты. Это и есть тот самый реверс-инжиниринг, с которым столкнулся Татт!

12. British Tunny: эмулятор невиданной машины

После восстановления алгоритма британцам понадобился свой дешифратор. В исследовательской лаборатории почтового ведомства в Доллис-Хилле создали British Tunny: стойку с реле и шаговыми искателями, воспроизводившую логику немецких колёс. В ранней реализации участвовал Фрэнк Моррелл. Машина выглядела совершенно иначе, но при одинаковых логических настройках должна была давать тот же результат.

Перед работой в British Tunny вводили уже найденные узоры и позиции. Затем машина принимала шифрованные группы с ленты и помогала получить печатный немецкий текст. Неизвестные настройки она сама не искала — для этого требовались другие методы. О раннем аппарате и его музейной реконструкции рассказывает Virtual Colossus.

Британские инженеры построили собственную стойку, не видя оригинальную немецкую машину. Это была функциональная реконструкция, а не копия её механики.

В военном отчёте прямо описано электрическое воспроизведение Tunny и несколько его последующих вариантов.

По тому же принципу работают современные эмуляторы: не важно, как выглядит устройство. Главное, что оно воспроизводит нужные переходы состояния и преобразования данных. Для расшифровки этого достаточно.

13. Heath Robinson: первый шаг к автоматизации

Математик Макс Ньюман предложил поручить машине массовую проверку статистических гипотез. Подразделение Newmanry официально создали 1 февраля 1943 года. Его задача заключалась в том, чтобы ускорить поиск настроек по методам криптоаналитиков; об этом написано здесь GCHQ.

Первой важной реализацией стал Heath Robinson. Название отсылало к художнику Уильяму Хиту Робинсону, известному рисунками невероятно сложных механизмов. Аппарат сравнивал два потока: перехваченный шифротекст на одной бумажной ленте и проверяемые узоры на другой. После прохода взаимный сдвиг менялся, счёт повторялся.

Идея работала, но две быстро бегущие ленты требовали точного согласования. Бумага растягивалась, начинала расходиться по фазе, и статистика становилась недостоверной. На раннем аппарате операторы ещё и вручную переписывали быстро сменявшиеся показания. Эти конкретные недостатки перечислены в отчёте 1945 года.

Robinson показал, что статистический поиск можно механизировать. Потоки сравнивались быстро; трудность была в том, чтобы обе ленты проходили через считыватели синхронно. В следующем поколении одну из лент заменили электронным генератором.

14. Томми Флауэрс и секрет электронных ламп

Инженер Томми Флауэрс работал с телефонной аппаратурой в Доллис-Хилле. Из довоенного опыта он знал, что электронные лампы можно использовать как быстрые переключатели. Многих смущала надёжность устройства с тысячами ламп.

Флауэрс понимал роль режима работы. Особенно неприятны нагрев и остывание при включениях и выключениях; постоянно работающие лампы могут вести себя гораздо стабильнее. Это не означало отсутствия отказов само по себе.

Для стабильной работы требовались правильные электрические режимы, организация обслуживания и инженерная дисциплина. Его опыт и путь к Colossus великолепно разобраны в историческом исследовании Коупленда; первоисточник — статья самого Флауэрса The Design of Colossus.

Флауэрс предложил выкинуть все эти бумажные ленты шифротекстов и использовать куда более эффективный подход. Проверяемые последовательности колёс стали генерировать электроникой. Обе последовательности можно было привязать к одному тактовому потоку. Согласовывать движение двух отдельных бумажных петель больше не требовалось, а значит скорость и надежность работы устройства сильно возросла.

Электронным схемам поручили и сам расчёт: выполнять XOR, проверять заданные логические условия, увеличивать счётчики.

15. Colossus: первый программируемый электронный цифровой компьютер

Первый Colossus заработал в конце 1943 года, а в январе 1944-го его перевезли в Блетчли-Парк. Машина читала перфоленту фотоэлектрическим способом со скоростью около 5000 кодовых групп в секунду и электронно воспроизводила нужные последовательности.

Во втором поколении было примерно 2400–2500 ламп и расширенные возможности параллельного счёта. Описание основных характеристик и историю реконструкции можно узнать по этой ссылке TNMOC.

Фотография взята отсюда Rutherford Journal.

Сведения о public domain приведены на странице того же снимка.

Называть Colossus «первым компьютером» было бы, наверное, слишком грубо.

Точная формулировка будет такой: первый программируемый электронный цифровой компьютер.

Программирование здесь означает настройку переключателей и коммутационных панелей.

Это был первый в истории специализированный вычислитель для криптоанализа, без хранимой программы в современном смысле.

Криптоаналитик присылает тест, Colossus автоматически оценивает множество вариантов и печатает результаты. Человек выбирает перспективные кандидаты и назначает следующие проверки. Таким образом, полного перебора всех 1,60 × 10¹⁹ состояний машина не выполняла.

16. «Колосс» в работе: первая расшифровка

5 февраля 1944 года обычно все приводят как дату первой успешной обработки реального сообщения на Colossus. Затем в июне появился Mark II, а к окончанию войны работали уже десять таких машин. Это описано, например, тут Crypto Museum.

Обработка сообщения шла в несколько этапов.

Сначала перехват превращали в проверенную перфоленту. Для нее подбирались узоры и начальные позиции χ, оценивались результаты, затем решались оставшиеся части задачи — ψ и моторная последовательность. На British Tunny получался открытый текст, который после проверки, перевода и анализа мог стать разведывательной сводкой.

Для первых двух импульсов криптоаналитик задавал какое-нибудь условие вроде этого

ΔD₁ ⊕ ΔD₂ = 0.

Colossus считал, сколько раз оно выполняется на всей ленте. Выделяющийся результат указывал на кандидата для последующих тестов. Работа развивалась: поздние методы и настройки Colossus охватывали куда больше этапов, чем первоначальный поиск χ. Разделение задачи и развитие методов отлично описано в очерке GCHQ о Шоне Уайли.

Расшифрованное сообщение нужно было еще успеть передать разведке, пока сведения о планах противника были ещё полезны. К лету 1944 года чтение стратегических сообщений помогало оценивать расположение немецких сил и результат операции по дезинформации о месте высадки. Вклад Tunny в подготовку D-Day разобран в историческом материале GCHQ.

17. Как работали люди за шифровальными машинами

На немецкой стороне оператор телетайпа должен был правильно выставить ключ, выдержать процедуру связи и не повторить использованный поток. Хотя автоматическое шифрование снимало ручное преобразование каждой буквы, оно не отменяло ответственности за верно выставленные настройки. Если хотя бы одна сторона потеряла бы синхронизацию, осмысленный текст на приёмнике исчезал.

На британской же стороне работала целая цепочка из групп людей.

Одни сотрудники станции перехвата получали сигнал, другие готовили и проверяли ленты.

Криптоаналитики Testery использовали знание немецкого языка и ручные методы криптоанализа.

Newmanry гоняла машинные статистические проверки.

Операторы заправляли ленты, выполняли заданные серии счётов и фиксировали результаты.

Любая неверно подготовленная лента могла обесценить даже полностью правильно выполненный машинный расчёт. Обслуживание аппаратуры также требовало инженеров, которые знали лишь свою часть работы.

Воспроизведению истории всей этой сложной согласованной работы коллективов людей, в которой ошибка каждой группы разрушала всю работу, посвящен известный музейный проект The Hidden Figures of Colossus.

18. Шифруем и взламываем на Python

Теперь соберём работающий иллюстративный пример взлома кода с помощью Python.

Границы модели.

Модель воспроизводит базовую двенадцатиколёсную логику SZ 40: пять χ, пять ψ и два моторных колеса. Ограничения SZ 42A/B, радиосигнал и специальная процедура первых шагов реального аппарата не моделируются.

Здесь список starts — это позиции считываемых контактов перед первым моделируемым знаком, с нумерацией от нуля. В описании Тилтмана отдельно указаны особые правила начала передачи. Узор штифтов в примере выдуманный.

Сначала создадим колесо и генератор ключа. В каждом такте читаются старые контакты, затем принимаются решения о движении и сдвигаются колёса. Это важно: если сначала сдвинуть μ37, а затем спросить его новый бит, получится другая последовательность ψ.

from dataclasses import dataclass
from random import Random
from math import prod

CHI_LENGTHS = (41, 31, 29, 26, 23)
PSI_LENGTHS = (43, 47, 51, 53, 59)
LENGTHS = CHI_LENGTHS + PSI_LENGTHS + (61, 37)


@dataclass
class Wheel:
    pins: tuple
    pos: int = 0

    def __post_init__(self):
        if not self.pins or any(type(v) is not int or v not in (0, 1)
                                for v in self.pins):
            raise ValueError("Узор колеса — непустая последовательность битов")
        if type(self.pos) is not int or not 0 <= self.pos < len(self.pins):
            raise ValueError("Начальная позиция вне колеса")

    def read(self):
        return self.pins[self.pos]

    def step(self):
        self.pos = (self.pos + 1) % len(self.pins)


class Lorenz40:
    def __init__(self, patterns, starts):
        if tuple(map(len, patterns)) != LENGTHS or len(starts) != 12:
            raise ValueError("Нужны 12 узоров правильной длины и 12 позиций")
        self.wheels = [Wheel(tuple(p), s) for p, s in zip(patterns, starts)]

    def next_key(self):
        chi, psi = self.wheels[:5], self.wheels[5:10]
        mu61, mu37 = self.wheels[10:]
        key = sum((a.read() ^ b.read()) << i
                  for i, (a, b) in enumerate(zip(chi, psi)))
        # Решения принимаем по старым контактам обоих моторных колёс.
        move_mu37, move_psi = mu61.read(), mu37.read()
        for w in chi:
            w.step()
        if move_psi:
            for w in psi:
                w.step()
        if move_mu37:
            mu37.step()
        mu61.step()
        return key

    def crypt(self, codes):
        return [v ^ self.next_key() for v in check_codes(codes)]


def demo_patterns(seed=42):
    rng = Random(seed)
    return [tuple(rng.randrange(2) for _ in range(n)) for n in LENGTHS]

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

Далее проведем два разных вычислительных эксперимента.

Первый, чтобы показать повторное использование ключа.

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

Второй эксперимент будет учебной версией double-delta.

Считаем нули в ΔC₁ ⊕ ΔC₂ ⊕ Δχ₁ ⊕ Δχ₂ для всех 1271 стартов. У атакующего есть только шифротекст и заранее известные узоры первых двух χ. Значения настоящих стартов используются лишь в конце для проверки результата. Это поиск двух начальных позиций, а не полный взлом неизвестного SZ 42.

def delta(values):
    values = check_codes(values)
    return [a ^ b for a, b in zip(values, values[1:])]


def rank_chi12(cipher, chi1, chi2):
    """Все 41*31 сдвигов; оценка double-delta для импульсов 1 и 2."""
    dz = delta(cipher)
    if not dz:
        raise ValueError("Для статистики нужны хотя бы два символа")
    n1, n2 = len(chi1), len(chi2)
    d1 = [chi1[i] ^ chi1[(i + 1) % n1] for i in range(n1)]
    d2 = [chi2[i] ^ chi2[(i + 1) % n2] for i in range(n2)]
    z12 = [(v & 1) ^ ((v >> 1) & 1) for v in dz]
    scores = []
    for s1 in range(n1):
        for s2 in range(n2):
            hits = sum((z ^ d1[(s1+t) % n1] ^ d2[(s2+t) % n2]) == 0
                       for t, z in enumerate(z12))
            scores.append((hits, s1, s2))
    return sorted(scores, reverse=True)


def depth_demo():
    # Сообщения одинаковой длины: выравнивание групп здесь заведомо известно.
    p1 = encode_ita2("ANGRIFF UM 04 UHR")
    p2 = encode_ita2("ANGRIFF UM 05 UHR")
    patterns, starts = demo_patterns(), [0] * 12
    c1 = Lorenz40(patterns, starts).crypt(p1)
    c2 = Lorenz40(patterns, starts).crypt(p2)
    difference = xor_codes(c1, c2)
    assert difference == xor_codes(p1, p2)
    recovered = xor_codes(p1, difference)
    assert recovered == p2
    return decode_ita2(recovered)

Программа для запуска:

def main():
    message = "HALLO WELT 1941rnENDE."
    patterns = demo_patterns()
    starts = [7, 12, 5, 9, 3, 4, 11, 2, 8, 6, 10, 13]
    plain = encode_ita2(message)
    cipher = Lorenz40(patterns, starts).crypt(plain)
    restored = Lorenz40(patterns, starts).crypt(cipher)
    assert restored == plain
    assert decode_ita2(restored) == message
    print("Шифротекст (5-битные числа):", cipher)
    print("Обратное преобразование:", repr(decode_ita2(restored)))
    print("Повтор ключа:", depth_demo())

    # Искусственный корпус с повторениями для устойчивого видимого пика.
    sample = encode_ita2(("DIE TRUPPEN MELDEN KEINE BESONDEREN "
                          "VORKOMMNISSE. LAGE UNVERAENDERT.rn") * 600)
    encrypted = Lorenz40(patterns, starts).crypt(sample)
    ranking = rank_chi12(encrypted, patterns[0], patterns[1])
    best = ranking[0]
    assert best[1:] == tuple(starts[:2]), ranking[:5]
    print("Лучшие кандидаты (совпадения, chi1, chi2):", ranking[:5])
    print("Случайный ориентир:", (len(encrypted) - 1) / 2)
    print("Комбинации стартов:", prod(LENGTHS))


if __name__ == "__main__":
    main()

Запустите сохранённый файл интерпретатором Python. Фактический результат проверенного запуска:

Шифротекст (5-битные числа): [25, 31, 19, 14, 16, 28, 16, 31, 7, 3, 18, 16, 12, 17, 9, 0, 12, 7, 11, 5, 12, 28, 12, 3, 5, 1]
Обратное преобразование: 'HALLO WELT 1941rnENDE.'
Повтор ключа: ANGRIFF UM 05 UHR
Лучшие кандидаты (совпадения, chi1, chi2): [(22901, 7, 12), (22588, 31, 14), (22567, 24, 18), (22479, 33, 27), (22469, 31, 6)]
Случайный ориентир: 22199.5
Комбинации стартов: 16033955073056318658

Цвет каждой клетки здесь обозначает число совпадений для одной пары стартов.

В корпусе 44 400 групп, значит, проверяются 44 399 переходов. Для идеально равновероятного теста ориентир равен 22 199,5 совпадения.

Правильная пара получила 22 901.

При независимых равновероятных испытаниях стандартное отклонение было бы равно √(44 399 / 4) ≈ 105,4; превышение составляет около 6,66 таких отклонений, что является практически невероятным результатом, если бы он был случайным.

Код проверен десятью тестами: эталонными кодами ITA2, переходами FIGS/LTRS, поддерживаемыми знаками и управляющими группами, неверными входными данными, примером C ⊕ M = L, ручной трассой моторных шагов, оборотом колеса, обратным шифрованием на десяти наборах узоров, обработкой по частям, повтором ключа и восстановлением пары χ1/χ2.

19. Сравнение с Enigma

Машины реализуют разные преобразования и дают разные возможности криптоаналитику.

Enigma M3 с отражателем не шифрует букву в саму себя.

Lorenz способен оставить пятибитную группу неизменной, когда текущий ключ равен нулю. Это следует непосредственно из P ⊕ 0 = P.

Colossus использовался против Tunny, а не для взлома Enigma. Для Enigma были другие методы и устройства. Названия машин и их назначения полезно сверять по музейным описаниям TNMOC и исходной статье об Enigma M3.

20. Наследие, скрытое из-за секретности

После войны восемь из десяти Colossus уничтожили, а два оставшихся ещё служили британской разведке до начала 1960-х. Все, кто участвовал в дешифровке, не могли свободно рассказывать о своей работе из-за военной тайны.

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

Судьба аппаратуры прекрасно и подробно описана тут GCHQ в материале к 80-летию Colossus.

Секретность снималась постепенно. Первые существенные сведения и фотографии Colossus стали публичными в 1970-х, а детали криптоанализа — значительно позднее. Отчёт General Report on Tunny рассекретили в 2000 году. Поэтому неверно говорить и «всё стало известно в 1975-м», и «о Colossus никто не знал до 2000-х». Разные части истории в итоге были раскрыты в разное время. Историю первых публикаций хорошо осветил Брайан Рэнделл.

В TNMOC сегодня работает реконструкция Colossus, созданная командой Тони Сейла. Она была испытана впервые на международном Cipher Challenge 2007 года.

Рядом можно увидеть восстановленный British Tunny. Он позволяет всем интересующимся пройти весь путь от перехвата до открытого текста и увидеть, насколько различались устройства по обе стороны линии. История проекта есть в самом музее.

Сайты и литература

Сайты, архивы и интерактивные модели

1. The National Museum of Computing: Colossus — характеристики, история и работающая реконструкция; галереи музея — Tunny и другие машины.

2. TNMOC: Virtual Lorenz — музейный проект изучения шифровальной приставки.

3. Martin Gillow: Virtual Lorenz — интерактивная трёхмерная модель, варианты SZ 40/42; техническое описание — колёса и механика.

4. Virtual Colossus — эмулятор Colossus; объяснение статистических атак.

5. Tony Sale: статистика атаки на Lorenz; уязвимости; Lorenz Cipher Event.

6. Frode Weierud’s CryptoCellar: The Secrets of the Lorenz Schlüsselzusatz SZ42 — немецкие руководства, переводы, документы TICOM, узоры колёс и ключевые книги.

7. Crypto Museum: Lorenz SZ-40/42 — обзор семейства, материалы и ссылки на аппаратуру.

8. GCHQ: секретные станции перехвата; Билл Татт; Макс Ньюман; Шон Уайли; 80-летие Colossus.

9. ITU-T Recommendation S.1: International Telegraph Alphabet No. 2 — стандарт ITA2; историческая таблица импульсов ITU.

10. Deutsches Museum: Chiffrierfernschreibmaschine Lorenz SZ 42 — музейный объект 81019.

11. TNMOC: The Hidden Figures of Colossus — инженеры, интервью и история команды.

Первоисточники и исследования

1. I. J. Good, D. Michie, G. Timms. General Report on Tunny: With Emphasis on Statistical Methods, 1945. Веб-версия разделов отчёта. Научное издание: Breaking Teleprinter Ciphers at Bletchley Park, под редакцией James A. Reeds, Whitfield Diffie и J. V. Field, Wiley / IEEE Press, 2015. ISBN 978-0-470-46589-9.

2. John H. Tiltman. The “Tunny” Machine and Its Solution, 1961 — изложение раннего анализа самим участником работы.

3. T. H. Flowers. The Design of Colossus. Annals of the History of Computing, 5(3), 1983, pp. 239–252.

4. Donald W. Davies. The Lorenz Cipher Machine SZ42. Cryptologia, 19(1), 1995, pp. 39–61. Библиографические сведения и ссылка на издателя — в CryptoCellar.

5. B. Jack Copeland, editor. Colossus: The Secrets of Bletchley Park’s Codebreaking Computers. Oxford University Press, 2006. ISBN 0-19-284055-X.

6. B. Jack Copeland. Colossus: Breaking the German ‘Tunny’ Code at Bletchley Park. An Illustrated History. The Rutherford Journal, vol. 3, 2010.

7. Paul Gannon. Colossus: Bletchley Park’s Greatest Secret. Atlantic Books, 2006. ISBN 1-84354-330-3.

Если вы заметите какие-то неточности, или что-то, чем следовало бы дополнить статью — пишите в личных сообщениях или комментариях ниже, будет полезно, я внесу.