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

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

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

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.

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.

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.