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

После изобретения Энигмы в 1917 году, начиная с 1930 года этот инновационный метод шифрования стал регулярно применяться в Германии. Её соседи, особенно Франция, Великобритания и Польша относились к нему с подозрением, особенно после прихода нацистов к власти, когда Энигма стала играть ключевую роль в перевооружении Вермахта. Несмотря на то, что французские и британские криптоаналитики её взломать не смогли и классифицировали как невзламываемую[2], 27-летний польский математик Мариан Реевский уже в 1932 году смог взломать Энигму[3], обнаружив серьёзную уязвимость в процедуре отправки сообщений.

Для расшифровки сообщений с помощью Энигмы требовалось знать несколько параметров: порядок роторов, их начальные позиции, положения колец роторов и соединения коммутационной панели. Позиции роторов представляли собой ключ из трех букв (например, «PDN») и являлись частью дневного ключа. Для дополнительной безопасности, тем не менее, каждое индивидуальное сообщение было зашифровано с использованием дополнительной модификации ключа. Оператор случайно выбирал настройки ротора для каждого сообщения (например, «PDN»). Ключ этого сообщения набирался дважды («PDNPDN») и зашифрован с использованием дневного ключа. Затем оператор сбрасывал машину на ключ сообщения, который использовался в дальнейшем.[1] Поскольку внутренняя разводка проводов Энигмы изменялась с каждым нажатием клавиши, повторение не будет очевидным в шифртексте, так как одни и те же буквы открытого текста будут зашифрованы в различные буквы шифртекста (например, «PDNPDN» может стать «ZRSJVL»).

Вместо повторения ключа и затем его шифрования, немцы могли просто шифровать ключ сообщения и отправлять его два раза подряд (например, «ZRSZRS»), или в начале и в конце сообщения. При этом все равно будет достигнута желаемая избыточность для возможности детектирования ошибок. Однако это бы стало очевидным недостатком, поскольку подозрительное повторение будет привлекать внимание криптоаналитиков. Для предотвращения такой ситуации они стали применять, на первый взгляд, надежный вариант с копированием ключа и его последующим шифрованием, поскольку повторение в шифртексте не было заметным. В действительности такой метод привел к грубой криптографической ошибке.

Также стоит отметить, что оператор устройства мог свободно выбирать ключ. Они, особенно в стрессовых ситуациях, выбирали очень простые ключи. Вместо желаемого случайного ключа часто выбирались простые сочетания букв вроде «AAA», «ABC» или «ASD» (рядом расположенные клавиши на клавиатуре устройства), которые взломщики могли просто отгадать.[4] Кроме того, выбранный ключ шифровался самой Энигмой, что раскрывало выбранную конфигурацию устройства. С другой стороны, если бы использовался независимый метод шифрования ключа сообщения, внутреннее устройство Энигмы определить бы не удалось. На самом деле, шифрование ключа вообще не требовалось. Он мог транслироваться в незашифрованном виде, повторенный дважды или даже трижды (в этом случае была бы возможность не только детектировать помехи, но и устранять их). Из-за неизвестного положения колец роторов положение самих роторов не несет какой-либо важной информации для криптоаналитика. Вместо этого, процедура удвоения ключа позволила польским криптоаналитикам дешифровать сообщения[5].

Циклометр

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

Циклометр позволил полякам определить для каждого из шести возможных порядков роторов характерные перестановки для каждой из 26³ = 17 576 начальной позиции роторов. Циклометр существенно упрощал утомительную и затратную по времени работу по поиску характеристик в каждом из 6 × 17 576 = 105 456 возможных случаев. Полученные характеристики записывались в каталог. Работа по разработке каталога характеристик, как заметил Реевский, «была утомительной и заняла больше года, но после её завершения дневные ключи могли быть определены за 15 минут»[6].

После замены рефлектора UKW-A на UKW-B 1 ноября 1937 года[7] польским криптоаналитикам пришлось составлять новый каталог характеристик. Но перед тем, как они смогли завершить этот процесс, немцы изменили протокол передачи ключа сообщения[5]. Вместо определённого положения роторов для зашифровки ключа сообщения теперь оператор мог выбрать его произвольно и передавал в незашифрованном виде в начале сообщения[8]. Внезапно каталог характеристик стал бесполезным, и Бюро шифров стало работать над новыми методами атаки на шифр Энигмы. Это привело к созданию листов Зыгальского и бомбы Реевского.

Происхождение названия «бомба» остается загадкой. Даже после войны Мариан Реевски не мог этого вспомнить[9]. По рассказам Тадеуша Лисицкого, Реевский, Рожицкий и Зыгальский ели пирожное «бомба», когда Рожицкий предложил название устройства. По другой версии, звук, издаваемый устройством во время его работы напоминал тиканье часового механизма бомбы, что стало причиной такого названия. Поскольку до наших дней не сохранилось ни одной машины, эту версию проверить невозможно. По утверждению самого Реевского, «из-за отсутствия лучшего варианта мы называли их бомбами»[1].

Идея бомбы основывается исключительно на ненадежной процедуре удвоения ключа. Поляки не знали ни позиций роторов, ни позиций колец. Кроме того, начальная позиция роторов не была однозначной, а выбиралась свободно шифровальщиком. Несмотря на это, оставалось ясным, что сессионный ключ сначала удваивался, а затем шифровался. Отсюда польские криптоаналитики могли заключить что первой и четвёртой, второй и пятой, а также третей и шестой буквам шифртекста соответствовали одинаковые буквы открытого текста. Это важное замечание позволило провести поиск по шаблону «123123».[10]

Схематичное изображение бомбы:
1 — роторы (один установленный набор роторов и пять шпинделей для установки других наборов)
2 — электромотор
3 — три набора переключателей

Техническое исполнение атаки на шифр Энигмы заключалось в создании электромеханической машины, включающей шесть наборов роторов Энигмы. Поляки смогли не только быстро разработать концепт бомбы, но и собрать и ввести их в работу при поддержке AVA (AVA Wytwórnia Radiotechniczna). Поскольку на тот момент существовало шесть различных порядков роторов Энигмы, шесть бомб было построено, по одной на каждый порядок. Приводящаяся в движение от электрического мотора, бомба проходила через все 17576 различных позиций роторов (от «AAA» до «ZZZ») за примерно 110 минут[11].

Атака заключалась в поиске позиций, в которых при вводе определённой тестовой буквы, выходная буква совпадала с выходной буквой для позиции, смещенной на три вперед. Поскольку каждая бомба имела шесть наборов роторов, можно было проверять три сообщения одновременно. Искали позиции в которых во всех трех парах были одинаковые буквы.[1]

Такое совпадение случалось довольно редко, и было сильным признаком успеха, то есть правильно определённых порядка роторов и положения колец. Но следовало ожидать и неудач, таких настроек, которые тоже дают попарные совпадения букв, но не являющихся ключом.[10] В среднем на одну позицию роторов приходилась одна неудача. Польские криптоаналитики использовали специально спроектрированные реплики Энигм для определения неудач и поиска правильных соединений коммутационной панели. Они были настроены с использованием полученных с помощью бомбы возможного порядка роторов и положения колец.[10]

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

Конкретное применение бомбы может быть продемонстрировано на следующем примере. Предположим, что применялась процедура удвоения ключа, как это было в период с 15 сентября 1938 года. Пусть в качестве дневного ключа порядок роторов был «B123», положение колец роторов «abc», а штекеры коммутационной панели были «DE», «FG», «HI», «JK» и «LM». Оператор случайно выбирал начальную позицию, например «BVH», и ключ сообщения, например «WIK». Как объяснялось ранее, ключ сообщения удваивался и шифровался при выбранных дневном ключе и начальном положении роторов. В результате (что может быть проверено свободно доступными симуляторами Энигмы) получается зашифрованный ключ сообщения, который отправляется вместе с незашифрованной начальной позицией, как индикатор шифртекста, в данном примере «BVH BPLBKM».

Криптоаналитикам сначала необходимо было перехватить как можно больше сообщений и рассмотреть индикаторы в каждом случае. Целью было найти три зашифрованных ключа сообщения, в которых первая и четвёртая, вторая и пятая и, наконец, третья и шестая буквы совпадали.[1] Пример выше удовлетворяет данному условия. Осталось найти ещё два индикатора, где вторая и пятая или третья и шестая буквы тоже «B».

В принципе, вместо поиска трех одинаковых неподвижных точек (как называли парные буквы в удвоенном и зашифрованном ключе)[10] можно было использовать три различные точки. Это упростило бы поиск подходящих индикаторов, поскольку индикаторы с тремя различными парами встречаются чаще. Однако из-за наличия коммутаторной панели, пары преобразуются до и после прохода панели неизвестным полякам образом. Вставала необходимость удачно выбрать букву, не изменяющуюся в панели (self-plugged)[12], в противном случае дешифровка бы не удалась. При пяти-восьми проводах панели, как это было принято в 1938 году, вероятность удачного взлома составляет 50 %. С другой стороны, при использовании трех различных пар, эта вероятность падает до 12,5 %[10]. По этой причине поляки выбрали более редкую, но более эффективную комбинацию из трех одинаковых неподвижных точек.

Пусть после перехвата нескольких немецких сообщений были также найдены индикаторы «DCM WBVHBM» и «EJX NVBUUB». Таким образом имеется набор из трех совпадающих неподвижных точек:

1) BVH BPLBKM 2) DCM WBVHBM 3) EJX NVBUUB

Для дальнейшего понимания следует ввести понятие разности (или расстояния) между двумя позициями роторов. Доподлинно неизвестно, как нумеровались позиции в Бюро шифров. Британцы в Блетчли-парк использовали следующее соглашение: каждой позиции соответствовало трехзначное число в двадцатишестиричной системе счисления, где «Z» была нулем, «A» — единицей и так далее до «Y» — 25.[13] Тогда разностью между двумя позициями была разность соответствующих им чисел. В нашем примере разность между позициями «BVH» и «DCM» будет «AGE», а между «DCM» и «EJX» — «AGK».

Для взлома Энигмы, криптоаналитики настраивали бомбы следующим образом. Каждая из шести машин соответствовала различным порядкам роторов, один из которых — нужный вариант «B123». Шесть наборов роторов на одной бомбе образовывали три пары. Расстояние между роторами в одной паре равнялось трем, а расстояние между парами соответствовало расстояниям между конфигурациями в перехваченных сообщениях.[14] Затем запускался мотор, и все 17576 позиций проходились меньше, чем за два часа.

Целью был поиск таких позиций, в которых все наборы роторов в бомбе дают одинаковую букву на соответствующей позиции. Такое совпадение проверялось с помощью простого реле[10]. Для примера выше с роторами «B123» и тестовой буквой «B» получаются только две позиции. Первая оказывается промахом, а вторая дает три начальных позиции (все ещё нормированных на положение колец «aaa») «BUF», «DBK» and «EIV».

Простым поиском разности между найденными позициями и позициями в перехваченных индикаторах и её суммированием с «aaa» можно определить положение колец роторов.[15] В примере выше во всех трех случаях получается «abc».

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

1) BVH BPLBKM → WHHWSF 2) DCM WBVHBM → HPDIPZ 3) EJX NVBUUB → EHAEHA

Искомый шаблон «123123» уже виден в третьем случае, но пока результат необязательно правильный. Причиной этому является все ещё пустая коммутаторная панель. Последней задачей осталось определение этой настройки, использованной немцами (от пяти до восьми проводов). Четкий алгоритм поиска отсутствовал, вместо этого применялся метод проб и ошибок с целью нахождения такой настройки, при которой во всех трех случаях получалось сообщение вида «123123».[14] Хорошим ходом действий будет соединение ещё не совпадающих букв в парах, например «H» и «I» во втором случае. Это улучшает возможный ключ сообщения от «HPDIPZ» до «IPDIPZ». Теперь имеется две совпадающих пары вместо одной. Это сильный признак правильно определённого соединения. Другой многообещающей попыткой является соединений соответствующих букв шифртекста вместо букв открытого текста. Как известно, ток проходит через панель дважды, один раз в форме открытого текста, один раз после прохода роторов. Например, в первом случае, третья («H») и шестая («F») возможного ключа сообщения «WHHWSF» не совпадают. Соединение «FH» ситуации не улучшает. С другой стороны, соединение третьей и шестой буквы шифртекста («L» и «M») приводит к результату «WHYWSY». Опять, паре одинаковых букв шифртекста теперь соответствует пара одинаковых букв открытого текста, а значит, ещё было правильно определено ещё одно соединение панели. Теперь при соединенных парах «HI» и «LM» расшифровка в первом случае дает текст «WIJWSJ», а во втором — «IPDIPD» где уже прослеживается шаблон «123123». Правильно определив соединение «JK», которое может быть отгадано из получившихся букв, первое сообщение при расшифровке также будет удовлетворять нужному шаблону, и ключ сообщения «WIKWIK» будет окончательно взломан. Два последних соединения «DE» и «FG» могут быть найдены при попытке дешифровки сообщения с начальной позицией роторов «WIK», после чего окончательно будут найдены дневные настройки Энигмы, и расшифровка остальных сообщений не составит труда.

Шесть бомб помогли полякам продолжить расшифровывать сообщения после введения свободного начального состояния роторов 15 сентября 1938 года. Однако 15 декабря 1938 года появилась новая проблема. Немцы стали использовать два новых ротора (IV и V). Следовательно, число различных позиций роторов увеличилось с шести (=3•2•1) до шестидесяти (=5•4•3)[5]. Вместо 6•17'576=105'456 возможных позиций, их число увеличилось в десять раз и стало превышать миллион. Внезапно стало необходимым использование 60 бомб, что значительно превышало возможности поляков.

Всего через две недели, на стыке 1938/39 годов стало иметь место ещё одно осложнение дел, которое не только стало причиной количественных проблем поляков, но и качественных. Вместо использования от пяти до восьми соединений коммутаторной панели (а значит, меняя от 10 до 16 букв), с 1 января 1939 года, немцы стали использовать 7-10 соединений. Значит, из 26 букв Энигмы, только от шести до двенадцати букв оставались несоединенными. Учитывая, что панель используется дважды в преобразовании, это значительно ухудшило (в два раза) вероятность «улова» незатронутой панелью буквы, что значительно снизило эффективность бомб, и с начала 1939 года они едва вносили вклад в определение дневных ключей Энигмы. В конце концов, с отказом от удвоения ключа сообщения 1 мая 1940 года, идея «бомбы» стала окончательно бесполезной[10][16].

В это время, однако, «бомбы» больше не существовали: в сентябре 1939 после немецкого вторжения в Польшу криптоаналитики были вынуждены уничтожить машины и бежать из Варшавы[7].

26-27 июля 1939 года состоялась встреча польских, французских и британских криптоаналитиков в Пырах, в 20 км к югу от Варшавы[17]. На ней поляки поделились со своими коллегами своими методами атаки на шифр «Энигмы», двумя репликами устройства и чертежами циклометра и бомбы. На основе этих знаний Алан Тьюринг разработал новую машину для взлома Энигмы, названную bombe. В отличие от польской «бомбы», её принцип работы основывался не на уязвимостях в немецком протоколе передачи сообщений, а на уязвимостях самой «Энигмы». Bombe, в отличие от польских машин, имела бо́льшую вычислительную мощность и работала по более эффективному алгоритму, нежели полный перебор, а также могла расшифровывать сообщения, даже если были бы использованы все 13 соединений коммутационной панели[18].

• Онлайн-симулятор Энигмы
• I, David. Resurrecting Bomba Kryptologiczna: Archaeology of Algorithmic Artefacts (англ.). Link Published online: p.167-168 (9 июля 2009). Дата обращения: 11 декабря 2013.
• The US 6812 Div. Bombe Report (англ.) (1944). Дата обращения: 11 декабря 2013. Архивировано 23 мая 2006 года.

• Rejewski, Marian. Summary of Our Methods for Reconstructing ENIGMA and Reconstructing Daily Keys, and of German Efforts to Frustrate Those Methods:. — 1984c. Appendix C to Kozaczuk, 1984, pp=241-245
• Rejewski, Marian. The Mathematical Solution of the Enigma Cipher:. — 1984e. Appendix D to Kozaczuk, 1984, pp=272-291 (польск.)
• Kozaczuk, Władysław. Enigma: How the German Machine Cipher was Broken, and How it was Read by the Allies in World War Two. — Frederick, Maryland: University Publications of America, 1984. — ISBN 978-0-89093-547-7. (переведено Кристофером Каспарэком. Дополнена материалами из книги Marian Rejewski. «W kręgu enigmy». — Warsaw: Książka i Wiedza, 1979. (польск.)
• Rejewski, Marian. "Remarks on Appendix 1 to British Intelligence in the Second World War by Harry Hinsley". — 1980.