Kaip kvantinis kompiuteris gali sulaužyti 2048 bitų RSA šifravimą per 8 valandas

Iš arti D-Wave Vesuvius lusto Steve'as Jurvetsonas | Flickr

Daugelis žmonių nerimauja, kad kvantiniai kompiuteriai galės nulaužti tam tikrus kodus, naudojamus saugiems pranešimams siųsti. Aptariami kodai užšifruoja duomenis naudodami matematines spąstų funkcijas, kurios lengvai veikia viena kryptimi, bet ne kita. Tai leidžia lengvai užšifruoti duomenis, tačiau labai sunku juos iššifruoti be specialaus rakto.

Šios šifravimo sistemos niekada nebuvo nepalaužiamos. Vietoj to, jų saugumas pagrįstas didžiuliu laiko kiekiu, kurio prireiktų klasikiniam kompiuteriui atlikti šį darbą. Šiuolaikiniai šifravimo metodai yra specialiai sukurti taip, kad jų dekodavimas truktų tiek laiko, kad jie praktiškai nepalaužiami.

Tačiau kvantiniai kompiuteriai pakeičia šį mąstymą. Šios mašinos yra daug galingesnės nei klasikiniai kompiuteriai ir turėtų lengvai sulaužyti šiuos kodus.

Tai kelia svarbų klausimą – kada kvantiniai kompiuteriai bus pakankamai galingi, kad tai padarytų? Po šios datos bet kokia informacija, apsaugota šia šifravimo forma, tampa nesaugi.

Taigi kompiuterių mokslininkai bandė apskaičiuoti išteklių, kurių gali prireikti tokiam kvantiniam kompiuteriui, ir tada išsiaiškinti, kiek laiko užtruks, kol bus galima pastatyti tokią mašiną. Ir atsakymas visada buvo dešimtmečius.

Šiandien šį mąstymą reikia peržiūrėti, nes Craig Gidney dirba „Google“ Santa Barbaroje ir Martin Ekerå KTH Karališkajame technologijos institute Stokholme, Švedijoje. Šie vaikinai rado efektyvesnį būdą kvantiniams kompiuteriams atlikti kodo laužymo skaičiavimus, sumažindami jiems reikalingus išteklius.

Vadinasi, šios mašinos yra daug arčiau tikrovės, nei kas nors įtariama. Dėl to vyriausybėms, karinėms ir saugumo organizacijoms, bankams ir visiems kitiems, kuriems reikia apsaugoti duomenis 25 metus ar ilgiau, bus nepatogu skaityti.

Pirmiausia šiek tiek fono. Dar 1994 metais amerikiečių matematikas Peteris Šoras atrado kvantinį algoritmą, kuris pranoko klasikinį atitikmenį. „Shor“ algoritmas lemia didelius skaičius ir yra esminis elementas laužant kodų, pagrįstų spąstais, procese.

Trapdoor funkcijos yra pagrįstos daugybos procesu, kurį lengva atlikti viena kryptimi, bet daug sunkiau atlikti atvirkščiai. Pavyzdžiui, nereikšminga padauginti du skaičius: 593 iš 829 yra 491 597. Tačiau sunku pradėti nuo skaičiaus 491 597 ir išsiaiškinti, kuriuos du pirminius skaičius reikia padauginti, kad jis būtų gautas.

Ir darosi vis sunkiau, nes skaičiai didėja. Iš tiesų, kompiuterių mokslininkai mano, kad klasikiniam kompiuteriui praktiškai neįmanoma apskaičiuoti didesnių nei 2048 bitų skaičių, o tai yra dažniausiai naudojamos RSA šifravimo formos pagrindas.

Šoras parodė, kad pakankamai galingas kvantinis kompiuteris gali tai padaryti be vargo, o tai sukėlė smūgio bangas per saugumo pramonę.

Ir nuo to laiko kvantinių kompiuterių galia auga. 2012 m. fizikai naudojo keturių kubitų kvantinį kompiuterį 143 koeficientui nustatyti. Tada 2014 m. jie panaudojo panašų įrenginį, kad koeficientas būtų 56 153.

Nesunku įsivaizduoti, kad esant tokiam progreso greičiui, kvantiniai kompiuteriai netrukus turėtų pranokti geriausius klasikinius.

Ne taip. Pasirodo, kvantinis faktoringas praktiškai yra daug sunkesnis, nei būtų galima tikėtis. Priežastis ta, kad triukšmas tampa didele didelių kvantinių kompiuterių problema. Šiuo metu geriausias būdas kovoti su triukšmu yra naudoti klaidas taisančius kodus, kuriems patiems reikia didelių papildomų kubitų.

Atsižvelgiant į tai, labai padidėja išteklių, reikalingų 2048 bitų skaičiams koeficientuoti. 2015 metais mokslininkai apskaičiavo, kad kvantiniam kompiuteriui prireiks milijardo kubitų, kad šis darbas būtų patikimai atliktas. Tai žymiai daugiau nei 70 kubitų šiuolaikiniuose kvantiniuose kompiuteriuose.

Tuo remdamiesi saugumo ekspertai galėjo pagrįsti mintį, kad praeis dešimtmečiai, kol pranešimus su 2048 bitų RSA šifravimu galės sulaužyti kvantinis kompiuteris.

Dabar Gidney ir Ekerå parodė, kaip kvantinis kompiuteris gali atlikti skaičiavimus naudojant tik 20 milijonų kubitų. Iš tiesų, jie rodo, kad tokiam įrenginiui atlikti skaičiavimą prireiktų vos aštuonių valandų. [Dėl to] blogiausio atvejo įvertinimas, kiek kubitų reikės norint apskaičiuoti 2048 bitų RSA sveikuosius skaičius, sumažėjo beveik dviem dydžiais, teigia jie.

Jų metodas orientuotas į efektyvesnį būdą atlikti matematinį procesą, vadinamą moduliniu eksponentu. Tai yra likučio radimo procesas, kai skaičius padidinamas iki tam tikro laipsnio, o tada padalinamas iš kito skaičiaus.

Šis procesas yra pati brangiausia operacija pagal Šoro algoritmą. Tačiau Gidney ir Ekerå rado įvairių būdų, kaip jį optimizuoti, žymiai sumažindami išteklius, reikalingus algoritmui vykdyti.

Tai įdomus darbas, kuris turėtų turėti svarbių pasekmių visiems, kaupiantiems informaciją ateičiai. 20 milijonų kubitų kvantinis kompiuteris šiandien tikrai atrodo tolima svajonė. Tačiau šie ekspertai turėtų užduoti sau klausimą, ar toks įrenginys galėtų būti įmanomas per 25 metus, kai jie nori apsaugoti informaciją. Jei jie mano, kad taip, tada jiems reikia naujos šifravimo formos.

Iš tiesų, saugumo ekspertai sukūrė postkvantinius kodus, kurių net kvantinis kompiuteris negalės nulaužti. Taigi jau šiandien galima apsaugoti duomenis nuo kvantinių kompiuterių atakų ateityje. Tačiau šie kodai dar nėra naudojami kaip standartas.

Paprastiems žmonėms rizika yra maža. Daugelis žmonių naudoja 2048 bitų šifravimą ar kažką panašaus, kad galėtų atlikti tokias užduotis kaip kredito kortelės duomenų siuntimas internetu. Jei šios operacijos bus įrašytos šiandien ir sulaužytos po 25 metų, mažai kas bus prarasta.

Tačiau vyriausybėms gresia daugiau. Pranešimai, kuriuos jie siunčia šiandien, pavyzdžiui, tarp ambasadų ar kariuomenės, gali būti reikšmingi po 20 metų ir todėl juos verta laikyti paslaptyje. Jei tokie pranešimai vis dar siunčiami naudojant 2048 bitų RSA šifravimą ar kažką panašaus, šios organizacijos turėtų greitai pradėti nerimauti.

Nuoroda: arxiv.org/abs/1905.09749 : Kaip koeficientuoti 2048 bitų RSA sveikuosius skaičius per 8 valandas naudojant 20 milijonų triukšmingų kubitų

paslėpti