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

31–40 of 81 posts

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

#31

Post by k3liutZu »

JoblessWonder wrote: post #23
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…

> Of course, I don't know what I'm talking about. I would honestly have no way of knowing either way. It is always fun to get a peek into people working out ideas in fields I have no experience in.

> It is always fun to get a peek into people working out ideas in fields I have no experience in.

Phew. I'm not alone.

I understood _some_ of the words used in the HN comments in this thread.

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

#32

Post by hinkley »

TacticalCoder wrote: post #12
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…

Way back when dinosaurs roamed the earth and comp.compression on Usenet was a place to be, usually we went beyond the pigeonhole principle by asking people to grab a megabyte from random.org, compress it, and then get back to us.

Nobody ever did.

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

#33

Post by airhead969 »

KMag wrote: post #18
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, bu…

Seems like not a fault of the construction of RSA or anything else that relies on the cost of factoring, but a fault of appropriately anticipating the costs to break it. Useable quantum will also make crypto security more expensive and complicated.

Another thing that often bothers me are claims and emphasis of how fast constructions are. This just makes it easier to brute force.

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

#34

Post by phigcch »

Without experimental data to back it up (e.g. implementation and benchmarks), I'd consider this claim veeeery dubious - regardless of who it came from.

Extraordinary claims need extraordinary evidence, and in this case it would be easy to provide such evidence - by cracking appropriately-sized challenge primes in a transparent way that can be independently verified.

On the other hand, the theoretical approach in the paper is quite complex and hard to follow - even for professional cryptographers.

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

#35

Post by pfortuny »

In the 2020 preprint:

"These new algorithms factor integers N ≈ 2^400 and N ≈ 2^800 using 7x10^10 and 4.3x10^12 arithmetic operations".

He does not specify how many it uses for 2^1024 or 2^2048. This is clearly nonlinear. Assume (nevertheless) that you multiply x100 every 400 binary digits, then for

2^2048, you get

(2048-800) equiv 1200/400 equiv 3, so you would need approx. 10^12*10^6 operations. Assuming you can do 10^6 ops , you need 10^12 seconds (like 30000 years).

BUT those are very very rough assumptions (an "arithmetic op" might probably take more than 1 microsec).

EDIT: sorry, this link is pretty interesting. Factor RSA-260, which only has 862 bits. Should be feasible in about 2 hours. The link: https://crypto.stackexchange.com/questions/88582/does-schnor...

EDIT2: sorry again: Schnorr is 78 years old. I am not gerontophobic (being 50 I am approaching that age) but: Atiyah claimed the Riemann Hypothesis, Hironaka has claimed full resolution of singularities in any characteristic... And I am speaking of Fields medalists.

So: you do really need peer-review for strong arguments.

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

#36

Post by [deleted] »

airhead969 wrote: post #33
KMag wrote: post #18

Earlier quoted context omitted.

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, bu…

Seems like not a fault of the construction of RSA or anything else that relies on the cost of factoring, but a fault of appropriately anticipating the costs to break it. Useable quantum will also make crypto security more expensive and complicated. Another thing that often bothers me are claims and emphasis of how fast constructions are. This just makes it easier to brute force.

[deleted]

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

#37

Post by pfortuny »

klmadfejno wrote: post #27
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...

From the look of it, he hasn't really claimed this yet in public. This link is someone on twitter saying he did in private. I would just wait

It is in the ePrints abstract, which is essentially public.

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

#38

Post by stefan_ »

I take it someone finally put down the smartphone and picked up the telephone? It turns out retired 70+ year old math legends don't frequent Twitter, so of course the chances of the "crypto community" hashing this out through ever increasing frantic Tweets weren't great.

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

#39

Post by KMag »

airhead969 wrote: post #33
KMag wrote: post #18

Earlier quoted context omitted.

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, bu…

Seems like not a fault of the construction of RSA or anything else that relies on the cost of factoring, but a fault of appropriately anticipating the costs to break it. Useable quantum will also make crypto security more expensive and complicated. Another thing that often bothers me are claims and emphasis of how fast constructions are. This just makes it easier to brute force.

> Another thing that often bothers me are claims and emphasis of how fast constructions are. This just makes it easier to brute force.

People generally talk about speed of encryption and decryption. You're complaining about time for bruit-force attacks. In general, there's not a linear relation between the two, and the time for initial TLS session setup matters. If it takes a year to hit amazon.com for the first time, how many people are going to visit amazon.com?

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

#40

Post by [deleted] »

airhead969 wrote: post #33
KMag wrote: post #18

Earlier quoted context omitted.

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, bu…

Seems like not a fault of the construction of RSA or anything else that relies on the cost of factoring, but a fault of appropriately anticipating the costs to break it. Useable quantum will also make crypto security more expensive and complicated. Another thing that often bothers me are claims and emphasis of how fast constructions are. This just makes it easier to brute force.

[deleted]
Post reply on HN