Vedoucí: Ing. Vladimír Beneš Praha Duben 2013 Prohlášení

Příloha AA
Ukázka postupu při použití asymetrické šifry RSA

Tento postup je převzat z Příloha I.

Tajná komunikace probíhá mezi Alicí a Bobem. Eva se snaží odposlechnout zprávu.

Vytvoření klíče:

Příloha ABAlice si zvolí dvě velmi velká prvočísla. Ve skutečnosti se jedná o čísla o mnoha řádech, pro přehlednost v tomto příkladu použijeme čísla menší. Alice tedy volí .

Příloha ACTato čísla Alice mezi sebou vynásobí a dostává další číslo .

Příloha ADPoté zvolí další číslo .

Příloha AEČísla a by neměla mít společného dělitele.

Příloha AFAlice zveřejní a jako svůj veřejný klíč.

Šifrování zprávy:

Příloha AGŠifrovaná zpráva musí být převedena do čísla , jelikož nad ním budeme provádět matematické operace. Například převedením do ASCII kódu, který je reprezentován binárním kódem a lze použít také jeho desítkovou reprezentaci. Řekněme, že pro zašifrování zvolíme písmeno X. Toto písmeno má reprezentaci v kódu ASCII.

Příloha AHKdyž Bob bude chtít zprávu zašifrovat, vyhledá veřejný klíč Alice Tak získává pro zašifrování potřebný vzorec. Pro vypadá tento vzorec . Takto velké číslo by byl problém počítat na kalkulačce, tedy pomůžeme si trikem, jelikož :

Šifrovaný text, který pošle Bob Alici je tedy .

Příloha AIJelikož jsou mocniny v modulární aritmetice jednosměrné funkce, nelze jednoduše z  dostat otevřený text. Eva nemůže dostat otevřený text pouze z těchto informací. Alice však má pro dešifrování informaci navíc. Alice zná hodnoty a . Pomocí těchto informací si vypočítá soukromý klíč, který označíme :

K výpočtu použije Alice postup, známý jako Euklidův Algoritmus.

Dešifrování zprávy:

Příloha AJAlice k rozluštění zprávy potom použije následující postup:

Výsledkem dešifrovacího procesu je . Toto číslo reprezentuje zpět znak X v ASCII kódu.

Příloha AK
Ukázka frekvenční analýzy

Nejprve je třeba určit pro daný jazyk četnost jednotlivých znaků. Pokud budeme mluvit o frekvenční analýze českého jazyka, budeme pracovat pouze s abecedou bez rozlišení velkých a malých písmen a bez diakritiky. Usnadníme si tím odečítání výsledků a pro tuto ukázku nám takto zjednodušená sada znaků poslouží nejlépe.

Pro text, ze kterého odvodíme četnost znaku je lépe zvolit text dostatečně dlouhý a nejlépe, pokud se bude shodovat se zkoumaným textem svou podobou – tedy oba texty ze stejné doby, užívající stejné nářečí, stejnou abecední sadu apod. V naší ukázce jsme zvolili pro odečtení četností knihu Karla Čapka, Dášenka čili život štěněte. Takto analyzovaný vzorek obsahoval celkem 29455 znaků, což by mělo být dostatečné množství pro co nejpřesnější určení statistického zastoupení jednotlivých znaků v našem jazyce. Text byl převeden do podoby bez diakritiky – viz abeceda Graf .

V případě, že by si čtenář chtěl podobný vzorek připravit sám, lze stáhnout vybranou knihu např. na stránkách Městské knihovny v Praze (http://www.mlp.cz/cz/), kde v době psaní této práce lze nalézt rozsáhlé množství elektronických knih různých autorů v různých formátech. Takto získaný text je možné převézt do podoby bez diakritiky například na http://textmod.pavucina.com/odstraneni-diakritiky. Pro zjišťování četností v rámci frekvenční analýzy, ale i experimentování v různých jiných oblastech kryptografie, doporučuji program CrypTool 2, který lze stáhnout na stránkách http://www.cryptool.org/en/.
Graf : Frekvenční analýza zastoupení českých znaků v díle Karla Čapka, Dášeňka čili život štěněte, řazeno abecedně

(zdroj: vlastní úprava)
Graf : Frekvenční analýza zastoupení českých znaků v díle Karla Čapka, Dášeňka čili život štěněte, řazeno sestupně podle zastoupení

(zdroj: vlastní úprava)

Nyní lze přistoupit k samotnému šifrovému textu. Mějme zprávu, která bude zašifrována: Wnrfsj efafijon pwduytlwfknn it xajmt atojsxyan. A yjyt itgj xj it ijons pwduytlwfknj sfaeid efunxzoj orjst Ozqnf Hfjxfwf, pyjwd zenaf ojistizhmj xzgxynyzhsn xnkwd uwn atojsxpdhm yfejsnhm uwt ptrzsnpfhn rjen xadrn tiinqd. Yfyt ajqrn ojistizhmf xzgxynyzhj xuthnafqf a utxzsz fgjhjid tyjawjsjmt yjcyz t ywn rnxyf ituwfaf.

Graf : Frekvenční analýza zastoupení znaků v šifrované zprávě, řazeno abecedně

(zdroj: vlastní úprava)
Graf : Frekvenční analýza zastoupení znaků v šifrované zprávě, řazeno sestupně podle zastoupení

(zdroj: vlastní úprava)

Z analýzy textu nám vyplývá, že čtyři nejvíce zastoupené znaky jsou J, N a F. Podle analýzy českého jazyka na vzorku od Karla Čapka víme, že čtyři nejčastější písmena v otevřeném textu jsou E, A a O. Pojďme si tedy zkusit nahradit nejčetnější znak šifrového textu J nejčetnějším znakem z naší analýzy českého jazyka – E (viz Tabulka ). Pokud dále budeme zkoumat šifrovaný text, tak zaznamenáme písmena, která jsou ve větě sama. V češtině by se mohlo jednat nejčastěji o A, nebo O. Obě jsou shodou okolností ve třetici nejčetnějších znaků. Tedy by je měl v šifrovém textu reprezentovat znak N, nebo F. Žádné takové písmeno se nám v textu ale neobjevuje. Vidíme pouze T a A. Pokud se tedy zaměříme na fakt, že A, nebo O, by mohlo být v šifrovém textu reprezentováno písmenem T, nebo A, měli bychom tato dvě písmena vidět ve frekvenční analýze mezi nejčetnějšími znaky šifrového textu. Skutečně, hned čtvrtým nejčastějším znakem v šifrovém textu je znak T. Pojďme tedy prozkoumat situaci, kdy budeme písmeno T považovat za A, nebo O.

Pokud se navíc pečlivěji zadíváme, najdeme výskyt několika slov o dvou znacích, které končí znakem T (tedy buď A, nebo O), podle toho, který z těchto znaků předpokládáme. Pokud by dvojpísmenné slovo mělo končit na A, bude před ním nejspíš znak N, jako předložka „na“. Pokud budeme uvažovat O, bude před ním pravděpodobně D, jako v předložce „do“.

Také vidíme dvoupísmenné slovo, které podle našeho předchozího dosazení pravděpodobně končí na E, a první písmeno by svou četností mělo být na pátém pořadí. Pokud si tuto oblast četností otevřené abecedy prohlédneme, najdeme písmeno S a v jeho okolí I a N. I můžeme ze znalosti češtiny vynechat. Zbývají dvojice „se“ a „ne“. Ne je velmi častou předponou na začátku slov, ale už ne tak častým samostatným slovem. V tomto kontextu je „se“ častější. Pojďme tedy dále předpokládat, že X je náhradou za S.

Pokud budeme analyzovat, která nejčetnější písmena ještě nemáme využita, najdeme písmeno N v šifrové abecedě (na druhém místě) a písmeno I v otevřené abecedě (na čtvrtém místě). Pojďme tedy zkušebně provést náhradu N za I.

Text se nám postupně doplňuje, a i když se některá slova zdají být patrná, stále ještě nelze s určitostí říci, zda se ve svém pátrání vydáváme správným směrem. Jeden fakt byl při našem hledání opomenut. Je to (dokonce druhé nejpočetnější) písmeno šifrové abecedy F. Jeho čestnost je tak vysoká, že si již nemůžeme dovolit jej ignorovat. Ale které písmeno otevřené abecedy doplnit? Máme již obsazena písmena otevřené abecedy až do šesté pozice. To vypadá velmi zvláštně až do okamžiku, kdy si uvědomíme, že jsme si nebyli jisti u dvou písmen s podobnou četností a tak jsme zkoušeli dosadit obě. Jednalo se o písmena A a O. Pojďme tedy zkusit za F dosadit v jedné verzi otevřeného textu písmeno O a v druhé A (vždy opačné k tomu, které jsme již dosadili v minulých pokusech).

Další k záměně se nabízí Y z šifrového textu, které by mohlo být nahrazeno dalším nejpočetnějším a zároveň nedosazeným písmenem T.

Nyní jsme dospěli k zásadnímu objevu. Soustřeďme se na chvíli na začátek poslední věty. Šifrový text Yfyt může být buď slovo „Tota“, nebo „Tato“ v otevřeném textu. Je zřejmé, že první varianta nedává smysl, proto můžeme s konečnou platností prohlásit za platnou druhou variantu. První škrtneme a nadále se budeme věnovat pouze variantě v druhém řádku. Je také velmi důležité si uvědomit, že nám z otevřeného textu tímto krokem zcela zmizelo, početním zastoupením velmi významné, písmeno N. Měli bychom tedy prozkoumat, jakému znaku šifrové abecedy ho lze nově přiřadit.

Nejvýše zastoupené ze zbývajících znaků je A. Zkusme tedy A nahradit písmenem N. Po doplnění tohoto znaku ale pozornému luštiteli neunikne fakt, že druhá věta začíná textem „N teto do_e se do de_i_“. Je velmi pravděpodobné, že máme v dosazení chybu. Přímo se nabízí, aby věta začínala „V této době…“ (nezapomeňme, že text neobsahuje diakritiku).

Pojďme tedy nyní zkusit na chvíli předpokládat, že naše substituce byl špatný krok a změňme náhradu na . Text nyní vypadá daleko lépe.

Dále zkusme trochu více analyzovat text místo dalšího doplňování. Zkopírujeme si již doplněný text na nový řádek a další doplňovaná písmena zapisujme červeně. Páté slovo první věty má aktuálně podobu „sve_o“. Pokud se postupně pokusíme doplnit jednotlivé znaky abecedy za chybějící znak, nalezneme pouze jednu nejpravděpodobnější podobu tohoto slova: „svého“. Pojďme tedy doplnit do textu substituci . Dále deváté slovo poslední věty obsahuje konstrukci „otev_e_eho“. Toto slovo nelze upravit jinak, než do tvaru „otevřeného“. Z toho vyplývá a . Třinácté a čtrnácté slovo jsou také velmi nápadné. Text „o tri _ista do_rava“ snad nelze doplnit jinak než „o tři místa doprava“. Tedy proveďme záměny a . Dále se nabízí slovo „vo_enstvi“, které vhodně nahradí slovo „vojenství“. Tedy . Nyní se již další písmena nabízejí velmi rychle. Třetí slovo druhé věty „V této do_e se do dějin“ znamená záměnu . Dále věta „V teto dobe se do dejin _r_pto_ra_fie nav_d_ _apis_je jmeno“ znamená náhrady , , . Druhá část prvního souvětí má nyní následující podobu: „_tery uziva jednodu_he sustitu_ni si_ry pri vojens_y_h tazeni_h pro _omuni_a_i mezi svymi oddi_y“. Bez výrazného zkoumání můžeme říci, že zde dojde k náhradám , , a . Poslední části substituce odvodíme ze slov „krypto_rafie“ a „s_ocivala _ posunu abecedy te_tu o tri mista“. Odtud poslední záměny , , a .

Wnrfsj efafijon pwduytlwfknn it xajmt atojsxyan. A yjyt itgj xj it ijons pwduytlwfknj sfaeid efunxzoj orjst

i o e o one i ta o ii na s e a a e st i teta na e se na ne i ta o ie o n o is e e a i a e anade i to a ii do sne o no e stni. N teto do e se do de i to a ie an d a is e e o i a e avade i to a ii do sve o vo e stvi. V teto do e se do de i to a ie av d a is e e o Rimane zavadeji krypto rafii do sveho vojenstvi. V teto dobe se do dejin kryptografie navzdy zapisuje jmeno

Ozqnf Hfjxfwf, pyjwd zenaf ojistizhmj xzgxynyzhsn xnkwd uwn atojsxpdhm yfejsnhm uwt ptrzsnpfhn rjen xadrn tiinqd.

i oeso o, te i o en an e s stit i si i a e s to e i a a i o i e i s i anni . ia aesa a, te ina ed od e s stit i si i no e s ta e i o o i a i e i sn i oddi . ia aesa a, te iva ed od e s stit i si i vo e s ta e i o o i a i e i sv i oddi . Julia Caesara, ktery uziva jednoduche substitucni sifry pri vojenskych tazenich pro komunikaci mezi svymi oddily.

Yfyt ajqrn ojistizhmf xzgxynyzhj xuthnafqf a utxzsz fgjhjid tyjawjsjmt yjcyz t ywn rnxyf ituwfaf.

Tota e i en an o s stit e s a i o o as o e en ate e e a te t a t i isto na o o Tato ne i ed od a s stit e s o ina a os a e ed oten e e o te t o t i ista do ana. Tato ve i ed od a s stit e s o iva a os a e ed otev e e o te t o t i ista do ava. Tato velmi jednoducha substituce spocivala v posunu abecedy otevreneho textu o tri mista doprava.

Tabulka : Převod šifrového textu – záměna písmen

(zdroj: vlastní úprava)

Na závěr se tedy dozvídáme, že předlohou pro šifrový text byla část prvního odstavce z kapitoly B.1.7.

1^ V případě čtenářova zájmu o podrobnou historii tohoto velmi zajímavého oboru doporučuji knihy The Codebreakers (anglicky) od Davida Kahna Příloha J, nebo Kniha kódů a šifer od Simona Singha Příloha O. První jmenovaná je považována v současnosti za nejúplnější přehled historie kryptologie, druhá je o poznání stručnější, avšak v českém jazyce a velmi příjemně čtivá.

2^ Příběh Enigmy velmi zajímavě popisuje mnoho knih. Pro zájemce doporučuji např. Příloha N, viz použitá literatura.

3^ Dne 3. prosince 2012 předvedl Jeremi Gosney, CEO společnosti Stricture Consulting Group (http://stricture-group.com), na konferenci o bezpečnosti Password^12, klastr pěti 4U serverů, osazených 25 AMD Radeon grafickými čipy (GPU). Tato sestava obsahovala 10 grafických karet HD 7970, 4 grafické karty HD 5970 (po dvou GPU každá), 3 grafické karty HD 6990 (po dvou GPU každá) a jednu grafickou kartu HD 5870. Spotřeba této sestavy byla 7kW a umožňovala vyzkoušet za sekundu 350 miliard klíčů kryptografického algoritmu NTLM od společnosti Microsoft, kterým jsou vybaveny všechny verze Windows od verze Server 2008. Tento stroj umožnil odhalení typického šifrového klíče do šesti hodin.

4^ Jako reference pro kapitoly, využívající fyzikálních formulací a popisující fyzikální zákony bylo užito projektu Encyklopedie Fyziky autorů Jaroslava Reichla a Martina Všetičky, dostupné z: http://fyzika.jreichl.com.

5^ Na toto téma lze nalézt mnoho informačních zdrojů na internetu, proto se nebudeme tímto pokusem blíže zabývat. Např. http://www.physics.rutgers.edu/~motl/brian/ves-04lm.html.

6^ Blíže o principu neurčitosti: http://cs.wikipedia.org/wiki/Princip_neur%C4%8Ditosti

7^ Ve skutečnosti se jedná o vlastnost částice, která nemá v naší makroskopické fyzice analogii. Spin je popsán jako vektor vnitřního momentu hybnosti, který může mít dvě orientace a kvantové velikosti (v násobcích redukované Planckovy konstanty ћ).

8^ Anglicky: QKD – Quantum Key Distribution

9^ Zdroj: Příloha K, Příloha L

10^ PNS – photon number spliting – v praxi se k vysílání neužívá pouze jednoho fotonu, ale krátký signál koherentního světla, vyslaný laserem. To samo o sobě otevírá možnosti PNS útoku, během kterého útočník oddělí část tohoto záření k vlastní činnosti.

11^ Secure Communication based on Quantum Cryptography

12^ Úplný popis projektu včetně implementovaných technologií lze nalézt na www.secoqc.net

13^ Austrian Institute of Technology

14^ Quantum Back-Bone

15^ European Telecommunications Standards Institute

16^ Zdroj Příloha Q

17^ Defense Advanced Research Project Agency, od roku 1972 jen ARPA, rozpočet cca 3,2 mld. dolarů

18^ Takto jí označuje Chip Elliott, vedoucí inženýr výzkumu Raytheon BBN Technologies

19^ National Institute of Standard and Technology

20^ Zdroj informací: http://www.uqcc.org/QKDnetwork/index.html

21^ Updating Quantum Cryptography and Communications

22^ Japan’s Gigabit Network

23^ Kompletní specifikace na: http://idquantique.com/company/presentation/52.html

24^ Více informací o Národním bezpečnostním úřadu lze získat na www.nbu.cz

25^ Znění zákona ve znění pozdějších předpisů lze nalézt například na http://www.nbu.cz/download/nodeid-618/

26^ Více o projektu na http://www.isvav.cz/projectDetail.do?rowId=GA201%2F01%2F0413 a http://www.muni.cz/research/projects/932?lang=cs

27^ Více o projektu na http://www.isvav.cz/projectDetail.do?rowId=GA201%2F04%2F1153 a http://www.muni.cz/research/projects/1587

28^ Více o projektu na http://www.isvav.cz/projectDetail.do?rowId=GA201%2F07%2F0603 a http://www.muni.cz/research/projects/2976

29^ Více o projektu na http://www.isvav.cz/projectDetail.do?rowId=GA202%2F95%2F0002

30^ Více o projektu na http://www.isvav.cz/projectDetail.do?rowId=GP201%2F06%2FP338 a http://www.muni.cz/research/projects/2412

31^ Více o projektu na http://www.isvav.cz/projectDetail.do?rowId=GP202%2F03%2FD239

32^ Více o projektu na http://www.isvav.cz/projectDetail.do?rowId=RN19951997007

33^ Více o projektu na http://www.isvav.cz/projectDetail.do?rowId=SU19982003011

34^ Více o projektu na http://www.isvav.cz/projectDetail.do?rowId=SU19982003012

35^ Více o projektu na http://www.isvav.cz/projectDetail.do?rowId=SU19982003013

36^ Více o projektu na http://www.isvav.cz/projectDetail.do?rowId=SU19982003014

37^ Více informací o projektu na http://www.isvav.cz/projectDetail.do?rowId=1ET300100403