51–60 of 81 posts
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
"This destroys the RSA cryptosystem" - Claus Peter Schnorr[0]
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...
Agreed. Typical mathematician mentality People would be more convinced by presenting a factorization of a challenge RSA number
Expecting everybody to have mastery of every specialization that their work touches is toxic and unproductive. I look forward to a team of motivated undergrad number theorists to tear into this and hack up an implementation.
Earlier quoted context omitted.
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.
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.
Earlier quoted context omitted.
>> As far as I know, it's still just a long-standing conjecture that breaking RSA is as difficult as factoring. No, that's not a conjecture. If you factor the modulus you can directly calculate the private key from the public one. Edit: oh maybe you mean that it's possible to break RSA faster without factoring... Its been too long since I looked at that.
> No, that's not a conjecture. If you factor the modulus you can directly calculate the private key from the public one. You have misread my post. The conjecture is that the RSA problem is as difficult as the factoring problem. In other words, it's possible that solving the RSA problem isn't as difficult as the factoring problem (but most people doubt it). A This is the inverse of your statement. Factoring breaking R…
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…
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 whether the message was correct or not.)
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? ;)
Earlier quoted context omitted.
> 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…
> People generally talk about speed of encryption and decryption. You're complaining about time for bruit-force attacks. If it takes me k time to decrypt something where there are N key variations and where I can run p attempts in parallel, the maximum runtime for a brute force attack is k*N/p. Perfectly linear relationship. This is why we want large key spaces, and why algorithms needing offline brute force protecti…
Yes, but large key spaces are really easy to have. The size of the key space doesn't cost you anything when you're encrypting or decrypting, but it costs the earth if you're trying to guess the key.
> and why algorithms needing offline brute force protection like password hashing algorithms artificially increase execution time and resource requirements
Ehhhh... this is more of a function of the fact that the password space is much smaller than it looks. Password cracking attempts generally aren't trying to exhaust the space. Instead, they're trying to guess the password based on the known properties of passwords. You start with common passwords and work your way down to iffy ones. You don't bother guessing rare passwords; there are too many of them.
Rainbow tables exist, but they have sharp length limits, precisely because of the explosion-of-the-key-space phenomenon.
What if it's actually someone else that discovered this and is just publicly posting and acting as Schnorr, in an attempt to prove their point? ;)
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.
I learned a little bit about information theory that day, and my sneakernet bandwidth was saturated for a while afterwards.
I wrote my thesis on post-quantum public key cryptosystems, though I'm not currently a practitioner and haven't been academically active since ~2017 or so. With those provisos in mind, I'll try to give the summary as I see it. As a basic tl;dr I'm skeptical of the paper. Crypto-twitter is lit up about this right now and as far as I can tell, harbors the same skepticism. - For context and background: yes, there are we…
Schnorr's main novel claim here seems to be a speedup in finding the SVP and CVP in some cases (he explicitly acknowledges limitations.) A Proof Of Concept seems like it would be great to test for edge cases, and that's where I think the interesting bits are likely to be. Disclaimer: Not a mathematician or complexity theorist. Just here to learn, and glad to be corrected any time.