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

作　　者：WANG Yahui ZHANG Huanguo 

机构地区：[1]School of Computer and Information Technology,Xinyang Normal University,Xinyang 464000,Hubei,China [2]School of Cyber Science and Engineering,Wuhan University,Wuhan 430072,Hubei,China

出　　处：《Wuhan University Journal of Natural Sciences》2021年第6期489-494,共6页武汉大学学报（自然科学英文版）

基　　金：Supported by Nanhu Scholars Program for Young Scholars of Xinyang Normal University。

摘　　要：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 gcd(a^(r/2)±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^(er)≡C(mod n)does not need to be even.Moreover,the success probability of the new algorithm is at least 4φ(r)/π^(2)r and higher than that of Shor’s algorithm,though the time complexity for both algorithms is about the same.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]