Loading AI tools
Криптологическая бомба (пол. Bomba kryptologiczna) — аппарат, предложенный польским криптологом Марианом Реевским и разработанный в 1938 году совместно с двумя его коллегами-математиками Ежи Ружицким и Генриком Зыгальским для систематической расшифровки сообщений, зашифрованных немцами при помощи «Энигмы». Предпосылкой к созданию машины стала ненадёжная процедура удвоения ключа, использовавшаяся немцами, позволившая определить дневные настройки «Энигмы»[1]
Начиная с 1930 года в Германии стало широко применяться шифрование с помощью «Энигмы». Её соседи, Франция, Великобритания и Польша, относились к этому с подозрением, особенно после прихода нацистов к власти, когда «Энигма» стала играть ключевую роль в перевооружении Вермахта. Несмотря на то что французские и британские криптоаналитики «Энигму» взломать не могли и классифицировали как невзламываемую[2], 27-летний польский математик Мариан Реевский уже в 1932 году взломал её[3], обнаружив серьёзную уязвимость в процедуре отправки сообщений.
Зная, что первые три буквы сообщения совпадают со вторыми тремя, Реевский определил внутреннюю проводку «Энигмы» и таким образом восстановил логическую структуру устройства. Его выводы, однако, носили лишь общий характер и опирались на коммерческий вариант «Энигмы», который немцы использовали для дипломатической связи; военные версии существенно отличались от него. Для взлома зашифрованного сообщения необходимо было проверить многие тысячи потенциальных ежедневных ключей, что при растущей сложности «Энигмы» и процедур генерации ключей становилось всё более трудной задачей.
Чтобы механизировать и ускорить процесс, Реевский, работавший в Шифровальном бюро Польского Генерального штаба в Варшаве, изобрел «bomba kryptologiczna» («криптологическую бомбу»), вероятно в октябре 1938 года. Каждая из «бомб», которых до сентября 1939 года для Бюро шифров в Варшаве было построено шесть, по существу представляла собой электрическую совокупность из шести «Энигм» и могла заменить около сотни человек персонала.
Метод бомбы, как и разработанный поляками ранее метод гриля, был основан на том, что соединения на коммутаторе (коммутационной панели) меняли не все буквы. Но если метод гриля требовал неизменённых пар букв, то для метода бомбы было достаточно неизменённых отдельных букв. Следовательно, его можно было применять даже несмотря на то, что количество используемых соединений на коммутационной панели в этот период составляло от пяти до восьми. К середине ноября 1938 года «бомбы» были готовы, и восстановление ежедневных ключей теперь занимало около двух часов.
До 25 июля 1939 года поляки взламывали сообщения, зашифрованные «Энигмами», более шести с половиной лет, не сообщая об этом французским и британским союзникам. 15 декабря 1938 года немцы добавили в конструкцию «Энигмы» два новых ротора — IV и V (одновременно могли использоваться три из пяти). Комментируя «Официальную историю британской разведки во Второй мировой войне» Гарри Хинсли, Реевский писал в 1979 году: «Мы быстро восстановили проводку внутри новых роторов, но их введение ... увеличило количество возможных последовательностей барабанов с 6 до 60 ... и, следовательно, увеличило работу по поиску ключей в десять раз. Таким образом, изменение было не качественным, а количественным. Нам пришлось бы заметно увеличить численность работающего с „бомбами“ персонала для производства перфорированных листов (теперь требовалось 60 серий по 26 листов в каждой, тогда как до встречи 25 июля 1939 года у нас было готово только две таких серии) и манипулирования ими»[4].
Реевский отверг предположение Хинсли, что поляки решили поделиться своими методами и оборудованием с французами и британцами в июле 1939 года, потому что столкнулись с непреодолимыми техническими трудностями: «Нас побудили работать с британцами и французами не [криптологические] трудности, а ухудшающаяся политическая ситуация. Мы бы в любом случае поделились нашими достижениями с союзниками; если бы никаких трудностей вовсе не было - поделились бы тем более. Это был наш вклад в борьбу против Германии»[4].
Для расшифровки сообщений с помощью «Энигмы» требовалось знать несколько параметров: порядок роторов, их начальные позиции, положения колец роторов и соединения коммутационной панели. Позиции роторов представляли собой ключ из трёх букв (например, «PDN») и являлись частью дневного ключа. Для дополнительной безопасности, тем не менее, каждое индивидуальное сообщение было зашифровано с использованием дополнительной модификации ключа. Оператор случайно выбирал настройки ротора для каждого сообщения (например, «PDN»). Ключ этого сообщения набирался дважды («PDNPDN») и зашифровывался с использованием дневного ключа. Затем оператор сбрасывал машину на ключ сообщения, который использовался в дальнейшем[1]. Поскольку внутренняя разводка проводов «Энигмы» изменялась с каждым нажатием клавиши, повторение не будет очевидным в шифртексте, так как одни и те же буквы открытого текста будут зашифрованы в различные буквы шифртекста (например, «PDNPDN» может стать «ZRSJVL»).
Вместо повторения ключа и затем его шифрования немцы могли просто шифровать ключ сообщения и отправлять его два раза подряд (например, «ZRSZRS») или в начале и в конце сообщения. При этом все равно будет достигнута желаемая избыточность для возможности детектирования ошибок. Однако это бы стало очевидным недостатком, поскольку подозрительное повторение будет привлекать внимание криптоаналитиков. Для предотвращения такой ситуации они стали применять, на первый взгляд, надёжный вариант с копированием ключа и его последующим шифрованием, поскольку повторение в шифртексте не было заметным. В действительности такой метод привёл к грубой криптографической ошибке.
Оператор устройства мог свободно выбирать ключ. Они, особенно в стрессовых ситуациях, выбирали очень простые ключи. Вместо желаемого случайного ключа часто выбирались простые сочетания букв вроде «AAA», «ABC» или «ASD» (рядом расположенные клавиши на клавиатуре устройства), которые взломщики могли просто отгадать[5]. Кроме того, выбранный ключ шифровался самой «Энигмой», что раскрывало выбранную конфигурацию устройства. С другой стороны, если бы использовался независимый метод шифрования ключа сообщения, внутреннее устройство «Энигмы» определить бы не удалось. На самом деле, шифрования ключа вообще не требовалось. Он мог транслироваться в незашифрованном виде, повторённый дважды или даже трижды (в этом случае была бы возможность не только детектировать помехи, но и устранять их). Из-за неизвестного положения колец роторов положение самих роторов не несёт какой-либо важной информации для криптоаналитика. Вместо этого процедура удвоения ключа позволила польским криптоаналитикам дешифровать сообщения[6].
До сентября 1938 года все ключи сообщения, переданные за один день, шифровались одним и тем же дневным ключом. В радиоэфире ежедневно были доступны десятки, если не сотни сообщений, все зашифрованные одинаковым ключом. Используя две процедурные ошибки, допущенные немцами, польские криптоаналитики сконструировали устройство, названное циклометром, состоящее из двух последовательно соединённых «Энигм», с позициями роторов, смещёнными на три друг относительно друга.
Циклометр позволил полякам определить для каждого из шести возможных порядков роторов характерные перестановки для каждой из 263 = 17 576 начальной позиции роторов. Циклометр существенно упрощал утомительную и затратную по времени работу по поиску характеристик в каждом из 6 × 17 576 = 105 456 возможных случаев. Полученные характеристики записывались в каталог. Работа по разработке каталога характеристик, как заметил Реевский, «была утомительной и заняла больше года, но после её завершения дневные ключи могли быть определены за 15 минут»[7].
После замены рефлектора UKW-A на UKW-B 1 ноября 1937 года[8] польским криптоаналитикам пришлось составлять новый каталог характеристик. Но перед тем, как они смогли завершить этот процесс, немцы изменили протокол передачи ключа сообщения[6]. Вместо определённого положения роторов для зашифровки ключа сообщения теперь оператор мог выбрать его произвольно и передавал в незашифрованном виде в начале сообщения[9]. Внезапно каталог характеристик стал бесполезным, и Бюро шифров стало работать над новыми методами атаки на шифр «Энигмы». Это привело к созданию листов Зыгальского и бомбы Реевского.
Происхождение названия «бомба» остаётся загадкой. Даже после войны Мариан Реевски не мог этого вспомнить[10]. По рассказам Тадеуша Лисицкого, Реевский, Рожицкий и Зыгальский ели пирожное «бомба», когда Рожицкий предложил название устройства. По другой версии, звук, издаваемый устройством во время его работы напоминал тиканье часового механизма бомбы, что стало причиной такого названия. Поскольку до наших дней не сохранилось ни одной машины, эту версию проверить невозможно. По утверждению самого Реевского, «из-за отсутствия лучшего варианта мы называли их бомбами»[1].
В сверхсекретном отчете армии США от 15 июня 1945 года говорилось: Машина под названием «бомба» используется для ускорения решения. Первая машина была построена поляками и представляла собой ручную машину с множеством «Энигм». Когда возможное решение было найдено, деталь с громким шумом падала с машины на пол. Отсюда и название «бомба».
Приведенное выше описание польской «бомбы» армией США расплывчато и неточно, как видно из описания устройства в конце второго абзаца «Истории» раздел ниже: «Каждая „бомба“… по существу представляет собой совокупность шести „Энигм“…»
Идея «бомбы» основывается исключительно на ненадёжной процедуре удвоения ключа. Поляки не знали ни позиций роторов, ни позиций колец. Кроме того, начальная позиция роторов не была однозначной, а свободно выбиралась шифровальщиком. Несмотря на это, оставалось ясным, что сессионный ключ сначала удваивался, а затем шифровался. Отсюда польские криптоаналитики могли заключить, что первой и четвёртой, второй и пятой, а также третьей и шестой буквам шифртекста соответствовали одинаковые буквы открытого текста. Это важное замечание позволило провести поиск по шаблону «123123»[11].
1 — роторы (один установленный набор роторов и пять шпинделей для установки других наборов)
2 — электромотор
3 — три набора переключателей
Техническое исполнение атаки на шифр «Энигмы» заключалось в создании электромеханической машины, включающей шесть наборов роторов «Энигмы». Поляки смогли не только быстро разработать концепт «бомбы», но и собрать и ввести их в работу при поддержке AVA (AVA Wytwórnia Radiotechniczna). Поскольку на тот момент существовало шесть различных порядков роторов «Энигмы», шесть бомб было построено, по одной на каждый порядок. Приводимая в движение электромотором, «бомба» проходила через все 17576 различных позиций роторов (от «AAA» до «ZZZ») примерно за 110 минут[12].
Атака заключалась в поиске позиций, в которых при вводе определённой тестовой буквы, выходная буква совпадала с выходной буквой для позиции, смещённой на три вперёд. Поскольку каждая «бомба» имела шесть наборов роторов, можно было проверять три сообщения одновременно. Искали позиции, в которых во всех трёх парах были одинаковые буквы[1].
Такое совпадение случалось довольно редко, и было сильным признаком успеха, то есть правильно определённых порядка роторов и положения колец. Но следовало ожидать и неудач — таких настроек, которые тоже дают попарные совпадения букв, но не являющихся ключом[11]. В среднем на одну позицию роторов приходилась одна неудача. Польские криптоаналитики использовали специально спроектрированные реплики «Энигм» для определения неудач и поиска правильных соединений коммутационной панели. Они были настроены с использованием полученных с помощью «бомбы» возможного порядка роторов и положения колец[11].
Наконец, проводилась попытка дешифрования текста сообщения. Если прослеживался текст на немецком языке, то это означало, что были правильно определены порядок роторов, положения колец и как минимум часть штекеров панели. Оставалось окончательно определить оставшиеся соединения панели и, возможно, немного изменить настройку колец. После чего дневной ключ был полностью определён, и можно было дешифровать сообщения.
Конкретное применение «бомбы» может быть продемонстрировано на следующем примере. Предположим, что применялась процедура удвоения ключа, как это было в период с 15 сентября 1938 года. Пусть в качестве дневного ключа порядок роторов был «B123», положение колец роторов «abc», а штекеры коммутационной панели были «DE», «FG», «HI», «JK» и «LM». Оператор случайно выбирал начальную позицию — например, «BVH», и ключ сообщения — например, «WIK». Как объяснялось ранее, ключ сообщения удваивался и шифровался при выбранных дневном ключе и начальном положении роторов. В результате (что может быть проверено свободно доступными симуляторами «Энигмы») получается зашифрованный ключ сообщения, который отправляется вместе с незашифрованной начальной позицией, как индикатор шифртекста, в данном примере «BVH BPLBKM».
Криптоаналитикам сначала необходимо было перехватить как можно больше сообщений и рассмотреть индикаторы в каждом случае. Целью было найти три зашифрованных ключа сообщения, в которых первая и четвёртая, вторая и пятая и, наконец, третья и шестая буквы совпадали[1]. Пример выше удовлетворяет данному условия. Осталось найти ещё два индикатора, где вторая и пятая или третья и шестая буквы тоже «B».
В принципе, вместо поиска трёх одинаковых неподвижных точек (как называли парные буквы в удвоенном и зашифрованном ключе)[11] можно было использовать три различные точки. Это упростило бы поиск подходящих индикаторов, поскольку индикаторы с тремя различными парами встречаются чаще. Однако из-за наличия коммутаторной панели, пары преобразуются до и после прохода панели неизвестным полякам образом. Вставала необходимость удачно выбрать букву, не изменяющуюся в панели (self-plugged)[13], в противном случае дешифровка бы не удалась. При пяти-восьми проводах панели, как это было принято в 1938 году, вероятность удачного взлома составляет 50 %. С другой стороны, при использовании трёх различных пар, эта вероятность падает до 12,5 %[11]. По этой причине поляки выбрали более редкую, но более эффективную комбинацию из трёх одинаковых неподвижных точек.
Пусть после перехвата нескольких немецких сообщений были также найдены индикаторы «DCM WBVHBM» и «EJX NVBUUB». Таким образом имеется набор из трёх совпадающих неподвижных точек:
1) BVH BPLBKM 2) DCM WBVHBM 3) EJX NVBUUB
Для дальнейшего понимания следует ввести понятие разности (или расстояния) между двумя позициями роторов. Доподлинно неизвестно, как нумеровались позиции в Бюро шифров. Британцы в Блетчли-парк использовали следующее соглашение: каждой позиции соответствовало трёхзначное число в двадцатишестиричной системе счисления, где «Z» была нулём, «A» — единицей и так далее до «Y» — 25[14]. Тогда разностью между двумя позициями была разность соответствующих им чисел. В нашем примере разность между позициями «BVH» и «DCM» будет «AGE», а между «DCM» и «EJX» — «AGK».
Для взлома «Энигмы», криптоаналитики настраивали «бомбы» следующим образом. Каждая из шести машин соответствовала различным порядкам роторов, один из которых — нужный вариант «B123». Шесть наборов роторов на одной бомбе образовывали три пары. Расстояние между роторами в одной паре равнялось трём, а расстояние между парами соответствовало расстояниям между конфигурациями в перехваченных сообщениях[15]. Затем запускался мотор, и все 17576 позиций проходились меньше, чем за два часа.
Целью был поиск таких позиций, в которых все наборы роторов в «бомбе» дают одинаковую букву на соответствующей позиции. Такое совпадение проверялось с помощью простого реле[11]. Для примера выше с роторами «B123» и тестовой буквой «B» получаются только две позиции. Первая оказывается промахом, а вторая даёт три начальных позиции (все ещё нормированных на положение колец «aaa») «BUF», «DBK» and «EIV».
Простым поиском разности между найденными позициями и позициями в перехваченных индикаторах и её суммированием с «aaa» можно определить положение колец роторов[16]. В примере выше во всех трёх случаях получается «abc».
Полученные положения роторов, положения колец и начальные позиции роторов устанавливались в реплике «Энигмы», и попытки дешифровки сообщений давали следующие результаты:
1) BVH BPLBKM → WHHWSF 2) DCM WBVHBM → HPDIPZ 3) EJX NVBUUB → EHAEHA
Искомый шаблон «123123» уже виден в третьем случае, но пока результат необязательно правильный. Причиной этому является все ещё пустая коммутаторная панель. Последней задачей осталось определение этой настройки, использованной немцами (от пяти до восьми проводов). Чёткий алгоритм поиска отсутствовал, вместо этого применялся метод проб и ошибок с целью нахождения такой настройки, при которой во всех трёх случаях получалось сообщение вида «123123»[15]. Хорошим ходом действий будет соединение ещё не совпадающих букв в парах, например «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)[6]. Вместо 6•17’576=105’456 возможных позиций, их число увеличилось в десять раз и стало превышать миллион. Внезапно стало необходимым использование 60 бомб, что значительно превышало возможности поляков.
Всего через две недели, на стыке 1938/39 годов стало иметь место ещё одно осложнение дел, которое не только стало причиной количественных проблем поляков, но и качественных. Вместо использования от пяти до восьми соединений коммутаторной панели (а значит, меняя от 10 до 16 букв), с 1 января 1939 года, немцы стали использовать 7-10 соединений. Значит, из 26 букв «Энигмы», только от шести до двенадцати букв оставались несоединенными. Учитывая, что панель используется дважды в преобразовании, это значительно ухудшило (в два раза) вероятность «улова» незатронутой панелью буквы, что значительно снизило эффективность бомб, и с начала 1939 года они едва вносили вклад в определение дневных ключей «Энигмы». В конце концов, с отказом от удвоения ключа сообщения 1 мая 1940 года, идея «бомбы» стала окончательно бесполезной[11][17].
В это время, однако, «бомбы» больше не существовали: в сентябре 1939 после немецкого вторжения в Польшу криптоаналитики были вынуждены уничтожить машины и бежать из Варшавы[8].
26-27 июля 1939 года состоялась встреча польских, французских и британских криптоаналитиков в Пырах, в 20 км к югу от Варшавы[18]. На ней поляки поделились со своими коллегами своими методами атаки на шифр «Энигмы», двумя репликами устройства и чертежами циклометра и бомбы. На основе этих знаний Алан Тьюринг разработал новую машину для взлома «Энигмы», названную bombe. В отличие от польской «бомбы», её принцип работы основывался не на уязвимостях в немецком протоколе передачи сообщений, а на уязвимостях самой «Энигмы». Bombe, в отличие от польских машин, имела бо́льшую вычислительную мощность и работала по более эффективному алгоритму, нежели полный перебор, а также могла расшифровывать сообщения, даже если были бы использованы все 13 соединений коммутационной панели[19].
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
