# Improved Cryptanalysis of Some RSA Variants
## 1 Introduction  
Following the publication of the groundbreaking work of [PERSON] and [PERSON] [1], the first public-key scheme was introduced by [PERSON], [PERSON], and [PERSON] [2]. This system is known as RSA and remains widely used in practical applications. Its security is rooted in computationally hard problems, particularly the integer factorization problem. The cryptosystem involves generating two large prime numbers \(p\) and \(q\) with equal bit lengths, and producing the RSA modulus \(N=pq\). A public exponent is an integer \(e\) selected so that it is prime relative to \(\varphi(N)\), where \(\varphi(N)=(p-1)(q-1)\) denotes the Euler totient function. The private exponent \(d\) is defined as the inverse of \(e\) modulo \(\varphi(N)\), satisfying the key equation \(ed\equiv 1\pmod{\varphi(N)}\). The public key comprises \((N,e)\), while the private key consists of \((N,d)\). For a message \(m\) such that \(m<N\), encryption is achieved using \(c\equiv m^{e}\pmod{N}\). Decryption then recovers \(m\) via \(m\equiv c^{d}\pmod{N}\). Encryption and decryption processes can be computationally expensive with large numbers, and using small exponents can improve the efficiency of RSA. However, in 1990, [PERSON] [3] established that RSA is susceptible to attacks when \(d<\frac{1}{3}N^{1/4}\). Later, [PERSON] and [PERSON] [4] refined this limit up to \(N^{0.292}\). These findings have spurred ongoing efforts to enhance the efficiency and security of RSA, leading to the development of various alternative variants. Noteworthy examples include CRT-RSA [5] and Multi-Prime RSA [6]. Additionally, other modifications and variants of the RSA scheme have emerged, wherein the Euler totient function \(\varphi(N)=(p-1)(q-1)\) is substituted with different formulations. In 1995, [PERSON] et al. [7] proposed a variant of the RSA cryptosystem that utilizes singular cubic curves, specifically curves with the equation \(y^{2}\equiv x^{3}+bx^{2}\pmod{N}\), where\(N=pq\) is the RSA modulus, and \(b\) is an integer in \(\mathbb{Z}_{N}\). In this scheme, the public exponent \(e\) is chosen such that \(\gcd(e,\psi(N))=1\), where \(\psi(N)=(p^{2}-1)(q^{2}-1)\). The private exponent \(d\) is determined by the congruence \(d\equiv\frac{1}{e}\pmod{(p^{2}-1)(q^{2}-1)}\). In 2002, [PERSON] et al. [8] introduced an RSA variant using the arithmetic of the ring of Gaussian integers \(\mathbb{Z}[i]\). This cryptosystem employs moduli of the form \(N=\mathcal{PQ}\), with Gaussian prime numbers \(\mathcal{P}\) and \(\mathcal{Q}\). The central key equation governing the encryption and decryption process is given by \(ed\equiv 1\pmod{(|\mathcal{P}|^{2}-1)(|\mathcal{P}|^{2}-1)}\). Notably, when \(|\mathcal{P}|=p\) and \(|\mathcal{P}|=q\) are both prime integers, this relation reduces to \(ed\equiv 1\pmod{(p^{2}-1)(q^{2}-1)}\). In 2003, [PERSON] and [PERSON] [9] presented a modified version of the LUC cryptosystem [10]. In this scheme, the modulus is \(N=pq\), where \(p\) and \(q\) are prime numbers, and the public exponent \(e\) and the private exponent \(d\) are constrained by the equation \(ed\equiv 1\pmod{\psi(N)}\), where \(\psi(N)=(p^{2}-1)(q^{2}-1)\) represents a generalized Euler totient function. The RSA cryptosystem and its variants are used in several real-world applications, to secure email communications, e-commerce, digital signatures and verifications, VPNs and network security, and digital certificates such as TLS [11]. As a consequence, any attack on RSA and its variants is closely scrutinized by security specialists and cryptography system designers. Besides [PERSON]'s attack [3] and its refinement by [PERSON] and [PERSON] [4], a range of other attacks have been developed for the various RSA variants. In [12], [PERSON] et al. examined the equation \(ed-k(p^{2}-1)(q^{2}-1)=1\), where \(e=N^{\alpha}\) and \(d=N^{\delta}\), using [PERSON]'s method. Their findings improved upon previous attacks and demonstrated that if \(\delta<2-\sqrt{\alpha}\), the factorization of the modulus \(N\) can be achieved in polynomial time.