世界首次，上海大学利用量子计算机成功破解 22 位 RSA 加密算法
世界首次，上海大学利用量子计算机成功破解 22 位 RSA 加密算法
上海大学王潮团队在量子计算领域取得重大突破，成功利用D-Wave公司的Advantage量子计算机实现了50比特RSA整数分解。这一成果不仅展示了量子退火算法在密码学问题中的应用潜力，还对现有加密算法构成了实质性威胁。
中国研究人员再次在国际网络安全领域取得了重大突破。上海大学王潮领导团队利用加拿大公司D-Wave开发的Advantage量子计算机和量子退火算法，成功实现了首次50比特RSA整数分解。相关研究成果已经发表于《计算机学报》，并详细阐述了如何利用D-Wave量子计算机破解RSA加密。
RSA加密是一种非对称加密算法，广泛应用于电子商务、金融交易等领域。它的安全性基于大数分解问题的困难性，即在实际计算中，将一个大整数分解为两个质数的乘积是非常困难的。
值得一提的是，D-Wave是世界上第一家量子计算机商业供应商，也是唯一一家同时建造量子退火和基于门的量子计算机的公司，其Advantage量子计算机包含了超过5000个量子比特，正在开发中的Advantage 2拥有超过7000个量子比特。
传统算法在面对复杂问题时，需要不断尝试各种路径，反复“爬山下谷”以寻找最优解。然而，量子退火算法得益于量子隧穿效应，可以使“球体”直接穿越障碍，迅速达到最优解。
据研究人员介绍，他们已经通过D-Wave Advantage系统成功分解了一个22位的RSA整数，展现了量子计算在密码学问题中的应用潜力。通过两类技术路线，研究人员验证了D-Wave量子退火对RSA的现实攻击能力。从目前RSA的实际攻击效果来看，量子退火大幅度超过其他各类量子计算。
2022年郭光灿院士指导的本源量子撰文认为，退火机能够分解的数字比通用机大几十个量级。与一些量子算法比，量子退火没有其他像QAOA等算法会出现的贫瘠高原问题，有相当高的稳定性。量子退火尤其擅长解决组合优化问题和指数级解空间问题。很多密码问题都可以转化为组合优化问题或指数级解空间求解问题并使用量子退火求解，因此量子退火可以推广到其他公钥密码以及对称密码的安全性评估。
研究人员指出：“这是首次有真正的量子计算机对当前多个全规模的SPN（代换-置换网络）结构算法构成实质性威胁。”SPN结构是许多主流加密算法的核心基础。
此外，该研究还不仅仅局限于RSA攻击。研究团队还成功攻破了在高级加密标准（AES）中占重要地位的其他算法，如Present、Rectangle和Gift-64分组密码。
研究人员表示：“我们的研究结果表明，D-Wave量子技术能够高效攻击用于保护全球敏感信息的加密系统。”
本文原文来自IT之家