国内学者提出新算法可破解RSA-2048，引发外国学者争议

中国研究人员提出新算法可利用量子计算机破解RSA-2048，外国研究人员对此结果质疑。

2022年12月，数学工程与先进计算国家重点实验室、清华大学、浙江大学、北京量子信息科学研究院等国内知名机构研究人员在arxiv平台上传了一篇题为Factoring integers with sublinear resources on a superconducting quantum processor的论文。论文指出，Shor算法对基于公钥的加密系统带来挑战。为破解广泛使用的RSA-2048方案，需要数百万量子比特，这超出了当前的技术能力。论文中提出一种通用的量子整数分解算法，该算法融合了经典的格规约(Lattice Reduction)和QAOA（quantum approximate optimization algorithm，量子近似优化算法）。该方法所需的量子比特位O(logN/loglogN)，是截止目前最节省量子比特的分解算法。在实验中，研究人员用10个超导量子比特可以分解48位整数。据估算，只需要372个量子比特的计算机使用该算法就可以破解RSA-2048算法。

而2022年11月，IBM就实现了433量子比特的量子计算机。因此，使用该算法加上IBM的量子计算机就可以破解RSA-2048算法。

随后，国外多名学者对该论文提出了质疑。美国密码学专家布鲁斯·施奈尔 （Bruce Schneier）认为论文提出的算法是依赖于Peter Schnorr论文中提出的算法，而该论文仍存在争议。此外，论文中只在10量子比特的量子计算机上对48位数字就行了分解。这与372量子比特和2048位数存在很大差距。

论文下载地址：https://arxiv.org/pdf/2212.12372.pdf

https://www.scmagazine.com/brief/emerging-technology/chinese-researchers-report-breakthrough-in-quantum-computing

参考及来源：https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html