量子计算破解密码新突破：信息安全面临大考
量子计算破解密码新突破：信息安全面临大考
清华大学交叉信息研究院陈一镭助理教授在eprint平台上发表了一篇划时代的论文，提出了一种全新的量子算法，可以破解格密码。如果这一突破得到验证，不仅将推动量子计算进入新的时代，还将对现有的密码学、安全等领域产生深远影响。
量子计算对传统密码的威胁
量子计算的出现，尤其是Shor算法的提出，给传统密码体系带来了前所未有的挑战。1994年，麻省理工学院的数学家Peter Shor提出了一种算法，解决了离散对数问题，从而为攻破RSA加密铺平了道路。Shor算法利用量子计算机的并行处理能力，可以快速找到大数的质因数，而这是RSA算法安全性的基础。
目前，RSA是最为广泛采用的一种非对称加密技术，允许信息发送者使用公开密钥进行信息加密，而只有持有相应私钥的接收者才能解密信息。这样的设计确保了即便信息在传输过程中被截获，也无法被未授权的第三方解密。密钥的安全性主要依赖于其长度，即所用密钥的位数。美国国家标准与技术研究院（NIST）推荐的RSA密钥长度为2048位。
然而，这一切在1994年发生了变化，麻省理工学院的数学家Peter Shor提出了一种算法，解决了离散对数问题，从而为攻破RSA加密铺平了道路。离散对数问题本质上是一种计算简单但难以逆向的函数，如因数分解。在量子计算机上应用Shor算法，寻找RSA的因子由此可能变得可行。
瑞士苏黎世IBM研究院的安全研究小组经理Michael Osborne指出：“量子计算机擅长处理的问题类型非常有限。它们并不适合解决所谓的精确问题，因为它们的运行基于概率性。不幸的是，由于Shor算法本质上适合量子计算机处理问题的不同方式，因此得以从量子加速中受益。”
椭圆曲线加密（ECC）是另一种流行的非对称加密技术，基于椭圆曲线数学。ECC在速度和复杂性上都优于RSA，并构成了区块链安全的基础。然而，量子计算机的速度潜力同样可能威胁到ECC的安全性，因为它们的数学基础与Diffie-Hellman密钥交换相似。
另一方面，对称加密使用单一密钥进行加密和解密，其中最著名的例子是美国国家安全局批准的AES。基于哈希值的这些加密方法相对不易受到Shor算法的影响，但可能面临其他类型的攻击。
NIST的后量子密码学项目负责人、数学家Dustin Moody解释道：“总体而言，Shor算法几乎可以破解我们目前使用的所有公钥密码体系，包括RSA、Diffie-Hellman及其椭圆曲线版本。对于AES这样的对称算法以及SHA2和SHA3等哈希函数，我们不必更换算法，因为它们尚未被破解。在最坏的情况下，我们只需要使用稍长的密钥即可。”
去年，纽约大学教授Oded Regev的研究可能进一步加快了Shor算法的执行速度，引发了对现有加密方法安全性的进一步关注。
各国应对措施
面对量子计算带来的安全威胁，各国纷纷采取行动，推动抗量子密码技术的发展和标准化。
美国NIST于2015年启动了抗量子算法的筛选和标准化工作。经过8年的努力，NIST于2024年8月发布了首批3项后量子加密标准，包括ML-KEM（基于模块-晶格的密钥封装机制）、ML-DSA（基于模块网格的数字签名算法）和SLH-DSA（无状态散列数字签名算法）。这些标准旨在保护从机密电子邮件信息到推动现代经济发展的电子商务交易等各种电子信息的安全。
中国在量子科技领域持续领跑，特别是在超导量子和光量子两种物理体系上都实现了“量子优越性”。中电信量子集团作为中国电信全资子公司，致力于构建量子安全基础设施，推进量子密钥分发技术和抗量子密码技术的融合应用。该集团已形成涵盖量子密钥分发、量子密码资源池和量子密码管理平台的建设方案，并在多个城市建成量子城域网。
抗量子密码技术发展现状
抗量子密码主要基于格、哈希和多变量等数学难题，这些难题即便面对量子计算机的挑战，也被认为是难以直接解决的。基于格的密码学以其对量子攻击的强大抵抗力、高效的加密解密过程以及多功能加密原语为优势，但密钥较大且实际实施方面存在挑战。基于代码的密码学则凭借随机线性码译码的复杂性抵御量子攻击，具有良好的数学基础和广泛的应用性，但其密钥长度相比于其他后量子方案较大并且实施效率和实用性仍需进一步考虑。多元多项式密码学基于求解高维多项式系统的难度抵御量子攻击，具有强大的安全基础和高效实施的潜力，但同样面临密钥大小和效率问题并且其数学结构较为复杂。
量子密钥分发（QKD）是另一种重要的量子安全技术，它利用量子力学原理实现安全通信。中电信量子集团技术团队基于QKD，成功打造了抗量子密码体系，形成了量子密码全面解决方案。该方案融合了量子密钥分发技术和抗量子算法技术，以量子密钥为核心，与商密算法相结合，提供量子安全传输、量子身份认证、量子安全存储三大能力，面向IT系统、业务系统、云平台、云上业务系统等多个场景，实现基于量子技术的安全防护。
未来展望
随着量子计算技术的快速发展，信息安全面临着前所未有的挑战。然而，通过持续的科研创新和国际合作，人类正在积极构建抵御量子计算威胁的安全防线。美国NIST的首批后量子加密标准发布，标志着全球密码学界在应对量子计算挑战方面迈出了重要一步。中国在量子科技领域的持续领跑，特别是在超导量子和光量子两种物理体系上都实现了“量子优越性”，为全球量子安全技术的发展注入了新的动力。
然而，这仅仅是开始。量子计算技术的发展仍在快速推进，我们还需要不断研究新的抗量子算法，完善量子密钥分发技术，构建更加安全的密码基础设施。同时，我们也需要加强国际合作，共同应对这一全球性的挑战。只有这样，我们才能在即将到来的量子计算时代，确保信息安全，维护社会稳定和经济发展。