banburismus
Banburismus byl cryptanalyticproces vyvinutý Alan Turing vBletchley Parku v Anglii běhemdruhé světové války . To bylo používáno Bletchley Park v chatě 8 pomoci rozbít německéKriegsmarine (Naval) zprávy zašifrován na Enigma strojů .Proces používaný sekvenčnípodmíněné pravděpodobnostiodvodit informace o pravděpodobných nastavením Enigma. [ 1 ] To vedlo k vynálezu Turing v zákazu jako opatření na průkaznosti důkazů ve prospěch hypotézy. [ 2 ] [ 3 ] Tento koncept byl později aplikován v Turingery a všechny ostatní metody použité pro porušení Lorenz šifru . [ 4 ]
Cílem Banburismus bylo snížit čas potřebný k elektromechanickým bombe stroje určením nejpravděpodobnější pravý a střední kola Enigma.[ 5 ] [ 6 ] Hut 8 provádí postup nepřetržitě po dobu dvou let, zastavovat se jen v roce 1943 Při dostatečné bombe času staly snadno dostupné. [ 7 ] [ 8 ] Banburismus byl vývoj " hodin metodou "vynalezli polské cryptanalyst Jerzy Rozycki . [ 9 ]
Hugh Alexander byl považován za nejlepší z Banburists. On a IJ Goodpovažován proces intelektuální hra, než práci. Že "není snadné být triviální, ale ne dost těžké vyvolat nervové zhroucení". [ 10 ]
V prvních několika měsících po příchodu na Bletchley Parku v září 1939, Alan Turing správně vyvodil, že zpráva-nastavení Enigma signálů Kriegsmarine byly zašifrovány o společném Grundstellung (počáteční pozice rotorů), a byl pak super-zašifrován s bigram a trigram vyhledávací tabulka. Tyto trigram tabulky byly v knize s názvem Kenngruppenbuch (K book) . Nicméně, bez bigram tabulek, Hut 8 nemohli začít útočit na provoz. [ 11 ] Průlom bylo dosaženo popinče Narvik ve kterém maskovaní ozbrojení trawlery Polares , který byl na své cestě k Narviku v Norsku byl, bylo zabaveno HMS Griffin v Severním moři dne 26. dubna 1940. [ 12 ] Němci neměli čas zničit všechny své kryptografické dokumenty, a zachytil materiál odhalil přesnou podobu indikačního systému, dodává Plugboard připojení a Grundstellung v dubnu 23 a 24 a log operátorů, který dal dlouhý úsek párové holého textu a nešifrovanou zprávu pro 25. a 26..[ 13 ]
V bigram tabulky samy nebyly součástí zachycování, ale Hut 8 byli schopni používat nastavení-seznamy číst zpětně, všechny Kriegsmarine provoz, který byl zachycený 22 do 27 dubna. To jim udělat částečnou rekonstrukci bigram tabulek a začít první pokus o použití Banburismus zaútočit Kriegsmarine provoz, od 30 roku dubna. Způsobilé dny byly ty, kde byly získány alespoň 200 zpráv a pro které dílčí bigram stolky rozluštil ukazatelů . První den, aby se porušovala bylo 8 května 1940, poté oslavován jako "Den Foss hřiště" na počest Hugha Foss , cryptanalyst, kteří dosáhli tohoto činu.
Tento úkol se až do listopadu téhož roku, do které doby inteligence byl velmi zastaralý, ale to přece ukázat, že Banburismus mohlo fungovat. To také dovolilo mnohem více bigram tabulek k rekonstrukci, což umožněno 14.dubna do června 26 až rozdělit. Nicméně, Kriegsmarine měnila bigram tabulky 1. července. [ 14 ] Do konce roku 1940, hodně z teorie systému Banburismus bodovací byly vypracovány.
První Lofoten špetka z trawlerem Krebs dne 03.3.1941 za předpokladu, kompletní klíče za únor - ale žádné bigram tabulky nebo K knihy . Důsledku dešifruje povoleno statistické skórovací systém k je upravit tak, aby Banburismus by se mohl stát standardní postup proti Enigma Kriegsmarine až do poloviny roku 1943. [ 14 ]
Banburismus využil slabinu v ukazateli postupu (šifrovanou zprávu nastavení) provozu Enigma Kriegsmarine. Na rozdíl od německé armádě a letectvu Enigma postupů, Grundstellung byla poskytnuta podle klíčových seznamy, a tak byl stejný pro všechny zprávy na konkrétní den (nebo pár dní). To znamenalo, že tři-ukazatele byly všechny zašifrován se stejným rotoru nastavení tak, aby byli všichni v hloubce navzájem. [ 15 ] Za normálních okolností, ukazatele pro dvě zprávy nikdy nebyly stejné, ale to by se mohlo stát, že část- způsobem prostřednictvím zprávy, že rotor funkce se stejně jako výchozí polohy rotorů pro jiné zprávy, části dvou zpráv, které překrývají tímto způsobem byly do hloubky.
Princip Banburismus je poměrně jednoduchá (a zdá se, že je spíše podobnýindexu shody okolností ). Jestliže dvě věty v angličtině nebo němčině jsou napsány nad sebou, a počet je vyroben z jak často písmeno ve zprávě je stejná, jako odpovídající písmeno v druhé zprávy, že bude více zápasů, než by se vyskytují v případě, že tresty náhodné řetězce písmen. Pro náhodném pořadí, je opakování míra jednotlivých písmen Očekává se, že je 1 v 26, a pro německé námořnictvo zpráv bylo prokázáno, že 1 v 17. [ 16 ] Pokud se tyto dvě zprávy byly do hloubky, pak spolu se vyskytují jen jako tomu bylo v holé.Nicméně, v případě, že zprávy nebyly v hloubce, tak obě ciphertexts porovná, jako kdyby byly náhodné, což opakování rychlost asi 1 do 26 let. To umožňuje útočníkovi převzít dvě zprávy, jejichž ukazatele se liší pouze v třetím znaku, a posuňte je proti sobě hledali vzoru prozradí opakování, která ukazuje, kde se ztotožnit se v hloubce.
Srovnání dvou zpráv se podívat na opakování bylo jednodušší tím, že udeří zpráv na tenkých karet o 250 mm vysoké (10 "), o několik metrů široký (oni měli různé karty pro různé délky zprávy). Otvor v horní části sloupec na kartě zástupce "" na této pozici, otvor ve spodní části představuje "Z". Obě zprávy-karty byly položeny na sebe na světlo-boxu a tam, kde svítilo světlo přes, tam byl opakování. To dělal to mnohem jednodušší detekovat a počítat opakuje. Karty byly vytištěny v Banbury , Anglie. Oni stali se známí jako "banburies" na Bletchley Parku, a tudíž postup jejich použití bylo Banburismus. [ 17 ]
Aplikace scritchmus postupu (viz níže) poskytuje vodítko, pokud jde o možnou pravém rotoru.
Zpráva s ukazatelem " VFG ":XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF
Zpráva s ukazatelem " VFX ":YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ
Hut 8 by udeřil nich na banburies a počítat opakování všech platných kompenzace -25 dopisy 25 písmen. Existují dvě slibné pozice:
XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF
YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ
---------
Tento posun osmi písmen ukazuje devět opakování, včetně dvou bigrams, v přesahem 56 písmen.
Další slibné pozice vypadá následovně:
XCYBGDSLVWBDJLKWIPEHVYGQZWDTHRQXIKEESQSSPZXARIXEABQIRUCKHGWUEBPF
YNSCFCCPVIPEMSGIZWFLHESCIYSPVRXMCFQAXVXDVUQILBJUABNLKMKDJMENUNQ
---
Tento posun sedmi výstavách jen jeden trigram v přesahem 57 písmen.
Turing metoda hromadění skóre řady decibans umožňuje výpočet, který z těchto situací je s největší pravděpodobností představovat zprávy do hloubky.Jak se dalo očekávat, bývalý je vítězem s kurzem 5:01 na, druhý je pouze 2:01 na. [ 18 ]
Turing počítá skóre pro počet jednotlivých opakování v překrývání tolika dopisů, a počet bigrams a trigramů. Tetragrams často zastoupeny německé slovo v otevřeném textu a jejich skóre byly vypočteny podle typu zprávy (z analýzy provozu), a dokonce i jejich postavení v rámci zprávy. [ 19 ] Ty byly zpracovány do tabulky příslušné hodnoty shrnuty v Banburists při posuzování párů zprávy k vidění, které byly pravděpodobně do hloubky.
Bletchley Park používá konvenci, že ukazatel holý of "VFX", je osm znaků dopředu "VFG", nebo (pokud jde o jen třetí, rozdílné, dopisu), že "X = G+ 8".
Scritchmus byla část Banburismus řízení, které by mohly vést k identifikaci pravé (rychle) kola. Banburist může mít důkazy z různých párů zpráv-(pouze s třetím písmenem udávajícím odlišný) ukazuje, že "X = Q-2", "H = X-4" a "B = G+ 3". On nebo ona [ 20 ] by podívejte se deciban listy pro všechny vzdálenosti s kurzem lépe než 1:01 (tj. skóre ≥ 34). Pokus byl pak předstíral, že postavit "Konec kola abecedu 'tím, že tvoří" řetězy "pro koncové kol písmena z těchto opakování. [ 21 ] Oni by pak vytvoření "řetěz" se mění takto:
G - BH --- XQ
Pokud je to pak porovnají na progresivní offsety s známého listovní sledu Enigma rotoru, jsou poměrně málo možností zlevněné z důvodu porušení buď "reciproční" majetek nebo "no-self-šifrování" majetku Enigma:
G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je možné G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (G zašifruje do B, zatím B zašifruje až E) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (H zřejmě zašifruje až H) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (G zašifruje až D, zatím B zašifruje až G) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (B zašifruje do H, zatím H zašifruje do J) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (Q zřejmě zašifruje až Q) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (G zřejmě zašifruje až G) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (G zašifruje do H, zatím H zašifruje do M) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je možné G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je možné G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je možné G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (H zašifruje do Q, zatím Q zašifruje do W) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (X zašifruje do V, zatím Q zašifruje až X) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (B zašifruje do Q, zatím Q zašifruje do Y) G - BH --- XQ ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (X zašifruje až X) Q G - BH --- X-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je možné -Q G - BH --- X-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (Q zašifruje do B, zatím B zašifruje do T) XQ G - BH ---> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je možné -XQ G - BH -> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (X zašifruje do B, zatím B zašifruje do V) - XQ G - BH-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je možné --- XQ G - BH-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (X zašifruje až D, zatím B zašifruje až X) H --- XQ G - B-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (Q zašifruje až G, zatím G zašifruje do V) -H --- XQ G - B-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (H zašifruje do B, zatím Q zašifruje do H) BH --- XQ G -> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je možné (všimněte G zašifruje do X, X zašifruje až G majetku) -BH --- XQ G-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je nemožné (B zašifruje do B) - BH --- XQ G-> ABCDEFGHIJKLMNOPQRSTUVWXYZ ......... je možné
Tzv. "end-kola abeceda" je již omezen na pouhých devět možností, pouze tím, že stanoví dopis řetězů z pěti písmen odvozených od pouhých čtyři párů Message-. Hut 8 by se nyní snaží padnoucí další dopis řetězy - ty se bez společných písmen s prvním řetězci - do těchto devíti abeced kandidátských end-kol.
Nakonec budou doufat, že je ponecháno jen s jedním kandidátem, možná vypadá takhle:
NUP F ---- A - D --- O - XQ G - BH-> ABCDEFGHIJKLMNOPQRSTUVWXYZ
Nejen to, ale takový konec kola abeceda nutí k závěru, že konec kola je ve skutečnosti "Rotor I". To je proto, že "Rotor II" by způsobil v polovině kola obrat, neboť vystoupil z "E" na "F", přesto, že je ve středu rozpětí písmene řetězce "F ---- A - D --- O ". Stejně tak jsou vyloučeny všechny ostatní možné polovině kola obraty. Rotor jsem se jeho obrat mezi "Q" a "R", a to je jen část z abecedy není trvaného řetězce.
Že různé hádanky kola dostaly různé obratu bodů byl, pravděpodobně, že opatření, návrháři stroje zlepšit jeho bezpečnost. To však velmi komplikace mohou Bletchley Park odvodit totožnost koncového kola.
Po ukončení kola je identifikován, může tytéž principy rozšířen pro zpracování prostřední rotor, i když s přidanou složitostí, který nyní hledá překrývání zpráv-dvojicích sdílejících pouze první písmenem udávajícím, a že se překrývá by proto dojít k až 650 znaků sebe. [ 22 ]
Zatížení tohoto úkolu je mimo ruční práce, takže BP praštil zprávy na 80-sloupec karet a používá Hollerith stroje pro skenování tetragram opakování nebo lepší. To jim řekl, které banburies nastavit na světelných boxů (a s tím, co se překrývají) hodnotit celou opakování vzoru.
Vyzbrojeni souboru pravděpodobných střední kol překrývá, může Hut 8 skládat dopis řetězy pro střední kola mnohem stejným způsobem, jak bylo popsaného výše pro koncového kola. To zase (po Scritchmus) by alespoň částečně střední kola abecedu, a doufejme, že alespoň mohly být některé z možných voleb v rotoru pro střední kola vyřazena z obratu znalostí (jak tomu bylo v identifikaci koncového kolo).
Dohromady by pravděpodobné pravá ruka a střední kola dát sadu Bombe běží na den, který by se tím výrazně snížil z 336 je to možné.