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

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

Основные статьи: Энигма, История криптографии

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

Различные историки по-разному оценивают влияние полученной информации на ход Второй мировой войны.

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

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

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

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

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

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

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

• 

  Генрик Зигальский

• 

  Ежи Рожицкий

• 

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

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

«Энигма»

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

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

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

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

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

В декабре 1932 года Реевский получил кодовые книги с дневными ключами для сентября и октября 1932 года. Данные материалы позволили восстановить внутреннюю электропроводку роторов и построить военный вариант «Энигмы» (коммерческий вариант уже был, но он имел другую электропроводку роторов).^[7] Более ни он, ни его коллеги не имели доступа к кодовым книгам, хотя агент «Аше» их успешно поставлял. Вероятно это было вызвано тем, что начальство хотело заставить криптоаналитиков суметь найти дневной ключ без кодовых книг, чтобы подготовиться к тому моменту, когда агент больше не сможет их поставлять.^[6]

Усилия Мариана сосредоточились на анализе уязвимости протокола обмена сообщениями, а именно — на повторении ключа сообщения. Из ежедневных сообщений выбирались первые шесть букв и на их основе составлялась таблица соответствия (примеры взяты из книги Сингха^[6]):

Сообщение 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!, что делает эту работу невозможной в обозримое время. Реевский стал пытаться выделить из таблиц некоторые шаблоны или найти некоторые структурные закономерности. И это ему удалось. Он стал рассматривать цепочки букв следующего вида^[6]:

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! * 26^3 = 105456$. Это было значительно меньше чем 26!, что позволило, используя построенные (или украденные) машины «Энигма» составить каталог, содержащий все возможные цепочки. Данная работа заняла почти год, однако результатом стала возможность читать германскую переписку.^[6]

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

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

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

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

— Мариан Реевский^[6]

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

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

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

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

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

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

Блетчли-парк

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

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

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

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

Дальнейшая работа по взлому была организована в Блетчли-парке, сегодня являющемся одним из предметов национальной гордости Великобритании. В разгар деятельности центр «Station X» насчитывал 12 тысяч человек, но, несмотря на это, немцы не узнали о нём до самого конца войны. Среди математиков, работавших в Блетчли-парке, стоит отметить Алана Тьюринга, Гордона Велчмана (англ. Gordon Welchman), Макса Ньюмана (англ. Max Newman) и Тону Фоулера.^[1]

Летом 1939 года немцы усложнили процедуру шифрования, добавив в набор ещё два ротора, увеличив количество возможных комбинаций установок роторов с $3!=6$ до $A_5^3 = \frac{{5!}}{{\left( {5 - 3} \right)!}} = 60$. После изучения польских материалов Алан Тьюринг пришёл к выводу, что использовать подход с полным перебором сообщений уже не получится. Во-первых, это потребует создания более 30 экземпляров «Бомбы», что во много раз превышало годовой бюджет «Station X». Во-вторых, Германия должна была в скором времени догадаться и исправить конструктивный недостаток, на котором основывался польский метод. Поэтому он разработал собственный метод, основанный на переборе последовательностей символов исходного текста. Однако, появившаяся в «Энигме» коммутационная доска, простейший с точки зрения схемотехники элемент, добавила проблем исследователям. С ней «боролся» Гордон Велчман, который изобрёл метод «диагональной доски». На основе своих методов, в августе 1940 года, с помощью компании «British Tabulating Machines» (англ.) и её конструктора Гарольда Кина (англ. Harold Keen) была построена первая британская криптоаналитическая машина, которая была названа Bombe, в знак уважения к польским криптографам. Впоследствии за время войны было выпущено 210 устройств^[1], позволивших расшифровывать до двух-трёх тысяч сообщений в день.^[9]

Хотя машина претерпевала некоторые изменения в деталях, её общий вид оставался прежним. Шкаф весом около тонны, передняя панель два на три метра и 36 наборов роторов на ней, по три в каждом. Использование машины требовало специальных навыков, и очень много зависело от обслуживающего персонала — девушек-добровольцев из Women’s Royal Naval Service (англ.). Впоследствии, когда часть работ была перенесена в США, вместе с технологиями была направлена и часть сотрудниц.^[1]

После окончания Второй мировой войны все машины были разобраны. Много позже группа из 60 энтузиастов в исследовательских целях воссоздала одну из машин, на что ушло около 10 лет.^[9]

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

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

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

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

Секретность — ультра

Сообщения, расшифрованные центром, имели гриф секретности «Ultra» — выше, чем использовавшийся до этого «Top Secret» (по одной из версий отсюда и название всей британской операции — «Операция Ультра»). Англичане предпринимали повышенные меры безопасности, чтобы Германия не догадалась о раскрытии шифра. Ярким эпизодом является случай с бомбардировкой Ковентри 14 ноября 1940 года, о которой премьер-министру Великобритании Уинстону Черчиллю было известно заранее благодаря расшифровке приказа. Однако Черчилль, опираясь на мнение аналитиков о возможности Германии догадаться об операции «Ультра», принял решение о непринятии мер к защите города и эвакуации жителей.^[2]

Война заставляет нас все чаще играть в Бога. Не знаю, как бы я поступил…

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

War is forcing us more and more to play God. I don't know what I should have done

— Президент США Франклин Рузвельт о бомбардировке Ковентри^[2][10][11]

СССР

Для СССР существование и даже результаты работы «Station X» секрета не представляли. Именно из результатов сообщений, дешифрованных в «Station X», СССР узнал о намечающемся «реванше» Гитлера за Сталинградскую битву и смог подготовиться к операции на Курском направлении, получившем названии «Курская дуга».^[1]

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

Перехваченное сообщение

Передано СССР

Следует ожидать нарастания давления вражеских войск на 2-ю армию. Желательно сдержать мощные силы противника на фронте армии с учётом операций Восточной армии в целом. В задачу армейской группы фон Вайхса входит удержание совместно со 2-й Венгерской армией Донецкого фронта между устьями р. Потудань и р. Воронеж и совместно со 2-й армией — Воронежского плацдарма и позиции по линии Ольховатка — Озерск — Борск — железнодорожная станция Котыш

Для информации Генерального штаба русских. По полученным из разных источников сведениям, сообщаем, что немцы, включая венгерские части, намерены удерживать русских на фронте Ливны — Воронеж — Свобода, в то время как танковые силы пойдут к юго-востоку между реками Дон и Донец

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

С современной точки зрения шифр «Энигмы» был не очень надёжным, но только сочетание этого фактора с наличием множества перехваченных сообщений, кодовых книг, донесений разведки, результатов усилий военных и даже террористических атак позволило «вскрыть» шифр.^[1]

Примечания

1. ↑ ^{1 2 3 4 5 6 7 8 9 10 11 12} Леонид Черняк Тайны проекта Ultra
2. ↑ ^{1 2 3 4 5 6 7 8} Д. А. Ларин, к. т. н., Г. П. Шанкин, д. т. н., профессор Вторая мировая война в эфире: некоторые аспекты операции «Ультра» (рус.) // Защита информации. Инсайд.
3. ↑ Gebrauchsanweisung für die Chiffriermaschine Enigma (нем.)
4. ↑ Schlüsselanleitung für die Chiffriermaschine Enigma (нем.)
5. ↑ Enigma Procedure
6. ↑ ^{1 2 3 4 5 6 7 8 9} Simon Singh Cracking the Enigma // The Code Book — The Secret History of Codes & Code-breaking (англ.). — London: Forth Estate, 2000. — P. 143—160. — ISBN 1-85702-889-9
7. ↑ ^{1 2 3} Richard A. Woytak A Conversation with Marian Rejewski (англ.) // Cryptologia. — Taylor & Francis, 1982. — В. 1. — Т. 6. — P. 50—60.
8. ↑ ISBN 5-227-00659-8
9. ↑ ^{1 2} Парамонов, Владимир Британские энтузиасты воссоздали дешифратор "Энигмы"  (рус.). Компьюлента (12 сентября 2006). Проверено 17 января 2010.
10. ↑ Kathleen Cushman The Broken Code: Churchill's Dilemma at Coventry (англ.) // Horace. — 1990, Sept.. — В. 7, #1..
11. ↑ James Hugh Toner Preface // The sword and the cross: reflections on command and conscience. — Greenwood Publishing Group, 1992. — 186 p. — ISBN 0-275-94212-0
12. ↑ Уинтерботем Ф. Операция «Ультра». — М.: Воениздат, 1978. В источнике также указывается, что в дальнейшем, из-за соображения секретности, англичане информаией не делились. И о Курской операции вермахта в СССР узнали из других источников.
13. ↑ ISBN 5-227-00659-8

Ссылки