Univerzita Karlova v Praze Matematicko-fyzikální fakulta
BAKALÁŘSKÁ PRÁCE
Vojtěch Brtník Rekonstrukce šifrovacího stroje ŠD-2 Katedra algebry
Vedoucí bakalářské práce: Mgr. Pavel Vondruška Studijní program: Matematika Matematické metody informační bezpečnosti
2009
Děkuji zejména mé rodině za podporu v průběhu studia. Dále velmi děkuji vedoucímu práce Mgr. Pavlu Vondruškovi za cenné rady, připomínky a poskytnutí užitečných materiálů a RNDr. Petru Tesařovi za poskytnutou pomoc.
Prohlašuji, že jsem svou bakalářskou práci napsal samostatně a výhradně s použitím citovaných pramenů. Souhlasím se zapůjčováním práce a jejím zveřejňováním.
V Praze dne 20. května 2009
Vojtěch Brtník
2
Obsah 1.
Úvod ......................................................................................................................................................................6
2.
Úvod do problematiky, představení rotorových šifrátorů ............................................................7 2.1.
Rotorové polyalfabetické šifrátory s vlastní tvorbou hesla ................................................7
2.2.
Stav v Československu v poválečném období...........................................................................8
3.
ŠD-2: úvod, historie a popis stroje ...........................................................................................................9 3.1.
Historie ŠD-2 ...........................................................................................................................................9
3.2.
Všeobecný popis šifrátoru ............................................................................................................. 10
3.3.
Popis šifrovací jednotky .................................................................................................................. 11
4.
ŠD-2: Popis klíče a režimů komunikace .............................................................................................. 15 4.1.
Denní klíč............................................................................................................................................... 15
4.2.
Jednorázový klíč a režimy komunikace .................................................................................... 16
4.3.
Poznámky k dešifrování.................................................................................................................. 18
4.4.
Velikost prostoru klíčů, perioda .................................................................................................. 18
5.
Základní vlastnosti šifrového textu ...................................................................................................... 19 5.1.
Teorie: Frekvenční analýza & statistické testy ..................................................................... 19
5.2.
Aplikace: Frekvenční analýza & statistické testy ................................................................. 20
5.3.
Teorie: Entropie, obsažnost a nadbytečnost jazyka, index koincidence .................... 21
5.4.
Aplikace: Entropie, obsažnost a nadbytečnost jazyka ....................................................... 23
5.5.
Teorie: Korelace a autokorelace .................................................................................................. 23
5.6.
Aplikace: Korelace a autokorelace.............................................................................................. 24
5.7.
Teorie & aplikace: Počet znaků v pohyblivém úseku ......................................................... 25
5.8.
Podposloupnosti ................................................................................................................................ 26
6.
Matematický popis šifrátoru ................................................................................................................... 28
7.
Simulátor .......................................................................................................................................................... 30 7.1.
Licence .................................................................................................................................................... 31
8.
Závěr .................................................................................................................................................................. 32
9.
Literatura ......................................................................................................................................................... 33
10. 10.1.
Apendix A: Testovací nastavení a zpráva ..................................................................................... 34 Testovací nastavení ..................................................................................................................... 34
3
10.2. 11.
Testovací zpráva ........................................................................................................................... 36 Apendix B: Obsah přiloženého DVD................................................................................................ 38
4
Název práce: Autor: Katedra (ústav): Vedoucí bakalářské práce: e-mail vedoucího: Abstrakt:
Rekonstrukce šifrovacího stroje ŠD-2 Vojtěch Brtník Katedra algebry Mgr. Pavel Vondruška
[email protected]
Rotorový šifrovací stroj ŠD-2 s kódovým označením Cvalík byl pokusem
československé vlády zlepšit špatnou úroveň kryptografických služeb v zemi v 50. letech 20. století. Měl vzniknout jako kopie šifrátoru CM-I, používaného v Sovětském svazu na několika stupních velení. Nicméně problémy s domácí výrobou a postupující technologický pokrok rozhodl, že šifrátor nikdy nebude sériově vyráběn a zůstane pouze historickým mezníkem československých dějin. Tato práce je prvním uceleným materiálem o obou, v zásadě totožných, strojích. Zabývá se jejich historií, všeobecným a kryptografickým popisem a základním kryptoanalytickým rozborem. Součástí práce je také softwarový simulátor stroje a soubor doplňkových materiálů publikovaný na webových stránkách a přiloženém DVD. Klíčová slova: kryptoanalýza, ŠD-2, CM-I
Title: Author: Department: Supervisor: Supervisor's e-mail address: Abstract:
Reconstruction of SD-2 cipher machine Vojtěch Brtník Department of Algebra Mgr. Pavel Vondruška
[email protected]
The SD-2 rotor cipher machine was an attempt by the Czechoslovak
government to improve the poor state of cryptographic services in the country during the 1950s. The SD-2 was supposed to serve as a replica of original CM-I cipher machine, used in the Soviet Union on multiple levels of command. However, troubles with domestic produce and technological progress determined that the machine was never manufactured and remained only as a boundary mark in Czechoslovak history. This work is the first comprehensive study of the seemingly identical machines. It covers their history, general and cryptographic description and basic cryptanalysis. Part of the thesis is a program which simulates both machines, as well as a collection of supplementary materials published on the Internet and on the attached DVD.
5
1.
Úvod
Záhady přitahovaly lidstvo od nepaměti. Jednotlivci i celé týmy dokážou vynaložit veškeré prostředky, sílu a mnohdy obětovat život při snaze nějaké tajemství vyluštit. Naproti tomu schopnost uchránit své soukromí a cenné informace před následujícími generacemi, zbytkem rodiny, obchodním partnerem či snad před sebou samým je klíčem k úspěchu v mnoha životních etapách. Tento souboj mezi touhou tajemství prolomit a nutností jej uchránit provází lidstvo celou jeho historií a předurčil vývoj mnoha historických událostí – stěžejních bitev válečných konfliktů, diplomatických jednání, přepadení, spiknutí či revolucí. O tajemství na nejvyšších státních úrovních se běžný člověk příliš mnoho nedozví. Tyto informace jsou přísně střežené vládami jednotlivých států a až s postupem času jsou pozvolna a opatrně odtajňovány veřejnosti. Takový je i příběh československého šifrovacího stroje ŠD-2 patřícího do třídy rotorových šifrátorů, jejíž nejznámějším zástupcem je beze sporu německá Enigma. ŠD-2 měl být vyráběn jako replika sovětského šifrátoru CM-I a měl zajistit kryptografické služby v zemi koncem 50. a v průběhu 60. let 20. století. Vlivem událostí doby ale nakonec k jeho nasazení do provozu nedošlo a přístroj nebyl používán. I tak ale slouží jako inspirace, obraz doby a svědectví toho, kam až vývoj rotorových šifrátorů dospěl. CM-I byl patrně jeden z posledních průmyslově vyráběných rotorových šifrátorů. Jeho spletitost a komplikovanost je o mnoho větší, než na jakou jsme u podobných strojů zvyklí. O jeho historii v Sovětském svazu, resp. Rusku stále neexistuje žádný veřejný materiál a je možné, že je stále ojediněle používán. Tato práce je prvním publikovaným uceleným materiálem o obou, v zásadě totožných, strojích. Všeobecně zpracovává dané téma a snaží se stroje představit z hlediska historického, čistě popisného, kryptografického i kryptoanalytického. Měla by proto sloužit jako odrazový můstek k jejich dalšímu zkoumání, které již může být zaměřeno více specificky. V druhé kapitole nastíníme atmosféru doby a přiblížíme historické souvislosti v tehdejším Československu. Další kapitola představí stroj ŠD-2, jeho původ, stručný všeobecný a podrobný kryptografický popis. Ve čtvrté kapitole se věnujeme klíčové politice a režimům komunikace. Následuje série statistických testů, matematický model stroje a diskuze nad možností kryptoanalýzy. Součástí práce je také simulátor obou strojů, který je na přiloženém DVD, stručně se mu věnuje kapitola 7.
6
2.
Úvod do problematiky, představení rotorových šifrátorů
2.1.
Rotorové polyalfabetické šifrátory s vlastní tvorbou hesla
Šifrování bylo až do nedávné minulosti výhradní a přísně střežená záležitost armády každého jednotlivého státu. Zlaté časy kryptografie proto nastávají v obdobích, kdy armáda figuruje na prvním místě, v obdobích velkých válečných konfliktů. V novodobé historii jsou jednou z nejbujnějších period zbrojení a rozvoje válečné techniky 30. – 50. léta 20. století. Tehdy míra utajených zpráv jak na diplomatické, tak na armádní úrovni prudce stoupla. Již nebylo možno šifrovat vše na papíře, bylo jisté, že zejména z hlediska časového je nutné činnost šifrování zautomatizovat. Jednou z šifer, která staletí odolávala útokům kryptoanalytiků, byla polyalfabetická šifra Vigenèrova šifra. Od jejího objevení okolo roku 1586, až do rozluštění Charlesem Babagem v 40. letech 18. století byla pokládána za nerozluštitelnou1. Její finální rozlomení bylo založeno na příliš krátkém a často se opakujícím klíči. Kdyby byl klíč stejně dlouhý, jako zpráva sama, stala by se polyalfabetická šifra Vernamovou šifrou, absolutně bezpečnou a nerozluštitelnou. Myšlenka prvních automatických šifrátorů je postavena právě na polyalfabetické šifře. Co když heslo v polyalfabetické šifře bude generováno strojem? Odpadá nutnost volit heslo krátké a zapamatovatelné, a šance na jeho náhodnost bude také větší, než u hesla vymyšleného člověkem. Různé počáteční nastavení stroje před každou zprávou umožní, že takové heslo bude pro každou zprávu různé. Příjemce navíc nebude muset vědět celé heslo, což je hlavní překážka praktickému použití Vernamovy šifry. Bude mu stačit znát klíč – počáteční nastavení přístroje před danou zprávou. To je na distribuci podstatně jednodušší. Právě jsme nastínili základní myšlenku rotorových šifrovacích strojů druhé třetiny 20. století, říká se jim stroje s vlastní tvorbou hesla. Okolo poloviny padesátých let existovaly dva přístupy ke konstrukci šifrátoru s vlastní tvorbou hesla. První byl z dílny Borise Hagelina [3, 4], konkrétně můžeme jmenovat šifrátory M-209 či C36. Zařízení mělo na společné ose šest nastavitelných kotoučů, které se na rozdíl od konkurenčních strojů všechny pohybovaly v každém taktu šifrování o jeden krok. Protože kotouče měly různý počet pracovních poloh (17, 19, 21, 23, 25 a 26), postupně se jejich polohy při šifrování rozcházely. Jejich vzájemná nesoudělnost vytvořila pro každé počáteční nastavení kotoučů jiné heslo, které bylo neperiodické a dlouhé přes 101 milionů znaků. Toto heslo bylo pak sčítáno s otevřeným textem a tvořilo výsledný šifrový text. Druhý přístup je známější, především díky pravděpodobně nejslavnějšímu rotorovému šifrovacímu stroji – německá Enigmě. V každém kroku stroje je v účinku substituční šifra, Charles Babbage svůj objev nikdy nepublikoval. První publikovaná kryptoanalýza Vigenerovy šifry pochází od Friedricha Kisiskiho z roku 1863 [13]. 1
7
která se po zašifrování jediného písmene změní. A to tak, že uvnitř stroje jsou rotory, které se po každém zašifrování jednoho písmene pootočí, změní své nastavení a vygenerují tak novou substituční šifru. Heslo tedy není jako u Hagelinového typu generováno explicitně a poté sčítáno s otevřeným textem. Tento princip je také základem šifrových strojů ŠD-2 a CM-I, kterým se věnuje tato práce. I rotorové šifrovací stroje s vlastní tvorbou hesla byly nakonec kryptoanalytiky zdolány2, což můžeme ilustrovat například na práci [1] či [2]. K většině takových poražení ale poprvé v historii nepřispěla hlavním měrou špatná konstrukce daného šifrovacího stroje, ale chyba obsluhy a nedodržení základních kryptografických pravidel, či špionáž.
2.2.
Stav v Československu v poválečném období
Situace v menších státech, tedy i v Československu byla vždy komplikovaná. V období nástupu rotorových šifrátorů se již vědělo, že kryptografie je doménou matematiků3. Vzhledem k velikosti Československa jsme těch kvalitních nikdy mnoho neměli. Konkurovat světovým mocnostem, zejména USA či Sovětskému svazu nikdy nebylo v našich silách. Veškeré poválečné pokusy o vývoj vlastního šifrátoru dopadly špatně. Od roku 1945 do roku 1955 se na československém ministerstvu obrany postupně pracovalo na vývoji devíti typů šifrátorů. Byly to stroje Štolba 2, Heda, Karel, Panlist, Magda, Boba, Era, Ela a Věra [10]. Celý tento vývoj byl prováděn dosti primitivně s velmi špatnými výsledky. Žádný z uvedených strojů nebyl použit v armádním ani jiném provozu, neboť již tehdy prováděné kryptoanalýzy neměly kladné výsledky. Místo toho byly používány zahraniční trofejní stroje Anna, Enigma a Schlüsselgerät.4 V roce 1955 vznikla Zvláštní správa Ministerstva vnitra a československá vláda se po předchozích zkušenostech rozhodla svěřit svou bezpečnost do rukou našim matematicky a technicky vyspělejším partnerům. V poválečném období se logicky nabízel Sovětský svaz. Spolupráce byla korunována šifrátorem ŠD-2, bohužel ani on nebyl nakonec armádně nasazen. Další podrobnosti uvádíme v následujících kapitolách.
Zde se myslí rotorové šifrátory z období druhé poloviny dvacátého století, i dnes existují rotorové šifrovací stroje, které jsou nerozluštěny. 3 Dnes je například americký bezpečností úřad vůbec největším zaměstnavatelem matematiků na světě. 4 Zájemce o dějiny české poválečné historie odkazujeme na seriál v ezinu Crypto-World z let 2007 – 2008. 2
8
3.
ŠD-2: úvod, historie a popis stroje
Nyní se dostáváme k vlastnímu tématu bakalářské práce, šifrovacímu stroji ŠD-2 5. V této kapitole přiblížíme jeho stručnou historii, zevrubný všeobecný a detailní kryptografický popis. V dalších kapitolách popíšeme klíč, tvar a způsob přenosu zprávy a režimy práce stroje. Poté následuje kryptografická bezpečnost stroje jako generátoru náhodného hesla, výsledky statistických testů a celková diskuse nad kvalitou stroje.
Obr. 1: Šifrátor ŠD-2, pohled zepředu
3.1.
Historie ŠD-2
V této kapitole nastíníme stručnou historii stroje. Zájemce o detailnější rozbor odkazujeme na články [5, 6], případně na prozkoumání přiloženého DVD, či webových stránek [7]. Historie československého šifrovacího stroje ŠD-2 6, totiž české modifikace ruského šifrátoru CM-I je velmi zajímavá a unikátní. Jak bylo uvedeno v minulé kapitole, Československo v období po druhé světové válce kapacitně nestačilo na výrobu vlastního šifrátoru. V roce 1955 byla vytvořena Zvláštní správa Ministerstva vnitra, která řídila a koordinovala šifrovou službu v Československu. Tím se bezpečnostní situace rapidně zlepšila. A tak byla v roce 1957 vládou ČSR požádána sovětská strana o pomoc při výrobě šifrátoru. Sovětská strana vyhověla a počátkem listopadu 1957 dodala do Československa dva kusy stroje, které měly představovat vzor pro výrobu šifrátoru s označením ŠD-2. Jednalo se o Šifrátor ŠD-2 vznikl jako replika šifrátoru CM-I (viz dále v textu). Proto veškeré popisy a tvrzení o stroji ŠD-2 platí také pro stroj CM-I, ačkoliv to není vždy explicitně zdůrazněno. 6 V oboru byl stroj běžně nazýván také jako Cvalík, ačkoliv žádná oficiální dobová dokumentace tento termín nezmiňuje. 5
9
modifikaci ruského šifrátoru CM-I v té době používaného v Sovětském svazu na několika stupních velení. Jednou z podmínek dodávky ovšem bylo, že o původu stroje bude zachováno mlčení. To zejména proto, že stroje svou koncepcí vždy naznačují směr vývoje šifrátorů v zemi svého vzniku. Nicméně situace se zdála být komplikovanou. Problémy s domácí výrobou, zejména časová zdlouhavost, náročnost přepracování technické a výrobní dokumentace, utajení vlastní výroby, vyškolení techniků a organizování celého procesu se ukázalo jako příliš velká překážka. Druhou možností byla sériová výroba strojů v SSSR. Tato varianta by vyřešila mnoho komplikací domácí výroby a taktéž by zkrátila dobu čekání na nový šifrátor. Zádrhelem této varianty byla ale příliš velká cena jednoho stroje, a tak ani k její realizaci nedošlo. Šifrovací stroj ŠD-2 je jedním z posledních zástupců zlaté éry rotorových šifrátorů. Již v době jeho výskytu v ČSR začaly být tyto stroje považovány za kryptograficky slabé a pro utajené spojení nevhodné. I to je jeden z důvodů, proč ŠD-2 nebyl v Československu nakonec nikdy vyvíjen, či nasazen do praxe. Stroj ŠD-2 je tak v našich dějinách pouze historickým mezníkem. Jakou roli hrál či hraje jeho vzor CM-I v dějinách Sovětského svazu se můžeme pouze domnívat, protože tyto informace nebyly k dnešnímu dni odtajněny. Místo výroby ŠD-2 se československá vláda zaměřila na výzkum nového, čistě domácího stroje, který by byl vyvinut kryptologicky bezpečně prověřenou a osvědčenou cestou. Tak vznikl ŠD-3, lépe známý pod názvem Dalibor D-302 [8]. Později byly v Československu používány jiné diskové šifrátory s vlastní tvorbou hesla, zejména pak stroje s označením M125M, M-125MR a M-125-3MR3.
3.2.
Všeobecný popis šifrátoru
Všeobecnému popisu se věnujeme pouze okrajově. Více podrobností je k dispozici v již uvedených článcích [5, 6] a zejména na doprovodných webových stránkách [7]. Jak již bylo řečeno, ŠD-2 byl elektromechanický diskový šifrátor s vlastní tvorbou hesla určený pro šifrování offline. Offline šifrování je režim práce, ve kterém výstup z šifrátoru není adresátovi předáván okamžitě v čase. Může být pomocí stroje odeslán později nebo může být použit příklad třetí kanál – typicky dálnopis. ŠD-2 byl na tento způsob komunikace také navržen. Kromě obyčejného tisku na papír umí také děrovat písmena do dálnopisné (perforační) pásky pomocí pětimístného ITA2 (Baudotova) kódu7. Také vstup je možno zadat buď ručně z klávesnice, nebo automaticky pomocí dálnopisné pásky. Stroj tedy v kombinaci s dálnopisnou perforační páskou mohl dešifrovat po počátečním nastavení šifrovací jednotky jednorázovým heslem automaticky. Toto mělo oproti starším strojům tu výhodu, Pětibitový Baudotův kód byl patentován v roce 1874 Émilem Baudotem. Okolo roku 1930 byl nahrazen kódem ITA2 (International Telegraph Alphabet No. 2), který je proto často také nesprávně označován jako Baudotův. Jedná se o předchůdce znakových sad ASCII a EBCDIC [12]. 7
10
že přijatá zpráva mohla být ihned dešifrována a zašifrovaná zpráva okamžitě odeslána. Rychlost komunikace se rapidně zvýšila. Elektromechanický znamená, že mechanismus stroje byl založen na systému pák, ozubených koleček a hřídelů. Elektrické impulsy zajišťovaly přenos elektrického kontaktu od vstupního zařízení skrz šifrátor k výstupnímu zařízení. Mechanika pak zajišťovala vše ostatní, tedy otáčení a posouvání jednotlivých částí stroje, funkčnost klávesnice i tiskacího a perforačního zařízení. Ještě zbývá přiblížit termín s vlastní tvorbou hesla. Opakem jsou stroje s vloženým heslem8, do kterých je nutno vložit heslo tak dlouhé, jako je posílaná zpráva. Šifrátory pak heslo pouze sečtou s otevřeným textem. U strojů s vlastní tvorbou hesla toto není nutné, protože heslo skrytě generují na základě počátečního nastavení. Nevýhodou je řádově vyšší konstrukční složitost strojů a existence periody. Celý šifrátor měří 511 × 514 × 282 milimetrů a váží 41,5 kilogramů. Kostru tvoří klávesnice, snímač dálnopisné perforační pásky, tiskací a dálnopisné děrovací (perforační) zařízení. Tyto složky již byly představeny. Součástí je dále podstavec, hnací jednotka a šifrovací blok. Hnací jednotka se skládá z elektromotoru, převodních hřídelů, mechanických zařízení na počítání pracovních cyklů stroje a posouvání pracovních součástek. Je to mechanické srdce stroje, zajímavé hlavně ze strojařského pohledu. Pouze pro ilustraci možností uveďme, že elektromotor byl schopen pracovat jak na střídavý proud s napětím v rozmezí od 100V do 230V, tak na stejnosměrný proud s napětím 110V. Šifrovací blok bude popsán podrobně v následující kapitole.
3.3.
Popis šifrovací jednotky
Vlastní šifrovací jednotka se skládá z 26 elektromagnetických obvodů. Ty se v každém kroku šifrátoru mění a tvoří pro každý pracovní cyklus unikátní substituční šifru. Vlastní elektromagnetický obvod začíná na konci klávesnicové páky nebo po načtení vstupního písmene na perforační pásce, dále pokračuje do přepínače druhu práce, kde se rozhodne, jestli proud šifrovým blokem půjde po směru (šifrování), proti směru (dešifrování), nebo se celý šifrovací blok přeskočí a vstup se rovnou vytiskne (režim psacího stroje). Při šifrování se z přepínače druhu práce postupuje do kolíkového komutátoru, pravého pevného disku, pěti vnitřních pracovních disků, levého pevného disku až k výstupnímu zařízení. Při dešifrování se postupuje opačně. Z přepínače druhu práce impuls putuje do levého pevného disku, pěti vnitřních disků, pravého pevného disku, kolíkového komutátoru, až konečně k výstupnímu zařízení. 8
Takovým strojem byl například předchůdce ŠD-2, ŠD-1.
11
Následuje popis jednotlivých součástí šifrovacího bloku. 3.3.1.
Kolíkový komutátor
Kolíkový komutátor je určen pro změnu spojení šifrovacích obvodů při vstupu do šifrátoru. Je umístěn mimo vlastní šifrovací blok na lehce dostupném místě a umožňuje tak jednoduchým způsobem bez nutnosti cokoliv rozebírat změnit počáteční nastavení šifrovacích obvodů. Skládá se ze dvou skupin zdířek, pracovně nazvaných VSTUP a VÝSTUP, každá skupina je rozdělena do dvou řad po 13 písmenech (A-M, N-Z). Zdířky skupiny VSTUP jsou pak spojeny vodiči se zdířkami skupiny výstup dle denního klíče. Těmito vodiči pak putuje vlastní elektrický impuls při šifrování/dešifrování. Při šifrování ve směru VSTUP-> VÝSTUP, při dešifrování naopak. Zdířky skupiny VSTUP jsou spojeny s přepínačem druhu práce, zdířky skupiny VÝSTUP s pravým pevným diskem. Obrázek: zapojení kolíkového komutátoru. Ve směru šipek obsluha dle denního klíče zapojí 26 kolíkových vodičů a spojí tak odpovídající písmena skupiny vstup s odpovídajícími písmeny skupiny výstup. 3.3.2.
Obr. 2: Schéma kolíkového komutátoru. Vodiče se zapojují ve směru šipek
Pravý pevný disk
Také nazýván vstupní pevný disk. Slouží pouze k převodu elektrického impulsu na ostatní šifrové disky. Z hlediska bezpečnosti nemá žádnou funkci. 3.3.3.
Vnitřní pracovní disky
Vnitřní pracovní disky jsou srdcem šifrátoru a z hlediska bezpečnosti to nejpodstatnější. Vnitřních šifrových disků je pět, označených čísly 1 – 5. Pořadí, v jakém se poskládají za sebe na osu, je dáno denním klíčem. Každý pracovní disk má na obou svých stranách 26 elektrických zakončení, kterými probíhá elektrický impuls. Pracovní disk se v každém kroku stroje, tj. po zpracování jednoho písmene, otáčí o určitý počet pozic, konkrétně o 0-2 pozice a mění tak zapojení elektrických obvodů. Systém otáčení disků je určen kolíčky a bude popsán později v kapitole. Uvnitř disku je komutační vložka. Ta je vlastním nositelem šifrové informace. V disku je ustanovena v jedné z 26 pevných pozic, ta je dána denní klíčovou tabulkou stejně jako výběr kompletu šifrových vložek.
12
Schéma
zapojení
jednoho
pracovního
disku je znázorněno na následujícím obrázku. Černými
čarami
je
elektrických
vodičů
elektrických
obvodů.
vyznačeno
26
tvořících
26
Tmavě
modrou
barvou je naznačena komutační vložka, světlejší je pak vlastní disk. Ten se v každém
kroku
otáčí
a
otáčí
také
komutační vložkou, která je v něm vložena. Jednotlivá písmena na obvodu komutační vložky i pracovního disku jsou pouze pro obsluhu stroje, aby mohla jednodušeji nastavit
stroj
Nejsvětlejší vyznačen
do
počáteční
modrou pouze
barvou
abstraktní
polohy. je
pak
prostor,
v kterém se komutační disk pohybuje. Poskládáme-li pět těchto abstraktních prostorů za sebe do sekvence a sledujemeli jednu z čar od začátku až do konce, získáme, které písmeno otevřeného textu se
Obr. 3: Schéma obvodů v prostoru pracovního disku a komutační vložky.
zašifruje
na
které
(samozřejmě:
ignorujeme nyní přítomnost kolíkového komutátoru a pevných disků na krajích).
3.3.4.
Levý pevný disk
Také nazýván výstupní pevný disk. Na rozdíl od pravého pevného disku má bezpečnostní funkci. Je v něm vložena jedna komutační vložka. Levý pevný disk nikdy netočí. Můžeme si jej proto představit stejně jako kolíkový komutátor na druhém konci posloupnosti šifrových jednotek. Jen je o dost obtížnější změnit jeho zapojení, protože abychom vyměnili komutační vložku uvnitř, musíme disk celý rozebrat. Která komutační vložka a v jaké poloze v něm bude usazena je opět dáno denním klíčem. Denní klíč bude popsán níže.
13
3.3.5.
Rotování pracovních disků
Jak již bylo řečeno, v každém kroku stroje se pět pracovních disků otočí o určitý počet pozic a změní tak v dalším kroku používanou substituční šifru. O kolik se disky pootočí, udávají kolíčky, které se vkládají do jednotlivých disků na některé z 26 pracovních pozic. V každém kroku disku je pak aktivní jedna z pozic a podle toho, zdali se v ní nachází kolíček nebo ne, se disk pootočí o určitý počet zubů. Která pracovní pozice z daných 26 je přesně v daném kroku aktivní není patrné a budeme tedy předpokládat, že je to pozice úplně dole, tedy v řeči obrázku pozice N abstraktního diskového prostoru. Působení kolíčků udává následující obrázek: Postupně se otáčejí jednotlivé disky. Je-li otočen jeden disk, tak ve směru šipek je přesunuta otáčivá síla na vedlejší disk. Síla se přesune pouze v tom případě, že v daném místě není zablokována kolíčkem. Tedy disk 3 se otočí vždy o 1 pozici, disk 1 minimálně o 1, maximálně o 2, zbytek stojí nebo se otočí o 1. Z obrázku je také patrné, že kolíčky v disku 1 nehrají žádnou roli, protože již nemají co blokovat. Příklad. Představme si, že kolíček je pouze u disku 4. Otočí se tedy disk 3, přenese sílu na disk 4 a disk 1. Disk 4 chce přenést
Obr. 4: Působení kolíčků
sílu na disk 5, ale tomu zabrání kolíček. Z disku 1 už není kam sílu přenést, a tedy se otočí disky 3, 4 a 1 o jednu pozici, disky 5 a 2 se nehýbou. Za zmínku také stojí, že v tomto případě je naprosto irelevantní, zdali je v aktivní pozici disku 5 či 2 kolíček. Pevné disky se neotáčejí nikdy a nebyly v této úvaze vůbec zmíněny. 3.3.6.
Dlouhodobý směnný prvek, umístění kolíčků
Umístění kolíčků v jednotlivých discích je dlouhodobým směnným prvkem a je určeno pro celou skupinu strojů komunikujících spolu. Počet kolíčků a jejich umístění je dáno specielní klíčovou tabulkou. Teoreticky může být umístěno 0 – 26*5 kolíčků. Kolíčky v disku 1 ale nehrají žádnou roli.
14
4.
ŠD-2: Popis klíče a režimů komunikace
Pro šifrovanou komunikaci dvou stanic je potřeba znát denní a jednorázový klíč. Denní klíč je společný pro všechny režimy komunikace, jednorázový se liší v závislosti na daném režimu. Dlouhodobým směnným prvkem je již diskutované umístění kolíčků v jednotlivých discích.
4.1.
Denní klíč
Každá pracovní stanice disponovala denní klíčovou tabulkou. Ta byla distribuovaná pravděpodobně měsíčně a byla společná pro celou komunikační síť. Denní klíč se skládá z následujících položek: -
Určení dne v měsíci, pro který daný klíč platí Výběr šesti komutačních vložek (z kompletu 26) a určení strany, kterou bude komutační vložka do daného disku vložena Úhlové natočení komutačních vložek v discích Pořadí šifrových disků na ose šifrovacího bloku Zapojení kolíkového komutátoru
Jeden záznam v tabulce denních klíčů vypadal například takto: 02 AXFPRH XZSSDF 13542 ABCDEFGHIJKLMNOPQRSTUVWXYZ PKLSFZTBXCYQMADGEJHIORNUWV
Obsluha stroje použije tento klíč druhý den v měsíci, pro který je daná klíčová tabulka distribuována a bude postupovat následovně: -
Z kompletu 26 komutačních vložek budou vybrány vložky A, X, F, P, R a H. Vložka A bude vložena do levého pevného disku. Vložky X, F, P, R a H pak postupně zleva do prvního až pátého vnitřního pracovního disku. Vložka A, P a H bude vložena lícem, zbylé rubem. Komutační vložky mají pro tyto účely od výroby vyražené písmeno, na lícové straně bez potržení, na rubové s podtržením
-
Disky budou na osu vloženy v pořadí 1-3-5-4-2, přičemž disk 1 bude úplně vlevo, disky mají pro tyto účely od výroby vyražené číslo.
-
V komutátoru bude písmeno A skupiny VSTUP spojeno s písmenem P skupiny VÝSTUP, písmeno B s písmenem K, až písmeno Z s písmenem V.
Podíváme-li se opět na obrázek 3 znázorňující prostor jednoho pevného disku, situace je následující:
15
-
Pevný disk je v poloze X. To proto, že písmeno X je v pozici A (tedy úplně nahoře) abstraktního prostoru, v kterém se disk pohybuje. To je pozice, která se mění s otočením disku. Pokud by se tedy disk v dalším kroku otočil o jeden krok, nacházel by se v pozici Y.
-
Komutační vložka je v pozici N, to proto, že její písmeno N se nachází naproti písmene A disku, v kterém je vložena. Jinými slovy, pokud bychom otočili disk do základní polohy, aby jeho písmeno A bylo nahoře. Bylo by nahoře písmeno N komutační vložky. Umístění komutační vložky je dáno denním klíčem a v průběhu šifrování se nemění. Komutační vložka se otáčí spolu s diskem a jejich vzájemná pozice je tedy konstantní.
ŠD-2 byl navržen pro tři režimy komunikace: vzájemnou, oběžníkovou a obecnou.
4.2. 4.2.1.
Jednorázový klíč a režimy komunikace Vzájemná komunikace
Režim vzájemné komunikace sloužil pro výhradní komunikaci dvou stanic. Každá ze dvou komunikujících stran měla k dispozici tabulku jednorázových klíčů. Ta byla stejná pro obě strany a musela být distribuovaná před samotnou komunikací. Ve vzájemném režimu komunikace tak mohly komunikovat pouze dvojice, jenž byly předem ustaveny, a byla jim distribuována tabulka jednorázových klíčů. Jak vypadala tabulka jednorázových klíčů je patrné z obrázku 6. Na začátku každé zašifrované zprávy bylo otevřeně odesláno číslo řádku, jehož jednorázový klíč se má použít. Vlastní jednorázový klíč sestává z pětice písmen a udává úhlové natočení vnitřních pracovních disků před vlastním šifrováním. Jako první disk je uveden disk levý. 4.2.2. Formát
zprávy
v
režimu
vzájemné komunikace Odesílatel na začátek otevřeným textem napíše příjemce, důležitost zprávy a další případně podstatné informace, dále uvede řádek ve sdílené tabulce jednorázových klíčů. Poté tímto jednorázovým klíčem
Obr 6: Tabulka jednorázových klíčů
zašifruje vlastní zprávu. Nakonec opět otevřeným textem uvede takzvanou služební skupina, tj. den odeslání zprávy, který určuje denní klíč, a počet pětiznakových skupin v dané zprávě. Zpráva připravená k odeslání dálnopisem tedy mohla vypadat například takto: 125 DULEZITE 02 ACKSD KDLSIE LDKFHD LDIEZC LDKEIF LKXXX 03007 16
Tato zpráva byla odeslána 2. dne v měsíci adresátovi s číslem 125 s poznámkou důležité. Pro její zašifrování byl použit jednorázový klíč, který daná dvojice najde na třetím řádku ve společné tabulce jednorázových klíčů. 4.2.3.
Oběžníkové komunikace
Oběžníková komunikace funguje na stejném principu jako vzájemná. Pouze s tím rozdílem, že nekomunikují jednotlivé dvojice stanovišť odděleně, ale celá skupina neboli oběžník najednou. Příjemcem jsou všichni v daném oběžníku. Tabulka jednorázových klíčů je tak společná a je distribuována všem stanovištím v daném oběžníku. 4.2.4.
Formát zprávy v režimu oběžníkové komunikace
Formát zprávy je téměř stejný jako v režimu vzájemné komunikace. Navíc je na začátku v rámci otevřené skupiny uvedena identifikace oběžníku, čímž je jasně řečeno že se jedná o zprávu v oběžníkovém režimu. Skupina je identifikována pěticí stejných znaků, zde BBBBB: 125 DULEZITE BBBBB 02 ACKSD KDLSIE LDKFHD LDIEZC LDKEIF LKXXX 03007 4.2.5.
Obecná komunikace
Slouží v případě, že odesílatel potřebuje šifrovaně zaslat zprávu někomu, s kým nemá ustanoven vzájemný klíč a navíc s ním nesdílí žádnou oběžníkovou skupinu. Režim bylo doporučeno používat pouze ve velmi nutném případě, není-li k dispozici jiná alternativa. Postupuje se následovně: 4.2.6.
Stroj se nastaví do libovolné pozice a zmáčknutím libovolných pěti kláves se v režimu šifrování vygeneruje náhodné jednorázové heslo. Stroj se nastaví do pozice dané denním klíčem a zašifruje se vygenerované jednorázové heslo. Poté se stroj přednastaví dle tohoto náhodného hesla. Vygenerovaná pětice slouží jako heslo pro úhlové nastavení pěti vnitřních šifrových disků. Zašifruje se zbytek zprávy. Formát zprávy v režimu obecné komunikace
Formát zprávy je podobný jako u předchozích dvou režimů. Na začátek odesílatel napíše identifikaci adresáta, důležitost zprávy, a na konec služební skupinu. Před vlastní zprávou zašifrovanou vygenerovaným jednorázovým klíčem je ale navíc denním klíčem zašifrován tento jednorázový klíč. 125 DULEZITE QRFSX ACKSD KDLSIE LDKFHD LDIEZC LDKEIF LKXXX 03007 Adresát v tomto případě z formátu zprávy pozná, že se jedná o obecnou komunikaci. Nastaví stroj dle denního klíče 2. dne daného měsíce a dešifruje první pětimístnou skupinu. Tak získá jednorázový klíč pro dešifrování zbytku zprávy.
17
4.3.
Poznámky k dešifrování
Stroj se nastavuje naprosto identicky jako při šifrování. Pouze se přepínačem druhu práce na stroji zvolí režim dešifrování. Z formátu zprávy je na první pohled patrné, v kterém režimu a kdy byla zaslána a kdo je jejím adresátem. V závislosti na tom se pak provede dešifrování patřičného kusu zašifrované zprávy.
4.4.
Velikost prostoru klíčů, perioda
Spočítejme nyní horní odhad na velikost prostoru klíčů. Komutátor je permutace na 26 znacích a možností zapojení tedy je
.
Zjednodušeně můžeme uvažovat komutační vložku v disku, její natočení, natočení celého disku a jeho pořadí na ose jako jednu permutaci v diskovém prostoru. Těchto permutací je opět 26! a aktivních disků je 6. Tedy komutační vložky vytvářejí prostor klíčů velikost . V čtyřech discích uvažujeme kolíčky. Těch může pro každý disk být 0-26. Tedy počet možných umístění kolíčků v jednom disku je
Tedy celý prostor klíčů je velký
Jen pro úplnost je třeba říct, že výpočet je horním odhadem a trochu zjednodušený. Ve skutečnosti je celý prostor klíčů menší, protože komutační vložky jsou dodávány v sadě a není možné si vyrobit svoji vlastní.
18
5.
Základní vlastnosti šifrového textu
Nyní se budeme na šifrový text generovaný strojem ŠD-2 dívat jako na posloupnost pseudonáhodných znaků a budeme zkoumat její vlastnosti. Spočítáme frekvenční analýzu, entropii, obsažnost jazyka a několik dalších souvisejících konstant. Provedeme testy náhodnosti a zkusíme popsat a odhalit slabiny stroje. Obvykle budeme postupovat ve dvou paralelních vláknech, v jednom vždy teoreticky popíšeme daný model, v druhém jej aplikujeme na ŠD-2. Vzhledem k tomu, že možných nastavení stroje ŠD-2 je několik milionů a výsledné statistiky se drobně až mnoho liší v závislosti na počátečním nastavení, vybrali jsme jedno, na kterém budou všechny testy a výpočty provedeny. Nastavme tedy přístroj do počátečního testového nastavení dle Apendixu A a zašifrujme otevřený text, jenž je popsán v té samé části.
5.1.
Teorie: Frekvenční analýza & statistické testy
Mějme posloupnost
délky
nad abecedou
velikosti
. Označme
absolutní počet výskytů jednotlivých znaků abecedy
pro
v dané posloupnosti.
Spočtěme následující statistiku
Pokud je testovaná posloupnost výběrem z náhodné veličiny s rovnoměrným rozdělením znaků z , bude se statistika
asymptoticky řídit rozdělením
s
Proveďme nyní statistický test. Hypotéza: posloupnost
stupni volnosti.
je náhodná a rovnoměrně
rozdělená ve smyslu distribuce jednotlivých znaků abecedy . Alternativa: komplementární tvrzení, tj. posloupnost
není náhodná a rovnoměrně rozdělená.
Provádíme-li test na hladině významnosti
(
), zajímá nás krajní hodnota
kritického intervalu, tedy hodnota inverzní distribuční funkce hodnotu
a celý kritický interval
v bodě . Označme tuto
. Padne-li hodnota testové statistiky
do , je
hypotéza zamítnuta, v opačném případě je potvrzena. Ukážeme si tři příklady aplikace statistiky . 5.1.1.
Test četnosti znaků
Tento test je nejjednodušší aplikací statistiky . Abecedou se rozumí mezinárodní abeceda délky
.
19
5.1.2.
Test četnosti bigramů
Rozdělme testovanou posloupnost na bigramy tak, že dva sousední bigramy se navzájem nepřekrývají. Prvním bigramem tedy bude dvojice Celkem tak dostaneme
, atd.
bigramů. Nyní se můžeme na nově získanou posloupnost
bigramů dívat jako na posloupnost znaků z abecedy 5.1.3.
, dalším dvojice velikosti
.
Test četnosti řetězových bigramů
Rozdělme ještě jednou testovanou posloupnost na bigramy; nyní ale tak, že se sousední bigramy navzájem překrývají v jednom znaku. Prvním bigramem bude dvojice druhým
. Celkem dostaneme
a
bigramů. Pro aplikaci vzorce se opět dívejme na
získané bigramy jako na posloupnost nad abecedou
délky 676.
Konkrétní výpočty provedeme v následující sekci.
5.2.
Aplikace: Frekvenční analýza & statistické testy
Aplikujme nyní poznatky předchozí sekce. Nastavme přístroj ŠD-2 do testovací polohy a zašifrujme text dle Apendixu A. Získáme tím šifrový text
délky
Statistické testy provedeme na hladině významnosti 5.2.1.
.
.
Test četnosti znaků
Proveďme frekvenční analýzu šifrového textu; v prvním řádku jsou znaky abecedy , v druhém jsou jejich relativní četnosti . Absolutní četnosti
délky
neuvádíme, protože
jejich hodnota není příliš vypovídající. A
B
C
D
E
F
G
H
I
J
K
L
M
3,84
3,89
3,75
3,86
3,79
3,85
3,88
3,79
3,82
3,94
3,94
3,83
3,81
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
3,83
3,87
3,85
3,85
3,83
3,88
3,80
3,83
3,89
3,83
3,83
3,86
3,87
Hodnota testované statistiky je
krajní hodnota kritického intervalu je
. Statistika nespadá do
kritického intervalu, tedy potvrzujeme hypotézu, testovaná posloupnost je z hlediska četnosti jednotlivých znaků asymptoticky rovna náhodné posloupnosti.
20
5.2.2.
Test četnosti bigramů
Ze zřejmých důvodů nebudeme uvádět četnosti všech bigramů v testované posloupnosti a pouze se omezíme na výsledky. Jak bylo uvedeno v předchozí sekci, abecedou se nyní rozumí
délky
a testová posloupnost má délku
.
Testová statistika nespadá do kritického intervalu. Potvrzujeme tak hypotézu, která říká, že z hlediska bigramů je vstupní posloupnost rozdělena náhodně. 5.2.3.
Test četnosti řetězových bigramů
Pro zajímavost uvádíme deset nejfrekventovanějších a nejméně frekventovaných dvojic znaků v šifrovém textu. Bigram
IK
QJ
GD
BL
NQ
TO
TE
WK
JL
KI
Fr. (%)
17,27
17,01
16,90
16,54
16,50
16,36
16,36
16,32
16,28
16,28
Bigram
LV
TG
NW
YT
WD
HM
BQ
HX
ZC
QQ
Fr. (%)
12,55
12,70
12,73
12,84
12,95
12,95
12,95
12,99
13,06
13,14
Opět vidíme, že testovaná posloupnost je i z hlediska řetězových bigramů asymptoticky rovna náhodné posloupnosti. 5.2.4.
Závěr
Výsledky jsou jak pro jednotlivé znaky, tak pro bigramy velmi dobré. Ačkoliv délka pozorovaného textu není pro bigramovou analýzu příliš dostatečná, dovolujeme si konstatovat, že ŠD-2 je vůči frekvenční kryptoanalýze velmi odolný a žádný útok tímto směrem není možný. Na základě provedených testů se ŠD-2 na hladině významnosti asymptoticky chová jako náhodný generátor.
5.3.
Teorie: Entropie, obsažnost a nadbytečnost jazyka, index koincidence
Entropie říká, kolik bitů informace nese jedna zpráva. Přesně tento pojem formalizuje Shannonova teorie informace [9]. My se zde soustředíme na zjednodušený popis. 21
Definice (entropie): Předpokládejme, že máme zdroj zpráv , který může vydávat zprávy . Pravděpodobnost, že vydá zprávu
označme
. Entropie jedné zprávy ze zdroje
je číslo
Poznámka: Logaritmus v sumě udává, kolik bitů je potřeba k zakódování zprávy Příklad: Nechť zdroj
vydává zprávy délky
pravděpodobnost. Popsaných zpráv je Entropie
.
bitů takové, že všechny mají stejnou
a každá má tedy pravděpodobnost
.
je
Protože každá zpráva
nese tolik bitů, jak je sama dlouhá, tedy , říkáme, že zdroj nabývá
maximální entropie. Je zřejmé, že běžné jazyky tuto entropii nedosahují. Definice (obsažnost jazyka): Obsažnost
jazyka zdroje
vydávajícího -bitové zprávy
definujeme jako průměrnou entropii jednoho bitu takovéto zprávy.
Příklad: Ať zdroj zpráva
vysílá -znakové zprávy z jazyka obsahujícího znaků. Má-li každá
stejně pravděpodobných znaků a všechny tyto zprávy jsou také stejně
pravděpodobné, pak entropie
je
Obsažnost takového jazyka je potom
Je to maximální možná obsažnost jazyka o
stejně pravděpodobných znacích. Přirozený
jazyk jí opět nedosahuje. To proto, že za prvé nejsou všechna písmena stejně pravděpodobná a za druhé jsou různé
-znakové zprávy jinak pravděpodobné. S rostoucím
pro přirozené jazyky obsažnost zprávy klesá. Od jisté chvíle již je zřejmé, jaké další písmeno ve zprávě následuje, takové písmeno pak samozřejmě nenese entropii
bitů.
Definice (obsažnost, nadbytečnost vzhledem k jednomu znaku): Obsažnost se v limitě pro rostoucí
blíží nějaké konstantě, označme ji . Tuto konstantu nazýváme obsažnost jazyka
vzhledem k jednomu znaku. Číslo
udává, kolik bitů informace v průměru nese jeden znak
zprávy. Rozdíl
22
nazýváme nadbytečnost jazyka vzhledem k jednomu písmenu zprávy. Definice (Index koincidence dvou textů): Jsou-li
a
dva texty délky
nad
stejnou abecedou , pak definujeme index koincidence těchto dvou textů jako
kde je Kroneckerův symbol. Poznámka: Index koincidence je tedy relativní počet pozic, ve kterých mají dané dva texty stejný symbol. Tento přístup jde aplikovat i na jediný text. Definice (Index koincidence textu): Je-li a
posloupnost délky
nad abecedou
velikosti
jsou absolutní četnosti výskytů jednotlivých znaků, tak index koincidence
definujeme jako
Poznámka: Je-li
5.4.
náhodná posloupnost, index koincidence je přibližně
.
Aplikace: Entropie, obsažnost a nadbytečnost jazyka
Definujeme zdroj
jako náš stroj ŠD-2, který vydává zprávy
s pravděpodobnostmi dle frekvenční analýzy uvedené v předchozí sekci. Potom
Předpokládáme-li, že každé písmeno kódujeme binárně, tak na zakódování jednoho písmena potřebujeme
bitů. Tedy ŠD-2 má maximální možnou entropii a chová
se jako náhodný generátor. Obsažnost zdroje je tedy 1 a nadbytečnost 0. Index koincidence
5.5.
Teorie: Korelace a autokorelace
Autokorelace je nástroj sloužící k hledání opakujících se vzorů v zadané posloupnosti. Hodnotu si můžeme představit jako index podobnosti různých částí vstupního textu. Pomocí ní můžeme někdy spočítat délku klíče či odhadnout slabé periody v šifrovém textu. Slabou periodu nebudeme formálně definovat. Je to taková perioda, v níž nedochází k opakování všech, ale pouze netriviálně mnoha znaků. Nejprve zavedeme korelaci dvou posloupností.
23
Definice (korelace): Nechť posloupnosti délky
je konečná abeceda velikosti
nad
. Označme , respektive
a
a
jsou dvě
počet těch indexů, na kterých jsou
hodnoty v obou posloupnostech stejné, resp. různé. Tedy . Potom korelace
mezi danými posloupnosti je číslo
Poznámka 1: Pravděpodobnost shody v jednom určitém indexu je neshody je
a
a pravděpodobnost
Ve definici jsou jejich převrácené hodnoty.
Poznámka 2: Pro binární abecedu
má vzorec tvar
. S touto
podobou se setkáváme v moderní kryptografii nejčastěji. Poznámka 3: Z definice korelace jsou vidět následující fakta: -
Shodují-li se posloupnosti a v (tedy ve všech) pozicích, je korelace . Neshodují-li se posloupnosti a v žádné pozici, je korelace . Očekávaný počet shod pro dvě náhodné posloupnosti je . Nastane-li právě tento počet shod, vychází a říkáme, že posloupnosti jsou nekorelované.
Nyní již můžeme definovat autokorelaci. Je to korelace dané posloupnosti a posloupnosti vzniklé jejím posunem o
míst doprava. Tedy kontrolujeme shodu prvku
s prvkem
. Takové autokorelaci budeme říkat -autokorelace. Nás budou zajímat hodnoty autokorelace pro všechny možné posuny. Pokud by vyšla některá z těchto hodnot významně vzdálená od 0, znamenalo by to, že ve vstupní posloupnosti se nachází na tomto místě slabá perioda. Definice (autokorelace): Nechť Konstruujme posloupnosti -
a
a
je posloupnost délky
délky
nad abecedou
.
takto:
pro pro
-autokorelace posloupnosti
je definována jako korelace posloupností
a
.
Poznámka: Definice korelace a autokorelace platí i pro nekonečné posloupnosti. My se ze zřejmých důvodů zabýváme pouze posloupnostmi konečnými. Posun doprava je acyklický, proto se zvyšujícím se klesá délka zkoumané posloupnosti a tedy i relevantnost výsledků.
5.6.
Aplikace: Korelace a autokorelace
ŠD-2 pracuje nad anglickou abecedou
velikosti
. Dvě náhodné posloupnosti délky
se budou v každé pozici shodovat s pravděpodobností pravděpodobností
.
24
a neshodovat s
Nastavme nyní přístroj do testovacího nastavení dle Apendixu A a zašifrujme testovací zprávu. Zašifrovaný text označme jako posloupnost
nad
. V našem případě
. Očekávaný počet shod mezi posloupnostmi v předchozí sekci, je
a
délek
, které jsou definované
a očekávaná korelace je samozřejmě nulová.
Uvádíme graf znázorňující počet shod pro prvních 200 posunů. Očekávaná hodnota se sice pro každé
liší, ale vzhledem k velikosti
je odchylka od původní hodnoty
zanedbatelná.
Obr. 7: Aplikace autokorelace
Vidíme, že odchylka od očekávané hodnoty ,
a
to
,
nejmenší
je minimální. Nejvyšší počet shod je pro pak
pro
,
konkrétně
.
Kreslit graf pro všechny posuny není možné, podívejme se alespoň na extrémní hodnoty autokorelace. Testujeme pro minimální
Maximální hodnota autokorelace je
a
.
Závěr: Z pozorovaných hodnot můžeme konstatovat, že přístroj ŠD-2 byl navržen z pohledu korelace ideálně. Nebyla pozorována žádná odchylka od náhodného generátoru či existence slabých period.
5.7.
Teorie & aplikace: Počet znaků v pohyblivém úseku
Počet znaků v pohyblivém úseku je lokální charakteristika vstupní posloupnosti. Říká, kolik různých znaků se nachází v podposloupnostech pevných délek. Definice (pohyblivý úsek): Nechť
je abeceda délky
posloupnost nad touto abecedou. Nechť pohyblivého úseku. Posloupnost v pohyblivém úseku
značíme
a nechť
je délka pohyblivého úseku a
délky , kde
je začátek
je pohyblivý úsek. Počet znaků
a je to počet různých znaků v
, tedy
Nastavme ŠD-2 do testovacího stavu a zašifrujme testovací vstup, výstup označme Zvolme
je
.
a spočítejme počet znaků ve všech pohyblivých úsecích. V uvedeném grafu
je na vodorovné ose hodnota a na svislé .
25
Obr. 8: Počet znaků v pohyblivém úseku pro celou testovanou posloupnost.
Graf je díky velké hustotě hodnot na vodorovné ose hůře čitelný a je potřeba jej chápat spíše intuitivně. Pro pochopení situace uvádíme podobný graf, nyní ale pouze pro hodnoty . Například tedy v prvních 64 znacích je 23 různých znaků.
Obr. 9: Počet znaků v pohyblivém úseku pro prvních 950 znaků testované posloupnosti.
Závěr: můžeme konstatovat, že výsledek analýzy je opět z pohledu ŠD-2 ideální. Počet znaků málokdy klesne pod
a nikdy neklesne pod
případů také dosahuje maxima, totiž
5.8.
. V nezanedbatelném množství
znaků.
Podposloupnosti
Mějme posloupnost délky
nad abecedou
velikosti
délky . Těchto podposloupností je abecedou
je
a zkoumejme její podposloupnosti
. Všech možných posloupností délky
nad
. Máme-li tedy zafixovanou libovolnou posloupnost délky , tak očekávaný
počet jejího výskytu v původní posloupnosti délky 26
je
Naše testovaná posloupnost (dle Apendixu A) má délku velikosti
a je nad abecedou
. Očekávaný počet výskytů podposloupnosti délky
je tedy
Nyní se podívejme, jaká je realita. V prvním řádku je hodnota , tedy délka zkoumaných podposloupností, ve druhém řádku je očekávaný počet jejich opakování, tedy hodnota
, v posledním řádku je střední hodnota
počtu jednotlivých opakování v testovacím souboru. 3
4
15,55
0,598
15,9
0,598
5
Pro ilustraci si ukažme výpočet hodnoty
6
pro
7
8
. Po spočítání četností výskytu všech
možných pětic mezinárodní abecedy zjistíme, že 30 pětic se opakuje třikrát, 3053 dvakrát, 267110 se vyskytuje právě jednou a zbylých 11611183 pětic se v testovacím souboru nevyskytuje vůbec. Střední počet výskytů náhodné pětice tak je
a
.
Není nutno provádět žádnou formální statistiku, již z názoru je patrné, že generátor velmi dobře dodržuje rozdělení jednotlivých podposloupností, co se počtu opakování týče.
27
6.
Matematický popis šifrátoru
V této sekci bude nastíněn matematický model stroje. Vzhledem k tomu, že se nepovedlo statistickým testem odhalit žádnou slabinu stroje, je tato část práce spíš slepou uličkou. Označme množinu 26 šifrových vložek, které má obsluha k dispozici jako kde
,
je permutace mezinárodní abecedy.
Označme právě používané komutační vložky jako kapitoly vždy prochází množinu
,
, kde
; v dalším textu
. Označme dále posun jednotlivých vložek vůči
disku, v kterém jsou umístěné jako
, kde
. Tento posun je dán
klíčovou tabulkou a v průběhu práce stroje se nemění. Označme disky ;
a jejich momentální natočení jako
, kde
je konstantní, protože levý disk se netočí.
Nyní označme prostor, v kterém se daný disk
pohybuje jako
, ten se skládá z 26
elektrických obvodů, po kterých jdou impulsy. Doporučujeme nalistovat obrázek
viz
obrázek 3: Schéma obvodů v prostoru pracovního disku a komutační vložky. Připomeňme, že v každém kroku šifrování je pro každý disk Je to pozice, která odpovídá prvnímu obvodu prostoru
aktivní právě jedna pozice.
. Aktivní je ta pozice, u které se
v daném kroku kontroluje přítomnost kolíčku, a která tak určuje, o kolik se v daném kroku disky s vložkou otočí. Protože změna aktivní pozice disku označíme ji také
odpovídá jeho otáčení,
.
Nyní se podívejme, co se stane, když na prvním disku přijde impuls na drát
.
V závislosti na natočení disku, posunu komutační vložky v jeho středu a zapojení komutační vložky impuls odejde po drátě
, kde
Podobně se spočte
. Zbývá definovat komutátor, který se při šifrování aplikuje nejdříve. Označme jeho permutaci jako Počáteční obvod s impulsem označme jako a
počítejme
Nyní již víme, jak impuls šifrátorem prochází
,
a
. Na výstupním zařízení bude aktivní obvod Označme nyní
pravdivostní hodnotu, která udává, zda-li je v disku
Podívejme se, jak se změní hodnoty
na
v jednom kroku stroje.
28
kolíček.
konečně
Přičemž sčítání booleovských hodnot chápeme tak, že true je a false je 0.
Vzhledem k tomu, že hodnoty
jsou v průběhu práce konstantní a hodnoty
stejně při šifrování i dešifrování, můžeme hodnotu zjednodušeně jako Výstupní hodnota
se mění
v jednom kroku zapsat
. při šifrování znaku pak je
Impuls při dešifrování cestuje šifrovou jednotkou v opačném směru. Ze zápisu je proto také vidět, že dešifrováním šifrového textu získáme správný otevřený text:
29
7.
Simulátor
Součástí práce je simulátor stroje ŠD-2, resp. jeho ruského vzoru CM-I. Je umístěn na přiloženém DVD a na doprovodných webových stránkách [7]. Ovládání je snadné a intuitivní, všechny funkce jsou dostupné přes hlavní menu. V programu je také uživatelská nápověda, která detailněji popisuje nastavení jednotlivých funkcí stroje. Rozhraní i nápověda jsou pro univerzálnější použití v anglickém jazyce. Program funguje pod operačním systémem Windows, pro jeho správnou funkci je nutné prostředí .NET Framework 3.5, které je dodáváno spolu s programem. Byl použit programovací jazyk C# ve verzi 3.5 z roku 2008 a značkovací jazyk XAML. Tyto moderní technologie si vybraly svou daň v podobě pomalejšího startu programu a také jeho menší přenositelnosti na starší počítače a alternativní operační systémy.
Po spuštění programu je přístroj přednastaven dle testovacího nastavení popsaného v Apendixu A. Změnu nastavení lze provést pod položkou menu Settings, a to buď načtením konfiguračního souboru, nebo ručním nastavením jednotlivých položek. Před samotnou prací šifrátoru je potřeba zvolit mód, to provedeme v menu pod položkou Cipher Mode. 30
Program zpracovává data zadaná buď postupně z klávesnice, anebo jako celý vstupní soubor. V druhém případě je výstup uložen do souboru. Tato akce může pro velké vstupní soubory trvat i několik minut. Program je stále ve vývoji a další verze včetně opravy případných chyb budou publikovány na webových stránkách.
7.1.
Licence
Program je distribuován pod následující licencí: © 2009, Vojtěch Brtník – www.brtnik.eu. Všechna práva vyhrazena. Redistribuce a použití programu, v původním tvaru, jsou povoleny za následujících podmínek: -
-
Program je distribuován zdarma. Šířený binární tvar musí nést výše uvedenou informaci o copyrightu, tento seznam podmínek a níže uvedené zřeknutí se odpovědnosti ve své dokumentaci a dalších poskytovaných materiálech. Ani jméno autora, ani jména přispěvatelů nemohou být použita při podpoře nebo právních aktech souvisejících s produkty odvozenými z tohoto software bez výslovného písemného povolení.
Tento software je poskytován držitelem licence a jeho přispěvateli „jak stojí a leží“ a jakékoliv výslovné nebo předpokládané záruky včetně, ale nejen, předpokládaných obchodních záruk a záruky vhodnosti pro jakýkoliv účel jsou popřeny. Držitel, ani přispěvatelé nebudou v žádném případě odpovědni za jakékoliv přímé, nepřímé, náhodné, zvláštní, příkladné nebo vyplývající škody jakkoliv způsobené na základě jakékoliv teorie o zodpovědnosti, ať už plynoucí z jiného smluvního vztahu, určité zodpovědnosti nebo přečinu (včetně nedbalosti) na jakémkoliv způsobu použití tohoto software, i v případě, že držitel práv byl upozorněn na možnost takových škod. Zdrojový kód je vlastnictvím autora a není poskytován. Program nemůže být redistribuován v upravovaném tvaru.
31
8.
Závěr
Účelem bakalářské práce bylo představit odborné veřejnosti šifrový stroj ŠD-2 a jeho ruský protějšek CM-I. Stroj ŠD-2 podléhal až do nedávné doby v ČR utajení a stroj CM-I je v Ruské federaci stále utajován. Byla provedena pravděpodobná rekonstrukce strojů na základě dostupných materiálů, záznamů pamětníků a částečně dochované dokumentace. Na základě získaných dat byl také vytvořen programový model šifrátorů. Žádná odborná publikace na toto téma s výjimkou dvou zevrubných článků [5] a [6] zatím nebyla vydána. Kompletní mechanický model včetně popsané obrazové dokumentace, tak jak se jej podařilo sestrojit, je k dispozici na webových stránkách projektu [7]. V textu jsme ze zaměřili pouze na historii, základní podstatu fungování stroje a popis hlavních částí. Z kryptologického hlediska jsme detailně prozkoumali fungování šifrovací jednotky a klíčovou politiku. Byla provedena řada statistických testů a naznačen matematický model fungování stroje. Součástí práce mělo být odhalení slabiny stroje. Žádný větší nedostatek ale nebyl zjištěn a otázka úspěšné kryptoanalýzy tak zůstává otevřena. Práce otevřela mnoho cest k dalšímu zkoumání obou strojů. Které klíče jsou slabší, které silnější a při jakém nastavení stroje je možné prolomení? Jak moc je stroj odolný vůči chybám obsluhy, např. šifrování více zpráv jedním klíčem či naopak šifrování jedné zprávy více klíči? Do těchto úvah jsme se v práci nepustili zejména proto, že žádné klíče či odchytnuté zprávy nebyly u stroje CM-I zjištěny. Z historického hlediska je dále zajímavá role stroje CM-I v Sovětském svazu. Oba šifrátory jsou jistě zajímavými mezníky v dějinách svých států, zdrojem inspirace, ponaučení a obrazem své doby a zasloužily si pozornost, která jim až zásluhou této práce byla věnována.
32
9.
Literatura
Literatura je citována dle normy ČSN ISO 690:1987 (vydaná ČNI v prosinci 1996 s účinností od 1.1.1997) a ČSN ISO 690-2:1997 (vydaná v lednu 2000 s účinností od 1.2.2000), které jsou určené pro přípravu seznamů bibliografických odkazů na dokumenty, resp. informační zdroje, i jejich citace. [1]
REJEWSKI, Marian: How Polish Mathematicians Deciphered the Enigma. Annals of the History of Computing, 1981, vol. 3, no. 3.
[2]
CARTER, F: Codebreaking with the Colossus Computer. Bletchley Park Report #1 – #3.
[3]
HAGELIN, Boris C.W.; KAHN, David. The Story of the Hagelin Cryptos. Cryptologia. 1994, vol. 18, issue 3, 204–242.
[4]
KAHN, David. The Codebreakers. 2nd edition. Scribner, 1996. Chapter 13, p. 426–427. ISBN 0-684-83130-9.
[5]
ŠKLÍBA, Karel: Z dějin československé kryptografie, část V., Československé šifrovací stroje z období 1955 – 1960. Šifrovací stroj ŠD – 2 (1. díl). Crypto-World. 2008, vol. 1.
[6]
ŠKLÍBA, Karel: Z dějin československé kryptografie, část VI., Československé šifrovací stroje z období 1955 – 1960. Šifrovací stroj ŠD – 2 (2. díl). Crypto-World. 2008, vol. 3.
[7]
Online prezentace šifrátorů ŠD-2 a CM-I. Dostupný z WWW:
[8]
ŠKLÍBA, Karel: Z dějin československé kryptografie, část VII., Československé šifrovací stroje z období 1960 – 1970. Šifrovací stroj ŠD – 3. Crypto-World. 2008, vol. 5.
[9]
SHANNON, C.E.: A Mathematical Theory of Communication. Bell System Technical Journal. 1948, vol. 27, 379-423, 623-656.
[10]
ŠKLÍBA, Karel. Z dějin československé kryptografie, část I. Československý šifrátor MAGDA. Crypto-World. 2007, vol. 5.
[11]
VONDRUŠKA, Pavel. Kryptologie, šifrování a tajná písma. Albatros, 2006. ISBN 80-0001888-8.
[12]
RALSTON, Anthony; REILLY, Edwin D. (ed.). Encyclopedia of Computer Science Third Edition. S. Baudot Code. IEEE Press/Van Nostrand Reinhold, 1993. ISBN 0-44227679-6.
[13]
KASISKI, F.W: Geheimschriften und die Dechiffrirkunst. Mittler und Sohn, 1963.
33
10.
Apendix A: Testovací nastavení a zpráva
10.1. Testovací nastavení V této sekci popišme základní nastavení stroje tak, jak jsme jej používali při všech testech a výpočtech. Jedná se o konkrétní stav přístroje v počáteční poloze po aplikování dlouhodobého klíče (nastavení kolíčků), denního klíče (nastavení komutačních vložek a pořadí disků) a jednorázového klíče (nastavení počátečního stavu disků). Toto nastavení je také implicitní v simulátoru, podporujeme čtenáře, aby si zkusil výpočty provést sám. V mnohém zachováme intuitivní nastavení stroje. Z hlediska testů není důvod měnit pořadí disků, neboť jde pouze o pojmenování předem dané permutace, kterou můžeme kdykoliv přečíslovat. Stejně tak všechny komutační vložky a disky v původní poloze můžou být v pozici A, neboť změna pozice pouze lehce změní použitou komutační vložku a posune permutaci. Pro výpočet základních vlastností šifry nemá toto nastavení žádný vliv. Použité permutační vložky a kolíčky se řídí následujícími tabulkami. V prvních dvou řádcích je definice použité permutace v komutační vložce; v dalším řádku pak umístění kolíčků: hodnota 1 znamená, že kolíček je v daném písmeni přítomen, 0 naopak. Pořadí disků:
1-2-3-4-5
Disk 1 A
B
C
D
E
F
G
H
I
J
K
L
M
H
Y
B
J
N
E
P
A
G
I
V
X
U
0
0
0
0
0
0
0
0
0
0
0
0
0
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
D
C
L
W
R
S
Z
T
Q
F
K
M
O
0
0
0
0
0
0
0
0
0
0
0
0
0
Název komutační vložky:
C
Nastavení komutační vložky:
A
Počáteční nastavení disku:
A
Poznámka: Nastavení kolíčků v disku 1 nic neovlivňuje a kolíčky proto nejsou nastaveny. Jsou zmíněny pouze pro zachování reality s vlastním strojem. Disk 2 A
B
C
D
E
F
G
H
I
J
K
L
M
F
Y
V
K
D
P
E
X
U
Z
T
W
B
0
1
0
1
0
0
0
1
0
0
0
0
0
34
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
H
J
O
I
C
N
G
R
S
Q
M
L
0
0
0
0
0
0
1
0
0
0
0
1
0
Název komutační vložky:
D
Nastavení komutační vložky:
A
Počáteční nastavení disku:
A
Disk 3 A
B
C
D
E
F
G
H
I
J
K
L
M
K
H
S
C
F
Q
W
G
I
T
D
Z
B
0
0
0
0
0
0
0
0
0
0
0
0
0
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
L
P
X
N
A
U
J
O
M
F
W
R
Y
1
0
0
0
0
1
1
0
0
0
0
0
0
Název komutační vložky:
E
Nastavení komutační vložky:
A
Počáteční nastavení disku:
A
Disk 4 A
B
C
D
E
F
G
H
I
J
K
L
M
H
K
Z
J
F
R
W
P
Y
E
T
S
B
0
0
0
0
0
0
0
1
0
0
0
0
1
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
G
V
Q
N
D
L
I
X
C
U
O
A
M
0
0
0
0
0
0
0
0
0
0
1
0
0
Název komutační vložky:
F
Nastavení komutační vložky:
A
Počáteční nastavení disku:
A
Disk 5 A
B
C
D
E
F
G
H
I
J
K
L
M
C
Q
Y
O
S
T
E
R
P
A
J
L
Z
1
1
0
0
0
0
0
0
0
0
0
0
0
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
H
V
B
G
I
N
U
X
M
F
D
W
K
1
1
0
0
0
0
1
0
0
0
0
0
1
35
Název komutační vložky:
G
Nastavení komutační vložky:
A
Počáteční nastavení disku:
A
Disk L A
B
C
D
E
F
G
H
I
J
K
L
M
Y
L
Q
Z
O
W
X
B
M
T
F
K
S
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
J
D
I
P
N
E
H
G
V
R
C
A
U
Název komutační vložky:
H
Nastavení komutační vložky:
A
Nastavení disku:
A
Poznámka: Kolíčky se v disku L nepoužívají. Komutátor A
B
C
D
E
F
G
H
I
J
K
L
M
S
T
L
A
O
K
F
X
E
C
J
Q
G
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
D
H
V
B
M
W
Y
U
R
P
Z
I
N
10.2. Testovací zpráva Pro frekvenční analýzu a další statistické testy posloupnosti generované šifrovým strojem ŠD-2 byl jako zdroj použit text knihy Kryptologie, šifrování a tajná písma [11] o délce cca 270 tisíc znaků (bez mezer). Pro představu uvádíme frekvenční analýzu otevřeného textu a jeho srovnání s očekávanou frekvencí češtiny. Frekvenční analýza testovaného otevřeného textu A
B
C
D
E
F
G
H
I
J
K
L
M
8,38
1,66
3,19
3,56
10,96
0,99
0,48
2,04
7,13
1,85
3,49
3,9
3,17
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
6,09
8,03
3,76
0,09
4,85
5,40
5,94
3,84
4,15
0,16
0,53
3,26
3,10
36
Frekvenční analýza typického textu českého jazyka: A
B
C
D
E
F
G
H
I
J
K
L
M
8,83
1,67
2,62
3,63
10,5
0,39
0,34
1,30
7,68
1,98
3,75
4,10
3,26
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
6,75
8,32
3,46
0,01
5,16
5,44
5,59
3,85
4,38
0,07
0,09
2,70
3,16
Je vidět, že frekvence jednotlivých písmen testovacího textu se drobně liší od očekávané frekvence češtiny. Je to z toho důvodu, že text je lehce odborný. Typická frekvence češtiny vlastně ani neexistuje, statistika je vytvářena na základě obsáhlého jazykového korpusu a také se může lišit dle použité metodiky a druhu textů, které jsou zpracovány. Uvádíme krátkou ukázku analyzovaného textu: Zlomkový šifrovací systém. Jedná se o speciální třídu šifrových systémů, které byly poměrně bezpečné a relativně jednoduché na realizaci. Svými parametry překonávají tyto systémy řadu jiných klasických šifrových systémů. Název zlomkový systém je odvozen z toho, že písmeno otevřeného textu je nejprve vyjádřeno pomocí dvojice čísel. Tato dvojice lze zapsat do podoby zlomku. Algoritmus pak pracuje zvlášť s hodnotami uvedenými ve jmenovateli nebo čitateli, šifrový text se pak získá opětovným převodem „zlomků“ (dvojic čísel) na písmena.
37
11. -
Apendix B: Obsah přiloženého DVD
Instalátor prostředí .NET Framework, které je potřebné pro správnou funkčnost simulátoru. Simulátor ŠD-2 a CM-1 Obrazová dokumentace strojů ŠD-2 a CM-I. Ukázkový vstup, na kterém je možno ověřit funkčnost simulátoru.
38
