Tényleg itt a minden titkosítást feltörő kvantumszámítógép?

Bő három év telt el azóta, hogy a Google hivatalosan is bejelentette, hogy sikerült elérniük a kvantumfölényt, azaz a kvantumszámítógépük olyan problémát oldott meg, amely a legerősebb hagyományos szuperszámítógépeknek is több ezer évébe tellett volna. A hír akkoriban nagy port kavart, sokan egyből a jelenleg érvényben lévő kriptográfiai modellek bukását vizionálták, azonban a kvantumszámítógépek közel sem voltak olyan fejlettségi szinten, hogy ez bekövetkezzen, és bár azóta történtek komolyabb előrelépések, ez még mindig nem változott.

Az utóbbi időszakban viszont megint előkerült a téma, miután december végén kijött egy kínai tanulmány, amely azt állította, hogy létezik olyan módszer, amellyel fel lehet törni az egyik legelterjedtebb titkosítási eljárás, az RSA betonbiztosnak gondolt kulcsait, méghozzá egy olyan kvantumszámítógép segítségével, amelynél erősebb már ma is létezik. Erről többek közt a Financial Times is írt cikket, egy január végén megjelent tanulmány pedig erre is rálicitált, így ismét felmerült tehát a kérdés, hogy közel van-e a nap, amikor a kvantumszámítógépek minden titkunkat felfedik.

A válasz: egyértelműen nem, és nem is nagyon lehet megmondani, hogy mikor juthat el arra a szintre a technológia, hogy tartani kelljen tőle. Készülni viszont ettől még nem felesleges arra, hogy ez egyszer bekövetkezhet.

Az RSA és az új tanulmány

A történet megértéséhez első körben érdemes gyorsan végigvenni, hogy mi az az RSA-eljárás, elvégre az első tanulmány mögött álló kínai kutatók kifejezetten ezt, azon belül is a jelenleg sztenderdnek mondható 2048 bites kulcsokat emelték ki. Az RSA egy nyílt kulcsú titkosító algoritmus, melynek gyakorlati biztonságát az adja, hogy a nagy számok prímtényezőkre bontására, vagyis faktorizációjára jelenleg nem létezik minden esetben hatékony algoritmus. Néhány számjegynél még könnyű megtalálni a prím osztókat, de százas nagyságrendnél már akkora számítási kapacitás kell hozzá, hogy a gyakorlatban kivitelezhetetlenné válik a dolog.

Az eljárás megalkotói által alapított RSA Laboratories korábban külön kihívást is szentelt az RSA-kulcsok feltörésének, és bár ez 2007-ben lezárult, többen azóta is dolgoznak a problémán, utoljára 2020-ban sikerült faktorizálni egy kétszázötven számjegyből álló számot (ez volt az RSA-250). A korábban még a kihívás hivatalos részeként bedobott, hatszáztizenhét számjegyből álló RSA-2048 esetében (ahol a 2048 a bitek számát jelöli) viszont ennek még a közelébe sem jutottak. Egy két évvel ezelőtti svéd tanulmány szerint egy 20 millió qubites kvantumszámítógéppel nyolc óra alatt lehetne feltörni egy ilyen kulcsot, francia kutatók pedig ugyancsak két éve arról írtak, hogy egy 13 436 qubites kvantumprocesszor is képes lehet erre 177 nap alatt.

A decemberben közzétett kínai tanulmány viszont ennél sokkal izgalmasabb megoldással kecsegtetett: ebben arról volt szó, hogy ha kombinálják Claus Peter Schnorr 2021-es, hagyományos faktorizációs algoritmusát egy kvantumoptimalizációs algoritmussal, akkor akár egy 372 qubites kvantumszámítógéppel is fel lehet törni az RSA-2048-at. A kínaiaknak ilyen nem volt a birtokában, de az algoritmus segítségével képesek voltak mindössze 10 qubittel faktorizálni egy 48 bites, vagyis tizenöt számjegyű számot, ami az eddigi legjobb eredmény kvantumszámítógépen. Mindez leginkább azért volt érdekes, mert az IBM tavaly bejelentett, Osprey nevű kvantumprocesszora

a maga 433 qubitjével erősebb annál, amivel a kínaiak szerint már törni lehetne az 2048 bites RSA-kulcsokat, azaz ha itt nem is sikerült a törés, felmerült a lehetősége annak, hogy kivitelezhető lehet.

A tanulmányt persze több okból is érdemes volt fenntartásokkal kezelni, első körben például azért, mert még csak az ArXiv nevű pre-print szerveren jelent meg, így lektoráláson nem esett át. Fontosabb probléma volt ugyanakkor, hogy Schnorr már említett, hagyományos számítógépekre írt algoritmusa ugyan alacsony bitméretnél valóban alkalmas arra, hogy prímtényezőkre bontson számokat, viszont nem skálázható, vagyis több számjegynél egyelőre ismeretlen okból nem lehet használni. A kínai kutatók állítása szerint ezt a problémát tudták áthidalni kisebb kapacitású kvantumszámítógépekkel, de a tanulmányból nem derült ki, hogy pontosan hogyan, és a gyakorlatban sem tesztelték, hogy nagyobb bitszámnál is működik-e a dolog.

Erre mutatott rá többek közt a megjelenés után a témával komolyan foglalkozó IT-biztonsági szakértő, Bruce Schneier, illetve valamivel később az egyik legelismertebb kvantumalgoritmus-szakértő, Scott Aaronson is. Aaronson elég sarkosan fogalmazott, nemcsak Schnorr algoritmusával, hanem az azt felturbózó kvantumoptimalizációs algoritmussal szemben is, amelyről szerinte egyelőre még nem sikerült hitelt érdemlően bizonyítani, hogy a gyakorlatban bármire jó lenne. Mint írta, szerinte csodára lenne szükség, hogy a használata látható előnnyel járjon ahhoz képest, hogy valaki egy laptopról futtatja Schnorr algoritmusát, ha pedig azzal fel lehetne törni az RSA-t, akkor ez már rég megtörtént volna.

Ennyire nem gyors a fejlődés

Dr. Asbóth János kvantumfizikus, a BME Elméleti Fizikai Tanszékének docense, a Wigner Fizikai Kutatóközpont kutatója kérdésünkre elmondta, hogy a nagy különbség az itt felmerült módszer, és Peter Shor 1994-ben megalkotott kvantumalgoritmusa között az, hogy itt igazából kis mértékben támaszkodnak a kvantumszámítógépekre. Ezért is volt lehetséges az, hogy képesek voltak 48 bites számokat feltörni anélkül, hogy 48 qubitet használtak volna ehhez, mert az algoritmus nagy része nem kvantumszámítógépen fut. Azt is érdemes megemlíteni, hogy bár az IBM Osprey papíron nagyobb teljesítményű, mint amire a kínaiak szerint szükség lenne az RSA-2048 feltöréséhez,

a kutató szerint még nem végeztek ennek a kalibrációjával sem, inkább azért jelenthették be hivatalosan, hogy tartsák magukat a korábban felvázolt menetrendhez.

Arra a kérdésre, hogy mikorra juthat el olyan szintre a kvantumtechnológia, hogy érdemben készülni kelljen rá, például a poszt-kvantum-kriptográfiai modellek bevezetésével, Asbóth azt mondta, hogy ezt jelenleg nagyon nehéz megmondani. A 2010-es években szerinte az optimizmus volt a jellemző, a kvantumszámítógépek kapcsán is előkerült a hagyományos számítástechnikában érvényes Moore-törvény, és persze ott volt az is, hogy 2019-ben a Google bejelentette, hogy az 53 qubites, Sycamore nevű kvantumprocesszora elérte a kvantumfölényt. A Sycamore egy olyan problémát oldott meg percek alatt, amin a legerősebb szuperszámítógépek is több ezer évig dolgoztak volna. Azóta viszont kiderült, hogy a konvencionális számítógépek ezen a téren versenyre kelhetnek a kvantumtechnológiával.

Erre tavaly nyáron mutatott rá egy kínai kutatócsoport, amely egy új algoritmussal a Google mérnökei által prognosztizált tízezer év helyett 15 óra alatt megoldotta ugyanezt a problémát, és azt becsülték, hogy ez jóval gyorsabb lett volna, ha egy szuperszámítógéppel dolgoznak 512 grafikai processzor helyett. Asbóth elmondása szerint négy évvel később ott tartunk, hogy van ugyan 433 qubites processzora az IBM-nek, de még nincs megfelelően kalibrálva, az elődje, a 127 qubites Eagle esetében pedig elég nagy a szórás, hogy melyik bit milyen, ezért inkább 100 qubit lehet a reális szám. A kiolvasás is nagyon pontatlan, inkább 1-2 százalék a hiba, ami egyszerűen túl magas a technológia szempontjából hosszú távon kulcsfontosságú hibajavításhoz, ahol menet közben is folyamatosan szükség van erre.

A fejlődés persze tagadhatatlan, mind a Magyarországon a Műegyetemen vizsgált szupravezető áramkörök, mind pedig a csapdázott ionokkal működő gépek terén, de nem olyan gyors ütemű, mint a hagyományos számítógépeknél. Azt, hogy jelenleg hol állunk ezen a téren, remekül illusztrálja ez a grafikon, melynek alkotója úgy látja, a tavalyi előrelépések ellenére is még mindig exponenciális fejlődésre lenne szükség, hogy a kvantumszámítógépek veszélyt jelentsenek a jelenlegi kriptográfiai modellekre. Asbóth szerint az egész kvantumszámítógépes hardver annyira friss, hogy egyelőre még nincs is igazi ipari erőfeszítés, így felesleges is lenne elvárni a gyors fejlődést, és bár a cégeknek érdekében áll folyamatosan nagyobb számokat bemondani, jelenleg nem tűnik reálisnak, hogy 2030-ra tényleg érkezzen az egymillió qubites kvantumszámítógép, amit az elmúlt években a Google és az IBM is beígért.

Felkészülni azért érdemes

Annak ellenére ugyanakkor, hogy még láthatóan nincs terítéken a legelterjedtebb kriptográfiai algoritmusok feltörése, évek óta dolgoznak már poszt-kvantum-kriptográfiai modelleken, a versenyeztetésük és a sztenderdizálásuk pedig jelenleg is zajlik. Az amerikai Nemzeti Szabványügyi és Műszaki Intézet (NIST) például 2016-ban írt ki versenyt erre, amelyben Asbóth elmondása szerint magyar kutatók is részt vettek, tavaly nyáron pedig bemutatta az első négy olyan algoritmust, amelyek ellenállóak lesznek a jövő kvantumszámítógépeivel szemben is.

Az Egyesült Államokban szövetségi szinten is felvették már a kesztyűt, és az állami és önkormányzati szervek elektronikus információbiztonságáról szóló 2013-as törvény tavaly nyáron hatályba lépett módosítása értelmében elméletileg egy rakás szervezetet Magyarországon is köteleztek már a poszt-kvantum-titkosítás alkalmazására. Pfeiffer Szilárd, a Balasys információbiztonságot népszerűsítő szakértője szerint a problémakör olyan, mint a globális felmelegedés – van egy létező probléma, amit ha nem kezelünk a jelenben, a kritikussá válásakor már nem is fogunk tudni kezelni.

A technológiába komoly pénzek mennek, látható is a fejlődés és bármikor be is robbanhat a dolog, de a nagyra törő állítások után érkező cáfolatokból látszik, hogy egyelőre sokszor nagyobb a füstje, mint a lángja. Ha törhetővé válik az RSA, akkor visszamenőlegesen minden adat, ami ezzel, vagy más, jelen állás szerint a gyakorlatban megoldhatatlan matematikai problémán alapuló algoritmussal lett titkosítva, egy csapásra törhetővé válik. Pfeiffer hozzátette, hogy manapság az RSA-kulcsoknál 2048 bit alatt semmit nem ajánlott használni, de egyre inkább terjed a 3072-es és a 4096-os bitméret is. A bitszám duplájára növelésével a töréshez szükséges számítási igény exponenciálisan nő, tehát eddig lehetett előre menekülni,

ha viszont megjelennének a használható kvantumszámítógépek, a mostani jóslatok szerint ez már nem feltétlenül segítene, így mindenképpen szükség lenne az új algoritmusok használatára.

Ez annak ellenére is célszerű lenne, hogy egyelőre ettől a ponttól még minden jel szerint nagyon messze vagyunk, ugyanis a protokollváltás azzal járna, hogy rengeteg adatot újra kellene titkosítani. Az új algoritmusok implementációiban kezdetben gyakoribbak lehetnek a hibák, hiszen az évtizedek alatt kiforrott technológia helyett gyökeresen mást kellene használni, ezeket a hibákat pedig nehezebb lesz felfedezni, mert az új algoritmusok matematikailag is összetettebbek lesznek majd a prímszámokkal végzett műveleteknél.

A szakértő szerint azért is érdemes lenne új modelleket sztenderdizálni, függetlenül attól, hogy 10-20 éven belül érkeznek meg a kvantumszámítógépek, vagy sokkal később. Egyrészt mert jelenleg nincsen sokféle aszimmetrikus kriptográfiai algoritmus, a diverzifikáció pedig biztonsági szempontból mindenképpen hasznos lenne, másrészt pedig mert egy ilyen átállást alapból is csak hosszú évek alatt lehet lezongorázni, közvetlen fenyegetettség híján pedig még kevésbé hajlandó bárki érdemben foglalkozni vele. Ha viszont menet közben mégis beköszönt a kvantumszámítógépek kora, hirtelen rengeteg olyan adatot lehet majd feltörni, amelyeket a „lopd el most, törd fel később” elv alapján éppen erre számítva nyúltak le a kiberbűnözők, legálisan és illegálisan egyaránt.