Úvod do kryptografie

Představ si, že žiješ ve světě, kde každý může číst tvoje zprávy. Pošleš kamarádovi tajný dopis? Nepřítel si ho po cestě přečte. Chceš si napsat do deníku svá tajemství? Někdo si ho otevře a zjistí vše. Jsi král a chceš svému generálovi poslat rozkaz? Pokud se dostane do rukou nepřátel, můžeš přijít o celou armádu.

A teď si představ svět, kde existuje zámek na informace – kde můžeš skrýt svou zprávu tak, že ji pochopí jen ten, kdo zná správný klíč. To je kryptografie – umění tajných zpráv, které lidé vymýšlejí už tisíce let.

Ale kryptografie má protivníka – kryptoanalýzu. Ta se snaží tajemství prolomit, rozluštit cizí zprávy a zjistit, co se skrývá pod vrstvou šifrování.

Obě tyto disciplíny spadají pod kryptologii – vědu, která se zabývá tím, jak utajit a odhalit informace. A právě kryptologie je dnes základem digitální bezpečnosti – chrání naše bankovní účty, hesla i soukromé zprávy.

Kryptologie, kryptografie, kryptoanalýza

Pojmy kryptografie, kryptoanalýza a kryptologie se často zaměňují, ale každý znamená něco jiného.

• Kryptologie je velká věda, která se zabývá všemi metodami šifrování a jejich luštěním. Pod ni spadá:
  • Kryptografie je část kryptologie, která vymýšlí šifry a metody, jak bezpečně skrývat zprávy.
  • Kryptoanalýza je zase ta část, která se snaží šifry prolomit a najít v nich chyby.

Základní pojmy

Než se ponoříme hlouběji do světa moderního šifrování, musíme si upevnit základy. Kryptografie není jen o „zamykání a odemykání“ zpráv, ale o celém systému pravidel, metod a pojmů, které dohromady tvoří pevný bezpečnostní štít.

Klíč

Všechno šifrování stojí na klíči. Je to tajná informace, která určuje, jak se zpráva zašifruje a jak ji můžeme dešifrovat zpět do čitelné podoby.

Představ si klíč jako kód k trezoru. Pokud neznáš správný kód, trezor neotevřeš. Stejně tak, pokud neznáš správný šifrovací klíč, nemůžeš zprávu rozluštit.

V Caesarově šifře je klíčem číslo posunu v abecedě, ve Vigenèrově je klíčem tajné slovo a v moderních šifrách, např. AES nebo RSA je klíčem velké číslo s desítkami až stovkami bitů, které se generuje náhodně a je prakticky neprolomitelné.

Otevřený a šifrovaný text

Každý zpráva má dvě podoby:

• otevřený text (plaintext) – normální zpráva, kterou chceme zašifrovat
• šifrovaný text (ciphertext) – podoba zprávy po zašifrování, vypadá jako nějaký nesmysl

Pokud neznáš správný klíč, nemůžeš se dostat zpět k otevřenému textu.

Bez klíče je šifrovaný text jen nesmyslná změť znaků.

Algoritmus

Šifrovací algoritmus je matematický postup, podle kterého se zpráva převádí na šifrovaný text a zase zpět. Pokud chceš zašifrovat zprávu, musíš použít správný algoritmus a klíč.

Čím je algoritmus složitější, tím je šifra bezpečnější.

Hashovací funkce

Hashování je jiný druh kryptografie – nelze ho zpětně dešifrovat.

Když něco zahashujeme, vytvoříme z toho otisk (hash) – jedinečný řetězec znaků, který se už nikdy nedá převést zpět na původní text.

Například slovo HESLO po převodu na hash vypadá takto: 5e884898da28047151d0e56f8dc6292773603d0d6aabbddc2f3bc4b929

Hashování se používá pro ochranu hesel, digitální podpisy nebo zabezpečení souborů.

Hashování je nevratné – nelze ho dešifrovat zpět.

Digitální podpis

Pokud ti přijde e-mail od banky, jak poznáš, že ho neposlal hacker? K tomu slouží digitální podpis.

Digitální podpis ověřuje pravost zprávy – dokazuje, že zprávu skutečně poslal daný člověk a že nebyla po cestě změněna.

Používá kombinaci hashování a asymetrického šifrování, aby bylo nezfalšovatelné.

Digitální podpisy se používají v e-mailové komunikaci, při podpisu smluv, certifikáty na webových stránkách nebo při podepisování softwaru.

Historie

Šifrování je vlastně způsob, jak utajit zprávu, aby jí rozuměl jen ten, kdo ji má číst. A proč to bylo v historii tak důležité? Představ si, že jsi král a chceš poslat tajnou zprávu svému generálovi. Pošleš posla s dopisem, ale co když ho cestou chytí nepřítel? Pokud by byla zpráva napsaná normálně, mohl by si ji přečíst a zjistit tvoje plány. Ale kdyby byla zašifrovaná, nepřítel by viděl jen nesmyslné znaky a nic by nepochopil.

Šifrování se hodilo hlavně ve třech oblastech:

• války – vojevůdci si mezi sebou posílali tajné rozkazy, aby je nepřítel neodhalil,
• diplomacie – králové si vyměňovali tajné zprávy, aby se domluvili na aliancích nebo intrikách,
• obchod – kupci si mezi sebou posílali informace o cenách zboží, aby je konkurence nepodrazila.

Caesarova šifra

Představ si, že chceš napsat tajnou zprávu kamarádovi, ale bojíš se, že ji někdo cestou najde a přečte. Jak to zařídit, aby tomu nikdo jiný nerozuměl? Řešení je jednoduché – změníš písmena ve zprávě tak, aby dávala smysl jen tomu, kdo ví, jak je přeložit zpět. A přesně takto přemýšlel i slavný římský vojevůdce Julius Caesar, když před více než 2000 lety potřeboval posílat tajné rozkazy svým vojákům.

Caesarova šifra je substituční šifra, což znamená, že každé písmeno v otevřené zprávě zaměníme za jiné písmeno podle pevně daného pravidla. Toto pravidlo je jednoduché – každé písmeno v abecedě posuneme o určitý počet míst doprava.

Například, pokud se rozhodneme posunout o 3 místa, písmeno A se změní na D, B na E, C na F a tak dále. Když dojdeme na konec abecedy, začneme znovu od začátku (Z → C, Y → B).

My budeme používat Caesarovu šifru pouze na znacích v ASCII tabulce (tedy bez diakritiky a bez písmena CH).

Například text AHOJ zašifrujeme s posunem 3. Text po zašifrování je DKRM. Protože A+3 = D, H+3 = K (písmeno CH jsme přeskočili), a tak dále.

Následně můžeme text zpátky dešifrovat pomocí stejného posunu zpět. Takže D-3 = A, K-3 = H a dále. Takhle se dostaneme zpět ke slovu AHOJ.

To znamená, že pokud znáš posun (kterému říkáme šifrovací klíč), můžeš zprávu snadno přečíst.

Dnes by Caesarova šifra už žádnou zprávu neochránila. Proč?
Protože má jednu obrovskou slabinu – je strašně jednoduchá!

Pokud neznáš klíč (tedy kolik písmen bylo posunuto), stačí vyzkoušet všechny možné posuny. Abeceda má jen 26 písmen, takže maximálně 25 pokusů a vždy se dostaneš ke správné zprávě.
Navíc, pokud je zpráva delší, můžeš si pomoci frekvenční analýzou – nejčastěji se v češtině vyskytuje třeba písmeno E, takže pokud je nějaké písmeno v šifrované zprávě extrémně časté, pravděpodobně bude právě „E“ a od něj můžeš dopočítat celý klíč.

Vigenèrova šifra

Caesarova šifra byla skvělá na svůj čas, ale měla jeden velký problém – byla příliš jednoduchá. Jakmile někdo zjistil, že se písmena jen posouvají o pevný počet míst, stačilo vyzkoušet všechny možnosti a šifra byla prolomena.

Lidé ale nechtěli, aby jejich tajné zprávy byly tak snadno rozluštitelné. A tak se zrodila Vigenèrova šifra – metoda, která přidala do šifrování další vrstvu složitosti a dokázala odolat prolomení po stovky let!

Na rozdíl od Caesarovy šifry, kde se všechna písmena posouvala stejně, Vigenèrova šifra každé písmeno šifruje jiným posunem. A co určuje ten posun? Tajné klíčové slovo!

Jak šifra funguje?

Vybereme klíčové slovo, například heslo, které se opakuje nad šifrovaným textem. Čím delší klíč, tím složitější šifra.

Takže máme otevřený text TAJNAZPRAVA a k němu klíč HESLOHESLOH. Vidíš, že jsme klíčové slovo opakovali tak, aby bylo stejně dlouhé jako zpráva? To je důležité!

Pro šifrování používáme Vigenèrovu tabulku – matematickou tabulku, která kombinuje 26 Caesarových šifer. Každý řádek tabulky odpovídá Caesarově šifře s jiným posunem.

Zdroj obrázku: https://wikisofia.cz/wiki/Vigen%C3%A8rova_%C5%A1ifra

Každé písmeno zprávy se šifruje podle odpovídajícího písmene v klíčovém slově.

Chceme zašifrovat text „TAJNA ZPRAVA“ s klíčovým slovem „HESLOHESLOH„.

• Najdeme první písmeno zprávy (T) a odpovídající písmeno v klíči (H)
  • v řádku „H“ v tabulce najdeme sloupec „T“ → dostaneme A
• Druhé písmeno zprávy (A) a odpovídající klíč (E)
  • v řádku „E“ najdeme „A“ → dostaneme E
• Třetí písmeno zprávy (J) a klíč (S)
  • v řádku „S“ najdeme „J“ → dostaneme B

Pokračujeme stejným způsobem.

Původní text	T	A	J	N	A	Z	P	R	A	V	A
Klíčové slovo	H	E	S	L	O	H	E	S	L	O	H
Šifrovaný text	A	E	B	Y	O	F	T	I	L	J	H

Zašifrovaná zpráva je tedy „AEBYOF TILJH“.

Dešifrování probíhá opačně. Podíváme se na písmeno v klíči, najdeme odpovídající řádek v tabulce a pak zjistíme, které písmeno v tom řádku odpovídá zašifrovanému písmenu.

Pokud bychom dostali „AEBYOF TILJH“, vzali bychom klíčové slovo „HESLOHESLOH“ a podívali se do tabulky.

Matematik Charles Babbage ji nakonec prolomil pomocí frekvenční analýzy – sledoval, která písmena se v šifře opakují a jak často. Jakmile zjistil délku klíčového slova, mohl zprávu rozdělit na několik Caesarových šifer a rozluštit ji. Vigenèrova šifra byla silná, ale ne dokonalá. S dostatečně dlouhým textem a analýzou písmen ji šlo prolomit. Proto ji dnes nahrazují moderní matematické algoritmy jako AES nebo RSA, které jsou mnohem složitější a bezpečnější.

Enigma

Jednoduché šifry jako Caesarova nebo Vigenèrova už nestačí – nepřítel je dokáže prolomit. Potřebuješ něco mnohem složitějšího, něco, co si nikdo nedokáže jen tak rozluštit.

A právě proto Němci během 2. světové války začali používat Enigmu – šifrovací stroj, který měl být neprolomitelný. Kdyby opravdu zůstal neprolomitelný, možná by válka dopadla úplně jinak…

Enigma nebyla obyčejná šifra napsaná na papír. Byl to elektromechanický šifrovací stroj, který vypadal trochu jako psací stroj. Měl klávesnici, světelnou tabulku a několik otočných kotoučů. Každé písmeno, které jsi napsal, prošlo přes tyto kotouče a změnilo se na jiné písmeno.

Když jsi na Enigmě stiskl písmeno A, mohlo se změnit třeba na X. Když jsi stiskl A znovu, mohlo se ale tentokrát změnit na M.

Proč? Protože uvnitř Enigmy byly rotory – otočné kotouče, které se po každém stisknutí klávesy posunuly. To znamenalo, že stejné písmeno se pokaždé zašifrovalo jinak.

Enigma se skládala z těchto částí:

• klávesnice – napsal jsi písmeno, ale nešlo rovnou do šifry. Nejprve prošlo složitým systémem uvnitř stroje,
• rotory – tři až pět otočných kotoučů, které měnily písmena na základě elektrických obvodů uvnitř,
• odrazový (reflektorový) disk – zajišťoval, že šifrování bylo symetrické (když „A“ bylo šifrováno jako „X“, tak „X“ se při dešifrování změnilo zpět na „A“),
• zapojovací deska – Němci si mysleli, že samotné rotory nejsou dost bezpečné, tak přidali možnost manuálně prohazovat písmena. Tím vzniklo mnohem víc možných kombinací.

Výsledkem bylo, že Enigma měla kolem 150 kvintilionů možných nastavení – číslo tak obrovské, že kdyby ses ho snažil napsat, zabralo by několik řádků.

Pokud jsi neznal správné nastavení rotorů a zapojovací desky, musel bys vyzkoušet 150 000 000 000 000 000 000 (150 kvintilionů) možností, což bylo pro člověka nemožné. Na rozdíl od Caesarovy šifry nebo Vigenèrovy šifry, kde se vzory daly odhalit, Enigma zašifrovala stejné písmeno pokaždé jinak, což znemožňovalo frekvenční analýzu. Navíc, každý den se v německé armádě měnilo nastavení Enigmy podle tajného kódu, který znali jen vybraní důstojníci. I kdyby někdo prolomil Enigmu jeden den, druhý den už by to nefungovalo.

Přestože Enigma byla geniální stroj, měla slabinu – lidskou chybu.
Ještě před válkou polští kryptografové zjistili, jak Enigma funguje. Pomocí chytrých triků a prvních mechanických počítačů dokázali rozluštit některé zprávy.

Po začátku války Němci zlepšili Enigmu, ale Alan Turing a jeho tým vytvořili první skutečný počítač – Bombe, který dokázal rychle testovat možná nastavení Enigmy. Britové také zjistili, že němečtí operátoři často začínali zprávy stejnými slovy (např. „DRAHÝ ADOLFE“ nebo „POČASÍ DNES JE“), což jim pomohlo najít vzory a urychlit dešifrování.

Dnes máme mnohem lepší šifrovací metody, které nejsou závislé na mechanických strojích. Moderní šifrování je založeno na matematice a počítačových algoritmech, které jsou mnohem složitější a bezpečnější než Enigma.

Zdroj obrázku: https://en.wikipedia.org/wiki/Enigma_machine

Útoky na šifry

Vypadá to, že když zprávu zašifruješ, je navždy bezpečná, že? No… bohužel ne. Každá šifra má nějakou slabinu, a pokud je protivník dost chytrý (nebo má dostatečně výkonný počítač), může ji prolomit. Podíváme na nejčastější metody útoků na šifry a ukážeme si, proč historické šifry už dnes nejsou bezpečné.

Frekvenční analýza

Představ si, že jsi špión a podařilo se ti zachytit zašifrovanou zprávu. Nemáš klíč, nevíš, jak byla zpráva šifrována. Jak ji rozluštíš?

Tady přichází na řadu frekvenční analýza – metoda, která sleduje, jak často se jednotlivá písmena v textu vyskytují.

V každém jazyce se některá písmena objevují častěji než jiná. Například v češtině jsou nejčastější písmena „E“, „A“, „O“, „I“, „N“, zatímco písmeno „X“ se skoro neobjevuje.

Pokud zachytíme text zašifrovaný Caesarovou šifrou, můžeme spočítat, které písmeno se v něm vyskytuje nejčastěji. S velkou pravděpodobností to bude původní „E“, jen posunuté o několik míst. Jakmile to zjistíme, můžeme dopočítat celý klíč a šifru rozluštit!

Příklad:

Máme šifrovaný text: „XLMW MW HVMRO JSVI XLMW TEWWI“. Když spočítáme výskyt písmen, tak zjistíme, že:

• M se vyskytuje 5×
• W se vyskytuje 4×
• X se vyskytuje 2×
• L se vyskytuje 2×
• H se vyskytuje 2×
• V, I, R, O, J, S, T, P, A, E – každé 1×

Nejčastější písmeno v češtině je „E“, takže můžeme hádat, že „M“ by mohlo být původní „E“. Pokud je to Caesarova šifra, stačí posunout všechna písmena zpět stejným posunem a dostaneme původní zprávu. Písmeno M je 13. písmeno v abecedě, písmeno E je 5. písmeno v abecedě. Posun je tedy 8 míst zpět.

Dekódováním zjistíme, že původní zpráva byla TOTO JE ZPRAVA PRO TEBE.

Brute-force útok

Někdy se šifra dá prolomit jednoduchou hrubou silou (brute force). To znamená, že prostě vyzkoušíme všechny možné klíče, dokud nenajdeme správný.

Například: abeceda má 26 písmen, což znamená, že Caesarova šifra má pouze 25 možných posunů. Pokud neznáš klíč, můžeš prostě zkusit všechny možnosti a najdeš správnou zprávu během pár minut.

Nebo, pokud má někdo heslo „123456“, může ho hacker prolomit během zlomku sekundy – stačí, aby počítač vyzkoušel všechna běžná hesla ze seznamu. Proto je důležité používat složitá hesla!

Brute-force funguje jen tehdy, když je málo možností. Proto silné šifry mají dlouhé klíče, aby brute-force nebyl použitelný.

Představ si, že jsi špión a podařilo se ti zachytit zašifrovanou zprávu. Nemáš klíč, nevíš, jak byla zpráva šifrovánadní zpráva byla TOTO JE ZPRAVA PRO TEBE.

Matematický útok

Frekvenční analýza a brute-force fungují hlavně na staré, jednoduché šifry. Ale co když je šifra založená na složité matematice?

Dnes se šifrování spoléhá na matematické problémy, které jsou jednoduché na provedení, ale těžké na rozluštění. Některé útoky se snaží najít slabiny v této matematice.

Například – prolomení RSA šifry:

RSA je moderní šifra, která se používá na zabezpečení internetu. Je založená na tom, že je lehké vynásobit dvě obrovská prvočísla, ale skoro nemožné zjistit, jaká ta čísla byla, pokud znáš jen jejich součin.

Matematikové se snaží vymyslet rychlý způsob, jak rozložit čísla na prvočinitele, ale zatím to neumíme dostatečně rychle. Pokud by někdo přišel na lepší metodu faktorizace, mohl by prolomit šifry používané na internetu.

Dnes nemáme dostatečně výkonné kvantové počítače, které by tyto šifry prolomily. Existují lepší a bezpečnější šifrovací algoritmy, které chrání internet.

Matematické útoky jsou tedy jediný způsob, jak prolomit moderní šifry, ale zatím jsou velmi pomalé.

Prezentace

8-Uvod-do-kryptografie

---

Zdroje

Seznam zdrojů

ŠEDIVÝ, Libor. Operační systémy IV. ročník: Učební text. Městská střední odborná škola Klobouky u Brna, 2023.
ŠEDIVÝ, Libor. Operační systémy IV. ročník: Prezentace. Městská střední odborná škola Klobouky u Brna, 2023.
PASEKA, Jan. Kryptografie. Online. Brno: Masarykova univerzita, 2018. Dostupné také z: https://is.muni.cz/el/sci/jaro2018/M0170/um/um/PREDLAwideboc_nfbjkgjs.pdf.
JEŽEK, Jakub. Kryptografické metody. Online, Bakalářská práce. Brno: AMBIS, 2009. Dostupné také z: https://is.ambis.cz/th/zoant/1.pdf.
OULEHLA, Milan a JAŠEK, Roman. Moderní kryptografie: průvodce světem šifrování. [Praha]: IFP Publishing, 2017. ISBN 978-80-87383-67-4.
BURDA, Karel. Aplikovaná kryptografie. Brno: Vutium, 2013. ISBN 978-80-214-4612-0.