Banburismus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 4. srpna 2018; kontroly vyžadují 2 úpravy .

Banburismus  je kryptoanalytická metoda navržená k usnadnění procesu dešifrování zpráv ze šifrovacího stroje Enigma nacistického německého námořnictva. Metoda byla vynalezena Alanem Turingem , vylepšením „cyklické metody“ Jerzyho Rozickiho . [1] [2]

Historie

Když se Alan Turing v roce 1939 připojil k chatě č. 8, nebyla dosud provedena žádná práce na rozluštění zpráv Navy Enigma. V té době se věřilo, že Enigma není hacknutelná. [3] Zprávy byly šifrovány pomocí bigramů a trigramů a také pomocí speciální abecedy ( německy  Grundstellung ). [4] [5] Trigramy byly umístěny ve speciální knize zvané Kennbuch (K kniha). [6] Bigramy jsou v tabulkách bigramů. [7] Bez znalosti těchto tabulek bylo dešifrování nemožné. [8] Po operaci Narvik Pinch se však crackerům zpřístupnily záznamy obsahující kompletní popis fungování systému indikátorů a také Grundstellung. [9] [10]

Přehled metod

V roce 1941 se kombinace kol Enigma měnily každý den. Šifrátoři vybrali tři kola z osmi dostupných, která byla použita pro šifrování. Celkem tedy bylo na každý den 336 možností. Hlavním účelem popsané dešifrovací metody bylo poskytnout informaci o poloze pravého kola Enigmy , což výrazně snížilo počet sad umístění kola šifrovacího stroje, jejichž polohy bylo nutné v procesu kryptoanalýzy třídit. [2] [11]

Požadavky

Pro implementaci metody byly nutné následující podmínky:

  1. Poměrně velké množství zachycených zpráv – minimálně tři sta.
  2. Znalost charakteristických skupin ( německy:  Verfahren kenngruppe ) používaných zpráv. Pro nalezení této skupiny (trigramů) bylo nutné dosadit hodnoty bigramů do indikátoru zprávy. Aplikace metody je nemožná, dokud nebude známa většina tabulek bigramů.
  3. Značné množství lidských zdrojů a také Hollerithovy karty . Veškerý provoz se musí třídit a analyzovat ručně, což znamená obrovské množství papírování. [12]

Metoda nápad

Myšlenka metody je založena na skutečnosti, že pokud jsou dva řetězce sestávající z písmen latinské abecedy, vybraných náhodně, umístěny jeden pod druhým, pak pravděpodobnost opakování každého znaku bude rovna .

Řádek 1: ThatIsTheFirstStringWithEnglishText Řádek 2: ItIsTheSecondStringPlacedBelowFirst Zápasy * *

Pokud porovnáme dva segmenty šifrového textu německého námořnictva, pak se pravděpodobnost shody zvýší na . Ale to se stane pouze v případě, že tyto zprávy byly zašifrovány pomocí stejné výchozí pozice ( germ. Grundstellung ) rotorů Enigmy. [13] Říká se, že takové zprávy se shodují „do hloubky“ , to znamená, pokud byly získány šifrováním se stejným počátečním nastavením Enigmy . [14] Tento nápad pomohl dosáhnout hlavního cíle metody – identifikovat polohy pravého kola Enigmy, tedy zkrátit čas strávený výčtem pomocí stroje Bombe . [2] Pokud mají zprávy společné části textu dlouhé 4, 6, 8 nebo více písmen, jejich zašifrované protějšky budou mít shody stejné délky. Takové souhře okolností se říkalo „vhodná náhoda“ ( angl. fit ). [patnáct]   

Útok

Abecedy Grundstellung vypadaly takto:

ABCDEFGHIJKLMNOPQRSTU VWXYZ 1. TVSMUIWNFLPJDHYKZSRAE BGCOQ 2. EYKWAQXRTUCNSLVZFHMIJ ODGBP 3. JGDCFEBPZAVQWONHLTURS KMYXI

Pravděpodobnost dvou zpráv se zcela odlišnými trigramy a shodnými "do hloubky" byla a priori , ale pokud byly trigramy v tomto pořadí a , pravděpodobnost se zvýšila na . U trigramů se pravděpodobnost také zvýšila na . Pro naši abecedu

PDP = KWH PDB=KWG

Proto trigram stál o jedno místo dříve . To bylo označeno jako , to znamená, že v abecedě pravého kola Enigmy bylo písmeno o jednu pozici dříve .

První fází útoku bylo najít „shody“ pro 4 a více písmen. Zprávy byly ručně přeneseny na listy Banburi, dlouhé pruhy papíru potištěné abecedou, což umožňovalo najít opakování ve zprávách na každé pozici, a to vzájemným posunutím listů. Bodovací systém hodnotil každý „zápas“ v decibanech pro každou pozici. Příklad zápasové tabulky

Pravděpodobnost BBC + .2 = BBE hexagram nějaký ENF + 3,7 = EPQ pentagram 17:1 RWC + 0,13 = RWL tetragram 4:1 PNX + .5 = PIC nějaký tetragram IUS + 3,3 = IUY hexagram 20:1 ZDR + 5,5 = hexagram ZIX 15:1 SWI + 4,3 = SUD tetragram 4:1 PPD + 0,16 = PPU tetragram 1:2

Písmena byla poté zarovnána

C-E F-Q C-L X-C S-Y R-X

Vzhledem ke vzdálenostem by se dal řetěz napsat jako

R....X....CE..........L

A tak dále pro všechny známé trigramy. Nyní crackeři věděli, jaké relativní pozice by tato písmena měla být v abecedě pravého kola. Dále byl řádek z výsledné sekvence umístěn pod abecedou. Bylo nutné vypracovat všech 26 pozic (R je pod A, pod B, pod C atd.).

ABCDEFGHIJKLMNOPQRSTU VWXYZ 1.R. K. MX. . . . CXE. . . . A. . . . . L. . 2. F

Pozice, které naznačovaly rozpory, byly přeškrtnuty. V této situaci je L pod X, stejně jako F, ​​což dává dvě hodnoty pro jedno písmeno. Výše uvedené je příklad, v reálné praxi to byly desítky linek. Dalším krokem byl výpočet známek pro abecedu na základě toho, že byla vybrána správně. Například, pokud existují dvě zprávy BDL a BDS, skóre pro BDL + 4 = BDS by mělo být lepší než náhodné, pokud je abeceda správná. Provedením takového procesu současně s několika řádky bylo možné výrazně snížit počet možností pro abecedu pravého kola. [16]

Poznámky

  1. ↑ Dobrý, 1993 , str. 155.
  2. ↑ 1 2 3 B. Jack Copeland, 2006 , str. 206.
  3. ↑ Mahon, 1945 , str. čtrnáct.
  4. ↑ Alexander, 1945 , str. 5.
  5. ↑ Alexander, 1945 , str. 7-8.
  6. ↑ Mahon, 1945 , str. 5.
  7. ↑ Alexander, 1945 , str. 7.
  8. ↑ Alexander, 1945 , str. 94.
  9. ↑ Mahon, 1945 , str. 22.
  10. ↑ Alexander, 1945 , str. 24.
  11. ↑ Alexander, 1945 , str. čtyři.
  12. ↑ Alexander, 1945 , str. 22.
  13. ↑ Mahon, 1945 , str. 16.
  14. ↑ B. Jack Copeland, 2006 , s. 207.
  15. ↑ Mahon, 1945 , str. 17.
  16. ↑ Mahon, 1945 , str. 17-20.

Literatura