Криптологічна бомба

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Криптологічна бомба (пол. Bomba kryptologiczna) — апарат, запропонований польським криптологом Маріаном Реєвським і розроблений в 1938 році разом з двома колегами-математиками Єжи Рожицьким і Генриком Зигальським для систематичної розшифровки повідомлень, зашифрованих німцями за допомогою Енігми. Передумовою до створення машини стала ненадійна процедура подвоєння ключа, яка використовувалась німцями, що дозволило визначити денні налаштування Енігми.

Історія[ред. | ред. код]

Після винаходу Енігми в 1917 році, починаючи з 1930 року цей інноваційний метод шифрування став регулярно застосовуватися в Німеччині. Її сусіди, особливо Франція, Велика Британія та Польща ставилися до нього з підозрою, особливо після приходу нацистів до влади, коли Енігма стала відігравати ключову роль у переозброєнні Вермахту. Незважаючи на те, що французькі та британські криптоаналітики її зламати не змогли і класифікували як незламну[1], 27-річний польський математик Маріан Реєвський вже в 1932 році зміг зламати Енігму[2], виявивши серйозну уразливість в процедурі надсилання повідомлень.

Процедура генерації ключа[ред. | ред. код]

Для розшифровки повідомлень з допомогою Енігми потрібно знати декілька параметрів: порядок роторів, їх початкові позиції, положення кілець роторів і з'єднання комутаційної панелі. Позиції роторів представляли собою ключ з трьох літер (наприклад, «PDN») і були частиною денного ключа. Для додаткової безпеки, тим не менш, кожне індивідуальне повідомлення було зашифровано з використанням додаткової модифікації ключа. Оператор випадково вибирав налаштування ротора для кожного повідомлення (наприклад, «PDN»). Ключ цього повідомлення набирався двічі («PDNPDN») і шифрувався з використанням денного ключа. Потім оператор скидав машину на ключ повідомлення, який використовувався в подальшому. Оскільки внутрішня розводка проводів Енігми змінювалася з кожним натисканням клавіші, повторення не буде очевидним в шифротексті, так як одні і ті ж букви відкритого тексту будуть зашифровані в різні літери шифртексту (наприклад, «PDNPDN» може стати «ZRSJVL»).

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

Також варто відзначити, що оператор пристрою міг вільно вибирати ключ. Вони, особливо в стресових ситуаціях, вибирали дуже прості ключі. Замість бажаного випадкового ключа, часто вибиралися прості поєднання букв кшталт «AAA», «ABC», або «ASD» (поруч розташовані клавіші на клавіатурі пристрою), які зломщики могли просто відгадати.[3] Шкоди завдавало і те, що вибраний ключ шифрувався самою Енігмою, що розкривало обрану конфігурацію пристрою. З іншого боку, якби використовувався незалежний метод шифрування ключа повідомлення, внутрішню будову Енігми визначити не вдалося. Насправді, шифрування ключа взагалі не було потрібно. Він міг транслюватися в незашифрованому вигляді, повторений двічі або навіть тричі (в цьому випадку була б можливість не тільки детектувати перешкоди, але й усувати їх). Через невідоме положення кілець роторів, становище самих роторів не несе якої-небудь важливої інформації для криптоаналітика. Замість цього, процедура подвоєння ключа дозволила польським криптоаналитикам дешифрувати повідомлення[4].

Циклометр як попередник[ред. | ред. код]

Файл:Циклометр Реевского 2.png
Циклометр

До вересня 1938 року всі ключі повідомлення, передані за один день, шифрувалися одним і тим же денним ключем. У радіоефірі щодня були доступні десятки, якщо не сотні повідомлень, всі зашифровані однаковим ключем. Використовуючи дві процедурні помилки, допущені німцями, польські криптоаналітики сконструювали пристрій, названий циклометром, що складається з двох послідовно з'єднаних Енігм, з позиціями роторів, зміщеними на три відносно один одного.

Циклометр дозволив полякам визначити для кожного з шести можливих порядків роторів характерні перестановки для кожної з 263 = 17 576 початковій позиції роторів. Циклометр суттєво спрощував тяжку і витратну за часом роботу з пошуку характеристик в кожному з 6 × 17 576 = 105 456 можливих випадків. Отримані характеристики записувалися в каталог. Робота по розробці каталогу характеристик, як зауважив Реєвський, «була втомливою і зайняла більше року, але після її завершення денні ключі могли бути визначені за 15 хвилин»[5].

Після заміни рефлектора UKW-A на UKW-B 1 листопада 1937 року[6] польським криптоаналітикам довелося складати новий каталог характеристик. Але перед тим, як вони змогли завершити цей процес, німці змінили протокол передачі ключа повідомлення. Замість певного положення роторів для зашифровування ключа повідомлення, тепер оператор міг вибрати довільно і передавав в незашифрованому вигляді на початку повідомлення[7]. Раптово каталог характеристик став марним, і Бюро шифрів стало працювати над новими методами атаки на шифр Енігми. Це призвело до створення аркушів Зигальского і бомби Реєвського.

Походження назви[ред. | ред. код]

Походження назви «бомба» залишається загадкою. Навіть після війни Маріан Реєвський не міг пригадати[7]. За розповідями Тадеуша Лисицького, Реєвський, Рожицький і Зигальський їли тістечко «бомба», коли Рожицький запропонував назву пристрою. За іншою версією, звук, видаваний пристроєм під час його роботи нагадував цокання годинникового механізму бомби, що стало причиною такої назви. Оскільки до наших днів не збереглося жодної машини, цю версію перевірити неможливо. За твердженням самого Реєвського, «через відсутность кращого варіанту ми називали їх бомбами»[8].

Будова[ред. | ред. код]

Ідея бомби ґрунтується виключно на ненадійній процедурі подвоєння ключа. Поляки не знали ні позицій роторів, ні позицій кілець. Крім того, початкова позиція роторів не була однозначною, а вибиралася довільно шифрувальником. Незважаючи на це, залишалося неясним, що сесійний ключ спочатку подвоювався, а потім шифрувався. Звідси польські криптоаналітики могли зробити висновок, що першій і четвертій, другій і п'ятій, а також третій і шостій буквам шифртексту відповідали однакові букви відкритого тексту. Це важливе зауваження дозволило провести пошук за шаблоном «123123».

Схематичне зображення бомби:
1 — ротори (один встановлений набір роторів і п'ять шпинделів для установки інших наборів)
2 — електродвигун
3 — три набори перемикачів

Технічне виконання атаки на шифр Енігми полягало у створенні електромеханічної машини, що включає шість наборів роторів Енігми. Поляки змогли не тільки швидко розробити концепт бомби, але й зібрати і ввести їх в роботу при підтримці AVA (AVA Wytwórnia Radiotechniczna). Оскільки на той момент існувало шість різних порядків роторів Енігми, шість бомб було побудовано, по одній на кожен порядок. Рух здійснювався від електричного мотора, бомба проходила через всі 17576 різних позицій роторів (від «AAA» до «ZZZ») приблизно за 110 хвилин[7].

Атака полягала в пошуку позицій, у яких при введенні певної тестової літери, вихідна буква збігалася з вихідною буквою для позиції, зміщеної на три вперед. Оскільки кожна бомба мала шість наборів роторів, можна було перевіряти три повідомлення одночасно. Шукали позиції в яких у всіх трьох парах були однакові літери.

Такий збіг траплялося досить рідко, і був ознакою успіху, тобто правильно визначених порядку роторів і положення кілець. Але варто було очікувати і невдач, таких налаштувань, які теж дають попарні збіги букв, але не є ключем. У середньому на одну позицію роторів припадала одна невдача. Польські криптоаналітики використовували спеціально зпроектовані репліки Енігми для визначення невдач і пошуку правильних з'єднань комутаційної панелі. Вони були налаштовані з використанням отриманих з допомогою бомби можливого порядку роторів і положення кілець.

Нарешті, проводилася спроба дешифрування тексту повідомлення. Якщо простежувався текст німецькою мовою, то це означало, що були правильно визначені порядок роторів, положення кілець і як мінімум частина штекерів панелі. Залишалося остаточно визначити з'єднання панелі, що залишилися і, можливо, трохи змінити налаштування кілець. Після чого денний ключ був повністю визначений, і можна було дешифрувати повідомлення.

Приклад[ред. | ред. код]

Конкретне застосування бомби може бути продемонстровано на наступному прикладі. Припустимо, що застосовувалася процедура подвоєння ключа, як це було в предіод з 15 вересня 1938 року. Нехай в якості денного ключа порядок роторів був «B123», положення кілець роторів «abc», а штекери комутаційної панелі були «DE», «FG», «HI», «JK» та «LM». Оператор випадково вибирав початкову позицію, наприклад «BVH», і ключ повідомлення, наприклад «WIK». Як пояснювалося раніше, ключ повідомлення подвоювався і шифрувався при вибраних денному ключі і початковому положенні роторів. В результаті (що може бути перевірено вільно доступними симуляторами Енігми) виходить зашифрований ключ повідомлення, який відправляється разом з незашифрованою початковою позицією, як індикатор шифротексту, в даному прикладі «BVH BPLBKM».

Криптоаналітикам спочатку необхідно було перехопити як можна більше повідомлень і розглянути індикатори в кожному випадку. Метою було знайти три зашифровані ключа повідомлення, в яких перша і четверта, друга та п'ята і, нарешті, третя та шоста букви збігалися. Приклад вище задовольняє дану умову. Залишилося знайти ще два індикатори, де друга і п'ята або третя і шоста букви теж «B».

В принципі, замість пошуку трьох однакових нерухомих точок (як називали парні букви в подвоєному і зашифрованому ключі)[9] можна було використовувати три різні точки. Це спростило б пошук відповідних індикаторів, оскільки індикатори з трьома різними парами зустрічаються частіше. Однак за наявності комутаторної панелі, пари перетворюються до і після проходу панелі невідомим полякам чином. Поставала необхідність вдало вибрати літеру, яка не змінюється в панелі (self-plugged[7], в іншому випадку дешифрування б не вдалася. При п'яти-восьми проводах панелі, як це було прийнято в 1938 році, ймовірність вдалого злому становить 50 %. З іншого боку, при використанні трьох різних пар, ця ймовірність падає до 12,5 %. З цієї причини поляки вибрали більш рідкісну, але більш ефективну комбінацію з трьох однакових нерухомих точок.

Нехай після перехоплення декількох німецьких повідомлень були також знайдені індикатори «DCM WBVHBM» і «EJX NVBUUB». Таким чином є набір з трьох співпадаючих нерухомих точок: 

1) BVH BPLBKM
2) DCM WBVHBM
3) EJX NVBUUB

Для подальшого розуміння слід ввести поняття різниці (або відстані між двома позиціями роторів. Достеменно невідомо, як нумерувалися позиції в Бюро шифрів. Британці в Блетчлі-парк використовували наступну домовленість: кожній позиції відповідало тризначне число двадцятишісткової системи числення, де «Z» була нулем, «A» — одиницею і так далі до «Y» — 25.[10] Тоді різницею між двома позиціями була різниця відповідних їм чисел. У нашому прикладі різниця між позиціями «BVH» і «DCM» буде «AGE», а між «DCM» і «EJX» — «AGK».

Для злому Енігми, криптоаналітики налаштовували бомби наступним чином. Кожна з шести машин відповідала різним порядкам роторів, один з яких — потрібний варіант «B123». Шість наборів роторів на одній бомбі утворювали три пари. Відстань між роторами в одній парі дорівнювала трьом, а відстань між парами відповідало відстаням між конфігураціями в перехоплених повідомлень.[11] Потім запускався двигун, і всі 17576 позицій проходились менше, ніж за дві години.

Метою був пошук таких позицій, в яких всі набори роторів у бомбі дають однакову літеру на відповідній позиції. Такий збіг перевірялося за допомогою простого реле. Для прикладу вище з роторами «B123» і тестовою літерою «B» виходять лише дві позиції. Перша виявляється промахом, а друга дає три початкових позиції (все ще нормованих на положення кілець «aaa») «BUF», «DBK» and «EIV».

Простим пошуком різниці між знайденими позиціями і позиціями в перехоплених індикаторах і її підсумовуванням з «aaa» можна визначити положення кілець роторів.[12] У прикладі вище у всіх трьох випадках виходить «abc».

Отримані положення роторів, положення кілець і початкові позиції роторів встановлювалися в репліці Енігми, і спроби дешифрування повідомлень давали наступні результати: 

1) BVH BPLBKM → WXWSF
2) DCM WBVHBM → HPDIPZ
3) EJX NVBUUB → EHAEHA

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

Хорошим ходом дій буде з'єднання ще не співпадаючих букв в парах, наприклад «H» та «I» в другому випадку. Це покращує можливий ключ повідомлення від «HPDIPZ» до «IPDIPZ». Тепер є дві пари, що збігаються  замість однієї. Це сильний ознака правильно визначеної сполуки. Іншою багатообіцяючою спробою є з'єднання відповідних літер шифортексту замість букв відкритого тексту. Як відомо, струм проходить через панель двічі, один раз у формі відкритого тексту, один раз після проходу роторів. Наприклад, у першому випадку, третя («H») і шоста («F») можливого ключа повідомлення «WHHWSF» не збігаються. З'єднання «FH» ситуацію не покращує. З іншого боку, з'єднання третій і шостій літери шифортексту («L» і «M») приводить до результату «WHYWSY». Знову, парі однакових букв шифротексту тепер відповідає пара однакових букв відкритого тексту, а значить, було правильно визначено ще одне з'єднання панелі.

Тепер при сполучених парах «HI» та «LM» розшифровка в першому випадку дає текст «WIJWSJ», а в другому — «IPDIPD» де вже простежується шаблон «123123». Правильно визначивши з'єднання «JK», яке може бути відгадане з отриманих букв, перше повідомлення при розшифровці також буде задовольняти потрібному шаблону, і ключ повідомлення «WIKWIK» буде остаточно зламаний. Два останніх з'єднання «DE» і «FG» можуть бути знайдені при спробі дешифрування повідомлення з початковою позицією роторів «WIK», після чого остаточно будуть знайдені денні налаштування Енігми, і розшифровка інших повідомлень не займе багато часу.

Кінець бомби[ред. | ред. код]

Шість бомб допомогли полякам продовжити розшифровувати повідомлення після введення вільного початкового стану роторів 15 вересня 1938 року. Однак 15 грудня 1938 року з'явилася нова проблема. Німці стали використовувати два нових ротора (IV і V). Отже, число різних позицій роторів збільшилася з шести (=3•2•1) до шістдесяти (=5•4•3). Замість 6 · 17,576 = 105,456 можливих позицій, їх число збільшилося в десять разів і стало перевищувати мільйон. Раптово стало необхідним використання 60 бомб, що значно перевищувало можливості поляків.

Всього через два тижні, на стику 1938/39 років стало мати місце ще одне ускладнення справ, яке не тільки стало причиною кількісних проблем поляків, але і якісних. Замість використання від п'яти до восьми сполук комутаторної панелі (а значить, міняючи від 10 до 16 літер), з 1 січня 1939 року, німці почали використовувати 7-10 сполук. Отже, з 26 букв Енігми, лише від шести до дванадцяти літер залишалися не з'єднаними. Враховуючи, що панель використовується двічі в перетворенні, це значно погіршило (у два рази) ймовірність «улову» незачепленою панеллю літери. Це значно знизило ефективність бомб, і з початку 1939 року вони ледь вносили вклад у визначення денних ключів Енігми. Зрештою, з відмовою від подвоєння ключа повідомлення 1 травня 1940 року, ідея «бомби» стала остаточно марною[7].

В цей час, однак, «бомби» більше не існувало, оскільки у вересні 1939 після німецького вторгнення в Польщу, криптоаналітики були змушені знищити машини і втекти з Варшави.

Turing Bombe як наступник[ред. | ред. код]

26-27 липня 1939 року відбулася зустріч польських, французьких і британських криптоаналітиків в Пирах, в 20 км на південь від Варшави[13]. На ній поляки поділилися зі своїми колегами своїми методами атаки на шифр Енігми, двома репліками пристрою і кресленнями циклометра і бомби. На основі цих знань Алан Тюрінг розробив нову машину для злому Енігми, названу bombe. На відміну від польської бомби, її принцип роботи не ґрунтувався на уразливісті в німецькому протоколі передачі повідомлень, а на вразливості самої Енігми. Bombe мала більшу обчислювальну потужність і працювала з більш ефективним алгоритмом, ніж повний перебір, а також могла розшифровувати повідомлення, навіть якщо були використані усі 13 з'єднань комутаційної панелі, на відміну від польських машин[7].

Примітки[ред. | ред. код]

  1. ↑ Singh, Simon (1999). The code book: the science of secrecy from Mary Queen of Scots to quantum cryptography. London: Fourth Estate. ISBN 978-1-85702-879-9.
  2. ↑ Marian Rejewski. . — № 16 (4).
  3. ↑ RICHARD A. WOYTAK. . — Т. 6. — ISSN 0161-1194. — DOI:10.1080/0161-118291856830.
  4. ↑ Welchman, Gordon. The Hut Six story : breaking the Enigma codes. — Cleobury Mortimer, Shropshire : M&M Baldwin, 1997. — xiv, 263 p. с. — ISBN 0947712348.
  5. ↑ Marian Rejewski, "Summary of Our Methods for Reconstructing ENIGMA and Reconstructing Daily Keys, and of German Efforts to Frustrate Those Methods, " Appendix C to Władysław Kozaczuk, Enigma: How the German Machine Cipher Was Broken, and How It Was Read by the Allies in World War Two, 1984, pp. 241-45.
  6. ↑ Kippenhahn, Rudolf, 1926-. Code breaking : a history and exploration. — Revised and updated ed. — New York : Overlook Duckworth, 2012. — 301 pages с. — ISBN 1468300741.
  7. ↑ а б в г д е Sebag-Montefiore, 2004.
  8. ↑ Marian Rejewski. How Polish Mathematicians Broke the Enigma Cipher // IEEE Annals of the History of Computing. — 1981. — Т. 3, вип. 3. — С. 213–234. — ISSN 1058-6180. — DOI:10.1109/mahc.1981.10033.
  9. ↑ Bauer, Friedrich Ludwig, 1924-. Decrypted secrets : methods and maxims of cryptology : [арх. 1 травня 2021]. — 3rd, rev. and updated ed. — Berlin : Springer, 2002. — С. 439-443. — 473 с. — ISBN 3540426744.
  10. ↑ Carter, Frank. July 1999. The First Breaking of Enigma. Some of the Pioneering Techniques Developed by the Polish Cipher Bureau. Bletchley Park Report No. 10. Milton Keynes: Bletchley Park Trust.
  11. ↑ David Link. Resurrecting Bomba Kryptologiczna: Archaeology of Algorithmic Artefacts, I : [англ.] // Cryptologia. — Vol. 33, no. 2. — С. 166–182. — DOI:10.1080/01611190802562809.
  12. ↑ Marian Rejewski, "How Polish mathematicians broke the Enigma cipher", Appendix D to Władysław Kozaczuk, Enigma: How the German Machine Cipher Was Broken, and How It Was Read by the Allies in World War Two, 1984, pp. 241-45.
  13. ↑ Ralph Erskine. . — Т. 30. — ISSN 0161-1194. — DOI:10.1080/01611190600920944.

Посилання[ред. | ред. код]

Література[ред. | ред. код]

Отримано з https://uk.wikipedia.org/w/index.php?title=Криптологічна_бомба&oldid=41442557