Hacker News Reader

Comment by pkulak | Hacker News Reader

Yeah, if this really is fast prime factoring, we're all in a lot of trouble.

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.”

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.”

The first thing I'd do is moving Satoshi's coins with a very suspect transaction.

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 ;)

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...

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

2^1024 bit RSA is about 2^80 in bit strength.

This example was 2^65 bit RSA, which is negligible in bit-strength.

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

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.

[1] https://charts.bitcoin.com/btc/chart/hash-rate#5ma4

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.

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.

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.

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.

“No more secrets”

Setec Astronomy

Cocktail party at the reservoir

I'll be there!

P.S. Please don't bring Cooty.

Too many secrets

Reply on news.ycombinator.com