Kryptoanalýza Lorenzovy šifry - Cryptanalysis of the Lorenz cipher

Kryptanalýza Lorenzovy šifry byl proces, který umožnil Britům během druhé světové války číst zprávy německé armády na vysoké úrovni . Britský vládní zákoník a Cypher School (GC&CS) v Bletchley Parku dešifrovaly mnoho komunikací mezi Oberkommando der Wehrmacht (OKW, německé vrchní velení) v Berlíně a jejich armádními veleními po okupované Evropě, z nichž některé byly podepsány „Adolf Hitler, Führer“. Jednalo se o zachycené rádiové přenosy jiných než Morseových signálů, které byly zašifrovány šifrovacími přílohami proudového rotoru Lorenz SZ dálnopisného rotoru . Dešifrování tohoto provozu se stalo důležitým zdrojem „ ultra “ inteligence, která významně přispěla k vítězství spojenců.

Pro své tajné zprávy na vysoké úrovni, německé ozbrojené služby zašifroval každý znak pomocí různých online Geheimschreiber (tajné spisovatel) proud šifrovací stroje na obou koncích telegrafní spojení s použitím 5-bitový mezinárodní telegrafie abeceda č.2 (ITA2). Tyto stroje byly následně objeveny jako Lorenz SZ (SZ pro Schlüssel-Zusatz , což znamená „šifrovací připevnění“) pro armádu, Siemens a Halske T52 pro letectvo a Siemens T43, který byl málo používaný a nikdy nebyl rozbit Spojenci.

Bletchley Park dešifruje zprávy zašifrované pomocí strojů Enigma odhalilo, že Němci nazývali jeden ze svých přenosových systémů bezdrátových dálnopisů „Sägefisch“ ( sawfish ), což vedlo britské kryptografy k označení šifrovaného německého radiotelegrafického provozu jako „ Fish “. „ Tunny “ (tuňák) byl název pro první odkaz, který nepocházel z Morse, a následně byl použit pro šifrovací stroje a jejich provoz.

Stejně jako u zcela oddělené kryptoanalýzy Enigmy to byly německé provozní nedostatky, které umožnily počáteční diagnostiku systému a cestu k dešifrování. Na rozdíl od Enigmy žádný fyzický stroj nedosáhl spojeneckých rukou až do samého konce války v Evropě, dlouho poté, co byla zavedena velkoobchodní dešifrování. Problémy s dešifrováním tuňáckých zpráv vedly k vývoji „ Colossus “, prvního elektronického, programovatelného digitálního počítače na světě, z nichž deset bylo používáno do konce války, kdy bylo dešifrováno přibližně 90% vybraných tuňáckých zpráv v Bletchley Parku.

Albert W. Small, kryptoanalytik z amerického armádního signálního sboru, který byl přidělen do Bletchley Parku a pracoval na Tunny, ve své zprávě z prosince 1944 zpět do Arlington Hall řekl, že:

Denní řešení zpráv Fish na GC&CS odrážejí pozadí britského matematického génia, vynikajících technických schopností a zdravého rozumu. Každý z nich byl nezbytným faktorem. Každý mohl být příliš zdůrazňován nebo podhodnocen na úkor řešení; pozoruhodným faktem je, že fúze prvků byla zjevně v dokonalém poměru. Výsledkem je vynikající příspěvek ke kryptoanalytické vědě.

Německé stroje Tunny

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á	J.	K	L
Název kola BP	${\ Displaystyle \ psi}$1	${\ Displaystyle \ psi}$2	${\ Displaystyle \ psi}$3	${\ Displaystyle \ psi}$4	${\ Displaystyle \ psi}$5	${\ Displaystyle \ mu}$37	${\ Displaystyle \ mu}$61	${\ displaystyle \ chi}$1	${\ displaystyle \ chi}$2	${\ displaystyle \ chi}$3	${\ displaystyle \ chi}$4	${\ displaystyle \ chi}$5
Počet vaček (kolíků)	43	47	51	53	59	37	61	41	31	29	26	23

Šifrovací přílohy Lorenz SZ implementovaly šifru Vernam stream , využívající komplexní řadu dvanácti kol, která jako klíčový proud poskytovala to, co mělo být kryptograficky zabezpečené pseudonáhodné číslo . Tok klíčů byl spojen s prostým textem za vzniku šifrového textu na vysílacím konci pomocí funkce exclusive nebo (XOR) . Na přijímacím konci identicky konfigurovaný stroj produkoval stejný tok klíčů, který byl kombinován s šifrovacím textem za vzniku prostého textu, tj. Systém implementoval algoritmus symetrických klíčů .

Klíčový proud generovalo deset z dvanácti kol. Jednalo se o produkt XOR-ing 5bitového znaku generovaného pravými pěti koly, koly chi ( ) a levou rukou, koly psi ( ). Tyto chi kola vždy posune o jednu pozici za každou příchozí ciphertext charakteru, ale psi kola ne. ${\ displaystyle \ chi}$${\ Displaystyle \ psi}$

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

Centrální dvě mu ( ) nebo „motorová“ kola určovala, zda se kola psi otáčí s novým znakem. Po zašifrování každého písmene se buď všech pět psi kol posunulo, nebo zůstalo nehybných a bylo znovu použito stejné písmeno psi-klíče. Stejně jako kola chi se kolo ₆₁ posunulo dále po každé postavě. Když ₆₁ měla vačku v aktivní poloze a tak generovala x (před pohybem) ₃₇ se jednou posunula: když byla vačka v neaktivní poloze (před pohybem) ₃₇ a psi kola zůstala nehybná. Na všech strojích kromě nejstarších existoval další faktor, který hrál v pohybu na kolečkách psi nebo ne . Jednalo se o čtyři různé typy a v Bletchley Parku se jim říkalo „Omezení“. Všechny zahrnovaly určitý aspekt předchozích poloh kol stroje. ${\ Displaystyle \ mu}$${\ Displaystyle \ mu}$${\ Displaystyle \ mu}$${\ Displaystyle \ mu}$${\ Displaystyle \ mu}$

Počty vaček na soubor dvanácti koly SZ42 strojů činily 501 a byly ko-prime navzájem, což mimořádně dlouhou dobu, než klíčové sekvence se opakuje. Každá vačka může být buď ve zvýšené poloze, v takovém případě přispěla x k logice systému, obrátením hodnoty bitu, nebo ve snížené poloze, v takovém případě generovala • . Celkový možný počet vzorů vyvýšených vaček byl 2 ^501, což je astronomicky velké číslo. V praxi však byla asi polovina vaček na každém kole ve zvednuté poloze. Později si Němci uvědomili, že pokud by počet zvednutých vaček nebyl příliš blízko 50%, došlo by k běhům x s a • s, což je kryptografická slabost.

Proces zjišťování, které z 501 vaček byly ve zvednuté poloze, se v Bletchley Parku nazývalo „rozbití kola“. Odvození počátečních poloh kol pro konkrétní převodovku se nazývalo „nastavení kola“ nebo jednoduše „nastavení“. Skutečnost, že se kola psi pohybovala společně, ale ne s každou vstupní postavou, byla hlavní slabinou strojů, které přispěly k britskému kryptanalytickému úspěchu.

Šifrovací stroj Lorenz SZ42 s odstraněnými kryty v Národním muzeu výpočetní techniky v Bletchley Parku

Bezpečná telegrafie

Elektromechanická telegrafie byla vyvinuta ve třicátých a čtyřicátých letech 19. století, tedy ještě před telefonováním , a v době druhé světové války fungovala po celém světě . Rozsáhlý systém propojených kabelů v rámci zemí i mezi nimi se standardním napětím −80 V označujícím „značku“ a +80 V označujícím „mezeru“. Tam, kde se kabelový přenos stal neproveditelným nebo nepohodlným, například pro mobilní jednotky německé armády, byl použit rádiový přenos.

Dálnopisky na každém konci obvodu sestávaly z klávesnice a tiskového mechanismu a velmi často z mechanismu pro čtení a děrování děrované papírové pásky s pěti otvory . Při použití online způsobí stisknutí abecední klávesy na vysílacím konci tisk příslušného znaku na přijímacím konci. Běžně však komunikační systém zahrnoval vysílajícího operátora, který připravil sadu zpráv offline jejich vyražením na papírovou pásku a poté připojením online pouze pro přenos zpráv zaznamenaných na pásku. Systém by obvykle odesílal asi deset znaků za sekundu, a tak zabíral linku nebo rozhlasový kanál na kratší dobu než pro online psaní.

Znaky zprávy byly reprezentovány kódy mezinárodní telegrafické abecedy č. 2 ( ITA2 ). Přenosové médium, buď drátové nebo rádiové, používalo asynchronní sériovou komunikaci s každým znakem signalizovaným startovacím (mezerovým) impulzem, 5 datovými impulsy a 1½ stop (označení) impulzů. V Bletchley Parku byly impulsy značky označeny x(„křížem“) a vesmírné impulsy •(„tečkou“). Například písmeno „H“ bude kódováno jako ••x•x.

Znaky posunu obrázku (OBRÁZKY) a posunu písmene (LETRS) určovaly, jak přijímající konec interpretoval řetězec znaků až do dalšího znaku posunu. Kvůli nebezpečí poškození znaku posunu by někteří operátoři při přechodu z písmen na čísla nebo naopak zadali dvojici znaků posunu . Takže by zadali 55M88, aby představovali tečku. Takové zdvojnásobení postav bylo velmi užitečné pro statistickou kryptoanalýzu používanou v Bletchley Parku. Po zašifrování neměly posunovací znaky žádný zvláštní význam.

Rychlost přenosu radiotelegrafní zprávy byla třikrát nebo čtyřikrát vyšší než v Morseově abecedě a lidský posluchač ji nedokázal interpretovat. Standardní dálnopis by však vytvořil text zprávy. Lorenzova šifrovací příloha změnila prostý text zprávy na šifrový text, který byl pro ty, kteří neměli identicky nastavený identický stroj, neproveditelný. S touto výzvou se potýkali lámači kódů Bletchley Park.

Zachycení

Zachytávání přenosů Tunny představovalo podstatné problémy. Protože vysílače byly směrové, většina signálů byla u přijímačů v Británii docela slabá. Kromě toho se pro tyto přenosy používalo přibližně 25 různých frekvencí a frekvence se někdy částečně změnila. Po počátečním objevu nemorseovských signálů v roce 1940 byla na kopci na Ivy Farm v Knockholt v Kentu zřízena rozhlasová záchytná stanice s názvem Foreign Office Research and Development Establishment , konkrétně k zachycení tohoto provozu. V čele centra stál Harold Kenworthy, mělo 30 přijímacích souprav a zaměstnávalo asi 600 zaměstnanců. To začalo být plně funkční na začátku roku 1943.

Délka pásky, široká 12 milimetrů (0,47 palce), vyrobená zvlněním podobným těm, které se používaly během druhé světové války pro zachycený bezdrátový telegrafický provoz v Knockholtu s „tunou“, pro překlad do znaků ITA2, které mají být odeslány do Bletchley Parku

Protože jeden zmeškaný nebo poškozený znak mohl znemožnit dešifrování, byla vyžadována největší přesnost. Technologie zvlnění používaná k zaznamenávání impulsů byla původně vyvinuta pro vysokorychlostní Morse. Vytvářel viditelný záznam impulsů na úzké papírové kazetě. To pak přečetli lidé zaměstnaní jako „čtenáři skluzu“, kteří vrcholy a koryta interpretovali jako značky a mezery postav ITA2. Poté byl vyroben perforovaný papírový pásek pro telegrafický přenos do Bletchley Parku, kde byl vyražen.

Šifra Vernam

Šifra Vernam implementovaná stroji Lorenz SZ využívá booleovskou funkci „exclusive“ nebo „(XOR) , symbolizovanou ⊕ a verbalizovanou jako„ A nebo B, ale ne obojí “. To je znázorněno v následující tabulce pravdivosti , kde x představuje „true“ a • představuje „false“.

Další názvy této funkce jsou: exkluzivní disjunkce, nerovná se (NEQ) a sčítání modulo 2 (bez „carry“) a odčítání (bez „půjčit“). Sčítání a odčítání modulu 2 je totožné. Některé popisy dešifrování Tunny se týkají sčítání a některé rozlišování, tj. Odčítání, ale znamenají totéž. Operátor XOR je asociativní i komutativní .

Reciprocita je žádoucí vlastností strojové šifry, takže stejný stroj se stejným nastavením lze použít buď k šifrování, nebo k dešifrování. Šifra Vernam toho dosahuje, protože kombinace proudu znaků prostého textu s proudem klíčů vytváří šifrový text a kombinace stejného klíče s šifrovým textem regeneruje prostý text.

Symbolicky:

Plaintext ⊕ Key = Ciphertext

a

Šifrovací text ⊕ Klíč = prostý text

Vernamova původní myšlenka byla použít konvenční telegrafickou praxi s papírovou páskou prostého textu kombinovanou s papírovou páskou klíče na vysílacím konci a identickou klíčovou páskou spojenou se signálem šifrového textu na přijímacím konci. Každý pár klíčových pásek by byl 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 šifrovací stroje rotorů Vernam k produkci proudu klíčů, který měl působit místo pásku s klíči. Lorenz SZ40/42 byl jedním z nich.

Bezpečnostní funkce

Typická distribuce písmen v textu v anglickém jazyce . Nedostatečné šifrování nemusí dostatečně maskovat nejednotnou povahu distribuce. Tato vlastnost byla využita při kryptoanalýze Lorenzovy šifry oslabením části klíče.

Monoalphabetic substituční kód , jako je například Caesar šifry lze snadno rozdělit, vzhledem k tomu, přiměřené množství ciphertext. Toho je dosaženo frekvenční analýzou různých písmen šifrového textu a porovnáním výsledku se známým rozdělením frekvence písmen prostého textu.

U polyalfabetické šifry existuje pro každý následující znak jiná substituční abeceda. Frekvenční analýza tedy ukazuje přibližně rovnoměrné rozložení , jaké bylo získáno z (pseudo) generátoru náhodných čísel . Protože se však jedna sada Lorenzových kol otáčela s každou postavou, zatímco druhá ne, stroj nezakryl vzor použití sousedních znaků v německém holém textu. Alan Turing objevil tuto slabost a vynalezl níže popsanou diferenciační techniku, aby ji využil.

Vzor, který z vaček byl ve zvednuté poloze, a který ve snížené poloze byl denně měněn na motorových kolech ( 37 a 61). Tyto chi kola vačky vzory byly původně změnil měsíčně. Tyto psi vzory kol se změnily čtvrtletní až do října 1942, kdy se frekvence zvýší na měsíční, a pak denně od 1. srpna 1944, kdy se frekvence mění chi vzory kol se také změnil na denní. ${\ Displaystyle \ mu}$${\ Displaystyle \ mu}$

Počet počátečních poloh kol byl 43 × 47 × 51 × 53 × 59 × 37 × 61 × 41 × 31 × 29 × 26 × 23, což je přibližně 1,6 × 10 ¹⁹ (16 miliard miliard), což je příliš velké číslo. aby kryptoanalytici vyzkoušeli vyčerpávající „ útok hrubou silou “. Někdy operátoři společnosti Lorenz neuposlechli pokynů a dvě zprávy byly vyslány se stejnými počátečními polohami, což je jev nazývaný „hloubka“ . Způsob, kterým vysílající operátor sdělil přijímajícímu operátorovi nastavení kola, které zvolil pro zprávu, kterou se chystal vysílat, se v Bletchley Parku nazývala „indikátor“ .

V srpnu 1942 byly formulační zprávy, které byly užitečné pro kryptoanalytiky, nahrazeny nějakým irelevantním textem, což trochu ztížilo identifikaci skutečné zprávy. Tento nový materiál byl v Bletchley Parku nazván quatsch (německy „nesmysl“).

Během fáze experimentálních převodovek se indikátor skládal z dvanácti německých křestních jmen, jejichž počáteční písmena označovala polohu, do které operátoři otočili dvanácti koly. Kromě toho, že ukazoval, kdy byly dva převodovky plně v hloubce, umožnil také identifikaci dílčích hloubek, kde se dva ukazatele lišily pouze v poloze jednoho nebo dvou kol. Od října 1942 se systém indikátorů změnil na odesílajícího operátora přenášejícího nešifrovaná písmena QEP následovaná dvouciferným číslem. Toto číslo bylo převzato sériově z číselníku, který byl vydán oběma operátorům, a pro každé číslo QEP udával nastavení dvanácti kol. Knihy byly nahrazeny, když byly spotřebovány, ale mezi výměnami byly úplné hloubky identifikovány opětovným použitím čísla QEP na konkrétním odkazu Tunny.

Diagnóza

Prvním krokem při prolomení nové šifry je diagnostikovat logiku procesů šifrování a dešifrování. V případě strojové šifry, jako je Tunny, to znamenalo vytvoření logické struktury a tím i fungování stroje. Toho bylo dosaženo bez výhody vidět stroj - což se stalo pouze v roce 1945, krátce před spojeneckým vítězstvím v Evropě. Šifrovací systém velmi dobře zajišťoval, že šifrový text Z neobsahoval žádné statistické, periodické nebo lingvistické charakteristiky, které by jej odlišovaly od náhodných. To však neplatilo pro K , χ , ψ ' a D , což byla slabina, která znamenala, že klíče Tunny bylo možné vyřešit.

Během experimentálního období přenosů Tunny, když byl používán dvanáctipísmenný indikátorový systém, John Tiltman , veterán Bletchley Parka a pozoruhodně nadaný kryptanalyzátor, studoval šifrovací kontexty Tunny a zjistil, že používají Vernamovu šifru.

Když dva přenosy ( a a b ) používají stejný klíč, tj. Jsou do hloubky, jejich kombinace eliminuje účinek klíče. Nazvěme dva šifrovací texty Za a Zb , klíč K a dva prosté texty Pa a Pb . Pak máme:

Za ⊕ Zb = Pa ⊕ Pb

Pokud lze zpracovat dva holé texty, lze klíč obnovit z dvojice ciphertext-holý text, např .:

Za ⊕ Pa = K nebo
Zb ⊕ Pb = K

Dne 31. srpna 1941 byly přijaty dvě dlouhé zprávy, které měly stejný indikátor HQIBPEXEZMUG. Prvních sedm znaků těchto dvou šifrových textů bylo stejných, ale druhá zpráva byla kratší. Prvních 15 znaků těchto dvou zpráv bylo následující (v interpretaci Bletchley Park):

John Tiltman zkoušel proti řetězci Za ⊕ Zb různé pravděpodobné kousky prostého textu, tj. „Betlémy“ , a zjistil, že první textová zpráva začala německým slovem SPRUCHNUMMER (číslo zprávy). Ve druhém prostém textu operátor použil běžnou zkratku NR pro NUMMER . Ve druhé zprávě bylo více zkratek a interpunkce se někdy lišila. To umožnilo Tiltmanovi zpracovat během deseti dnů prostý text obou zpráv, jako posloupnost znaků prostého textu objevených v Pa , pak bylo možné vyzkoušet proti Pb a naopak . To zase přineslo téměř 4000 znaků klíče.

Členové výzkumné sekce pracovali na tomto klíči, aby se pokusili odvodit matematický popis procesu generování klíče, ale neúspěšně. Bill Tutte vstoupil do sekce v říjnu 1941 a dostal za úkol. Než byl přijat do Bletchley Parku, četl chemii a matematiku na Trinity College v Cambridgi . Na jeho výcvikovém kurzu ho naučili Kasiskiho vyšetřovací techniku vypsání klíče na čtvercový papír s novou řadou po definovaném počtu znaků, u nichž bylo podezření, že se jedná o frekvenci opakování klíče. Pokud by toto číslo bylo správné, sloupce matice by ukazovaly více opakování sekvencí znaků než samotná náhoda.

Tutte si myslel, že je možné, že namísto použití této techniky na celá písmena klíče, u nichž bylo pravděpodobné, že budou mít dlouhou frekvenci opakování, by možná stálo za to to vyzkoušet na sekvenci vytvořené odebráním pouze jednoho impulsu (bitu) z každého písmene s odůvodněním, že „ část může být kryptograficky jednodušší než celá “. Vzhledem k tomu, že indikátory Tunny používaly 25 písmen (kromě J) pro 11 pozic, ale pouze 23 písmen pro dvanácté, zkusil Kasiskiho techniku ​​na první impuls klíčových postav pomocí opakování 25 × 23 = 575. To se stalo nevytváří ve sloupcích velký počet opakování, ale Tutte tento jev pozoroval na diagonále. Zkusil to tedy znovu s 574, což ukázalo opakování ve sloupcích. Uznává, že prvotními faktory tohoto čísla jsou 2, 7 a 41, zkusil to znovu s periodou 41 a „ získal obdélník bodů a křížů, který byl plný opakování “.

Bylo však jasné, že sled prvních impulzů byl komplikovanější než sled produkovaný jediným kolem 41 pozic. Tutte nazval tuto složku klíče χ ₁ ( chi ). Došlo mu, že existuje ještě jedna součást, která byla s tímto XOR-ed, která se ne vždy měnila s každou novou postavou, a že to byl produkt kola, kterému říkal ψ ₁ ( psi ). To samé platilo pro každý z pěti impulsů - zde označených předplatnými. Pro jeden znak tedy klíč K sestával ze dvou složek:

K = χ ⊕ ψ .

Skutečná posloupnost znaků přidaná koly psi , včetně těch, které nepostupují, byla označována jako rozšířená psi a symbolizována ψ ′

K = χ ⊕ ψ ′ .

Tutte je odvození v | složky byl umožněn tím, že tečky byly více než pravděpodobné, je třeba se řídit tečkami, a kříže pravděpodobné, je třeba se řídit křížky. To byl výsledek slabosti německého klíčového nastavení, které později zastavili. Jakmile Tutte udělal tento průlom, připojil se zbytek výzkumné sekce, aby studoval další impulsy, a bylo zjištěno, že pět ψ kol se pohybovalo společně pod kontrolou dvou μ ( mu nebo „motorových“) kol.

Diagnostika fungování stroje Tunny tímto způsobem byla skutečně pozoruhodným kryptoanalytickým úspěchem a byla popsána, když byl Tutte v říjnu 2001 uveden jako důstojník Řádu Kanady, jako „ jeden z největších intelektuálních počinů druhé světové války “.

Turingery

V červenci 1942 Alan Turing strávil několik týdnů v sekci výzkumu. Začal se zajímat o problém rozbití Tunnyho z klíčů, které byly získány z hlubin. V červenci vyvinul způsob odvození nastavení vačky („rozbití kola“) z délky klíče. Stala se známá jako „Turingery“ (Peter Ericsson, Peter Hilton a Donald Michie hravě nazvaná „Turingismus“ ) a představila důležitou metodu „diferenciace“, na které byla založena většina zbytku řešení klíčů Tunny v nepřítomnosti hloubek. .

Rozdíl

Hledal se proces, který by manipuloval s šifrovacím textem nebo klíčem za účelem vytvoření frekvenčního rozložení znaků, které se odchýlilo od uniformity, které bylo cílem šifrovacího procesu dosáhnout. Turing vypracoval, že kombinace hodnot XOR hodnot po sobě jdoucích (sousedících) znaků v proudu ciphertextu nebo klíče zdůraznila jakékoli odchylky od jednotného rozdělení. Výsledný proud se nazýval rozdíl (symbolizovaný řeckým písmenem „delta“ Δ ), protože XOR je stejné jako odčítání modulo 2. Takže pro proud znaků S byl rozdíl ΔS získán následujícím způsobem, kde podtržítko označuje následující znak:

ΔS = S ⊕ S

Tok S může být šifrový text Z , prostý text P , klíč K nebo některá z jeho dvou složek χ a ψ . Vztah mezi těmito prvky stále platí, když se liší. Například také:

K = χ ⊕ ψ

Je to tak, že:

ΔK = Δ χ ⊕ Δ ψ

Podobně pro šifrový text, prostý text a klíčové komponenty:

ΔZ = ΔP ⊕ Δ χ ⊕ Δ ψ

Tak:

ΔP = ΔZ ⊕ Δ χ ⊕ Δ ψ

Důvodem, že diferenciace poskytla cestu do Tunny, bylo to, že ačkoli frekvenční rozdělení znaků v šifrovacím textu nelze odlišit od náhodného proudu, totéž neplatilo pro verzi šifrového textu, ze které měl chi prvek klíče byly odstraněny. Důvodem je to, že tam, kde prostý text obsahoval opakující se znak a psi kola se nepohybovala, bude rozdílný znak psi ( Δ ψ ) znakem null (' / ' v Bletchley Parku). Když XOR-ed s jakýmkoli znakem, tento znak nemá žádný účinek, takže za těchto okolností ΔK = Δ χ . Ciphertext modifikovány odstraněním chi složky klíče se nazývá de- chi D v Bletchley parku, a proces odstraňování jako „de- chi ing“. Podobně pro odstranění psi složky, která byla známá jako „de- psi ing“ (nebo „hluboké vzdychání“, když to bylo velmi obtížné).

Takže delty vý- chi ód byl:

ΔD = ΔZ ⊕ Δ χ

Opakované znaky v otevřeném textu byly častější jak kvůli vlastnostem němčiny (EE, TT, LL a SS jsou relativně běžné), tak proto, že telegrafisté často opakovali znaky s posunem čísla a písmena jako jejich ztrátu v běžném telegrafním přenosu může vést k blábolení.

Citovat obecnou zprávu o Tunny:

Turingery zavedl zásadu, že klíč odlišný od jednoho, nyní nazývaného ΔΚ , může poskytnout informace, které nelze získat z běžného klíče. Tento princip Δ měl být základem téměř všech statistických metod rozbíjení kol a nastavení.

Na každý z impulsů kódovaných znaků ITA2 bylo aplikováno rozlišení. Takže pro první impuls, který byl zašifrován koly χ ₁ a ψ ₁ , se lišil v jednom:

ΔK ₁ = K ₁ ⊕ K ₁

A pro druhý impuls:

ΔK ₂ = K ₂ ⊕ K ₂

A tak dále.

Periodicita kol chi a psi pro každý impuls (41 respektive 43 pro první impuls) se také odráží ve vzoru ΔK . Avšak vzhledem k tomu, že psi psi nepostupovala pro každý vstupní znak, stejně jako chi kola, nešlo jen o opakování vzoru každých 41 × 43 = 1763 znaků pro ΔK ₁ , ale o složitější sekvenci.

Turingova metoda

Turingova metoda odvození nastavení vaček kol z délky klíče získaného z hloubky zahrnovala iterační proces. Vzhledem k tomu, že delta psi byl průměrně nulový znak ' / ' polovinu času, předpoklad, že ΔK  =  Δ χ měl 50% šanci, že bude správný. Proces začal ošetřením konkrétního znaku ΔK jako Δ χ pro danou pozici. Výsledný domnělý bitový vzor x a • pro každé chi kolo byl zaznamenán na list papíru, který obsahoval tolik sloupců, kolik znaků bylo v klíči, a pět řádků představujících pět impulsů Δ χ . Vzhledem k znalostem z Tutteho práce o periodicitě každého z kol to umožnilo šíření těchto hodnot na příslušných pozicích ve zbytku klíče.

Připravena byla také sada pěti listů, po jednom pro každé chi kolečko. Ty obsahovaly sadu sloupců odpovídajících počtu vaček pro příslušné kolo chi a byly označovány jako „klec“. Takže χ ₃ klec měla 29 těchto sloupů. Po sobě jdoucí „odhady“ hodnot Δ χ pak vytvořily další domnělé hodnoty stavu vačky. Mohou buď souhlasit, nebo nesouhlasit s předchozími předpoklady, a na těchto listech byla učiněna řada dohod a nesouhlasů. Tam, kde neshody podstatně převažovaly nad dohodami, byl učiněn předpoklad, že znak Δ ψ nebyl znakem null ' / ', takže příslušný předpoklad byl diskontován. Postupně byla odvozena všechna nastavení vačky kol chi a z nich nastavení vačky psi a motorového kola.

Jak se zkušenosti s touto metodou vyvinuly, byla provedena vylepšení, která umožnila její použití s ​​mnohem kratšími délkami klíče než původních 500 znaků. "

Testery

Testery byla sekce v Bletchley Parku, která vykonávala většinu práce spojené s dešifrováním zpráv Tunny. V červenci 1942 se objem dopravy značně zvyšoval. Byla proto zřízena nová sekce vedená Ralphem Testerem - odtud název. Zaměstnanci se skládali převážně z bývalých členů výzkumné sekce a byli mezi nimi Peter Ericsson, Peter Hilton , Denis Oswald a Jerry Roberts . Metody Testery byly téměř výhradně manuální, a to jak před, tak po zavedení automatizovaných metod do Newmanry, které doplňovaly a urychlovaly jejich práci.

První fáze práce Testery probíhala od července do října, přičemž převládající metoda dešifrování byla založena na hloubkách a částečných hloubkách. Po deseti dnech však byl vzorový začátek zpráv nahrazen nesmyslným quatschem , což dešifrování ztížilo. Toto období bylo přesto produktivní, i když každé dešifrování trvalo značný čas. Nakonec byla v září přijata hloubka, která umožnila použít Turingovu metodu rozbíjení kol „ Turingery “, což vedlo k možnosti začít číst aktuální provoz. Byla sestavena rozsáhlá data o statistických charakteristikách jazyka zpráv a rozšířena sbírka betlémů.

Na konci října 1942 bylo původní experimentální spojení Tunny uzavřeno a byla otevřena dvě nová spojení (Codfish a Octopus). S těmito a následujícími odkazy byl nahrazen 12písmenný indikátorový systém určující klíč zprávy systémem QEP. To znamenalo, že byly rozpoznávány pouze úplné hloubky - ze stejných čísel QEP - což vedlo ke značnému snížení provozu dešifrovaného.

Jakmile byla Newmanry uvedena do provozu v červnu 1943, změnila se povaha práce prováděné ve zkušebně, dešifrování a rozbíjení kol již nespoléhalo na hloubky.

Britský tuňák

Přestavěný British Tunny v Národním muzeu výpočetní techniky , Bletchley Park . Emuloval funkce Lorenza SZ40 / 42 a ze vstupu šifrovacího textu vytvořil tištěný čistý text.

Takzvaný „stroj British Tunny“ byl zařízení, které přesně replikovalo funkce strojů SZ40/42. Poté, co bylo určeno nastavení vačky, bylo použito k výrobě německého čistého textu z pásky se šifrovacím textem. Funkční design byl vyroben v Bletchley Parku, kde bylo do konce války používáno deset testery Tunnies. Gil Hayward , „Doc“ Coombs , Bill Chandler a Sid Broadhurst byl navržen a postaven v laboratoři Tommy Flowers na výzkumné stanici General Post Office na Dollis Hill . Byl vyroben hlavně ze standardních britských elektromechanických zařízení pro telefonní ústředny, jako jsou relé a uniselectory . Vstup a výstup byl pomocí dálnopisu se čtením a děrováním papírové pásky. Tyto stroje byly použity jak ve Testery, tak později v Newmanry . Dorothy Du Boisson, která byla strojní obsluhou a členkou Královské námořní služby pro ženy (Wren), popsala připojení zařízení jako provozování staromódní telefonní ústředny a že během toho dostala elektrický šok.

Když Hayward pozval Flowers, aby vyzkoušel první stroj British Tunny na Dollis Hill zadáním standardní testovací fráze: „Nyní je čas, aby všichni dobří muži přišli na pomoc večírku“, velmi ocenil, že rotor funguje byl nastaven tak, aby poskytoval následující Wordsworthův výstup:

Do britských tuňáků byly přidány další funkce, aby se zjednodušil jejich provoz. Mezi další úpravy byly provedeny pro verze používaných v Newmanry třetí Tuňák je vybaven tak, aby produkovat rozkládá se chi pásky.

Newmanry

Newmanry byl úsek zřízený podle Max Newman v prosinci 1942, aby se zabývala možností pomáhat práci Testery automatizací částí procesu dešifrování Tuňák zprávy. Newman pracoval s Gerrym Morganem, vedoucím výzkumné sekce o způsobech rozbití Tunny, když je v listopadu 1942 Bill Tutte oslovil s myšlenkou toho, co se stalo známým jako „1+2 vloupání“. Toto bylo uznáno jako proveditelné, ale pouze pokud bylo automatizováno.

Newman vytvořil funkční specifikaci toho, co se mělo stát strojem „ Heath Robinson “. Aby realizoval svůj nápad, najal Post Office Research Station na Dollis Hill a Dr. CE Wynn-Williams z Telecommunications Research Establishment (TRE) v Malvernu. Práce na strojírenském návrhu začaly v lednu 1943 a první stroj byl dodán v červnu. Personál v té době tvořili Newman, Donald Michie , Jack Good , dva inženýři a 16 Wrens. Do konce války Newmanry obsahovaly tři stroje Robinson, deset Colossus Computers a řadu britských tuňáků. Personál byl 26 kryptografů, 28 inženýrů a 275 Wrens.

Automatizace těchto procesů vyžadovala zpracování velkého množství děrných papírových pásek, jako jsou ty, na kterých byly přijímány zašifrované zprávy. Absolutní přesnost těchto kazet a jejich přepis byl zásadní, protože jediný chybný znak by mohl znehodnotit nebo poškodit obrovské množství práce. Jack Good představil zásadu „Pokud to není zaškrtnuto, je to špatně“.

„Vloupání 1+2“

WT Tutte vyvinul způsob využití nerovnoměrnosti bigramů (sousedních písmen) v německém prostém textu pomocí diferencovaného cyphertextu a klíčových komponent. Jeho metodě se říkalo „vniknutí 1+2“ nebo „útok dvojité delty“. Podstatou této metody bylo najít počáteční nastavení chi komponenty klíče vyčerpávajícím zkoušením všech pozic jeho kombinace s ciphertextem a hledáním důkazů nejednotnosti, která odrážela vlastnosti původního holého textu. Proces rozbití kola musel úspěšně vytvořit aktuální nastavení vačky, aby bylo možné generovat příslušnou sekvenci znaků chi kol. Bylo naprosto neproveditelné vygenerovat 22 milionů znaků ze všech pěti chi kol, takže původně to bylo omezeno na 41 × 31 = 1271 z prvních dvou.

Vzhledem k tomu, že pro každý z pěti impulsů i :

Z _i = χ _i ⊕ ψ _i ⊕ P _i

a proto

P _i = Z _i ⊕ χ _i ⊕ ψ _i

pro první dva impulsy:

(P ₁ ⊕ P ₂ ) = (Z ₁ ⊕ Z ₂ ) ⊕ ( χ ₁ ⊕ χ ₂ ) ⊕ ( ψ ₁ ⊕ ψ ₂ )

Výpočet předpokládaného P ₁ ⊕ P ₂ tímto způsobem pro každý počáteční bod sekvence χ ₁ ⊕ χ ₂ by přinesl x s a • s, s dlouhodobým větším podílem • s, když byl správný počáteční bod použitý. Tutte však věděl, že použití diferencovaných (∆) hodnot zesiluje tento efekt, protože jakékoli opakující se znaky v otevřeném textu vždy generují • a podobně ∆ ψ ₁ ⊕ ∆ ψ ₂ budou generovat • vždy, když se kola psi nepohybují a asi polovinu času, kdy to udělali - celkově asi 70%.

Tutte analyzoval dešifrovaný šifrový text s odlišnou verzí výše uvedené funkce:

(∆Z ₁ ⊕ ∆Z ₂ ) ⊕ (∆ χ ₁ ⊕ ∆ χ ₂ ) ⊕ (∆ ψ ₁ ⊕ ∆ ψ ₂ )

a zjistil, že generuje • přibližně 55% času. Vzhledem k povaze přínosu kol psi bylo zarovnání proudu chi se šifrovacím textem, který poskytl nejvyšší počet • s z (∆Z ₁ ⊕ ∆Z ₂ ⊕ ∆ χ ₁ ⊕ ∆ χ ₂ ) to, které bylo s největší pravděpodobností správné. Tato technika by mohla být aplikována na jakýkoli pár impulsů, a tak poskytla základ automatizovaného přístupu k získání dechi (D) šifrového textu, ze kterého by mohla být složka psi odstraněna manuálními metodami.

Robinsoni

Heath Robinson byl prvním strojem vyrobeným k automatizaci metody Tutte 1 + 2. Název dostal podle Wrensových, kteří jej provozovali, podle karikaturisty Williama Heatha Robinsona , který kreslil nesmírně komplikovaná mechanická zařízení pro jednoduché úkoly, podobně jako americký karikaturista Rube Goldberg .

Funkční specifikaci stroje vyrobil Max Newman. Hlavní konstrukční návrh byl dílem Franka Morrella na Post Office Research Station na Dollis Hill v severním Londýně a jeho kolega Tommy Flowers navrhl „Combining Unit“. Dr. CE Wynn-Williams z telekomunikačního výzkumného ústavu v Malvernu vyrobil vysokorychlostní elektronický čítač ventilů a relé. Stavba byla zahájena v lednu 1943, prototyp stroje byl používán v Bletchley Parku v červnu.

Hlavní části stroje byly:

• páskový transportní a čtecí mechanismus (přezdívaný „lůžko postele“ kvůli jeho podobnosti s převráceným kovovým rámem postele), který spouštěl smyčkové pásky klíčů a zpráv rychlostí 1 000 až 2 000 znaků za sekundu;
• kombinující jednotka, která implementovala logiku Tutteovy metody;
• počítací jednotka, která spočítala počet • s, a pokud překročila předem nastavený součet, zobrazila nebo vytiskla ji.

Prototyp stroje byl účinný i přes řadu závažných nedostatků. Většina z nich byla postupně překonána ve vývoji toho, co se stalo známým jako „starý Robinson“.

Kolos

Počítač Mark 2 Colossus. Operátory Wren jsou (zleva doprava) Dorothy Du Boisson a Elsie Booker. Šikmý ovládací panel vlevo sloužil k nastavení vzorů kolíků na Lorenzu. Doprava papírového pásku „na lůžko“ je vpravo.

V roce 1994 zahájil tým vedený Tony Saleem (vpravo) rekonstrukci kolosu Mark 2 v Bletchley Parku. Zde v roce 2006 Sale a Phil Hayes dohlížejí na řešení zašifrované zprávy s dokončeným strojem.

Zkušenosti Tommyho Flowerse s Heathem Robinsonem a jeho předchozí, jedinečná zkušenost s termionickými ventily (vakuové trubice) jej přivedla k poznání, že pomocí elektroniky lze vyrobit lepší stroj. Místo toho, aby byl klíčový proud čten z děrované papírové pásky, mohl elektronicky generovaný klíčový tok umožnit mnohem rychlejší a flexibilnější zpracování. Flowersův návrh, že by toho bylo možné dosáhnout pomocí stroje, který byl zcela elektronický a obsahoval by jeden až dva tisíce ventilů, byl s nedůvěrou zacházen jak v Telecommunications Research Establishment, tak v Bletchley Park, protože se předpokládalo, že to bude také „ nespolehlivý dělat užitečnou práci “. Měl však podporu správce výzkumu na Dollis Hill, W Gordona Radleyho, a tyto myšlenky implementoval a vytvořil Colossus , první elektronický, digitální, počítačový stroj na světě, který byl vůbec programovatelný, v pozoruhodně krátké době deset měsíců. V tom mu pomáhali jeho kolegové z Post Office Research Station Dollis Hill : Sidney Broadhurst, William Chandler, Allen Coombs a Harry Fensom .

Prototyp Mark 1 Colossus (Colossus I) se svými 1500 ventily začal fungovat v Dollis Hill v prosinci 1943 a byl používán v Bletchley Parku v únoru 1944. To zpracovávalo zprávu rychlostí 5000 znaků za sekundu pomocí impulsu ze čtení kazety otvory pro řetězová kola, aby fungovaly jako hodinový signál . Rychle se ukázalo, že to byl obrovský skok kupředu v kryptanalýze Tunny. Byly objednány další stroje Colossus a objednávky na další Robinsony zrušeny. Zlepšený Mark 2 Colossus (Kolos II) obsahoval 2400 ventily a nejprve pracoval u Bletchley Parku dne 1. června 1944, právě včas pro D-den vylodění v Normandii .

Hlavní součásti tohoto stroje byly:

• mechanismus přenosu a čtení pásky („lůžko“), který spustil pásku zpráv ve smyčce rychlostí 5 000 znaků za sekundu;
• jednotka, která generovala tok klíčů elektronicky;
• pět paralelních procesorových jednotek, které lze naprogramovat tak, aby prováděly širokou škálu booleovských operací;
• pět počítacích jednotek, z nichž každý počítal počet • s nebo x s, a pokud překročil předem nastavený součet, vytisklo ho.

Těchto pět paralelních procesorových jednotek umožnilo spuštění „1 + 2 vloupání“ Tutte a dalších funkcí s efektivní rychlostí 25 000 znaků za sekundu pomocí obvodů vynalezených společností Flowers, které by se nyní nazývaly posuvný registr . Donald Michie vypracoval způsob, jak pomocí Colossuse pomáhat při lámání kol a při nastavování kol. To bylo poté implementováno ve speciálním hardwaru na pozdější Colossi.

Bylo použito celkem deset počítačů Colossus a jedenáct byl uveden do provozu na konci války v Evropě ( Den VE ).

Speciální stroje

Kromě komerčně vyráběných dálnopisů a perforátorů byla postavena řada dalších strojů, které pomáhají při přípravě a kontrole pásek v Newmanry a Testery. Přibližný doplněk k květnu 1945 byl následující.

Kroky v nastavení kola

Vypracování počáteční polohy kol chi ( χ ) nejprve vyžadovalo, aby jejich nastavení vačky bylo určeno „rozbitím kola“. Zpočátku toho bylo dosaženo dvěma zprávami, které byly odeslány do hloubky .

Počet počátečních pozic pro první dvě kola, χ ₁ a χ _2, byl 41 × 31 = 1271. Prvním krokem bylo vyzkoušet všechny tyto počáteční pozice na pásce zpráv. To byl Tutteův „1+2 break in“, který zahrnoval výpočetní techniku (∆Z ₁ ⊕ ∆Z ₂ ⊕ ∆ χ ₁ ⊕ ∆ χ ₂ ) - což dává domněnku ( ∆D ₁ ⊕ ∆D ₂ ) - a počítání počtu kolikrát to dalo • . Nesprávné počáteční pozice by v průměru poskytly počet bodů 50% délky zprávy. V průměru by počet bodů pro správný výchozí bod byl 54%, ale kolem těchto průměrů byl nevyhnutelně značný rozptyl hodnot.

Jak Heath Robinson, který se vyvinul do takzvaného „starého Robinsona“, tak Colossus byly navrženy tak, aby tento proces zautomatizovaly. Statistická teorie umožnila odvození míry toho, jak daleko byl jakýkoli počet od očekávaných 50% s nesprávným výchozím bodem pro chi kola. Tato míra odchylky od náhodnosti se nazývala sigma. Výchozí body, které dávaly počet menší než 2,5 × sigma, pojmenované „celkový součet“, nebyly vytištěny. Ideální pro běh pro nastavení χ ₁ a χ ₂ bylo, že jeden pár zkušebních hodnot vytvořil jednu vynikající hodnotu pro sigma a identifikoval tak počáteční pozice prvních dvou chi koleček. Níže je uveden příklad výstupu z takového běhu na kolosu Mark 2 s pěti čítači: a, b, c, d a e.

Při průměrně velké zprávě by to trvalo asi osm minut. Využitím rovnoběžnosti kolosu Mark 2 však bylo možné počet přečtení zprávy snížit o faktor pětkrát, a to z 1271 na 255. Po identifikaci možných počátečních pozic χ ₁ , χ ₂ je dalším krokem bylo pokusit se najít počáteční polohy pro ostatní chi kola. Ve výše uvedeném příkladu existuje jediné nastavení χ ₁ = 36 a χ ₂ = 21, jehož hodnota sigma jej odlišuje od ostatních. Nebylo tomu tak vždy a Small uvádí 36 různých dalších běhů, které lze vyzkoušet podle výsledku běhu χ ₁ , χ ₂ . Nejprve volby v tomto iteračním procesu prováděl kryptanalytik sedící u výstupu z psacího stroje a vyvolávající pokyny operátorům Wren. Max Newman vymyslel rozhodovací strom a poté stanovil Jacka Gooda a Donalda Michieho za úkol vymyslet ostatní. Ty byly použity Wrens bez použití kryptoanalytiků, pokud byla splněna určitá kritéria.

Ve výše uvedeném malém příkladu byl další běh s prvními dvěma koly chi nastavenými do počátečních poloh a třemi samostatnými paralelními průzkumy zbývajících tří chi kol. Takovému běhu se říkalo „krátký běh“ a trval asi dvě minuty.

Pravděpodobné počáteční pozice pro kola chi jsou: χ ₁ = 36, χ ₂ = 21, χ ₃ = 01, χ ₄ = 19, χ ₅ = 04. Tyto musely být ověřeny před zprávou dechi ( D ) byl předán Testery. To zahrnovalo Colossus, který provedl výpočet frekvence 32 znaků v ΔD . Small popisuje kontrolu počtu frekvencí znaků ΔD jako „test kyseliny“ a že prakticky každý kryptoanalytik a Wren v Newmanry and Testery znal zpaměti obsah následující tabulky.

Pokud získané počáteční body chi kola prošly touto zkouškou se de- chi ed zpráva byla předána Testery, kde byly použity manuální metody k odvození psi nastavení a motoru. Jak poznamenal Small, práce v Newmanry vyžadovala velké množství statistických věd, zatímco práce v Testery vyžadovala mnoho jazykových znalostí a byla velkým zájmem jako umění. Kryptanalytik Jerry Roberts poukázal na to, že tato testovací práce byla pro zaměstnance větší zátěž než automatizované procesy v Newmanry.

Viz také

• Národní muzeum výpočetní techniky

Poznámky a reference

Bibliografie