Computer Science

CLC number: TP391

Quantum Algorithm for Attacking RSA Based on Fourier Transform and Fixed-Point

¹ School of Computer and Information Technology, Xinyang Normal University, Xinyang 464000, Hubei, China
² School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, Hubei, China

† To whom correspondence should be addressed. E-mail: liss@whu.edu.cn

Received: 28 September 2021

Abstract

Shor in 1994 proposed a quantum polynomial-time algorithm for finding the order r of an element a in the multiplicative group Z_n^*, which can be used to factor the integer n by computing $\text{gcd(}{a}^{r/2}\pm 1,n),$ and hence break the famous RSA cryptosystem. However, the order r must be even. This restriction can be removed. So in this paper, we propose a quantum polynomial-time fixed-point attack for directly recovering the RSA plaintext M from the ciphertext C, without explicitly factoring the modulus n. Compared to Shor’s algorithm, the order r of the fixed-point C for RSA(e, n) satisfying $C^{e^r}\equiv C(\text{mod\hspace{0.17em}}n)$ does not need to be even. Moreover, the success probability of the new algorithm is at least $4\phi (r)\text{/}{\pi }^{2}r$ and higher than that of Shor’s algorithm, though the time complexity for both algorithms is about the same.