Криптоаналіз «Енігми»

Криптоаналіз «Enigma» — криптоаналіз німецької шифрувальної машини «Enigma» під час Другої світової війни, здійснений силами польських та британських спецслужб. Розшифровка повідомлень внесла помітний внесок у поразку нацистської Німеччини.

Німецька трьох-роторна військова шифрувальна машина «Enigma».

Поява «Enigma»

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

У червні 1924 року британська криптографічна служба (Room 40) зацікавилася будовою машини. З цією метою була закуплена партія машин у німецької компанії Chiffrier-maschinen AG, яка виробляла «Enigma». Однією з умов угоди було реєстрація патенту в британському патентному бюро, завдяки чому криптографічна служба отримала доступ до опису криптографічної схеми.

Починаючи з 1925 року, коли німецькі військові почали масові закупівлі шифрувальної машини, і до кінця Другої світової війни було виготовлено близько 200 тисяч машин. З 1926 року на використання машини переходить німецький флот, з 1928 року — сухопутні війська. Вони застосовувалися також у службі безпеки та розвідки.

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

Перші перехоплення повідомлень, зашифрованих за допомогою «Enigma», відносяться до 1926 року. Однак прочитати їх довгий час не могли. У січні 1929 року коробка з комерційним варіантом «Enigma» випадково потрапила на варшавську митницю. Німеччина попросила повернути коробку, після чого її вмістом зацікавилися поляки.

За дорученням польського «Бюро шифрів» машина була вивчена фахівцями фірми «AVA», в тому числі її керівником, криптоаналітиком Антонієм Пальтхом, після чого коробку відправили в німецьке посольство. Вивчення машини не дозволило дешифрувати повідомлення, до того ж німецькі військові використовували свій, посилений варіант «Enigma».

У 1928-29 роках у Польщі були організовані перші математичні курси з криптографії. Слухачами були два десятки студентів-математиків зі знанням німецької мови. Троє з слухачів — Маріан Реєвський, Генріх Зигальський і Єжи Рожицький — пішли на службу в «Бюро шифрів». Згодом саме вони отримають перші результати щодо розкриття коду «Енігми». У 1931 році співробітник шифрбюро міністерства оборони Німеччини Ганс-Тіло Шмідт, який став уже агентом «Аше», почав передавати французькій розвідці коди, котрі вийшли з ужитку, які, згідно службових обов'язків, йому було потрібно знищувати, а також передав інструкцію з використання військового варіанту «Enigma». Серед причин, що спонукали Ганса-Тіло зробити це, були і матеріальна винагорода, і образа на рідну країну, яка не оцінила його успіхи під час Першої світової війни, а також заздрість армійській кар'єрі свого брата Рудольфа Шмідта.

Першими двома документами стали «Gebrauchsanweisung für die Chiffriermaschine Enigma» та «Schlüsselanleitung für die Chiffriermaschine Enigma». Французька та англійська розвідки, однак, не проявили інтересу до отриманих даних — можливо тому, що вважалося, що розкрити шифр «Enigma» неможливо. Полковник французької розвідки Гюстав Бертран передав матеріали польському «Бюро шифрів» і продовжував передавати їм подальшу інформацію від агента до осені 1939 року.

«Enigma»

Ротори «Enigma»

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

Завдяки отриманим документам, криптоаналітики знали, що для шифрування повідомлення оператор машини повинен був обрати з кодової книги так званий денний ключ, який складався з:

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

Однак оператор не повинен був використовувати денний ключ для шифрування повідомлень. Замість цього оператор придумував новий ключ з трьох букв (нім. Spruchschlüssel) і двічі шифрував його з використанням денного ключа. Після чого налаштування роторів змінювалися у відповідності з придуманим ключем і вироблялося шифрування повідомлення.

У грудні 1932 року Реєвський отримав кодові книги з денними ключами для вересня і жовтня 1932 року. Дані матеріали дозволили відновити внутрішню електропроводку роторів і побудувати військовий варіант «Enigma» (комерційний варіант вже був, але він мав іншу електропроводку роторів). Більше ні він, ні його колеги не мали доступу до кодовою книг, хоча агент «Аше» їх успішно постачав. Ймовірно, це було викликано тим, що начальство хотіло змусити криптоаналітиків зуміти знайти денної ключ без кодових книг, щоб підготуватися до того моменту, коли агент більше не зможе їх постачати.

Зусилля Маріана зосередилися на аналізі місця протоколу обміну повідомленнями, а саме — на повторенні ключа повідомлення. З щоденних повідомлень вибиралися перші шість літер і на їх основі складалася таблиця відповідності (приклади взяті з книги Сінгха):

Повідомлення 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

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

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

Документи Аше стали манною небесною — всі двері в той же момент відчинилися.

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

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. Все це значно ускладнило криптоаналіз «Enigma».

Влітку 1939 року, коли неминучість вторгнення в Польщу стала очевидна, бюро передало результати своєї роботи англійській і французькій розвідкам. Хоча польські математики так і не змогли розкрити шифр, серед результатів були і живі екземпляри машини, і електромеханічна «Bombe», що складалася з двох спарених «Enigma» та допомагала у розшифровці, а також використовувала унікальні методики криптоаналізу.

PC Bruno

Докладніше: Бюро шифрів

Британський етап

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

Фрагмент відновленої Bombe в Блетчлі-парку. Ротори.

Відновлювана Bombe в Блетчлі-парку, 2004 рік

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

Кадри

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

Метод

Перехоплення радіоповідомлень противника виконували десятки приймальних станцій, що мали кодову назву «Y-station». Щодня в Блетчлі-парк надходили тисячі таких повідомлень. Блетчлі-парк мав у своєму розпорядженні точну копію «Enigma», тому розшифровка повідомлень зводилася до підбору установки дисків, для більш пізніх моделей, — штекерного комутатора.

Складність завдання ускладнювалася тим, що встановлення роторів змінювалися щодня, тому служби дешифрування працювали цілодобово у три зміни.

Конструкція «Enigma» при правильному використанні забезпечувала практично повну секретність. На практиці, однак, з боку німецьких користувачів «Енігми» найчастіше допускалися недбалі дії, які давали підказки британським аналітикам (такі підказки на сленгу англійських студентів називалися cribs). Саме на використанні і систематизації таких похибок і був заснований метод дешифрування.

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

При відсутності необхідної кількості підказок, особливо напередодні великих операцій, проводилися спеціальні заходи по їх створенню. Цей підхід отримав кодову назву «садівництво» (англ. gardening). Наприклад, перед виходом чергового полярного конвою проводилося демонстративне мінування певної ділянки моря. Якщо супротивник доповідав результати розмінування із зазначенням заздалегідь відомих координат, це давало шукану підказку.

Тюрінг

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

Незабаром німці додали в конструкцію Enigma комутуючий пристрій, істотно розширивши цим кількість варіантів коду. Завдання, що виникло для англійців вирішив Гордон Уелчман, запропонувавши конструкцію «діагональної дошки». В результаті цієї роботи в серпні 1940 року була побудована криптоаналітична машина Bombe. З часом в Блетчлі-Парку було встановлено понад 200 машин, що дозволило довести темп розшифровки до двох-трьох тисяч повідомлень у день.

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

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

Час від часу Німеччина вносила в машину конструктивні зміни або яким-небудь способом посилювала криптографічний захист. У таких випадках криптоаналітики з Блетчлі-парку виявлялися безсилими, і для подальшої роботи терміново потрібно знайти опис змін або хоча б нові екземпляри інструкцій і машин «Enigma».

У 1940 році морський флот Німеччини вніс деякі зміни в машину. Лише після захоплення підводного човна U-110 разом з кількома новими екземплярами машини британські криптоаналітики змогли розібратися у змінах.

У 1942 році, після введення в дію чотири-роторної машини, Блетчлі-парк не зміг дешифрувати повідомлення протягом півроку, поки протичовновий корабель , ціною життя двох моряків, не захопив «Enigma» з підводного човна U-559.

Секретність

Докладніше: Операція «Ультра»

Це моя курочка-ряба, яка несе золоті яйця, але ніколи не кудкудакає.

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

Англійський уряд робив все можливе для того, щоб приховати успіхи в розшифровці німецьких шифрів як від противника, так і від керівництва СРСР. З цією метою всі дії, засновані на даних програми «Ультра» повинні були супроводжуватися операціями прикриття, які маскують справжнє джерело інформації.

Так, для передачі відомостей «Ультра» в СРСР використовувалася швейцарська організація Lucy, маючи за легендою джерело у верхах німецького керівництва. Інформацію, отриману від Lucy, передавав в СРСР резидент радянської розвідки в Швейцарії Шандор Радо.

Для маскування «Ультра» застосовувалися фіктивні розвідувальні польоти, імітувалися радіоперемовини і подібні заходи.

Про існування програми «Ультра» було відомо чітко обмеженому колу осіб, кількість яких становила близько десяти. Необхідні відомості передавалися за призначенням мережею підрозділів розвідки, прикомандированих до штабів командувачів армії і флоту. Джерело інформації при цьому не розкривалося, що іноді призводило до недооцінки британським командуванням цілком надійних відомостей «Ультра» і великих втрат (Див. Операція «Юнона»).

СРСР

У числі отриманої Великою Британією інформації були і відомості про підготовку вторгнення в СРСР. Незважаючи на ризик розкриття джерела, відомості були передані радянському уряду. Однак Сталін не повірив у можливість нападу.

Незважаючи на побоювання про можливість Німеччини слухати радянські радіопереговори, 24 липня 1941 року Вінстон Черчилль розпорядився все-таки ділитися з СРСР інформацією, одержуваної в результаті операції «Ультра», за умови повного виключення ризику компрометації джерела.

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

Деякі автори вказують, що з сучасної точки зору шифр «Enigma» був не дуже надійним. Однак у свій час його абсолютна надійність не викликала жодних сумнівів у німецьких фахівців: до самого кінця війни німецьке командування шукало причини витоків секретної інформації де завгодно, але не в розкритті «Enigma». Саме тому успіх британських дешифрувальників став особливо цінним внеском у справу перемоги над нацизмом.

Після війни

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

Дивись також

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

Примітки

1. Траплялися й помилки: серед запрошених у проект виявився біолог капітан-лейтенант Джеффрі Танді — фахівець по криптогамам
2. Макс Ньюман, Том Флауерс та інші фахівці потрапили до Блетчлі-парку пізніше у зв'язку з роботою над шифром «Танні»
3. Шифром «Енігми» користувалися не лише армія, авіація та флот, а й військова розвідка (Abwehr), залізниця та інші служби. Усі вони застосовували власні установки роторів
4. Суттєвим недоліком конструкції була неможливість кодування будь-якої літери тією самою літерою. Ця особливість «Енігми» була використана при дешифруванні
5. Тюрінг зауважив, що цифра «один» (нім. eins) зустрічається в 90 % повідомлень. На цій основі було побудовано особливий метод дешифрування — «eins-алгоритм». Як crib використовувалося навіть привітання Heil Hitler і грубі лайки, що особливо тішило численний жіночий персонал Блетчлі-парку
6. Польська машина називалася "бомба" (пол. Bomba kryptologiczna — Криптологічна бомба). Англійською бомба — «bomb». Її назва, за однією з версій, походить від назви десерту з морозива "Bombe glacée"(«One theory was that bomba was named after the ice cream, bombe glacee, which was being eaten when the machine was invented.» [ 18 квітня 2018 у Wayback Machine.] // Enigma: The Battle for the Code, By Hugh Sebag-Montefiore, 2002, ).
7. Виготовленням Bombe займалась компанія ^[en]»; проект машини зробив головний конструктор компанії ^[en].
8. Машини та допоміжний персонал розміщувалися поза територією Блетчлі-парку в навколишніх селищах
9. Версія відмови від захисту Ковентрі заради збереження секретності Ultra, не відповідає дійсності і заснована виключно на спогадах Ф. У. Уінтерботема, — офіцера Королівських ВПС, який не мав доступу до подібної інформації. Версія Уінтерботема неодноразово спростовувалась іншими мемуаристами та істориками.
10. СРСР мав деякі відомості про програму Ultra від свого агента в Блетчлі-парку — Джона Кернкросса, одного з членів Кембриджської п'ятірки. Англійці не підозрювали про роль Кернкросса до 1951 року
11. Ф. Уінтерботем пише, що надалі, з міркувань секретності, англійці не ділилися інформацією. Так, на думку Уінтерботема, про Курську операцію вермахту в СРСР дізналися з інших джерел. Потрібно враховувати, однак, що книга Уінтерботема вийшла до зняття грифу секретності з британських архівів про дешифрування коду «Лоренц» (1975), а сам він, будучи під час війни офіцером ВПС, доступу до секретних відомостей про «Енігму» не мав. Архівні матеріали однозначно свідчать про передачу до Москви детального плану операції «Цитадель» на початку 1943 через фіктивну агентурну мережу Lucy (Rutherford journal: «Colossus: Breaking the German ‘Tunny’ Code at Bletchley Park» [ 4 жовтня 2013 у Wayback Machine.])
12. Програма «Ультра» включала розшифровку не тільки коду «Енігми», а й набагато складнішого коду «Лоренц». Першим результатом дешифрування останнього став план літнього наступу Вермахту під Курськом (Операція Цитадель)
13. Colossus був призначений для розшифрування не «Енігми», а «Лоренца»

Джерела

1. Леонид Черняк Тайны проекта Ultra [ 26 червня 2019 у Wayback Machine.]
2. Д. А. Ларин, к. т. н., Г. П. Шанкин, д. т. н., профессор. Вторая мировая война в эфире: некоторые аспекты операции «Ультра» : [ 20 січня 2014] : ( )[рос.] // .
3. Gebrauchsanweisung für die Chiffriermaschine Enigma [ 17 травня 2011 у Wayback Machine.](нім.)
4. Schlüsselanleitung für die Chiffriermaschine Enigma [ 24 вересня 2015 у Wayback Machine.](нім.)
5. . Архів оригіналу за 9 травня 2019. Процитовано 5 квітня 2018.
6. Singh S. (1999). The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. New York City: Doubleday. с. 143—160. ISBN .
7. Richard A. Woytak. A Conversation with Marian Rejewski : ( )[англ.] // Cryptologia. — Taylor & Francis, 1982. — Vol. 6, no. 1. — P. 50—60.
8. Анин, 2000, с. 449—451, Прочие. Поляки. «Бруно» против «Энигмы».
9. Парамонов, Владимир (12 вересня 2006). . Компьюлента. Архів оригіналу за 1 листопада 2010. Процитовано 17 січня 2010.
10. . Архів оригіналу за 4 жовтня 2013. Процитовано 5 квітня 2018.
11. Lewin, 2001, с. 104.
12. Уинтерботем Ф. Операция «Ультра». — М.: Воениздат, 1978.
13. Анин, 2000, с. 359—366.

Література

• Lewin, Ronald (2001) [1978], Ultra Goes to War: The Secret Story, Classic Military History (вид. Classic Penguin), London, England: Hutchinson & Co, ISBN 

Посилання

• Rutherford journal: «Colossus: Breaking the German ‘Tunny’ Code at Bletchley Park» [ 4 жовтня 2013 у Wayback Machine.]