Kryptoanalýza "Enigma"

Kryptoanalýza "Enigma"  - kryptoanalýza německého šifrovacího stroje " Enigma " během 2. světové války , prováděná silami polských a britských zpravodajských služeb. Rozluštění zpráv významně přispělo k porážce nacistického Německa .

Poprvé byla šifra Enigma rozluštěna v polském „ Cipher Bureau “ v prosinci 1932 . Čtyři zpravodajští důstojníci, Marian Rejewski, Jerzy Różycki, Henryk Zygalski a Johann Reuclid, dokázali s pomocí francouzských zpravodajských dat, matematické teorie a metod reverzního inženýrství vyvinout speciální zařízení pro dešifrování kódovaných zpráv, které se nazývalo kryptologická bomba .

Příchod Enigmy

Historie elektrického rotačního šifrovacího stroje „Enigma“ začíná v roce 1917 patentem , který obdržel Holanďan Hugo Koch . V následujícím roce patent koupil Arthur Scherbius , který zahájil komerční činnost prodejem kopií stroje jak soukromým osobám, tak německé armádě a námořnictvu [1] . Až do poloviny 20. let byly prodeje slabé, částečně kvůli vysoké ceně [2] .

V červnu 1924 se o konstrukci stroje začala zajímat britská kryptografická služba ( místnost 40 ). Za tímto účelem byla zakoupena várka strojů od německé firmy Chiffrier-maschinen AG, která Enigmu vyráběla. Jednou z podmínek obchodu byla registrace patentu u Britského patentového úřadu, díky kterému získala kryptografická služba přístup k popisu kryptografického schématu [2] .

Počínaje rokem 1925 , kdy německá armáda zahájila masové nákupy šifrovacího stroje, a do konce 2. světové války bylo vyrobeno asi 200 tisíc strojů [2] . Od roku 1926 stroj používá německá flotila a od roku 1928  pozemní síly. Používaly se i v bezpečnostní službě a rozvědce [2] .

Polská scéna

První zachycení zpráv zašifrovaných pomocí Enigmy se datuje do roku 1926. Dlouho je však nemohli číst. V lednu 1929 se do varšavské celnice omylem dostala krabice s komerční verzí Enigmy. Německo požádalo o vrácení krabice, načež se o její obsah začali zajímat Poláci. Jménem Polish Cipher Bureau stroj zkoumali specialisté AVA, včetně jeho šéfa, kryptoanalytika Anthonyho Paltha, a poté byla krabice odeslána na německé velvyslanectví. Studie stroje neumožňovala rozluštění zpráv, navíc německá armáda používala vlastní, vylepšenou verzi Enigmy [2] .

V letech 1928-1929 byly v Polsku organizovány první matematické kurzy v kryptografii. Publikem byly dvě desítky studentů matematiky se znalostí německého jazyka. Tři ze studentů - Marian Rejewski , Henryk Zygalski a Jerzy Rozhitsky  - vstoupili do služby v Sipher Bureau . Následně to jsou oni, kdo obdrží první výsledky o otevření kódu Enigmy [2] .

V roce 1931 začal zaměstnanec šifrovacího úřadu německého ministerstva obrany Hans-Thilo Schmidt , který se již stal agentem Ashe, předávat francouzské rozvědce zastaralé kódy, které podle oficiálních povinností potřeboval zničit, a také přenesl návod k použití vojenské verze Enigmy. Mezi důvody, které k tomu Hanse-Thila přiměly, byly materiální odměny a nelibost vůči rodné zemi, která nedocenila jeho úspěchy za první světové války , a závist na armádní kariéru jeho bratra Rudolfa Schmidta [1] . První dva dokumenty byly „Gebrauchsanweisung für die Chiffriermaschine Enigma“ [3] a „Schlüsselanleitung für die Chiffriermaschine Enigma“ [4] . Francouzská a britská rozvědka však o obdržená data neprojevila žádný zájem - možná se věřilo, že není možné otevřít šifru Enigma. Plukovník francouzské rozvědky Gustave Bertrand předal materiály polskému „ Cipher Bureau “ a pokračoval v předávání dalších informací od agenta až do podzimu 1939 [1] .

Díky obdrženým dokumentům kryptoanalytici věděli, že k zašifrování zprávy musí obsluha stroje vybrat z číselníku tzv. denní klíč , který se skládal z [5] :

  1. nastavení propojovacího panelu ( německy  Steckerverbindungen );
  2. pořadí montáže rotorů ( německy:  Walzenlage );
  3. pozice prstenů ( německy:  Ringstellung );
  4. počáteční nastavení rotorů ( německy:  Kenngruppen ).

Operátor však neměl používat denní klíč k šifrování zpráv. Místo toho operátor přišel s novým třípísmenným klíčem ( německy  Spruchschlüssel ) a zašifroval jej dvakrát pomocí denního klíče. Poté se nastavení rotorů změnilo v souladu s vynalezeným klíčem a zpráva byla zašifrována [6] .

V prosinci 1932 obdržel Rejewski kódové knihy s denními klíči pro září a říjen 1932. Tyto materiály umožnily obnovit vnitřní elektrické rozvody rotorů a postavit vojenskou verzi Enigmy (existovala již komerční verze, ale ta měla jiné elektrické rozvody rotorů) [7] . Ani on, ani jeho kolegové neměli přístup ke knihám kódů, přestože je agent "Ashe" úspěšně dodal. Pravděpodobně to bylo způsobeno tím, že úřady chtěly donutit kryptoanalytiky, aby dokázali najít denní klíč bez kódových knih, aby se připravili na okamžik, kdy je agent již nebude moci dodat [6] .

Marianovo úsilí se zaměřilo na analýzu zranitelnosti protokolu pro zasílání zpráv, konkrétně na opakování klíče zprávy. Z denních zpráv bylo vybráno prvních šest dopisů a na jejich základě byla sestavena korespondenční tabulka (příklady jsou převzaty ze Singhovy knihy [6] ):

Zpráva 1 L Ó K R G M …
Zpráva 2 M PROTI T X Z E …
Zpráva 3 J K T M P E …
Zpráva 4 D PROTI Y P Z X …
1. písmeno A B C D E F G H já J K L M N Ó P Q R S T U PROTI W X Y Z
4. písmeno P M R X

Pokud byl dostatek zpráv, pak byla tabulka zcela zaplněna.

1. písmeno A B C D E F G H já J K L M N Ó P Q R S T U PROTI W X Y Z
4. písmeno F Q H P L W Ó G B M PROTI R X U Y C Z já T N J E A S D K

Zvláštností plné verze tabulky bylo, že zatímco denní klíč zůstává nezměněn, obsah tabulky se také nemění. A s vysokou pravděpodobností i naopak. Bylo by možné sestavit katalog tabulek ... ale jejich počet je 26!, což tuto práci v dohledné době znemožňuje. Reevsky se začal pokoušet izolovat některé vzory z tabulek nebo najít nějaké strukturální vzory. A uspěl. Začal uvažovat o řetězcích písmen následujícího tvaru [6] :

1. písmeno A B C D E F G H já J K L M N Ó P Q R S T U PROTI W X Y Z
A→F→W→A ↓ ↓ ↓
4. písmeno F Q H P L W Ó G B M PROTI R X U Y C Z já T N J E A S D K

V příkladu úplné tabulky jsou výše 4 takové řetězce:

  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

Dalším Marianovým objevem bylo, že ačkoli konkrétní písmena zcela závisela na denním nastavení Enigmy, počet řetězů a písmen v nich byl nastaven pouze nastavením rotorů. Protože počet rotorů byl 3 (ale mohly být v libovolném pořadí) a počáteční nastavení sestávalo ze tří písmen latinské abecedy, počet možností byl . To bylo výrazně méně než , což umožnilo s využitím postavených (nebo ukradených) strojů Enigma sestavit katalog obsahující všechny možné řetězce. Tato práce trvala téměř rok, ale výsledkem byla schopnost číst německou korespondenci [6] .

Jak poznamenává Singh, byla to schopnost rozdělit problém na dvě složky (nastavení rotorů a nastavení plugboardu), která umožnila Rejewskému se s tímto úkolem vyrovnat, stejně jako pomoc matematiků Cipher Bureau a Schmidta [6] :

Asheovy dokumenty se staly mannou z nebes  - všechny dveře se otevřely ve stejnou chvíli.

Původní text  (anglicky)[ zobrazitskrýt] Ascheho dokumenty byly vítány jako manna z nebes a všechny dveře byly okamžitě otevřené. – Marian Rejewski [6]

Poté, co bylo obnoveno denní nastavení rotoru, zbývalo zjistit nastavení plugboardu. Z kryptografického hlediska to byla jednoduchá monoalfabetická šifra , navíc omezená na pouhých 6 párů záměn písmen. Text často ani nebylo potřeba podrobit frekvenční kryptoanalýze, ale pouze podívat se na řádky jako „alliveinbelrin“ ( do Berlína dorazí  s náhradou R ↔ L) a další, které bylo snadné obnovit „od oka“ [6] .

V roce 1934 začalo Německo přestavovat polohu rotorů každý měsíc místo každého čtvrtletí. V reakci na to Marian Rejewski navrhl zařízení zvané „cyklometr“, které umožňuje rychle znovu vytvořit katalog cyklů [8] .

15. září 1938 Německo změnilo postup šifrování a znemožnilo použití katalogů sestavených pomocí cyklometru. Polští kryptografové byli nuceni hledat jiné způsoby dešifrování. Takové bylo použití bombových strojů a Zygalského děrovaných plechů [7] .

15. prosince 1938 Německo přidalo 4. a 5. rotor a 1. ledna 1939 zvýšilo počet plugboardových spojení z 6 na 10. To vše značně ztížilo kryptoanalýzu Enigmy [6] [7] .

V létě 1939 , kdy byla zřejmá nevyhnutelnost invaze do Polska, úřad předal výsledky své práce britským a francouzským zpravodajským službám. Přestože polští matematici nikdy nebyli schopni šifru rozluštit, mezi výsledky byly „živé“ kopie stroje a elektromechanická „Bomba“, která se skládala ze dvou spárovaných Enigmat a pomáhala při dešifrování, stejně jako unikátní techniky kryptoanalýzy [1] .

PC Bruno

Britská scéna

Další práce na hacknutí Enigmy probíhaly na Station X, tajném britském zpravodajském středisku později známém jako Bletchley Park .

Personál

Vedoucím projektu byl jmenován veterán vojenské rozvědky Alistair Denniston . Dešifrovací práce vedl Dennistonův kolega v místnosti č. 40 , renomovaný lingvista a kryptoanalytik Alfred Knox ( "  Dilly" Knox ). Za celkovou organizaci práce odpovídal profesor matematiky Gordon Welchman . Denniston začal nabírat kryptoanalytiky na základě inteligence: lingvisty, matematiky, šachisty, mistry v luštění křížovek , egyptology a dokonce i paleontology . 1] . Zejména slavný šachový mistr Stuart Milner-Barry byl jedním z prvních přijatých .  Mezi matematiky byl i mladý profesor logiky z Cambridge – Alan Turing [1] [Pozn. 2] .

Metoda

Zachycování nepřátelských rádiových zpráv bylo prováděno desítkami přijímacích stanic, které měly kódové označení „ Y-stanice “. Bletchley Park denně dostával tisíce takových zpráv. Bletchley Park měl k dispozici přesnou kopii Enigmy, takže se dešifrování zpráv omezilo na výběr instalace disků a u pozdějších modelů zásuvný přepínač. Složitost úkolu zhoršovala skutečnost, že se denně měnilo nastavení rotorů, takže dešifrovací služby pracovaly nepřetržitě ve třech směnách [Pozn. 3] .

Design Enigmy při správném použití poskytoval téměř úplné utajení [pozn. 4] . V praxi však byli němečtí uživatelé Enigmy často nedbalí a dávali vodítka britským analytikům (takové vodítka se v anglickém studentském slangu nazývaly jesličky ). Právě na využití a systematizaci takových chyb byla metoda dešifrování založena.

Nápovědou byly jakékoli často se opakující texty, jako jsou pozdravy, čísla (kódované podle výslovnosti: „jeden“, „dva“ atd. [Poznámka 5] ). Všechny stopy byly zaneseny do kartotéky (Index) spolu s kontextem: rukopis radisty, místo a čas přenosu atd.

Při absenci potřebného počtu stop, zejména v předvečer velkých operací, byla přijata zvláštní opatření k jejich získání. Tato technika dostala kódové označení „ zahradnictví “ ( anglicky  gardening ). Například před odjezdem dalšího polárního konvoje byla provedena demonstrativní těžba určitého úseku moře. Pokud nepřítel oznámil výsledky odminování s uvedením dříve známých souřadnic, poskytlo to požadované vodítko.

Turing

Jedním z hlavních teoretiků Bletchley Park byl Alan Turing . Po prostudování polských materiálů došel Turing k závěru, že již nebude možné použít předchozí přístup s úplným výčtem zpráv. Za prvé by to vyžadovalo vytvoření více než 30 strojů polského typu, což byl mnohonásobek ročního rozpočtu „Stanice X“, a za druhé by se dalo očekávat, že Německo by mohlo napravit konstrukční chybu, na které byla založena polská metoda . Proto vyvinul vlastní metodu, založenou na výčtu sekvencí znaků ve výchozím textu.

Němci brzy přidali do designu Enigmy spínací zařízení, čímž výrazně rozšířili počet možností kódu. Problém, který pro Brity vyvstal, vyřešil Gordon Welchman , který navrhl design „diagonální desky“. Výsledkem této práce byl v srpnu 1940 sestrojený kryptoanalytický stroj Bombe [pozn. 6] . Postupem času bylo v Bletchley Park instalováno více než 200 strojů [1] , což umožnilo zvýšit rychlost dešifrování na dva až tři tisíce zpráv denně [9] [Pozn. 7] .

Přestože Bombe doznala určitých změn v detailech, její celkový vzhled zůstal stejný: skříň vážící asi tunu, přední panel dva krát tři metry a na něm 36 skupin rotorů, v každé tři. Použití stroje vyžadovalo speciální dovednosti a bylo velmi závislé na kvalifikaci obsluhy – dobrovolnic z ženské pomocné služby námořnictva [pozn. 8] . Následně, když byla část práce převedena do Spojených států, spolu s technologiemi byla vyslána část zaměstnanců [1] .

"Živé" informace

Německo čas od času provedlo strukturální změny stroje nebo nějakým způsobem posílilo kryptografickou ochranu. V takových případech byli kryptoanalytici z Bletchley Park bezmocní a naléhavě bylo potřeba další práce, aby našli popis změn nebo alespoň nové kopie instrukcí a strojů Enigmy [1] .

V roce 1940 provedlo německé námořnictvo na voze některé změny. Teprve po zajetí ponorky U-110 9. května 1941 spolu s několika novými kopiemi stroje byli britští kryptoanalytici schopni pochopit změny [1] .

V roce 1942 , po uvedení čtyřrotorového stroje do provozu, nebyl Bletchley Park šest měsíců schopen dešifrovat zprávy. Teprve 30. října 1942 ukořistila protiponorková loď Petard za cenu životů dvou námořníků modernizovanou Enigmu z ponorky U-559 [1] .

4. června 1944 zajalo americké námořnictvo šifrovací stroj Enigma s kódy na ponorce U-505 .

Utajení

Tohle je moje slepice s netopýry, která snáší zlatá vejce, ale nikdy se necheká.

Winston Churchill v Bletchley Parku

Britská vláda udělala vše pro to, aby skryla svůj úspěch v luštění německých šifer jak před nepřítelem, tak před vedením SSSR. Za tímto účelem musely být všechny akce založené na datech programu Ultra doprovázeny krycími operacemi, maskujícími skutečný zdroj informací [pozn. 9] . Takže k přenosu informací z Ultra do SSSR byla použita švýcarská organizace Lucy , která podle legendy měla zdroj na vrcholu německého vedení. Informace obdržené od Lucy předal do SSSR rezident sovětské rozvědky ve Švýcarsku Sandor Rado [pozn. 10] .

K maskování Ultra byly použity fiktivní průzkumné lety, rozhlasová hra atd .

Existenci programu Ultra znal přísně omezený okruh lidí, jejichž počet byl asi deset lidí. Potřebné informace předávala na místo určení síť zpravodajských jednotek vyslaných na velitelství velitelů armády a námořnictva. Zároveň nebyl zveřejněn zdroj informací, což někdy vedlo k podcenění celkem spolehlivých informací Ultra a velkým ztrátám britským velením (viz. Smrt letadlové lodi Glories ).

SSSR

Mezi informacemi, které Velká Británie obdržela, byly informace o přípravách invaze do SSSR . Přes riziko prozrazení zdroje byly informace předány sovětské vládě [10] . Stalin však požadoval, aby informace pocházely ze tří nezávislých zdrojů [11] [12] [pozn. 11] .

Navzdory obavám ze schopnosti Německa naslouchat sovětské rádiové komunikaci Churchill 24. července 1941 nařídil, aby informace získané v důsledku operace Ultra byly sdíleny se SSSR , s výhradou úplného vyloučení rizika kompromitace zdroje [13]. [Poznámka. 12] .

Vyhodnocení výsledků

Někteří autoři poukazují na to, že z moderního hlediska nebyla šifra Enigma příliš spolehlivá [1] . Jeho naprostá spolehlivost však svého času nevzbuzovala u německých specialistů žádné pochybnosti: až do samého konce války hledalo německé velení důvody pro úniky utajovaných informací kdekoli, jen ne v prozrazení Enigmy. To je důvod, proč se úspěch britských šifrátorů stal zvláště cenným příspěvkem k vítězství nad nacismem.

Po válce

Po skončení války byly téměř všechny dešifrovací stroje zničeny. Na začátku 21. století skupina britských nadšenců znovu vytvořila stroj Colossus [pozn. 13] , což trvalo asi 10 let [9] .

Viz také

Poznámky

  1. ↑ Byly tam i chyby: mezi pozvanými do projektu byl biolog, nadporučík Geoffrey Tundy, specialista na kryptogamy .
  2. ↑ Max Newman , Tom Flowers a další specialisté přišli do Bletchley Parku později v souvislosti s prací na šifře Tunny .
  3. ↑ Šifru Enigma využívala nejen armáda, letectví a námořnictvo, ale také vojenské zpravodajství ( Abwehr ), železnice a další služby. Všechny používaly vlastní nastavení rotoru.
  4. ↑ Důležitou konstrukční chybou byla nemožnost zakódovat písmeno stejným písmenem. Tato vlastnost Enigmy byla široce používána při dešifrování.
  5. ↑ Turing poznamenal, že číslo „jedna“ ( německy  Eins ) se vyskytuje v 90 % zpráv. Na tomto základě byla postavena speciální metoda dešifrování - "eins-algorithm". Dokonce i pozdrav Heil Hitler a hrubé nadávky byly použity jako jesličky , což zvláště pobavilo početný ženský personál Bletchley Park.
  6. ↑ Polský stroj se jmenoval "bomba" ( polsky Bomba kryptologiczna  - Kryptologická bomba ). Bomba v angličtině - bomba . Jeho název podle jedné verze pochází z názvu zmrzlinového dezertu Bombe glacée ( „Jedna teorie byla, že bomba byla pojmenována po zmrzlině, bombe glacee, která se jedla, když byl stroj vynalezen.“ Archivní kopie ze dne 18. dubna 2018 na Wayback Machine // Enigma: The Battle for the Code, Hugh Sebag-Montefiore, 2002, ISBN 978-0-471-43721-5 ).
  7. ↑ Bombe byla vyrobena Machines ; design stroje zpracoval hlavní konstruktér společnosti Harold Keen . 
  8. ↑ Auta a obsluha se nacházela mimo Bletchley Park v okolních vesnicích.
  9. ↑ Verze o odmítnutí chránit Coventry za účelem zachování tajemství Ultra není pravdivá a je založena výhradně na vzpomínkách F. W. Winterbottoma , důstojníka RAF, který k takovým informacím neměl přístup. Winterbottomova verze byla opakovaně vyvrácena jinými memoáry a historiky.
  10. ↑ SSSR měl nějaké informace o programu Ultra od svého agenta v Bletchley Parku - Johna Cairncrosse , jednoho z členů Cambridge Five . Britové nevěděli o Cairncrossově roli až do roku 1951.
  11. ↑ F. Winterbotham píše, že v budoucnu Britové z důvodu utajení informace nesdíleli. Takže podle Winterbothama se kurská operace Wehrmachtu v SSSR dozvěděla z jiných zdrojů. Je však třeba mít na paměti, že Winterbothamova kniha byla vydána předtím, než bylo dešifrování Lorenzova kódu (1975) odstraněno z britských archivů , a on sám, jako důstojník letectva během války, neměl přístup k tajným informacím. informace o Enigmě. Archivní materiály jednoznačně svědčí o předání podrobného plánu operace Citadela na začátku roku 1943 do Moskvy prostřednictvím fiktivní sítě agentů Lucy ( časopis Rutherford: "Colossus: Breaking the German 'Tunny' Code at Bletchley Park" Archived 4. října 2013 na Wayback stroj ).
  12. ↑ Program Ultra zahrnoval rozluštění nejen kódu Enigmy, ale také mnohem složitějšího Lorenzova kódu . Prvním výsledkem rozluštění posledně jmenovaného byl letní útočný plán Wehrmachtu u Kurska ( Operace Citadela ).
  13. ↑ Colossus neměl rozluštit „Enigmu“, ale „ Lorenze “.

Zdroje

  1. ↑ 1 2 3 4 5 6 7 8 9 10 11 Leonid Chernyak Tajemství projektu Ultra Archivní kopie z 26. června 2019 na Wayback Machine
  2. ↑ 1 2 3 4 5 6 D. A. Larin, kandidát technických věd, G. P. Shankin, doktor technických věd, profesor. Druhá světová válka ve vzduchu: Některé aspekty operace Ultra  // Ochrana informací. Uvnitř . Archivováno z originálu 20. ledna 2014.
  3. ↑ Gebrauchsanweisung für die Chiffriermaschine Enigma . Archivováno 17. května 2011 na Wayback Machine  (německy) .
  4. ↑ Schlüsselanleitung für die Chiffriermaschine Enigma . Archivováno 24. září 2015 na Wayback Machine  (německy) .
  5. ↑ Enigma Procedure Archived 5. března 2021 na Wayback Machine .
  6. ↑ 1 2 3 4 5 6 7 8 9 Singh S. Craking the Enigma // The Code Book , Histoire des codes secrets  (anglicky) : The Science of Secrecy from Ancient Egypt to Quantum Cryptography, De l'Égypte des pharaons à l ' ordinateur quantique - NYC : Doubleday , Knopf Doubleday Publishing Group , 1999. - S. 143-160. — 416 s.
  7. ↑ 1 2 3 Richard A. Woytak. Rozhovor s Marianem Rejewskim  (anglicky)  // Cryptologia. - Taylor & Francis, 1982. - Sv. 6 , iss. 1 . - S. 50-60.
  8. ↑ Anin, 2000 , Ostatní. Poláci. "Bruno" vs. "Enigma", str. 449-451.
  9. ↑ 1 2 Paramonov, Vladimir Britští nadšenci znovu vytvořili dekodér Enigma (nepřístupný odkaz) . Compulenta (12. září 2006). Datum přístupu: 17. ledna 2010. Archivováno z originálu 1. listopadu 2010. 
  10. ↑ Rutherford journal: "Colossus: Breaking the German 'Tunny' Code at Bletchley Park" Archivováno 4. října 2013 na Wayback Machine .
  11. ↑ Lewin, 2001 , str. 104.
  12. ↑ Winterbotham F. Operation Ultra. - M.: Military Publishing, 1978.
  13. ↑ Anin, 2000 , str. 359-366.

Literatura

Odkazy

 Kryptografie druhé světové války
Organizace
Osobnosti
Šifry a šifrovací zařízení
Kryptanalytická zařízení