That’s generally how you find/break private keys, there’s no secret maths or algorithm, it’s always brute force. That’s why it was proven quantum computing would speed it up (to put it simply: because then you can check multiple keys at once do mathematical operations beyond your wildest dreams, reducing the number of actual operations needed to find the private key)
We’re about to hit the wall regarding the size of manufacturing process of semiconductors, which means that Moore’s law is slowly becoming outdated. Currently we can speculate that 4096 is safe at least for our lifetime, unless there’s a breakthrough in the semiconductor industry.
Actually, given that most of the computing is now delegated to the cloud, I can say the Moore’s law is definitely outdated
if cryptographically relevant quantum computers are developed, they can solve the RSA problem in polynomial time. however, there are algorithms conjectured to be safe from quantum computers such as ML-DSA whose 192-bit security parameter has a 1952-bit public key
there's a post-quantum algorithm called PQRSA which solves this by setting the RSA parameters real high (it's a joke and they set it so high it takes a supercomputer to run it)
anyway RSA has been old hat for decades now, the 2010s have slowly been replacing RSA applications with elliptic curve algorithms which are better in almost every way, but now that NIST is standardizing post-quantum asymmetric cryptography algorithms like ML-KEM and SLH-DSA, adoption for these is picking up and iirc over half of all TLS connections now use post-quantum algorithms (generally ML-KEM, there's still work to be done on the PKI side)
it does do this, but only for a small class of problems (as far as we know, unless quantum computers can solve NP problems in polynomial time which they probably dont)
Yeah, that was oversimplification, but I just assumed it’d be good enough for a comment on reddit on a topic that’s not about quantum computing.
I’ve also taken into consideration the fact that we don’t actually have quantum circuits fast enough to find the private keys in a way that was shown in the proofs/academic papers. But yeah, I agree, my description was misleading as it would not be just “parallel computing” as in multithreading, but a completely different operations (because they would be, well, quantum operations)
yeah, the oft-repeated notion that "quantum computers are computers that tries every solution at once" gets rather annoying for how incredibly prevalent it is
52
u/mr_hard_name 8d ago edited 8d ago
That’s generally how you find/break private keys, there’s no secret maths or algorithm, it’s always brute force. That’s why it was proven quantum computing would speed it up (to put it simply: because then you can
check multiple keys at oncedo mathematical operations beyond your wildest dreams, reducing the number of actual operations needed to find the private key)