NSA in GCHQ se pripravljata na kvantno lomljenje šifrirnih algoritmov

Moderni šifrirni algoritmi se naslanjajo na dejstvo, da poznamo vrsto matematičnih problemov, ki so v eno smer enostavno izračunljivi, v obratno pa toliko težje, da jih v celotni dosedanji zgodovini vesolja ne bi bili mogli. Analogija je množenje dveh velikih praštevil, kar je z današnjo tehnologijo trivialen problem, medtem ko je faktorizacija psevdopraštevil bistveno težji problem. Ob primerni implementaciji so današnji šifrirni algoritmi inherentno varni, četudi bo računska moč napredovala. Razen če dobimo dejansko uporabne kvantne računalnike, ki bodo predvidoma sposobni zlomiti asimetrične algoritme, kot so DSA, Diffie Hellman ali RSA.

Kvantni računalniki niso več zgolj teoretične zamisli, temveč imamo primitivne prototipe že tu. Google razvija svojega, NSA želi svojega, za trenutne komercialne izvedenke pa nismo niti prepričani, kako delujejo. Pravi kvantni računalniki izkoriščajo kvantno prepletenost kubitov, zaradi česar lahko algoritem poganjajo na vseh možnih vrednostih spremenljivk hkrati. Kvantni računalnik ni a priori hitrejši od klasičnega. Tak je le, če za problem obstaja kvantni algoritem - tak primer je Shorov algoritem za faktorizacijo števil.

Zato so nekateri šifrirni algoritmi ranljivi, drugi pa ne. RSA in ostali, ki se zanašajo na neizvedljivost faktorizacije, so trivialno zlomljivi s Shorovim algoritmom. DSA, Diffie-Hellman in ostali, ki izkoriščajo težavnost izračuna diskretnega logaritma, so prav tako ranljivi. Simetrični algoritmi so po drugi strani nekoliko ranljivi, a ne nujno za odpis. Kvantni računalnik se skozi prostor 2²ⁿ prebije v času 2ⁿ, torej bo zanj 128-bitni AES enako težaven, kot je 64-bitni AES za klasični računalnik. Podobno velja tudi za zgoščevalne funkcije (npr. SHA-256).

Doslej so s Shorovim algoritmov uspeli faktorizirati število 21, z drugim algoritmom (AQC) pa 143 in 56153, kar se ne sliši ravno impresivno in za varnost šifriranja ne predstavlja nobene grožnje. A kakor si nihče ni znal pred 50 leti predstavljati, česa bodo zmožni današnji računalniki, tako se NSA že danes boji, česa bodo zmožni računalniki čez 50 let. Če bodo kvantni računalnik realnost, bo današnje šifriranje tako neuporabno, kot je danes Cezarjeva šifra.

NSA se zato pospešeno pripravlja na to možnost in razvija algoritme, ki bodo na kvantne računalnike odporni. Trenutno je priporočen nekvantni nabor znan pod oznako Suite B, pripravljajo pa tako imenovane kvantno odporne algoritme (quantum resistant algorithms), o katerih bomo v prihodnosti gotovo še dosti slišali. Vse institucionalne uporabnike, ki še niso prešli na algoritme iz Suite B, pozivajo, naj ne hitijo s prehodom na Suite B. Namesto tega naj počakajo na naslednji Suite, ki bo kvantno odporen. Tudi britanska agencija GCHQ je pred kratkim v članku prepoznala realnost v tako imenovanem post-kvantnem svetu.

Skupaj s spremembo smernic za razvoj šifrirnih algoritmov je to pomenljivo sporočilo, saj kaže, da so znanstveniki razvoj kvantnih računalnikov prepoznali kot realno možnost. Z razvojem novih algoritmov lahko pričakujemo, da bodo sčasoma začeli kapljati tudi v programsko opremo, ki je namenjena poslovnim in kasneje domačim uporabnikom.