Hacker News Reader

Comment by jeofken | Hacker News Reader

Would someone competent in cryptography please explain this to a “regular” programmer?

RSA is a "public key" cryptography system, where you have a public key that everyone's allowed to know, and a private key that you keep secret. Anyone can use the public key to encrypt messages, but you need the private key to decrypt messages.

(You can also use it for digital signatures, where you provide a copy of the message and also "encrypt" the message with the private key; anyone can publicly decrypt it. If the "decrypted" message matches the original, then the signature proves that the message was signed by someone who has the private key.)

RSA works by starting with two large random prime numbers P and Q. You multiply P and Q to get a number M, and that number becomes part of the public key. An attacker who knows P and Q can compute your private key and decrypt your messages.

RSA assumes that it's computationally infeasible to factor M back into P and Q. It's supposed to be something like O(2^n), where n is the length of M.

A fast factorization algorithm breaks that assumption, allowing attackers to decrypt messages and forge digital signatures.

If Schorr has found an algorithm that does this, I would say it "destroyes the RSA cryptosystem."

(My guess: it probably doesn't work, because drafts of this paper have been out for a few years and the sky hasn't fallen yet.)

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

“No more secrets”

Setec Astronomy

Cocktail party at the reservoir

I'll be there!

P.S. Please don't bring Cooty.

Too many secrets

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.

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

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.

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

Travelling Salesman (2012) movie is about exactly this.

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.

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

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.

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

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.

ECM will easily factor 160-bit numbers https://doc.sagemath.org/html/en/reference/interfaces/sage/i...

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

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

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.

Yes and if it is feasible given current computer architectures or requires significant advances in quantum algorithms/computers?

Reply on news.ycombinator.com