Cognition inženieris Eriks Lu 3. septembrī plkst. 01:48 UTC pabeidza 260 ciparu skaitļa RSA-260 sadalīšanu divos pirmskaitļos. 9. septembrī viņš publicēja aprakstu ar skaitļiem: rēķins prasīja aptuveni 4900 GPU dienas jeb 13,5 GPU gadus, kas pēc tirgus cenām maksā ap 400 000 dolāru.
Iepriekšējais publiskais rekords bija RSA-250, ko 2020. gada februārī sadalīja akadēmiķu komanda. Sešarpus gadus neviens to nebija pārspējis. RSA-260 ir 862 bitu skaitlis. Abi tā reizinātāji ir tieši 431 bitu gari.
Ko tieši sadalīja
RSA Factoring Challenge skaitļi ir mēraukla tam, cik dārgi ir uzlauzt RSA šifrēšanu. Mūsdienu publiskās atslēgas satur 2048 bitu jeb aptuveni 617 ciparu problēmu. 1024 bitu atslēgas jeb 309 ciparus par novecojušām atzina 2013. gadā.
Lu izmantoja vispārīgo skaitļu lauka sietu (GNFS), efektīvāko zināmo algoritmu skaitļiem virs aptuveni 100 cipariem. Programmatūras pamatā ir stipri pārtaisīts CADO-NFS, tā pati atvērtā koda pakotne, ar kuru tika sadalīts RSA-250. Jaunu matemātiku Lu nepiesaka. Viņa vārdiem, vajadzēja tikai “labu veco veiktspējas inženieriju”, lai izmantotu GPU atmiņas joslas platumu.
Pirmais paziņojums bija tukšs. Lu sociālajā tīklā publicēja 130 ciparu skaitli un pajokoja par papīru un zīmuli. Daļa izdevumu joku pārpublicēja kā faktu. Scientific American 4. septembrī rakstīja, ka metode nav zināma. Aprakstā Lu atsevišķi noliedz abas versijas: 130 ciparu pirmskaitļus ar roku viņš neminēja, kvantu datora Cognition nav.
GPU sietu Devin uzrakstīja vienā naktī
13. augustā plkst. 00:11:58 pēc Klusā okeāna laika Lu iedeva Devin uzdevumu uzrakstīt GPU sietu, kas aizstātu CADO-NFS komponenti las. Divas stundas vēlāk viņš piebilda, ka tam jāspēj apstrādāt RSA-250 parametrus. Tad viņš aizgāja gulēt. Pēc vēl septiņām stundām iterāciju jaunais siets glas bija ātrāks par CPU versiju.
Līdz šim visos publiskajos GNFS rekordos sietu darbināja tikai procesori. Režģa sijāšana prasa miljardiem sīku, savstarpēji neatkarīgu darba vienību ar nejaušu piekļuvi lielam masīvam. Tieši šī piekļuves shēma ilgi turēja to prom no GPU. RSA-260 gadījumā sijāšana saražoja 8,3 miljardus retinātu lineāru sakarību virs GF(2).
Devin pārtaisīja arī pārējo konveijeru: polinomu atlases pirmo pakāpi (ar gabaliem no msieve), dublikātu tīrīšanu, matricas apvienošanu, bloka Wiedemann algoritmu lineārās sistēmas risināšanai un kvadrātsakņu soli. Neaiztikti palika četri CADO-NFS gabali: cado-nfs.py, polyselect_ropt, makefb un dup1.
Rēķins pa soļiem
Lu sadala 4900 GPU dienas trīs daļās. Polinomu atlase paņēma 643 GPU dienas. Viņš pats to sauc par nesamērīgi daudz un vaino savu operatora nemāku. Sijāšana paņēma 3813 GPU dienas. Lineārās sistēmas risināšana paņēma 467 GPU dienas, no kurām aptuveni 7 % aizgāja zudumā avāriju vai svarīgāku darbu dēļ.
Naudā tas Cognition neizmaksāja neko. Aprēķins gāja uz brīviem mezgliem NVL72 skapjos, ko LLM apmācības darbi neaizņēma. Plānotājs iepako darbus veselos skapjos. Pāri paliek pa mezglam vai diviem, kopā daži procenti no klastera. Lu pieslēdza sijāšanu šim atlikumam ar zemāko prioritāti, jo to var apturēt jebkurā brīdī bez zaudējumiem.
Es izprotu šos komponentus tāpat kā vidēja līmeņa auto entuziasts izprot auto detaļas. Lielu daļu no pamatā esošās matemātikas es nesaprotu. Šajā jomā es nebūt neesmu eksperts.
Pirmajās piecās dienās komanda kāpa pa grūtības kāpnēm. Sākumā 157 ciparu skaitlis prasīja nedaudz vairāk par trim stundām. Piektajā dienā tikpat ilgi prasīja 190 ciparu skaitlis. Pats RSA-260 rēķins sākās 18. augustā plkst. 12:14:19 UTC un beidzās 3. septembrī plkst. 01:48:57 UTC, kopā 1 344 878 sekundes.
Ko tas maina 1024 un 2048 bitu atslēgām
RSA-1024 pēc standarta GNFS mērogošanas prasa 78 reizes vairāk rēķinu nekā RSA-260. Lu to novērtē aptuveni 30 miljonos dolāru pēc tirgus GPU cenām. Viņš piebilst, ka pašreizējā versija joprojām ir tālu no optimālas. Vidēji liels papildu darbs cenu varētu nogriezt vēl uz pusi.
RSA-2048 paliek neskarts. Tas ir aptuveni miljardu reižu grūtāks par RSA-1024, tāpēc šis darbs to neietekmē.
Ka 1024 bitu RSA ir nedrošs, nav jaunums. Jau 2000. gadu vidū apsprieda, vai NSA to nevarētu izdarīt ekonomiski, atsaucoties uz TWIRL un Bernšteina matricu mašīnu. Mainījās trīs lietas. Cena kritās desmitkārt. Rekordu tagad var uzstādīt jebkurš, kam ir pietiekami GPU, jo speciāla aparatūra vairs nav vajadzīga. Sietu paātrināt spēj cilvēks, kas nav kriptogrāfs.
Cik daudz tur bija cilvēka
Projekts ilga trīs nedēļas. Vienlaikus strādāja vidēji trīs Devin sesijas, maksimums astoņpadsmit. Faktorizācijai kopā izmantotas 233 sesijas, no tām 192 saņēma ziņas no Lu. Viņš tām nosūtīja 3328 ziņojumus jeb 82 702 vārdus. Paši Devin aģenti palaida vēl 101 meitas sesiju. Trīsdesmit sešas sesijas nesaņēma no Lu nevienu iejaukšanos.
Lu apraksta savu lomu kā izpildfunkciju: uzstādīt mērķu hierarhiju, pamanīt aplamu darbu un norādīt neizmēģinātus virzienus. Divi viņa piemēri ir “tev nevajag to mērījumu” un “pārliecinies, ka GPU nekad negaida uz CPU”.
Emanuels Tomē no INRIA, viens no 2020. gada RSA-250 rekorda autoriem, pirms apraksta publicēšanas Scientific American aplēsa, ka RSA-260 vajadzētu prasīt apmēram trīs reizes vairāk rēķinu nekā RSA-250. Toreiz RSA-250 sadalīšanai aizgāja ap 2700 procesora kodolgadu.
Komentāri
Šim rakstam vēl nav komentāru. Esi pirmais, kurš dalās ar savu viedokli.