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

71–80 of 81 posts

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

#71

Post by nine_k »

waterhouse wrote: post #64
fallingknife wrote: post #63

Earlier quoted context omitted.

I'm getting 1e9 multiplication (2.5e8 div) ops per second in Node on a 2018 Macbook pro. So that would be 30 - 120 years. Not sure how well this algorithm can be parallelized, but since it's factoring, I think it can. So I would think that a dedicated attacker could get at least another 1000x on that, which gives 11-44 days. Note that I am pretty much guessing here but this is my test code: function test(opp, n) { co…

Guess: The "multiplications" we're talking about are those of 400-bit or 800-bit numbers (and, in general, would be the size of the number you're trying to factor), which are much more expensive than 64-bit x 64-bit or float x float multiplications. If you want to test the cost of that, I recommend GMPlib's bignums (or possibly just your favorite language that has built-in bignum support, although if it's not built o…

If one takes a good FPGA and implements a 4096 bit multiplier in it, would it be faster?

Or, if we take a GPU, can we split a 4096 bit number into, say, 32-bit fragments, mass-multiply them, and combine the results faster than on a CPU? I suspect pretty common hardware can help speed such things up a lot; isn't crypto mining already using some of these approaches?

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

#72

Post by waterhouse »

nine_k wrote: post #71
waterhouse wrote: post #64

Earlier quoted context omitted.

Guess: The "multiplications" we're talking about are those of 400-bit or 800-bit numbers (and, in general, would be the size of the number you're trying to factor), which are much more expensive than 64-bit x 64-bit or float x float multiplications. If you want to test the cost of that, I recommend GMPlib's bignums (or possibly just your favorite language that has built-in bignum support, although if it's not built o…

If one takes a good FPGA and implements a 4096 bit multiplier in it, would it be faster? Or, if we take a GPU, can we split a 4096 bit number into, say, 32-bit fragments, mass-multiply them, and combine the results faster than on a CPU? I suspect pretty common hardware can help speed such things up a lot; isn't crypto mining already using some of these approaches?

That I don't know. It's probably first worth looking at what software can do: https://en.wikipedia.org/wiki/Multiplication_algorithm#Karat...

Naive multiplication is O(n^2) (where n = number of digits). The fastest algorithms seem to involve either cutting the numbers into pieces and doing multiplies, adds, shifts, and maybe subtracts on the pieces, and doing so recursively, which are O(n^[something slightly greater than 1]); or doing Fourier transforms, which apparently approach O(n log n). I don't know how easy it is to implement pieces of these more advanced approaches in hardware (especially if the size of the numbers isn't pre-chosen).

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

#73

Post by klmadfejno »

EthanHeilman wrote: post #51
klmadfejno wrote: post #27

Earlier quoted context omitted.

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

He claimed it in the paper he posted on eprint. "This destroys the RSA cryptosystem" - Claus Peter Schnorr[0] [0]: https://eprint.iacr.org/2021/232.pdf

But is this a final released copy?

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

#74

Post by fogof »

capitol_ wrote: post #53
hinkley wrote: post #32

Earlier quoted context omitted.

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.

I remember one of those exchanges, two people waged money about compressing random data so that the data + decompress program would be smaller than the original data. The other guy came back with a program that moved some of the random data into the metadata of the filesystem, in such a way so that the produced files did indeed become small enough. Don't know if the other guy ever paid out.

He did not,

full story, for the perspective of the metadata guy is here

https://www.patrickcraig.co.uk/other/compression.htm

Excellent computer story, on a par with "We can't send email more than 500 miles" IMO.

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

#75

Post by plankers »

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…

Isn't this a bit disingenuous though? If somebody had designed an algorithm capable of breaking RSA given supercomputer-level resources, that's still breaking RSA even if they may not be able to provide ironclad proof.

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

#76

Post by silly-silly »

GordonS wrote: post #50
cperciva wrote: post #29

Earlier quoted context omitted.

If Frederic Jacobs says he communicated with Schnorr, he thinks he communicated with Schnorr. It's possible that someone is impersonating Schnorr.

If only there was some kind of way of proving who you were... possibly using public key cryptography? ;)

This only works for alice and bob.

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

#77

Post by KMag »

thaumasiotes wrote: post #55
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…

> 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. This condition is satisfied by ~100% of all communications, including stuff like software downloads. (If I send you a file, then yes, any message is legal , but as soon as you try to do anything with it, you'll know whe…

More importantly, Rabin would be used in a hybrid cryptosystem, including message authentication codes, so you could calculate MACs using all 4 possible keys. Though, it would be much lower overhead and safer to use OAEP[0] to encode the symmetric cipher/MAC key(s) and then encrypt with Rabin. There's very low probability that more than one of the 4 possible plaintexts has all zeroes for padding after OAEP decoding.

[0] https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_...

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

#79

Post by [deleted] »

richardfey wrote: post #61
klyrs wrote: post #52

Earlier quoted context omitted.

As a computational mathematician, I must object. The world is large enough for multiple deep specializations. I can't think at this level of abstraction (hence, I quit number theory after bashing at it for a few years). I can, however, read a math paper and put together an implementation as long as I'm familiar with the notation and the axiom of choice hasn't been used in a nontrivial matter. But then, my implementat…

Count me in!

[deleted]

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

#80

Post by airhead969 »

KMag wrote: post #39
airhead969 wrote: post #33

Earlier quoted context omitted.

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…

Strawman. There's always a legitimate user cost to attacker cost ratio, and also scaling the bike lock cost and durability to the cost of the bike.
Post reply on HN