Na-factor ni Claude ang RSA-896. Narito kung paano "nababasag" ang RSA

Ang sakop ng video na ito

• Bumabagsak ang RSA-896: 270 digit, 2,048 GPU, sampung araw
• 1977 → 1994: apatnapung quadrillion taon, anim na raang boluntaryo
• 2009 → 2020: isang rekord bawat dekada, lahat sa CPU
• Sep 2026: Devin, pagkatapos Claude, dalawang rekord sa labing-anim na araw
• Ang sieve: polynomial → sieving → isang 656-milyong-linyang matrix → square root

Isinaling transcript

Isinalin mula sa orihinal na salaysay sa English. Ang available na audio at mga caption ay kinokontrol ng YouTube.

Bumabagsak ang RSA-896: 270 digit, 2,048 GPU, sampung araw

0:00 Noong Sabado, isang inhinyero sa Anthropic ang nag-factor ng RSA walong siyamnapu't anim, isang dalawang daan at pitumpung digit na numero na inilaan para tumagal ng habambuhay, gamit si Claude at dalawang libong idle GPU, na siyang pinakamahal na paraan kailanman natuklasan upang kumpirmahing malamang ay maayos ang iyong SSH key. Tatlong numero. Tatlumpung GPU-years sa loob ng sampung araw. Pitumpu't limang libong dolyar ng premyo para sa eksaktong numerong ito, ibinawi noong dalawang libo't pito. At ang presyo ng paggawa nito sa key sa iyong laptop,

0:24 tatlumpu't pitong quadrillion dolyar. Sa loob ng tatlong minuto, paano itinatatag ang isang factoring record, bakit ang algorithm ay isang tatlumpung taong gulang na sieve at hindi isang chatbot, at alin sa iyong mga susi ang dapat mong alalahanin. Ito ang The Daily Diff, sa ilalim ng hood.

1977 → 1994: apatnapung quadrillion taon, anim na raang boluntaryo

0:38 Labing-siyam na pitumpu't pito. Ipinrint ni Martin Gardner ang isang daan at dalawampu't siyam na digit na numero sa Scientific American, at tinantiya ni Ron Rivest na ang factoring nito ay tumatagal ng apatnapu quadrillion taon. Ito ay tumatagal ng labing-pito, anim na raang boluntaryo at dalawang fax machine, at ang lihim na mensahe ay ang mahiwagang salita ay squeamish ossifrage. Dalawang libo't siyam, RSA pitong daan at animnapu't walo, dalawang libong core-years.

2009 → 2020: isang rekord bawat dekada, lahat sa CPU

0:58 Dalawang libo't dalawampu, RSA dalawang daan at limampu, dalawang libo't pitong daang core-years sa isang open-source sieve na tinatawag na Cado NFS, mula sa isang French lab. Isang rekord sa isang dekada, ang bilis ng mga taong may tenure.

Sep 2026: Devin, pagkatapos Claude, dalawang rekord sa labing-anim na araw

1:10 Pagkatapos Setyembre. Sinabihan ni Eric Lu sa Cognition si Devin, ang kanilang coding agent, na i-port ang sieve sa GPU at natulog. Pagkaraan ng tatlong linggo at apat na raang libong dolyar ng bakanteng oras ng cluster, tapos na ang RSA dalawang daan at animnapu. Labing-anim na araw pagkatapos, inulit ni Steve Weis sa Anthropic ang trick kay Claude. Anim na taon sa pagitan ng mga rekord, pagkatapos ay dalawa sa loob ng dalawang linggo, isa mula sa isang hobbyist na may isang coding agent, isa mula sa isang cryptographer na may bakanteng GPU. Ang mekanismo. Apat na yugto.

Ang sieve: polynomial → sieving → isang 656-milyong-linyang matrix → square root

1:36 Pumili ng isang polynomial. Sieve, na nangangahulugang pangangaso ng bilyun-bilyong numero na may maliliit na factors lamang, bawat kandidato ay independyente, kaya iyon ang bahagi na inilipat sa GPU. Pagkatapos linear algebra, kung saan ang walong bilyong relasyon ay nagiging isang matrix na anim na raan limampu milyong row sa isang gilid, at bawat node ay nakikipag-ugnayan sa bawat isa pang node hanggang mayroong na-preempt. Pagkatapos ay isang square root, na ang run ng Cognition ay umapaw at muling isinulat ng tatlong beses.

Bakit hawak pa rin ang 2048: $30M para sa RSA-1024, $38 quadrillion para sa RSA-2048

1:59 Bakit iba ang iyong dalawang libo't apatnapu't walong bit key. Ang sieve ay subexponential, kaya ang bawat karagdagang bit ay mas mura kaysa sa pagdoble, ngunit ito ay pinagsama-sama. Ang RSA sampung dalawampu't apat ay pitumpu't walong beses ang gawain ng RSA dalawang daan at animnapu, tawagin itong tatlumpung milyong dolyar, pera para sa hyperscaler. Ang RSA dalawang libo't apatnapu't walo ay isang bilyong beses na mas mahirap muli, tatlumpu't pitong quadrillion dolyar, na siyang pagtatantya ni Rivest na ang unit ay binago mula sa taon patungo sa dolyar.

Pahayag vs. pagbasa: 'Sinira ni Claude ang RSA' vs 'walang bagong algorithm'

2:24 Ang pahayag kumpara sa nabasa. Ang headline ay nagsasabing sinira ni Claude ang RSA. Kredito mismo ni Claude ang mga taong gumawa ng sieve sa loob ng mga dekada, at nagdagdag si Weis ng tatlong linya. Walang bagong algorithm, exponential pa rin, na kalaunan ay kinorektahan niya sa subexponential, at walang bagong banta sa mga deployed key. Pareho ay totoo. Hindi gumalaw ang matematika.

2:41 Ang presyo ay gumalaw, dahil ang idle GPU plus isang ahente na nagpo-port ng lumang C sa Cuda magdamag ay ginagawang isang mahabang weekend ang isang dekada-bawat-record na libangan. Sabi ng Hacker News hindi mo kailangan ng AI para dito, kailangan mo lang ng compute. Totoo, hanggang sa may mapansin na pinirmahan pa rin ng Instagram ang email nito gamit ang isang pito daan at animnapu't walong bit key, na ngayon ay isang weekend project. Pinakamahusay na sagot, mula kay Allan Peng. Dalawa ang factor ng RSA walong siyamnapu't anim plus isa.

Lunes: ssh-keygen -l, ang iyong mga mail-signing keys, linya ng NIST sa 2030

3:04 Lunes. Patakbuhin ang ssh keygen dash L sa iyong mga public key, at anumang nagpi-print ng sampu dalawampu't apat ay isang problema noong dalawang libo't labing-tatlo na itinago mo. Hukayin ang iyong mga mail-signing record sa parehong paraan. At basahin ang draft ng Nist, dahil ang RSA dalawang libo't apatnapu't walo ay deprecated pagkatapos ng dalawang libo't tatlumpu pa rin, hindi para sa sieves, para sa qubits na hindi pa umiiral

Verdict, sa ilalim ng hood

3:21 rin. Verdict, sa ilalim ng hood. NEEDS REVIEW. Ang dalawang libo't apatnapu't walong bit ay maayos. Ang pitong daan at animnapu't walong bit sa iyong DNS ay hindi, at hindi na kailangan ng attacker ng lab, kailangan lang ng bakanteng GPU at isang chat window. Sabihin sa akin kung ano ang susunod na bubuksan sa mga komento. At iyon ang diff para sa araw na ito. Ako si Niko mula sa Axrisi. Merge responsibly.

Mga Pinagmulan

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