Enhanced Algorithm for Recovering RSA Plaintext when Two Modulus Values Share at least One Common Prime Factor
Kritsanapong Somsuk · Journal of Cyber Security and Mobility · 2025
RSA is a significant cryptographic technique depending on public key cryptography. In fact, if this technique does not have any vulnerabilities, it is considered as a robust algorithm. Nevertheless, if the system contains vulnerabilities, it can be compromised through the utilization of algorithms that target those weaknesses. Currently, RSA is vulnerable to multiple potential weaknesses. This research identifies a novel vulnerability in RSA and presents a technique to exploit this vulnerability. The proposed method, known as Common Prime Attack (CPA), aims to exploit this vulnerability to recover the original message. The vulnerability arises when at least two key producers generate their modulus that inadvertently have at least one prime factor in common. It is divided into three cases. Case 1 relates to two moduli created from two prime numbers, with one prime being common. Case 2 involves the two moduli generated from at least three primes, with one prime common to both values. Case 3 concerns two moduli produced from at least three primes, with a minimum of two primes in common. The evidence and examples show that all situations can effectively retrieve the original message. The datasets have been generated to support three cases in which each modulus shares a common prime factor. Therefore, the experimental results demonstrate that all situations can rapidly compromise RSA with modulus lengths of 1024, 2048 and 4096 bits. CPA can successfully recover plaintexts in all cases, with a 100% success rate under simulated conditions. Moreover, the average computation time is extremely low, ranging from 1.6 ms to 17.2 ms. Because of the large bit length of the modulus, other methods are not suitable for comparison with the proposed method in terms of computational time. In addition, they require a significant amount of time to execute. However, CPA will instead be compared to other algorithms with respect to security aspects. In conclusion, all generated moduli must be mutually coprime to avoid vulnerabilities associated with CPA.