Kvantové počítače představují revoluci v lámání šifer, zejména těch asymetrických. Mohou ohrozit současné šifrovací systémy, na kterých stojí naše digitální bezpečnost? Zjistěte, jak funguje Shorův algoritmus a proč se nemusíme obávat konce digitálního soukromí díky Post-kvantové kryptografii.
Jedním z důvodů, proč státy masivně dotují vývoj kvantových počítačů, je jejich schopnost lámat šifry, tedy alespoň některé třídy šifer, které se dnes běžně používají. V současnosti je nejdůležitější asymetrická šifra RSA (Rivest-Shamir-Adleman) neboli systém s veřejným kryptografickým klíčem. Tento systém umožňuje zveřejnit jeden klíč (veřejný klíč), kterým se zprávy kódují, zatímco dekódovat je možné pouze druhým (soukromým) klíčem. Tato metoda zakládá svou odolnost na tom, že umíme velmi snadno násobit velká prvočísla, ale jen obtížně provádět faktorizaci, tedy hledání prvočíselných dělitelů velkého čísla.
Od roku 1994 je znám takzvaný Shorův algoritmus, pojmenovaný podle amerického matematika Petera Shora. Ten navrhl algoritmus pro kvantové počítače, který dokáže při dostatečném počtu dostupných qubitů řešit faktorizaci velkých čísel superpolynomiálně rychleji (zrychlí výpočet více než polynomiálně), což představuje masivní zrychlení hledání dělitelů. Lámání šifry se tak stává srovnatelně složité jako její vytváření, protože se porušuje předpoklad algoritmu, že hledání faktorů velkého čísla bude časově mnohem náročnější než jeho vytvoření.
V praxi to znamená, že funkční kvantový počítač by mohl lámat RSA v rozumném čase, zatímco dnes to není na klasických počítačích kvůli složitosti prakticky možné. Pro praktické využití Shorova algoritmu na dostatečně velká čísla potřebujeme funkční kvantový počítač s přibližně milionem qubitů, což je zatím dost vzdáleno od bodu, kde se právě nacházíme.
Shorův algoritmus hledá prvočíselné faktory velkého čísla. Jde o velmi promyšlený algoritmus, který využívá toho, že se problém hledání faktorů dá převést na diskrétní kvantovou Fourierovu transformaci, kterou kvantové počítače díky superpozici mohou řešit velice efektivně. Ne každý problém se ale dá takto snadno převést – a to, jestli bude kvantový počítač efektivnější než ten klasický, záleží právě na tom, zda se dá problém chytře převést na něco, co kvantové počítače zvládají snadno.
Lze vysvětlit Shorův algoritmus bez použití jediného ket znaku? Zjistíte na blogu Scotta Aaronsona v jeho článku vysvětlující Shorův algoritmus.
Kvantové počítače by mohly ohrozit kryptograficky chráněnou komunikaci tak, jak ji dnes známe, protože na AES je založeno prakticky všechno, od zabezpečené internetové komunikace přes platby až po celé kryptograficky chráněné počítačové systémy. V současnosti je AES tak důležitý, že ho podporují procesory, které nabízí přímo hardwarovou akceleraci této kryptografie, což umožňuje mít kryptograficky chráněné nejen údaje na disku, ale také přímo v počítačové paměti.
Je tedy možné, že příchod kvantových počítačů znamená konec soukromí tak, jak ho známe? Rozhodně ne! Kvantové počítače efektivně řeší pouze některé třídy problémů – a nalezení „kvantově rezistentní kryptografie“, tedy takové, která odolá lámání ze strany kvantových počítačů, byla jen otázka času. Tuto třídu kryptografie označujeme jako PQC (Post Quantum Cryptography) – a je nejen vytvořená, ale dokonce od srpna 2024 kodifikovaná americkým NIST (US National Institute of Standards and Technology).
Michal Rybka
Michal Rybka je publicista a nadšenec s 20 lety zkušeností v IT a gamingu. Je kurátorem AlzaMuzea a YouTube kanálu AlzaTech. Napsal několik fantasy a sci-fi povídek, které vyšly v knižní podobě, a pravidelně pokrývá páteční obsah na internetovém magazínu PCTuning.
