Security Analysis of Modified ESRKGS-RSA Using Lenstra’s Elliptic Curve Method

Abstract

The Enhanced and Secure RSA Key Generation Scheme (ESRKGS), introduced in 2014, aimed to improve RSA security by employing a modulus constructed from four prime factors. However, subsequent studies in 2016 revealed that this structure did not provide additional security over standard RSA. In response, a modified version of ESRKGS was proposed in 2021, incorporating dual encoding techniques using a masking parameter γ and double encryption. This study evaluates the security of the modified ESRKGS by simulating an attack scenario in which the adversary is assumed to know of ϕ(N ), enabling recovery of encrypted messages. Additionally, we implement Lenstra’s Elliptic Curve Method (ECM) to assess the factorization resistance of the four-prime modulus when ϕ(N ) is not known. Experimental results indicate that ECM can efficiently factor the modulus into its four constituent primes under practical time constraints. These findings demonstrate that, despite recent modifications, the ESRKGS variant remains vulnerable to factorization based attacks. This highlights the necessity for more rigorous cryptographic design principles in multiprime RSA systems and calls into question the long-term viability of ESRKGS-based schemes in high-security applications.