Národní ústav pro kybernetickou a informační bezpečnost vydal v poslední době i doporučení pro zabezpečení IT ve spojitosti s očekávaným rozvojem kvantových počítačů, respektive obecně kvantových technologií. Upřesnění souvisejících rizik přináší následující rozhovor. Odpovídají specialisté z Národního úřadu pro kybernetickou a informační bezpečnost (NÚKIB) Luboš Přibyl (LP) a Tomáš Rabas (TB).
Jaký typ současně používaných metod šifrování je podle vás ze strany kvantových počítačů zranitelný? Lze říci, že jde pouze o metody založené na faktorizaci?
LP: Jde o naprostou většinu současných asymetrických šifrovacích metod.
Domníváte se, že tyto metody bude třeba opustit jako celek, nebo postačí zvýšit náročnost odpovídající úlohy, délku klíče apod.? (Protože i kvantové počítače/algoritmy mají s rostoucí délkou vstupu stále větší problém dojít k výsledku.)
LP: Zvyšování délky klíčů není efektivním řešením. Takové klíče by sice možná odolaly útoku vedenému s pomocí kvantového počítače, ale nebyly by praktické pro běžné užití, kvůli jejich velikosti. V současnosti se ovšem dokončuje vývoj takzvané postkvantové kryptografie, šifrovacích standardů, které budou odolné vůči kvantovým počítačům a zároveň nebudou výrazně náročnější než současné standardy.
Jaké jsou podle vás realistické parametry předních kvantových počítačů řekněme za 10 let.
LP: To je velmi těžké předvídat, jelikož kvantové počítače jsou v současnosti stále především experimentální technologií, kterou ještě nelze označit za „dospělou“. V současnosti se experimentuje s mnoha principy těchto počítačů, konfiguracemi, kvantovými samoopravnými kódy atd., a není jasné, která z těchto cest se ukáže jako úspěšná. Může dojít k velkému průlomu, ale rovněž nemusí, a v takovém případě budeme během následujících deseti let pozorovat jen dílčí pokroky.
Lze říci, že metody šifrování, kde dešifrování spadá do kategorie úloh NP-hard nebo NP-complete, jsou před kvantovými počítači v bezpečí?
TB: Zda kvantové počítače umí řešit NP-těžké problémy s polynomiální složitostí, to bohužel není známo (stačilo by nalézt alespoň jeden). Dokázané je pouze to, že veškeré problémy řešitelné klasickými počítači s polynomiální složitostí mohou být vyřešeny s polynomiální složitostí také kvantovými počítači.
Nicméně pozor, vytvořit kryptosystém, založený na NP-těžkém problému ještě nestačí. Problémům kategorie NP totiž stačí, že pouze některé instance problému jsou těžké. V kryptografii ale potřebujeme, aby průměrná instance dané kategorie problémů byla těžká.
Existují problémy, které jsou NP těžké, a přitom jejich průměrná instance je řešitelná polynomiálně [1]. Opačným příkladem je například problém hledání nejbližšího vektoru (CVP), u kterého je dokázáno, že je těžký i v průměrném případě. Na tom jsou založené například kryptosystémy Ajtai-Dwork [2] nebo Goldreich-Goldwasser-Halevi [5]. I v těchto případech se ale ukázalo, že jejich zlomení není NP-těžké [3] [4]. Ponaučením z toho je, že i kryptosystém založený na NP-těžkém problému, navíc i jehož průměrná instance je těžká, ještě nemusí stačit.
Má nějaká další schopnost kvantových počítačů vztah ke kryptografii, pomineme-li Shorův algoritmus pro faktorizaci?
TB: Kromě Shorova algoritmu, který kriticky ohrožuje veškerou kryptografii založenou na faktorizaci velkých čísel a problému diskrétního logaritmu (jeho složitost je totiž polynomiální!), je pro kryptografii zásadní ještě známý Groverův algoritmus. Ten obecně umí nalézt prvek v neuspořádaném poli se složitostí překvapivě pouhé druhé odmocniny (vzhledem k počtu prvků v poli). V kryptografii lze pak tento algoritmus použít pro efektivnější hledání klíčů hrubou silou, snižující teoretickou bezpečnost všech symetrických kryptosystémů z exponenciální složitosti na její druhou odmocninu, což je naštěstí stále exponenciální složitost. Plně dostačující reakcí je tak konstantní navýšení (nejvýše dvojnásobek) délky klíčů bezpečných symetrických kryptosystémů (např. AES128 -> AES256), v případě hashovacích funkcí je pak doporučenou reakcí zvětšení velikosti jejich výstupu (tagu).
Ve svých prognózách počítáte s rozvojem kvantových počítačů ve smyslu počtu qubitů (apod.), nebo i s prudkým růstem efektivních kvantových algoritmů? (podle mě nepříliš pravděpodobné)
TB: „Předvídání je velice těžké, zvláště předvídání budoucnosti.“Robert Storm Petersen, dánský básník a filozof; přisuzováno také fyzikovi Nielsu Bohrovi
Hlavním problémem, na který bych rád upozornil, je extrémně dlouhá doba, po kterou jsou „naživu“ zastaralé kryptografické algoritmy. Takovým odstrašujícím případem jsou šifra DES a hashovací funkce SHA1. S oběma těmito algoritmy, i přestože jsou na ně známé praktické útoky, se můžeme setkat i v současných systémech. Obzvláště SHA1 se vyskytuje jako defaultní nastavení u řady nástrojů, které používáme každý den (například podepisování e-mailů). Přitom tato hashovací funkce byla vyřazena jako standard NIST již v roce 2011! To je celých 12 let na to, aby se kryptografie v prostředích inovovala, ale v nemalém množství případů se tak nestalo! Z tohoto důvodu je třeba se alespoň pro kritické části naší infrastruktury začít na kvantovou hrozbu připravovat již teď.
„Ani mudrc, ani odvážlivec si nelehne na koleje dějin, aby počkal na to, až ho přejede vlak budoucnosti.“
Dwight D. Eisenhower
[1] DYER, Martin E.. ; FRIEZE, Alan M.. . The solution of some random NP-hard problems in polynomial expected time. Journal of Algorithms, 1989, 10.4: 451-489.
[2] AJTAI, Miklós; DWORK, Cynthia. A public-key cryptosystem with worst-case/average-case equivalence. In: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. 1997. p. 284-293.
[3] NGUYEN, Phong; STERN, Jacques. Cryptanalysis of the Ajtai-Dwork cryptosystem. In: Annual International Cryptology Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. p. 223-242.
[4] NGUYEN, Phong. Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from crypto’97. In: Annual International Cryptology Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. p. 288-304.
[5] GOLDREICH, Oded; GOLDWASSER, Shafi; HALEVI, Shai. Public-key cryptosystems from lattice reduction problems. In: Advances in Cryptology—CRYPTO’97: 17th Annual International Cryptology Conference Santa Barbara, California, USA August 17–21, 1997 Proceedings 17. Springer Berlin Heidelberg, 1997. p. 112-131.
