Lorenzova šifra - Lorenz cipher - Wikipedia

Stroj Lorenz SZ42 s odstraněnými kryty. Bletchley Park muzeum

The Lorenz SZ40, SZ42a a SZ42b byli Němci rotor proudová šifra stroje používané Německá armáda v době druhá světová válka. Byly vyvinuty C. Lorenz AG v Berlín. Název modelu SZ byl odvozen z Schlüssel-Zusatz, význam šifrovací příloha. Prováděné nástroje a Vernam proudová šifra.

britský kryptoanalytici, který odkazoval na šifrovanou němčinu dálnopis provoz jako Ryba nazval stroj a jeho provoz Tuňák (což znamená tunafish) a odvodil jeho logickou strukturu tři roky předtím, než takový stroj uviděli.[1]

Stroje SZ byly řadovým připojením ke standardu dálnopisů. Experimentální spojení pomocí strojů SZ40 bylo zahájeno v červnu 1941. Vylepšené stroje SZ42 byly od poloviny roku 1942 dále využívány pro komunikaci na vysoké úrovni mezi Německé vrchní velení ve Wünsdorfu poblíž Berlína a armádní velitelé v celé okupované Evropě.[2] Pokročilejší SZ42A se začal běžně používat v únoru 1943 a SZ42B v červnu 1944.[3]

Typ radiotelety (RTTY) byl pro tento provoz použit spíše než pozemní obvody.[4] Tyto ne-Morse (NoMo) zprávy byly sebrány britskými Y-stanice na Knockholt a Denmark Hill a poslal na Vládní zákoník a škola Cypher na Bletchley Park (BP). Některé byly dešifrovány pomocí ručních metod, než byl proces částečně automatizován, nejprve pomocí Robinsonské stroje a pak s Kolosové počítače.[5] Dešifrované Lorenzovy zprávy byly jedním z nejvýznamnějších příspěvků Britům Ultra vojenská rozvědka a do Spojenecké vítězství v Evropě díky strategické povaze informací na vysoké úrovni, které byly získány dešifrováním Lorenza.[6]

Dějiny

Po druhé světové válce vstoupila do Německa skupina britských a amerických kryptoanalytiků s jednotkami v první linii, aby zajali dokumenty, technologie a personál různých německých signálních zpravodajských organizací, než mohla být tato tajemství zničena, vyrabována nebo zajata Sověti. Říkali jim Cílový zpravodajský výbor: TICOM.[7][8]

Od zajatých německých kryptografů Dr. Huttenhaina a Frickeho se dozvěděli o vývoji SZ40 a SZ42 a / b.[9] Konstrukce byla pro stroj, který lze připojit k jakémukoli dálnopisu. První stroj byl označován jako SZ40 (starý typ), který měl deset rotorů s pevnými vačkami. Bylo zjištěno, že bezpečnost tohoto stroje nebyla velká. Definitivní SZ40 měl dvanáct rotorů s pohyblivými vačkami. Bylo vyvoláno pět rotorů zcela vpravo Spaltencäsar ale pojmenoval Chi kola od Bill Tutte. Pět nejvíce vlevo bylo jmenováno Springcäsar, Psi kola do Tutte. Prostřední dva Vorgeleger byly povolány rotory Mu nebo motorová kola od firmy Tutte.

Pět datových bitů každého z nich ITA2 -kódovaný telegrafní znak byl zpracován nejprve pěti chi kola a pak je dále zpracovává pět psi kola. Vačky na kolech trochu změnily hodnotu, pokud jsou ve zvednuté poloze, ale ponechaly ji beze změny, pokud jsou ve snížené poloze.

Šifra Vernam

Hlavní článek: Gilbert Vernam

Gilbert Vernam byl AT&T Bell Labs výzkumný inženýr, který v roce 1917 vynalezl šifrovací systém, který používal Booleovský „exclusive or“ (XOR) funkce, symbolizovaná ⊕.[10] To představuje následující "pravdivostní tabulka ", kde 1 představuje" true "a 0 představuje" false ".

Tabulka pravd XOR
VstupA ⊕ B
AB
000
011
101
110

Jiná jména pro tuto funkci jsou: nerovná se (NEQ), modulo 2 sčítání (bez „carry“) a odčítání modulo 2 (bez „vypůjčení“).

Vernamova šifra je a algoritmus symetrického klíče, tj. stejné klíč se používá k šifrování prostý text vyrábět šifrový text a dešifrovat šifrovací text, aby se získal původní holý text:

holý text ⊕ klíč = šifrový text

a:

ciphertext ⊕ key = holý text

Tím se vytvoří zásadní vzájemnost, která umožňuje použít stejný stroj se stejným nastavením pro šifrování i dešifrování.

Vernamovým nápadem bylo použít konvenční telegrafní praxi s papírovou páskou prostého textu v kombinaci s papírovou páskou klíče. Každá klíčová páska by byla jedinečná (a jednorázová páska ), ale výroba a distribuce těchto pásek představovala značné praktické obtíže. Ve dvacátých letech minulého století vynalezli čtyři muži v různých zemích rotorové šifrovací stroje, které místo pásky vytvářely klíčový proud.[11] Jedním z nich byl Lorenz SZ40 / 42 z roku 1940.[12]

Klíčový stream

Logické fungování systému Tunny bylo vypracováno dlouho předtím, než kryptanalytici Bletchley Park uviděli jeden ze strojů - k čemuž došlo až v roce 1945, kdy se Německo vzdávalo spojencům.[13]

Stroje Lorenz SZ měly každé 12 kol s jiným počtem vaček (neboli „čepů“).
OKW /Chi
název kola 		A B C D E F G H Já J K. L
BP kolo
název[14]		 ψ1 ψ2 ψ3 ψ4 ψ5 μ37 μ61 χ1 χ2 χ3 χ4 χ5
Počet
vačky (kolíky) 		43 47 51 53 59 37 61 41 31 29 26 23

Stroj SZ sloužil jako řadové příslušenství ke standardnímu dálnopisu Lorenz. To mělo kovovou základnu 19 v × 15,5 v (48 cm × 39 cm) a byl 17 v (43 cm) vysoký.[12] Znaky dálnopisu se skládaly z pěti dat bity (nebo "impulsy"), kódované v Abeceda mezinárodní telegrafie č. 2 (ITA2). Stroj vygeneroval proud pseudonáhodné postavy. Ty tvořily klíč, který byl kombinován se vstupními znaky prostého textu a vytvořil výstupní znaky šifrovacího textu. Kombinace byla pomocí procesu XOR (nebo přidání modulo 2).[15]

Klíčový tok sestával ze dvou komponentních částí, které byly XOR-ed společně. Ty byly generovány dvěma sadami pěti kol, která se otáčela společně. Kryptanalytik Bletchley Park Bill Tutte je nazval χ ("chi ") kola a ψ ("psi „) kola. Každé kolo mělo po svém obvodu řadu vaček (nebo„ kolíků “). Tyto vačky bylo možné nastavit do zvednuté (aktivní) nebo snížené (neaktivní) polohy. Ve zvednuté poloze vygenerovaly„ 1 “, které obrátili hodnotu bitu, ve snížené poloze vygenerovali „0“, která ponechala bit beze změny.[16] Počet vaček na každém kole se rovnal počtu impulzů potřebných k tomu, aby mohly dokončit plnou rotaci. Tato čísla jsou všechna co-prime navzájem, což poskytlo nejdelší možnou dobu před opakováním vzoru. To je součin počtu pozic kol. Pro soubor χ kola to bylo 41 × 31 × 29 × 26 × 23 = 22 041 682 a pro ψ kola to bylo 43 × 47 × 51 × 53 × 59 = 322 303 017. Počet různých způsobů, jak bylo možné nastavit všech dvanáct kol, byl 1.603×1019 tj. 16 miliard miliard.

Sada pěti χ všechna kola se pohybovala na jedné pozici poté, co byla zašifrována každá postava. Pět ψ kola však přerušovaně postupovala. Jejich pohyb byl řízen těmito dvěma μ ("mu ") nebo" motorová "kola v sérii.[17] SZ40 μ61 motorové kolo šlapalo pokaždé kromě μ37 motorové kolo šlapalo, pouze pokud bylo první motorové kolo „1“. The ψ kola poté šlapala, pouze pokud bylo druhé motorové kolo „1“.[18] Modely SZ42A a SZ42B přidaly tomuto mechanismu, známému v Bletchley Park jako, další složitost Omezení. Dvě ze čtyř různých omezení zahrnovala charakteristiky holého textu, a tak tomu bylo autoklávy.[19]

Klíčový tok generovaný stroji SZ tedy měl a χ komponenta a ψ součástka. Symbolicky lze klíč, který byl zkombinován s holým textem pro šifrování a se šifrovacím textem pro dešifrování, reprezentovat následovně.[17]

klíč = χ-klíč ⊕ ψ-klíč

Nicméně k označení, že ψ komponenta se často nezměnila od znaku k znaku, výrazu prodloužený psi bylo použito, symbolizováno jako: Ψ '. Šifrování lze tedy zobrazit symbolicky jako:

holý text ⊕ χ-stream ⊕ ψ '-stream = ciphertext

a dešifrování jako:

ciphertext ⊕ χ-stream ⊕ ψ '-stream = holý text.

Úkon

Vačky na kolech 9 a 10 ukazující jejich zvednutou (aktivní) a sníženou (neaktivní) polohu. Aktivní vačka obrátila hodnotu bitu (0 → 1 a 1 → 0).

Každé spojení „Tunny“ mělo čtyři stroje SZ s vysílacím a přijímacím dálnopisem na každém konci. Aby šifrování a dešifrování fungovalo, musely být vysílací a přijímací stroje nastaveny shodně. Byly to dvě složky; nastavení vzorů vaček na kolech a otáčení kol pro začátek šifrování zprávy. Před létem 1944 byla nastavení vačky změněna méně často ψ vačky kol se zpočátku měnily pouze čtvrtletně, později však měsíčně χ kola se měnila každý měsíc, ale vzory motorových kol se měnily denně. Od 1. srpna 1944 se všechny modely kol denně měnily.[20]

Zpočátku bylo nastavení kola pro zprávu odesláno na přijímací konec pomocí 12 písmen indikátor zaslány nešifrované, přičemž písmena jsou spojena s pozicemi kol v knize. V říjnu 1942 to bylo změněno na použití knihy nastavení pro jedno použití v té, která byla známá jako kniha QEP. Poslední dvě číslice záznamu knihy QEP byly odeslány přijímajícímu operátorovi, aby vyhledal ve své kopii knihy QEP a nastavil kola svého stroje. Každá kniha obsahovala sto nebo více kombinací. Jakmile byly použity všechny kombinace v knize QEP, byla nahrazena novou.[21] Nastavení zpráv by nikdy nemělo být znovu použito, ale příležitostně byly, poskytující „hloubku“, kterou mohl využít dešifrovaný pracovník.[22]

Jak bylo běžné v telegrafické praxi, zprávy jakékoli délky byly zakódovány do a dálnopis s papírová páska perforátor. Typická posloupnost operací by byla, že odesílající operátor zprávu udeří, naváže kontakt s přijímajícím operátorem, použije EIN / AUS zapněte stroj SZ a připojte jej k obvodu a poté páskou protáhněte čtečku.[12] Na přijímacím konci by operátor podobně připojil svůj SZ stroj do obvodu a výstup by byl vytištěn na souvislou lepicí pásku. Protože to byla praxe, prostý text neobsahoval znaky pro „návrat vozíku“, „posun řádku“ ani znak null (prázdná páska, 00000).[4]

Kryptoanalýza

Hlavní článek: Cryptanalýza Lorenzovy šifry
Přestavěný britský tuňák v Národní muzeum výpočetní techniky, Bletchley Park. Emuloval funkce Lorenza SZ40 / 42 a ze vstupu šifrovacího textu vytvořil tištěný čistý text.

Britští kryptografové na Bletchley Park odvodil provoz stroje do ledna 1942, aniž by viděl stroj Lorenz, což byl čin umožněný chybou německého operátora.

Zachycení

Provoz tunelu byl znám uživateli Stanice Y operátoři zvyklí poslouchat Morseova abeceda přenos jako „nová hudba“. Jeho odposlech se původně soustředil na stanici Y ministerstva zahraničních věcí, kterou provozovala Metropolitní policie na Denmark Hill v Camberwell, Londýn. Ale kvůli nedostatku zdrojů v této době (kolem roku 1941) dostal nízkou prioritu. Nová stanice Y, Knockholt v Kent, byl později zkonstruován speciálně pro zachycení tunelového provozu, aby bylo možné zprávy efektivně zaznamenávat a odesílat do Bletchley Parku.[23] Přednost stanice Y, Harold Kenworthy, přesunul se k hlavě nahoru Knockholt. Později byl povýšen do čela Foreign Office Research and Development Establishment (F.O.R.D.E).

Rozbití kódu

Dne 30. srpna 1941 byla ze zprávy přenesena zpráva o délce přibližně 4000 znaků Athény na Vídeň. Zpráva však nebyla přijata správně na druhém konci. Přijímající operátor poté odeslal nekódovaný požadavek zpět odesílateli s žádostí o opětovné odeslání zprávy. To poskytovatelům kódů dalo vědět, co se děje.

Odesílatel poté znovu odeslal zprávu, ale kriticky nezměnil klíčové nastavení z původního „HQIBPEXEZMUG“. To byla zakázaná praxe; použití jiného klíče pro každou jinou zprávu je zásadní pro zabezpečení jakékoli proudové šifry. To by nevadilo, kdyby byly obě zprávy identické, avšak podruhé operátor provedl několik malých změn ve zprávě, například pomocí zkratek, čímž byla druhá zpráva poněkud kratší.

Z těchto dvou příbuzných šifrovacích strojů, které kryptoanalytici označují jako a hloubka, veteránský kryptoanalytik Brigádní generál John Tiltman ve výzkumné sekci škádlil dva holé texty a tudíž i keystream. Ale ani téměř 4 000 znaků klíče nestačilo na to, aby tým zjistil, jak byl stream generován; bylo to příliš složité a zdánlivě náhodné.

Po třech měsících předala sekce výzkumu úkol matematikovi Bill Tutte. Aplikoval techniku, kterou se naučil při kryptografickém výcviku, ruční psaní klíče a hledání opakování. Tutte to udělal s původním 5bitovým dálnopisem Baudotovy kódy, což ho vedlo k jeho počátečnímu průlomu v rozpoznání 41bitového opakování.[13][24] Během následujících dvou měsíců až do ledna 1942 Tutte a jeho kolegové vypracovali úplnou logickou strukturu šifrovacího stroje. Tento pozoruhodný kousek reverzní inženýrství byl později popsán jako „jeden z největších intelektuálních činů druhé světové války“.[13]

Po tomto popraskání Tunny byl vytvořen speciální tým kódovačů Ralph Tester, nejvíce původně převedeny z Alan Turing je Chata 8. Tým se stal známým jako Testery. Provádělo většinu následné práce při rozbíjení tuňáckých zpráv, ale pomáhali jí stroje v doplňkové části níže Max Newman známý jako Newmanry.[25]

Dešifrovací stroje

Britové postavili několik složitých strojů na pomoc při útoku na Tunny. První byla Britský tuňák.[26][27] Tento stroj navrhl Bletchley Park na základě reverzní inženýrství práce provedená Tiltmanovým týmem v Testery, aby napodobila šifrovací stroj Lorenz. Když testery našly nastavení otočného kolečka, byl stroj Tunny nastaven a spuštěn tak, aby bylo možné zprávy vytisknout.

Rodina strojů známých jako „Robinsons "byly postaveny pro Newmanry. Tito používali dva papírové pásky, spolu s logickými obvody, najít nastavení χ čepy stroje Lorenz.[28] Robinsonovi měli velké problémy se synchronizací obou papírových pásek a byli relativně pomalí, když četli jen 2 000 znaků za sekundu.

Tým vedený Tony Sale (vpravo) rekonstruoval Colossus (Mark II) v Bletchley Parku. Tady v roce 2006 dohlíží Sale na prolomení zašifrované zprávy s dokončeným strojem.

Nejdůležitějším strojem byl Kolos z nichž deset bylo používáno do konce války, první začalo fungovat v prosinci 1943. Ačkoli nebyly plně programovatelné, byly mnohem efektivnější než jejich předchůdci a představovaly pokrok v elektronické digitální počítače. The Kolos počítače byly vyvinuty a vyrobeny společností Tommy květiny, z Dollis Hill Výzkumná stanice pošty pomocí algoritmů vyvinutých společností W.T. Tutte a jeho tým matematiků.[29] Colossus se ukázal jako účinný a rychlý proti online šifrovacímu stroji Lorenz SZ42 s dvanácti rotory.

Některé vlivné osobnosti měly pochybnosti o jeho navrhovaném designu dešifrovacího stroje a Flowers pokračoval v projektu a částečně jej sám financoval.[30][31] Jako později ENIAC z roku 1946 Colossus neměl uložený program, a byl programován prostřednictvím zásuvných modulů a propojovacích kabelů. Bylo to rychlejší, spolehlivější a schopnější než Robinsonovi, a tak se urychlil proces hledání Lorenza χ nastavení kolíku. Jelikož Kolos generoval předpokládané klíče elektronicky, stačilo přečíst pouze jednu pásku. Udělalo to pomocí optické čtečky, která byla při rychlosti 5 000 znaků za sekundu poháněna mnohem rychleji než Robinsons a znamenala, že páska se pohybovala rychlostí téměř 30 mil za hodinu (48 km / h).[32] Toto a taktování elektroniky z opticky přečtených otvorů pro ozubená kola z papírové pásky zcela eliminovalo Robinsonovy problémy se synchronizací. Vedení Bletchley Park, které bylo skeptické vůči schopnosti Flowers vyrobit funkční zařízení, ho okamžitě začalo tlačit, aby postavilo další. Po skončení války byly Kolosovy stroje demontovány na rozkaz Winstona Churchilla,[33] ale GCHQ si ponechal dva z nich.[34]

Manažeři testery a Tunny codebreakers

  • Ralph Tester: lingvista a vedoucí testery
  • Jerry Roberts: vedoucí směny, lingvista a vedoucí porušovatel zákonů
  • Peter Ericsson: vedoucí směny, lingvista a vedoucí tvůrce kódů
  • Victor Masters: vedoucí směny
  • Denis Oswald: lingvista a vedoucí porušovatel zákonů
  • Peter Hilton: porušovatel kódu a matematik
  • Peter Benenson: lámač kódu
  • Peter Edgerley: porušovatel kódu
  • John Christie: porušovatel kódu
  • John Thompson: porušovatel kódu
  • Roy Jenkins: lámač kódu
  • Shaun Wylie: lámač kódu
  • Tom Colvill: generální ředitel

Na konci války se Testery rozrostly na devět kryptografek a 24 dívek ATS (jak se ženám, které sloužily v této roli, tehdy říkalo), s celkovým počtem zaměstnanců 118, organizovaných ve třech směnách nepřetržitě nepřetržitě.

Přežívající stroje

Tuňák (Lorenz) stroj na displeji v Národním kryptologickém muzeu, Fort Meade, Maryland, USA

Lorenzovy šifrovací stroje byly postaveny v malém počtu; dnes v muzeích přežije jen hrstka.

V Německu lze příklady vidět v Heinz Nixdorf MuseumsForum, počítačovém muzeu v Německu Paderborn a Deutsches Museum, muzeum vědy a techniky v Mnichově.[35] U obou jsou také zobrazeny dva další stroje Lorenz Bletchley Park a Národní muzeum výpočetní techniky ve Velké Británii. Další příklad je také na displeji u Národní kryptologické muzeum ve Spojených státech.

John Whetter a John Pether, dobrovolníci z Národního muzea výpočetní techniky, zakoupili dálnopis Lorenz eBay za 9,50 GBP, které byly získány ze zahradní boudy Southend-on-Sea.[36][37] Bylo zjištěno, že jde o vojenskou verzi druhé světové války, byla zrekonstruována a v květnu 2016 instalována vedle stroje SZ42 v galerii muzea „Tunny“.

Viz také

Poznámky

  1. ^ Hinsley 1993, str. 141
  2. ^ Hinsley 1993, str. 142
  3. ^ Copeland 2006, s. 38, 39
  4. ^ A b Dobře, Michie & Timms 1945, str. 4 z Německý tuňák
  5. ^ Dobrý 1993, str. 160–165
  6. ^ „Historie Lorenzovy šifry a kolosového stroje“. Stanfordská Univerzita. Citováno 9. září 2018.
  7. ^ Parrish 1986, str. 276.
  8. ^ Rezabek 2017, I Úvod: Původ TICOM.
  9. ^ Huttenhain & Fricke 1945, s. 16-19.
  10. ^ Klein, str. 2
  11. ^ Klein, str. 3
  12. ^ A b C Dobře, Michie & Timms 1945, str. 10 z Německý tuňák
  13. ^ A b C Prodej, Tony, Lorenzova šifra a jak to Bletchley Park zlomil, vyvoláno 21. října 2010
  14. ^ Dobře, Michie & Timms 1945, 1 Úvod: 11 German Tunny, 11B The Tunny Cipher Machine, str. 6.
  15. ^ Dobře, Michie & Timms 1945, str. 6 z Německý tuňák
  16. ^ Churchhouse 2002 156, 157.
  17. ^ A b Dobře, Michie & Timms 1945, str. 7 ze dne Německý tuňák
  18. ^ Roberts, Eric, Lorenz Schluesselzusatz SZ40 / 42, Stanfordská Univerzita
  19. ^ Dobře, Michie & Timms 1945, str. 8 z Německý tuňák
  20. ^ Dobře, Michie & Timms 1945, str. 14 z Německý tuňák
  21. ^ Copeland 2006, str. 45
  22. ^ Churchhouse 2002, str. 34
  23. ^ Dobře, Michie & Timms 1945, str. 281 palců Knockholt
  24. ^ Tutte 1998, str. 356, 357
  25. ^ Roberts 2009
  26. ^ Halton 1993
  27. ^ Bletchley Park dokončuje epický tunny stroj Registrace, 26. května 2011, Přístup k květnu 2011
  28. ^ Copeland 2006, str. 66
  29. ^ „Biografie profesora Tutteho - kombinatorika a optimalizace“. 13. března 2015.
  30. ^ Boden, Margaret Ann (2006). Mind as Machine: A History of Cognitive Science. Oxford: Clarendon Press. p. 159. ISBN  9780199543168.
  31. ^ https://books.google.ca/books?isbn=1861897375, strana 29
  32. ^ Květiny 2006, str. 100
  33. ^ Verdikt míru: Británie mezi ní včera a budoucností, Correlli Barnett, 2002
  34. ^ Copeland 2006, str. 173
  35. ^ "Kryptologie". Deutsches Museum. Citováno 30. října 2014.
  36. ^ O'Connell, Paddy (29. května 2016). „Tajný německý stroj na kód WW2 nalezen na eBay“. Broadcasting House. BBC novinky. Citováno 6. listopadu 2016.
  37. ^ Gayle, Damien; Meikle, James (29. května 2016). „Zařízení používané v nacistickém kódovacím stroji nalezeno k prodeji na eBay“. Opatrovník. Londýn. Citováno 6. listopadu 2016.

Reference

Další čtení

externí odkazy