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

2022

 · 

October

公钥密码的量子攻击研究现状与展望

作者简介：

崔 富 鑫：男，硕 士，算 法 工 程 师，主 要 研 究 方 向：量 子 计 算、密 码 分 析。

王 辈：女，博 士，算 法 工 程 师，主 要 研 究 方 向：量 子 计 算、密 码 学。
刘 焱：男，硕 士，算 法 工 程 师，主 要 研 究 方 向：量 子 计 算、密 码 分 析。

01

论文简介

《公钥密码的量子攻击研究现状与展望》一文发表于《网络安全与数据治理》期刊2022年第3期。

近些年，随着量子计算的发展，以Shor算法为首的量子算法展现了对公钥密码体制的严重威胁。研究者们一方面研究量子算法对公钥密码的攻击实现，一方面着手后量子密码算法的过渡迁移。就此议题，首先介绍几类常用的公钥密码算法和相关量子攻击算法。其次，重点介绍Shor算法以及量子优化等算法攻击公钥密码算法的国内外研究现状，特别是对RSA和ECC的攻击实现以及当前存在的困难。最后，结合当前公钥密码量子攻击的研究进展以及后量子密码的发展，对产学研的未来发展规划作出了一些建议与展望。

 2022 · October

02

主要内容

一、背景介绍

在现代密码学中，根据密钥的不同特征，主要分为对称密码体制和公钥密码体制。前者在加解密算法中使用相同的密钥，而后者则是使用不同的密钥。公钥密码体制中最著名的三个算法分别是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算法的量子算法可以高效攻击格密码进而带来底层隐患尚不确定。

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

 2022 ·October

 阅读原文 

 

扫描上方二维码即可获取全文

期刊介绍

2022年7月，国内首本兼备网络安全和数据治理双领域的学术性期刊《网络安全与数据治理》（刊号：CN10-1863/TP）正式创刊出版。该刊由中国电子主管，华北计算机系统工程研究所主办，清华大学-中国电子数据治理工程联合研究院和中国电子数字办协办。该刊聚焦网络空间安全和数据治理前沿领域最新科研动态，密切关注政产学研用各环节在网络强国和数字中国建设过程中跨学科学术成果，坚持技术与应用、产品与研发、产业与市场相结合，服务国家网络空间安全和数据治理工程建设。

《网络安全与数据治理》由中国电子首席科学家、中国工程院院士方滨兴担任主编，中国电子第六研究所所长张尼和清华大学公共管理学院教授、长江学者特聘教授、清华中国电子数据治理工程研究院院长孟庆国担任副主编，数十名院士和知名专家组成专家编辑委员会。该期刊将主动开展理论研究，聚焦学术生态资源，拓展网络安全和数据治理领域基础研究，打造一流学术成果交流展示窗口；充分发挥学界专家力量，组织高水平学术会议，组织出版学术专著；坚持理论与实践相结合，服务国家网络空间安全和数据治理工程建设。

投稿方式请点击下方“阅读原文”。

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