Lorenzova šifra - Lorenz cipher

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

Lorenz SZ40 , SZ42a a SZ42b němečtí rotor proudová šifra stroje používané německou armádou během druhé světové války . Vyvinula je společnost C. Lorenz AG v Berlíně . Název modelu SZ byl odvozen od Schlüssel-Zusatz , což znamená šifrované připojení . Přístroje implementovaly šifru proudu Vernam .

Britští kryptoanalytici , kteří označovali šifrovaný německý dálnopisný provoz jako Fish , dabovali stroj a jeho provoz Tunny (což znamená tuňák) a vyvodili jeho logickou strukturu tři roky předtím, než takový stroj viděli.

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

Pro tento provoz byl použit spíše radioteletový typ (RTTY) než pevné obvody. Tyto zprávy jiné než Morseovy (NoMo) byly vyzvednuty britskými Y stanicemi v Knockholtu v Kentu a Dánském vrchu v jižním Londýně a odeslány do Vládního zákoníku a školy Cypher v Bletchley Parku (BP). Některé byly dešifrovány pomocí ručních metod, než byl proces částečně automatizován, nejprve pomocí strojů Robinson a poté pomocí počítačů Colossus . Rozluštěné Lorenzovy zprávy byly jedním z nejvýznamnějších příspěvků k britské ultra vojenské rozvědce a k vítězství spojenců v Evropě, a to díky strategické povaze informací, které byly získány z Lorenzových dešifrování.

Dějiny

Po druhé světové válce vstoupila skupina britských a amerických kryptoanalytiků do Německa s frontovými jednotkami, 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, vypleněna nebo zajata Sověty. Říkalo se jim Target Intelligence Committee : TICOM.

Od zajatých německých kryptografů Dr. Huttenhaina a Frickeho se dozvěděli o vývoji SZ40 a SZ42 a/b. Design byl pro stroj, který by mohl být připojen 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 uznáno, že bezpečnost tohoto stroje nebyla velká. Definitivní SZ40 měl dvanáct rotorů s pohyblivými vačkami. Pět nejvíce rotorů zcela vpravo se nazývalo Spaltencäsar, ale Bill Tutte je pojmenoval Chi kola . Pět úplně vlevo bylo pojmenováno Springcäsar , kola Psi pro Tutte. Prostřední dva rotory Vorgeleger nazývaly Tutte Mu nebo motorová kola.

Pět datových bitů každého telegrafního znaku kódovaného ITA2 bylo nejprve zpracováno pěti koly chi a poté dále zpracováno pěti psi koly. Vačky na kolech obrátily hodnotu trochu, pokud jsou ve zvednuté poloze, ale ponechaly ji beze změny, pokud ve snížené poloze.

Vernamova šifra

Gilbert Vernam byl výzkumný inženýr společnosti AT&T Bell Labs, který v roce 1917 vynalezl šifrovací systém, který používal booleovskou funkci „exclusive or“ (XOR) , symbolizovanou ⊕. To představuje následující „ tabulka pravdy “, kde 1 představuje „pravda“ a 0 znamená „nepravda“.

Tabulka pravdivosti XOR
Vstup A ⊕ B
A B
0 0 0
0 1 1
1 0 1
1 1 0

Další názvy této funkce jsou: Nerovné (NEQ), sčítání modulo 2 (bez 'carry') a odčítání modulo 2 (bez 'půjčit').

Vernamova šifra je algoritmus se symetrickým klíčem , tj. Stejný klíč se používá jak k šifrování prostého textu k výrobě šifrového textu, tak k dešifrování šifrového textu k získání původního prostého textu:

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

a:

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

To vytváří základní reciprocitu, která umožňuje použít stejný stroj se stejným nastavením pro šifrování i dešifrování.

Vernamova myšlenka byla použít konvenční telegrafickou 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á ( jednorázová páska ), ale generování a distribuce takových pásek představovalo značné praktické potíže. Ve 20. letech 20. století vynalezli čtyři muži v různých zemích stroje s rotorovým šifrovacím zařízením, které vytvářely klíčový proud, který by fungoval místo pásky. Jedním z nich byl Lorenz SZ40/42 z roku 1940.

Klíčový proud

Logické fungování systému Tunny bylo dobře vyřešeno, než kryptoanalytici z Bletchley Parku viděli jeden ze strojů - což se stalo až v roce 1945, kdy se Německo vzdalo Spojencům.

Stroje Lorenz SZ měly po 12 kolech s různým počtem vaček (neboli „čepů“).
OKW/
Název kola Chi
A B C D E F G H J. K L

Název kola BP
ψ 1 ψ 2 ψ 3 ψ 4 ψ 5 μ 37 μ 61 χ 1 χ 2 χ 3 χ 4 χ 5
Počet
vaček (kolíků)
43 47 51 53 59 37 61 41 31 29 26 23

Stroj SZ sloužil jako in-line nástavec ke standardnímu dálnopisu Lorenz. Měla kovovou základnu 19 palců × 15,5 palců (48 cm × 39 cm) a byla 17 palců (43 cm) vysoká. Znaky dálnopisu sestávaly z pěti datových bitů (neboli „impulsů“) zakódovaných v mezinárodní telegrafické abecedě č. 2 (ITA2) . Stroj generoval proud pseudonáhodných znaků. Ty tvořily klíč, který byl kombinován se vstupními znaky prostého textu, aby se vytvořily výstupní znaky šifrového textu. Kombinace proběhla pomocí procesu XOR (nebo přidání modulo 2).

Tok klíčů se skládal ze dvou komponentních částí, které byly společně vytvořeny XOR. Ty byly generovány dvěma sadami pěti kol, která se otáčela dohromady. Kryptanalytik Bletchley Parku Bill Tutte je nazval χ („ chi “) kola a ψ („ psi “) kola. Každé kolo mělo po svém obvodu řadu vaček (neboli „čepů“). Tyto vačky lze nastavit ve zvýšené (aktivní) nebo snížené (neaktivní) poloze. Ve zvýšené poloze vygenerovaly '1', která obrátila hodnotu bitu, ve snížené poloze vygenerovaly '0', což ponechalo bit beze změny. Počet vaček na každém kole se rovnal počtu impulzů potřebných k jejich úplnému otočení. Všechna tato čísla jsou navzájem co-prime , což dává nejdelší možnou dobu, než se vzor opakuje. Toto je součin počtu pozic kol. U sady χ kol to bylo 41 × 31 × 29 × 26 × 23 = 22 041 682 a u kol ψ 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, byl1,603 × 10 19, tj. 16 miliard miliard.

Po zašifrování každé postavy se sada pěti χ kol pohybovala na jedné pozici. Pět ψ kol však postupovalo přerušovaně. Jejich pohyb byl řízen dvěma μ („ mu “) nebo „motorovými“ koly v sérii. Motorové kolo SZ40 μ 61 našláplo pokaždé, ale motorové kolo μ 37 našláplo, pouze pokud bylo první motorové kolo „1“. V ¥ kola pak vystoupil jen v případě, že druhý motor kola byla ‚1‘. Modely SZ42A a SZ42B přidaly tomuto mechanismu další známost, známou v Bletchley Park jako Omezení . Dvě ze čtyř různých omezení zahrnovaly charakteristiky otevřeného textu, a tak byly autoklávy .

Tok klíčů generovaný stroji SZ měl tedy χ složku a ψ složku. Symbolicky lze klíč, který byl zkombinován s otevřeným textem pro šifrování a s šifrovaným textem pro dešifrování, znázornit následovně.

key = χ -key ⊕ ψ -key

Nicméně pro označení, že ψ složka často nezměnila o znak, termín prodloužen psi byl použit, symbolizované jako: ln‘ . Šifrování lze tedy symbolicky zobrazit jako:

prostý text ⊕ χ -stream ⊕ ψ ' -stream = šifrový text

a dešifrovat jako:

šifrový text ⊕ χ -stream ⊕ ψ ' -stream = prostý text.

Úkon

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

Každý spoj „Tunny“ měl č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ě. Měly to dvě složky; nastavení vzorů vaček na kolech a otáčení koleček pro zahájení šifrování zprávy. Nastavení vačky se před létem 1944 měnilo méně často. Ψ vačkové hřídele se zpočátku měnily pouze čtvrtletně, ale později měsíčně, χ kola se měnily měsíčně, ale vzory motorových kol se měnily denně. Od 1. srpna 1944 byly všechny vzory kol denně měněny.

Zpočátku byla nastavení kola pro zprávu odeslána na přijímací konec pomocí 12písmenného indikátoru odesílaného nešifrovaně, přičemž písmena jsou spojena s pozicemi kol v knize. V říjnu 1942 to bylo změněno na používání knihy jednorázových nastavení v takzvané knize 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 a více kombinací. Jakmile byly použity všechny kombinace v knize QEP, byly nahrazeny novou. Nastavení zpráv nemělo být nikdy znovu použito, ale příležitostně bylo, poskytovalo „hloubku“, kterou by mohl využít kryptoanalytik.

Jak byla běžná praxe v telegrafii, zprávy jakékoli délky byly zadávány do teleprinteru s perforátorem papírové pásky . Typický sled operací by spočíval v tom, že vysílající operátor zprávu zpacká, naváže kontakt s přijímajícím operátorem, pomocí spínače EIN / AUS na stroji SZ jej připojí do obvodu a poté protáhne pásku čtečkou. 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 lepící pásku. Protože to byla praxe, prostý text neobsahoval znaky pro "návrat na začátek řádku", "posun řádku" nebo znak null (prázdná páska, 00000).

Kryptoanalýza

Přestavěný britský tuňák v Národním muzeu výpočetní techniky , Bletchley Park . Emuloval funkce Lorenzu SZ40/42, produkující tištěný čistý text ze vstupu šifrového textu.

Britští kryptografové v Bletchley Parku odvodili provoz stroje do ledna 1942, aniž by kdy viděli stroj Lorenz, což byl čin umožněný chybou německého operátora.

Zachycení

Provoz tuňáků znali operátoři stanice Y zvyklí poslouchat přenos morseovky jako „novou hudbu“. Jeho odposlech byl původně soustředěn na stanici ministerstva zahraničí Y provozovanou metropolitní policií na Denmark Hill v Camberwell v Londýně. Ale kvůli nedostatku zdrojů v této době (kolem roku 1941), to dostalo nízkou prioritu. Nová stanice Y, Knockholt v Kentu , byla později postavena speciálně pro zachycení provozu Tunny, aby bylo možné zprávy efektivně zaznamenávat a odesílat do Bletchley Parku. Vedoucí stanice Y Harold Kenworthy se přesunul k Knockholtu. Později byl povýšen do čela ministerstva zahraničí pro výzkum a vývoj (FORDE).

Porušení kódu

Dne 30. srpna 1941 byla z Athén do Vídně přenesena zpráva o přibližně 4 000 znacích . Zpráva však na druhém konci nebyla přijata správně. 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 dalo kódovačům vědět, co se děje.

Odesílatel poté zprávu znovu odeslal, ale zásadně 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 šifry proudu. Na tom by nezáleželo, kdyby obě zprávy byly totožné, nicméně podruhé operátor provedl ve zprávě několik malých změn, například pomocí zkratek, čímž byla druhá zpráva o něco kratší.

Z těchto dvou příbuzných šifrových textů, kryptanalytikům známých jako hloubka , vysvobozený kryptanalytik brigádní generál John Tiltman ve výzkumné sekci vyňal dva prosté texty a tím i klíčový proud . Ale ani téměř 4 000 znaků klíče týmu nestačilo zjistit, jak se stream generuje; bylo to příliš složité a zdánlivě náhodné.

Po třech měsících předala sekce pro výzkum úkol matematikovi Billovi Tuttemu . Použil techniku, kterou se naučil při svém kryptografickém výcviku, ručně vypisovat klíč a hledat opakování. Tutte to udělal s původními 5bitovými Baudotovými kódy dálnopisu , což ho přivedlo k jeho počátečnímu průlomu v rozpoznávání 41bitového opakování. Během následujících dvou měsíců až do ledna 1942 Tutte a jeho kolegové vypracovali kompletní logickou strukturu šifrovacího stroje. Tento pozoruhodný kus reverzního inženýrství byl později popsán jako „jeden z největších intelektuálních počinů druhé světové války“.

Po tomto prasknutí Tunny speciální tým kódů jističů byla zřízena na základě Ralph Tester , většina původně přestoupil z Alan Turing ‚s Hut 8 . Tým se stal známým jako Testery . Prováděl převážnou část následné práce při rozbíjení zpráv Tunny, ale pomohly mu stroje v doplňkové sekci pod Maxem Newmanem známým jako Newmanry .

Dešifrovací stroje

Britové postavili několik složitých strojů na pomoc útoku na Tunny. První byl britský Tunny . Tento stroj byl navržen společností Bletchley Park na základě reverzní inženýrské práce provedené Tiltmanovým týmem v Testery, aby napodobil Lorenzův šifrovací stroj. Když testery našly nastavení kolíku, byl stroj Tunny nastaven a spuštěn tak, aby bylo možné zprávy vytisknout.

Pro Newmanry byla postavena rodina strojů známých jako „ Robinsoni “. Tito použili dvě papírové pásky spolu s logickými obvody k nalezení nastavení kol kolíků χ stroje Lorenz. Robinsonovi měli velké problémy udržet synchronizované dvě papírové pásky a byli relativně pomalí, četli jen 2 000 znaků za sekundu.

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

Nejdůležitějším strojem byl Kolos, jehož bylo do konce války používáno deset, první byl uveden do provozu v prosinci 1943. Ačkoli nebyly plně programovatelné, byly mnohem efektivnější než jejich předchůdci, což představovalo pokroky v elektronických digitálních počítačích . The Colossus počítače byly vyvinuty a postaveny Tommy Flowers , na Dollis Hill Post Office Research Station , s použitím algoritmů vyvinutých Bill tutte a jeho týmem matematiků. Colossus se ukázal být účinný a rychlý proti šifrovacímu stroji Lorenz SZ42 s dvanácti rotory online.

Některé vlivné osobnosti měly pochybnosti o jeho navrhovaném návrhu dešifrovacího stroje a Flowers pokračoval v projektu, přičemž jej částečně financoval sám. Stejně jako pozdější ENIAC z roku 1946, Colossus neměl uložený program a byl programován pomocí zásuvných desek a propojovacích kabelů. Bylo to rychlejší, spolehlivější a schopnější než Robinsoni, takže to urychlilo proces hledání nastavení kolíků Lorenz χ . Vzhledem k tomu, že Colossus generoval domnělé klíče elektronicky, musel přečíst pouze jednu pásku. Stalo se tak s optickou čtečkou, která s rychlostí 5 000 znaků za sekundu byla poháněna mnohem rychleji než u Robinsonů, což znamenalo, že páska cestovala rychlostí téměř 30 mil za hodinu (48 km/h). To a taktování elektroniky z otvorů na řetězových kolečkách opticky čtené papírové pásky zcela odstranilo problémy se synchronizací Robinsonů. Vedení Bletchley Park, které bylo skeptické vůči schopnosti Flowers vyrobit funkční zařízení, na něj okamžitě začalo tlačit, aby zkonstruoval další. Po skončení války byly stroje Colossus na rozkaz Winstona Churchilla rozebrány, ale GCHQ si dva z nich ponechal.

Vedoucí testerů a lámači kódů Tunny

  • Ralph Tester : lingvista a vedoucí Testery
  • Jerry Roberts : vedoucí směny, lingvista a vedoucí lámač kódů
  • Peter Ericsson: vedoucí směny, lingvista a vedoucí prolomení kódu
  • Victor Masters: vedoucí směny
  • Denis Oswald: lingvista a senior codebreaker
  • Peter Hilton : rozbíječ kódů a matematik
  • Peter Benenson : rozbíječ kódů
  • Peter Edgerley: rozbíječ kódů
  • John Christie: rozbíječ kódů
  • John Thompson: codebreaker
  • Roy Jenkins : rozbíječ kódů
  • Shaun Wylie : rozbíječ kódů
  • Tom Colvill: generální ředitel

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

Přeživší stroje

Stroj Tunny (Lorenz) vystavený v Národním kryptologickém muzeu, Fort Meade, Maryland, USA

Lorenzovy šifrovací stroje byly stavěny 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 Paderbornu a Deutsches Museum , muzeu vědy a technologie v Mnichově. Dva další stroje Lorenz jsou také vystaveny v Bletchley Parku a The National Museum of Computing ve Spojeném království. Další příklad je také vystaven v Národním kryptologickém muzeu ve Spojených státech.

John Whetter a John Pether, dobrovolníci z Národního muzea výpočetní techniky, koupili na eBay za 9,50 libry dálkový tisk Lorenz , který byl získán ze zahradní kůlny v Southend-on-Sea . Bylo zjištěno, že jde o vojenskou verzi druhé světové války, byl renovován a v květnu 2016 instalován vedle stroje SZ42 v galerii muzea „Tunny“.

Viz také

Poznámky

Reference

Další čtení

externí odkazy