Мариан Реевский
Изучая математику в университете в Познани, Реевский посещал секретный курс по криптографии, проводившийся польским Бюро шифров при Генштабе, в который он поступил на полный рабочий день в 1932 году. Бюро достигло небольших успехов в расшифровке Энигмы и в конце 1932 года Реевский был принят для работы над этой задачей. Спустя всего лишь несколько недель он разгадал секрет внутренней проводки Энигмы. Затем Реевский и двое его коллег-математиков разработали различные технические устройства для систематической расшифровки сообщений, зашифрованных при помощи Энигмы. Разработки Реевского, включенные в так называемую «картотеку»(card catalog), получены с использованием его устройств «cyclometer» и «Криптологическая бомба».
За пять недель до вторжения Германии в Польшу в 1939 году, Реевский и его коллеги представили результаты своих исследований по расшифровке Энигмы французской и британской разведке. Вскоре после начала войны польские криптографы были эвакуированы во Францию, где они продолжили свою работу в сотрудничестве с британскими и французскими коллегами. Они вновь были вынуждены эвакуироваться после падения Франции в июне 1940го, но спустя несколько месяцев вернулись к тайной работе в вишистской Франции. После того, как страна была полностью оккупирована Германией в ноябре 1942го, Реевский и математик Генрих Зигальский бежали через Испанию, Португалию и Гибралтар в Великобританию. Там они работали в подразделении Польской Армии, решая немецкие шифры низкого уровня. В 1946 году Реевский вернулся к своей семье в Польшу и работал бухгалтером, храня молчание о своей работе криптографом до 1967го года.
Обучение и первая работа
Мариан Реевский родился 16 августа 1905 года, в Бромберге, ныне Быдгощ.(2) Его родителями были Йозеф, продавец сигар, и Матильда, в девичестве Thoms. Он посещал уроки немецкого в K?nigliches Gymnasium zu Bromberg (Королевская школа грамматики в Бромберге) и закончил старшую школу, сдав матура(аналог аттестата зрелости в Польше) в 1923. Затем Реевский обучался математике в Университете в Познани, который он закончил 1 марта 1929.
В начале 1929го, незадолго до того, как он закончил университет, Реевский начал посещать секретные криптографические курсы для избранных немецкоговорящих студентов-математиков, проводившиеся Бюро шифров(Biuro Szyfr?w) при Польском Генеральном Штабе. Реевский и студенты Генрих Зигальский и Ежи Рожицкий были теми немногими, кто мог следовать учебному курсу, учитывая требования их исследований.
Реевский закончил университет имея степень магистра математики 1го марта 1929; темой его дипломной работы была «Теория двойных периодических функций второго и третьего рода и их применения.» Несколько недель спустя он начал двухгодичное обучение на актуария в Гёттингене, в Германии. Он не закончил обучение, потому как, будучи дома летом 1930го, он согласился принять должность ассистента для преподавания математики в Университете в Познани. В то же самое время он также поступил на неполный рабочий день в Бюро шифров, которое к тому времени закрыло курсы криптографии и создало форпост в Познани для расшифровки перехваченных немецких радио-сообщений. Реевский работал по 12 часов в неделю рядом с Институтом Математики в подземелье, которое прозвали «Черной комнатой».
Летом 1932 Познаньский филиал Бюро шифров был распущен. 1го сентября 1932, как гражданский служащий, Реевский присоединился к Бюро шифров в здании Генерального Штаба (Сакский дворец) в Варшаве, также как Зигальский и Ружицкий.
Их первым заданием была расшифровка четырёхсимвольного кода, использовавшегося Кригсмарине (Немецкий ВМФ). Прогресс в разгадке этой системы был слишком медленным, но значительно ускорился после тестового обмена закодированными сообщениями: в результате было получено шесть групп сигналов, за которыми следовал ответ из четырёх групп. Криптографы верно догадались, что первым сигналом был вопрос «Когда родился Фридрих Великий?», за которым следовал ответ «1712.»
Энигма
В октябре 1932, когда ещё шла работа над военно-морским кодом, Реевский был в одиночку секретно направлен на работу над расшифровкой новой немецкой шифровальной машины, Энигма I, которая получила широкое распространение у немецких войск. Хотя, согласно позднему докладу, Бюро шифров преуспело в разгадке ранней, лишенной коммутационной панели, Энигмы I(3), на самом деле им это не удалось.
Энигма была электромеханическим устройством, оборудованным 26-клавишной клавиатурой и набором из 26 ламп, соответствующих буквам латинского алфавита. Внутри был набор цилиндров со встроенной электропроводкой («роторы» и «рефлектор»), который запутывал ввод. Машина также отличалась наличием коммутационной панели для замены пар букв. Чтобы расшифровать букву, оператор нажимал соответствующую клавишу и записывал, которая из ламп загорелась. Каждое нажатие клавиши заставляло один или несколько роторов двигаться, таким образом расшифровка менялась от одного нажатия клавиши к следующему. Для того, чтобы два оператора могли общаться, в обеих Энигмах требовалось установить абсолютно одинаковое положение роторов. Большое число возможных положений роторов и коммутационной панели порождало астрономическое число различных вариаций, каждая из которых создавала свой индивидуальный шифр. Настройки менялись ежедневно, в результате чего машина снова и снова «ломалась» каждый день, если сообщения приходили непрерывно.
Для расшифровки сообщений Энигмы требовалось три пункта:
- Понимание того, как работает Энигма
- Схема проводки в роторах
- Соответствующие сегодняшнему дню настройки: порядок и положение роторов (которых изначально было три), а также схема соединений на коммутационной панели
Реевский владел только ответом на первый вопрос, базирующемся на информации, полученной Бюро шифров.
Разгадка проводки Энигмы
Сперва Реевский бился над разгадкой схемы проводки роторов. Для этого он использовал чистую математику в криптоанализе. Первоначальный метод широко использовал лингвистические схемы и статистику текстов на естественном языке — частоту появления тех или иных букв. Реевский даже применял технику из теории групп — теоремы о перестановкаx — в своих нападениях на Энигму. Эти математические методы в сочетании с материалами, поставляемыми французской разведкой, позволили ему реконструировать внутреннюю проводку роторов машины и неповорачивающегося рефлектора. «Разгадка», пишет историк Дэвид Кан, «было принадлежащим Реевскому ошеломляющим достижением, которое возвысило его до пантеона величайших криптографов всех времен». Реевский использовал математическую теорему, которую один профессор математики с тех пор называл «теоремой, выигравшей Вторую мировую».
Реевский исследовал первые 6 букв всех сообщений Энигмы, полученных за один день. Для безопасности, каждое сообщение, посылаемое Энигмой было зашифровано при различных начальных установках трех роторов, выбирающихся оператором. Это обозначалось «сообщение настроек» и было длиной в 3 символа. Для сообщения этих настроек принимающему оператору, отправляющий оператор начинал каждое сообщение, отправляя сообщение настроек в замаскированной форме — шестизнаковый «индикатор». Индикатор был сформирован при помощи Энигмы с роторами, установленным в положение, соответствующее текущим дневным настройкам, обозначенным «главными настройками», общими для всех операторов. К несчастью для Германии, устроенный таким образом индикатор являлся основным слабым местом в системе.
Например, предположим оператор выбрал для сообщения «сообщение настроек» KYG. Сначала оператор должен выставить роторы Энигмы в соответствии с «главными настройками», которые могут быть в этот день, например, GBL, а затем зашифровать сообщение настроек на Энигме «дважды»; то есть оператор должен ввести KYGKYG (в результате может получиться что-то вроде QZKBLX). Затем оператор должен переставить роторы в положение KYG и зашифровать само сообщение. Принимающий оператор должен применить обратный процесс для расшифровки сообщения настроек, а затем самого сообщения. Повторение сообщения настроек по-видимому предназначалось для проверки на наличие ошибок для выявления искажений, но оно имело непредвиденное последствие — значительное ослабление шифра. Благодаря повторению в индикаторе сообщения настроек, Реевский знал, что в индикаторе первая и четвёртая буква были закодированной одной и той же, вторая соответствовала пятой, а третья шестой. Эти соотношения можно было использовать для разгадки шифра.
Реевский изучал эти соотносящиеся пары букв. Например, если было четыре сообщения, которые имели следующие индикаторы за один день: BJGTDN, LIFBAB, ETULZR, TFREII, то посмотрев на первые и четвёртые буквы каждого индикатора, он знал, что соответствующие пары букв взаимосвязаны. B относится к T, L к B, E к L, а T к E: (B,T), (L,B), (E,L), и (T,E). Если у него было достаточно различных сообщений, с которыми можно было работать, он мог строить целые последовательности отношений: буква B связана с T, которая следует за E, затем L и снова B (на иллюстрации). Это был «четырёхэтапный цикл», так как происходило четыре шага, прежде чем он возвращался на начальную букву. Другой цикл в тот же день мог быть AFWA, или «тройной цикл». Если было достаточно сообщений за один день, все буквы алфавита могли охватываться различными циклами разных размеров. Циклы были совместимы всего один день, затем они менялись на другие наборы циклов. Такой же анализ мог быть проведен над 2ой и 5ой букваи, 3ей и 6ой, выявляя циклы в каждом случае и количество этапов в них.
Используя данные таким образом, в сочетании с оплошностью операторов Энигмы, которые стали выбирать для индикаторов предсказуемые комбинации (инициалы подружек или наборы ключей, которые они видели на клавиатуре Энигмы), Реевский смог вывести шесть перестановок, соответствующих шести настройкам Энигмы. Эти перестановки могут быть описаны шестью уравнениями с различными неизвестными, описывающими проводку в машине и установки на коммутационной панели.
Помощь из Франции
Тут Реевский начал испытывать затруднения: большое количество неизвестных требовало систему уравнений. Позднее в 1980 он скажет, что до сих пор не известно, можно ли решить такую систему из шести уравнений без дополнительных данных. Но у него была поддержка в виде документов, которые отдел французской разведки (Deuxi?me Bureau), под руководством будущего генерала Гюстава Бертранда, раздобыл и доставил в польское Бюро шифров. Документы были добыты шпионом(Hans-Thilo Schmidt) в немецкой службе шифров и включали в себя настройки Энигмы для сентября и октября 1932 года. 9го или 10го декабря,(4) 1932 года документы были отданы Реевскому, который использовал их для удаления влияния коммутационной панели на уравнения. С уменьшенным числом неизвестных решение уравнений перестало быть проблемой.
Однако, необходимо было преодолеть ещё одно препятствие. Военный вариант Энигмы был модифицированной версией коммерческой Энигмы, экземпляр которой был у Реевского. В коммерческой машине клавиши были соединены с цилиндрами в немецкой раскладке («QWERTZU…»). В военной же Энигме клавиши были установлены в алфавитном порядке: «ABCDEF…» Эта новая проводка была отклонена британскими взломщиками кодов, работавшими над Энигмой, как чересчур очевидная. Реевский, руководствуясь возможно интуитивными соображениями о любви немцев к порядку, просто догадался, что клавиши соединялись в алфавитном порядке. Позднее он вспоминал, что как только он сделал такую догадку, "из-под моего карандаша, как по мановению волшебной палочки, стали появляться номера, показывавшие соединения в роторе N. Эти соединения в роторе, который располагался справа, были окончательно известны.
Настройки, добытые французской разведкой охватывали два месяца — период изменений порядка роторов. Другой ротор оказывался в правой позиции на следующий месяц, таким образов проводку двух других цилиндров можно было выяснить аналогичным методом.(5) Это облегчало анализ и в конце года проводка всех трех роторов и рефлектора была изучена. Пример сообщения в пользовательском руководстве Энигмы представлял последовательность незашифрованного и зашифрованного текста, зашифрованного по данным настройкам; это помогло Реевскому устранить остававшиеся неясности с проводкой.
Существовала теория, что проводка роторов могла быть разгадана без документов, доставленных французской разведкой. Реевский заявил в 1980, что был найден и другой путь для решения этой проблемы, но метод он назвал «несовершенным и утомительным», к тому же он опирается на удачу. В 2005 математик Джон Лоуренс опубликовал расчеты, согласно которым для этого метода потребовалось бы 4 года, чтобы он имел разумные шасны на успех. Реевский писал, что «материалы разведки, предоставленные нам, следует рассматривать как решающие в разгадке машины.»
Разгадывая ежедневные настройки
После того, как Реевский определил схему проводки в остальных роторах, к нему в начале 1933 года присоединились Ружицкий и Зигальский для разработки методов и устройств, которые позволяли бы ежедневно взламывать шифры Энигмы.(6) Позднее Реевский вспоминает:
Первые методы
Целый ряд методов и устройств был изобретен для противодействия постоянным улучшениям оперативных процедур в Германии и самой машины Энигма. Самым первым методом для реконструкции ежедневных ключей был «гриль», базировавшийся на том факте, что на коммутационной панели менялись соединения только шести пар букв, оставляя четырнадцать букв неизменными. Следующим был метод Ружицкого «часы», который иногда делал возможным определить, который ротор был в позиции справа в данный день.
После 1 октября 1936 года немецкая процедура изменилась, увеличив число соединений на коммутационной панели. В результате метод «гриль» стал значительно менее эффективным. Однако, в 1934 или 1935 году был разработан метод, использовавший картотеку и не зависевший от количества соединений на панели Энигмы. Картотека была создана при помощи «циклометра» Реевского, специального устройства для создания каталога перестановок. Когда каталог был готов, за перестановками можно было следить по каталогу, получая установки роторов Энигмы на данный день.
Цуклометр содержал два набора роторов Энигмы и использовался для определения длины и количества циклов перестановок, которые могли быть произведены Энигмой. Даже с циклометром подготовка картотеки была долгой и трудной задачей. Каждый вариант настроек Энигмы (всего таких вариантов было 17,576) должен был быть изучен для каждой возможной последовательности роторов (было 6 возможных последовательностей); поэтому в каталоге в итоге было 105,456 записей. Подготовка каталога потребовала больше года, но когда он был готов в 1935 году, для получения ежедневных ключей требовалось 12—20 минут. Однако, 1го или 2го ноября 1937 года (согласно некоторым источникам 1го, согласно другим 2го; например ст290 и ст.264 Kozaczuk 1984) Германия заменила рефлекторы во всех Энигмах, это означало, что весь каталог должен был быть рассчитан заново. Тем не менее, в январе 1938 года немецкая секция Бюро шифров разгадывала 75 % сообщений Энигмы, а со слов Реевского, при незначительном увеличении числа сотрудников, это число легко можно было увеличить до 90 %.
Bomba и листы Зигальского
В 1937 году Реевский вместе с германским отделом Бюро Шифров был переведен на тайные объекты недалеко от Пыры в Кабатском лесу южнее Варшавы.
15 сентября 1938 года Германией были введены в действие новые правила расшифровки ключа сообщений (новая «процедура действия индикатора»), делавшие устаревшими криптографические техники, использовавшимися поляками.(7) Польские криптографы быстро отреагировали, разработав новую технику.
Примером такой техники была бомба Реевского, электрический прибор из шести Энигм, который позволял вычислять ежедневные ключи примерно за два часа. Шесть бомб были собраны и готовы к работе к середине Ноября 1938 года. «Бомба» использовала тот факт, что соединения на коммутационной панели не влияли на все символы; поэтому когда немцы сделали очередное изменение в процедуре кодирования 1го января 1939 года, увеличив число соединений на коммутационной панели, полезность «бомбы» резко упала. Британская bombe, основной инструмент, использовавшийся для взламывания кодов Энигмы в течение Второй мировой, был назван в честь польской «бомбы», несмотря на то, что криптографические методы, использовавшиеся двумя машинами, были абсолютно разными.
Примерно в то же время Генрик Зикальский изобрел ручной метод «листов Зигальского» (перфокарты), зависевший от числа соединений на коммутационной панели.
Однако, применение «бомбы» Реевского и «листов Зигальского» было усложнено в очередной раз, после внесения 15 декабря 1938 года очередных изменений в процесс шифрования. Немцы увеличили число роторов в Энигме на два в дополнение к первоначальным трем, что это повысило сложность расшифровки в десять раз.
В следующем месяце ситуация стала еще хуже, когда число соединений коммутационной панели увеличилось с шести до десяти. Вместо двенадцати символов, менявшихся местами ранее, теперь их стало двадцать, снизив эффективность «бомбы» и увеличив число возможных настроек коммутационной панели более чем в тысячу раз.
Информирование союзников
Когда стало ясно, что война неизбежна и польских ресурсов было недостаточно для того, чтобы поспевать за эволюцией Энигмы (например, было невозможно производить вовремя требовавшиеся 60 комплектов «листов Зигальского»), польский генштаб и правительство приняли решение посвятить западных союзников в свои разработки. Польские разработки были представлены британской и французской разведке на встрече в Пыры 26 июля 1939 года.
Польский подарок — расшифровка Энигмы, своим западным союзникам, за месяц до начала Второй мировой войны, пришелся очень вовремя. Осознание того, что шифр мог быть взломан, стало моральным импульсом для криптографов союзников. Британцы имели возможности для производства по крайней мере двух комплектов перфорированных листов (один был отправлен на Командный пункт Бруно, недалеко от Парижа, в середине декабря 1939) и начали перехватывать сообщения Энигмы уже через несколько месяцев после начала войны.
Без помощи Польши, британские взломщики кодов в лучшем случае значительно задержались бы, прежде чем начать расшифровки. Автор Хью Себаг-Монтефьоре пришел к выводу, что существенные взломы в шифре Энигмы случались, самое раннее, только после ноября 1941, после того, как Энигма и каталог ключей были захвачены. Для Энигмы, относящейся к морскому флоту Германии, называется вторая половина 1942 год. Бывший криптограф Bletchley Park Гордон Велчман пишет, что отдел Hut 6, занимавшийся Энигмой, «никогда бы не поняли, в чем секрет, если бы мы не научились у поляков, в последний момент, подробности немецких военных … Enigma машин, и использовавшихся процедур шифровки и дешифровки».
Разведка добывала данные в основном из расшифровок высокоуровневых немецких кодов (отдел разведки получил у британцев и американцев кодовое название «ULTRA»). Хотя точный вклад «Ультры» в победу союзников спорен, Козачук и Стразак отмечают, что «широко распространено мнение, что „ULTRA“ спасли мир, по крайней мере, от двух лет войны и возможной победы Гитлера». Английский историк Сэр Гарри Гинсли, работавший в Блетчли Парк, оценивает деятельность разведки так: «сократили войну, как минимум, на два года и, вероятно, на четыре». Существование «Ультры» было возможно, как минимум, благодаря огромной ранней работе польских взломщиков Энигмы.