+− THE DAILY DIFFdev & AI news
NEEDS REVIEW

Claude je faktorizovao RSA-896. Evo kako se RSA zapravo "razbija"

Dana 19.

Want to see our stories first on Google? Add us to your preferred sources — it helps us grow.

Dana 19. septembra, inženjer iz Anthropic-a je faktorizovao RSA-896 — izazovni broj od 270 cifara — koristeći Claude, GPU port otvorenog koda CADO-NFS sita i ~30 GPU-godina na 2.048 neaktivnih GPU-a tokom deset dana, šesnaest dana nakon što je Devin iz Cognition-a uradio isto sa RSA-260. Ispod haube: kako se zapravo postavlja rekord u faktorisanju (polinom → rešetanje → matrica od 656 miliona redova → kvadratni koren), zašto 896 bita "pada", a 2048 ne, i koji od vaših ključeva bi trebalo da vas brine. Presuda: POTREBNO PREGLEDATI.

Pročitajte pisano izdanje (engleski) ↗

Šta ovaj video pokriva

  • RSA-896 "pada": 270 cifara, 2.048 GPU-a, deset dana
  • 1977 → 1994: četrdeset kvadriliona godina, šest stotina dobrovoljaca
  • 2009 → 2020: jedan rekord po deceniji, sve na CPU-ima
  • Septembar 2026: Devin, zatim Claude, dva rekorda za šesnaest dana
  • Sito: polinom → rešetanje → matrica od 656 miliona redova → kvadratni koren

Pitanja i odgovori

Kako je RSA-896 faktorizovan sa Claude-om, i koliko je računarske snage bilo potrebno?

Dana 19. septembra, inženjer iz Anthropic-a, Stephen Weis, faktorizovao je RSA-896, izazovni broj od 270 cifara, koristeći Claude i GPU port otvorenog koda CADO-NFS sita. Izvođenje je koristilo oko 30 GPU-godina na 2.048 neaktivnih GPU-a tokom deset dana. To je usledilo šesnaest dana nakon što je Devin iz Cognition-a faktorizovao RSA-260 na isti način.

Pogledajte ovaj deo 0:00 · saweis.net · x.com · cognition.com

Koje su faze metode brojnog polja (number field sieve) koja se koristi za rekordno faktorisanje?

Sito ima četiri faze. Bira polinom, prosejava brojeve sa samo malim faktorima, gradi veoma veliku matricu i izvlači kvadratni koren. U Cognition-ovom izvođenju RSA-260, matrica je imala 656 miliona redova, a korak kvadratnog korena je prelivao i bio prepisivan tri puta. Faza prosejavanja je deo koji je prebačen na GPU-e.

Pogledajte ovaj deo 1:35 · cognition.com · cado-nfs.gitlabpages.inria.fr

Zašto faktorisanje 896-bitnog broja ne ugrožava 2048-bitne RSA ključeve?

Sito je subeksponencijalno, tako da svaki dodatni bit košta manje od udvostručavanja, ali se troškovi kumuliraju. Epizoda kaže da RSA-1024 zahteva oko sedamdeset osam puta više posla od RSA-260, otprilike trideset miliona dolara, a RSA-2048 je ponovo milijardu puta teži. Weis je dodao da rezultat ne donosi novi algoritam i nema nove pretnje za postavljene ključeve.

Pogledajte ovaj deo 1:59 · x.com · cognition.com

Koje kriptografske ključeve bi programeri trebalo da provere nakon rezultata faktorisanja RSA-896?

Proverite sve kratke RSA ključeve. Pokretanje ssh-keygen -l na javnim ključevima prikazuje njihovu veličinu, a 1024-bitni ključ je problem iz 2013. koji je zadržan. Zapisi o potpisivanju pošte zaslužuju istu proveru, jer Instagram-ov DKIM zapis je i dalje koristio ključ od sedam stotina šezdeset osam bita. NIST-ov nacrt plana tranzicije, IR 8547, zastareva RSA-2048 posle 2030.

Pogledajte ovaj deo 3:04 · nvlpubs.nist.gov · dns.google

Da li to što je Claude faktorizovao RSA-896 znači da timovi moraju da zamene svoje RSA ključeve?

Presuda The Daily Diff-a je bila POTREBNO PREGLEDATI. Dve hiljade četrdeset osam bita je u redu, dok ključ od sedam stotina šezdeset osam bita u DNS-u nije. Matematika je ostala ista, a cena je pala, jer neaktivni GPU-i plus agent koji prebacuje stari C u CUDA čine rekorde jeftinim. Sam Claude je priznao zasluge ljudima koji su sito gradili decenijama.

Pogledajte ovaj deo 3:21 · x.com · dns.google

Preveden transkript

Prevedeno sa originalne engleske naracije. Dostupan audio i titlovi kontrolisani su od strane YouTube-a.

RSA-896 "pada": 270 cifara, 2.048 GPU-a, deset dana

0:00 U subotu je inženjer u Anthropic-u faktorizovao RSA osam devedeset šest, broj od dve stotine sedamdeset cifara namenjen da traje doživotno, sa Claude-om i dve hiljade neaktivnih GPU-a, što je najskuplji način ikada pronađen da se potvrdi da je vaš SSH ključ verovatno u redu. Tri broja. Trideset GPU-godina za deset dana. Sedamdeset pet hiljada dolara nagradnog novca za ovaj tačan broj, povučeno dve hiljade sedme. I cena da se to uradi sa ključem na vašem laptopu,

0:24 trideset sedam kvadriliona dolara. Za tri minuta, kako se postavlja rekord u faktorisanju, zašto je algoritam trideset godina staro sito, a ne chatbot, i koji od vaših ključeva bi trebalo da vas brine. Ovo je The Daily Diff, ispod haube.

1977 → 1994: četrdeset kvadriliona godina, šest stotina dobrovoljaca

0:38 Devetnaest sedamdeset sedma. Martin Gardner štampa broj od sto dvadeset devet cifara u Scientific American, a Ron Rivest procenjuje da faktorisanje traje četrdeset kvadriliona godina. Trebalo je sedamnaest, šest stotina dobrovoljaca i dva faksa, a tajna poruka su magične reči 'squeamish ossifrage'. Dve hiljade deveta, RSA sedam šezdeset osam, dve hiljade jezgro-godina.

2009 → 2020: jedan rekord po deceniji, sve na CPU-ima

0:58 Dve hiljade dvadeseta, RSA dvesta pedeset, dve hiljade sedamsto jezgro-godina na situ otvorenog koda zvanom Cado NFS, iz francuske laboratorije. Jedan rekord po deceniji, tempo ljudi sa stalnim zaposlenjem.

Septembar 2026: Devin, zatim Claude, dva rekorda za šesnaest dana

1:10 Zatim septembar. Eric Lu iz Cognition-a kaže Devinu, njihovom agentu za kodiranje, da portuje sito na GPU-e i odlazi na spavanje. Tri nedelje i četiri stotine hiljada dolara slobodnog vremena klastera kasnije, RSA dvesta šezdeset je gotov. Šesnaest dana kasnije, Steve Weis iz Anthropic-a ponavlja trik sa Claude-om. Šest godina između rekorda, zatim dva za dve nedelje, jedan od hobiste sa agentom za kodiranje, jedan od kriptografa sa slobodnim GPU-ima. Mehanizam. Četiri faze.

Sito: polinom → rešetanje → matrica od 656 miliona redova → kvadratni koren

1:36 Izaberite polinom. Rešetanje, što znači lov na milijarde brojeva sa samo malim faktorima, svaki kandidat nezavisan, tako da je to deo koji je prebačen na GPU-e. Zatim linearna algebra, gde osam milijardi relacija postaje matrica od šest stotina pedeset miliona redova sa strane, i svaki čvor razgovara sa svakim drugim čvorom dok neko ne bude prekinut. Zatim kvadratni koren, koji je Cognition-ov program prelivao i prepisivao tri puta.

Zašto 2048 i dalje "drži": 30 miliona dolara za RSA-1024, 38 kvadriliona dolara za RSA-2048

1:59 Zašto je vaš dvadeset četrdeset osmobitni ključ drugačija životinja. Sito je subeksponencijalno, tako da svaki dodatni bit košta manje od udvostručavanja, ali se kumulira. RSA deset dvadeset četiri je sedamdeset osam puta veći posao od RSA dvesta šezdeset, nazovite to trideset miliona dolara, novac za sofu za hiperskalera. RSA dve hiljade četrdeset osam je ponovo milijardu puta teži, trideset sedam kvadriliona dolara, što je Rivestova procena sa jedinicom promenjenom iz godina u dolare.

Tvrdnja naspram čitanja: 'Claude je razbio RSA' naspram 'nema novog algoritma'

2:24 Tvrdnja naspram čitanja. Naslov kaže Claude je razbio RSA. Sam Claude priznaje zasluge ljudima koji su sito gradili decenijama, a Weis dodaje tri reda. Nema novog algoritma, još uvek eksponencijalnog, što je kasnije ispravio na subeksponencijalni, i nema nove pretnje za postavljene ključeve. Oboje je tačno. Matematika se nije pomerila.

2:41 Cena jeste, jer neaktivni GPU-i plus agent koji prebacuje stari C u Cudu preko noći pretvara hobi od decenije po rekordu u dugačak vikend. Hacker News kaže da vam za ovo ne treba AI, samo računanje. Tačno, dok neko ne primeti da Instagram i dalje potpisuje svoju e-poštu sa sedam stotina šezdeset osmobitnim ključem, što je sada vikend projekat. Najbolji odgovor, od Allana Penga. Dva je faktor RSA osam devedeset šest plus jedan.

Ponedeljak: ssh-keygen -l, vaši ključevi za potpisivanje pošte, NIST-ova linija 2030.

3:04 Ponedeljak. Pokrenite ssh keygen dash L na svojim javnim ključevima, i sve što štampa deset dvadeset četiri je problem iz 2013. koji ste zadržali. Pretražite svoje zapise o potpisivanju pošte na isti način. I pročitajte Nist nacrt, jer je RSA dve hiljade četrdeset osam zastareo posle 2030. godine, ne zbog sita, već zbog kvantnih bitova koji još uvek ne postoje.

Presuda, ispod haube

3:21 Presuda, ispod haube. POTREBNO PREGLEDATI. Dve hiljade četrdeset osam bita je u redu. Sedam stotina šezdeset osam bita u vašem DNS-u nije, a napadaču više nije potrebna laboratorija, samo slobodni GPU-i i prozor za čet. Recite mi šta da sledeće otvorim u komentarima. I to je razlika za danas. Ja sam Niko iz Axrisi-ja. Spojite odgovorno.

Izvori

  1. Stephen A. Weis, "RSA-896" (N, p, q)saweis.net
  2. Weis on X — the run (2,048 GPUs, 30 GPU-years, 10 days)x.com
  3. Weis on X — Claude's statement: https://x.com/sweis/status/2101492820028895607 · the three clarifications: https://x.com/sweis/status/2101494688528400792 · "GNFS is subexponential"x.com
  4. Allan Peng: "2 is a factor of (RSA-896 + 1)"x.com
  5. Hacker News threadnews.ycombinator.com
  6. Eric Lu / Cognition, "Factoring RSA-260" (GPU siever, cost ladder, 656M-row matrix, sqrt rewritten 3×)cognition.com
  7. CADO-NFS (INRIA)cado-nfs.gitlabpages.inria.fr
  8. RSA numbers (RSA-129 … RSA-2048, prizes): https://en.wikipedia.org/wiki/RSA_numbers · "The Magic Words are Squeamish Ossifrage"en.wikipedia.org
  9. NIST IR 8547 (initial public draft), transition timelinenvlpubs.nist.gov
  10. Instagram DKIM recorddns.google

Niko from Axrisi

Nikoloz Turazashvili · Vexrail · Axrisi

LinkedIn · dev.to · GitHub · X · Substack

Povezani video snimci