Quantum Polynomial-Time Fixed-Point Attack for RSA

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.