Эта статья посвящена взлому Энигмы польскими криптографами. Описание строения Энигмы можно прочитать в первой части

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

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

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

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

Опишем сообщения, которыми располагал Реевский. У операторов Энигмы были кодовые книги, в которых содержались ключи на каждый день. Ключ – это настройки Энигмы: порядок роторов, настройки роторов, настройки колец, настройки коммутационной панели.

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

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

Пример:

Пусть дневные настройки роторов – 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

∎

В среднем требовалось около 60 сообщений, чтобы заполнить все буквы в табличках для всех трёх перестановок.

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

Определение:

$S$ – перестановка, заданная коммутационной панелью
$N, M, L$ – перестановки, заданные роторами
$R$ – перестановка, заданная рефлектором
$H$ – перестановка между коммутационной панелью и первым ротором

Тогда шифрование Энигмы описывается уравнением:

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

Но ещё нужно учесть, что ротор $N$ вращается перед шифрованием каждой буквы на одну позицию. При этом вращение роторов $M$ и $L$ не учитываются, по причинам, описанным выше.

Определение:

Циклическая перестановка $P$ – перестановка, которая сдвигает буквы на одну вперёд:
$ P = \begin{pmatrix} a & b & c & … & z \\ b & c & d & … & a \end{pmatrix} $

Определение:

$A$ – перестановка, которая получается при шифрровании Энигмой первой буквы
$B,C,D,E,F$ – аналогичные перестановки для 2-6 буквы

Выпишем выражения для $A,B,C,D,E,F$ с учётом вращения ротора $N$:

$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$

Введение в теорию перестановок

Определение:

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

Определение:

Транспозиция – цикл, состоящий из двух элементов.

Определение:

Цикловая структура перестановки – набор чисел, обозначающий число циклов каждой длины.

Пример:

Цикловая структура перестановки
$ 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 (f-e) (он является транспозицией). Мы можем записать перестановку в цикловом виде: $X = (abcd)(ef)$

∎

Теорема:

∎

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

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

Доказательство:

Обозначим $K=LMP^{-1}NPHS$, то есть всё, кроме рефлектора. Тогда $A = K^{-1}RK$. По теореме цикловая структура перестановки $A$ такая же, как у рефлектора $R$, т. е. состоит только из транспозиций букв, а значит $A=A^{-1}$. Аналогично для остальных перестановок.

Обозначим первую букву ключа $x$, а первую и четвёртую букву зашифрованного сообщения – $u$ и $v$.
$A(x) = u$
$D(x) = v$

$D(A^{-1}(u)) = D(A(u)) = DA(u) = v$
Это означает, что перестановка первой и четвёртой буквы есть ни что иное как последовательное применение перестановок $DA$, второй и пятой буквы – $EB$, третьей и шестой – $FC$.

∎

Примечание

Можно встретить обозначения $AD, BE, FC$ для тех же самых перестановок в других источниках. В таких обозначениях подразумевается, что аргумент пишется слева, а перестановки применяются слева-направо.

Реевский перешёл к анализу свойств перестановок $DA, EB, FC$. Если разложить их на отдельные перестановки $A-F$ то это позволит узнать ключи сообщений. Пока это не позволяет расшифровывать сами сообщения, но уже кое-что.

Используя теорию перестановок и оплошности операторов, Реевскому удавалось иногда находить перестановки $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$ ничего не переставляет, исключим её из уравнения и перенесём в левую часть всё, что известно:

$U = PSAS^{-1}P^{-1} = N^{-1}PQP^{-1}N$
$V = P^{2}SAS^{-1}P^{-2} = N^{-1}P^{2}QP^{-2}N$
…
$Z = P^{6}SAS^{-1}P^{-6} = N^{-1}P^{6}QP^{-6}N$

Построим попарные композиции перестановок:

$WV = N^{-1}PN(UV)N^{-1}P^{-1}N$
$XW = N^{-1}PN(WV)N^{-1}P^{-1}N$
$XY = N^{-1}PN(WX)N^{-1}P^{-1}N$
$YZ = N^{-1}PN(XY)N^{-1}P^{-1}N$

Из этой системы уравнений можно найти перестановку $N^{-1}PN$, удовлетворяющую всем уравнениям. Таким образом, можно найти $N$. Проводка одного из роторов была восстановлена.

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

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

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

Grill метод

Метод основан на том, что коммутационная панель переставляет всего 6 букв, а значит большая часть букв не изменяется.
Представим, что коммутационной панели нет, т.е. $S=I$. Обозначим положение ротора $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$ переставляет всего 6 букв, оставляя остальные на месте, левые части почти совпадут. В этом и состоит суть метода: нужно найти такое $x$ чтобы перестановки в левой части стали похожи, а затем методом проб и ошибок найти, какие буквы переставляет $S$.

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

Циклометр

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

Нужны были новые идеи, и криптоаналитики вернулись к анализу перестановок $DA, EB, FC$. Так как коммутационная панель применяется и в начале и в конце шифрования, то по теореме о цикловой структуре $S$ не влияет на цикловую структуру $DA, BE, FC$. Поэтому возникла идея построить таблицу: для каждого положения роторов записать цикловую структуру перестановок $DA, EB, FC$. Оказалось, что цикловая структура практически уникальна для каждого положения роторов. Для построения таблицы было сделано специальное устройство – Циклометр.

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

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

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

Пример:

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

∎

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

Пример:

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

∎

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

Для работы были сделаны листы: для все вариантов расположений роторов, для всех возможных положений ротора $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” перебирала все возможные положения колец и проверяла совпадение букв.

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

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

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

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

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

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

📢тг-канал