RSA加密为何可行？关于其依赖大数分解难题的技术疑问

Great question—this is one of those nagging, foundational questions that sits right at the crossroads of cryptography, complexity theory, and real-world engineering. You’re absolutely correct to call out the lack of a formal proof that integer factorization is super-polynomial time, so let’s break down why the field has leaned into RSA despite this gap:

• Decades of practical "hardness" evidence: For over 40 years, the best known factorization algorithms (like the General Number Field Sieve) only scale subexponentially, not polynomially. Even with massive distributed computing networks or specialized hardware, breaking standard 2048-bit RSA keys remains completely infeasible. This real-world track record of resistance is a huge part of the community’s trust—if someone could factor these numbers quickly, we’d likely have seen hints of it by now.

• No proven alternatives that work for real-world use: Right now, cryptographic primitives based on provably super-polynomial problems are few and far between. Many of them are either too slow for everyday applications, require enormous key sizes, or only resist limited types of attackers. RSA, by contrast, is fast, compact, and integrates seamlessly with existing internet infrastructure—making it a pragmatic choice for widespread deployment.

• The community isn’t complacent: The cryptography world has long recognized the risk you’re describing. That’s why post-quantum cryptography (PQC) standards are already being rolled out, relying on problems like lattice learning, hash-based signatures, and code-based cryptography—many of which have stronger complexity-theoretic foundations. RSA is still in use because it’s battle-tested, but the transition to more theoretically sound alternatives is already underway.

• Proving lower bounds is extraordinarily hard: It’s easy to forget how tough it is to formalize computational hardness. We can prove lower bounds for simple problems (like comparison-based sorting needing Ω(n log n) time), but for complex problems like factorization, formal proofs are out of reach with our current mathematical tools. So the field relies on the next best thing: decades of failed attempts to find efficient algorithms, which is strong (if not formal) evidence of hardness.

At the end of the day, RSA is a practical compromise, not a perfect theoretical solution. The community knows it’s not bulletproof, but it’s the most reliable option we’ve had for widespread use, and we’re actively preparing for a future where it might be broken.

内容的提问来源于stack exchange，提问作者Yaron Scherf