The improved algorithm to limit scope for recovering private key in Multi-Prime RSA by utilizing Quantum Fourier Transform

Abstract

Rivest–Shamir–Adleman (RSA) is widely recognized as one of the most effective and well-known public key encryption techniques. This technology has the capability for both data encryption and digital signature purposes. The private key is the primary target for unauthorized individuals attempting to damage the security of the RSA. In fact, recovering the private key becomes a challenging task when only the modulus and the public key are disclosed. The aim of this research is to present a methodology that may be employed to retrieve the private key and other alternative keys. This methodology is specifically designed to recover the plaintext through modular exponentiation. Periodic result from Quantum Fourier Transform (QFT) is an important part of this method. The process is split into two steps. In the first step, QFT is used in a quantum environment to find the periodic result of modular exponentiation. This result is then used to find the private key and alternative keys in a classical computing setting. When considering the generation of modulus from multiple primes, it is imperative to note that Shor’s algorithm requires a minimum of two factoring steps to get the expected outcomes. On the other hand, the proposed method may be executed in a single step. Furthermore, the odd periodic outcome that is not solvable by Shor’s algorithm can be chosen to find the results by using the proposed method. In addition, this approach can also reveal other keys that may be considered as possible candidates for the private key. The experimental results emphasize the effectiveness of the utilized method in accurately identifying the private key and possible alternative candidates when implemented in instances of lower size. Moreover, the periodic outcome ensures accurate achievement of objectives in classical computing; it is different from Shor’s algorithm, which must generate a new periodic outcome when the result is not in the condition.

Keywords:

• QFT
• RSA
• Shor’s algorithm
• periodic

Reviewing Editor:

• Jenhui Chen, Chang Gung University, Taiwan; Dhiya Al-Jumeily, Liverpool John Moores University, United Kingdom

Subjects:

• Applied Mathematics
• Computing & IT Security
• Computation

Disclosure statement

No potential conflict of interest was reported by the author.

Additional information

Notes on contributors

Kritsanapong Somsuk

Kritsanapong Somsuk is an associate professor at the Department of Computer and Communication Engineering, Faculty of Technology, Udon Thani Rajabhat University, Udon Thani, Thailand. He obtained his M.Eng. (Computer Engineering) from Department of Computer Engineering, Faculty of Engineering, Khon Kaen University, M.Sc. (Computer Science) from Department of Computer Science, Faculty of Science, Khon Kaen University and his Ph.D. (Computer Engineering) from Department of Computer Engineering, Faculty of Engineering, Khon Kaen University. The researcher’s area of study includes computer security, cryptography, integer factorization techniques quantum computing and Shor’s algorithm.