Earlier quoted context omitted.
So, 616 and 1233 digits, respectively.
Jinx! :-)
lol. Oops. At least glad I didn't screw up the math.
“This destroys the RSA cryptosystem”
81–90 of 152 posts
Re: “This destroys the RSA cryptosystem”
#82Earlier quoted context omitted.
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.”
Re: “This destroys the RSA cryptosystem”
#83The author of this paper is Claus P. Schnorr[1], of Schnorr signature fame. The paper has almost the same title as a 2017 draft paper[2] of his. The “This destroyes the RSA cryptosystem” quote is not in the linked paper abstract. This seems fishy. [1] https://en.wikipedia.org/wiki/Claus_P._Schnorr [2] https://www.math.uni-frankfurt.de/~dmst/research/papers/SVP9...
So are you saying I shouldn't run out and short the RSA stock? :)
I was curious about the submission process for ePrint, it looks like there is supposed to be some vetting, even though it is explicitly not fact checked or peer reviewed. You do get papers from cranks and blockchainers but presumably Schnorr doesn't fall into those categories.
Re: “This destroys the RSA cryptosystem”
#84Would 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.)
Re: “This destroys the RSA cryptosystem”
#85The website is being hugged to death, but archive.org has scraped the PDF: https://web.archive.org/web/20210302215033/https://eprint.ia...
This is a different paper.
The linked one is: received 1 Mar 2021
The PDF is: work in progress 31.10.2019
Re: “This destroys the RSA cryptosystem”
#86Earlier quoted context omitted.
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.
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!!
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.
Re: “This destroys the RSA cryptosystem”
#87Earlier quoted context omitted.
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...
Re: “This destroys the RSA cryptosystem”
#88Earlier quoted context omitted.
> work in progress 31.10.2019 ^ Date on the pdf
Yes, that's what I meant with dated. So the linked paper is a work in progress from half a year ago, but presented today on ePrint and with an abstract that has extra text added. I can not determine if this "discovery" could actually break any practically operating RSA systems. Considering how that is probably true for most people, that could even be the intent here. The claim that this will destroy RSA cryptosystems…
You're supposed to generate your own key pair. Keep the private one and publish the public one.
Re: “This destroys the RSA cryptosystem”
#89Earlier quoted context omitted.
> work in progress 31.10.2019 ^ Date on the pdf
Yes, that's what I meant with dated. So the linked paper is a work in progress from half a year ago, but presented today on ePrint and with an abstract that has extra text added. I can not determine if this "discovery" could actually break any practically operating RSA systems. Considering how that is probably true for most people, that could even be the intent here. The claim that this will destroy RSA cryptosystems…
Why would someone backdoor their own key when they could instead just mirror the data or something?
Yes, the person you are encrypting something towards is responsible for ensuring that encryption is secure. No matter how secure you make the cryptography, the other party could still just leak the key...
Re: “This destroys the RSA cryptosystem”
#90Earlier quoted context omitted.
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.
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!!
ECM will easily factor 160-bit numbers https://doc.sagemath.org/html/en/reference/interfaces/sage/i...