Už o necelé desaťročie budú kvantové počítače prelamovať niektoré súčasné šifry

Jednou z kľúčových tém IT konferencie ITAPA, ktorá sa v Bratislave uskutočnila 25. až 28. novembra, bola kybernetická bezpečnosť.

V jej rámci sa uskutočnilo niekoľko vystúpení zaoberajúcich sa prichádzajúcou hrozbou pre súčasné metódy šifrovania. Ide o kvantové počítače, ktoré v relatívne krátkej dobe umožnia dešifrovať tajomstvá chránené určitými druhmi šifrovacích algoritmov. 

Podľa vyjadrenia Ramsésa Gallegoa z Quantum World Association, ktoré odznelo na konferencii ITAPA, budú kvantové počítače schopné ohroziť v súčasnosti používané šifrovacie algoritmy už o 7 až 12 rokov.

Objavilo sa počítadlo Y2Q vytvorené Alianciou pre cloudovú bezpečnosť, kde sa za kľúčový dátum, keď kvantové výpočty narušia bezpečnosť súčasnej infraštruktúry považuje 14. apríl 2030. Ide o analógiu „problému Y2K“, keď používanie dvojmiestneho čísla roku v dátach hrozilo kolapsom na prelome 1999 a 2000.

Zraniteľné je hlavne asymetrické šifrovanie

Základom súčasného spôsobu ukrývania tajomstiev je komplikovaná matematika. Dôležitú rolu hrajú takzvané „jednosmerné funkcie“, teda operácie, ktoré sa dajú jednoducho vypočítať, ale získať z výsledku pôvodné operandy je nesmierne náročné.

Príkladom môže byť aj násobenie. Vynásobiť dve prvočísla (čísla deliteľné len jednotkou a samým sebou) je operácia zvládnuteľná aj na papieri, ale získanie pôvodných činiteľov z výsledku je tak náročné, že sa pri tom „zapotia“ aj najvýkonnejšie počítače. Ak sú operandy násobenia dostatočne veľké, rozdelenie ich súčinu by na klasických počítačoch trvalo aj stáročia.

Jednosmerné funkcie sa využívajú hlavne pri takzvanom asymetrickom šifrovaní. To využíva dva šifrovacie kľúče, verejný a súkromný. Dôležitou vlastnosťou je skutočnosť, že z verejného kľúča, ktorý sa publikuje, nie je jednoducho možné odvodiť súkromný, práve pre extrémnu výpočtovú náročnosť tohto procesu,

Ak však vstúpia do hry kvantové počítače, na nich bežiaci Shorov algoritmus umožňuje extrémne zrýchliť matematické operácie, akými sú rozklad súčinu prvočísiel na činitele alebo takzvané diskrétne logaritmy, teda funkcie využívané práve pri asymetrických šifrách.

Niektoré algoritmy odolávajú

Symetrické šifrovanie využíva iba jeden kľuč, ktorý sa používa na šifrovanie aj na dešifrovanie. Je pochopiteľné, že sa preto musí udržiavať v utajení. Najtypickejším príkladom tohto druhu ukrývania tajomstiev je algoritmus AES.

Kvantové počítače síce dokážu zrýchliť aj lámanie tohto druhu šifier, ale nejde tu o radikálne urýchlenie. Groverov algoritmus umožňuje znížiť počet pokusov pri lámaní šifier takým spôsobom, ako keby bola dĺžka kľúča iba polovičná.

Teda pri AES bežne používaný 256-bitový kľuč sa bude pre kvantový počítač "javiť", ako keby mal „iba“ 128 bitov. Aj to však znamená, že číslo charakterizujúce počet pokusov o uhádnutie šifrovacieho kľúča bude mať 38 číslic a čas rozlúštenia pri dnešných rýchlostiach výpočtov by presiahol čas existencie vesmíru.

Ďalšími zbraňami v arzenáli kryptografie sú takzvané hašovacie funkcie. Ide o operácie, kde sa z dlhšieho bloku dát vytvorí krátky textový reťazec. Základnou vlastnosťou takejto funkcie je, že z rovnakého bloku dát vytvorí vždy rovnaký výstupný reťazec a zároveň aj malá zmena vstupu vytvorí veľkú zmenu na výstupe.

Základným princípom „lámania“ hašovacích funkcií je nájsť „kolíziu“, teda odlišný blok dát, ktorý poskytne rovnaký výstup. Kvantové počítače tu nepredstavujú výrazné ohrozenie, hoci sa aj tu sa dá využiť Groverov algoritmus alebo iné postupy.

Bezpečný internet či kryptomeny

Aj keď z pohľadu bežného používateľa predstavujú tieto úvahy iba „ezoterické“ záležitosti vhodné pre „ajťákov“ a trojpísmenkové agentúry, opak je pravdou. Šifrovacie algoritmy patria v súčasnosti medzi nástroje využívané v každodennom živote.

Pomocou nich sa chráni bezpečnosť údajov prenášaných internetom. Asymetrické šifrovanie slúži na potvrdenie identity servera a výmenu šifrovacích kľúčov, ktoré potom využíva symetrická šifra. Takto sa komunikuje aj s bankami či inými službami pracujúcimi s financiami.

Asymetrické šifry sú spolu s hašovacími funkciami základom elektronického podpisu. Ten vo svojej kvalifikovanej forme má rovnakú právnu silu ako vlastnoručný podpis.

Blockchain je základný technologický prvok umožňujúci existenciu kryptomien. Bez asymetrických šifrovacích algoritmov a hašovacích funkcií by tiež neexistoval.

Postkvantové šifrovanie alebo kvantové komunikačné siete

Na obranu pred dominanciou kvantových počítačov existuje viac ciest.

Tou prvou sú šifrovacie postupy, ktoré, aspoň na základe súčasných znalostí, nie sú napadnuteľné kvantovými počítačmi. Ide o takzvanú postkvantovú kryptografiu.

Národný inštitút pre štandardy a technológie (NIST) z USA v auguste zverejnil prvé tri takéto algoritmy. Každý z nich je pritom založený na inom matematickom postupe.

Ďalším spôsobom ochrany je nevyužívať na utajovanie tajomstiev komplikované matematické postupy. Spoľahnúť sa môžeme na rovnaký princíp, na akom fungujú kvantové počítače, teda na kvantovú fyziku.

Existujú postupy kvantovej distribúcie šifrovacích kľúčov, ktoré sú vo svojej podstate nenapadnuteľné ani kvantovými počítačmi. Tieto kľúče sa potom využívajú na šifrovanie klasických komunikačných kanálov.

Na vyššej úrovni sú kvantové komunikačné siete, kde sa aj informácia prenáša v kvantovej forme. Tieto spôsoby spojenia nie sú odpočúvateľné už zo svojej podstaty, vzhľadom na to, že kvantové meranie ovplyvňuje prenášanú informáciu.

Bity a qubity

Klasické počítače, až na pár výnimiek, akým bol sovietsky počítač Setuň založený na trojkovej sústave, využívajú binárny systém. Jedna číslica dvojkovej sústavy tak môže nadobudnúť hodnoty 0 alebo 1. Do núl a jednotiek sú potom zakódované všetky dáta, ktoré bežné počítače spracovávajú. V angličtine sa dvojková číslica nazýva binary digit, v praxi sa používa jej skrátené pomenovanie bit.

Základná jednotka informácie spracovávaná kvantovými počítačmi sa nazýva qubit. Na rozdiel od bitu, ktorý môže nadobudnúť hodnotu nula alebo jedna, obsahuje qubit nulu a jednotku zároveň. Obidva stavy sa v ňom nachádzajú v stave takzvanej kvantovej superpozície.

Hlavným problémom realizácie kvantových počítačov sa tak stáva problém udržania tejto situácie počas celého procesu výpočtu. Už drobný kontakt s prostredím totiž môže spôsobiť takzvaný kolaps vlnovej funkcie. Pri ňom sa komplexný kvantový stav qubitu zredukuje na „obyčajný“ bit a kvantový výpočet nefunguje.

Praktická implementácia kvantových počítačov preto vyžaduje komplikované podmienky, napríklad chladenie do blízkosti absolútnej nuly, teda 273,15 stupňov pod bodom mrazu.

Dnešné prevedenie kvantových počítačov tak pripomína skôr fyzikálne laboratórium ako dátové centrum. Aj prvé klasické počítače v čase ich počiatku v päťdesiatych rokoch minulého storočia však vyžadovali masívne chladenie a ich obsluhu zabezpečovali vedci v bielych plášťoch.

Dva druhy kvantových počítačov

Počet qubitov, ktoré kvantový počítač obsahuje, indikuje jeho potenciálny výkon. Treba však spresniť, že v súčasnosti existujú minimálne dva druhy týchto zariadení.

V prvej kategórii sa nachádzajú tie, ktoré sú špecializované na algoritmus „kvantového žíhania“. Tento výpočet je vhodný na určité druhy optimalizačných úloh, napríklad dokáže veľmi efektívne riešiť „problém obchodného cestujúceho“, prakticky využiteľný v logistike.

Takéto stroje sa dajú využiť aj na „lámanie“ šifier. Čínskym výskumníkom sa podarilo s pomocou 5760-qubitového počítača D-Wave Advantage „prelomiť“ 50-bitový algoritmus RSA.

Aj keď internet zaplavili alarmujúce články, nejde o skutočné ohrozenie bezpečnosti, rovnaký výpočet by za pár sekúnd urobil aj bežný mobilný telefón. Algoritmus RSA sa totiž v súčasnosti používa minimálne v 2048-bitovej verzii, pričom každý pridaný bit predlžuje čas prekonania šifry na dvojnásobok. Dvadsiatka dodatočných bitov zvyšuje náročnosť približne miliónkrát, a ak bitov pridáme tisíc, na „prelomenie“ treba násobok popísaný ako jednotka s 301 nulami.

Výhodou tohto typu kvantových počítačov je ich schopnosť „škálovania“, teda rýchleho pribúdania počtu qubitov. Kanadská firma D-Wave Systems tak pripravuje počítač Advantage 2, ktorý by mal prísť na trh v najbližšej dobe a obsahovať viac ako 7-tisíc qubitov. Nevýhodou zostáva schopnosť spracovávať iba určité druhy úloh.

Druhou kategóriou sú „univerzálne“ kvantové počítače, založené na takzvaných kvantových obvodoch. Tie sú určené na beh všetkých úloh pre kvantové počítače, medzi nimi aj Shorov algoritmus určený špeciálne na zrýchlenie „lámania“ šifier.

Tu sa pohybuje počet qubitov od desiatok až mierne nad tisícku. Ak ich množstvo prekročí približne desaťtisícovú hladinu, súčasná šifrovacia infraštruktúra bude mať problém, odznelo na konferencii ITAPA.