【期刊精选】公钥密码的量子攻击研究现状与展望

在现代密码学中，根据密钥的不同特征，主要分为对称密码体制和公钥密码体制。前者在加解密算法中使用相同的密钥，而后者则是使用不同的密钥。公钥密码体制中最著名的三个算法分别是RSA密码体制、ElGamal密码体制以及ECC体制。下面着重介绍RSA和ECC密码体制的加密算法。
RSA加密算法的安全性是基于数学中整数分解问题(Integer Factoring Problem，IFP)的困难性，因而在密钥生成阶段选取的素数越大，该算法越安全。但是RSA的攻击问题是否等价于整数分解问题目前学界还没有定论。当前整数分解最高效的算法——广义数域筛法(General Number Field Sieve，GNFS)的时间复杂度依然是(亚)指数级的，并且人们普遍相信这一问题在经典计算领域没有多项式级别的算法。
ECC算法的安全性是基于椭圆曲线群运算上的离散对数问题(Elliptic Curve Discrete Logarithm Problem，ECDLP)的困难性：已知K，G∈Ep(a，b)且K=[k]G，求k mod ord(G)。该算法相较RSA算法能够使用更短的密钥达到相当的安全性，代价是增加了加密和解密时的计算量，NIST在2016年的分析中指出，256位的ECC和72位RSA所达到的安全级别相同。

Shor算法被提出后引起了人们的广泛关注，此后的时间不断有基于Shor算法的改进方案被提出。改进工作在多个不同的角度同时进行，比如，致力于减少算法所需的逻辑比特数或者物理比特数，使用模拟计算不断提高可分解的比特数或者将Shor算法与高性能算法相结合等。另一处改进是借助了Draper在2000年的一种利用傅里叶变换构造加法模块的技术，从而构造更加节省比特数目的模指数运算模块。然后在2021年，Rossi等人将上述2n+3方法进行了部分优化，并在IBM的量子模拟机运行该方法分解了51和57，并将该方法分解成功的概率与一般Shor算法之间进行了详细的比较。值得注意的是，该方法相比原始Shor算法中针对无法完成分解的对(N，a)提高了一定的成功概率。

本文较详细地分析了量子算法攻击公钥密码的研究现状，重点介绍了Shor以及量子优化算法攻击RSA的发展进程和Shor算法攻击ECDLP的发展进程，旨在帮助研究者们快速地了解国内外的研究方法与最新进展，为后续的工作起到借鉴作用。

未来，密码学与量子计算的结合将会越来越紧密，后续需研究与发展的方向可以关注下面几个方面：

(1)不断优化Shor算法对公钥密码的攻击实现。Shor算法在理论上已威胁到公钥密码体制的安全性，且实验已经验证其正确性。在量子硬件条件受限的情况下，不断优化与改进Shor算法攻击RSA或ECC所需的量子比特数、量子门个数及其他性能指标是未来必然的一项研究工作。

(2)发掘专用型量子计算用于密码部件设计及公钥密码攻击的潜能。量子设计密码是一个新的领域，如何从传统密码的经典线路过渡到量子线路实现，以及实现怎样的密码算法安全指标。结合量子密码设计，在量子环境下，分析公钥密码的攻击实现以及可达到的安全级别。

(3)PQC迁移是必然趋势，且宜早不宜迟。IBM可能在2030年之前实现1 000量子比特的大规模实用量子计算机；加拿大将在2030年规划实现PQC的迁移；美国政府系统的后量子迁移工作将在10年后初步完成，并倡导工业界尽快完成后量子密码迁移。当前，部署后量子密码的迁移工作是未来十年工作的重点，工程量浩大，需要全世界各行各业一起努力，一起面对与解决迁移过程中遇到的各种问题。

(4)拓展量子算法对后量子密码的攻击工作。未来后量子密码面临的挑战主要是针对不同的困难问题分析它们的量子计算安全性。基于编码的后量子密码算法可以经得起多年考验，根本原因是其底层困难问题的归约仍然处于未知状态，因而缺乏针对性的高效算法。对于基于格的后量子密码，其底层安全性是基于确切的数学困难问题，未来是否也有类似Shor算法的量子算法可以高效攻击格密码进而带来底层隐患尚不确定。

综上所述，量子算法对公钥密码的威胁程度主要取决于量子计算硬件的发展，但对公钥密码的量子攻击研究依然需要不断优化与改进以提高其性能效率。未来十年，后量子密码的迁移是大势所趋，需要各行各业协同推进。

 

原文始发于微信公众号（网络安全与数据治理）：【期刊精选】公钥密码的量子攻击研究现状与展望