Криптоанализ «Энигмы»

Немецкая трёхроторная военная шифровальная машина «Энигма» (версия с метками).

Криптоанализ «Энигмы» — криптоанализ немецкой шифровальной машины «Энигма» во время Второй мировой войны, осуществлённый силами польских и британских спецслужб. Расшифровка сообщений внесла заметный вклад в поражение нацистской Германии.

Впервые шифр «Энигмы» удалось дешифровать в польском «Бюро шифров» в декабре 1932 года. Четверо сотрудников разведки — Мариан Реевский, Ежи Ружицкий, Генрих Зыгальский и Иоганн Ревклид — с помощью данных французской разведки, математической теории и методов обратной разработки разработали специальное устройство для дешифровки закодированных сообщений, которое назвали криптологической бомбой.

Появление «Энигмы»

Основная статья: Энигма

История электрической роторной шифровальной машины «Энигма» начинается в 1917 году с патента, полученного голландцем Хьюго Кочем. В следующем году патент был перекуплен Артуром Шербиусом, начавшим коммерческую деятельность с продажи экземпляров машины как частным лицам, так и немецкой армии и флоту. До середины 1920-х годов продажи шли плохо, в частности из-за высокой цены.

В июне 1924 года британская криптографическая служба (Room 40) заинтересовалась устройством машины. С этой целью была закуплена партия машин у германской компании Chiffrier-maschinen AG, производившей «Энигму». Одним из условий сделки была регистрация патента в британском патентном бюро, благодаря чему криптографическая служба получила доступ к описанию криптографической схемы.

Начиная с 1925 года, когда германские военные начали массовые закупки шифровальной машины, и до конца Второй мировой войны было произведено около 200 тысяч машин. С 1926 года на использование машины переходит германский флот, с 1928 года — сухопутные войска. Они применялись также в службе безопасности и разведке.

Польский этап

Основные статьи: Бюро шифров и Криптологическая бомба

Первые перехваты сообщений, зашифрованных при помощи «Энигмы», относятся к 1926 году. Однако прочитать их долгое время не могли. В январе 1929 года коробка с коммерческим вариантом «Энигмы» случайно попала на варшавскую таможню. Германия попросила вернуть коробку, после чего её содержимым заинтересовались поляки. По поручению польского «Бюро шифров» машина была изучена специалистами фирмы «AVA», в том числе её руководителем криптоаналитиком Антонием Пальтхом, после чего коробку отправили в германское посольство. Изучение машины не позволило дешифровать сообщения, к тому же германские военные использовали свой, усиленный вариант «Энигмы».

В 1928—1929 годах в Польше были организованы первые математические курсы по криптографии. Слушателями были два десятка студентов-математиков со знанием немецкого языка. Трое из слушателей — Мариан Реевский, Генрих Зыгальский и Ежи Рожицкий — поступили на службу в «Бюро шифров». Впоследствии именно они получат первые результаты по вскрытию кода «Энигмы».

• 
  Генрик Зигальский
• 
  Ежи Рожицкий
• 
  Мариан Реевский

В 1931 году сотрудник шифрбюро министерства обороны Германии Ганс-Тило Шмидт, ставший уже агентом «Аше», начал передавать французской разведке вышедшие из употребления коды, которые, согласно служебным обязанностям, ему требовалось уничтожать, а также передал инструкцию по использованию военного варианта «Энигмы». Среди причин, побудивших Ганс-Тило сделать это, были и материальное вознаграждение, и обида на родную страну, не оценившую его успехи во время Первой мировой войны, и зависть к армейской карьере брата Рудольфа Шмидта. Первыми двумя документами стали «Gebrauchsanweisung für die Chiffriermaschine Enigma» и «Schlüsselanleitung für die Chiffriermaschine Enigma». Французская и английская разведки, однако, не проявили интереса к полученным данным — возможно, считалось, что вскрыть шифр «Энигмы» невозможно. Полковник французской разведки Гюстав Бертран передал материалы польскому «Бюро шифров» и продолжал передавать им дальнейшую информацию от агента до осени 1939 года.

«Энигма»

Роторы «Энигмы»

Ротор «Энигмы» в разобранном виде:
1. кольцо с выемками
2. маркирующая точка для контакта «A»
3. алфавитное кольцо
4. залужённые контакты
5. электропроводка
6. штыревые контакты
7. пружинный рычаг для настройки кольца
8. втулка
9. пальцевое кольцо
10. храповое колесо

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

1. настроек коммутационной панели (нем. Steckerverbindungen);
2. порядка установки роторов (нем. Walzenlage);
3. положений колец (нем. Ringstellung);
4. начальных установок роторов (нем. Kenngruppen).

Однако оператор не должен был использовать дневной ключ для шифрования сообщений. Вместо этого оператор придумывал новый ключ из трёх букв (нем. Spruchschlüssel) и дважды шифровал его с использованием дневного ключа. После чего настройки роторов менялись в соответствии с придуманным ключом и производилось шифрование сообщения.

В декабре 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

A → F → W → A

↓

↓

↓

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:

1. A → F → W → A
2. B → Q → Z → K → V → E → L → R → I → B
3. C → H → G → O → Y → D → P → C
4. J → M → X → S → T → N → U → J

Следующим открытием Мариана стало то, что хотя конкретные буквы зависели от дневной настройки «Энигмы» полностью, количество цепочек и букв в них задавалось только настройками роторов. Так как количество роторов было равно 3 (но они могли стоять в любом порядке), а начальная настройка состояла из трёх букв латинского алфавита, то число вариантов было равно $3!\cdot 26^{3}=105\,456$. Это было значительно меньше, чем $26!\approx 4\cdot 10^{26}$, что позволило, используя построенные (или украденные) машины «Энигма», составить каталог, содержащий все возможные цепочки. Данная работа заняла почти год, однако результатом стала возможность читать германскую переписку.

Как отмечает Сингх, именно возможность разделить задачу на две составляющих (настройки роторов и настройки коммутационной панели) позволили Реевскому справиться с данной задачей, а также помощь как математиков «Бюро шифров», так и Шмидта:

Документы Аше стали манной небесной — все двери в тот же момент открылись.

Оригинальный текст (англ.)

Asche's documents were welcomed like manna from heaven, and all doors were immediately open.

— Мариан Реевский

После того как настройки роторов для дневного сообщения были восстановлены, оставалось выяснить настройки коммутационной панели. С криптографической точки зрения это был простой моноалфавитный шифр, дополнительно ограниченный лишь 6 парами замен букв. Текст даже часто не требовалось подвергать частотному криптоанализу, а всего лишь присмотреться к строкам вроде «alliveinbelrin» (англ. arrive in Berlin с заменой R ↔ L) и другим, которые было легко восстановить «на глаз».

«Циклометр» из бумаг Мариана Реевского

В 1934 году Германия начала менять конфигурацию положения роторов каждый месяц вместо каждого квартала. В ответ на это Мариан Реевский спроектировал устройство под названием «циклометр», позволяющий быстро воссоздать каталог циклов.

15 сентября 1938 года Германия изменила процедуру шифрования, сделав невозможным использование каталогов, составленных с использованием циклометра. Польские криптографы были вынуждены искать другие методы для расшифровки. Такими стали использование машин bombe и перфорированных листов Зыгальского.

15 декабря 1938 года Германия добавила 4-й и 5-й роторы, а 1 января 1939 года увеличила количество соединений коммутационной панели с 6 до 10. Всё это значительно затруднило криптоанализ «Энигмы».

Летом 1939 года, когда неизбежность вторжения в Польшу стала очевидна, бюро передало результаты своей работы английской и французской разведкам. Хотя польские математики так и не сумели вскрыть шифр, среди результатов были и «живые» экземпляры машины, и электромеханическая «Bomba», состоявшая из двух спаренных «Энигм» и помогавшая в расшифровке, а также уникальные методики криптоанализа.

PC Bruno

Основная статья: Бюро шифров § ПК Бруно

Британский этап

Основная статья: Блетчли-парк

Музей в Блетчли-парке

Фрагмент восстановленной Bombe в Блетчли-парке. Роторы.

Восстанавливаемая Bombe в Блетчли-парке, 2004 год

Дальнейшая работа по взлому «Энигмы» проходила в секретном центре британской разведки «Station X», известном впоследствии как Блетчли-парк.

Кадры

Руководителем проекта был назначен ветеран военной разведки Алистер Деннистон. Работу по дешифровке возглавил коллега Деннистона по комнате № 40, известный лингвист и криптоаналитик Альфред Нокс (англ. «Dilly» Knox). За общую организацию работы отвечал профессор-математик Гордон Уэлшман. Деннистон начал набирать штат криптоаналитиков по принципу умственных способностей: лингвистов, математиков, шахматистов, чемпионов по решению кроссвордов, египтологов и даже палеонтологов. В частности, одним из первых был принят известный шахматный мастер Стюарт Милнер-Бэрри (англ. Stuart Milner-Barry). Среди математиков был и молодой профессор логики из Кембриджа — Алан Тьюринг.

Метод

Основные статьи: Cribs и Gardening

Перехват радиосообщений противника выполняли десятки приёмных станций, имевших кодовое название «Y-station». Ежедневно в Блетчли-парк поступали тысячи таких сообщений. Блетчли-парк имел в своем распоряжении точную копию «Энигмы», поэтому расшифровка сообщений сводилась к подбору установки дисков и, для более поздних моделей, — штекерного коммутатора. Сложность задачи усугублялась тем, что установки роторов менялись ежедневно, поэтому службы дешифровки работали круглосуточно в три смены.

Конструкция «Энигмы» при правильном использовании обеспечивала практически полную секретность. На практике, однако, со стороны немецких пользователей «Энигмы» зачастую допускались небрежные действия, дававшие подсказки британским аналитикам (такие подсказки на сленге английских студентов назывались cribs). Именно на использовании и систематизации таких погрешностей и был основан метод дешифровки.

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

При отсутствии необходимого количества подсказок, особенно накануне крупных операций, проводились специальные мероприятия по их получению. Этот приём получил кодовое название «садоводство» (англ. gardening). Например, перед выходом очередного полярного конвоя проводилось демонстративное минирование определённого участка моря. Если противник докладывал результаты разминирования с указанием заранее известных координат, это давало искомую подсказку.

Тьюринг

Одним из основных теоретиков Блетчли-парка был Алан Тьюринг. После изучения польских материалов Тьюринг пришёл к выводу, что использовать прежний подход с полным перебором сообщений уже не получится. Во-первых, это потребует создания более 30 машин польского типа, что во много раз превышало годовой бюджет «Station X», во-вторых, можно было ожидать, что Германия может исправить конструктивный недостаток, на котором основывался польский метод. Поэтому он разработал собственный метод, основанный на переборе последовательностей символов исходного текста.

Вскоре немцы добавили в конструкцию Энигмы коммутирующее устройство, существенно расширив этим количество вариантов кода. Возникшую для англичан задачу решил Гордон Уэлшман, предложив конструкцию «диагональной доски». В результате этой работы в августе 1940 года была построена криптоаналитическая машина Bombe. Со временем в Блетчли-Парке было установлено более 200 машин, что позволило довести темп расшифровки до двух-трёх тысяч сообщений в день.

Хотя Bombe претерпевала некоторые изменения в деталях, её общий вид оставался прежним: шкаф массой около тонны, передняя панель два на три метра и 36 групп роторов на ней, по три в каждой. Использование машины требовало специальных навыков и сильно зависело от квалификации обслуживающего персонала — девушек-добровольцев из Женской вспомогательной службы ВМС. Впоследствии, когда часть работ была перенесена в США, вместе с технологиями была направлена и часть сотрудниц.

«Живая» информация

Время от времени Германия вносила в машину конструктивные изменения или каким-либо способом усиливала криптографическую защиту. В таких случаях криптоаналитики из Блетчли-парка оказывались бессильными, и для дальнейшей работы срочно требовалось найти описание изменений или хотя бы новые экземпляры инструкций и машин «Энигма».

В 1940 году морской флот Германии внёс некоторые изменения в машину. Лишь после захвата 9 мая 1941 года подводной лодки U-110 вместе с несколькими новыми экземплярами машины британские криптоаналитики смогли разобраться в изменениях.

В 1942 году, после ввода в строй четырёхроторной машины, Блетчли-парк не мог расшифровывать сообщения в течение полугода. Лишь 30 октября 1942 года противолодочный корабль Petard ценой жизни двух моряков захватил модернизированную «Энигму» с подводной лодки U-559.

4 июня 1944 года ВМС США захватили шифровальную машину «Энигма» с кодами на подводной лодке U-505.

Секретность

Основная статья: Операция «Ультра»

Это моя курочка-ряба, которая несёт золотые яйца, но никогда не кудахчет.

Уинстон Черчилль о Блетчли-парке

Английское правительство делало всё возможное для того, чтобы скрыть успехи в расшифровке немецких шифров как от противника, так и от руководства СССР. С этой целью все действия, основанные на данных программы «Ультра», должны были сопровождаться операциями прикрытия, маскирующими истинный источник информации. Так, для передачи сведений «Ультра» в СССР использовалась швейцарская организация Lucy, располагавшая, по легенде, источником в верхах немецкого руководства. Информацию, полученную от Lucy, передавал в СССР резидент советской разведки в Швейцарии Шандор Радо.

Для маскировки «Ультры» применялись фиктивные разведывательные полёты, радиоигра и т. п. мероприятия.

О существовании программы «Ультра» было известно строго ограниченному кругу лиц, число которых составляло порядка десяти человек. Необходимые сведения передавались по назначению сетью подразделений разведки, прикомандированных к штабам командующих армии и флота. Источник сведений при этом не раскрывался, что иногда приводило к недооценке британским командованием вполне надёжных сведений «Ультры» и крупным потерям (См. Гибель авианосца «Глориес»).

СССР

В числе полученной Великобританией информации были и сведения о подготовке вторжения в СССР. Несмотря на риск раскрытия источника, сведения были переданы советскому правительству. Однако Сталин требовал, чтобы информация приходила от трёх независимых источников.

Несмотря на опасения о возможности Германии слушать советские радиопереговоры, 24 июля 1941 года Черчилль распорядился всё-таки делиться с СССР информацией, получаемой в результате операции «Ультра», при условии полного исключения риска компрометации источника.

Оценки результатов

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

После войны

После окончания войны почти все дешифровальные машины были уничтожены. В начале XXI века группа британских энтузиастов воссоздала машину Colossus, на что ушло около 10 лет.

См. также

• История криптографии
• «Игра в имитацию» (фильм, 2014 год)

Литература

• Анин, Б. Ю.. Англичане. Тайна. На службе у КГБ // Радиоэлектронный шпионаж. — М. : Центрполиграф, 2000. — 491, [2] с., [8] л. ил., портр. — (Секретная папка). — 10 000 экз. — ISBN 5-227-00659-8.
• Lewin, Ronald (2001) [1978], Ultra Goes to War: The Secret Story, Classic Military History (Classic Penguin ed.), London, England: Hutchinson & Co, ISBN 978-1-56649-231-7.

Ссылки

• Rutherford journal: «Colossus: Breaking the German ‘Tunny’ Code at Bletchley Park»