Plačiai naudojamas RSA algoritmas remiasi tuo, kad padauginti du pirminius skaičius, kad būtų gautas didelis šifravimo raktas, yra lengva – tačiau rasti tuos pirminius pirminius veiksnius, kai turimas tik gautas raktas, yra nepaprastai sunku. Tačiau jau seniai žinoma, kad kvantiniai kompiuteriai galės lengvai atlikti dalykus, kuriuos klasikiniai kompiuteriai laiko labai sudėtingais – pavyzdžiui, „nulaužti“ RSA raktus. Shoro algoritmu vadinamas metodas, skirtas būtent šiam tikslui, pirmą kartą buvo sukurtas 1994 metais.
Craigas Gidney iš „Google Quantum AI“ yra vienas iš 2019 m. tyrimo autorių, kuriame apskaičiuota, kad Shoro algoritmas gali būti naudojamas tam tikro dažniausiai naudojamo dydžio – 2048 bitų – RSA raktams nulaužti vos per 8 valandas naudojant kvantinį kompiuterį su 20 milijonų kubitų. Tai faktiškai leistų tokios mašinos valdytojui įsilaužti į bet kurio asmens elektroninį paštą ar banko sąskaitą, kurie buvo apsaugoti naudojant šią technologiją, ir potencialiai galėtų suteikti prieigą prie valstybės paslapčių. Dabar C. Gidney patobulino savo metodą ir sumažino reikiamą kompiuterio dydį iki mažiau nei milijono kubitų.
Oksfordo universiteto atstovas Peteris Leekas teigia, kad C. Gidney yra vienas iš šios srities lyderių, o jo naujasis straipsnis, kuris dar laukia recenzavimo, sukels sumaištį. Tačiau jis taip pat tikisi, kad tai yra paskutinis žemai kabantis vaisius Shoro algoritmo efektyvumo didinimo požiūriu.
„Per dešimtmečius jis vis mažėjo, mažėjo ir mažėjo, bet vis dar yra gana grėsmingo masto, – sako P. Leekas. – Yra galimybė, kad žmonės gali dar labiau pagerinti šio algoritmo efektyvumą – esu įsitikinęs, kad tai įmanoma – bet įtariu, kad dabar tai tikriausiai taps šiek tiek labiau inkrementiniu reiškiniu.“
„Tai geras priminimas, kad turime ir toliau judėti [postkvantinės kriptografijos] link. Šis naujas tyrimas nekeičia mūsų paskelbtų perėjimo terminų, tačiau mes viską stebime ir prireikus pakoreguosime, – sako Dustinas Moody iš JAV Nacionalinio standartų ir technologijų instituto (NIST). NIST atrinko naujos kartos šifravimo algoritmus, kurių neturėtų įveikti net kvantiniai kompiuteriai. – Vyriausybė ir pramonė jau dirba prie perėjimo“.
Vienas iš RSA privalumų yra tas, kad kvantiniai kompiuteriai vis dar toli gražu neatitinka C. Gidney reikalavimų – nes dabartinis rekordas yra šiek tiek daugiau nei 1000 kubitų. Tačiau P. Leekas sako, kad pagerėjus kvantinių kompiuterių klaidų lygiui, šis milijono kubitų reikalavimas gali dar labiau sumažėti.
„Nesitikėčiau, kad tai bus padaryta taip, kaip aprašyta šiame straipsnyje, – sako P. Leekas. – Tikėčiausi, kad bus naudojamas efektyvesnis klaidų taisymas ir kad tai darysime įrenginyje, kuris iš tikrųjų neturi milijono fizinių kubitų, bet turi inovatyvesnį būdą atlikti klaidų taisymą, efektyviau įgyvendintą. Kad tai pasiektume, reikia sumažinti tik keturis ar penkis kartus, taigi tai labai įmanoma.“
Tyrimas paskelbtas „arXiv“.
Parengta pagal „New Scientist“.