RSA加密的安全性取决于分解两个大质数乘积的难度。如果您可以有效地分解大数，您就可以破解 RSA。但如果能破解 RSA，你能分解大数吗？
有点。可以想象，有一种方法可以破解 RSA 加密，而无需恢复私钥。但如果您可以恢复私钥，那么您就可以有效地进行分解。也就是说，如果您可以从公钥 ( N , e )（其中N是模数， e是加密密钥）开始，并恢复私钥d ，那么您可以有效地因式分解N 。请参阅[1]中的“事实 1”。
令n = log 2 N 。那么上面提到的算法就可以在O ( n ³) 时间内运行。但最著名的因式分解算法需要超过O (exp(√ n )) 时间。
假设您正在使用具有 3072 位密钥的 RSA。那么n = 3072 且n 3 ≈ 3 × 10 10且 exp(√ n ) ≈ 10 667 。
相关帖子
[1] 丹·博内。对 RSA 密码系统的二十年攻击。可以在这里找到。
RSA 后的 Converse首次出现在John D. Cook身上。
原文： https://www.johndcook.com/blog/2025/01/06/rsa-factoring/