Как польские математики взломали Энигму17.12.2023 16:45

Мариан Реевский, Ежи Ружицкий, Генрих Зыгальский

В начале 1929 года польское подразделение военной разведки «Бюро шифров» организовало в Познанском университете засекреченный курс по криптографии для небольшой группы студентов-математиков. В 1932 году три выпускника курсов: Мариан Реевский, Ежи Ружицкий и Генрих Зыгальский приступили к работе в Бюро. Они получили задание по взлому Энигмы.

Польские криптоаналитики располагали только описанием коммерческой версии Энигмы. Они не знали строения военной версии, которая немного отличалась от коммерческой. Задачу по восстановлению строения машины поручили Мариану Реевскому.

Строение Энигмы

Внешний вид Энигмы

Энигма шифрует сообщения побуквенно. Оператор вводит буквы на входной клавиатуре, электрический сигнал проходит по схеме, и в результате на выходной клавиатуре под зашифрованной буквой загорается лампочка. Электрическая схема состоит из нескольких элементов:
S — коммутационная панель
H — начальная перестановка
N, M, L — роторы
R — рефлектор

Схема Энигмы

Роторы

Главной частью машины являются три ротора. Ротор — это диск, в котором с одной и другой стороны по кругу есть 26 электрических контактов, обозначенных буквами. Внутри диска контакты соединены проводами. Таким образом, ротор задаёт перестановку букв. При шифровании роторы вращаются, изменяя перестановку: самый быстрый ротор N вращается для каждой буквы, средний ротор M после того как N сделает полный оборот, а медленный L — после того как полный оборот сделает M. Оператор может выбирать порядок расположения роторов в машине и начальное положение каждого ротора.

Вокруг каждого ротора есть кольцо. Оно тоже настраивается оператором и задаёт сдвиг перестановки ротора. Также кольцо содержит зацепку, которая и вращает соседний ротор.

Рефлектор

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

Коммутационная панель

После входной клавиатуры находится коммутационная панель S. У оператора есть 6 проводов, которым он может соединить 6 пар букв на этой панели. Это приводит к попарной замене букв до и после прохождения всех роторов.

Начальная перестановка

Между коммутационной панелью и первым ротором находится ещё одна панель H, реализующая перестановку букв. Оператор не может её настраивать. Обычно при описании строения Энигмы эту панель опускают, далее станет понятно почему.

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

$E(x) = S^{-1}H^{-1}N^{-1}M^{-1}L^{-1}RLMNHS(x)$

Ключом шифрования являются начальные настройки машины, состоящие из:

Положения роторов
Настроек роторов
Настроек колец
Соединений коммутационной панели

Структура сообщений

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

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

Пример:

Дневные настройки роторов — cvb. оператор выбирает новое положение роторов, например, kjh и шифрует его два раза, получается qns mpd (хотя одна и та же тройка букв шифруется два раза, результат получается различный, потому что роторы в Энигме сдвигаются, что меняет перестановку). Далее оператор пишет в начале сообщения qns mpd, ставит роторы в положение kjh и шифрует сообщение, которое нужно передать.

Начало анализа

Таким образом, первая и четвёртая буква сообщения — это одна и та же зашифрованная первая буква трёхбуквенного ключа сообщения. Аналогично, 2–5 и 3–6 буквы. Реевский начал рассматривать связи между этими парами букв и строить перестановки между ними.

Пример:

Перехваченные сообщения:
dmq vbn
von puy
kuc fmq

Если посмотреть на первые и четвертые буквы сообщений, то имеем пары:
d-v, v-p, k-f

Для второй и пятой буквы:
m-b, o-u, u-m

Для третьей и шестой буквы:
q-n, n-y, c-q

Перед началом анализа нужно учесть одну особенность работы колец. Если бы на кольцах не было зацепки, вращающей следующий ротор, то их вообще можно было бы не учитывать при криптоанализе. Потому что вместо того, чтобы сначала повернуть ротор, а затем кольцо на нём, можно сразу повернуть ротор два раза и получить такой же результат шифрования. Но на самом деле зацепки на кольцах есть, и это влияет на шифрование. Польские криптоаналитики не учитывали поворот среднего (и соответственно, медленного) ротора для упрощения анализа, так как для сообщений из 6 букв средний ротор не будет двигаться в 20 из 26 случаев.

Обозначим A, B, C, D, E, F — перестановки, которые реализуются Энигмой при шифровании 1,2,3,4,5,6 буквы соответственно. Выпишем выражения для A, B, C, D, E, F с учётом вращения ротора N. Здесь P — это циклическая перестановка, сдвигающая буквы на одну вперёд: a-b, b-c,…, z-a.

$A = S^{-1}H^{-1}P^{-1}N^{-1}PM^{-1}L^{-1}RLMP^{-1}NPHS$
$B = S^{-1}H^{-1}P^{-2}N^{-1}P^{2}M^{-1}L^{-1}RLMP^{-2}NP^{2}HS$
…
$F = S^{-1}H^{-1}P^{-6}N^{-1}P^{6}M^{-1}L^{-1}RLMP^{-6}NP^{6}HS$

Первые успехи

В Энигме шифрование и расшифрование — это обратные операции. Если нажать букву w и загорится лампочка под v, то при нажатии v лампочка загорится под w. Это означает, что перестановки A–F состоят только из попарных замен букв, а значит, обратны самим себе. А в этом случае перестановка первой и четвёртой буквы — это последовательное применение перестановок DA, второй и пятой буквы — EB, третьей и шестой — FC.

Реевский перешёл к анализу свойств перестановок DA, EB, FC. Используя теорию перестановок и оплошности операторов, Реевскому удавалось иногда раскладывать их на отдельные перестановки A–F. Например, в пылу сражения операторы часто выбирали предсказуемые ключи, состоящие из трёх одинаковых букв: aaa, bbb и т. п. Эта дополнительная информация позволяла упростить анализ перестановок. Польские криптоаналитики следили за практиками немецких криптографов. Например, когда им запретили выставлять ключи из трёх одинаковых букв, они стали избегать повторения даже одной буквы, что тоже давало дополнительную информацию.

Восстановление строения машины

В декабре 1932 года агент Ганс Тило-Шмидт, который работал в шифровальном отделении имперского министерства обороны в Берлине, передал французам немецкие документы, в том числе использованные комплекты дневных ключей Энигмы за сентябрь и октябрь 1932 года, а также инструкции по работе с машиной. 9 декабря 1932 года Реевский получил фотокопии таблиц дневных ключей и инструкций. Поскольку в дневной ключ входит перестановка на коммутационной панели, при анализе сообщений за сентябрь и октябрь Реевский мог исключить её из уравнений.

Обозначим $Q=M^{-1}L^{-1}RLM$ , тогда уравнения для перестановок принимут вид:

$A = S^{-1}H^{-1}P^{-1}N^{-1}PQP^{-1}NPHS$
$B = S^{-1}H^{-1}P^{-2}N^{-1}P^{2}QP^{-2}NP^{2}HS$
…
$F = S^{-1}H^{-1}P^{-6}N^{-1}P^{6}QP^{-6}NP^{6}HS$

Задача состоит в том, чтобы найти неизвестные N, H, Q.

Реевский принялся за H — перестановку между коммутационной панелью и первым ротором, которая в коммерческом варианте машины была:

$H = \begin{pmatrix} abcdefghijklmnopqrstuvwxyz \\\ qwertzuioasdfghjkpyxcvbnml \end{pmatrix}$

Он пробовал как этот вариант, так и множество других, но все они не приводили к успеху. Потратив много времени, он обратил внимание, что нижняя строка — это порядок букв на клавиатуре Энигмы. Тогда Реевский предположил, что в военной версии эта перестановка сделана в алфавитном порядке: a-a, b-b и так далее. Поразительно, но его интуитивная догадка оказалась верной, и именно она в результате позволила восстановить строение машины. Позднее Реевский писал, что восстановить H можно было и без угадывания, однако, это потребовало бы большого количества сообщений и более сложных вычислений. После исключения H Реевский смог найти из системы уравнений проводку первого ротора.

И здесь польским криптоаналитикам повезло. Немцы в то время меняли порядок роторов раз в квартал, а сентябрь и октябрь как раз относятся к разным кварталам, и в октябре на первом месте стоял другой ротор. Благодаря этому удалось восстановить проводку второго ротора. Третий ротор и рефлектор Реевский восстановил благодаря тому, что в инструкции по эксплуатации содержался пример работы с машиной, включающий довольно длинный открытый и зашифрованный текст.

После того как Реевский разгадал структуру Энигмы, Бюро шифров поручило компании AVA Radio разработать копии Энигмы. Теперь у Бюро были рабочие машины, и можно было приступать к взлому ключей.

Взлом дневного ключа

Grill метод

Метод основан на том, что коммутационная панель переставляет всего 6 пар букв. Представим, что коммутационной панели нет, т. е. S можно исключить из уравнений. Обозначим положение ротора N как x и выпишем уравнения для Q:

$Q = P^{-x}NP^{x}AP^{-x}N^{-1}P^{x}$
$Q = P^{-x - 1}NP^{x + 1}BP^{-x - 1}N^{-1}P^{x + 1}$
…
$Q = P^{-x - 5}NP^{x + 5}FP^{-x - 5}N^{-1}P^{x + 5}$

При каком-то x от 1 до 26, все левые части станут одинаковыми — это и будет искомое положение ротора N. Однако на самом деле S присутствует, поэтому точного совпадения не будет. Но поскольку S переставляет не все буквы, левые части почти совпадут. В этом и состоит суть метода: нужно найти такое x чтобы перестановки в левой части стали похожи, а затем найти, какие именно буквы переставляет S.

После этого положение двух остальных роторов L и M находится с помощью перебора всех 676 вариантов по известному значению Q. Положение колец находится также перебором всех вариантов. Перебор осуществляется до тех пор, пока сообщения не начнут читаться. Например, использовалось то, что сообщения часто начинались с букв «anx» («an» обозначало «кому» , а «x» использовался как пробел). В результате дневной ключ полностью восстановлен. Grill метод был утомительным, требовал внимательности и терпения.

Циклометр

С 1 октября 1936 года количество замен на коммутационной панели стало варьироваться от 5 до 8, вместо прежних 6. А с 1 ноября порядок роторов стал меняться ежедневно. Это сильно усложнило использование Grill метода.

Нужны были новые идеи, и криптоаналитики вернулись к анализу перестановок DA, EB, FC.

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

Пример:

Цикловая структура перестановки
$X = \begin{pmatrix} a & b & c & d & e & f \\\ b & c & d & a & f & e \end{pmatrix}$

состоит из 1 цикла длины 4: a-b-c-d и 1 цикла длины 2: e-f.

Несложно показать, что коммутационная панель не влияет на цикловую структуру, она определяется только положением роторов. Поэтому возникла идея построить хеш-таблицу: для каждого положения роторов вычислить цикловую структуру перестановок DA, EB, FC, а при анализе определять положение роторов по цикловой структуре. И действительно оказалось, что цикловая структура практически уникальна для каждого положения роторов. Для вычисления таблицы было сделано специальное устройство — Циклометр.

Циклометр

Понадобилось больше года чтобы завершить построение таблицы. Но после этого определение дневного ключа занимало всего 10–15 минут: криптоаналитик строил перестановки DA, EB, FC, затем по таблице находил положение роторов. Чтобы восстановить коммутационную панель, криптоаналитик строил перестановки для найденного положения роторов без коммутационной панели и сравнивал их с оригинальными перестановками DA, EB, FC. В результате находил, какие пары букв заменялись коммутационной панелью. Наконец, положение колец по-прежнему находилось перебором.

Листы Зыгальского

2 ноября 1937 года в машине был изменён рефлектор. Всю работу, начиная с определения строения рефлектора, пришлось проделывать заново. А 15 сентября 1938 года изменилась процедура передачи сообщений: теперь оператор не шифровал ключ сообщения на дневном положении роторов, а сам выбирал положение роторов для каждого сообщения и передавал его в открытом виде.

Пример:

Оператор выбирает положение роторов svb и устанавливает их в это положение. Затем он выбирает новое положение роторов tux и шифрует его два раза, получает pkj qdm. Наконец, он устанавливает роторы в положение tux и шифрует само сообщение. В итоге получается: svb pkj qdm …

Циклометр стал бесполезен, так как больше нельзя было построить перестановки DA, EB, FC для дневного положения роторов. Польские криптоаналитики начали искать новые идеи. Они обратили внимание, что иногда попадаются сообщения, в которых одна и та же буква ключа шифровалось в одинаковую букву. Такие сообщение назывались female-парами.

Пример:

Сообщение cde crt — это 1–4-female пара. Так как первая и четвёртая буква — это одинаковая буква c.

Наличие female-пары означает, что в одной из перестановок DA, EB, FC буква отображается в себя. Но это характерно далеко не для всех перестановок, поэтому можно построить таблицу перестановок DA, EB, FC для всех положений роторов и отметить те, в которых подобное имеет место. При анализе сообщений с female-парами настройки отсеиваются до тех пор, пока не останется единственный вариант — это позволит определить дневное положение колец. После, перебором всех вариантов, определяется дневное положение роторов.

Для работы были сделаны листы: для все вариантов расположений роторов, для всех возможных положений ротора L строится матрица со всеми возможными положениями роторов M и N. Если в перестановке буква остаётся на месте — в листе прокалывается отверстие. В процессе анализа листы накладывались друг на друга, пока не оставалось одно открытое отверстие — это и была дневная настройка колец. Настройки коммутационной панели находились аналогично предыдущим методам.

Лист Зыгальского

В целях безопасности листы изготавливались в Бюро криптоаналитиками самостоятельно, работа было большая и требовала много времени. К концу 1938 года было готово только два комплекта листов из шести.

Криптологическая бомба

При достаточном количестве сообщений можно было найти три female-пары, в которых к тому же совпадала буква.

Пример:

cde crt — 1–4 пара
kcz dcf — 2–5 пара
wmc pac— 3–6 пара

Во всех парах одинаковая буква c

Если расшифровать эти сообщения, то при правильном положении колец в первом сообщении совпадёт 1 и 4 буква, во втором — 2 и 5, а в третьем — 3 и 6. При неправильной настройке такое совпадение маловероятно. На этом и основан метод. Машина под названием Bomba перебирала все возможные положения колец и проверяла совпадение букв.

Схема Bombe

Каждая Бомба состояла из трёх пар Энигм. Бомба перебирала все возможные настройки колец и проверяла, что в каждой паре при расшифровке получилась одинаковая буква. Если это происходило — цепь замыкалась, и машина останавливалась. Иногда остановка была ложной — все случаи разбирались криптоаналитиками вручную. Всего было 6 Бомб (по одной на каждое возможное расположение роторов). Этот метод вскрывал дневной ключ примерно за 2 часа.

Можно было использовать и female-пары с различными буквами. Но нужно учесть, что коммутационная панель имела 5–8 проводов, то есть задействовала примерно половину букв, а чтобы метод работал, обязательно нужно, чтобы зашифрованная буква не изменялась коммутационной панелью. При одной и той же букве эта вероятность около 50%, а при трёх различных — около 12.5%. Польские криптоаналитики выбрали более надёжный, но требующий больше сообщений метод.

Конец работы Бюро

15 декабря 1938 года были добавлены два новых ротора. Теперь оператор выбирал 3 ротора из 5 возможных, что увеличило количество вариантов в 10 раз: с 6 до 60. У Бюро не было ресурсов сделать нужное число Бомб и листов Зыгальского. А с 1 января 1939 года число соединений на коммутационной панели увеличилось до 10, что затруднило поиск букв, не задетых коммутационной панелью и ещё уменьшило эффективность Бомбы. Летом 1939 года стало ясно, что Польше не удастся остановить вторжение. Было принято решение эвакуировать Бюро и передать союзникам наработки и оборудование.

25 и 26 июля 1939 года польские криптоаналитики на встрече показали представителям Франции и Великобритании свои результаты, продемонстрировали рабочие копии Энигмы и объяснили методы взлома. Как писал Реевскй, они ничему не научились у своих гостей: те не знали методов взлома, и даже не смогли восстановить строение машины. После вторжения немцев в Польшу, вся работа Бюро была уничтожена в целях безопасности, а Бюро эвакуировано во Францию. Эстафета взлома перешла к Британии.

Ещё больше интересного можно прочитать в моём Телеграм-канале