Malaysian Journal of Mathematical Sciences, December 2025, Vol. 19, No. 4
Cryptanalysis of The RSA Variant Cryptosystem: Exploiting Weaknesses in Digital Certificates Generated via Compromised Certificate Authority
Mahad, Z., Kamel Ariffin, M. R., Abd Ghafar, A. H., and Salim, N. R.
Corresponding Email: zaharimahad@upm.edu.my
Received date: 23 October 2024
Accepted date: 5 May 2025
Abstract:
A fake or unauthorized digital certificate allows attackers to impersonate trusted websites, tricking users into believing they are on a legitimate site. This enables them to steal sensitive information, spy on communications, or pretend to be someone else on-line. Such certificates are typically created when a Certificate Authority (CA)–the trusted authority entity responsible for issuing secure digital certificates–is compromised or makes a mistake in the key generation process, resulting in certificates that meet security standards but contain vulnerabilities. This study examines the RSA variant cryptosystem known as Murru-Saettone scheme, which the compromised CA has generated the key pairs and used as a digital certificate. We demonstrate that the public parameter $N=pq$ used in this RSA variant cryptosystem can be factorized. Specifically, we show that if an approximation of $\psi(N)=(q^2 + q + 1)(p^2 + p + 1)$, denoted as $\Omega$, is determined and satisfies $\left |\psi(N)-\Omega\right|<\alpha N^{\frac{3}{2}}$, the modulus $N=pq$ can be efficiently factorized using continued fractions combined with Coppersmith's method.
Keywords: integer factorization problem; RSA; cubic Pell equation; continued fractions; Coppersmith's method
