He ehdottavat menetelmää RSA-2048-avainten salauksen purkamiseksi
Ryhmä tutkijoita eri tiedekeskuksista ja yliopistoista chinos ehdotinn uusi tapa optimoidar RSA-avainparametrien tekijöiden määritysprosessi kvanttitietokoneissa.
Tutkijoiden mukaan heidän kehittämänsä menetelmä mahdollistaa kvanttitietokoneen käytön 372 qubitillä RSA-2048-avainten salauksen purkamiseen. Vertailun vuoksi, IBM Osprey, tehokkain tällä hetkellä rakennettu kvanttiprosessori, sisältää 433 kubittia, ja vuoteen 2026 mennessä IBM suunnittelee rakentavansa Kookaburra-järjestelmän, jossa on 4000 XNUMX kubittia.
On syytä mainita se menetelmä on edelleen vain teoreettinen, sitä ei ole testattu käytännössä ja se herättää skeptisyyttä joidenkin kryptografien keskuudessa.
RSA-salaus perustuu eksponentiooperaatioon suuren määrän modulo. Julkinen avain sisältää moduulin ja tutkinnon. Moduuli muodostetaan kahden satunnaisen alkuluvun perusteella, jotka vain yksityisen avaimen omistaja tietää. Kvanttitietokoneet mahdollistavat tehokkaan luvun jakamisen ongelman alkutekijöiksi, joiden avulla voidaan syntetisoida yksityinen avain julkisesta.
Toistaiseksi sen uskottiin nykyisen kehityksen vuoksi kvanttitietokoneista, RSA-avaimia, joiden koko on 2048 bittiä, ei voida murtaa pitkään aikaan, koska käyttämällä klassista Shor-algoritmia, miljoonien kubittien kvanttitietokone vaatii paljon aikaa 2048-bittisen RSA-avaimen huomioimiseen.
Kiinalaisten tutkijoiden ehdottama menetelmä kyseenalaistaa tämän oletuksen. ja jos se vahvistetaan, se mahdollistaa RSA-2048-avaimien murtamisen ei kaukaisen tulevaisuuden järjestelmissä, vaan jo olemassa olevissa kvanttitietokoneissa.
Menetelmä perustuu Schnorrin nopeaan faktorointialgoritmiin. ehdotettu vuonna 2021, mikä mahdollistaa operaatioiden määrän jyrkän vähentämisen valittaessa tavallisissa tietokoneissa. Käytännössä algoritmi ei kuitenkaan osoittautunut kovin hyödylliseksi oikeiden avainten murtamiseen, koska se toimi vain RSA-avaimille, joilla oli pieniä moduloarvoja (kokonaisluku, joka on hajotettava alkuluvuiksi). Algoritmi havaittiin riittämättömäksi suurten lukujen laskemiseen. Kiinalaiset tutkijat väittävät, että kvanttimenetelmien avulla he pystyivät kiertämään Schnorrin algoritmin rajoituksen.
Skeptisyys joiltakin kryptografeilta johtuu tosiasiasta jonka kiinalaisten tutkijoiden artikkeli osoittaa soveltamalla menetelmääsi vain pieniin lukuihin, suunnilleen samassa järjestyksessä kuin Schnorrin algoritmi toimii. Huolimatta väitteistä, että kokorajoitus on ylitetty, todisteita tai tietoja ei ole vielä toimitettu. Käytännössä menetelmän on esitetty kertovan 48-bittiset kokonaisluvut 10 qubitin kvanttitietokoneella.
Shorin algoritmi on haastanut vakavasti julkisen avaimen salausjärjestelmiin perustuvan tiedon turvallisuuden. Laajalti käytetyn RSA-2048-järjestelmän rikkominen vaatii kuitenkin miljoonia fyysisiä kubitteja, mikä ylittää nykyiset tekniset mahdollisuudet. Tässä raportoimme yleisen kvanttialgoritmin kokonaislukujen tekijöihin jakamiseen yhdistämällä klassinen hilavähennys kvanttifuzzy-optimointialgoritmiin (QAOA).
Vaadittujen kubittien määrä on O(logN/loglogN), joka on alilineaarinen kokonaisluvun bittipituudessa N, joten se on tähän mennessä eniten kubittia säästävä faktorointialgoritmi. Esitämme algoritmin kokeellisesti ottamalla huomioon jopa 48 bitin kokonaisluvut 10 suprajohtavalla kubitilla, joka on suurin kvanttilaitteessa huomioitu kokonaisluku. Arvioimme, että tarvitaan kvanttipiiri, jossa on 372 fyysistä kubittia ja tuhansien syvyys, jotta voidaan haastaa RSA-2048 algoritmimme avulla. Tutkimuksemme osoittaa suurta lupausta nopeuttaa nykypäivän meluisten kvanttitietokoneiden käyttöä ja tasoittaa tietä suurten kokonaislukujen laskemiselle, joilla on realistinen kryptografinen merkitys.
Mainitaan, että olettamus, että 372 fyysistä kubittia riittää RSA-2048-avaimen ottamiseksi huomioon, on teoreettinen, joten on hyvin todennäköistä, että Schnorrin algoritmiin perustuvalla kvanttimenetelmällä on samat skaalausongelmat, eikä se toimi lukuja otettaessa. .
Jos skaalausongelma todella ratkeaa, suurten alkulukujen faktoroinnin monimutkaisuuteen perustuvien kryptoalgoritmien turvallisuus ei heikkene odotetusti pitkällä aikavälillä, vaan jo tänään.
Lopuksi, jos olet kiinnostunut tietämään enemmän siitä, voit tutustua sen yksityiskohtiin seuraava linkki.