Quantum Polynomial-Time Fixed-Point Attack for RSA  

作　　者：Yahui Wang Huanguo Zhang Houzhen Wang 

机构地区：[1]School of computer, Wuhan University [2]Key Laboratory of Aerospace Information security and trusted computing Ministry of Education, Wuhan University

出　　处：《China Communications》2018年第2期25-32,共8页中国通信（英文版）

基　　金：partially supported by he State Key Program of National Natural Science of China No. 61332019;Major State Basic Research Development Program of China (973 Program) No. 2014CB340601;the National Science Foundation of China No. 61202386, 61402339;the National Cryptography Development Fund No. MMJJ201701304

摘　　要：Security analysis of public-key cryptosystems is of fundamental significance for both theoretical research and applications in cryptography. In particular, the security of widely used public-key cryptosystems merits deep research to protect against new types of attacks. It is therefore highly meaningful to research cryptanalysis in the quantum computing environment. Shor proposed a wellknown factoring algorithm by finding the prime factors of a number n =pq, which is exponentially faster than the best known classical algorithm. The idea behind Shor's quantum factoring algorithm is a straightforward programming consequence of the following proposition: to factor n, it suffices to find the order r; once such an r is found, one can compute gcd( a^(r/2) ±1, n)=p or q. For odd values of r it is assumed that the factors of n cannot be found(since a^(r/2) is not generally an integer). That is, the order r must be even. This restriction can be removed, however, by working from another angle. Based on the quantum inverse Fourier transform and phase estimation, this paper presents a new polynomial-time quantum algorithm for breaking RSA, without explicitly factoring the modulus n. The probability of success of the new algorithm is greater than 4φ( r)/π~2 r, exceeding that of the existing quantum algorithm forattacking RSA based on factorization. In constrast to the existing quantum algorithm for attacking RSA, the order r of the fixed point C for RSA does not need to be even. It changed the practices that cryptanalysts try to recover the private-key, directly from recovering the plaintext M to start, a ciphertext-only attack attacking RSA is proposed.Security analysis of public-key cryptosystems is of fundamental significance for both theoretical research and applications in cryptography. In particular, the security of widely used public-key cryptosystems merits deep research to protect against new types of attacks. It is therefore highly meaningful to research cryptanalysis in the quantum com- puting environment. Shor proposed a well- known factoring algorithm by finding the prime factors of a number n--pq, which is exponentially faster than the best known clas- sical algorithm. The idea behind Shor＇s quan- tum factoring algorithm is a straightforward programming consequence of the following proposition： to factor n, it suffices to find the order r; once such an r is found, one can compute gcd（ar/2＋1,n）=p or q. For odd values of r it is assumed that the factors of n cannot be found （since ar/2 is not generally an integer）. That is, the order r must be even. This restriction can be removed, however, by working from another angle. Based on the quantum inverse Fourier transform and phase estimation, this paper presents a new poly- nomial-time quantum algorithm for breaking RSA, without explicitly factoring the modulus n, The probability of success of the new algo- rithm is greater than 4φ（r）/π2r ,exceeding that of the existing quantum algorithm forattacking RSA based on factorization. In con- strast to the existing quantum algorithm for at- tacking RSA, the order r of the fixed point C for RSA does not need to be even. It changed the practices that cryptanalysts try to recover the private-key, directly from recovering the plaintext M to start, a ciphertext-only attack attacking RSA is proposed.

关 键 词：information security cryptogra-phy RSA fixed-point quantum computing 

分 类 号：TN918.1[电子电信—通信与信息系统]