Ohrozí kvantové počítače naši bezpečnost?

21. 5. 2018 | Jindřich Zechmeister

Kvantové počítače jsou fenomén budoucnosti, který způsobí technologickou revoluci. Vědci stále pracují na možnosti jejich využití a očekávají obrovský skok ve výkonu a rychlosti výpočtů. V souvislosti s obrovským výpočetním výkonem vyvstává i riziko prolomení současného šifrování. Máme se bát o svou bezpečnost?

Pilíře současného šifrování

Tři pilíře současného šifrování a internetové bezpečnosti jsou Diffie-Hellmanova výměna klíčů, RSA algoritmus a eliptické křivky. Jejich bezpečnost závisí na složitosti matematických problémů, na kterých jsou algoritmy založeny. Nejpoužívanější šifrovací algoritmus RSA je založen na součinu velkých prvočísel a náročnosti rozkladu součinu na jednotlivé součinitele. Diffie-Hellman pracuje s problémem diskrétního logaritmu. Eliptické křivky jsou založeny na předpokladu, že nalezení diskrétního logaritmu náhodného elementu eliptické křivky s ohledem na známý základní bod je nemožné; odvození privátního klíče z veřejného ležícího na eliptické křivce je pomocí diskrétního logaritmu tedy prakticky nemožné.

V současnosti je kryptografie stále "neprolomitelná", ovšem za předpokladu silného šifrování. To je i důvodem nedávného přechodu na 2048-bitového RSA klíče a loňského velkého přechodu na SHA-2 hashovací algoritmus. Rizikem je slabší (symetrické) šifrování silné 80 nebo méně bitů; to se přestalo ve velkém používat mezi lety 2011-2013. Počítač na lámání této úrovně šifrování by se dal zkonstruovat za desítky nebo stovky miliony dolarů. Dnešní 112-bitové (a silnější) šifrování by útočník s rozpočtem ve výši miliardy dolarů lámal 30-40 let [2]. Nutno podotknout, že většina "moderních" serverů šifruje 256-bitovými symetrickými klíči a šifrování je z dnešního pohledu stále bezpečné.

Je zřejmé, že tyto zmíněné problémy jsou náročné pro současné počítače a jejich výpočetní výkon. Pokud bychom však měli k dispozici počítače výrazně výkonnější a schopné vypočítat více instrukcí, nebyla by pak hračka prolomit současnou úroveň šifrování?

Poznámka: Předpokládaná náročnost lámání šifer využívá extrapolaci Moorova zákona. Podle něj je cca 90-bitová bezpečnost prolomitelná za jednu miliardu dolarů a s těmito náklady trvá prolomení 1 bitu 18 měsíců.

Co je to kvantový počítač a k čemu ho potřebujeme

Historie kvantových počítačů

Věda se zabývá principem kvantového počítače již od 70. let. Vědci tehdy na základě kvantové mechaniky uvažovali o možnosti využití pro informatiku, avšak možnost realizace byla vzdálená. Museli tedy obor kvantové informatiky definovat pouze abstraktně.

V roce 1994 formuloval matematik Peter Shor důkaz, že kvantové počítače můžou efektivně vyřešit zmíněné kryptografické problémy, přičemž některé algoritmy předem odsoudil k zániku. Kvantové počítače tedy mohou vyřešit některé problémy mnohem rychleji, než počítače současné. Shorův algoritmus dokáže z prvočísla N vypočítat jeho součinitele; to je pro čtenáře tohoto článku synonymem prolomení RSA algoritmu.

Po dvaceti letech od Shorova objevu se kvantové počítače posunuly blíže realitě. Jednoduché (jednoúčelové) kvantové počítače dnes už existují a komerčně je od roku 2011 vyrábí firma D-wave. Vědci experimentují s jejich konstrukcí a malými kroky pokračují k větším projektům. V březnu tohoto roku sestrojili vědci z MIT a univerzity v Innsbrucku funkční kvantový počítač, který má ale pouze pět atomů v iontové pasti. Pomocí laserových pulsů na každém z atomů provedli výpočet Shorova algoritmu a podařilo se jím úspěšně rozložit číslo 15 na prvočísla [1]. Vytvoření většího stroje na základě zmíněného je teoreticky jednoduché, ale brání mu enormní náklady.

Princip kvantového počítače a jeho účel

Principem kvantového počítače je z fyzikálního pohledu využití kvantové mechaniky pro vykonávání operací s daty. Jednotkou informace kvantového počítače je qubit, který je odvozen od klasického bitu. Na rozdíl od něj však může nabývat stavů 0 i 1 (tedy obou zároveň) či hodnot mezi nimi. Díky principu superpozice je kvantový počítač schopen obejít nutnost paralizace a provádět některé operace na všech vstupech najednou.

Kromě lámání šifer mohou kvantové počítače v důsledku kryptografii prospět. Už nyní známe koncepty kvantové kryptografie, která má přinést algoritmy odolné i kvantovým počítačům. Jednoduché srovnání současné kryptografie, která nebude kvantovým počítačům odolná, a budoucí, která jim obstojí, přináší následující obrázek.

Dva typy kryptografie - současná a kvantová. Převzato z futurism.com.

Etická rizika kvantových počítačů

V současnosti se jednoduché kvantové počítače již používají pro jednorázové účely, nikoliv pro univerzální výpočty. Na ně musíme počkat minimálně další dekádu a v současnosti neexistuje kvantový počítač, který by uměl například lámat RSA algoritmus. Je však otázkou, zdali se o vytvoření kvantového počítače vůbec dozvíme a zdali budeme znát jeho pravý účel.

Možnosti prolomení současné úrovně šifrování vyvolávají konsekvence v podobě rizika masového sledování občanů na internetu. Je zřejmé, že kvantové počítače jsou velice nákladným prostředkem a nedají se koupit na běžném trhu. Jejich astronomická cena však nemusí být problém pro vládní agentury, jejichž zájmem je sledování osob na internetu a jejich komunikace. Už teď je známo, jak gigantické rozpočty mají tzv. třípísmenné agentury jako nejznámější NSA. Díky kvantovým počítačům a jejich "neetickému" využití by mohli špehové získat na mnoho let výhodu před námi, kteří se pomocí konvenčního šifrování tomuto sledování brání.

Výzva, nebo hrozba? Uvidíme za 16 let

Zničí kvantové počítače naši bezpečnost už za 16 let? Na to si musíme počkat. Už teď je však zřejmé, že algoritmy RSA, DSA, ECDSA a ECDH budeme muset nahradit silnějšími. U AES a SHA-2/3 postačí prodloužení klíčů a výstupu v případě hashovacích funkcí [2]. Jako obrana proti současným útokům prozatím stačí 112 nebo 128-bitové symetrické klíče [6]. Při existenci kvantových počítačů bychom měli současné symetrické šifry nahradit novějšími z již zmíněné kvantové kryptografie (viz obrázek výše), které novým útokům odolají.

Konkrétněji riziko prolomení současné kryptografie vyjádřil Michele Mosca z Global Risk Institute, který tvrdí, že existuje šance 1:7 k prolomení šifrovacích nástrojů už v roce 2026 a dokonce 50% šance na prolomení v roce 2031 [4]. Pokud by byl v roce 2030 sestrojen stroj schopný lámat 2000-bitové RSA klíče, stál by podle současných odhadů miliardu dolarů [2].

Těžko odhadovat, zdali se hrozba prolomení šifrování a hromadného sledování naplní. Určitě však zažijeme zajímavý pokrok v technologii a lidském vědění. Kvantové počítače způsobí průlom v astronomii, fyzice a dalších vědách. Důležité bude, abychom udrželi na uzdě naše vlády a nenechali je způsobit radikální rozvoj špehování a jeho plošné použití.

Zdroj:

1. MIT News. The beginning of the end for encryption schemes?
2. CHEN, Lily, et al. Report on post-quantum cryptography. National Institute of Standards and Technology Internal Report, 2016, 8105.
3. Wikipedia.org. Kvantový počítač.
4. Global Risk Institute. Quantum Computing: A New Threat to Cybersecurity.
5. SingularityHub. Quantum Computers Could Crush Today’s Top Encryption in 15 Years.
6. National Institute of Standards and Technology. NIST Special Publication (SP) 800-57 Part 1 Revision 4, Recommendation for Key Management – Part 1: General, 2016.