Kvantiniai kompiuteriai dar prieš kelerius metus atrodė kaip tolima ateities technologija, apie kurią kalbėjo tik fizikai akademiniuose sluoksniuose. Šiandien padėtis kitokia – IBM, Google, Microsoft ir dešimtys startuolių kasmet skelbia apie naujus kubitų rekordus, o kriptografų bendruomenė jau seniai nebesijuokia iš minties, kad RSA ar eliptinių kreivių algoritmai gali tapti praeitimi per vieną naktį. Postkvantinė kriptografija (PQC) – tai atsakas į šią grėsmę, ir apie ją verta kalbėti dabar, o ne tada, kai bus per vėlu.
Kodėl dabartinė kriptografija apskritai yra pažeidžiama
Beveik visa šiuolaikinė skaitmeninė sauga remiasi keliais matematiniais galvosūkiais, kuriuos klasikiniam kompiuteriui išspręsti praktiškai neįmanoma per protingą laiką. RSA saugumas grindžiamas didelių skaičių faktorizacija – jei turi 2048 bitų raktą, klasikinis kompiuteris tiesiog neturi laiko perkomponuoti jį atgal į pirminius daugiklius, net jei skaičiuotų iki žvaigždžių eksplozijos. Eliptinių kreivių kriptografija (ECC) remiasi diskrečiojo logaritmo problema kreivėse – iš esmės ta pati logika, tik kitas matematinis aparatas.
Problema ta, kad 1994 metais Peteris Shoras įrodė, jog kvantinis kompiuteris, veikiantis pagal kvantinės Furjė transformacijos principą, gali išspręsti tiek faktorizacijos, tiek diskrečiojo logaritmo problemas per polinominį laiką. Kitaip tariant, pakankamai galingas kvantinis kompiuteris RSA-2048 raktą galėtų sulaužyti per valandas ar dienas, o ne per milijardus metų, kaip reikėtų klasikiniam procesoriui. Tai nėra teorinis kuriozas – tai matematiškai įrodytas faktas, kuris tiesiog laukia pakankamai stabilios ir didelės kvantinės architektūros.
Šiandien turime kelias dešimtis ar šimtus kubitų sistemas, kurioms trūksta klaidų korekcijos ir stabilumo. Bet atstumas tarp „turime žaisliuką laboratorijoje” ir „turime įrankį, galintį sulaužyti internetinį bankininkystę” mažėja greičiau, nei daugelis norėtų pripažinti.
Groverio algoritmas ir simetrinė kriptografija
Įdomu tai, kad ne visa kriptografija nukenčia vienodai. Simetriniai šifrai, tokie kaip AES, teoriškai taip pat paveikiami, tačiau kur kas švelniau. Lovo Groverio algoritmas leidžia kvantiniam kompiuteriui atlikti raktų perrinkimo paiešką kvadratiniu pagreičiu – tai reiškia, kad AES-256, kuris klasikiniam kompiuteriui reikalauja 2^256 operacijų perrinkimo atakai, kvantiniam kompiuteriui su Groverio algoritmu efektyviai tampa lygiavertis AES-128 saugumo lygiui.
Geros naujienos tos, kad sprendimas paprastas – tiesiog padidinti rakto ilgį. AES-256 vietoj AES-128 iš esmės atsveria šią problemą, todėl simetrinė kriptografija nereikalauja radikalaus perrašymo. Tikroji krizė laukia asimetrinės kriptografijos pusėje – skaitmeninių parašų, rakto mainų protokolų, viešojo rakto infrastruktūros, ant kurios laikosi beveik visas internetas: TLS, VPN, el. paštas, blokų grandinės, skaitmeniniai sertifikatai.
„Harvest now, decrypt later” – grėsmė, kuri jau vyksta
Vienas dažniausiai pamirštamas, bet realiausias PQC argumentas yra ne tai, kas nutiks ateityje, o tai, kas vyksta dabar. Valstybinės žvalgybos agentūros ir sofistikuotos grupuotės jau seniai renka ir saugo užšifruotą srautą – internetinius pokalbius, el. laiškus, dokumentus – neturėdami galimybės jų iššifruoti šiandien. Strategija paprasta: surinkti duomenis dabar, palaukti, kol atsiras pakankamai galingas kvantinis kompiuteris, ir iššifruoti viską vėliau.
Tai reiškia, kad duomenys, kurie turi likti konfidencialūs 10–20 metų (medicininiai įrašai, valstybės paslaptys, verslo strategijos, intelektinė nuosavybė), yra pažeidžiami jau dabar, nepaisant to, kad kvantinis kompiuteris dar neegzistuoja praktine prasme. Būtent dėl šios priežasties finansų institucijos, vyriausybės ir gynybos sektoriaus organizacijos jau pradėjo migruoti į postkvantinius algoritmus, neatidėliodamos iki paskutinės akimirkos.
NIST standartizacijos maratonas ir ką jis mums davė
2016 metais JAV Nacionalinis standartų ir technologijos institutas (NIST) paskelbė atvirą konkursą naujiems postkvantiniams algoritmams. Procesas priminė ne biurokratinį formalumą, o tikrą kriptografų mūšį – per kelis etapus buvo pateikta virš 80 kandidatų, kurie buvo nuolat atakuojami, laužomi, kritikuojami akademinėje bendruomenėje viešai, kol liko tik patys atsparūs.
2024 metų rugpjūtį NIST oficialiai paskelbė pirmuosius standartus:
- ML-KEM (buvęs CRYSTALS-Kyber) – rakto įkapsuliavimo mechanizmas, skirtas saugiam raktų mainų procesui, panašiam į tai, ką dabar atlieka Diffie-Hellman ar ECDH.
- ML-DSA (buvęs CRYSTALS-Dilithium) – skaitmeninių parašų algoritmas, alternatyva RSA ir ECDSA parašams.
- SLH-DSA (buvęs SPHINCS+) – alternatyvus parašų algoritmas, grįstas maišos funkcijomis, tarnaujantis kaip atsarginis variantas, jei gardelinė kriptografija kada nors bus sulaužyta.
Verta paminėti ir FN-DSA (Falcon), kuris taip pat pateko į standartizacijos procesą kaip kompaktiškesnis parašų sprendimas, nors jo įgyvendinimas techniškai sudėtingesnis dėl slankiojo kablelio aritmetikos poreikio.
Kokie matematiniai pagrindai stovi už PQC
Skirtingai nuo dabartinės kriptografijos, kuri iš esmės remiasi dviem giminingomis problemomis (faktorizacija ir diskretusis logaritmas), postkvantinė kriptografija naudoja keletą visiškai skirtingų matematinių šeimų, kad sumažintų riziką, jog vieną dieną visos jos bus sulaužytos vienu smūgiu.
Gardelėmis (lattice) pagrįsta kriptografija yra šiuo metu populiariausia kryptis – tiek Kyber, tiek Dilithium remiasi vadinamąja Learning With Errors (LWE) problema arba jos struktūrizuota versija (Module-LWE). Idėja paprasta – daugiamatėje gardelėje reikia rasti artimiausią tašką prie duoto taško, o tai eksponentiškai sunku tiek klasikiniams, tiek kvantiniams kompiuteriams, kai matmenų yra pakankamai daug.
Maišos funkcijomis pagrįsta kriptografija (hash-based), kaip SPHINCS+, remiasi kriptografinių maišos funkcijų atsparumu, kuris jau seniai gerai ištirtas ir laikomas saugiu net kvantinių kompiuterių akivaizdoje (su Groverio pataisymu). Trūkumas – palyginti dideli parašų dydžiai ir lėtesnis veikimas.
Kodais pagrįsta kriptografija (code-based), pavyzdžiui, Classic McEliece sistema, egzistuoja jau nuo aštuntojo dešimtmečio pabaigos ir per tiek metų nebuvo praktiškai sulaužyta – tai suteikia didelį pasitikėjimą, bet raktų dydžiai čia matuojami šimtais kilobaitų, kas kelia problemų riboto pralaidumo aplinkose.
Daugiamatėmis (multivariate) polinominėmis lygtimis pagrįsti algoritmai kadaise atrodė perspektyvūs, tačiau po kelių skaudžių pralaimėjimų NIST konkurse (pavyzdžiui, Rainbow schema buvo sulaužyta 2022 metais naudojant tik nešiojamą kompiuterį) ši kryptis dabar vertinama atsargiau.
Praktinis diegimas – kodėl tai nėra tiesiog rakto pakeitimas
Jei kada teko diegti TLS sertifikatus ar konfigūruoti VPN, žinai, kad kriptografinių algoritmų keitimas retai būna paprastas „vieno mygtuko” sprendimas. PQC atveju iššūkiai dar didesni dėl kelių priežasčių.
Pirma, raktų ir parašų dydžiai gerokai išaugo. ECDSA parašas užima apie 64 baitus, o Dilithium parašas – kelis kilobaitus. Tinklo protokolams, kurie optimizuoti minimaliam paketo dydžiui (pavyzdžiui, DNSSEC ar IoT komunikacijos), tai reiškia realų pralaidumo ir latencijos padidėjimą.
Antra, skaičiavimo kaštai skiriasi priklausomai nuo algoritmo. Kyber santykinai greitas ir efektyvus net mobiliuose įrenginiuose, tačiau SPHINCS+ operacijos gali užtrukti pastebimai ilgiau, ypač generuojant parašus.
Trečia, ir turbūt svarbiausia – hibridinis požiūris tapo pramonės standartu pereinamuoju laikotarpiu. Google Chrome, Cloudflare, AWS ir kitos didelės organizacijos jau naudoja hibridinius rakto mainų mechanizmus, kur klasikinis ECDH ir postkvantinis Kyber veikia kartu – jei vienas algoritmas kada nors bus sulaužytas, kitas vis tiek apsaugo ryšį. Tai konservatyvus, bet protingas žingsnis, kadangi PQC algoritmai, nors ir gerai ištirti, dar neturi tokio ilgo „mūšio lauko” patikrinimo istorijos, kokį turi RSA ar AES.
Ką tai reiškia organizacijoms ir kūrėjams jau dabar
Migracija į postkvantinę kriptografiją nėra vienadienis projektas – dideles organizacijas tai gali užtrukti metus, ypač jei kalbame apie senas sistemas, patentuotą aparatinę įrangą (HSM įrenginius) ar sertifikuotus protokolus, kuriuos keisti reikia atsargiai dėl reguliacinių reikalavimų.
Praktiniai žingsniai, kuriuos verta apsvarstyti jau šiandien:
- Atlikti kriptografinį inventorizavimą – suprasti, kur ir kokie algoritmai naudojami visoje infrastruktūroje, įskaitant trečiųjų šalių bibliotekas ir aparatinę įrangą.
- Prioritetizuoti sistemas, kurios saugo ilgalaikės vertės duomenis – būtent jos labiausiai pažeidžiamos „harvest now, decrypt later” strategijai.
- Testuoti hibridinius sprendimus staging aplinkose, stebint našumo poveikį prieš diegiant produkcijoje.
- Sekti bibliotekų atnaujinimus – OpenSSL 3.2+, BoringSSL, liboqs (Open Quantum Safe projektas) jau palaiko NIST standartizuotus algoritmus.
- Neignoruoti kriptografinės agilumo koncepcijos – sistemos architektūra turėtų leisti keisti algoritmus be visiško perrašymo, nes tikėtina, kad per artimiausią dešimtmetį standartai dar keisis ar bus papildomi.
Vietoj išvadų: kur mes tikrai stovime šiandien
Realybė tokia, kad kriptografiškai reikšmingas kvantinis kompiuteris (dažnai vadinamas CRQC – cryptographically relevant quantum computer) dar neegzistuoja, ir ekspertų nuomonės apie tai, kada jis atsiras, svyruoja nuo penkerių iki dvidešimties ir daugiau metų. Tačiau tai netrukdo problemai būti aktualiai jau dabar, būtent dėl duomenų, kurių konfidencialumas turi tęstis dešimtmečius, ir dėl to, kiek laiko užtrunka visos ekosistemos migracija.
Jeigu dirbi IT srityje – nesvarbu, ar administruoji serverius, rašai backend kodą, ar tiesiog atsakingas už organizacijos saugumo strategiją – geriausia dabar praleisti kelias valandas susipažįstant su ML-KEM ir ML-DSA specifikacijomis, patikrinti, ar naudojamos bibliotekos jau turi eksperimentinį PQC palaikymą, ir pradėti mąstyti apie hibridinius sprendimus kaip apie standartą, o ne apie ateities eksperimentą. Tie, kurie palauks, kol kvantinis kompiuteris taps realybe, gali atsidurti situacijoje, kai migracija turės vykti per mėnesius, o ne per metus – ir tai retai baigiasi gerai, kai kalbame apie kriptografinę infrastruktūrą, kuri liečia kiekvieną skaitmeninę sąveiką.
Postkvantinė kriptografija nėra madingas žodis konferencijų pranešimams – tai konkretus, matematiškai pagrįstas atsakas į realią, jau žinomą grėsmę. Kuo anksčiau ji taps įprasta infrastruktūros dalimi, tuo mažiau skausmingas bus perėjimas, kai (ne jei) ateis diena, kai Shoro algoritmas nustos būti teorija.
