Úvod do kryptografie
Kryptografie je věda o matematických metodách pro utajování obsahu a pro ověřování původu přenášených zpráv. Zprávy jsou v kryptografii chápána jako čísla, s nimiž se provádějí matematické operace. V případě utajování obsahu je zpráva tzv. zašifrována, tj. převedena do podoby pseudonáhodného čísla. Toto číslo se nazývá kryptogram a je zasláno příjemci. Případný útočník, který kryptogram v přenosovém kanálu odposlechne, není v důsledku jeho pseudonáhodnosti (kryptogram se mu jeví jako zcela náhodné číslo) schopen zjistit, jaká zpráva je v něm přenášena. Do podoby původní zprávy dokáže kryptogram převést (tzv. dešifrovat) pouze určený adresát.
V případě ověřování původu se ke zprávě připojuje kontrolní pseudonáhodné číslo, které příjemci umožňuje ověřit, zda přijatá zpráva nebyla během přenosu pozměněna a zda ji zaslal udávaný odesílatel. Toto kontrolní číslo se u symetrických kryptosystémů (viz dále) obvykle nazývá autentizační kód zprávy („Message Authentication Code“ – MAC) a u asymetrických kryptosystémů se nazývá digitální podpis. Kontrolní číslo se ke zprávě přidružuje podobně jako se dříve připojovala pečeť k listinnému dokumentu a tak toto číslo budeme obecně (tj. bez ohledu zda se jedná o MAC, nebo o podpis) rovněž nazývat pečetí.
K převodu zprávy na kryptogram a naopak, resp. k vytvoření pečeti pro zprávu a její ověření se v kryptografii používají matematické funkce. Konkrétní přiřazení výstupů jednotlivým vstupům se u těchto funkcí nastavuje číselnými parametry – tzv. klíči. Aby útočník nemohl odposlechnuté kryptogramy dešifrovat, resp. zachycené zprávy nahrazovat falešnými, tak klíče potřebné k dešifrování kryptogramů, resp. k výpočtu pečetí musí být tajné. K zajištění dostatečné bezpečnosti musí navíc v kryptosystému existovat značné množství těchto klíčů. Pokud by tomu tak nebylo, tak by útočník mohl pro zachycený kryptogram, resp. pečeť vyzkoušet všechny možné hodnoty klíče (tzv. útok hrubou silou) a tak by zjistil, která zpráva je v kryptogramu přenášena, resp. by zjistil pečetící klíč, který by pak mohl použít k úspěšnému pečetění falešných zpráv.
Z hlediska utajování klíčů se rozlišují tzv. symetrické a asymetrické kryptosystémy. U symetrických kryptosystémů platí, že klíče na straně odesílatele i příjemce jsou buď stejné (zcela nejčastější případ), nebo jeden z druhého je snadno vypočitatelný. Klíče proto musí být na obou stranách tajné. V případě asymetrických kryptosystémů jsou klíče na obou stranách různé a žádný z klíčů není prakticky možné z druhého vypočítat. Jeden z klíčů potom může být veřejně známý (tzv. veřejný klíč) a tajný je pouze ten klíč, jímž se dešifruje, resp. podepisuje (tzv. soukromý klíč).
V případě utajovacích kryptosystémů je výhodou symetrických variant rychlost šifrování a dešifrování. Nevýhodou je u nich problém bezpečného ustavení klíče. Zajistit, aby obě strany disponovaly tajnými klíči je totiž komplikovaná záležitost. Asymetrické utajovací kryptosystémy tento problém nemají, protože k protistraně se přenášejí jen veřejné klíče. Na druhou stranu jsou asymetrické kryptosystémy oproti symetrickým více než tisíckrát pomalejší. Zpravidla se proto nepoužívají k šifrování zpráv, ale jen k šifrovanému přenosu klíčů pro symetrické kryptosystémy.
V případě pečetících kryptosystémů je výhodou symetrických variant vysoká rychlost pečetění a ověřování. Kromě problematického ustavení klíčů je jejich další nevýhodou, že správnou pečeť pro jakoukoliv zprávu dokáží vypočítat obě strany. Když strana A zašle nějakou kontroverzní zprávu sama sobě a obviní z toho stranu B, pak nelze určit, která strana danou zprávu ve skutečnosti odeslala. Asymetrické pečetící varianty tímto problémem netrpí, protože pečeť (v tomto případě digitální podpis) dokáže vytvořit jen jedna strana a to majitel soukromého klíče. Ten tak nemůže tvrdit, že danou zprávu nepodepsal (tzv. neodmítnutelnost odpovědnosti).
U asymetrických kryptosystémů je při utajování obsahu zpráv veřejný klíč na straně odesílatele a soukromý klíč je na straně příjemce – kdokoliv může příjemci zaslat zašifrovanou zprávu a jen příjemce si ji může přečíst. V případě ověřování původu zpráv (tzv. digitální podpis) je soukromý klíč na straně odesílatele a veřejný klíč je na straně příjemce – jen odesílatel dokáže zprávu správně podepsat a správnost jeho podpisu si může ověřit kdokoliv.
V případě asymetrických kryptosystémů je praktická nemožnost odvození hodnoty soukromého klíče z veřejného klíče založena na vhodném matematickém problému. V současné době v praxi dominují asymetrické kryptosystémy typu IF („Integer Factorization“), DL („Discrete logarithm“) a EC („Elliptic Curve“). IF kryptosystémy jsou založeny na obtížnosti faktorizace čísel, bezpečnost DL kryptosystémů spočívá na problému diskrétního logaritmu a EC kryptosystémy jsou založeny na problému sčítání bodů eliptické křivky.
Bezpečnost kryptosystémů
V kryptografii jsou známy algoritmy, které jsou tzv. neprolomitelné, tj. i útočník s neomezenou výpočetní kapacitou a s neomezeným časem k vedení útoku není schopen zjistit, která ze všech možných zpráv je v zachyceném kryptogramu přenášena (případ dokonalé šifry), resp. nedokáže určit, kterou ze všech možných pečetí by měl k falešné zprávě připojit, aby ji příjemce akceptoval (případ dokonalé pečeti). Bohužel tyto neprolomitelné kryptosystémy vyžadují extrémní počet klíčů a tak tyto klíče musí být velmi dlouhé. Například u dokonalé šifry musí být délka klíče stejná jako délka samotné zprávy a u dokonalé pečeti musí být délka klíče rovna součtu délky zprávy a délky pečeti. Navíc se jednou použitý klíč již nesmí použít k zabezpečení jakékoliv další zprávy.
Proto se z praktických důvodů používají kryptosystémy s délkou klíče řádově stovek až tisíců bitů, přičemž se tyto klíče používají pro zabezpečení mnoha různých zpráv. Důsledkem je, že tyto běžně používané kryptosystémy jsou teoreticky prolomitelné, tj. útočník je teoreticky schopen zjistit, jaká zpráva je v kryptogramu přenášena, resp. jakou pečeť by měl ke zprávě připojit, aby ji příjemce akceptoval. Slovo „teoreticky“ však vyjadřuje, že k úspěšnému útoku v rozumném čase zatím nemá nikdo na této planetě dostatečný výpočetní výkon.
K posuzování prolomitelnosti kryptosystémů se používá parametr, který nazveme bitová odolnost b („security strength“). Pro kryptosystém s bitovou odolností b musí platit, že nejefektivnější známý útok na daný kryptosystém vyžaduje provedení alespoň 2b výpočtů, tj. musí platit, že asymptotická složitost útoku je nejméně O(2b). Tato složitost se nazývá exponenciální a pro kryptografické algoritmy se považuje za optimální. Opačným extrémem je polynomiální složitost typu O(nc), kde n reprezentuje rozsáhlost úlohy (např. délku klíče) a c je nějaká konstanta. Kryptosystémy, na které je znám útok o polynomiální složitosti jsou považovány za prakticky prolomitelné a tudíž nevhodné pro praktické použití.
Světově respektovaný standardizační úřad NIST (National Institute of Standards and Technology) doporučuje, aby kryptografické aplikace měly od roku 2030 podle požadované úrovně bezpečnosti hodnoty b = 128, 192 nebo 256 bitů. Pro kryptosystém s b = 128 bitů je pak nutno k úspěšnému útoku provést N = 2128 = 3,4·1038 výpočtů. Pokud bychom předpokládali, že k útoku bude použit v současné době nejvýkonnější superpočítač Frontier s rychlostí v = 1,2·1018 FLOPS (počet operací v pohyblivé řádové čárce za sekundu), přičemž za jeden dílčí výpočet budeme pesimisticky považovat jedinou operaci v pohyblivé řádové čárce (v praxi je zmíněný výpočet třeba i celé jedno zašifrování zprávy), tak doba rezistence T kryptosystému je rovna hodnotě T = N/v ≈ 9·1012 let. To je více než 650krát delší doba než-li doba existence vesmíru.
Výše uvedená doba rezistence se jeví jako zcela bezpečná, ale u teoreticky prolomitelných kryptosystémů je zapotřebí brát v úvahu následující skutečnost. Pokud jsou pro určitý kryptosystém známy jen útoky s exponenciální složitostí, tak to vůbec neznamená, že pro tento kryptosystém útok s polynomiální složitostí nemůže existovat. Možná takovýto útok existuje a jen se na něj doposud nepřišlo. Anebo na něj přišla jen skupinka lidí a tuto znalost tajně využívá ve svůj prospěch.
Bitová odolnost b je pro kvalitní symetrické šifry rovna délce použitého klíče. Například známá šifra AES („Advanced Encryption Standard“) má volitelnou délku klíče k = 128, 192 nebo 256 bitů a tak pro bitovou odolnost AES platí, že b = k. Pro asymetrické kryptosystémy závisí b na bitové délce n zpracovávaných čísel. Například pro bitovou odolnost b = 128 je u IF a DL kryptosystémů potřebná hodnota n = 3072 a pro EC kryptosystém je n = 256.
Kryptografie a kvantové počítače
V případě odolnosti teoreticky prolomitelných kryptosystémů si je zapotřebí uvědomit, že tato odolnost se s rozvojem technologií a lidského poznání mění. Například do poměrně nedávné doby se považovaly za bezpečné kryptosystémy s b = 80. Dnes se takovéto kryptosystémy již musí nahrazovat odolnějšími. Zmíněný rozvoj poznání a technologií způsobil také vznik kvantových počítačů. Tento typ počítačů je založen na tom, že výpočetní operace jsou fyzikálně realizovány pomocí kvantových jevů. Tyto jevy umožňují konstruovat také zcela nové typy výpočetních operací, díky jimž kvantové počítače v určitých aplikacích ty klasické výkonnostně předstihují. Z hlediska prolamování kryptosystémů jsou u kvantových počítačů relevantní Shorův a Groverův algoritmus.
Shorův algoritmus je likvidační hrozbou pro nejčastěji používané asymetrické kryptosystémy, tj. pro kryptosystémy typu IF, DL i EC. Složitost jejich prolomení kvantovým počítačem totiž není exponenciální, ale jen polynomiální – konkrétně u IF kryptosystémů je kubická. Zmíněné kryptosystémy by tak přestaly být jen teoreticky prolomitelné a staly by se prakticky prolomitelnými.
Další potenciální hrozbou je Groverův algoritmus, který je použitelný k útoku na symetrické kryptosystémy. Tato hrozba naštěstí není likvidační, protože Groverovým algoritmem by se bitová odolnost symetrických kryptosystémů oproti útoku klasickým počítačem zmenšila na polovinu. K zajištění dostatečné bezpečnosti by proto stačilo délky klíčů jednoduše zdvojnásobit.
V obou předešlých odstavcích jsou důsledky útoku kvantovými počítači uváděny v podmiňovacím způsobu. Je to z toho důvodu, že prakticky dosažená výkonnost kvantových počítačů zatím zdaleka nepostačuje k ohrožení soudobých kryptosystémů. Pro Shorův algoritmus byl první hardware vytvořen v roce 2001. Dokázal faktorizovat číslo 15, tj. byl schopen určit, že 15 = 3·5. Dalším pokrokem byl hardware z roku 2012 k faktorizaci čísla 21 = 3·7.
Teď se píše rok 2024 a nějaký další výkonnější hardware pro Shorův algoritmus faktorizace čísel se zatím nepodařilo vytvořit. Pro srovnání si uveďme, že zmíněné rekordní číslo 21 má délku n = 5 bitů, přičemž délka čísel v IF kryptosystémech s bitovou odolností b = 128 je rovna hodnotě n = 3072 bitů. V této souvislosti se ještě lze setkat s tvrzeními, že kvantové počítače faktorizovaly již mnohem větší čísla. To je pravda, avšak tyto výpočty buď nebyly uskutečněny pomocí Shorova algoritmu (a tedy výpočet nemá polynomiální složitost), nebo nejsou obecné a je využita nějaká speciální vlastnost úlohy (např. že oba faktory se liší o hodnotu 2).
Výše uvedený poměr indikuje, že soudobá kryptografie kvantovými počítači není ohrožena ani zdaleka. Dokonce lze vyslovit pochyby, zda jsou kvantové počítače vůbec fyzikálně realizovatelné. V historii lidstva se totiž pokusy o zkonstruování kvantového počítače mohou stát opakováním pokusů k vytvoření perpetua mobile. Stroj, který může pracovat donekonečna bez vnějšího zdroje energie, se pokoušelo vytvořit spousta lidí už od 12. století. Teprve ve druhé polovině 19. století se podařilo vědecky dokázat, že perpetuum mobile vytvořit nelze. Co když skutečně kvantové počítače také nelze vytvořit?
Postkvantová kryptografie
Z výše uvedeného je zřejmé, že skepse vůči možnostem kvantových počítačů je oprávněná, ale na druhou stranu je důležitá i opatrnost. Proto bez ohledu na to, zda se dostatečně výkonné kvantové počítače vůbec objeví, se začalo pracovat na opatřeních k eliminaci jejich potenciálních možností.
Již jsme uvedli, že v případě symetrických kryptosystémů stačí vybrat délku klíče, která bude dvojnásobkem požadované bitové odolnosti vůči klasickým počítačům. Takovéto opatření je relativně jednoduché a některé kryptosystémy je již mají implementováno. Například útok kvantovým počítačem na šifru AES s délkou klíče k = 256 bitů bude mít složitost O(2256/2) = O(2128). To odpovídá bitové odolnosti b = 128, což je odolnost, která v současné době pro mnoho scénářů zcela vyhovuje. V případě potřeby přitom není velký problém vyvinout symetrické kryptosystémy s ještě větší délkou klíče.
Pro asymetrické kryptosystémy bohužel platí, že případné prodlužování délky n zpracovávaných čísel nedává smysl, neboť pro kvantové počítače roste jejich doba rezistence v závislosti na hodnotě n jen polynomiálně. Bylo tedy nutné vytvořit kryptosystémy, jejichž bezpečnost spočívá na matematickém problému, který bude mít exponenciální složitost i pro Schorův algoritmus.
V roce 2016 inicioval americký standardizační úřad NIST projekt tzv. postkvantové kryptografie („Post Quantum Cryptography“ – PQC). Cílem projektu bylo vyvinout a standardizovat asymetrické kryptosystémy, které zajistí bezpečnost zpráv v období po případném zavedení dostatečně výkonných kvantových počítačů.
Dne 13. srpna 2024 úřad NIST zveřejnil první tři standardy projektu PQC. Jedná se o standard kryptosystému k zapouzdření klíče ML-KEM („Module-Lattice-Based Key-Encapsulation Mechanism“, standard FIPS 203) a o dva kryptosystémy digitálního podpisu ML-DSA („Module-Lattice-Based Digital Signature“, FIPS 204) a SLH-DSA („Stateless Hash-Based Digital Signature“, FIPS 205). První dva uvedené kryptosystémy jsou založeny na problémech nad algebraickou strukturou, která se nazývá mřížka („lattice“) a bezpečnost podepisovacího kryptosystému SLH-DSA je založena na vlastnostech hešovacích funkcí.
Kryptosystém ML-KEM slouží k bezpečnému ustavení klíče K pro symetrický kryptosystém (např. AES). Systém zjednodušeně funguje následovně. Jedna ze stran vygeneruje dvojici soukromý klíč SK (ve standardu nazýván odpouzdřovací klíč) a veřejný klíč VK (alias zapouzdřovací klíč). Veřejný klíč bezpečně distribuuje (zpravidla ve formě digitálního certifikátu) protistraně. Protistrana na základě náhodně zvoleného čísla R a veřejného klíče vygeneruje tajný klíč K a kryptogram C, v němž je hodnota R zašifrována. Kryptogram je zaslán majiteli soukromého klíče, který z něho hodnotu R pomocí soukromého klíče dešifruje. Z této hodnoty pak stejným způsobem jako odesílatel odvodí klíč K. Další komunikace obou stran je pak již šifrována symetrickým (a tedy i velmi rychlým) kryptosystémem pomocí ustaveného klíče K. Jsou standardizovány tři varianty kryptosystému, pro něž se uvádí, že jejich bitová odolnost b = 128, resp. 192 a 256 bitů je jak proti klasickým, tak i kvantovým počítačům.
Kryptosystémy ML-DSA a SLH-DSA jsou podepisovacími kryptosystémy. Jejich fungování lze zjednodušeně popsat následovně. Podepisující strana vygeneruje dvojici soukromý klíč SK a veřejný klíč VK. Veřejný klíč se bezpečně distribuuje (obvykle ve formě digitálního certifikátu) ověřujícím protistranám. Podepisující strana pro příslušnou zprávu vygeneruje pomocí soukromého (tj. podepisujícího) klíče kontrolní číslo, které se nazývá podpis. Zpráva spolu s jejím podpisem je zaslána ověřující straně. Ta pomocí veřejného (alias ověřovacího) klíče správnost podpisu ověří. Pokud je ověřovací test pozitivní, tak je zpráva příjemcem akceptována. Standard pro ML-DSA nabízí 3 a pro SLH-DSA celkem 12 variant, u nichž se uvádí, že jejich bitová odolnost b = 128, 192 a 256 bitů je jak proti klasickým, tak i kvantovým počítačům.
Odolnost asymetrických kryptosystémů vůči kvantovým počítačům je vesměs vykoupena většími délkami klíčů. U klasických asymetrických kryptosystémů se pro b = 128 pohybuje délka klíčů v rozsahu 32 až 384 bajtů. U kryptosystémů založených na mřížkách (tj. ML-KEM, resp. ML-DSA) se pro tutéž hodnotu bitové odolnosti rovná délka delšího z obou klíčů hodnotě 1632, resp. 2560 bajtů. Vidíme, že se zde jedná o významné prodloužení délek klíčů. Naproti tomu je kryptosystém SLH-DSA v tomto ohledu docela úsporný – pro tutéž bitovou odolnost je délka delšího z klíčů rovna hodnotě 64 B.
Musíme připravit další algoritmy
Na závěr lze konstatovat, že pomocí výše uvedených asymetrických a již existujících symetrických kryptosystémů je možné vytvořit ucelený kryptografický ekosystém, který by měl být schopen vzdorovat případným kvantovým počítačům. Stávající symetrické utajovací kryptosystémy (typicky AES) budou sloužit k utajování zpráv. Pokud nebude potřeba zajistit neodmítnutelnost odpovědnosti odesílatele, tak k prokazování původu zpráv se budou používat existující symetrické pečetící kryptosystémy (např. HMAC – „Hash-based Message Authentication Code“).
Klíče pro oba tyto typy symetrických kryptosystémů se přitom budou ustavovat pomocí algoritmu ML-KEM. Pokud při prokazování původu zpráv bude nutné zajistit i neodmítnutelnost odpovědnosti odesílatele, tak se použije buď podepisovací algoritmus ML-DSA, nebo SLH-DSA. Tímto jsou pokryty základní potřeby naprosté většiny aplikací, jako jsou přenosové, informační, přístupové nebo platební systémy. Kryptografie je tak na případné útoky ze strany kvantových počítačů připravena.
Tento stav však nelze brát za definitivní a je zapotřebí pracovat na vývoji dalších PQC algoritmů, které budou založeny na jiných problémech. To z toho důvodu, kdyby byl některý ze stávajících algoritmů prolomen.
