Cogent Engineering (Dec 2024)
The improved algorithm to limit scope for recovering private key in Multi-Prime RSA by utilizing Quantum Fourier Transform
Abstract
AbstractRivest–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
