基于方程求解与相位估计攻击RSA的量子算法  

Quantum Algorithms for Breaking RSA Based on Phase Estimation and Equation Solving

作　　者：王亚辉[1,2] 张焕国 吴万青[3] 韩海清[1,2] WANG Ya-Hui;ZHANG Huan-Guo;WU Wan-Qing;HAN Hai-Qing(Computer School, Wuhan University,Wuhan430072;Key Laboratory o f Aerospace Information Security and Trusted Compuiing Ministry of Education,Wuhan430072;School of Computer Science and Technology,Hebei University,Baoding,Hebei071002)

机构地区：[1]武汉大学计算机学院,武汉430072 [2]空天信息安全与可信计算教育部重点实验室,武汉430072 [3]河北大学计算机科学与技术学院,河北保定071002

出　　处：《计算机学报》2017年第12期2688-2699,共12页Chinese Journal of Computers

基　　金：国家自然科学基金重点项目(61332019);国家自然科学基金(61303212;61202386);国家自然科学基金重大项目(91018008)资助;国家"九七三"重点基础研究发展(2014CB340601)~~

摘　　要：量子计算的发展对现有的公钥密码体制提出了严峻的挑战,利用Shor算法就可攻击公钥密码RSA,ELGamal等.因此,研究量子计算环境下的密码破译有重大意义.经典的因子分解算法是通过求解同余方程α~2≡β~2(modn)实现的.据查证,目前还没有求解此方程的量子算法,故我们试图从量子计算的角度提出解决此同余方程的量子算法.该算法是对经典求解同余方程α~2≡β~2(modn)的量子化实现.相比于Shor算法,算法1所需量子位少,具有亚指数时间复杂度,且成功概率接近于1.为了降低时间复杂度,我们从非因子分解角度出发,基于量子Fourier逆变换和相位估计,给出了算法.同Shor算法相比,算法2不需要分解n,而从RSA密文C直接恢复出明文M,具有多项式时间复杂度,且成功概率高于Shor算法攻击RSA的成功概率,同时不必要满足密文的阶为偶数.The development of quantum computation presents a serious challenge to the existing public key cryptosystems,and the public key cryptosystems,RSA,ELGamal,etc.are broken by using Shor’s algorithm.Therefore,it is of great significance to study the cryptanalysis in the quantum computing environment.It is well known that the RSA public key cryptography depends essentially only on the computational intractability of the Integer Factorization Problem(IFP),so obviously,the most direct method to attack RSA is to solve the IFP.If IFP can be solved in polynomial time,then RSA and many other cryptographic systems can be broken.However,the currently existing fastest integer factorization algorithm up to date is the Number Field Sieve,which runs in sub exponential time.Surprisingly,the world was astonished when Shor announced in1994that he found a quantum integer factorization algorithm which can solve IFP and break RSA both in polynomial time.Since then,various improved and compiled versions of Shor’s algorithm using different technics have been proposed and studied,in short,there are two important research directions in quantum integer factorization:(1)Build a(practical)quantum computer or even other types of physical computers to implement the full version or compiled version of Shor’s algorithm.(2)Improve,modify and simply Shor’s original algorithm or even invent new quantum factoring algorithms to be run on quantum computers with fewer quantum bits.Therefore,there are two aspects that need to be improved.One is that how to present a quantum algorithm for breaking RSA with fewer qubits.The classical factorization algorithm is realized by solving the congruent equationα2≡β2(modn).However,to the best knowledge of the authors,there is no quantum algorithm for solving this equation till now.So we are trying to give quantum Algorithm1to solve this equation from the perspective of quantum computation,which is the implementation of quantization of the classical quantum algorithm for solving the congruent equation.Com

关 键 词：信息安全 密码学 RSA密码体制 量子计算 

分 类 号：P301[天文地球—地球物理学]