Research On Quantum Attack Methods Of RSA Cryptography

Quantum computation that calculates using quantum mechanics theory and com-puter science is a computing model,and it is using the superposition of quantum sys-tems,entanglement and coherence,etc.to achieve quantum parallel computing.It is because of the uniqueness of quantum computing that it gradually attracts the atten-tions of physicists,mathematicians and computer scientists recently.The emergence of quantum algorithms has brought a serious threat to modern cryptography,among which Shor's algorithm and Grover's algorithm are the two most threatening algorithms for cryptanalysis currently.Shor's algorithm can solve the Integer Factorization Problem(IFP)and Discrete Logarithm Problem(DLP)in polynomial-time,which makes the current widely used RSA,ElGamal and ECC public key cryptosystem unsafe any more under the quantum computing environment;Grover's algorithm is a universal quantum search algorithm,and by which a quadratic speed-up can be made by it in solving a broad category of search problems,it reduces the key length of a key by half and poses a threat to the existing cryptosystem.Security analysis of public key cryptosystems in the quantum computing environment is of fundamental significance for both theoretical research and application implementations in cryptography.Especially,the security of widely used RSA,ElGamal and ECC public-key cryptosystems deserves deep research.Modern cryptography is designed based on the difficult problems in number theory,and the IFP is the important difficult problem in number theory.Nowadays the security of widely used RSA public key cryptography in electronic bank,network and other fields is designed depended on the intractability of integer factorization.RSA public key cryptosystem is difficult to decipher because it depends on the IFP which cannot be solved quickly.Focusing on the characteristics of RSA public key cryptosystem,this paper proposes quantum algorithms for attacking RSA,based on equation solving,phase estimation,fixed point property and ciphertext period.The main works and results of this paper can be summarized as follows:(1)We propose quantum algorithms for breaking RSA based on phase estimation and equation solving.The classical factorization algorithm is realized by solving the congruent equation ?2 ??2(mod n).However,it is verified that there is no quanturm algorithm for solving this equation till now.So we are trying to give quantum Algorithm 4 to solve this equation from the quantum computing point of view,which is the imple-mentation of quantization of the classical quantum algorithm for solving the congruent equation.Although Algorithm 4 has subexponential-time complexity,it is the first quantum algorithm for solving congruent equations.Moreover,the success probability of the Algorithm 4 is close to 1.In order to further reduce 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 Algorithm 5 is presented,it directly recovers the RSA plaintext M from the ciphertext C without explicitly factoring the modulus n,and hence,breaks the famous RSA public key cryptosystem.Compared to Shor's algorithm,Algorithm 5 directly recovers the RSA plaintext M from the ci-phertext C without factoring the modulus n;the order of the ciphertext C satisfying Cr ? 1(mod n)does not need to be even;and the success probability of Algorithm 5 is higher than Shor's.(2)We present quantum algorithms for breaking RSA based on RSA fixed-point.According to the properties of RSA fixed-point,the fixed point attack problem is trans-formed into a function periodic problem by using quantum computation technique.Based on the quantum inverse Fourier transform and phase estimation,new polynomial-time quantum algorithms are presented.The results show that the two algorithms di-rectly recover the plaintext M from the ciphertext C without factorization,and the success probability of the two algorithms are higher than the existing quantum algo-rithm for attacking RSA based on factorization.(3)We propose quantum algorithms for attacking RSA based on ciphertext pe-riod.Based on the periodicity of the ciphertext function f(x)= Cx(mod n),using the quantum fourier transform,we can obtain the period r of the ciphertext function f(x)= Cx(mod n).Moreover,combined with the knowledge of number theory,we can recover the plaintext message M.Here it avoids the order of the number must be even and the output maybe a trivial factor,given a ciphertext only attack against RSA cryptosystem.Moreover the success probability of the new algorithm is higher than Shor's.