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

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

量子计算的发展对现有的公钥密码体制提出了严峻的挑战,利用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.Compared to Shor’s algorithm,Algorithm1requires fewer quantum bits,with sub exponential time complexity.Moreover,the success probability is close to1.Another is that how to design the compiled version of Shor’s algorithm.In order to induce the time complexity,from the point of view of non factorization,based on the quantum inverse Fourier transform and phase estimation,a polynomial time quantum Algorithm2for directly recovering the RSA plaintext M from the ciphertext C without explicitly factoring the modulus n is presented,and hence,breaks the famous RSA public key cryptosystem.Compared to Shor’s algorithm,Algorithm2directly recovers the RSA plaintext M from the ciphertext C,without factoring the modulus n;the order of the ciphertext C satisfying Cr≡1(modn)does not need to be even;and the success probability of Algorithm2is higher than Shor’s.