Claude memfaktorkan RSA-896. Begini cara RSA sebenarnya dipecahkan
Pada 19 September seorang jurutera Anthropic memfaktorkan RSA-896 — nombor cabaran 270 digit — dengan Claude, port GPU dari penapis CADO-NFS sumber terbuka dan ~30 tahun GPU pada 2,048 GPU terbiar selama sepuluh hari, enam belas hari selepas Devin dari Cognition melakukan perkara yang sama kepada RSA-260.
Pada 19 September seorang jurutera Anthropic memfaktorkan RSA-896 — nombor cabaran 270 digit — dengan Claude, port GPU dari penapis CADO-NFS sumber terbuka dan ~30 tahun GPU pada 2,048 GPU terbiar selama sepuluh hari, enam belas hari selepas Devin dari Cognition melakukan perkara yang sama kepada RSA-260. Di sebalik tabir: bagaimana rekod pemfaktoran sebenarnya ditetapkan (polinomial → penapisan → matriks 656 juta baris → punca kuasa dua), mengapa 896 bit jatuh dan 2048 tidak, dan kunci mana yang perlu anda risaukan. Keputusan: PERLU SEMAKAN.
Baca edisi bertulis (Bahasa Inggeris) ↗
Apa yang diliputi video ini
- RSA-896 jatuh: 270 digit, 2,048 GPU, sepuluh hari
- 1977 → 1994: empat puluh kuadrilion tahun, enam ratus sukarelawan
- 2009 → 2020: satu rekod setiap dekad, semuanya pada CPU
- Sep 2026: Devin, kemudian Claude, dua rekod dalam enam belas hari
- Penapis: polinomial → penapisan → matriks 656 juta baris → punca kuasa dua
Transkrip terjemahan
Diterjemahkan daripada penceritaan asal Bahasa Inggeris. Audio dan kapsyen yang tersedia dikawal oleh YouTube.
RSA-896 jatuh: 270 digit, 2,048 GPU, sepuluh hari
0:00 Pada hari Sabtu seorang jurutera di Anthropic memfaktorkan RSA lapan ratus sembilan puluh enam, nombor dua ratus tujuh puluh digit yang dimaksudkan untuk bertahan seumur hidup, dengan Claude dan dua ribu GPU terbiar, yang merupakan cara paling mahal yang pernah ditemui untuk mengesahkan bahawa kunci SSH anda mungkin baik-baik saja. Tiga nombor. Tiga puluh tahun GPU dalam sepuluh hari. Tujuh puluh lima ribu dolar wang hadiah untuk nombor tepat ini, dikeluarkan pada tahun dua ribu tujuh. Dan harga untuk melakukannya pada kunci di komputer riba anda,
0:24 tiga puluh tujuh kuadrilion dolar. Dalam tiga minit, bagaimana rekod pemfaktoran ditetapkan, mengapa algoritma itu adalah penapis berusia tiga puluh tahun dan bukan chatbot, dan kunci mana yang perlu anda risaukan. Ini adalah The Daily Diff, di sebalik tabir.
1977 → 1994: empat puluh kuadrilion tahun, enam ratus sukarelawan
0:38 Seribu sembilan ratus tujuh puluh tujuh. Martin Gardner mencetak nombor seratus dua puluh sembilan digit dalam Scientific American, dan Ron Rivest menganggarkan pemfaktorannya memerlukan empat puluh kuadrilion tahun. Ia mengambil masa tujuh belas, enam ratus sukarelawan dan dua mesin faks, dan mesej rahsia itu adalah "the magic words are squeamish ossifrage" (kata-kata ajaib adalah "burung unta yang sensitif"). Dua ribu sembilan, RSA tujuh ratus enam puluh lapan, dua ribu tahun teras.
2009 → 2020: satu rekod setiap dekad, semuanya pada CPU
0:58 Dua ribu dua puluh, RSA dua ratus lima puluh, dua ribu tujuh ratus tahun teras pada penapis sumber terbuka yang dipanggil Cado NFS, dari makmal Perancis. Satu rekod sedekad, kadar orang dengan jawatan tetap.
Sep 2026: Devin, kemudian Claude, dua rekod dalam enam belas hari
1:10 Kemudian September. Eric Lu di Cognition memberitahu Devin, ejen pengekodan mereka, untuk memindahkan penapis ke GPU dan pergi tidur. Tiga minggu dan empat ratus ribu dolar masa kluster ganti kemudian, RSA dua ratus enam puluh selesai. Enam belas hari kemudian, Steve Weis di Anthropic mengulangi helah itu dengan Claude. Enam tahun antara rekod, kemudian dua dalam dua minggu, satu dari seorang penggemar dengan ejen pengekodan, satu dari seorang kriptografer dengan GPU ganti. Mekanisme. Empat peringkat.
Penapis: polinomial → penapisan → matriks 656 juta baris → punca kuasa dua
1:36 Pilih polinomial. Menapis, yang bermaksud memburu berbilion-bilion nombor dengan hanya faktor-faktor kecil, setiap calon bebas, jadi itulah bahagian yang berpindah ke GPU. Kemudian algebra linear, di mana lapan bilion hubungan menjadi matriks enam ratus lima puluh juta baris pada satu sisi, dan setiap nod bercakap dengan setiap nod lain sehingga seseorang dipintas. Kemudian punca kuasa dua, yang Cognition telah limpah dan menulis semula tiga kali.
Mengapa 2048 masih bertahan: $30 juta untuk RSA-1024, $38 kuadrilion untuk RSA-2048
1:59 Mengapa kunci dua ribu empat puluh lapan bit anda adalah haiwan yang berbeza. Penapis adalah subeksponen, jadi setiap bit tambahan kurang kos daripada penggandaan, tetapi ia bertambah. RSA sepuluh dua puluh empat adalah tujuh puluh lapan kali kerja RSA dua ratus enam puluh, panggil ia tiga puluh juta dolar, wang sofa untuk hyperscaler. RSA dua ribu empat puluh lapan adalah satu bilion kali lebih sukar lagi, tiga puluh tujuh kuadrilion dolar, yang merupakan anggaran Rivest dengan unit berubah dari tahun ke dolar.
Tuntutan vs bacaan: 'Claude memecahkan RSA' vs 'tiada algoritma baru'
2:24 Tuntutan versus bacaan. Tajuk utama mengatakan Claude memecahkan RSA. Claude sendiri memberikan penghargaan kepada orang yang membina penapis selama beberapa dekad, dan Weis menambah tiga baris. Tiada algoritma baru, masih eksponen, yang kemudian dia betulkan kepada subeksponen, dan tiada ancaman baru kepada kunci yang digunakan. Kedua-duanya adalah benar. Matematik tidak bergerak.
2:41 Harganya bergerak, kerana GPU terbiar ditambah ejen yang memindahkan C lama ke Cuda semalaman mengubah hobi sedekad-per-rekod menjadi hujung minggu yang panjang. Hacker News mengatakan anda tidak memerlukan AI untuk ini, hanya pengkomputeran. Benar, sehingga seseorang menyedari bahawa Instagram masih menandatangani e-melnya dengan kunci tujuh ratus enam puluh lapan bit, yang kini merupakan projek hujung minggu. Balasan terbaik, dari Allan Peng. Dua adalah faktor RSA lapan ratus sembilan puluh enam tambah satu.
Isnin: ssh-keygen -l, kunci penandatanganan mel anda, garisan 2030 NIST
3:04 Isnin. Jalankan ssh keygen dash L pada kunci awam anda, dan apa sahaja yang mencetak sepuluh dua puluh empat adalah masalah dua ribu tiga belas yang anda simpan. Gali rekod penandatanganan mel anda dengan cara yang sama. Dan baca draf Nist, kerana RSA dua ribu empat puluh lapan tidak lagi disokong selepas dua ribu tiga puluh, bukan untuk penapis, untuk qubit yang belum wujud
Keputusan, di sebalik tabir
3:21 lagi. Keputusan, di sebalik tabir. Perlu semakan. Dua ribu empat puluh lapan bit adalah baik. Tujuh ratus enam puluh lapan bit dalam DNS anda tidak, dan penyerang tidak lagi memerlukan makmal, hanya GPU ganti dan tetingkap sembang. Beritahu saya apa yang perlu dibuka seterusnya dalam komen. Dan itulah perbezaan untuk hari ini. Saya Niko dari Axrisi. Gabung dengan bertanggungjawab.
Sumber
- Stephen A. Weis, "RSA-896" (N, p, q)saweis.net
- Weis on X — the run (2,048 GPUs, 30 GPU-years, 10 days)x.com
- 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
- Allan Peng: "2 is a factor of (RSA-896 + 1)"x.com
- Hacker News threadnews.ycombinator.com
- Eric Lu / Cognition, "Factoring RSA-260" (GPU siever, cost ladder, 656M-row matrix, sqrt rewritten 3×)cognition.com
- CADO-NFS (INRIA)cado-nfs.gitlabpages.inria.fr
- RSA numbers (RSA-129 … RSA-2048, prizes): https://en.wikipedia.org/wiki/RSA_numbers · "The Magic Words are Squeamish Ossifrage"en.wikipedia.org
- NIST IR 8547 (initial public draft), transition timelinenvlpubs.nist.gov
- Instagram DKIM recorddns.google
