Shor量子计算对公钥密码的攻击分析

尹宝，王克达，王啸，王潮

Shor量子计算对公钥密码的攻击分析

尹宝，王克达，王啸，王潮

当前电子政务和电子商务CA中心采用的公钥密码主要是RSA和ECC，其安全基础分别是大数分解和椭圆曲线离散对数的数学难题。1994年，Peter W.Shor提出了Shor算法，指出Shor算法可以用于在多项式时间内求解大数质因子和离散对数数学难题，开启了Shor量子计算对公钥密码的攻击研究。在参阅大量国内外相关研究文献后，对目前Shor量子计算对公钥密码攻击的研究概况和量子计算机物理硬件上的实现做了综述性分析。

公钥密码；Shor算法；RSA算法；ECC算法；攻击

0 引言

Diffie和Hellman于1976年首次提出公钥密码学（public key cryptography简称PKC）的概念。这一新的思想，引起了密码学历史上的一次巨大的历史变革，开创了密码学和信息安全发展的新纪元。相对于以前的DES、AES等对称加密算法，公钥密码算法也被称为非对称加密算法。公钥密码学能够很好的解决经典对称密码体制所固有的密钥管理困难及不能进行数字签名等问题，而且公钥密码方便密钥的管理，这不仅使得对称密码体制的使用变得方便和可靠，而且使密码学在网络和信息安全中发挥的作用更加广泛和突出。目前，公钥密码理论与技术的发展正在为各种各样的信息系统的安全性发挥着不可或缺的保障作用。至今，公钥算法的发展已经经历了20多年，也出现了很多种类的公钥密码算法。

1 有代表性的公钥密码算法

目前有3种公钥密码具有代表性：

（1）基于大整数分解难题（IFP）的算法体制；

（2）基于离散对数难题（DLP）的算法体制；

（3）基于椭圆曲线离散对数难题（ECDLP）的算法体制。

应用比较广泛的是第一种和第三种密码体制对应下的密码算法：RSA和 ECC公钥密码算法。对于 IFP 问题和ECDLP问题，在数论上被认为是难解的NP问题即在现有的经典计算机上暂时还不能找到有效的多项式算法来成功求解的。这种数学上的难解特性使得RSA和ECC加密算法具有很高的安全性。

RSA加密体制是由麻省理工大学的Rivest、Shamir和Adleman在1978年提出的，椭圆曲线密码体制是Miller和Koblitz于1985首次提出的。这两种加密算法在非对称加密体制中占有重要地位，不仅能用来加密数据，还能用来进行数字签名。RSA加密算法主要应用在网上交易加密连接、网上银行身份验证、各种信用卡的数字证书、智能移动电话和存储卡的验证的功能芯片等商业方面。ECC的应用目前还没有统一的标准，且成本相对更高，使其应用不像 RSA那样广泛。但是由于其单位比特比RSA更高的安全性，在国家战略层面上更受亲睐，如其在二代身份证上的加密和数字签名应用。

随着计算机技术和量子力学的结合发展，一种全新的计算机概念被提出：量子计算机。量子计算机（quantum computer，简称QC），是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。当某个装置处理和计算的是量子信息，运行的是量子算法时，它就是量子计算。虽然现在还没有一台真正意义上的通用量子计算机，但是已经有了量子计算：在经典计算机上运行量子算法。这种量子计算使得传统计算机有了更高的运算效率，也使得当运行某种量子算法时，可以让传统计算机解决某些数学难题的不可能成为了可能。

1994年，美国AT&T公司的Shor提出了可在多项式时间内完成分解大整数质因子的量子算法，称其为Shor算法。在1997年的时候，Shor又对这种量子算法做了进一步详细的解释和阐述。基于Shor算法的思想，Shor算法被用来求解大数 N的两个质因子问题和求解椭圆曲线离散对数问题的研究开始出现。

这样，Shor算法的提出就使得正被广泛应用的RSA和ECC加密算法的安全性受到了极大的挑战。这一挑战也直接关系到我国使用公钥密码的电子商务和电子政务的信息安全，更关系到我国战略层面上的如二代身份证的信息安全。所以，作为本课题Shor量子计算对公钥密码攻击就具有了重要的科研价值和实际意义。

Shor算法是一种运行在量子计算机上的量子算法。人们已经付出了很多努力直接去构建量子计算机，但目前为止仍然难以实现控制成百上千个量子比特的量子计算机。令人遗憾的是，物理学界、密码学界、计算机学界和数学界等的科学家认为：要研究出能够控制成百上千个比特的量子计算机在未来很长一段时间内依然是极其困难的。本文参阅大量国内外相关研究文献，对目前Shor量子计算对公钥密码攻击的研究概况和物理硬件上的实现做综述性分析。

2 国内外研究的最新进展

目前应用最广泛的公钥密码是RSA和ECC，所以可以说量子算法（这里就是Shor算法）对公钥密码的攻击就是量子算法对RSA和ECC加密算法的攻击。由于RSA和ECC加密体制的安全基础分别是IFP和ECDLP问题，所以量子算法攻击RSA和ECC加密算法就是要使其能够求解IFP（大数质因子分解问题）和 ECDLP（椭圆曲线离散对数问题）问题。围绕着这两个问题，目前国内外专家学者做了大量的研究。

2.1 Shor算法攻击RSA研究概况

（1）国外研究概况

1996年，美国科学家Juan Pablo Paz在一个有干扰和损耗的量子电路上用了27量子比特成功分解了15。同时他指出对于分解大数N，需要的量子比特数应是n=5L+7（其中L取大于等于log2N的最小正整数）。这项工作的开展给实际操作中实现Shor量子算法提供了很好的借鉴。

2001年，美国IBM公司和斯坦福大学合作，利用核磁共振技术演示了Shor算法对15进行分解的实验，但该实验不能显示其量子属性，也无法扩展到更多的比特，限制了进一步的研究。

2003年，加拿大蒙特利尔大学的 Stephane Beauregard介绍了一个使用2n+3量子比特的Shor分解的电路[1]，还用量子电路的11个量子比特分解了15。该电路的部分灵感来自于1996年的英国牛津大学克拉伦登实验室[2]。

2004年，美国赫尔辛基理工大学材料物理实验室的Jula J.Vartiainen利用约瑟夫森电荷量子比特实现了Shor算法[3]。他把Shor算法的量子电路分成了一系列两量子比特和三量子比特的量子门不仅加速了Shor算法的实现，而且在此基础上通过数值优化的方法成功完成了对N=21分解的物理实现。

2007年，法国理论物理研究实验室在研究Shor算法的缺陷[4]（量子比特间残余耦合造成）所产生的影响时，通过编写 Quantware库并调用该库，用 30个量子比特实现了N=943的分解。

2010年，英国布里斯托大学电气和电子工程的物理实验室和部门的量子光学中心的M.G. Thompson 等介绍了基本的Shor因式分解量子算法的实现[5]，主要是在由6个H门和 2个可控的相位门组成的波导电路中建立了一个可以实现Shor量子分解算法的电路，并成功的用Shor算法分解N=15。

2012年，美国加州大学圣巴巴拉分校的Erik Lucero等人[6]，在之前一些量子控制和硬件的技术下，展示了一个九量子元件的固态量子处理器来分解15的过程。该文首先用光谱描述设备，最后执行一个3量子比特模型来分解15，当超导量子态相干时间和更复杂的电脑被提供时可以分解更大的数。

2013年，美国卫斯理大学的 Y.S.Nan等，在一个 128核的传统计算机集群上构建了一个虚拟的运行Shor算法的量子计算机[7]，该虚拟量子计算机被分为在两种模式下实现Shor算法。Shor算法的核心部分包括模幂运算部分ME和求周期运算部分PF。这两种模式也就是基于Shor算法划分的：第一种模式称之为 PF（周期查找）模式即只有周期查找部分没有Shor算法的模幂运算部分（这部分用传统模幂运算结果来代替），第二种模式称之为满Shor算法模式包括模幂运算和周期查找两部分。在第一种模式下运行的虚拟量子计算机可以最多控制39量子比特来实现N=55793的分解，在第二种模式下，可以最多实现N=57的分解。

（2）国内研究概况

国内的研究起步比较晚，这其中主要以中国科技大学的研究者为代表。

2007年，中国科学院公布，中国科技大学教授潘建伟和他的同事杨涛等[8]与英国牛津大学的研究人员合作，在国际上首次利用光量子计算机实现了Shor量子分解算法，研究发表在当年1月的物理评论快报上。并在该量子计算上成功操控了 4个光子量子比特构造一个简单的线性光网络实现N=15的分解。

2.2 Shor算法攻击ECC研究概况

关于量子算法Shor算法对ECC的攻击相对于Shor算法攻击RSA来说很少。原因主要有两方面：（1）Shor算法是建立在有限域的乘法群上来求解问题的，而ECC加密算法的椭圆曲线密码是基于有限域下的加法群。虽然有限域下乘法群和加法群都可以归纳为阿贝尔隐含子群，但它们之间还是有很大区别的。（2）ECC加密算法相对RSA算法具有更难理解、运算更复杂的特征。这就使得研究Shor算法攻击ECC加密算法变得更加困难。截止2014年12月份，经对《Nature》、《Science》、《PhyReview》等国内外相关文献的搜寻，针对Shor算法攻击ECC的研究主要有以下几家为代表：

首先是Shor本人。1994年，Shor提出了量子算法Shor算法，他指出Shor算法可以很容易破解大素数质因子分解，而且Shor算法可以去求解离散对数问题。至此开创了量子算法对公钥密码攻击的研究，也给后来基于Shor算法求解椭圆曲线离散对数问题提供了很重要的思路。

其次，是以美国里奇蒙大学的Jodie Eicher和YawOpoku为代表的研究[9]。在 1997年，他们在首先介绍了椭圆曲线加密系统和量子计算的基础之上，假设一个量子可以运行Shor算法的量子计算机已经存在，详细的分析了Shor算法求解离散对数问题的过程并给出理论上的实现操作步骤。因为，椭圆曲线离散对数问题与离散对数问题具有一定的相关性，他们做了类似于Shor算法求解离散对数问题的用Shor算法求解椭圆曲线离散对数问题的研究。令人欣喜的是，按着他们的思想和方法，他们在理论上成功分析了一个具体的用Shor算法求解椭圆曲线离散对数问题的例子。但是该举例实现起来相当困难。

另外一个具有代表性的是在2003年加拿大的滑铁卢大学做的关于用Shor算法求解椭圆曲线离散对数问题的研究。滑铁卢大学最开始是从数学和Shor算法两个方面进行着手分析：首先，分析有限域下各种椭圆曲线的特性并选择了一条特殊的椭圆曲线进行分析；然后，从实现Shor算法的模幂运算与量子傅里叶变换的两个模块本身出发，进行对Shor算法进行优化。在此基础上，逐步分析Shor算法求解IFP、DLP、ECDLP问题，理论上做了一个很完整的Shor算法求解椭圆曲线离散对数问题的研究，并指出对于Shor算法攻击n位比特的ECC，需要的量子比特数为6n Qubits。但是，仅限于理论分析没有给出实验模拟的过程。

此外，国内有关Shor算法求解椭圆曲线离散对数问题的研究也在逐步开展，这里面例如解放军信息工程大学等[9][10]都有这方面的研究。

3 物理硬件上的实现

量子计算机上的物理硬件的实现能力决定着Shor算法分解攻击的能力，对量子计算机上的物理硬件实现情况做相关分析总结。

在较新研究中，2012年，美国斯坦福大学爱德华.L.金兹顿实验室的N.Cody Jones等人提出了一个基于光控量子点的量子计算机分层结构[11]，通过将功能划分为层，可以独立设计和分析子系统，并在该硬件平台上执行分析了分解算法。

3.1 实现量子计算机的几种物理方法

（1）光子法（原子和光腔相互作用）：如用光子法进行量子密钥的分发。光晶格中的中性原子和光学级联腔中的原子进行量子模拟，光学腔可以任意的几何方式排列，每个腔和一个原子系统相互作用，同时可以加入外光场来驱动原子系统，腔中的原子和腔场一起构成了极化子，这个系统可以用于模拟Bose-Hubbard模型。

（2）捕获原子法（离子阱）：光腔（介质波导）中相干光子做Qubit；微波腔中相干电磁波做Qubit。例如利用Pauli电磁势阱来束缚离子，离子在势阱中呈轴向排布，量子比特编码在离子的内态上。优势在于存在高精度的门操作和量子探测方案，但是集成性不是特别好，离子较多时，为使库伦势能最低，离子不在呈现规则的轴向排布，而是会形成“之”字型或者其他更复杂的图样。

（3）核磁共振实验较简单，可在室温下进行，缺点：需做re-focds等，需要一定花费，使信号随量子比特数增加而指数下降，要找具备很多有效量子比特的特定分子也不容易，所以NMR的QC最高只达到10Qubit左右。有实验执行了基于7个量子位元的液态磁振量子电脑的Shor算法，对15做因式分解为3和5的示范，有写到对7个量子比特算法分解15为3和5有实现了99.94%的性能改进。

（4）量子点和渗杂物固体，在二维电子气中通过叠加两维的网格门，实现了一个半导体量子点链，只有量子点和超导约瑟夫森结方案更适合集成化和小型化。

（5）超导量子计算机，Qubits-SQUID中的库伯对或磁通量子，Access与操作—定位德尔电容，电感耦合（约瑟夫森结量子系统）。

（6）硅固态量子计算机，优势在于：有希望大规模扩展；固态；与硅技术可兼容。

3.2 FPGA模拟

王伶俐的FPGA模拟方法可以分解任意n量子比特门为m量子比特门和各种对角线门，即数学上n量子比特门U(2n) =U(2m)矩阵和对角矩阵。跟FPGA的结构类似，该量子结构由量子路由通道（QRC，用来量子路由资源和实现幺正变换，控制量子逻辑输入输出）和量子逻辑块（QLB，执行一个通用两量子比特门）组成。

4 总结

本文分析Shor量子计算对公钥密码的攻击的国内外研究及物理实现现状，得出：

Shor量子计算对公钥密码的攻击目前的研究还处于起步阶段，能分解的大数和求解椭圆曲线离散对数的能力还很有限。

采用传统方法来实现量子Shor量子计算攻击更具有可行性。这也有助于降低对通用量子计算机的要求，实现Shor量子计算破译公钥密码攻击现实性。

目前的物理实现还只能控制小规模的量子比特实现量子算法Shor的运行，尚不能实现对现今使用的1024位RSA和163位的ECC的完全攻击。所以要想能够在多项式时间规模内实现Shor算法对公钥密码的攻击，则必须依赖于千位以上的通用量子计算机。

[1]Juha J. Vartiainen, Antti O. Niskanen, Mikio Nakahara, and Martti M. Salomaa. Implementing Shor’s algorithm on Josephson charge qubits[J]. Phys. Rev. A 70, 012319, 2004.

[2]Ignacio Garcia-Mata, Klaus M. Frahm, and Dima L. Shepelyansky. Effects of imperfections for Shor’s factorization algorithm[J]. Phys. Rev. A 75, 052311, 2007.

[3]Chao-Yang Lu, Daniel E. Browne, Tao Yang, and Jian-Wei Pan. Demonstration of aCompiled Version of Shor’s Quantum Factoring Algorithm Using Photonic Qubits. Phys. [J]Rev. Lett. 99, 250504, 2007.

[4]M.G. Thompson, A. Politi, J.C.F. Matthews, J.L. O’Brien. Integrated Waveguide Circuits for Optical Quantum Computing[J]. Circuits, Device & System, IET. 2010, 5(2): 94-102.

[5]付向群, 鲍皖苏. 具有高概率的量子计算算法研究[D].解放军信息工程大学. 2010.

[6]Erik Lucero,R. Barends, Y. Chen, et al. Computing prime factors with a Josephson phase qubit quantum processor[J]. Nature physics. 2012, 8: 719-723.

[7]Nama Y. S., Blumel R..Streamlining Shor’s algorithm for potential hardware savings[J]. Phys. Rev. A ,87, 060304(R) (2013).

[8]Chao-Yang Lu, Daniel E. Browne, TaoYang, Jian-Wei Pan. Demonstration of a Compiled Version of Shor’s Quantum Factoring Algorithm Using Photonic Qubits[J]. Phys. Rev. Lett. 99, 250504, 2007.

[9]彭卫丰, 孙力. Shor量子算法的优化及应用研究. 计算机应用与软件[J]. 2009, 26(5): 239-247.

[10]付向群, 鲍皖苏, 王帅. ZN上离散对数量子计算算法[J].计算机学报, 2014, 37(5): 1058-1062.

[11]Jones, N. C., et al. A layered architecture for quantum computing using quantum dots[J]. Phys. Rev. X. 2, 031007 (2012).

Analysis of Shor quantum computer algorithm attacks to public key cryptography

Yin Bao1, Wang Keda2, Wang Xiao2, Wang Chao1
(1.Shanghai University Key Lab of Specialty Fiber Optics and Optical Access Network, Shanghai 200072, China; 2.China research institute of information security, Beijing 102200, China)

At present, e-government and e-commerce CA center use public key cryptography mainly containing RSA and ECC the security infrastructures of which are large integer factorization (IFP) and the elliptic curve discrete logarithm (ECDLP). In 1994，Peter W.Shor proposed Shor algorithm which could solvethe problems the of prime factorsof large numbers and elliptic curve discrete logarithm in polynomial time. It takes up the research of attackingpublic key cryptographywith Shor quantum algorithm. Referring to a lot of related research literatures, this paper makes analysis of the currently research on attacking public with key cryptography with Shor quantum algorithm and the realization of it in the physical hardware.

PublicKeyCryptography; Shor Algorithm; RSAAlgorithm; ECC Algorithm; Attacking

TN915

A

2015.04.01）

1007-757X(2015)05-0009-03

国家自然科学基金重点项目（61332019）；国家自然科学基金项目（61272096，60970006）；上海市教委创新基金重点项目（14ZZ089）

尹 宝（1990-），男，河南信阳人，上海大学，硕士研究生，研究方向：量子计算与量子攻击密码分析，上海，200072王克达（1976-），男，中国信息安全研究院，高级工程师，本科，研究方向：信息安全，北京，102200王 啸（1985-），男，中国信息安全研究院，工程师，本科，研究方向：信息技术标准化和信息安全北京，102200王 潮（1971-），男，江苏镇江人，上海大学，教授，博士生导师，博士，研究方向：无线传感器网络、网络信息安全与椭圆曲线密码学，量子计算与量子攻击密码分析，上海，200072