Ak ste sa dnes ráno prihlásili do svojho bankového účtu, bezpečnostné protokoly sú zrejme stále spoľahlivé, ale vo svete technológií sa všetko mení veľmi rýchlo. Tím vedcov z Číny práve demonštroval, že matematika, na ktorej je založené šifrovanie RSA, začína podliehať vplyvu kvantového sveta.
Pomocou kvantového procesora vytvoreného spoločnosťou D‑Wave Systems výskumníci vyhlásili, že rozložili na jednoduché násobky 22-bitové celé číslo RSA, ktoré sa predtým nedalo rozložiť na zariadení tej istej triedy. Experiment vykonali Wang Chao a jeho kolegovia zo Šanghajskej univerzity.
Reputácia RSA ako spoľahlivého šifrovacieho algoritmu
Keď sa šifrovanie RSA objavilo v roku 1977, bolo chválené za to, že spájalo bezpečnosť s obtiažnosťou rozloženia veľkého polodvojitého čísla na dva jednoduché činitele.
Klasické počítače stále potrebujú subexponenciálny čas na prelomenie moderných 2048-bitových kľúčov a najväčší kľúč, ktorý bol doteraz prelomený tradičnými metódami, má len 829 bitov (RSA-250) po niekoľkých týždňoch práce na superpočítači.
„Využitím výhod D‑Wave sme úspešne rozložili 22-bitové celé číslo RSA, čím sme demonštrovali potenciál kvantových strojov na riešenie kryptografických úloh,“ píšu autori.
Skupina transformovala faktorizáciu na úlohu kvadratickej neobmedzenej binárnej optimalizácie, ktorú systém D-Wave Advantage rieši prechodom kubitov cez energetické bariéry v hľadaní stavu s najnižšou energiou.
Ten istý metód použili aj na šifry s substitúciou a permutáciou, ako sú Present a Rectangle, a nazvali to „prvým prípadom, keď skutočný kvantový počítač predstavuje podstatnú hrozbu pre niekoľko plnohodnotných algoritmov so štruktúrou SPN, ktoré sa dnes používajú“.
Dvadsaťdva bitov stále má význam
22-bitový kľúč je triviálne malý v porovnaní s produkčným RSA, ale test má význam, pretože tento prístup prekročil rámec predchádzajúcich demonštrácií, ktoré sa zastavili na 19 bitov a vyžadovali viac kubitov na premennú.
Podľa článku zníženie koeficientov lokálneho poľa a spojenia v Izingovom modeli znižuje šum, čo umožňuje žíhaču častejšie dosahovať správne faktory a ukazuje cesty k dlhším kľúčom.
„Vývoj kvantových počítačov môže vážne ohroziť bezpečnosť údajov a dôvernosť rôznych podnikov,“ varoval Prabhjot Kaur z analytickej spoločnosti Everest Group, ktorý sa na výskume nepodieľal.
Odpálenie proti Shorovmu sľubu
Univerzálne kvantové stroje založené na ventiloch vykonávajú Shorov algoritmus, ktorý v princípe môže zničiť RSA tým, že nájde periodu modulárnej elevácie za polynomiálny čas.
Tieto zariadenia stále majú problémy s opravou chýb, zatiaľ čo D-Wave anealery, hoci nie sú univerzálne, už obsahujú viac ako 5000 kubitov a vyhýbajú sa hlbokým schémam vďaka použitiu chladiacej látky s teplotou 15 mK a analógovej evolúcii.
Žíhanie prevyšuje kombinatorickú optimalizáciu, preto šanghajský tím preformuloval faktorizáciu ako úlohu vyhľadávania tohto typu namiesto použitia Shoreovej metódy na nájdenie periódy.
Táto stratégia obchádza súčasné obmedzenia počtu kubitov v strojoch založených na bránach, ale platí za to exponenciálnym škálovaním, preto sa tentoraz podarilo prelomiť len 22-bitový modul.
Politické hodiny tikajú ďalej
Normalizačné orgány nečakajú. V auguste 2024 NIST vydal FIPS 203, 204 a 205, prvé federálne štandardy pre postkvantovú kryptografiu založené na mriežkových úlohách, a v marci 2025 vybral HQC pre ďalšiu fázu.
Na podujatí v Bielom dome venovanom uverejneniu týchto noriem bolo americkým úradom odporučené, aby začali s výmenou zraniteľných kľúčov, pretože útočníci pravdepodobne už zhromažďujú šifrované údaje na účely útokov podľa princípu „hacknúť teraz, dešifrovať neskôr“.
„Spoločnosti by mali k aktualizácii kryptografie pristupovať ako k viacročnému infraštruktúrnemu projektu,“ uviedol CIO Wall Street Journal v brífingu, keď sa minulý rok blížilo konečné schválenie noriem. Vedúci predstavitelia technologických spoločností tento názor podporili.
RSA proti kvantovému hackingu
Väčšina spoločností ešte neaktualizovala svoje kryptografické inventáre a mnohé ani nevedia, od akých algoritmov závisia ich systémy.
Bezpečnostní experti odporúčajú začať s interným auditom, aby sa zistili všetky prípady použitia RSA, ECC a iných zraniteľných algoritmov, skôr ako sa vypracuje plán nahradenia.
Hoci úplný prechod môže trvať roky, organizácie môžu začať testovaním kvantovo bezpečných knižníc, ako je Open Quantum Safe, a zavádzaním hybridných metód výmeny kľúčov.
Dobrou voľbou je tiež integrácia kryptoflexibility – možnosti nahradiť kryptografické algoritmy bez prepracovania celého systému. To uľahčí budúce aktualizácie v miere, ako budú vznikajúť nové štandardy.
Čo bude ďalej a na čo treba dávať pozor
RSA s veľkými kľúčmi je stále bezpečný, ale výskum ukazuje, že vylepšenia hardvéru a inteligentnejšie integrované riešenia naďalej zmenšujú túto medzeru.
Spoločnosť D-Wave plánuje koncom tohto roka vydať procesor s topológiou Zephyr, obsahujúci viac ako 7000 kubitov, pričom každá aktualizácia topológie zlepšuje konektivitu, čo zase znižuje počet fyzických kubitov potrebných na jednu logickú premennú.
Medzitým kryptografi odporúčajú používať hybridné schémy, ktoré obalujú algoritmy založené na reťazcoch, ako je CRYSTALS-Kyber, okolo klasických RSA podpisov, aby sa zabezpečila priama tajnosť v prechodnom období.
Organizácie, ktoré desiatky rokov uchovávajú dôverné údaje, ako sú zdravotné záznamy, genetické súbory alebo diplomatické telegramy, môžu stratiť najviac, ak budú čakať na príchod plnohodnotného kvantového počítača.
Niektorí pozorovatelia poukazujú na to, že výsledok dosiahnutý v Šanghaji bol založený na intenzívnom klasickom predbežnom a následnom spracovaní a že na nájdenie správnych faktorov annihilátora bolo stále potrebných veľa pokusov.
História však ukazuje, že kryptoanalytické dôkazy konceptu zriedka zostávajú malé: DES bol prelomený na stroji v hodnote 250 000 dolárov v roku 1998, len štyri roky po objavení prvých čiastočných prelomení.
