Re:“This destroys the RSA cryptosystem”
by pkulak on Tuesday March 02, 2021 @05:48PM
(#26322216)
Yeah, if this really is fast prime factoring, we're all in a lot of trouble.
[ Parent
| on HN ]
If 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.
This 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.”
Re:“This destroys the RSA cryptosystem”
by hardwaregeek on Tuesday March 02, 2021 @06:01PM
(#26322384)
I'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.
Travelling Salesman (2012) movie is about exactly this.
I’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.”
Re:“This destroys the RSA cryptosystem”
by rrobukef on Wednesday March 03, 2021 @06:20AM
(#26327004)
The first thing I'd do is moving Satoshi's coins with a very suspect transaction.
Re:“This destroys the RSA cryptosystem”
by setpatchaddress on Tuesday March 02, 2021 @07:12PM
(#26323074)
The 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.
The American government isn't the only one you have to worry about.
Somebody has been watching a lot of television.
I 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...
I'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"
Why 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.j...
Because 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 ;)
Re:“This destroys the RSA cryptosystem”
by londons_explore on Tuesday March 02, 2021 @06:02PM
(#26322394)
RSA 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!!
According 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
[1] https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/202...
Re:“This destroys the RSA cryptosystem”
by john_alan on Wednesday March 03, 2021 @03:20AM
(#26325962)
Don't confuse brute forcing 2^65 possibilities with factoring a 2^65 bit semi-prime (n in RSA).
I factored a 2^65.4 bit semi-prime using Sagemath on an M1 in milliseconds.
// get two random primes (pretend P, Q)
sage: random_prime(2^34)
12697300267
sage: random_prime(2^33)
3962800609
// make a semi-prime (pretend N)
sage: 12697300267*3962800609
50316869230723462603
// check length of semi-prime (65-bits)
sage: log(50316869230723462603,2).n()
65.4476759618453
// factor it in 18milliseconds.
sage: time factor(50316869230723462603)
CPU times: user 9.78 ms, sys: 9.07 ms, total: 18.8 ms
Wall time: 23.2 ms
This example was 2^65 bit RSA, which is negligible in bit-strength.
Re:“This destroys the RSA cryptosystem”
by photon-torpedo on Wednesday March 03, 2021 @11:31AM
(#26330669)
GNU coreutils `factor` program can do so as well:
bash$ time factor 50316869230723462603
50316869230723462603: 3962800609 12697300267
real 0m0.009s
user 0m0.009s
sys 0m0.000s
Re:“This destroys the RSA cryptosystem”
by SAI_Peregrinus on Tuesday March 02, 2021 @06:41PM
(#26322786)
Bitcoin 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.
Comparing these two sets of O() estimates is a bit dubious. SHA256 uses almost no memory and hashing can effectively be distributed across machines at no cost. All of the current factorization mechanisms build vast sparse matrices and then perform reduction operations. At some threshold point the memory needed exceeds the capacity of a single machine. This means the O() estimates will hit a speed wall as it is necessary to distribute the computation. Single machine size / memory availability is of course a moving target! O() complexity bounds are great, but unless you've got a machine that can perform every one of the operations at a cost multiplier of effectively 1 it is not always possible scale things up or make this sort of algorithm comparison.
Re:“This destroys the RSA cryptosystem”
by SAI_Peregrinus on Tuesday March 02, 2021 @07:38PM
(#26323258)
True! Comparing symmetric speeds for SHA256 to the operations needed in RSA is iffy at best. But for illustrating the point that brute-forcing the keys used in current RSA is a braindead way to attack things that doesn't really matter. It just further enhances the point. Brute force just isn't the attack to use for comparisons.
Re:“This destroys the RSA cryptosystem”
by munchbunny on Tuesday March 02, 2021 @06:14PM
(#26322514)
It'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.
ECM will easily factor 160-bit numbers https://doc.sagemath.org/html/en/reference/interfaces/sage/i...
There'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-Digi...
https://en.wikipedia.org/wiki/Public-key_cryptography#Classi...
Both, but neither for as long a period of time beforehand as you remember.
Aha! Good correction, thank you. I must have been remembering how long the discovery remained classified, not how long it predated the public discovery.
Re:“This destroys the RSA cryptosystem”
by heavyset_go on Wednesday March 03, 2021 @04:54PM
(#26335216)
If we go by the XKeyScore slides from the Snowden leak, then the NSA can crack RSA.
Dunno 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.
Semi-prime factoring. Also we have elliptic curves.
Re:“This destroys the RSA cryptosystem”
by toomuchtodo on Tuesday March 02, 2021 @05:54PM
(#26322281)
“No more secrets”
Re:“This destroys the RSA cryptosystem”
by immigrantsheep on Tuesday March 02, 2021 @05:56PM
(#26322303)
Setec Astronomy
Re:“This destroys the RSA cryptosystem”
by LinuxBender on Tuesday March 02, 2021 @05:58PM
(#26322330)
Cocktail party at the reservoir
I'll be there!
P.S. Please don't bring Cooty.
Re:“This destroys the RSA cryptosystem”
by ballballball on Tuesday March 02, 2021 @06:02PM
(#26322396)
Too many secrets