Which will come first? AGI or breaking RSA-1024
I’ll bet breaking RSA-1024 at this rate
RSA-260 Factorized
71–80 of 82 posts
Re: RSA-260 Factorized
#72Re: RSA-260 Factorized
#73Earlier quoted context omitted.
RSA might be fine mathematically but as a production cryptosystem it’s an unmitigated disaster by modern standards. Compared to elliptic curves, it is comically easy to build an RSA implementation which is catastrophically broken. Both the number of and subtlety of footguns in RSA are extreme. Even ignoring that, ECC is far more efficient (in part thanks to smaller key sizes and being able to be done with fixed-width…
Curve25519 exists because it's also easy to build ECC footguns - not checking if an input is a valid curve point comes to mind. ECC is definitely more efficient though. Then again, we're all supposed to switch to post-quantum.
> Then again, we're all supposed to switch to post-quantum.
Depends on what your goal is and if you like more footguns.
Re: RSA-260 Factorized
#74Earlier quoted context omitted.
256-bit ECC on the other hand is frequently performed by 4-wide 64-bit operations with a little extra accounting.
and the more recent (post-quantum) lattice-based stuff can get away with ~16 bit arithmetic (it's vectors of ~512-1024 dimension, but the operations are SIMD-friendly)
Can get all the way down to 4 with a little CRT/RNS if you're trying to go even faster
Re: RSA-260 Factorized
#75Can I decode my DVD collection now?
I don't think DVDs use RSA.
Re: RSA-260 Factorized
#76Earlier quoted context omitted.
So RSA 260 is about 2-3 times harder than RSA 250, which was solved in 2700 core hours in 2020, so it’s probably no algorithmic improvements, just a tweak here and there plus faster hardware.
faster hardware could also mean gpu/asic/etc.
I'm assuming it is still GNFS but GPU backed.
For reference, check this out:
> cuda-sieve is an experimental, standalone CUDA implementation of the lattice-sieving relation-collection pipeline used by the Number Field Sieve. It builds factor bases, sieves both sides of a special-q lattice, performs trial division and GPU cofactorisation, and emits relations for msieve.
Re: RSA-260 Factorized
#77Impressive. I wonder the methodology. Algorithmic improvements? More probably just an implementational optimisation. Last RSA record was due to special q sieving methods if I recall well, some 3k core hours. I hope there’s a theoretical improvement behind the result.
The general public is gradually catching up with NSA it seems...
Re: RSA-260 Factorized
#78Earlier quoted context omitted.
You are right that there are better options and there is no excuse not to choose something better today. But that’s not what GP is arguing! It’s just that: For any given interest level there is no way that expending the resources to attack the RSA key is valuable! You are either willing to expend resources then attacking the owner is far cheaper or not then you are also not investing weeks-to-month of cluster time. A…
You don't know that. We're at the point where the NSA can assuredly break RSA-1024. We know they have sufficient processing power, and it would be silly of them not to have developed that capability. "But they're not going to spend resources breaking my router!" No, not your router specifically. But batch GCD gives sqrt speedup over multiple keys, potentially 10's to 100's of millions of keys at once with off-the-she…
> If you are actually operating a service relying on RSA-1024 security, it is almost certainly pwoned.
If you're running something with code from a large US corporation, or outsourced to contractors, or made in China, or with a web interface, or [3 more pages of stuff] and your main worry is the size of your RSA keys, then I've got a Fortigate security appliance to sell you.
Re: RSA-260 Factorized
#79Earlier quoted context omitted.
I'd say ECDSA is even worse, because almost anything you get even slightly wrong with Schnorr schemes ends up leaking the private key. With RSA OTOH you just use a decent library and something like encode-and-compare for signing and you're done. I'm much more nervous about something using ECDSA than RSA once I've had a look at the code and verified that it's at least somewhat competently written.
(EC)DSA is indeed fiddly enough that you wonder if it was an NSA operation in the first place. EdDSA on the other hand seems ok.
EdDSA is also quite a mess, see e.g. https://hdevalence.ca/blog/2020-10-04-its-25519am/. Almost no two implementations that aren't the same code base can agree on what is and isn't a valid signature. ECDSA isn't nearly as bad, there's only two forms of the same signature possible and implementations seem to generate either of the two at random (this makes for a great subliminal channel to leak the private key if you don't have the source code). With RSA PKCS #1 (but not PSS) there's one and only one form for a signature.
So oddly enough the supposedly really bad insecure terrible etc PKCS #1 RSA is the only one where the signature is totally unambiguous.
Re: RSA-260 Factorized
#80Earlier quoted context omitted.
Because there is nothing not already automated here. RSA will either be cracked because some assumption about prime numbers doesn’t hold or because we throw more and more brute force on it. And if it were the former it wouldn’t be the “next” in line that would be cracked…
You don't have to have RSA be broken in order to get a competitive advantage over other people searching. You just need Claud to find software optimization that got overlooked or something from number theory to come up with better candidates to guess.
True, but if that happened, i think that would be the headline, not RSA-260 was factorized.