4 ms·
Yeah, if this really is fast prime factoring, we're all in a lot of trouble.
by pkulak 6y ago
Yeah, if this really is fast prime factoring, we're all in a lot of trouble.
- toomuchtodo 6y ago“No more secrets”
- immigrantsheep 6y agoSetec Astronomy
- LinuxBender 6y agoCocktail party at the reservoir
- trav4225 6y agoI'll be there! P.S. Please don't bring Cooty.
- ballballball 6y agoToo many secrets
- smolder 6y agoIf that's the case it's funny to think... NSA could have sat on this for years. Though that would be a really hard secret to keep.
- xxpor 6y agoI'd always figured they'd have a (useful) quantum computer sitting in the basement of Ft. Meade at some point, and it's existence would be Top Secret with whatever codeword means "if this leaks, or we think it'll leak, we just assassinate you"
- Lammy 6y agoWhy not just put it somewhere far away instead? You could even double up the benefits by picking a cold place to help keep your equipment temps down https://commons.wikimedia.org/wiki/File:Xkeyscore-worldmap.jpg https://commons.wikimedia.org/wiki/File:Xkeyscore-worldmap.j...
- xxpor 6y agoBecause that's not as fun to think about when you drive past the Ft. Meade exit and it's scary signs on the Baltimore-Washington Parkway ;)
- hardwaregeek 6y agoI've held the theory that if anybody found something like fast prime factoring or a P = NP proof, they'd get assassinated pretty quickly. It'd be in basically every government's interest to get the knowledge, then make sure nobody else has it.
- zaik 6y agoSomebody has been watching a lot of television.
- j0ej0ej0e 6y agoI don't think it's too far a leap to suggest that knowledge like that could get you killed. Lets ask some Iranian nuclear scientists to see what they think...
- morty_s 6y agoI’ve had similar thoughts, but walked them back to “oh, they’d probably keep it to themselves or drop it in the NSA’s amnesty box.”
- rrobukef 6y agoThe first thing I'd do is moving Satoshi's coins with a very suspect transaction.
- rasz 6y agoTravelling Salesman (2012) movie is about exactly this.
- setpatchaddress 6y agoThe Trump presidency forever cured me of the last vestiges of the idea that government would be capable of recognizing the importance of something like this and authorizing something like an assassination as a remedy. Which is mostly a good thing, to be clear.
- 6y ago
- londons_explore 6y agoRSA has always been a lot weaker than it seems at first... I mean, people have been moving from 1024 to 2048 bit primes... The biggest number I could conceivably brute force is probably about 2^50. Maybe 2^60 with a big budget, or 2^65 with a team of ASIC designers. The mere fact that 2^1024 is considered risky tells you how far from ideal RSA is!!
- munchbunny 6y agoIt's for various reasons, but one of them is that, from an attacker perspective, you don't have to strictly solve the factorization problem. You just need to be able to crack a tiny fraction of the keys in a reasonable amount of time in order for RSA at that key length to be considered unsafe to use. In that sense the attacker gets the benefit of best-case complexity.
- vbezhenar 6y agoAccording to RSA Factoring Challenge 829 bits were broken recently [0]. The total computation time was roughly 2700 core-years [1]. I would consider 1024 bits risky in the following 10 years. 2048 bits probably won't ever be broken without significant algorithmic breakthrough or quantum computers. [0] https://en.wikipedia.org/wiki/RSA_Factoring_Challenge https://en.wikipedia.org/wiki/RSA_Factoring_Challenge [1] https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/202...
- SAI_Peregrinus 6y agoBitcoin last peaked at a hash rate of 170EH/s[1]. That's about 2^61 double SHA256 hashes per second. There are about 31.6E6 seconds per year. So around 72.5E24 hashes/year, or 2^86. VERY expensive, but 2^80 is well within brute-force range. I'd consider any symmetric system with less than 112 bits of security to be potentially breakable within the next few years. For anything over 50 years, I'd want a 256-bit security level since general purpose quantum computers might be made within that time. But RSA is about a thousand times slower than double-SHA256, yet it still needs such large keys for security. That's because nobody is going to brute-force RSA, there are far better options. Like the General Number Field Sieve. Of course that's still exponential, this paper claims to be polynomial time for the vector-finding portion, not sure about overall. I've only skimmed it, and it's rather dense. [1] https://charts.bitcoin.com/btc/chart/hash-rate#5ma4 https://charts.bitcoin.com/btc/chart/hash-rate#5ma4
- morty_s 6y agoThis reminds me of a story a professor told us in school. We were talking about all this and he explained that it’s an assumption that no fast algorithm exists, he sure couldn’t find one but added maybe the NSA could. He said there was this student in his class that was really bright, top 5. On an exam this student scored a 40 the next highest score was a 50, the top three scores were something like 70-90+. He was the student that scored a 40. He and the 50 are accomplished professors/researchers in their field—the top two scorers work for the NSA—so he says, “maybe the NSA can do it.”
- _dps 6y agoThere's a very amusing epilogue in Steven Levy's "Crypto" [0] about the fact that either RSA or Diffie-Hellman (I've forgotten which) was in fact known to the intelligence services for 10+ years prior to its re-discovery among public researchers. These are people who are very good at keeping secrets. [0] https://www.amazon.com/Crypto-Rebels-Government-Privacy-Digital/dp/0140244328 https://www.amazon.com/Crypto-Rebels-Government-Privacy-Digi...
- schoen 6y agohttps://en.wikipedia.org/wiki/Public-key_cryptography#Classified_discovery https://en.wikipedia.org/wiki/Public-key_cryptography#Classi... Both, but neither for as long a period of time beforehand as you remember.
- _dps 6y agoAha! Good correction, thank you. I must have been remembering how long the discovery remained classified, not how long it predated the public discovery.
- heavyset_go 6y agoIf we go by the XKeyScore slides from the Snowden leak, then the NSA can crack RSA.
- muricula 6y agoDunno we have post quantum algorithms which don't rely on factoring prime numbers like RSA does, but it will be a lot of systems administration type work to make sure that nobody is using RSA keys anymore.
- john_alan 6y agoSemi-prime factoring. Also we have elliptic curves.
- deleted 6y ago[deleted]