Криптологическая бомба () — аппарат, предложенный польским криптологом Марианом Реевским и разработанный в 1938 году совместно с двумя его коллегами-математиками Ежи Ружицким и Генриком Зыгальским для систематической расшифровки сообщений, зашифрованных немцами при помощи «Энигмы». Предпосылкой к созданию машины стала ненадёжная процедура удвоения ключа, использовавшаяся немцами, позволившая определить дневные настройки «Энигмы»
История
Начиная с 1930 года в Германии стало широко применяться шифрование с помощью «Энигмы». Её соседи, Франция, Великобритания и Польша, относились к этому с подозрением, особенно после прихода нацистов к власти, когда «Энигма» стала играть ключевую роль в перевооружении Вермахта. Несмотря на то что французские и британские криптоаналитики «Энигму» взломать не могли и классифицировали как невзламываемую, 27-летний польский математик Мариан Реевский уже в 1932 году взломал её, обнаружив серьёзную уязвимость в процедуре отправки сообщений.
Зная, что первые три буквы сообщения совпадают со вторыми тремя, Реевский определил внутреннюю проводку «Энигмы» и таким образом восстановил логическую структуру устройства. Его выводы, однако, носили лишь общий характер и опирались на коммерческий вариант «Энигмы», который немцы использовали для дипломатической связи; военные версии существенно отличались от него. Для взлома зашифрованного сообщения необходимо было проверить многие тысячи потенциальных ежедневных ключей, что при растущей сложности «Энигмы» и процедур генерации ключей становилось всё более трудной задачей.
Чтобы механизировать и ускорить процесс, Реевский, работавший в Шифровальном бюро Польского Генерального штаба в Варшаве, изобрел «bomba kryptologiczna» («криптологическую бомбу»), вероятно в октябре 1938 года. Каждая из «бомб», которых до сентября 1939 года для Бюро шифров в Варшаве было построено шесть, по существу представляла собой электрическую совокупность из шести «Энигм» и могла заменить около сотни человек персонала.
Метод бомбы, как и разработанный поляками ранее метод гриля, был основан на том, что соединения на коммутаторе (коммутационной панели) меняли не все буквы. Но если метод гриля требовал неизменённых пар букв, то для метода бомбы было достаточно неизменённых отдельных букв. Следовательно, его можно было применять даже несмотря на то, что количество используемых соединений на коммутационной панели в этот период составляло от пяти до восьми. К середине ноября 1938 года «бомбы» были готовы, и восстановление ежедневных ключей теперь занимало около двух часов.
До 25 июля 1939 года поляки взламывали сообщения, зашифрованные «Энигмами», более шести с половиной лет, не сообщая об этом французским и британским союзникам. 15 декабря 1938 года немцы добавили в конструкцию «Энигмы» два новых ротора — IV и V (одновременно могли использоваться три из пяти). Комментируя «Официальную историю британской разведки во Второй мировой войне» Гарри Хинсли, Реевский писал в 1979 году: «Мы быстро восстановили проводку внутри новых роторов, но их введение ... увеличило количество возможных последовательностей барабанов с 6 до 60 ... и, следовательно, увеличило работу по поиску ключей в десять раз. Таким образом, изменение было не качественным, а количественным. Нам пришлось бы заметно увеличить численность работающего с „бомбами“ персонала для производства перфорированных листов (теперь требовалось 60 серий по 26 листов в каждой, тогда как до встречи 25 июля 1939 года у нас было готово только две таких серии) и манипулирования ими».
Реевский отверг предположение Хинсли, что поляки решили поделиться своими методами и оборудованием с французами и британцами в июле 1939 года, потому что столкнулись с непреодолимыми техническими трудностями: «Нас побудили работать с британцами и французами не [криптологические] трудности, а ухудшающаяся политическая ситуация. Мы бы в любом случае поделились нашими достижениями с союзниками; если бы никаких трудностей вовсе не было - поделились бы тем более. Это был наш вклад в борьбу против Германии».
Процедура удвоения ключа Для расшифровки сообщений с помощью «Энигмы» требовалось знать несколько параметров: порядок роторов, их начальные позиции, положения колец роторов и соединения коммутационной панели. Позиции роторов представляли собой ключ из трёх букв (например, «PDN») и являлись частью дневного ключа. Для дополнительной безопасности, тем не менее, каждое индивидуальное сообщение было зашифровано с использованием дополнительной модификации ключа. Оператор случайно выбирал настройки ротора для каждого сообщения (например, «PDN»). Ключ этого сообщения набирался дважды («PDNPDN») и зашифровывался с использованием дневного ключа. Затем оператор сбрасывал машину на ключ сообщения, который использовался в дальнейшем. Поскольку внутренняя разводка проводов «Энигмы» изменялась с каждым нажатием клавиши, повторение не будет очевидным в шифртексте, так как одни и те же буквы открытого текста будут зашифрованы в различные буквы шифртекста (например, «PDNPDN» может стать «ZRSJVL»).
Вместо повторения ключа и затем его шифрования немцы могли просто шифровать ключ сообщения и отправлять его два раза подряд (например, «ZRSZRS») или в начале и в конце сообщения. При этом все равно будет достигнута желаемая избыточность для возможности детектирования ошибок. Однако это бы стало очевидным недостатком, поскольку подозрительное повторение будет привлекать внимание криптоаналитиков. Для предотвращения такой ситуации они стали применять, на первый взгляд, надёжный вариант с копированием ключа и его последующим шифрованием, поскольку повторение в шифртексте не было заметным. В действительности такой метод привёл к грубой криптографической ошибке.
Оператор устройства мог свободно выбирать ключ. Они, особенно в стрессовых ситуациях, выбирали очень простые ключи. Вместо желаемого случайного ключа часто выбирались простые сочетания букв вроде «AAA», «ABC» или «ASD» (рядом расположенные клавиши на клавиатуре устройства), которые взломщики могли просто отгадать. Кроме того, выбранный ключ шифровался самой «Энигмой», что раскрывало выбранную конфигурацию устройства. С другой стороны, если бы использовался независимый метод шифрования ключа сообщения, внутреннее устройство «Энигмы» определить бы не удалось. На самом деле, шифрования ключа вообще не требовалось. Он мог транслироваться в незашифрованном виде, повторённый дважды или даже трижды (в этом случае была бы возможность не только детектировать помехи, но и устранять их). Из-за неизвестного положения колец роторов положение самих роторов не несёт какой-либо важной информации для криптоаналитика. Вместо этого процедура удвоения ключа позволила польским криптоаналитикам дешифровать сообщения.
Циклометр как предшественник
До сентября 1938 года все ключи сообщения, переданные за один день, шифровались одним и тем же дневным ключом. В радиоэфире ежедневно были доступны десятки, если не сотни сообщений, все зашифрованные одинаковым ключом. Используя две процедурные ошибки, допущенные немцами, польские криптоаналитики сконструировали устройство, названное циклометром, состоящее из двух последовательно соединённых «Энигм», с позициями роторов, смещёнными на три друг относительно друга.
Циклометр позволил полякам определить для каждого из шести возможных порядков роторов характерные перестановки для каждой из 263 = начальной позиции роторов. Циклометр существенно упрощал утомительную и затратную по времени работу по поиску характеристик в каждом из 6 × = возможных случаев. Полученные характеристики записывались в каталог. Работа по разработке каталога характеристик, как заметил Реевский, «была утомительной и заняла больше года, но после её завершения дневные ключи могли быть определены за 15 минут»Marian Rejewski, "Summary of Our Methods for Reconstructing ENIGMA and Reconstructing Daily Keys, and of German Efforts to Frustrate Those Methods, " Appendix C to Władysław Kozaczuk, Enigma: How the German Machine Cipher Was Broken, and How It Was Read by the Allies in World War Two, 1984, pp. 241-45..
После замены рефлектора UKW-A на UKW-B 1 ноября 1937 года польским криптоаналитикам пришлось составлять новый каталог характеристик. Но перед тем, как они смогли завершить этот процесс, немцы изменили протокол передачи ключа сообщения. Вместо определённого положения роторов для зашифровки ключа сообщения теперь оператор мог выбрать его произвольно и передавал в незашифрованном виде в начале сообщения. Внезапно каталог характеристик стал бесполезным, и Бюро шифров стало работать над новыми методами атаки на шифр «Энигмы». Это привело к созданию листов Зыгальского и бомбы Реевского.
Происхождение названия Происхождение названия «бомба» остаётся загадкой. Даже после войны Мариан Реевски не мог этого вспомнить. По рассказам Тадеуша Лисицкого, Реевский, Рожицкий и Зыгальский ели пирожное «бомба», когда Рожицкий предложил название устройства. По другой версии, звук, издаваемый устройством во время его работы напоминал тиканье часового механизма бомбы, что стало причиной такого названия. Поскольку до наших дней не сохранилось ни одной машины, эту версию проверить невозможно. По утверждению самого Реевского, «из-за отсутствия лучшего варианта мы называли их бомбами».
В сверхсекретном отчете армии США от 15 июня 1945 года говорилось: Машина под названием «бомба» используется для ускорения решения. Первая машина была построена поляками и представляла собой ручную машину с множеством «Энигм». Когда возможное решение было найдено, деталь с громким шумом падала с машины на пол. Отсюда и название «бомба».
Приведенное выше описание польской «бомбы» армией США расплывчато и неточно, как видно из описания устройства в конце второго абзаца «Истории» раздел ниже: «Каждая „бомба“… по существу представляет собой совокупность шести „Энигм“…»
Устройство Идея «бомбы» основывается исключительно на ненадёжной процедуре удвоения ключа. Поляки не знали ни позиций роторов, ни позиций колец. Кроме того, начальная позиция роторов не была однозначной, а свободно выбиралась шифровальщиком. Несмотря на это, оставалось ясным, что сессионный ключ сначала удваивался, а затем шифровался. Отсюда польские криптоаналитики могли заключить, что первой и четвёртой, второй и пятой, а также третьей и шестой буквам шифртекста соответствовали одинаковые буквы открытого текста. Это важное замечание позволило провести поиск по шаблону «123123».
Техническое исполнение атаки на шифр «Энигмы» заключалось в создании электромеханической машины, включающей шесть наборов роторов «Энигмы». Поляки смогли не только быстро разработать концепт «бомбы», но и собрать и ввести их в работу при поддержке AVA (AVA Wytwórnia Radiotechniczna). Поскольку на тот момент существовало шесть различных порядков роторов «Энигмы», шесть бомб было построено, по одной на каждый порядок. Приводимая в движение электромотором, «бомба» проходила через все 17576 различных позиций роторов (от «AAA» до «ZZZ») примерно за 110 минут.
Атака заключалась в поиске позиций, в которых при вводе определённой тестовой буквы, выходная буква совпадала с выходной буквой для позиции, смещённой на три вперёд. Поскольку каждая «бомба» имела шесть наборов роторов, можно было проверять три сообщения одновременно. Искали позиции, в которых во всех трёх парах были одинаковые буквы.
Такое совпадение случалось довольно редко, и было сильным признаком успеха, то есть правильно определённых порядка роторов и положения колец. Но следовало ожидать и неудач — таких настроек, которые тоже дают попарные совпадения букв, но не являющихся ключом. В среднем на одну позицию роторов приходилась одна неудача. Польские криптоаналитики использовали специально спроектрированные реплики «Энигм» для определения неудач и поиска правильных соединений коммутационной панели. Они были настроены с использованием полученных с помощью «бомбы» возможного порядка роторов и положения колец.