Криптоанализ «Энигмы» — криптоанализ немецкой шифровальной машины «Энигма» во время Второй мировой войны, осуществлённый силами польских и британских спецслужб. Расшифровка сообщений внесла заметный вклад в поражение нацистской Германии.
Впервые шифр «Энигмы» удалось дешифровать в польском «Бюро шифров» в декабре 1932 года. Четверо сотрудников разведки — Мариан Реевский, Ежи Ружицкий, Генрих Зыгальский и Иоганн Ревклид — с помощью данных французской разведки, математической теории и методов обратной разработки разработали специальное устройство для дешифровки закодированных сообщений, которое назвали криптологической бомбой.
Появление «Энигмы»
История электрической роторной шифровальной машины «Энигма» начинается в 1917 году с патента, полученного голландцем Хьюго Кочем. В следующем году патент был перекуплен Артуром Шербиусом, начавшим коммерческую деятельность с продажи экземпляров машины как частным лицам, так и немецкой армии и флотуЛеонид Черняк Тайны проекта Ultra . До середины 1920-х годов продажи шли плохо, в частности из-за высокой цены.
В июне 1924 года британская криптографическая служба (Room 40) заинтересовалась устройством машины. С этой целью была закуплена партия машин у германской компании Chiffrier-maschinen AG, производившей «Энигму». Одним из условий сделки была регистрация патента в британском патентном бюро, благодаря чему криптографическая служба получила доступ к описанию криптографической схемы.
Начиная с 1925 года, когда германские военные начали массовые закупки шифровальной машины, и до конца Второй мировой войны было произведено около 200 тысяч машин. С 1926 года на использование машины переходит германский флот, с 1928 года — сухопутные войска. Они применялись также в службе безопасности и разведке.
Польский этап
Первые перехваты сообщений, зашифрованных при помощи «Энигмы», относятся к 1926 году. Однако прочитать их долгое время не могли. В январе 1929 года коробка с коммерческим вариантом «Энигмы» случайно попала на варшавскую таможню. Германия попросила вернуть коробку, после чего её содержимым заинтересовались поляки. По поручению польского «Бюро шифров» машина была изучена специалистами фирмы «AVA», в том числе её руководителем криптоаналитиком Антонием Пальтхом, после чего коробку отправили в германское посольство. Изучение машины не позволило дешифровать сообщения, к тому же германские военные использовали свой, усиленный вариант «Энигмы».
В 1928—1929 годах в Польше были организованы первые математические курсы по криптографии. Слушателями были два десятка студентов-математиков со знанием немецкого языка. Трое из слушателей — Мариан Реевский, Генрих Зыгальский и Ежи Рожицкий — поступили на службу в «Бюро шифров». Впоследствии именно они получат первые результаты по вскрытию кода «Энигмы».
В 1931 году сотрудник шифрбюро министерства обороны Германии Ганс-Тило Шмидт, ставший уже агентом «Аше», начал передавать французской разведке вышедшие из употребления коды, которые, согласно служебным обязанностям, ему требовалось уничтожать, а также передал инструкцию по использованию военного варианта «Энигмы». Среди причин, побудивших Ганс-Тило сделать это, были и материальное вознаграждение, и обида на родную страну, не оценившую его успехи во время Первой мировой войны, и зависть к армейской карьере брата Рудольфа Шмидта. Первыми двумя документами стали «Gebrauchsanweisung für die Chiffriermaschine Enigma»Gebrauchsanweisung für die Chiffriermaschine Enigma. . и «Schlüsselanleitung für die Chiffriermaschine Enigma»Schlüsselanleitung für die Chiffriermaschine Enigma. .. Французская и английская разведки, однако, не проявили интереса к полученным данным — возможно, считалось, что вскрыть шифр «Энигмы» невозможно. Полковник французской разведки Гюстав Бертран передал материалы польскому «Бюро шифров» и продолжал передавать им дальнейшую информацию от агента до осени 1939 года.
Благодаря полученным документам, криптоаналитики знали, что для шифрования сообщения оператор машины должен был выбрать из кодовой книги так называемый дневной ключ, который состоял изEnigma Procedure .: настроек коммутационной панели (); порядка установки роторов (); положений колец (); начальных установок роторов (). Однако оператор не должен был использовать дневной ключ для шифрования сообщений. Вместо этого оператор придумывал новый ключ из трёх букв () и дважды шифровал его с использованием дневного ключа. После чего настройки роторов менялись в соответствии с придуманным ключом и производилось шифрование сообщения.
В декабре 1932 года Реевский получил кодовые книги с дневными ключами для сентября и октября 1932 года. Данные материалы позволили восстановить внутреннюю электропроводку роторов и построить военный вариант «Энигмы» (коммерческий вариант уже был, но он имел другую электропроводку роторов). Более ни он, ни его коллеги не имели доступа к кодовым книгам, хотя агент «Аше» их успешно поставлял. Вероятно, это было вызвано тем, что начальство хотело заставить криптоаналитиков суметь найти дневной ключ без кодовых книг, чтобы подготовиться к тому моменту, когда агент больше не сможет их поставлять.
Усилия Мариана сосредоточились на анализе уязвимости протокола обмена сообщениями, а именно — на повторении ключа сообщения. Из ежедневных сообщений выбирались первые шесть букв и на их основе составлялась таблица соответствия (примеры взяты из книги Сингха):
Сообщение 1 L O K R G M … Сообщение 2 M V T X Z E … Сообщение 3 J K T M P E … Сообщение 4 D V Y P Z X …
1-я буква A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 4-я буква P M R X
Если сообщений было достаточно, то таблица заполнялась полностью.
1-я буква A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 4-я буква F Q H P L W O G B M V R X U Y C Z I T N J E A S D K
Особенность полного варианта таблицы заключалась в том, что пока дневной ключ остаётся без изменений, содержимое таблицы также не меняется. И, с большой степенью вероятности, наоборот. Можно было бы составить каталог таблиц, однако их количество равнялось 26!, что делало завершение этой работы невозможным в обозримое время. Реевский стал пытаться выделить из таблиц некоторые шаблоны или найти некоторые структурные закономерности. И это ему удалось. Он стал рассматривать цепочки букв следующего вида:
1-я буква A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ↓ ↓ ↓ 4-я буква F Q H P L W O G B M V R X U Y C Z I T N J E A S D K
В примере полной таблицы выше таких цепочек оказалось 4: A → F → W → A B → Q → Z → K → V → E → L → R → I → B C → H → G → O → Y → D → P → C J → M → X → S → T → N → U → J Следующим открытием Мариана стало то, что хотя конкретные буквы зависели от дневной настройки «Энигмы» полностью, количество цепочек и букв в них задавалось только настройками роторов. Так как количество роторов было равно 3 (но они могли стоять в любом порядке), а начальная настройка состояла из трёх букв латинского алфавита, то число вариантов было равно . Это было значительно меньше, чем , что позволило, используя построенные (или украденные) машины «Энигма», составить каталог, содержащий все возможные цепочки. Данная работа заняла почти год, однако результатом стала возможность читать германскую переписку.
Как отмечает Сингх, именно возможность разделить задачу на две составляющих (настройки роторов и настройки коммутационной панели) позволили Реевскому справиться с данной задачей, а также помощь как математиков «Бюро шифров», так и Шмидта:
Документы Аше стали манной небесной — все двери в тот же момент открылись.
После того как настройки роторов для дневного сообщения были восстановлены, оставалось выяснить настройки коммутационной панели. С криптографической точки зрения это был простой моноалфавитный шифр, дополнительно ограниченный лишь 6 парами замен букв. Текст даже часто не требовалось подвергать частотному криптоанализу, а всего лишь присмотреться к строкам вроде «alliveinbelrin» ( с заменой R ↔ L) и другим, которые было легко восстановить «на глаз».
В 1934 году Германия начала менять конфигурацию положения роторов каждый месяц вместо каждого квартала. В ответ на это Мариан Реевский спроектировал устройство под названием «циклометр», позволяющий быстро воссоздать каталог циклов.
15 сентября 1938 года Германия изменила процедуру шифрования, сделав невозможным использование каталогов, составленных с использованием циклометра. Польские криптографы были вынуждены искать другие методы для расшифровки. Такими стали использование машин bombe и перфорированных листов Зыгальского.
15 декабря 1938 года Германия добавила 4-й и 5-й роторы, а 1 января 1939 года увеличила количество соединений коммутационной панели с 6 до 10. Всё это значительно затруднило криптоанализ «Энигмы».
Летом 1939 года, когда неизбежность вторжения в Польшу стала очевидна, бюро передало результаты своей работы английской и французской разведкам. Хотя польские математики так и не сумели вскрыть шифр, среди результатов были и «живые» экземпляры машины, и электромеханическая «Bomba», состоявшая из двух спаренных «Энигм» и помогавшая в расшифровке, а также уникальные методики криптоанализа.
PC Bruno
Британский этап
Дальнейшая работа по взлому «Энигмы» проходила в секретном центре британской разведки «Station X», известном впоследствии как Блетчли-парк.
Кадры Руководителем проекта был назначен ветеран военной разведки Алистер Деннистон. Работу по дешифровке возглавил коллега Деннистона по комнате № 40, известный лингвист и криптоаналитик Альфред Нокс (). За общую организацию работы отвечал профессор-математик Гордон Уэлшман. Деннистон начал набирать штат криптоаналитиков по принципу умственных способностей: лингвистов, математиков, шахматистов, чемпионов по решению кроссвордов, египтологов и даже палеонтологовСлучались и ошибки: среди приглашённых в проект оказался биолог капитан-лейтенант Джеффри Танди — специалист по криптогамам.. В частности, одним из первых был принят известный шахматный мастер Стюарт Милнер-Бэрри (). Среди математиков был и молодой профессор логики из Кембриджа — Алан ТьюрингМакс Ньюман, Том Флауэрс и другие специалисты попали в Блетчли-парк позднее в связи с работой над шифром «Танни»..
Метод
Перехват радиосообщений противника выполняли десятки приёмных станций, имевших кодовое название «Y-station». Ежедневно в Блетчли-парк поступали тысячи таких сообщений. Блетчли-парк имел в своем распоряжении точную копию «Энигмы», поэтому расшифровка сообщений сводилась к подбору установки дисков и, для более поздних моделей, — штекерного коммутатора. Сложность задачи усугублялась тем, что установки роторов менялись ежедневно, поэтому службы дешифровки работали круглосуточно в три сменыШифром «Энигмы» пользовались не только армия, авиация и флот, но и военная разведка (Abwehr), железная дорога и другие службы. Все они применяли собственные установки роторов..
Конструкция «Энигмы» при правильном использовании обеспечивала практически полную секретностьВажным недостатком конструкции была невозможность кодирования буквы той же самой буквой. Эта особенность «Энигмы» была широко использована при дешифровке.. На практике, однако, со стороны немецких пользователей «Энигмы» зачастую допускались небрежные действия, дававшие подсказки британским аналитикам (такие подсказки на сленге английских студентов назывались cribs). Именно на использовании и систематизации таких погрешностей и был основан метод дешифровки.
Подсказками служили любые часто повторяющиеся тексты, такие как приветствия, цифры (кодировались по произношению: «один», «два» и т. д.Тюринг подметил, что цифра «один» () встречается в 90 % сообщений. На этой основе был построен особый метод дешифровки — «eins-алгоритм». В качестве crib использовалось даже приветствие Heil Hitler и грубые ругательства, что особенно забавляло многочисленный женский персонал Блетчли-парка.). Все подсказки заносились в картотеку (Index) вместе с контекстом: почерком радиста, местом и временем передачи и т. п.