Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”

twitter.com

Post reply on HN
Print view View original

11–20 of 81 posts

Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”

#11

Post by EthanHeilman »

j_walter wrote: post #7
EthanHeilman wrote: post #3

Earlier quoted context omitted.

On one hand I am skeptical about strong claims especially in the early stage of the claim. On the other hand Schnorr is the person claiming it and no one has refuted it yet. I wonder how long until we will know for certain.

The paper seems to be built off of the work of a lot of previous research. It will take some time to prove it, but again if Schnorr is so adamant that this is true he should have no problem with a PoC...even a simple one.

Not sure I would agree that it would be "no problem" to do a PoC. Going from paper to PoC might take a long time. If you are very sure of a result, better to get it out early and let others look at it.

Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”

#12

Post by TacticalCoder »

j_walter wrote: post #2

It doesn't destroy it...at best it weakens the lower RSA bit keys. If it destroys it...why not prove it with a PoC on one of the RSA numbers that hasn't been factored yet. RSA-260 is still open...

Ron Rivest explains himself that once in a while he gets an email from someone saying basically "I broke RSA": not everyday but it's a semi-regular occurrence. And he always nicely answers by asking the person claiming to have broken it to solve a challenge (and it's not even a crazy high number of RSA bit keys he gives).

Theory is nice but if you can find the solution to something, just do it and then brag once it's done : )

Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”

#15

Post by bcaa7f3a8bbc »

If my understanding is correct, Schnorr converts the integer factorization problem to lattice problems: SVP and CVP. Then he claims he had an efficient algorithm to solve this particular instance of SVP and CVP, thus RSA is destroyed. But, the hardness assumption of SVP and CVP in general is the very foundation that another branch of public-key cryptosystems - lattice-based cryptography - is built upon. So, if Schnorr's claims are true (uncertain and still to be determined), I can't stop to think about its impact on lattice cryptosystems: Can we use the same technique to attack them? I think it's a more important question than RSA [0] - lattice cryptosystems are the candidate for Post-Quantum Cryptography, meant to replace all of the existing public-key cryptosystems of today (e.g. RSA and ECC). Even if the attack is purely theoretical, if it can solve other instances of SVP and CVP, it'll certainly affect the security assessment of lattice-based PQC (e.g. NTRU, also LWE).

Of course, I don't know what I'm talking about.

[0] Factorization had a history of speedups, both theoretical and practical. It doesn't really affect the practical security but always comes at a cost of either decreasing confidence or constantly increasing the keysize, so I won't be too surprised if Schnorr really has new insights to speed it up further. In fact, "We need something with a better security record than RSA" was one of the main arguments for transitioning to ECC - which has already completed at large on today's Internet, RSA is only used for digital signature, almost all key exchanges are ECC now. You can't decrypt post-2016 web traffic by breaking RSA.

Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”

#17

Post by marcinzm »

EthanHeilman wrote: post #3
j_walter wrote: post #2

It doesn't destroy it...at best it weakens the lower RSA bit keys. If it destroys it...why not prove it with a PoC on one of the RSA numbers that hasn't been factored yet. RSA-260 is still open...

On one hand I am skeptical about strong claims especially in the early stage of the claim. On the other hand Schnorr is the person claiming it and no one has refuted it yet. I wonder how long until we will know for certain.

Refuting it puts a massive burden on other people since finding the fault in complicated proofs can be very involved. Providing a PoC puts a burden on the person making the claim. So at a minimum not providing a PoC is a very selfish approach.

Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”

#18

Post by KMag »

tyingq wrote: post #4

The two links to the paper...had to navigate twitter a bit to find them: https://eprint.iacr.org/2021/232.pdf (older) https://www.math.uni-frankfurt.de/~dmst/teaching/WS2019/SVP9... (newer) Edit: And the abstract with the "destroyes the RSA..." blurb: https://eprint.iacr.org/2021/232

Quick summary, he's found a faster way to factor numbers. He hasn't found a way to break RSA that isn't equivalent to factoring the modulus.

(As far as I know, it's still just a long-standing conjecture that breaking RSA is as difficult as factoring. RSA always uses odd exponents. The Rabin cryptosystem is similar to RSA except that it always uses 2 as the public exponent and is provably as difficult as factoring, but if the modulus has 2 prime factors p and q, then by the Chinese remainder theorem, the output will always be a quadratic residue modulo p and also a quadratic residue modulo q. In other words, the number of possible plaintexts is 4 times the number of possible ciphertexts, so decryption gives you back 4 possibilities and you need some convention that only one of those was a legal message.)

Unfortunately, this is a faster factoring method, so it also applies to the Rabin cryptosystem, the Blum-Blum-Shub pseudorandom number generator, and Rivest's time lock puzzles (repeated squaring modulo a large composite).

Re: Schnorr confirms paper is his, claims it “destroys RSA cryptosystem”

#19

Post by pbsd »

bcaa7f3a8bbc wrote: post #15

If my understanding is correct, Schnorr converts the integer factorization problem to lattice problems: SVP and CVP. Then he claims he had an efficient algorithm to solve this particular instance of SVP and CVP, thus RSA is destroyed. But, the hardness assumption of SVP and CVP in general is the very foundation that another branch of public-key cryptosystems - lattice-based cryptography - is built upon. So, if Schnor…

Schnorr got close to making such a claim in a previous version of the paper [1, Section 6]. Namely, that NTRU is close to being broken if a sufficiently short vector (it is not specified how short) is found.

The main claim of Schnorr's, as far as I can gather, is that for lattices where the shortest vector(s) are much shorter than the maximum shortest vector(s) for the same dimension, i.e., low-density lattices, those vectors can be found in heuristic polynomial time with his enumeration approach.

Now, low-density lattices are fairly common in cryptographic settings, where the solution, discoverable by finding shortest vectors, is unusually short/close relatively to what one would expect in a random lattice.

As such, if true, I would expect Schnorr's idea to lead to more breaks than just RSA. But I don't personally think it's true. At the same time, I'm not a lattice expert, so make of that what you will.

[1] https://www.math.uni-frankfurt.de/~dmst/research/papers/SVP2...

Post reply on HN