Turingery
Turingery [ 1 ] nebo Turing Metoda [ 2 ] (hravě dabovaný Turingismus Peter Ericsson, Peter Hilton a Donald Michie [ 3 ] ) byl ruční codebreaking metoda vymyslel v červenci 1942 [ 4 ] , které matematik a cryptanalyst Alana Turinga na britské vládě Kód a Cypher School v Bletchley Parku during světové války .[ 5 ] [ 6 ] To bylo pro použití v kryptoanalýza šifry Lorenz produkované SZ40 a SZ42 dálnopisu rotor proudová šifra machines, jeden z Němců "Geheimschreiber (tajné spisovatel) stroje. Britové kódovým označením non-Morse provoz Ryby , a že z tohoto stroje Tunny .
Čtení tuňák zprávu požadované za prvé, že logická struktura systému bylo známo, za druhé, že byla odvozena periodicky-změnil vzor aktivních vaček na kolech, a zatřetí, že výchozí pozice rušivé kol pro tuto zprávu-na zprávy klíče - byla založena. [ 7 ] logická struktura Tunny byla vypracoval William Tutte a kolegové [ 8 ] během několika měsíců končících v lednu 1942. [ 9 ] Odvození klíč zprávy byl nazýván nastavení v Bletchley Parku, ale to bylo odvození z vačky vzorce-který byl známý jako kolo lámání -to byl cíl Turingery.
Německé provozovatel chyby v přenosu více než jednu zprávu se stejným klíčem, produkovat hloubku , možnost odvození tohoto klíče. Turingery byl aplikován na takové klíč k odvození vačkové nastavení. [ 10 ]
Obsah[ skrýt ] |
Hlavní článek: Lorenz šifra
Logickým fungování systému Tuňák byl dobře dopadlo před Bletchley Park cryptanalysts viděl jeden ze strojů-který jen se stalo v roce 1945, krátce předtím, než vítězství spojenecké v Evropě. [ 11 ]
SZ stroje byly 12-kolovérotorovéšifrovací stroje, které provádějícíVernamovaproudová šifra .Oni byli připojeny v řadě, aby standardní Lorenz teleprinters.Tyto zprávycharaktery byly kódovány v 5-bitové abecedy telegrafie International č. 2 (ITA2) .Výstupní ciphertext charaktery byly generovány kombinací pseudonáhodných znak po znaku klíče proud s vkládání znaků pomocí exkluzivní nebo (XOR) funkce (symbolizovaná ⊕ ).
Podobně, pro dešifrování, byla ciphertext kombinaci se stejným klíčem dát holý text.
To vytváří základní vzájemnosti umožnit stejný stroj se stejným nastavením, které mají být použity jak pro šifrováním a rozluštit.
Každá z pěti bitů klíče pro každého znaku je generována příslušných kol ve dvou částech stroje. Ty byly nazval chi ( ) kola, a psi ( ) kola. Na chi kola se všichni přesunuli na jednom místě pro každou postavu. V psi kolečka také se všichni přesunuli spolu, ale ne po každém znaku. Jejich pohyb byl řízen dvěma MU ( ) nebo motorová kola. [ 13 ]
Klíč proud generuje SZ stroje tak měla chi složkou a psi komponent, které byly v kombinaci spolu s XOR funkce. Takže,-dekódování může klíč, který se spojí s otevřeným textem pro zašifrovat nebo s ciphertext pro znázornit takto. [ 13 ]
Symbolicky:
Dvanáct kola každý měl sérii vaček (nebo čepy ) v jejich okolí. Tyto kamery mohou být ve zvýšené nebo snížené poloze. V horní poloze se vytvořila značku" x "( 1 v binární), v dolní poloze, že vytvořila prostor " • "( 0 v binární). Počet vaček na každém kole rovnala počet impulsů potřebných způsobit, aby dokončit plnou rotaci. Je třeba poznamenat, že tato čísla jsou co-primárnínavzájem, takže co nejdelší dobu, než se vzor opakuje. S celkem 501 kamer toto se rovná 2 501 , která je přibližně 10 151 , astronomicky velké číslo. [ 14 ]Nicméně, pokud pět impulsy jsou považovány za samostatně, čísla jsou mnohem lépe zvládnutelné. Produkt z rotačního období z každého páru chi kol dává čísla od 41 x 31 = 1271, 26 x 23 = 598.
Dešifrování často zahrnuje vyhledání vzorků nějakého druhu, které poskytují cestu do odstranění celé řady klíčových možností. Na Bletchley Park byl XOR kombinace hodnot dvou sousedních písmen v klíči nebo ciphertext nazývá rozdíl (symbolizováno řeckým delty 'Δ "), protože XOR je stejný jako modulo 2 odčítání (bez půjčit )-a, mimochodem, modulo 2 přidání (bez převodu ). Takže, pro znaky v klíči (K), byl rozdíl ΔK takto získat, pokud zdůrazňují označuje uspět znak:
Podobně se v otevřeném textu, ciphertext a dvou složek klíče. Také, vztah mezi nimi se použije v případě, že jsou differenced. Například, stejně jako:
To je případ, že:
Je-li holý představuje P a cipertext o Z, také následující platit:
A:
Důvodem, proč odlišení předpokladu cestu do Tunny, bylo, že i když distribuce frekvence znaků v šifrovém nelze odlišit od náhodného proudu, totéž neplatí pro verzi ciphertext z nichž chi prvek klíče měl byla odstraněna. To je proto, že tam, kde holý text obsahoval opakovanou charakter a psi kola nepohnul na, rozlišujeme psi znak (Δ by) být null znak ( • • • • • nebo 00000), nebo, v Bletchley Park terminologii, " / ". Když XOR-ed s libovolným znakem, tento znak NULL nemá žádný vliv, takže v těchto případech, Δ = ΔK. Opakované znaky otevřeného textu byly častější jak z důvodu vlastností němčiny (EE, TT, LL a SS jsou relativně časté), [ 15 ] , a proto telegraphists často opakoval figurky-posun a písmena-shift znaky [ 16 ] , jak jejich ztráta v běžném zprávy telegrafu by mohlo vést k blábolení. [ 17 ]
Chcete-li citovat Souhrnnou zprávu o Tunny:
Turingery zavedla zásadu, že klíčem rozlišujeme na jednom, nyní volal ΔΚ, by mohl přinést informace nedosažitelné z běžného klíče. Tato zásada Δ měla být základním podkladem téměř všech statistických metod kolo-lámání a nastavení. [ 1 ]
Stejně jako použití differencing na plný 5-bitových znaků ITA2 kódu, bylo také aplikován na jednotlivých impulsů (bitů). Takže, pro první impuls, bylo, že zašifrován kolečky 1 a 1 , differenced na jednom:
A za druhé impuls:
A tak dále.
Stojí také za zmínku, že periodicita chi a psi kol pro každý impuls (41 a 43 v uvedeném pořadí pro první) se odráží v jeho struktuře ΔK. Avšak vzhledem k tomu, že psi kola nepostoupil pro každý vstupní znak, stejně jako na chi kola, to není jen opakování vzoru každý 41 × 43 = 1763 znaků pro ΔK 1 , ale složitější sekvence.
V červenci 1942 Turing strávili několik týdnů ve výzkumné části. [ 18 ] On stal se zaujatý problémem lámání tuňák z klíčů, které byly získány z hlubin . [ 3 ] V červenci, on vyvinul metodu odvození vačku Nastavení z délky klíče. [ 1 ]Jednalo se o iterativní , téměř trial-and-error, proces. Se opírala o skutečnost, že když rozlišujeme psi znak je znak NULL ( • • • • • nebo 00000), / , pak XOR-ing to s jiným charakterem nemění to. Tak delta Klíčovou postavou dává charakter pěti -či kola (tj. Δ = ΔK).
Vzhledem k tomu, že delta psi charakter byl nulový charakter polovinu času v průměru, předpoklad, že ΔK = Δ měl 50% šanci, že správné. Proces začal léčení určitý ΔK charakter jako Δ pro tuto pozici. Výsledný putative bit vzor xa • pro each chi kola, byl zaznamenán na listu papíru, který obsahoval tolik sloupců, kolik tam bylo znaky v klíči, a pět řad představující pět impulsy z Δ .Vzhledem k tomu, znalosti z práce tutte je, periodicity každým z kol, to umožnilo šíření těchto hodnot na vhodných místech ve zbytku klíče.
Soubor pěti listů, jeden pro každý z chi kol, byl také připraven. Tito obsahovali sadu sloupců odpovídající počtu na vačky pro příslušné chi kola, a byl odkazoval se na jako "klec". Takže 3 klec měla 29 těchto sloupců. [ 19 ]Následné "hádá" o Δ hodnoty pak produkoval další domnělých hodnoty cam státní. To by mohlo buď souhlasit, nebo nesouhlasit s předchozími předpoklady, a hrabě z dohod a neshod bylo vyrobeno na těchto listech. Pokud neshody významně převažují dohody, byl předpoklad, že Δ postava nebyla null znak / , takže relevantní předpoklad byla odmítnuta. Postupně, všechny vačkové nastavení na chi byly odvozeny kola, a od nich se psi a motor kol vačkových nastavení.
Jak ukázaly zkušenosti rozvinutého metody, bylo zlepšení dělal, že dovolil, aby být používán s mnohem kratší délkou klíče než původních 500 nebo tak postav.[ 1 ]