Lorenz (šifrovací stroj)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 5. července 2022; kontroly vyžadují 2 úpravy .

"Lorenz" ( německy:  Lorenz-Chiffre , Schlüsselzusatz ; Lorenz SZ 40 a SZ 42 ) je německý šifrovací stroj používaný během druhé světové války k přenosu informací dálnopisem . Byl vyvinut společností C. Lorenz AG v Berlíně. Funkční princip stroje byl založen na Vernamově proudové šifře .

Z přepisů zpráv přenášených pomocí Enigmy vyšlo najevo, že Němci nazvali jeden ze svých systémů pro bezdrátový přenos informací dálnopisem „Sägefisch“ (z  němčiny  –  „ pila ryba “). Kvůli tomu začali britští analytici nazývat zakódovaný německý radiotelegrafní provoz „Fish“ ( angl.  fish „fish“). První kanál, který nepoužíval Morseovu abecedu , nazývali "Tunny" ( angl.  tunny " tuna ") [1] . Následně se tento název začal používat pro označení strojů Lorenz a všech jimi zašifrovaných zpráv.

Zatímco Enigma se používala hlavně v terénu, stroj Lorenz sloužil pro komunikaci na vysoké úrovni, kde bylo možné použít sofistikované zařízení, obsluhované speciálním personálem [2] .

Navenek se stroj Lorenz podobal Enigmě, protože používal rotor, ale pracoval na jiném principu. Rozměry stroje byly 45×45×45 cm a jednalo se o pomocné zařízení Lorenzova standardního dálnopisu ( Lorenz Lo133 Automatik ) [3] .

Vernamova šifra

Gilbert Vernam pracoval jako výzkumný pracovník v AT&T Bell Labs . V roce 1917 vynalezl šifrovací systém, který používal funkci XOR [4] . Lze si to představit jako následující pravdivostní tabulku, kde jedna představuje „pravdu“ a nula představuje „nepravdu“:

VSTUP VÝSTUP
A B A⊕B _ _
0 0 0
0 jeden jeden
jeden 0 jeden
jeden jeden 0

Ve Vernamově šifře:

Prostý text Klíč = Šifrovaný text Šifrovaný text Klíč = prostý text

To umožňuje stejnému počítači provádět šifrování a dešifrování.

Vernamovou myšlenkou bylo spojit děrnou pásku s prostým textem a děrnou pásku s klíčem. Každá děrná páska s klíčem musí být jedinečná, což je obtížné realizovat: takové pásky je poměrně obtížné vytvořit a distribuovat. V roce 1920 čtyři lidé z různých zemí vynalezli šifrovací stroje, které generovaly proudovou šifru [5] . Lorenz SZ40 byl jedním z nich, upravená verze vozu z roku 1942 se jmenovala SZ42A a SZ42B [3] .

Vnitřní uspořádání

Stroj SZ sloužil jako doplněk standardního Lorenzova dálnopisu [6] . Měl kovovou základnu o rozměrech 48 x 39 cm a byl vysoký 32 cm . Dálnopisné symboly se skládaly z pěti bitů dat a byly zakódovány pomocí mezinárodního telegrafního kódu č. 2 (ITC č. 2) [3] .

Šifrovací stroj provedl šifrování proudu generováním pseudonáhodné sekvence klíčů, která byla XORed přes znaky prostého textu vytvořena jako výstup znaků šifrovaného textu.

Každých pět bitů klíče bylo generováno odpovídajícími disky ve dvou částech stroje. Kryptanalytici z Bletchley Park je nazývali disky („ hee “) a („ psi “). Kontakty byly umístěny na každém disku. Mohou být ve zvednuté (aktivní) nebo spuštěné (neaktivní) poloze. Ve zvednuté poloze generovaly '1', ve snížené poloze - '0'. Všechny chi disky byly otočeny o jednu pozici po každém písmenu. Disky psi se také pohybovaly společně, ale ne po každém znaku. Jejich rotaci určují dva (" mu ") disky [7] . Disk 61 SZ40 se pohyboval o jednu pozici s každým znakem a disk 37 se pohyboval pouze tehdy, když byl kontakt na disku 61 v aktivní poloze. Pokud byl kontakt na 37. disku v aktivní poloze, pak bylo otočeno všech pět psi disků [7] . Modely SZ42A a SZ42B měly složitější mechanismus známý v Bletchley Park jako Limitations [8] . Proudová šifra generovaná strojem SZ tedy měla složky chi a psi , které byly kombinovány s funkcí XOR. Symbolicky by šifra, která byla kombinována pro šifrování s prostým textem – nebo dešifrování se šifrovaným textem – mohla být reprezentována následovně [7]

Key= Chi -Key ⊕ Psi -Key

Počet kontaktů na každém kotouči se rovná počtu impulsů přenesených na kotouč potřebných k dokončení celé otáčky. Stojí za zmínku, že tato čísla spolu souvisela takovým způsobem, že tvořila maximální možný čas před opakováním celé periody. Při celkovém počtu 501 kontaktů se to rovnalo 2 501 kombinacím, což je asi 10 151  – astronomicky velké číslo [9] . Analýza šifrování jednotlivých parcel v kódu každého písmene však umožnila odhalit krátkodobé chi-složky šifry; Pro dvojici zpráv jsou tedy nalezena opakování šifry s periodou od 41×31=1271 pro první dvě zprávy každého písmene do 26×23=598 pro poslední dvě.

Jak to funguje

Na každém výstupu Tunni byly čtyři stroje SZ s vysílacím a přijímacím dálnopisem na každém. Aby šifrování a dešifrování fungovalo, byly odesílací a přijímací stroje nakonfigurovány identicky. Pro spuštění šifrování stejným způsobem nastavili sekvence kontaktů na discích a disky otočili. Kontaktní sekvence byly měněny poměrně zřídka až do léta 1944. Kontakty na psi discích se zpočátku měnily jen jednou za čtvrt roku, ale pak se začaly měnit jednou za měsíc. Kontakty se také měnily měsíčně na discích chi a  denně na discích mu . Počínaje 1. srpnem 1944 se denně začalo měnit nastavení na všech discích [10] .

Zpočátku se nastavení kol posílalo pomocí 12písmenného indikátoru (indikátoru), který byl zasílán nekódovaně a ve kterém písmena odpovídala polohám kol. V říjnu 1942 to bylo změněno na použití jednorázových ladicích knih (QEP). Poslední dvě číslice zapsané v knize QEP byly odeslány přijímajícímu operátorovi, aby si je mohl vyhledat ve své kopii knihy QEP a nastavit disky na svém stroji. Každá kniha obsahovala sto nebo více kombinací. Jakmile byly použity všechny kombinace z QEP, byla kniha nahrazena. Nastavení pro přenos zprávy se nikdy nemělo opakovat, ale někdy se to stalo - a kryptoanalytici toho mohli využít.

V souladu s uznávanou praxí přenosu telegramů byla do dálnopisu přenášena zpráva libovolné délky z děrné papírové pásky . Typický sled akcí operátora byl následující: napsání zprávy, navázání spojení s přijímajícím operátorem, použití spínače EIN / AUS na stroji SZ pro připojení strojů a následné odeslání zprávy do čtečky. Na přijímací straně musí operátor navázat spojení mezi odesílajícím strojem a jeho strojem SZ a počkat na úplné vytištění zprávy na papírovou pásku. Text proto neobsahoval nový řádek, návrat vozíku ani znak null (00000).

Kryptoanalýza

Britským kryptoanalytikům z Bletchley Parku se v lednu 1942 podařilo prolomit kód Lorenzova stroje, aniž by stroj samotný viděli. To se stalo možným díky chybě německého operátora [11] .

Odposlech

Zachycení Tanniiny komunikace byl značný problém. Kvůli použití směrových rádiových vysílačů Němci byla úroveň signálu v Británii nízká. Navíc bylo pro přenos použito asi 25 různých frekvencí a někdy se měnily během přenosu jedné zprávy. Konkrétně k zachycení tohoto provozu byla v Ivy Farm Communications Center instalována Y stanice v Knockholtu, Sevenoaks , Kent [12] .

Jediný chybějící nebo zdeformovaný znak mohl znemožnit dekódování, proto byla vyžadována nejvyšší úroveň přesnosti příjmu signálu [12] . Technologie používaná k záznamu pulsů byla původně vyvinuta pro příjem Morseových zpráv vysokou rychlostí. Sekvence pulsů byla zaznamenána na úzkou papírovou pásku. Tato páska byla poté analyzována pracovníky Centra, kteří interpretovali vrcholy a poklesy jako symboly MTK2. Výsledné znaky byly naneseny na perforovanou papírovou pásku a telegraficky přeneseny do Bletchley Parku [13] .

Prolomit šifru

Ještě předtím, než Němci upustili od používání 12písmenného indexu, studoval Tunnyho šifry zkušený kryptoanalytik John Tiltman a dospěl k závěru, že k jejich vytvoření byla použita Vernamova šifra [14] .

Pokud dva přenosy ( a a b ) používají stejnou klávesu, pak po jejich sečtení efekt klíče úplně zmizí [15] . Podmíněně označme dva šifrové texty Za a Zb , klíč K a dva otevřené texty Pa a Pb . Pak dostaneme:

Za ⊕ Zb = Pa ⊕ Pb

Pokud je možné odvodit oba otevřené texty z jejich součtu, pak lze klíč získat z kterékoli ze dvou kombinací šifrovaného textu a otevřeného textu:

Za ⊕ Pa = K nebo
Zb ⊕ Pb = K

30. srpna 1941 byla z Athén do Vídně odeslána zpráva o 4500 znacích [11] . První pokus o přenos se nezdařil a přijímající operátor odeslal nešifrovaný požadavek na opakovaný přenos. Při opětovném odeslání zprávy udělal odesílající operátor chybu: poslal druhou zprávu pomocí stejného ukazatele jako poprvé, což bylo přísně zakázáno. Navíc při přepisování textu zprávy v něm udělal několik chyb a provedl řadu drobných změn, například nahradil některá slova zkratkami. Zaměstnanci Knockholt Communications Center, kteří zachytili zprávy i nešifrovaný požadavek na opětovné zaslání, si uvědomili jejich možnou důležitost a přenesli je do Bletchley Parku [11] .

V Bletchley Parku se John Tiltman a jeho tým pustili do rozluštění dvou šifrových textů a nalezení klíče. Prvních 15 znaků ze dvou zpráv bylo následujících:

Za JSH5N ZYZY5 GLFRG
Zb JSH5N ZYMFS/885I
Za ⊕ Zb ///// //FOU GFL4M

Tiltman dosadil různé části textu do součtu Za ⊕ Zb a zjistil, že otevřený text první zprávy začíná německým slovem SPRUCHNUMMER (číslo zprávy). Ve druhém otevřeném textu operátor použil běžnou zkratku NR pro NUMMER . Druhá zpráva obsahovala jiné zkratky a interpunkce se na některých místech lišila. To umožnilo Tiltmanovi získat otevřené texty obou zpráv za deset dní, protože sekvence znaků otevřeného textu nalezená v Pa umožnila se známým součtem Pa ⊕ Pb najít znaky otevřeného textu na stejných místech v Pb a naopak [16] . Vzhledem k oběma zdrojovým textům pak Tiltman dokázal najít více než 4000 znaků klíče [17] .

Poté výzkumné oddělení Bletchley Park zahájilo proces budování matematického modelu šifrovacího stroje založeného na nalezeném klíči. Po tři měsíce byly všechny jejich pokusy neúspěšné. V říjnu 1941 se William Tutt , který předtím učil chemii a matematiku na Trinity College , připojil k výzkumné sekci . K vyřešení problému použil metodu Kasiski , kterou se naučil v kurzech kryptografie. Podstata metody byla následující: klíčové symboly byly ručně napsány na list papíru, délky všech řádků byly stejné a odpovídaly předpokládané periodě opakování klíče. Pokud byla správně zvolena délka řádků, pak budou sloupce výsledné matice obsahovat více opakujících se znaků než obvykle. [osmnáct]

Tutt se domníval, že je lepší aplikovat tuto metodu ne na celé klíčové symboly, které by mohly mít velmi velkou periodu opakování, ale na samostatný puls, a tvrdil, že „ část může být kryptograficky jednodušší než celek “ [19] . Když si všiml, že indikátory Tunny používají 25 písmen (všechna písmena latinské abecedy kromě J) pro 11. pozici, ale pouze 23 písmen pro 12. pozici, použil metodu Kasiska na prvním pulzu (bitu) klíčových znaků s období 25*23=575. To nevedlo k velkému počtu opakování ve sloupcích, ale Tutt si všiml velkého množství opakování na úhlopříčkách. Znovu vypsal hodnoty prvního impulsu, ale s periodou 574. Tentokrát sloupce výsledné matice obsahovaly opakování. Uvědomil si, že prvočísla tohoto čísla jsou čísla 2, 7 a 41, opakoval postup s tečkou 41 symbolů a „ dostal obdélník teček a křížků, který byl plný opakování “ [20] .

Bylo však jasné, že první impuls klíče byl složitější než impuls generovaný pouze jedním diskem se 41 pozicemi [21] . Složka hybnosti vytvořená takovým diskem, který Tutt nazývá (" chi "). Zjistil, že existuje i druhá složka, se kterou přidal modulo 2. Druhá složka se při přechodu na další symbol ne vždy změnila a byla vytvořena diskem, který Tatt nazval („ psi “). Totéž se stalo s každým z pěti pulzů symbolu klíče. Pro jeden znak se klíč K skládal ze dvou složek:

K = ⊕ .

Skutečná sekvence znaků přidaných psi disky , včetně těch znaků, kde disky nezměnily pozici, se nazývala rozšířená psi [22] a byla označena jako

K = ⊕ ' .

Tatomova derivace složky psi byla umožněna tím, že tečky byly spíše následovány tečkami a křížky byly s největší pravděpodobností následovány křížky. Bylo to kvůli chybě v postupu nastavení klíče, kterou Němci následně opustili. Jakmile Tutt učinil tento průlom, přidal se k němu zbytek výzkumného oddělení, aby prostudoval zbytek impulsů [23] . Během následujících dvou měsíců, až do ledna 1942, byli pracovníci výzkumného oddělení schopni reprodukovat kompletní logickou strukturu šifrovacího stroje [24] .

Tattova analýza struktury Tunni byla úžasným úspěchem v kryptoanalýze, a když Tat obdržel Řád Kanady , byla popsána jako „ jeden z velkých intelektuálních úspěchů druhé světové války “ [25] .

Poté, co byl Tunny hacknut, byl zorganizován specializovaný tým kryptoanalytiků vedený Ralphem Testerem a stal se známým jako Testery. Úkolem tohoto týmu bylo přímo dešifrovat zachycené zprávy. Pomáhaly jim v tom stroje postavené v oddělení pod vedením Maxe Newmana známého jako Newmanry .

Dešifrovací stroje

V prosinci 1942 bylo pod vedením Maxe Newmana vytvořeno nové oddělení, jehož úkolem bylo studovat možnosti automatizace procesu dešifrování Tunny zpráv. Předtím Newman spolupracoval s Harrym Morganem, šéfem výzkumné divize, na Tunnyho hacku. V listopadu 1942 jim William Tutt představil nápad na metodu, která by se stala známou jako „vloupání 1+2“ [27] . Bylo zjištěno, že metoda je účinná, ale pouze při použití automatizace.

Heath Robinson

Pro automatizaci metody přerušení 1+2 napsal Newman funkční specifikaci, ze které byl postaven stroj Heath Robinson. Stroj postavili inženýři Frank Morell [28] , Tommy Flowers a C. E. Wynn-Williamson [29] . Proces vzniku začal v lednu 1943, v červnu téhož roku byl prototyp stroje již použit v Bletchley Parku k rozluštění zpráv „Tunni“ [30] .

Hlavní části „Heath Robinson“ byly:

  • Mechanismus čtečky, jehož prostřednictvím byly spouštěny pásky s klíčem a zprávou rychlostí 1 000 a 2 000 znaků za sekundu.
  • Blok, který implementoval logiku metody William Tut.
  • Počítadlo zpracovaných znaků.

Prototyp vozu se ukázal jako účinný i přes vážné nedostatky, z nichž většina byla v následujících verzích odstraněna. [31]

Kolos

S využitím zkušeností získaných při stavbě „Heath Robinson“ a minulých zkušeností s elektronkami dospěl Tommy Flowers k závěru , že je možné postavit efektivnější stroj založený na elektronice. Místo perforované papírové pásky bylo možné pro zadávání klíčových znaků použít elektrický signál, což bylo mnohem rychlejší a zpracování bylo mnohem flexibilnější. Flowersův návrh na podobný stroj nebyl zpočátku podporován v Bletchley Park, kde se zdálo, že by byl „příliš nespolehlivý pro užitečnou práci“. Získal ale podporu vedoucího výzkumu na výzkumné stanici Doris Hill Gordona Radleyho [32] a mohl svůj nápad zrealizovat. Výsledkem jeho práce byl první počítač na světě, Colossus . Celý proces tvorby trval rekordně krátkou dobu – pouhých deset měsíců [33] .

Hlavní části počítače Colossus byly [34] :

  • Čtečka znaků papírové pásky schopná zpracovat 5000 znaků za sekundu.
  • Blok, který převáděl čtenou sekvenci do elektronické podoby.
  • Pět paralelních výpočetních jednotek, z nichž každá může být naprogramována k provádění velkého množství typů logických operací .
  • Pět čítačů zpracovaných znaků.

Pět paralelních výpočetních jednotek umožňovalo „vniknutí 1 + 2“ a další funkce provádět skutečnou rychlostí 25 tisíc znaků za sekundu. Stejně jako počítač ENIAC vytvořený v roce 1946 neměl Colossus žádnou programovou paměť a byl programován pomocí ovládacího panelu. [35] Byl rychlejší a spolehlivější než stroje z rodiny Robinsonů, které mu předcházely, což umožnilo značně urychlit proces hledání nastavení diskových chi. Správa Bletchley Park, která byla zpočátku skeptická k myšlence Flowers, ho ihned po testování prvního vozu začala přesvědčovat, aby postavil další kopii.

Do konce války bylo postaveno celkem 10 počítačů Colossus. [36] Po skončení války byla většina demontována na příkaz Winstona Churchilla , ale vládnímu komunikačnímu centru se podařilo ponechat dvě kopie.

Speciální vozidla

Kromě komerčně vyráběných dálnopisů a děrných kopírovacích strojů byla v Bletchley Park postavena řada strojů pro usnadnění procesu přípravy a kontroly děrných pásek v odděleních Newman a Tester [37] [38] .

Viz také

Poznámky

  1. Hinsley, 1993 , s. 141
  2. Hinsley, 1993 , s. 142
  3. 1 2 3 Good, Michie & Timms, 1945 , str. 10 Německý tuňák
  4. Klein, , str. 2
  5. Klein, , str. 3
  6. prodej,
  7. 1 2 3 Good, Michie & Timms, 1945 , str. 7 Německý tuňák
  8. Good, Michie & Timms, 1945 , str. 8 Německý tuňák
  9. Kostelní dům, 2002 , str. 158
  10. Good, Michie & Timms, 1945 , str. 14 Německý tuňák
  11. 1 2 3 Prodej, , Německá chyba
  12. 1 2 Good, Michie & Timms, 1945 , str. 281 Knockholt
  13. Gannon, 2007 , str. 333.
  14. Prodej, , První zachycení
  15. Tutte, 2006 , str. 353.
  16. Copeland, 2010 .
  17. Tutte, 1998 , str. čtyři.
  18. Tutte, 2006 , str. 348.
  19. Tutte, 2006 , str. 356.
  20. Tutte, 2006 , str. 357.
  21. Tutte, 2006 , str. 358.
  22. Good, Michie & Timms, 1945 , str. 7 Úvod: 11 German Tunny, 11B The Tunny Cipher Machine, (e) Psi-key
  23. Tutte, 2006 , str. 361.
  24. Prodej, , Rozuzlení
  25. O'Connor, JJ & Robertson, EF (2003), MacTutor Biografie: William Thomas Tutte , University of St Andrews , < http://www-history.mcs.st-and.ac.uk/Biographies/Tutte.html > . Získáno 28. dubna 2013. Archivováno 17. června 2016 na Wayback Machine 
  26. Roberts, 2009
  27. Good, Michie & Timms, 1945 , str. 33 Některé historické poznámky: 15A. První fáze vývoje strojů
  28. Národní kódové centrum Bletchley Park: listopad 1943 , < http://www.bletchleypark.org.uk/content/archive/nov1943.rhtm > . Získáno 21. listopadu 2012. Archivováno 23. října 2017 na Wayback Machine 
  29. Good, Michie & Timms, 1945 , str. 33 Některé historické poznámky: 15A. První fáze vývoje strojů, (c) Heath Robinson
  30. Good, Michie & Timms, 1945 , str. 290 Organizace nastavení strojů: (b) Robinsons and Colossi
  31. Good, Michie & Timms, 1945 , str. 328 Vývoj Robinsona a Colossa: (b) Heath Robinson
  32. Fensom, 2006 , str. 300–301.
  33. Květiny, 2006 , str. 80.
  34. Květiny, 1983 , pp. 245-252.
  35. Good & Michie, 1992
  36. Květiny, 1983 , s. 247.
  37. Good, Michie & Timms, 1945 , str. 25 Stroje: 13A Vysvětlení kategorií
  38. Good, Michie & Timms, 1945 , str. 36756 Kopírovací stroje

Odkazy