6 ms·
RSA-260 Factorized
https://lilting.ch/en/articles/rsa-260-factored-how-computed https://lilting.ch/en/articles/rsa-260-factored-how-computed
https://www.scientificamerican.com/article/whats-the-tech-behind-the-record-breaking-rsa-260-crack/ https://www.scientificamerican.com/article/whats-the-tech-be...
https://en.wikipedia.org/wiki/RSA_numbers#RSA-260 https://en.wikipedia.org/wiki/RSA_numbers#RSA-260
- dclavijo 14d agoWhat was the methodology,software, hardware, cpu cores, time taken?
- internet2000 12d ago[flagged]
- bawolff 12d agoSeems unlikely given claude would not really be effective for this type of problem.
- charcircuit 12d agoWhy not? Claude has already shown it can automate mathematics and it can automate programming and running programs (including renting the servers).
- hnaccount_rng 12d agoBecause there is nothing not already automated here. RSA will either be cracked because some assumption about prime numbers doesn’t hold or because we throw more and more brute force on it. And if it were the former it wouldn’t be the “next” in line that would be cracked…
- charcircuit 12d agoYou don't have to have RSA be broken in order to get a competitive advantage over other people searching. You just need Claud to find software optimization that got overlooked or something from number theory to come up with better candidates to guess.
- bawolff 12d agoTrue, but if that happened, i think that would be the headline, not RSA-260 was factorized.
- adastra22 12d agoIt wasn’t. The person that posted the factorization has nothing to do with Anthropic, and has for many years held the leaderboard on GPU-hours applied to factorization and prime search problems. He’s not yet on record as to how this one was done (probably waiting for publication), but there is no reason at all to assume any LLM was involved.
- tyre 12d agoI heard it was a lucky guess
- samyok 14d agoanddd it's already on wikipedia https://en.wikipedia.org/wiki/RSA_numbers#RSA-260 https://en.wikipedia.org/wiki/RSA_numbers#RSA-260
- rho4 12d agoThat list ordering drives me nuts. What's up with 1024?! And how come much larger numbers have already been solved? Based on that information one cannot strictly assume that the current solution required improvements to the strategy or hardware, no?
- rcxdude 12d agoThe ordering is stupid because some of them are named by the number of bits and some of them are named by the number of decimal digits. They are in order of size and this is the largest one so far, despite the confusing names.
- madars 14d ago"4397328654844826923795068102505872571721883526553349659561256924505973939597593482272505698004801207988043088656411102133523080581 divides RSA-260" Background: https://en.wikipedia.org/wiki/RSA_Factoring_Challenge https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
- nk_kolja 14d agoImpressive. I wonder the methodology. Algorithmic improvements? More probably just an implementational optimisation. Last RSA record was due to special q sieving methods if I recall well, some 3k core hours. I hope there’s a theoretical improvement behind the result.
- nk_kolja 13d agoSo RSA 260 is about 2-3 times harder than RSA 250, which was solved in 2700 core hours in 2020, so it’s probably no algorithmic improvements, just a tweak here and there plus faster hardware.
- mswphd 12d agofaster hardware could also mean gpu/asic/etc.
- ni5arga 12d agoI'm assuming it is still GNFS but GPU backed. For reference, check this out: > cuda-sieve is an experimental, standalone CUDA implementation of the lattice-sieving relation-collection pipeline used by the Number Field Sieve. It builds factor bases, sieves both sides of a special-q lattice, performs trial division and GPU cofactorisation, and emits relations for msieve. https://github.com/kyleaskine/cuda-sieve https://github.com/kyleaskine/cuda-sieve
- alexfoo 12d ago2700 core years
- nk_kolja 12d agoOf course years. Typo.
- deleted 12d ago[deleted]
- 12d ago
- ajross 12d agoIt's sort of fun to remember the genuine worry in the community around RSA and the (really, really shocking at the time!) progress in factorization leading up to GNFS techniques. Like, it really looked like everything was going to fall apart. We all rushed to 1024 bit keys, and then to 2048 bit after what felt like a few months. And... maybe even that wouldn't be enough? And actual history ended up being the boring version: it was absolutely enough, factorization is seemingly settled math at this point, no new techniques have been discovered. At the end of the day RSA was just fine and no one really needed to bother with ECC and all of its confusing tutorials. And the ~23 year old 1024 bit key holding my GnuPG box closed is still just fine, cryptographically. (Though the chances of getting hit with a keylogger or other side channel attack over that period are nontrivially high and I suppose I really should rotate it or something).
- deleted 12d ago[deleted]
- layer8 12d agoECC does have the benefit of smaller keys, but yes, RSA seems fine security-wise for the foreseeable future.
- adastra22 12d agoRSA-1024 absolutely is not.
- pseudohadamard 12d agoWhy not? What's the actual threat? Let's say I'm using RSA-1024 on my firewall today. What happens next?
- adastra22 12d agoRSA-1024 is approx 6 bits more security than the RSA-260 challenge, so ~64x more work to factor. That is negligible by cryptographic standards. We don't know yet how much work OP put into factoring the RSA-260 challenge. No doubt it was a lot, but probably done with general purpose GPU hardware. That will continue to get cheaper to mount in the near future, and we ought to assume that nation states have access to RSA factoring hardware that would be multiple orders of magnitude more efficient. It is quite likely that there are at least two actors (US and China) that can break RSA-1024, and they are no doubt working through a priority list of all accessible servers with such weak keys. If your firewall is not broken & now back-doored, it is only because you're not important enough to have gotten to yet. RSA-2048 (or better, RSA-3072) is usually a drop-in replacement. ECC would be even better. There is no reason not to.
- drfuchs 12d agoCan I decode my DVD collection now?
- layer8 12d agoDVD encryption doesn’t use RSA; and yes, you could since late 1999 already.
- charcircuit 12d agoNot in the US due to DMCA as the encryption is a protection measure.
- ni5arga 12d agoI don't think DVDs use RSA.
- frays 12d agoWhich will come first? AGI or breaking RSA-1024
- doubletwoyou 12d agoI’ll bet breaking RSA-1024 at this rate