Turingery - Turingery - Wikipedia

Turingery^[1] nebo Turingova metoda^[2] (hravě dabovaný Turingismus Peter Ericsson, Peter Hilton a Donald Michie^[3]) byla ruka lámání kódů metoda navržená v červenci 1942^[4] matematik a kryptoanalytik Alan Turing u Britů Vládní zákoník a škola Cypher v Bletchley Park v průběhu druhá světová válka.^[5]^[6] Bylo to pro použití v dešifrování Lorenzovy šifry produkoval SZ40 a SZ42 dálnopis rotor proudová šifra stroje, jeden z Němci ' Geheimschreiber (spisovatel tajemství) stroje. Britové s kódovým označením non-Morse provoz "Ryba", a to z tohoto stroje „Tunny“.

Čtení zprávy Tunny vyžadovalo zaprvé, že byla známa logická struktura systému, zadruhé, že byl odvozen periodicky se měnící vzor aktivních vaček na kolech, a zatřetí, že počáteční polohy scramblerových kol pro tuto zprávu - klíč zprávy -byl založen.^[7] Logická struktura Tunny byla vypracována William Tutte a kolegové^[8] během několika měsíců končících v lednu 1942.^[9] Odvození klíče zprávy se nazývalo „nastavení“ v Bletchley Parku, ale bylo to odvození vačkových obrazců - které se nazývalo „rozbíjení kol“ -, což byl cíl Turingeryho.

Německý operátor chyby při přenosu více než jedné zprávy se stejným klíčem, produkovat a "hloubka", povolil odvození tohoto klíče. Turingery byl aplikován na takový klíčový proud k odvození nastavení vačky.^[10]

SZ40 a SZ42

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, krátce před spojeneckým vítězstvím v Evropě.^[11]

Stroje Lorenz SZ měly každé 12 kol s jiným počtem vaček (neboli „čepů“).

Číslo kola	1	2	3	4	5	6	7	8	9	10	11	12
Název kola BP^[12]	${ displaystyle psi}$ ₁	${ displaystyle psi}$ ₂	${ displaystyle psi}$ ₃	${ displaystyle psi}$ ₄	${ displaystyle psi}$ ₅	${ displaystyle mu}$ ₃₇	${ displaystyle mu}$ ₆₁	${ displaystyle chi}$ ₁	${ displaystyle chi}$ ₂	${ displaystyle chi}$ ₃	${ displaystyle chi}$ ₄	${ displaystyle chi}$ ₅
Počet vaček (kolíků)	43	47	51	53	59	37	61	41	31	29	26	23

Stroje SZ byly 12kolové rotor šifra stroje, které implementovaly a Vernam proudová šifra. Byly připojeny in-line ke standardním Lorenzovým dálnopisům. Zpráva postavy byly zakódovány v 5-bit Abeceda mezinárodní telegrafie č. 2 (ITA2). Výstupní znaky šifrovacího textu byly generovány kombinací a pseudonáhodné proud klíčů znak po znaku se vstupními znaky pomocí "exkluzivní nebo "(XOR) funkce (symbolizovaná ${ displaystyle oplus}$ ). Vztah mezi prostý text, šifrový text a kryptografický klíč je pak:

{ displaystyle mathrm {ciphertext} = mathrm {holý text} oplus mathrm {klíč}}

Podobně pro dešifrování byl šifrovací text kombinován se stejným klíčem, aby poskytl holý text:

{ displaystyle mathrm {plaintext} = mathrm {ciphertext} oplus mathrm {klíč}}

Tím se vytvoří zásadní vzájemnost, která umožní použití stejného stroje se stejným nastavením pro šifrování i dešifrování.

Každá z pěti bitů klíče pro každou postavu byla vygenerována příslušnými koly ve dvou částech stroje. Tito byli nazýváni chi ( ${ displaystyle chi}$ ) kola a psi ( ${ displaystyle psi}$ ) kola. The chi všechna kola se pohybovala na jedné pozici pro každou postavu. The psi kola se také pohybovala společně, ale ne po každém znaku. Jejich pohyb byl řízen těmito dvěma mu ( ${ displaystyle mu}$ ) nebo „motorová“ kola.^[13]

Klíčový tok generovaný stroji SZ tedy měl a chi komponenta a psi komponenta, která byla kombinována společně s funkcí XOR. Klíč, který byl zkombinován s holým textem pro dešifrování - nebo s ciphertextem pro dešifrování - lze tedy znázornit následovně.^[13]

{ displaystyle mathrm {key} = { textit {chi}} mathrm {{ mbox {-}} klíč} oplus { textit {psi}} mathrm {{ mbox {-}} klíč}}

Symbolicky:

{ displaystyle K = chi oplus psi}

Dvanáct kol měla kolem sebe řadu vaček (nebo „kolíků“). Tyto vačky lze nastavit do zvednuté nebo spuštěné polohy. Ve zvednuté poloze vygenerovali „značku“ “×„(„ 1 “v binárním formátu), ve snížené poloze vygenerovali„ mezeru ““·„(„ 0 “v binárním formátu). 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. S celkovým počtem 501 kamer se to rovná 2⁵⁰¹ což je přibližně 10¹⁵¹, astronomicky velké číslo.^[14] Pokud je však pět impulsů zvažováno nezávisle, jsou čísla mnohem lépe zvládnutelná. The produkt doby rotace libovolného páru chi Wheels dává čísla mezi 41 × 31 = 1271 a 26 × 23 = 598.

Rozdíly

Kryptoanalýza často zahrnuje hledání vzorů jakéhokoli druhu, které poskytují způsob, jak eliminovat řadu klíčových možností. V Bletchley Parku byla kombinace XOR hodnot dvou sousedních písmen v klíči nebo šifrovacím textu nazývána rozdíl (symbolizovaný řeckým písmenem delta ${ displaystyle Delta}$ ) protože XOR je stejný jako modulo 2 odčítání (bez „vypůjčení“) - a mimochodem, přidání modulu 2 (bez „přenášení“). U znaků v klíči (K) je tedy rozdíl ${ displaystyle Delta K}$ bylo získáno následovně, kde zdůraznit označuje následující znak:

{ displaystyle Delta K = K oplus { podtržení {K}}}

(Podobně s holým textem, šifrovým textem a dvěma složkami klíče).

Vztah mezi nimi platí, když se liší. Například, stejně jako:

{ displaystyle K = chi oplus psi}

Je možné, že:

{ displaystyle Delta K = Delta chi oplus Delta psi}

Pokud je holý text reprezentován P a cipertext Z, platí také následující:

{ displaystyle Delta Z = Delta P oplus Delta chi oplus Delta psi}

A:

{ displaystyle Delta P = Delta Z oplus Delta chi oplus Delta psi}

Důvodem, že rozdíl poskytl cestu do Tunny, bylo to, že i když nebylo možné rozlišit frekvenční rozdělení znaků v ciphertextu od náhodného proudu, totéž neplatilo pro verzi ciphertext, ze které chi prvek klíče byl odstraněn. Je tomu tak proto, že prostý text obsahoval opakovaný znak a znak psi kola se nepohybovala dál, rozdíl psi znak ( ${ displaystyle Delta psi}$ ) by byl nulový znak („·····„nebo 00000), nebo, v terminologii Bletchley Park,“/". Když je XOR-ed s jakýmkoli znakem, tento nulový znak nemá žádný účinek, takže za těchto okolností, ${ displaystyle Delta chi = Delta K}$ . Opakované znaky v holém textu byly častější, jednak kvůli charakteristice němčiny (EE, TT, LL a SS jsou relativně běžné),^[15] a protože telegrafisté často opakovali znaky posunu čísel a písmen^[16] jak by jejich ztráta v běžné telegrafní zprávě mohla vést hatmatilka.^[17]

Cituji obecnou zprávu o Tunny:

Turingery představil princip, že klíč se liší u jednoho, nyní nazývaného ${ displaystyle Delta K}$ , by mohlo přinést informace nedosažitelné z běžného klíče. Tento ${ displaystyle Delta}$ Princip měl být základem téměř všech statistických metod rozbíjení a nastavení kol.^[1]

Rozdíl na bitové úrovni

Stejně jako použití rozdílu na plné 5bitové znaky souboru ITA2 kód, byl také aplikován na jednotlivé impulsy (bity). Takže pro první popud, který byl zašifrován koly ${ displaystyle chi _ {1}}$ a ${ displaystyle psi _ {1}}$ , rozdílné v jednom:

{ displaystyle Delta K_ {1} = K_ {1} oplus { podtržení {K_ {1}}}}

A pro druhý impuls:

{ displaystyle Delta K_ {2} = K_ {2} oplus { podtržení {K_ {2}}}}

A tak dále.

Je také třeba poznamenat, že periodicita chi a psi kola pro každý impuls (41, respektive 43 pro první) se odráží v jeho vzoru ${ displaystyle Delta K}$ . Vzhledem k tomu, že psi kola nepostupovala pro každý vstupní znak, stejně jako chi kola, nešlo jen o opakování vzoru každých 41 × 43 = 1763 znaků ${ displaystyle Delta K_ {1}}$ , ale složitější sekvence.

Turingova metoda

V červenci 1942 strávil Turing několik týdnů ve výzkumné sekci.^[18] Začal se zajímat o problém vylomení Tunnyho z klíčů, které byly získány hloubky.^[3] V červenci vyvinul metodu odvození nastavení vačky od délky klíče.^[1] Jednalo se o iterativní, téměř pokus-omyl, proces. Spoléhala na to, že když se liší psi znak je nulový znak ("·····"nebo 00000),/, pak to XOR-ing s jiným znakem nezmění. Takto delta klíčový znak dává charakter pěti chi kola (tj. ${ displaystyle Delta chi = Delta K}$ ).

Vzhledem k tomu, že delta psi znak byl v průměru nulový znak v polovině času, za předpokladu, že ${ displaystyle Delta K = Delta chi}$ měl 50% šanci, že bude správný. Proces začal ošetřením konkrétního ${ displaystyle Delta K}$ znak jako Δ ${ displaystyle chi}$ pro tuto pozici. Výsledný předpokládaný bitový vzor × a · pro každého chi kolo bylo zaznamenáno na list papíru, který obsahoval tolik sloupců, kolik bylo znaků v klíči, a pět řádků představujících pět impulsů ${ displaystyle Delta chi}$ . Vzhledem k znalostem Tutteho práce, periodicitě každého z kol, to umožnilo šíření těchto hodnot na příslušných pozicích ve zbytku klíče.

Sada pěti listů, jeden pro každý z nich chi kola, byl také připraven. Ty obsahovaly sadu sloupců odpovídajících počtu vaček pro příslušné chi kolo, a byly označovány jako „klec“. Takže ${ displaystyle chi _ {3}}$ klec měla 29 takových sloupů.^[19] Postupné „odhady“ ${ displaystyle Delta chi}$ hodnoty pak vytvořily další domnělé hodnoty stavu vačky. Mohly by buď souhlasit, nebo nesouhlasit s předchozími předpoklady, a na těchto listech byla vytvořena řada dohod a neshod. Tam, kde neshody podstatně převažovaly nad dohodami, byl učiněn předpoklad, že ${ displaystyle Delta psi}$ znak nebyl nulovým znakem "/", takže relevantní předpoklad byl zlevněn. Postupně se všechna nastavení vaček chi kola byla odvozena a od nich psi a nastavení vačky motorového kola.

Jak byly zkušenosti s metodou vyvíjeny, byla učiněna vylepšení, která umožňovala její použití s mnohem kratší délkou klíče než u původních přibližně 500 znaků.^[1]

Viz také

Odkazy a poznámky

^ ^A ^b ^C ^d Dobře, Michie & Timms 1945, str. 313 palců Zkušební metody 1942–1944
^ Vládní zákoník a Cypher School 1944, str. 89
^ ^A ^b Copeland 2006, str. 380
^ Dobře, Michie & Timms 1945, str. 309 palců Metody rané ruky
^ Hodges 1992, str. 230–231
^ Copeland 2006, s. 380–382
^ Churchhouse 2002, str. 4
^ Tutte 1998, str. 5
^ Dobrý 1993, str. 161
^ Copeland 2006, str. 381
^ Prodej, Tony, Lorenzova šifra a jak to Bletchley Park zlomil, vyvoláno 21. října 2010
^ Dobře, Michie & Timms 1945, str. 6 palců Německý tuňák
^ ^A ^b Dobře, Michie & Timms 1945, str. 7 palců Německý tuňák
^ Churchhouse 2002, str. 158
^ Singh, Simon, Černá komora, vyvoláno 28. dubna 2012
^ Nový muž C. 1944 s. 387
^ Povozník, str. 3
^ Tutte 2006, str. 359, 360
^ Copeland 2006, str. 385, který reprodukuje a ${ displaystyle chi _ {3}}$ klec z obecné zprávy o Tunny

Bibliografie

Carter, Frank, Bletchley Park Technical Papers: Colossus and the Breaking of the Lorenz Cipher (PDF), vyvoláno 28. ledna 2011
Churchhouse, Robert (2002), Kódy a šifry: Julius Caesar, Enigma a internet, Cambridge: Cambridge University Press, ISBN 978-0-521-00890-7
Copelande, Jacku (2006), "Turingery", v Copeland, B. Jack (vyd.), Colossus: The Secrets of Bletchley Park's Codebreaking ComputersOxford: Oxford University Press, ISBN 978-0-19-284055-4
Dobře, Jacku (1993), "Enigma and Fish", in Hinsley, F.H.; Stripp, Alan (eds.), Codebreakers: Vnitřní příběh Bletchley ParkuOxford: Oxford University Press, ISBN 978-0-19-280132-6
Dobře, Jacku; Michie, Donald; Timms, Geoffrey (1945), Obecná zpráva o tunelu: S důrazem na statistické metody, UK Public Record Office HW 25/4 a HW 25/5, vyvoláno 15. září 2010 Tato verze je faxovou kopií, ale je zde přepis velké části tohoto dokumentu ve formátu „.pdf“ na adrese: Prodej, Tony (2001), Část „Obecné zprávy o Tunny“, historie Newmanry, formátovaná Tonym Saleem (PDF), vyvoláno 20. září 2010a webový přepis části 1 na adrese: Ellsbury, Graham, Obecná zpráva o tunelu s důrazem na statistické metody, vyvoláno 3. listopadu 2010
Vládní zákoník a škola Cypher (1944), Kryptografický slovník Bletchley Park 1944 formátovaný Tonym Saleem (PDF), vyvoláno 7. října 2010
Hodges, Andrew (1992), Alan Turing: Záhada, Londýn: Vinobraní, ISBN 978-0-09-911641-7
Newman, Max (kolem 1944), „Dodatek 7: Δ ${ displaystyle chi}$ -Metoda ", v Copeland, B. Jack (vyd.), Colossus: The Secrets of Bletchley Park's Codebreaking ComputersOxford: Oxford University Press, ISBN 978-0-19-284055-4
Tutte, William T. (2006), „Moje práce v Bletchley Parku“, in Copeland, B Jacku (vyd.), Colossus: The Secrets of Bletchley Park's Codebreaking ComputersOxford: Oxford University Press, ISBN 978-0-19-284055-4
Tutte, W. T. (19. června 1998), Ryby a já (PDF), archivovány z originál (PDF) dne 10. července 2007, vyvoláno 7. října 2010 Přepis přednášky prof. Tutte na University of Waterloo

[GRoTTuringery-1] A ^b ^C ^d Dobře, Michie & Timms 1945, str. 313 palců Zkušební metody 1942–1944

[2] Vládní zákoník a Cypher School 1944, str. 89

[Copeland2006P380-3] A ^b Copeland 2006, str. 380

[4] Dobře, Michie & Timms 1945, str. 309 palců Metody rané ruky

[5] Hodges 1992, str. 230–231

[6] Copeland 2006, s. 380–382

[7] Churchhouse 2002, str. 4

[8] Tutte 1998, str. 5

[9] Dobrý 1993, str. 161

[10] Copeland 2006, str. 381

[11] Prodej, Tony, Lorenzova šifra a jak to Bletchley Park zlomil, vyvoláno 21. října 2010

[GRoT11B6-12] Dobře, Michie & Timms 1945, str. 6 palců Německý tuňák

[GRoT11B7-13] A ^b Dobře, Michie & Timms 1945, str. 7 palců Německý tuňák

[14] Churchhouse 2002, str. 158

[15] Singh, Simon, Černá komora, vyvoláno 28. dubna 2012

[16] Nový muž C. 1944 s. 387

[17] Povozník, str. 3

[18] Tutte 2006, str. 359, 360

[19] Copeland 2006, str. 385, který reprodukuje a ${ displaystyle chi _ {3}}$ klec z obecné zprávy o Tunny

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]