+− THE DAILY DIFFdev & AI news
NEEDS REVIEW

Claude tegurdas RSA-896. Siin on, kuidas RSA tegelikult murdub

19.

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

19. septembril tegurdas Anthropicu insener RSA-896 — 270-kohalise proovinumbri — Claude'iga, avatud lähtekoodiga CADO-NFS-i sõela GPU-pordiga ja ~30 GPU-aastaga 2048 tühikäigul oleval GPU-l kümne päeva jooksul, kuusteist päeva pärast seda, kui Cognitioni Devin tegi sama RSA-260-ga. Kuidas see tegelikult toimub: kuidas tegurdamise rekord tegelikult püstitatakse (polünoom → sõelumine → 656-miljoni-reaga maatriks → ruutjuur), miks 896 bitti murduvad ja 2048 mitte, ning milliste oma võtmete pärast peaksite muretsema. Otsus: NEEDS REVIEW.

Loe kirjalikku väljaannet (inglise keeles) ↗

Mida see video hõlmab

  • RSA-896 murdub: 270 numbrit, 2048 GPU-d, kümme päeva
  • 1977 → 1994: nelikümmend triljonit aastat, kuussada vabatahtlikku
  • 2009 → 2020: üks rekord kümnendi kohta, kõik CPU-del
  • September 2026: Devin, siis Claude, kaks rekordit kuueteistkümne päeva jooksul
  • Sõel: polünoom → sõelumine → 656-miljoni-reaga maatriks → ruutjuur

Küsimused ja vastused

Kuidas RSA-896 Claude'i abil faktoriseeriti ja kui palju arvutusvõimsust selleks kulus?

19. septembril faktoriseeris Anthropicu insener Stephen Weis Claude'i ja avatud lähtekoodiga CADO-NFS sõela GPU-pordi abil RSA-896, 270-kohalise väljakutsenumbri. Jooksu käigus kasutati umbes 30 GPU-aastat 2048 tühikäigul oleval GPU-l kümne päeva jooksul. See toimus kuusteist päeva pärast seda, kui Cognitioni Devin faktoriseeris RSA-260 samal viisil.

Vaata seda osa 0:00 · saweis.net · x.com · cognition.com

Millised on arvuvälja sõela etapid, mida kasutatakse rekordite faktoriseerimisel?

Sõelal on neli etappi. See valib polünoomi, sõelab numbreid, millel on ainult väikesed tegurid, ehitab väga suure maatriksi ja võtab ruutjuure. Cognitioni RSA-260 jooksu ajal oli maatriksil 656 miljonit rida ja ruutjuure võtmise etapp ületäitus ja kirjutati kolm korda ümber. Sõelumisetapp on osa, mis viidi GPU-dele.

Vaata seda osa 1:35 · cognition.com · cado-nfs.gitlabpages.inria.fr

Miks 896-bitise arvu faktoriseerimine ei sea ohtu 2048-bitiseid RSA-võtmeid?

Sõel on subeksponentsiaalne, nii et iga lisabitt maksab vähem kui kahekordistumine, kuid kulu kumuleerub. Episoodis öeldakse, et RSA-1024 vajab umbes seitsekümmend kaheksa korda rohkem tööd kui RSA-260, ligikaudu kolmkümmend miljonit dollarit, ja RSA-2048 on veel miljard korda raskem. Weis lisas, et tulemus ei too kaasa uut algoritmi ega uut ohtu kasutusel olevatele võtmetele.

Vaata seda osa 1:59 · x.com · cognition.com

Milliseid krüptograafilisi võtmeid peaksid arendajad pärast RSA-896 faktoriseerimise tulemust kontrollima?

Kontrollige kõiki lühikesi RSA-võtmeid. Käsurea ssh-keygen -l käivitamine avalikel võtmetel näitab nende suurust ja 1024-bitine võti on 2013. aasta probleem, mis jäeti alles. Sama kontrolli väärivad ka meili allkirjastamise kirjed, kuna Instagrami DKIM-kirje kasutas endiselt seitsesada kuuskümmend kaheksa bitist võtit. NISTi üleminekuplaani eelnõu, IR 8547, tühistab RSA-2048 pärast 2030. aastat.

Vaata seda osa 3:04 · nvlpubs.nist.gov · dns.google

Kas Claude'i RSA-896 faktoriseerimine tähendab, et meeskonnad peavad oma RSA-võtmed asendama?

The Daily Diff'i otsus oli NEEDS REVIEW. Kakstuhat nelikümmend kaheksa bitti on korras, samas kui seitsesada kuuskümmend kaheksa bitine võti DNS-is ei ole. Matemaatika jäi samaks ja hind langes, sest tühikäigul olevad GPU-d pluss agent, mis teisendab vana C CUDA-ks, muudavad rekordid odavaks. Claude ise tunnustas inimesi, kes ehitasid sõela aastakümnete jooksul.

Vaata seda osa 3:21 · x.com · dns.google

Tõlgitud transkriptsioon

Tõlgitud ingliskeelsest originaaljutustusest. Saadaolevat heli ja subtiitreid kontrollib YouTube.

RSA-896 murdub: 270 numbrit, 2048 GPU-d, kümme päeva

0:00 Laupäeval tegurdas Anthropicu insener RSA kaheksasada üheksakümmend kuus, kakssada seitsekümmend kohaline number, mis oli mõeldud kestma kogu elu, Claude'i ja kahe tuhande tühikäigul oleva GPU-ga, mis on kõige kallim viis üldse leitud kinnitamaks, et teie SSH-võti on tõenäoliselt korras. Kolm numbrit. Kolmkümmend GPU-aastat kümne päeva jooksul. Seitsekümmend viis tuhat dollarit auhinnaraha just selle numbri eest, tagasi võetud kahe tuhande seitsmendal aastal. Ja selle tegemise hind teie sülearvuti võtmele,

0:24 kolmkümmend seitse triljonit dollarit. Kolme minutiga, kuidas tegurdamise rekord püstitatakse, miks algoritm on kolmekümneaastane sõel ja mitte vestlusrobot, ning milliste teie võtmete pärast peaksite muretsema. See on The Daily Diff, kuidas see tegelikult toimub.

1977 → 1994: nelikümmend triljonit aastat, kuussada vabatahtlikku

0:38 Üheksateist seitsekümmend seitse. Martin Gardner prindib Scientific Americanis saja kakskümmend üheksa kohalise numbri, ja Ron Rivest hindab selle tegurdamiseks nelikümmend triljonit aastat. See võtab seitseteist, kuussada vabatahtlikku ja kaks faksi masinat, ja salajane sõnum on maagilised sõnad on squeamish ossifrage. Kaks tuhat üheksa, RSA seitsesada kuuskümmend kaheksa, kaks tuhat tuum-aastat.

2009 → 2020: üks rekord kümnendi kohta, kõik CPU-del

0:58 Kaks tuhat kakskümmend, RSA kakssada viiskümmend, kakstuhat seitse sada tuum-aastat avatud lähtekoodiga sõelal nimega Cado NFS, Prantsuse laborist. Üks rekord kümnendi kohta, ametiaja pikkus inimestega.

September 2026: Devin, siis Claude, kaks rekordit kuueteistkümne päeva jooksul

1:10 Siis september. Eric Lu Cognitionis ütleb Devinile, nende kodeerimisagendile, et portida sõel GPU-dele ja läheb magama. Kolm nädalat ja nelisada tuhat dollarit vaba klastriaega hiljem, RSA kakssada kuuskümmend on valmis. Kuusteist päeva hiljem kordab Steve Weis Anthropicus seda trikki Claude'iga. Kuus aastat rekordite vahel, siis kaks kahe nädala jooksul, üks harrastajalt kodeerimisagendiga, üks krüptograafilt vaba GPU-ga. Mehhanism. Neli etappi.

Sõel: polünoom → sõelumine → 656-miljoni-reaga maatriks → ruutjuur

1:36 Vali polünoom. Sõelu, mis tähendab miljardite numbrite jahtimisel ainult väikeste teguritega, iga kandidaat iseseisev, nii et see on see osa, mis liikus GPU-dele. Siis lineaaralgebra, kus kaheksa miljardit seost muutub maatriksiks kuussada viiskümmend miljonit rida külje kohta, ja iga sõlm räägib iga teise sõlmega, kuni keegi saab eelõiguse. Siis ruutjuur, mille Cognitioni jooks voolas üle ja kirjutati kolm korda ümber.

Miks 2048 endiselt püsib: 30 miljonit dollarit RSA-1024 eest, 38 triljonit dollarit RSA-2048 eest

1:59 Miks teie kahe tuhande neljakümne kaheksa bitine võti on erinev loom. Sõel on subeksponentsiaalne, nii et iga lisabitt maksab vähem kui kahekordistumine, kuid see kuhjub. RSA kümme kakskümmend neli on seitsekümmend kaheksa korda RSA kakssada kuuskümne töö, nimetage seda kolmkümmend miljonit dollarit, tugitooli raha hüperskaalale. RSA kaks tuhat nelikümmend kaheksa on taas miljard korda raskem, kolmkümmend seitse triljonit dollarit, mis on Rivesti hinnang ühikuga muudetud aastatest dollariteks.

Väide vs lugemine: 'Claude murdis RSA' vs 'uut algoritmi pole'

2:24 Väide versus lugemine. Pealkiri ütleb, et Claude murdis RSA. Claude ise tunnustab inimesi, kes ehitasid sõela aastakümnete jooksul, ja Weis lisab kolm rida. Uut algoritmi pole, endiselt eksponentsiaalne, mida ta hiljem parandas subeksponentsiaalseks, ja pole uut ohtu paigaldatud võtmetele. Mõlemad on tõesed. Matemaatika ei liikunud.

2:41 Hind liikus, sest tühikäigul olevad GPU-d pluss agent, mis porteerib vana C Cuda'le üleöö muudab kümnendrekordi hobiks pikaks nädalavahetuseks. Hacker News ütleb, et selleks pole vaja AI-d, vaid arvutusvõimsust. Tõsi, kuni keegi märgib, et Instagram signeerib endiselt oma e-posti seitsme saja kuuskümmend kaheksa bitise võtmega, mis on nüüd nädalavahetuse projekt. Parim vastus Allan Pengilt. Kaks on RSA kaheksasada üheksakümmend kuus pluss ühe tegur.

Esmaspäev: ssh-keygen -l, teie meilisignatuurivõtmed, NIST-i 2030. aasta piir

3:04 Esmaspäev. Käivitage oma avalikel võtmetel ssh keygen dash L ja kõik, mis prindib kümme kakskümmend neli, on kahe tuhande kolmeteistkümnenda aasta probleem, mille te säilitasite. Kaevake oma meili signeerimise kirjed samamoodi välja. Ja lugege Nist'i mustandit, sest RSA kaks tuhat nelikümmend kaheksa on aegunud pärast kahe tuhat kolmekümnendat niikuinii, mitte sõelade, vaid kiobitite jaoks, mida pole veel olemas

Otsus, kuidas see tegelikult toimub

3:21 ka. Otsus, kuidas see tegelikult toimub. NEEDS REVIEW. Kaks tuhat nelikümmend kaheksa bitti on korras. Seitsesada kuuskümmend kaheksa bitti teie DNS-is ei ole, ja ründaja enam ei vaja laborit, ainult vabu GPU-sid ja vestlusakent. Öelge mulle kommentaarides, mida järgmiseks avada. Ja see on tänane The Daily Diff. Olen Niko Axrisist. Liida vastutustundlikult.

Allikad

  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

Seotud videod