RSA的攻与防（二）
内容提要
本文探讨RSA密码体制中的两种攻击方法：大数分解与维纳攻击。当素数p、q差距过小时，费马分解法可快速破解；差距过大时，波拉德ρ算法能有效分解。维纳攻击利用连分数逼近，在私钥指数d过小时可从公钥(N,e)恢复d，文中给出新上限并验证。防御需确保d足够大。
延伸解读
素数选择需平衡差距
文章指出，RSA模数N的素因子p和q若差距过小，费马分解法可快速破解；若差距过大，波拉德ρ算法也能有效分解。因此，生成密钥时不仅要随机选择大素数，还需检查两者差值，避免极端情况。实际应用中，应设置合理的上下限，确保p和q既不太近也不太远，以抵御这两类攻击。
维纳攻击的适用条件
维纳攻击利用连分数逼近，在私钥指数d过小时可从公钥(N,e)恢复d。文章引用了2019年研究给出的新上限d≤1/√[4]{18}·N^(1/4)，并验证了其正确性。这意味着，当d小于该上限时，RSA系统存在被攻破的风险。因此，选择d时应确保其大于此上限，甚至建议不小于N^(1/2)以更安全。
防御策略与性能权衡
为防止维纳攻击，需保证私钥指数d足够大，但这可能影响解密和签名速度，尤其在资源受限设备上。文章提到实际应用中常结合费马小定理和中国余数定理加速解密，从而在保持安全性的同时提升性能。这提示我们在设计RSA系统时，需在安全与效率之间做出权衡。
Q&A
费马因数分解法适用于什么情况？为什么？
费马因数分解法适用于RSA模数N的两个素因数p和q差距很小的情况。因为当p和q接近时，N可以表示为两个平方数之差，且所需的尝试步数很少，可以快速分解N。
波拉德ρ算法的时间复杂度是多少？它适用于什么情况？
波拉德ρ算法的时间复杂度为O(√p log N)，其中p是N的最小素因数。它适用于最小素因数较小的情况，因为p越小，分解越快。
维纳攻击的基本原理是什么？
维纳攻击利用连分数逼近，当私钥指数d较小时，可以从公钥(N,e)中恢复d。其原理是基于ed ≡ 1 mod φ(N)，通过连分数展开e/N，并检查收敛子来找到k/d，进而计算出φ(N)并分解N。
维纳攻击成立时私钥指数d的上限是多少？
维纳攻击成立时，私钥指数d的上限最初由维纳提出为N^(1/4)，后来博内证明在q<p<2q且e<φ(N)时，d < (1/3)N^(1/4)。2019年伍伦贡大学的研究者进一步将上限扩展为d ≤ (1/√[4]{18})N^(1/4)。
如何防御维纳攻击？
防御维纳攻击的关键是确保私钥指数d足够大，至少大于维纳攻击成立的上限。建议选择d不小于N^(1/2)，以确保安全。
生成RSA素数时，对p和q的大小和差距有什么要求？
生成RSA素数时，p和q必须足够大且差距不能太小或太大。差距太小容易被费马因数分解法破解，差距太大则可能被波拉德ρ算法破解。因此需要设置p和q的下限，并检查它们的差值。
