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

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

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

Поява «Enigma»

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

У червні 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»[3] та «Schlüsselanleitung für die Chiffriermaschine Enigma»[4]. Французька та англійська розвідки, однак, не проявили інтересу до отриманих даних — можливо тому, що вважалося, що розкрити шифр «Enigma» неможливо. Полковник французької розвідки Гюстав Бертран передав матеріали польському «Бюро шифрів» і продовжував передавати їм подальшу інформацію від агента до осені 1939 року.

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

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

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

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

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

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

Повідомлення 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 (але вони могли стояти в будь-якому порядку), а початкова настройка складалася з трьох літер латинського алфавіту, то число варіантів дорівнювало . Це було значно менше ніж 26!, що дозволило, використовуючи побудовані (або викрадені) машини «Enigma» скласти каталог, що містить всі можливі ланцюжки. Дана робота зайняла майже рік, однак результатом стала можливість читати німецьке листування.

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

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

Оригінальний текст (англ.)
Asche's documents were welcomed like manna from heaven, and all doors were immediately open

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

«Циклометр» з паперів Маріана Реєвського

У 1934 році Німеччина почала змінювати конфігурацію положення роторів кожен місяць замість кожного кварталу. У відповідь на це Маріан Реєвський спроектував пристрій під назвою «циклометр», що дозволяє швидко відтворити каталог циклів[8].

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

15 грудня 1938 року Німеччина додала 4-й і 5-й ротори, а 1 січня 1939 року збільшила кількість з'єднань комутаційної панелі з 6 до 10. Все це значно ускладнило криптоаналіз «Enigma».

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

PC Bruno

Британський етап
Музей в Блетчлі-парку
Фрагмент відновленої Bombe в Блетчлі-парку. Ротори.
Відновлювана Bombe в Блетчлі-парку, 2004 рік

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

Кадри

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

Метод

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

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

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

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

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

Тюрінг

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

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

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

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

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

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

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

Секретність

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

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

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

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

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

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

СРСР

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

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

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

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

Після війни

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

Дивись також

Примітки
  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.» // Enigma: The Battle for the Code, By Hugh Sebag-Montefiore, 2002, BookSources/9780471437215 ISBN 978-0-471-43721-5).
  7. Изготовлением Bombe занималась компания «British Tabulating Machines»; проект машины сделал главный конструктор компании Шаблон:Не переведено 2Harold KeenШаблон:Не переведено 2.
  8. Машины и обслуживающий персонал размещались вне территории Блетчли-парка в окружающих поселках.
  9. Версия отказа от защиты Ковентри ради сохранения секретности Ultra, не соответствует действительности и основана исключительно на воспоминаниях Ф. У. Винтерботтама, — офицера RAF не имевшего доступа к подобной информации. Версия Винтерботтама неоднократно опровергалась другими мемуаристами и историками.
  10. СССР имел некоторые сведения о программе Ultra от своего агента в Блетчли-парке — Джона Кернкросса, одного из членов Кембриджской пятерки. Англичане не подозревали о роли Кернкросса до 1951 г.
  11. Ф. Уинтерботем пишет, что в дальнейшем, из соображений секретности, англичане информацией не делились. Так, по мнению Уинтерботема, о Курской операции вермахта в СССР узнали из других источников. Нужно учитывать, однако, что книга Уинтерботема вышла до снятия грифа секретности с британских архивов о дешифровке кода «Лоренц» (1975), а сам он, будучи во время войны офицером ВВС, доступа к секретным сведениям об «Энигме» не имел. Архивные же материалы однозначно свидетельствуют о передаче в Москву детального плана операции «Цитадель» в начале 1943 г. через фиктивную агентурную сеть Lucy (Rutherford journal: «Colossus: Breaking the German ‘Tunny’ Code at Bletchley Park»)
  12. Программа «Ультра» включала расшифровку не только кода Энигмы, но и гораздо более сложного кода «Лоренц». Первым результатом дешифровки последнего стал план летнего наступления вермахта под Курском (Операция Цитадель)
  13. Colossus был предназначен для расшифровки не «Энигмы», а «Лоренца»

Джерела
  1. Леонид Черняк Тайны проекта Ultra
  2. Д. А. Ларин, к. т. н., Г. П. Шанкин, д. т. н., профессор. .
  3. Gebrauchsanweisung für die Chiffriermaschine Enigma Архівовано 17 травня 2011 у Wayback Machine.(нім.)
  4. Schlüsselanleitung für die Chiffriermaschine Enigma Архівовано 24 вересня 2015 у Wayback Machine.(нім.)
  5. Enigma Procedure
  6. Singh S. (1999). The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. New York City: Doubleday. с. 143–160. ISBN 978-1-85702-879-9.
  7. Richard A. Woytak. . — Т. 6. — С. 50—60.
  8. Анин, 2000, с. 449—451, Прочие. Поляки. «Бруно» против «Энигмы».
  9. Парамонов, Владимир (12 вересня 2006). Британские энтузиасты воссоздали дешифратор "Энигмы". Компьюлента. Архів оригіналу за 1 листопада 2010. Процитовано 17 січня 2010.
  10. Rutherford journal: «Colossus: Breaking the German ‘Tunny’ Code at Bletchley Park»
  11. Lewin, 2001, с. 104.
  12. Уинтерботем Ф. Операция «Ультра». — М.: Воениздат, 1978.
  13. Анин, 2000, с. 359—366.

Література
  • Анін, Б. Ю.. Англійці. Таємниця. На службі у КДБ. // Радіоелектронний шпигунство. — М. : Центрполиграф, 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). London, England: Hutchinson & Co. ISBN 978-1-56649-231-7.

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.