4 ms·
What does this mean about the size (and thus feasibility) of a circuit required to factor a cryptographically interesting number, say, to be generous, RSA1024?
by AceJohnny2 1y ago
What does this mean about the size (and thus feasibility) of a circuit required to factor a cryptographically interesting number, say, to be generous, RSA1024?
- add-sub-mul-div 1y ago"(Quick aside: the amount of optimization that has gone into this factoring-21 circuit is probably unrepresentative of what would be possible when factoring big numbers. I think a more plausible amount of optimization would produce a circuit with 500x the cost of the factoring-15 circuit… but a 100x overhead is sufficient to make my point. Regardless, special thanks to Noah Shutty for running expensive computer searches to find the conditional-multiplication-by-4-mod-21 subroutine used by this circuit.)"
- Davidzheng 1y agoOff topic, but are cryptographers convinced that on the new gigawatt data centers RSA1024 is infeasible to factor? I gather that the fastest known algorithms are still too slow to factor it in reasonable time. But is consensus that there will not be improvements to these algorithms in near future?
- deleted 1y ago[deleted]
- rwmj 1y agoNumber Field Sieves are still the best method, and the techniques are three or more decades old with only incremental improvements. (Of course there might be an incredible breakthrough tomorrow.)
- tiahura 1y agobest published method
- consp 1y agoAre the bitcoins in the first wallets gone? No? I will assume it's still the best method without any irrefutable evidence.
- capitainenemo 1y agoWell, this discussion is about prime number factorisation, and bitcoins use elliptic curve...
- tripplyons 1y agoBitcoin uses ECDSA to sign transactions, not RSA. In addition, selling information to a government on how to break either system would be more valuable than the amount of bitcoin you would able to sell before exchanges stop accepting deposits or the price crashes.
- close04 1y agoIf a government knows you have such information they’ll take it not buy it. So your best bet would probably be to try to sell as many BTC as possible then give away the solution for free to your/a government.
- deleted 1y ago[deleted]
- echelon 1y ago> If a government knows you have such information they’ll take it not buy it. They would probably kill you so you couldn't tell others. If a government can break crypto, that's worth more than money. Especially if it can remain peerless and undetected.
- aleph_minus_one 1y ago> In addition, selling information to a government on how to break either system would be more valuable Honest question because one can find such claims very often on forums like HN: Does there really exist a "feasible" way how some "lone hacker" could sell such information to some government and become insanely rich? I know that people who apparently have some deep knowledge about how exploit markets work claimed on HN that "if you have to ask how/where to solve your exploit (i.e. you have the respective contacts), you are very likely not able to". This latter observation seems a lot more plausible to me than the claim often found on HN that some "lone individual" would be able to monetize on it if he found a way how to break ECDSA or RSA by selling it to some government.
- ginko 1y agoIt recently occurred to me that now would be the best time ever for state actors to build out massive data centers without anyone noticing.
- tripplyons 1y agoI could reasons for them to build datacenters for AI or collecting encrypted messages to decrypt later, but not for brute force attacks on encrypted messages.
- adgjlsfhk1 1y agothe best time is in a year or two when you just buy the husks when all the ai companies go bankrupt
- tripplyons 1y agoI've seen pretty credible evidence that factoring large semiprime numbers is effectively a solved problem, even without considering quantum computing or gigawatt-scale computing. I'm not able to share specifics, but I would personally not trust RSA.
- close04 1y agoPeople who have seen this evidence don’t go around on the internet bragging they’ve seen this evidence.
- mcswell 1y agoFiction, but interesting nonetheless: the 1992 film "Sneakers", with Robert Redford among others. The MacGuffin is a mathematician who discovers another way to factor large numbers.
- Davidzheng 1y agoThis is wrong btw: a 1GW data center can indeed factor RSA1024 in around a month--I expect state actors to crack it faster in specialized hardware
- Strilanc 1y agoEstimates of the cost of RSA1024 use explicit circuit constructions at the target size, rather than extrapolating from the 4 bit case. So they implicitly account for the discontinuity being pointed out in the post. So this post has no impact on those costs.