A Cognition szerint rekordot döntött a Devin az RSA-260 faktorizálásával

Új rekord az RSA-faktorizálásban

A Cognition szeptember 9-én közzétett beszámolója szerint kutatócsapata Devin szoftverfejlesztő ügynökökkel faktorizálta az RSA-260-at. A 260 számjegyű RSA-szám két prímtényező szorzataként írható fel. A vállalat a teljes faktorizációt is közölte: 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199 egyenlő 4397328654844826923795068102505872571721883526553349659561256924505973939597593482272505698004801207988043088656411102133523080581 és 5028695206842569864686141618253083416610081090075366674776775706538324961364412200138116378509733307971876652984898985905923678379 szorzatával.

Az RSA-260 ezzel a legnagyobb nyilvánosan megoldott RSA Factoring Challenge feladattá vált. Az előző rekordot az RSA-250 jelentette, amelyet 2020 februárjában faktorizáltak. A Cognition szerint az ilyen feladatok azt mérik, mennyire megvalósítható az RSA kriptográfiai rendszer feltörése.

GPU-kra írták át a számításigényes algoritmust

A faktorizáláshoz a Cognition a general number field sieve, röviden GNFS algoritmus új, GPU-kra készített megvalósítását használta. A GNFS a vállalat szerint a nagyjából 100 számjegynél hosszabb számokhoz ismert leghatékonyabb algoritmus, és korábbi RSA-rekordoknál is ezt alkalmazták.

A megoldás alapját a CADO-NFS jelentősen módosított változata adta. A Cognition nem számolt be új algoritmikus áttörésről, a fejlesztés főként teljesítményhangolásból állt. A csapat a rácsszűrést és a ritka lineáris rendszerek megoldását GPU-kon futtatta, kihasználva azok nagy memória-sávszélességét.

A Devin feladata kezdetben egy olyan GPU-s rácsszűrő elkészítése volt, amely közvetlenül behelyettesíthető a CADO-NFS CPU-s, las nevű komponense helyére. A Cognition beszámolója szerint a rendszer két óra után kapott további követelményt az RSA-250 paramétereinek kezelésére, majd újabb hét optimalizálás következett a rácsszűrés és a GNFS többi lépésének javítására.

Mintegy 400 ezer dollárnyi számítás

A Cognition becslése szerint az RSA-260 faktorizálása összesen körülbelül 4900 GPU-napot, vagyis 13,5 GPU-évet igényelt. A jelenlegi piaci árakon ez nagyjából 400 ezer dollárnak felel meg.

A számításból 643 GPU-napot vitt el a polinomkiválasztás, 3813 GPU-napot a rácsszűrés, 467 GPU-napot pedig a lineáris rendszer megoldása. Utóbbi szakasz körülbelül 7 százalékában nem történt előrelépés összeomlások vagy más munkák miatti elővétel miatt. A polinomkiválasztás szokatlanul magas költségét a Cognition az operátori hibákhoz kötötte.

A munkát a vállalat egy klaszterének szabad vagy töredezett kapacitásán futtatták. Ezek a gépek elsősorban nagy nyelvi modellek tanítására és futtatására szolgálnak, de a munkaterhelések elhelyezése miatt egyes rackekben időnként egy vagy két csomópont kihasználatlan marad. A GPU-s rácsszűrés sok kisebb, egymástól független feladatra bontható, egyetlen csomóponton is futtatható, és azonnal megszakítható, ezért illeszkedett ehhez a kapacitáshoz.

Az RSA-1024 még elérhetőbbé válhat

A Cognition szerint az RSA-1024 egy 309 számjegyű faktorizálási feladatnak felel meg, és a szabványos GNFS-skálázás alapján 78-szor több számítást igényelhet az RSA-260-nál. A vállalat piaci GPU-árakon körülbelül 30 millió dollárra becsüli egy RSA-1024 szám faktorizálását. Azt is valószínűnek tartja, hogy további, mérsékelt optimalizálással ez a költség a felére vagy még alacsonyabbra csökkenthető.

A Cognition hangsúlyozza, hogy az RSA-1024 bizonytalansága önmagában nem új megállapítás. A beszámoló szerint a fejlesztés jelentősége a potenciálisan alacsonyabb költségben és időigényben, az elvégzésre képes szereplők körének bővülésében, valamint abban áll, hogy a faktorizálás gyorsításán nem kizárólag kriptográfiai szakértők dolgozhatnak.

Az RSA-2048 esetében a vállalat jóval óvatosabb: becslése szerint ez a méret az RSA-1024-nél nagyjából egymilliárdszor nehezebb, ezért a mostani hatékonyságnövekedés nem befolyásolja érdemben a faktorizálás megvalósíthatóságát.