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 

[ upravit překlad ]SZ40 a SZ42

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 ]

Lorenz SZ stroje měly 12 kola každý s různým počtem kamer (nebo kolíky ).

Wheel číslo

1

2

3

4

5

6

7

8

9

10

11

12

BP kola name[ 12 ]\ Psi1\ Psi2\ Psi3\ Psi4\ Psi5\ Mu37\ Mu61\ Chi1\ Chi2\ Chi3\ Chi4\ Chi5
Počet vaček (piny)

43

47

51

53

59

37

61

41

31

29

26

23

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á  ).

Plaintext  Key = Šifrový

Podobně, pro dešifrování, byla ciphertext kombinaci se stejným klíčem dát holý text.

Šifrový  Key = Prostý 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 ( \ Chi) kola, a psi ( \ 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 ( \ 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 ]

Key = Chi -Key  Psi -Key

Symbolicky:

K = \ Chi \ Psi

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.

[ editovat ]Differencing

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:

ΔK = K  K

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:

K = \ Chi \ Psi

To je případ, že:

ΔK = delta  delta\ Chi \ Psi

Je-li holý představuje P a cipertext o Z, také následující platit:

ΔZ = Dp  delta  delta\ Chi \ Psi

A:

P = ΔZ  delta  delta\ Chi \ Psi

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 (Δ \ Psiby) 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, Δ \ Chi= Δ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 ]

[ upravit překlad ]Bit-level odlišení

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:\ Chi\ Psi

ΔK 1 = K 1  K 1

A za druhé impuls:

ΔK 2 = K 2  K 2

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.

[ upravit překlad ]Turing metoda

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. Δ \ Chi = ΔK).

Vzhledem k tomu, že delta psi charakter byl nulový charakter polovinu času v průměru, předpoklad, že ΔK = Δ \ Chiměl 50% šanci, že správné. Proces začal léčení určitý ΔK charakter jako Δ \ Chipro 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 Δ \ Chi.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í.\ Chi\ Chi\ Psi

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 ]