# Improved Cryptanalysis of Some RSA Variants

Mohammed Rahmani, Abderrahmane Nitaj, Mhammed Ziane

► To cite this version:

Mohammed Rahmani, Abderrahmane Nitaj, Mhammed Ziane. Improved Cryptanalysis of Some RSA Variants. Algorithms, 2025, 18 (4), pp.223. 10.3390/a18040223. hal-05415093

HAL Id: hal-05415093

https://hal.science/hal-05415093v1

Submitted on 13 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
Article

# Improved Cryptanalysis of Some RSA Variants

Mohammed Rahmani<fnref n="1" />,*, Abderrahmane Nitaj<fnref n="2" /> and Mhammed Ziane<fnref n="1" />

**Abstract:** Several RSA variants enforce a constraint between their public and private keys through the relation $ed \equiv 1 \pmod{(p^2-1)(q^2-1)}$, where $p$ and $q$ are the prime factors of their RSA modulus $N = pq$. In this paper, we introduce a novel attack on RSA variant schemes where the public exponent satisfies an equation of the form $eu \equiv z \pmod{(p^2-1)(q^2-1)}$, with sufficiently small $|z|, |u|$, in a scenario where the attacker has access to an approximation of one of the prime factors. Our new attack utilizes Coppersmith's method, combined with lattice basis reduction techniques, to efficiently recover the prime factors of the RSA modulus in these scenarios. This method offers a significant improvement over prior attacks on RSA variants with small private exponents or partial prime information.

**Keywords:** factorization; RSA variants; RSA; Coppersmith's technique; lattice basis reduction; cryptanalysis

## 1. Introduction

Following the publication of the groundbreaking work of Diffie and Hellman [1], the first public-key scheme was introduced by Rivest, Shamir, and Adleman [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, Wiener [3] established that RSA is susceptible to attacks when $d < \frac{1}{3}N^{1/4}$. Later, Boneh and Durfee [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, Kuwakado 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

<figure><img src="image_2.png" /></figure>

check for
updates

Academic Editors: Jesper Jansson and
Christos D. Zaroliagis

Received: 27 February 2025

Revised: 30 March 2025

Accepted: 9 April 2025

Published: 12 April 2025

**Citation:** Rahmani, M.; Nitaj, A.; Ziane, M. Improved Cryptanalysis of Some RSA Variants. *Algorithms* **2025**, *18*, 223. https://doi.org/10.3390/a18040223

**Copyright:** © 2025 by the authors.
Licensee MDPI, Basel, Switzerland.
This article is an open access article
distributed under the terms and
conditions of the Creative Commons
Attribution (CC BY) license
(https://creativecommons.org/
licenses/by/4.0/).

<footnote n="1">¹ Department of Mathematics and Computer Science, Sciences Faculty, ACSA Laboratory, Mohammed First University, Oujda 60000, Morocco; mohammed.rahmani@ump.ac.ma (M.R.); m.ziane@ump.ac.ma (M.Z.)</footnote>

<footnote n="2">² UNICAEN, CNRS, LMNO, Normandy University, 14000 Caen, France</footnote>

<footnote>* Correspondence: abderrahmane.nitaj@unicaen.fr</footnote>
$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} (\text{mod } (p^2 - 1)(q^2 - 1))$.

In 2002, Elkamchouchi 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 = PQ$, with Gaussian prime numbers $P$ and $Q$. The central key equation governing the encryption and decryption process is given by $ed \equiv 1 (\text{mod } (|P|^2 - 1)(|Q|^2 - 1))$. Notably, when $|P| = p$ and $|Q| = q$ are both prime integers, this relation reduces to $ed \equiv 1 (\text{mod } (p^2 - 1)(q^2 - 1))$.

In 2003, Said and Loxton [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 (\text{mod } \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 Wiener's attack [3] and its refinement by Boneh and Durfee [4], a range of other attacks have been developed for the various RSA variants.

In [12], Peng et al. examined the equation $ed - k(p^2 - 1)(q^2 - 1) = 1$, where $e = N^\alpha$ and $d = N^\delta$, using Coppersmith'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.

In 2024, Feng et al. [13] proposed a novel partial prime exposure attack on RSA variants defined by the key equation $ed - k(p^2 - 1)(q^2 - 1) = 1$. They demonstrated that if $N = pq$ is an RSA modulus, where $\tilde{p}$ is an approximation of $p$ with $|p - \tilde{p}| = N^\sigma$, and if $e = N^\alpha$ and $d < N^\delta$, then the factorization of $N$ can be efficiently determined under the following conditions:

$$ \delta < \begin{cases} 2 - \sqrt{2\alpha\sigma}, & \text{if } 2\sigma < \alpha < \frac{9}{2}\sigma, \\ 2 - \frac{1}{3}\alpha - \frac{3}{2}\sigma, & \text{if } \frac{9}{2}\sigma \le \alpha < 6 - \frac{9}{2}\sigma. \end{cases} $$

## 1.1. Our Contribution

In the attack proposed by Feng et al. [13], the key strategy for breaking the schemes with the equation

$$ ed \equiv 1 \pmod{(p^2 - 1)(q^2 - 1)}, $$

involves transforming the key equation into a modular polynomial equation of the form

$$ x_1(x_2^2 + ax_2 + b) \equiv -1 \pmod{e}. $$

By solving this equation, the extracted solution satisfies

$$ (x_1, x_2) = (k, p + q - \tilde{p} - \tilde{q}), $$

where $\tilde{p}$ and $\tilde{q}$ are approximations of the primes $p$ and $q$, respectively. This enabled them to break the schemes in some scenarios.
In this paper, we extend the work of Feng et al. [13] by transforming the extended key equation

$$eu \equiv z \pmod{(p^2 - 1)(q^2 - 1)},$$

into the generalized modular equation

$$x_1(x_2^2 + ax_2 + b) \equiv x_3 \pmod{e}.$$

We demonstrate how the solution of this modular equation can be applied to attack the RSA variants characterized by the key equation $ed \equiv 1 \pmod{(p^2 - 1)(q^2 - 1)}$, whenever two parameters $u$ and $z$ exist such that $eu \equiv z \pmod{(p^2 - 1)(q^2 - 1)}$, and are sufficiently small, in addition to a known approximation of one of the RSA prime factors.

Notice that the equation $eu \equiv z \pmod{(p^2 - 1)(q^2 - 1)}$ is a generalization of the standard key equation $ed \equiv 1 \pmod{(p^2 - 1)(q^2 - 1)}$, and the private exponent $d$ and $u$ are related by the formula

$$u \equiv dz \pmod{(p^2 - 1)(q^2 - 1)}.$$

As a byproduct, we design a polynomial-time algorithm for attacking the mentioned schemes for a significantly broader range of public exponents compared to existing methods.

## 1.2. The Structure of the Paper

The remainder of this paper is organized in five sections. Section 2 presents some necessary preliminaries. Section 3 introduces our novel attack. Section 4 offers a comparison between our attack and existing ones. Section 5 presents two detailed numerical experiments that demonstrate the effectiveness of our proposed attack. Finally, Section 6 concludes the paper.

# 2. Preliminaries

In this section, we present fundamental results and important concepts that are pertinent to our main result.

## 2.1. Useful Lemmas

Given a positive integer of the form $N = pq$ with $q < p < 2q$, the following result provides the limiting values for $p$ and $q$ in relation to $N$, as well as the prime sum $p + q$ (see [14]).

**Lemma 1.** Let $p$ and $q$ be prime numbers satisfying $N = pq$ and $q < p < 2q$. Then, one finds that

$$\frac{\sqrt{2}}{2}N^{\frac{1}{2}} < q < N^{\frac{1}{2}} < p < \sqrt{2}N^{\frac{1}{2}}, \quad p + q < 3N^{\frac{1}{2}}.$$

The subsequent result shows that, given an approximation of $p$ for a modulus $N = pq$, one can also approximate both $q$ and $p + q$ (see [13]).

**Lemma 2.** Let $N = pq$ be the product of two prime numbers $p$ and $q$ with $q < p < 2q$. Assume that $\tilde{p}$ is a known approximation of $p$ with $|p - \tilde{p}| \le N^\sigma$. Then, $\tilde{q} = \lfloor \frac{N}{\tilde{p}} \rfloor$ approximates $q$, and

$$|q - \tilde{q}| < N^{\sigma}, \quad |p + q - (\tilde{p} + \tilde{q})| < 2N^{\sigma}.$$
## 2.2. Schemes with the Key Equation $ed - k(p^2 - 1)(q^2 - 1) = 1$

In 1995, Kuwakado et al. [7] introduced a cryptographic scheme utilizing a specific elliptic curve, defined by the equation

$$y^2 \equiv x^3 + bx^2 \pmod{N},$$

where $N = pq$ represents an RSA modulus. In this scheme, the public key is represented by the pair $(N, e)$, with $e$ chosen to satisfy

$$\gcd(e, (p^2 - 1)(q^2 - 1)) = 1.$$

The private key is $(N, d)$, where $d$ is determined such that

$$d \equiv \frac{1}{e} \pmod{(p^2 - 1)(q^2 - 1)}.$$

The encryption of the message $(m_x, m_y)$ is performed by computing

$$b \equiv \frac{m_y^2 - m_x^3}{m_x^2} \pmod{N},$$

after which the ciphertext $(c_x, c_y)$ is obtained by applying the encryption operation $e$ to $(m_x, m_y)$ on the elliptic curve.

Decryption is carried out by first computing

$$b \equiv \frac{c_y^2 - c_x^3}{c_x^2} \pmod{N},$$

and then applying the decryption operation $d$ to $(c_x, c_y)$ on the curve to recover the original plaintext $(m_x, m_y)$.

In 2002, Elkamchouchi et al. [8] proposed a cryptosystem in which arithmetic operations are carried out over $\mathbb{Z}[i]$, the ring of Gaussian integers, rather than the standard integers. In this scheme, the modulus is a standard $N = pq$, and the public and private exponents are related by $ed \equiv 1 \pmod{(p^2 - 1)(q^2 - 1)}$. For encryption, the plaintext $m \in \mathbb{Z}[i]$ is transformed into the ciphertext $c \equiv m^e \pmod{N}$, and the decryption is performed using $m \equiv c^d \pmod{N}$.

In [9,15], alternative RSA variants were introduced, where the modulus is expressed as $N = pq$, and the exponents $e$ and $d$ are interlinked by the key equation

$$ed \equiv 1 \pmod{(p^2 - 1)(q^2 - 1)}.$$

## 2.3. Lattice Reduction and Coppersmith's Technique

Lattices are fundamental mathematical structures that play a crucial role in various branches of mathematics. They can be understood as discrete subgroups of finite-dimensional vector spaces. Formally, a Euclidean lattice is defined as follows:

**Definition 1.** Let $\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_\omega \in \mathbb{R}^d$ be $\omega$ linearly independent vectors with $\omega \le d$. The Euclidean lattice spanned by $\{\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_\omega\}$ is the set

$$\mathcal{L} = \mathbb{Z}\mathbf{u}_1 + \mathbb{Z}\mathbf{u}_2 + \dots + \mathbb{Z}\mathbf{u}_\omega.$$
The collection {$\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_\omega$} is termed a basis for the lattice $\mathcal{L}$, with $\omega$ and $d$ corresponding to the rank and dimension of the lattice, respectively. When $\omega = d$, the lattice $\mathcal{L}$ is said to have full rank.

A matrix representation of a lattice $\mathcal{L}$ can be described as follows: Let $\mathcal{B} \in \mathbb{R}^{\omega \times d}$ be the matrix whose rows correspond to the basis {$\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_\omega$}. Then, an element $\mathbf{v}$ belongs to $\mathcal{L}$ if, and only if, there exists $\mathbf{x} \in \mathbb{Z}^\omega$ such that $\mathbf{v} = \mathbf{x}\mathcal{B}$. The quantity defined by $\det(\mathcal{L}) = \sqrt{\det(\mathcal{B}^t\mathcal{B})}$ is referred to as the determinant of the lattice, where $\mathcal{B}^t$ denotes the transpose of the basis matrix $\mathcal{B}$. For a lattice of full rank, the determinant simplifies to the form $\det(\mathcal{L}) = |\det(\mathcal{B})|$.

It is a known fact that a lattice $\mathcal{L}$ of rank $\omega \ge 2$ has infinitely many bases, each consisting of $\omega$ vectors and having an identical determinant. Nevertheless, identifying a basis made up of short vectors is a computationally difficult task, particularly as the lattice dimensions grow.

In 1982, Lenstra, Lenstra, and Lovász [16] proposed the LLL algorithm, a polynomial-time method for computing a reduced basis with relatively short vectors. The following theorem, derived from [17], outlines the properties of a reduced basis generated by the LLL algorithm:

**Theorem 1.** For any lattice $\mathcal{L} \subseteq \mathbb{R}^d$ defined by a basis {$\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_\omega$}. The LLL algorithm produces a reduced basis {$\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_\omega$}, such that

$$ \|\mathbf{v}_1\| \le \|\mathbf{v}_2\| \le \dots \le \|\mathbf{v}_j\| \le 2^{\frac{\omega(\omega-1)}{4(\omega+1-j)}} \det(\mathcal{L})^{\frac{1}{\omega+1-j}}. $$

for every $j = 1, \dots, \omega$.

Prior to 1996, polynomials of the form $P(z) \equiv 0 \pmod{M}$ were typically solved when the modulus $M$ had a known factorization, employing techniques like the Chinese Remainder Theorem and the properties of finite fields. In 1996, Coppersmith [18] presented an innovative approach for determining small roots of modular polynomial equations of the form

$$ P(z) \equiv 0 \pmod{M}, $$

even when the factorization of the modulus $M$ was not available. This breakthrough was extended to multivariate polynomials, which are expressed as

$$ P(z_1, z_2, \dots, z_n) = \sum_{i_1, i_2, \dots, i_n} \rho_{i_1, i_2, \dots, i_n} z_1^{i_1} z_2^{i_2} \dots z_n^{i_n}, $$

where $\rho_{i_1, i_2, \dots, i_n} \in \mathbb{Z}$. The Euclidean norm related to this polynomial is expressed as

$$ \|P(z_1, z_2, \dots, z_n)\| = \sqrt{\sum_{i_1, i_2, \dots, i_n} \rho_{i_1, i_2, \dots, i_n}^2}. $$

In 1997, Howgrave-Graham [19] revisited Coppersmith's technique and proposed a new technique for finding small roots. This advance provided a key result that became foundational in the field.

**Theorem 2 (Howgrave-Graham).** Let $P(z_1, z_2, \dots, z_n)$ be a multivariate polynomial in $\mathbb{Z}[z_1, z_2, \dots, z_n]$ with no more than $\omega$ monomials. Let $e$ and $\mu$ be positive integers. Then, the following statements

$$ 1. \quad P(z_1^{(0)}, z_2^{(0)}, \dots, z_n^{(0)}) \equiv 0 \pmod{e^\mu}, $$
2. $\|P(z_1Z_1, z_2Z_2, \dots, z_nZ_n)\| < \frac{e^\mu}{\sqrt{\omega}}$

3. For all $i = 1, \dots, n$, $|z_i^{(0)}| < Z_i$, imply that $P(z_1^{(0)}, z_2^{(0)}, \dots, z_n^{(0)}) = 0$.

In systems involving more than two variables, extensions of Coppersmith's method typically depend on heuristic approaches. For the purposes of this study, we make the following assumption [4,12,20,21]:

**Assumption 1.** The polynomials $r_1, r_2, \dots, r_\omega$ generated by the LLL algorithm are algebraically independent.

Based on this assumption, the unique solution $(z_1^{(0)}, z_2^{(0)}, \dots, z_n^{(0)})$ to the system of polynomial equations $r_i(z_1, z_2, \dots, z_n) = 0$ for $i \le n$, can be computed using methods such as the Gröbner basis or resultant computations.

### 3. Main Results

In this section, we introduce an efficient technique for breaking RSA variants characterized by the generalized key equation

$$eu \equiv z \pmod{((p^2 - 1)(q^2 - 1))}.$$

#### The New Attack

**Theorem 3.** Let $(N, e)$ denote an RSA public key where $N = pq$, $q < p < 2q$, and $e = N^\alpha$. Suppose that there are two parameters, $|u| \le N^\delta$ and $|z| \le N^\gamma$, such that $eu \equiv z \pmod{\psi(N)}$, with $\psi(N) = (p^2 - 1)(q^2 - 1)$. Assume also that $p$ is approximated by $\tilde{p}$ with an error bound of $|p - \tilde{p}| \le N^\sigma$, where $0 \le \sigma \le \frac{1}{2}$. If

$$2\sigma < \alpha < \frac{2}{\sigma} \quad \text{and} \quad \delta + \frac{\gamma}{2} < 2 - \sqrt{2\sigma\alpha},$$

then the factorization of $N$ can be performed in polynomial time.

**Proof.** Let $\tilde{p}$ be a close approximation of $p$ such that $|p - \tilde{p}| \le N^\sigma$. By Lemma 2, the value $\tilde{q} = \lfloor N/\tilde{p} \rfloor$ serves as an approximation for $q$, satisfying the bounds

$$|q - \tilde{q}| < N^{\sigma}, \quad |p + q - \tilde{p} - \tilde{q}| < 2N^{\sigma}.$$

Let $x$ be an integer satisfying $eu - x\psi(N) = z$. This can be rewritten as

$$-x\psi(N) \equiv z \pmod{e}.$$

Write $-\psi(N) = y^2 + ay + b$, for

$$a = 2(\tilde{p} + \tilde{q}), \quad b = (\tilde{p} + \tilde{q})^2 - (N + 1)^2, \quad y = p + q - \tilde{p} - \tilde{q}.$$

As a consequence, the triplet

$$(x_1^{(0)}, x_2^{(0)}, x_3^{(0)}) = (x, y, z),$$

is a solution of the equation

$$x_1(x_2^2 + ax_2 + b) \equiv x_3 \pmod{e}.$$
To compute the root $(x_1^{(0)}, x_2^{(0)}, x_3^{(0)})$, we employ an extended version of Coppersmith's method. This involves analyzing the polynomial equation

$$f(x_1, x_2, x_3) \equiv 0 \pmod{e},$$

where

$$f(x_1, x_2, x_3) = x_1(x_2^2 + ax_2 + b) - x_3.$$

Let $x_4 = x_1x_2^2 - x_3$. Then, $f(x_1, x_2, x_3) = g(x_1, x_2, x_4)$, where

$$g(x_1, x_2, x_4) = x_1(ax_2 + b) + x_4.$$

Building on Coppersmith's method, we introduce an additional parameter $\zeta > 0$, which will be optimized, along with two integers $\mu$ and $w$, where $0 \le w \le \mu$. We then define the following list of polynomials:

$$G_{w,a,b}(x_1, x_2, x_3, x_4) = x_1^a x_2^b x_3^{\mu-a-w} g(x_1, x_2, x_4)^w e^{\mu-w}, \quad (w, a, b) \in C \cup D,$$

where

$$C = \{(w, a, b) \mid b = 0, 1, w = 0, \dots, \mu, a = 1, \dots, \mu - w\}, \\ D = \{(w, a, b) \mid b = 0, \dots, \lfloor \zeta \rfloor, w = \lfloor \frac{\mu}{\zeta} \rfloor b, \dots, \mu, a = 0\},$$

and, in the computations, the term $x_1x_2^2$ is replaced by $x_4 + x_3$.

Given that $(x_1^{(0)}, x_2^{(0)}, x_3^{(0)})$ is a root of the equation

$$f(x_1, x_2, x_3) \equiv 0 \pmod{e}.$$

Then, by defining $x_4^{(0)} = x_1^{(0)}(x_2^{(0)})^2 - x_3^{(0)}$, the triplet $(x_1^{(0)}, x_2^{(0)}, x_4^{(0)})$ satisfies the equation $g(x_1, x_2, x_4) \equiv 0 \pmod{e}$. Furthermore, we observe that

$$G_{w,a,b}(x_1^{(0)}, x_2^{(0)}, x_3^{(0)}, x_4^{(0)}) \equiv 0 \pmod{e^{\mu}},$$

for all $(w, a, b) \in C \cup D$.

In Coppersmith's technique, it is important to establish the bounds $X_1, X_2, X_3$, and $X_4$ such that

$$|x_1^{(0)}| \le X_1, \quad |x_2^{(0)}| \le X_2, \quad |x_3^{(0)}| \le X_3, \quad |x_4^{(0)}| \le X_4.$$

Using $\psi(N) > \frac{N^2}{2}$ and assuming that $|z| < e|u|$, we obtain the following estimate:

$$|x_1^{(0)}| = \left| \frac{eu - z}{\psi(N)} \right| < 4e|u|N^{-2} \le 4N^{\alpha+\delta-2}.$$

To obtain a bound for $x_4^{(0)} = x_1^{(0)}(x_2^{(0)})^2 - x_3^{(0)}$, we suppose

$$|x_3^{(0)}| < x_1^{(0)}(x_2^{(0)})^2,$$

so that $|x_4^{(0)}| < 2x_1^{(0)}(x_2^{(0)})^2$. In addition to $|x_2^{(0)}| < 2N^{\sigma}$, the corresponding bounds are given by

$$X_1 = 4N^{\alpha+\delta-2}, \quad X_2 = 2N^{\sigma}, \quad X_3 = N^{\gamma}, \quad X_4 = 2X_1X_2^2 = 32N^{\alpha+\delta-2(1-\sigma)}. \quad (1)$$
Next, we construct the lattice $\mathcal{L}$ represented by the matrix whose rows consist of the coefficient vectors of the polynomials $G_{w,a,b}(X_1x_1, X_2x_2, X_3x_3, X_4x_4)$. A lower triangular matrix can be formed by considering the following criteria: The rows of this matrix correspond to the polynomials $G_{w,a,b}(X_1x_1, X_2x_2, X_3x_3, X_4x_4)$ and are arranged lexicographically, assuring that

$$G_{w,a,b}(X_1x_1, X_2x_2, X_3x_3, X_4x_4) \prec G_{w',a',b'}(X_1x_1, X_2x_2, X_3x_3, X_4x_4),$$

if $w < w'$, or if $w = w'$ and $a < a'$, or if $w = w'$, $a = a'$, and $b < b'$. Similarly, the columns are represented by the monomials $x_1^a x_2^b x_3^{\mu-a-w} x_4^w$, and the lexicographical ordering is as follows:

$$x_4^w x_1^a x_2^b x_3^{\mu-a-w} \prec x_4^{w'} x_1^{a'} x_2^{b'} x_3^{\mu-a'-w'}$$

if $w < w'$, or if $w = w'$ and $a < a'$, or if $w = w'$, $a = a'$, and $b < b'$.

A typical example of the lattice basis matrix for $\mu = \zeta = 2$ and

$$f(x_1, x_2, x_3) = x_1(x_2^2 + ax_2 + b) - x_3,$$

using $x_1x_2^2 = x_3 + x_4$, is provided in Table 1. The symbol $\star$ marks the non-zero entries.

<table><caption>**Table 1.** The lattice basis matrix for $(\mu, \zeta) = (2,2)$.</caption><thead><tr><th>G<sub>w,a,b</sub></th><th>x<sub>3</sub><sup>2</sup></th><th>x<sub>1</sub>x<sub>3</sub></th><th>x<sub>1</sub>x<sub>2</sub>x<sub>3</sub></th><th>x<sub>1</sub><sup>2</sup></th><th>x<sub>1</sub><sup>2</sup>x<sub>2</sub></th><th>x<sub>3</sub>x<sub>4</sub></th><th>x<sub>2</sub>x<sub>3</sub>x<sub>4</sub></th><th>x<sub>1</sub>x<sub>4</sub></th><th>x<sub>1</sub>x<sub>2</sub>x<sub>4</sub></th><th>x<sub>4</sub><sup>2</sup></th><th>x<sub>2</sub>x<sub>4</sub><sup>2</sup></th><th>x<sub>2</sub><sup>2</sup>x<sub>4</sub><sup>2</sup></th></tr></thead><tbody><tr><td>G<sub>0,0,0</sub></td><td>e<sup>2</sup>X<sub>3</sub><sup>2</sup></td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>G<sub>0,1,0</sub></td><td>0</td><td>e<sup>2</sup>X<sub>1</sub>X<sub>3</sub></td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>G<sub>0,1,1</sub></td><td>0</td><td>0</td><td>e<sup>2</sup>X<sub>1</sub>X<sub>2</sub>X<sub>3</sub></td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>G<sub>0,2,0</sub></td><td>0</td><td>0</td><td>0</td><td>e<sup>2</sup>X<sub>1</sub><sup>2</sup></td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>G<sub>0,2,1</sub></td><td>0</td><td>0</td><td>0</td><td>0</td><td>e<sup>2</sup>X<sub>1</sub><sup>2</sup>X<sub>2</sub></td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>G<sub>1,0,0</sub></td><td>0</td><td>*</td><td>*</td><td>0</td><td>0</td><td>eX<sub>3</sub>X<sub>4</sub></td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>G<sub>1,0,1</sub></td><td>*</td><td>0</td><td>*</td><td>0</td><td>0</td><td>*</td><td>eX<sub>2</sub>X<sub>3</sub>X<sub>4</sub></td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>G<sub>1,1,0</sub></td><td>0</td><td>0</td><td>0</td><td>*</td><td>*</td><td>0</td><td>0</td><td>eX<sub>1</sub>X<sub>4</sub></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>G<sub>1,1,1</sub></td><td>0</td><td>*</td><td>0</td><td>0</td><td>*</td><td>0</td><td>0</td><td>*</td><td>eX<sub>1</sub>X<sub>2</sub>X<sub>4</sub></td><td>0</td><td>0</td><td>0</td></tr><tr><td>G<sub>2,0,0</sub></td><td>0</td><td>*</td><td>0</td><td>*</td><td>*</td><td>0</td><td>0</td><td>*</td><td>*</td><td>X<sub>4</sub><sup>2</sup></td><td>0</td><td>0</td></tr><tr><td>G<sub>2,0,1</sub></td><td>0</td><td>*</td><td>*</td><td>0</td><td>*</td><td>*</td><td>0</td><td>*</td><td>*</td><td>*</td><td>X<sub>2</sub>X<sub>4</sub><sup>2</sup></td><td>0</td></tr><tr><td>G<sub>2,0,2</sub></td><td>*</td><td>*</td><td>*</td><td>0</td><td>0</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>*</td><td>X<sub>2</sub><sup>2</sup>X<sub>4</sub><sup>2</sup></td></tr></tbody></table>

By construction, the lattice basis matrix is lower triangular, and each diagonal entry takes the form $X_1^a X_2^b X_3^{\mu-a-w} X_4^w e^{\mu-w}$ for some combination $(w, a, b)$ belonging to $C \cup D$. This shows that the determinant of the lattice can be expressed as

$$\det(\mathcal{L}) = X_1^{n_{X_1}} X_2^{n_{X_2}} X_3^{n_{X_3}} X_4^{n_{X_4}} e^{n_e}, \qquad (2)$$

with $n_{X_1} = \mathcal{E}(a)$, $n_{X_2} = \mathcal{E}(b)$, $n_{X_3} = \mathcal{E}(\mu - a - w)$, $n_{X_4} = \mathcal{E}(w)$, $n_e = \mathcal{E}(\mu - w)$, and

$$\mathcal{E}(c) = \sum_{b=0}^{1} \sum_{w=0}^{\mu} \sum_{a=1}^{\mu-w} c + \sum_{b=0}^{\lfloor \frac{\mu}{\zeta} \rfloor} \sum_{w=\lfloor \frac{\mu}{\zeta} \rfloor}^{\mu} \sum_{a=0}^{0} c.$$
In order to optimize $\zeta$, we replace it with $\mu\zeta$, and to facilitate the computations, we adopt the approximation $|x| \approx x$ for a real number $x$. Consequently, the exponents $n_{X_1}, n_{X_2}, n_{X_3}, n_{X_4}, n_e$, along with the lattice dimension $\omega = \mathcal{E}(1)$, are governed by the following relations:

$$
\begin{align*}
n_{X_1} &= \frac{1}{3}\mu^3 + o(\mu^3) \\
n_{X_2} &= \frac{1}{6}\zeta^2\mu^3 + o(\mu^3) \\
n_{X_3} &= \frac{1}{6}(\zeta + 2)\mu^3 + o(\mu^3) \\
n_{X_4} &= \frac{1}{3}(\zeta + 1)\mu^3 + o(\mu^3) \\
n_e &= \frac{1}{6}(\zeta + 4)\mu^3 + o(\mu^3) \\
\omega &= \frac{1}{2}(\zeta + 2)\mu^2 + o(\mu^2).
\end{align*}
\tag{3}
$$

The LLL algorithm is applied to reduce the matrix $M$, yielding a reduced matrix $M'$ that preserves the determinant. From this reduced matrix, we construct $\omega$ polynomials $r_i(x_1, x_2, x_3, x_4)$, where $i = 1, \dots, \omega$, each of which satisfies the congruence

$$r_i(x_1^{(0)}, x_2^{(0)}, x_3^{(0)}, x_4^{(0)}) \equiv 0 \pmod{e^{\mu}}.$$

In order to find the solution, we establish a connection between Theorems 1 and 2, concentrating on the scenario where $j = 4$. Thus, we set

$$2^{\frac{\omega(\omega-1)}{4(\omega-3)}} \det(\mathcal{L})^{\frac{1}{\omega-3}} < \frac{e^{\mu}}{\sqrt{\omega}}.$$

By combining with (2), this simplifies to

$$e^{n_e - \mu(\omega-3)} X_1^{n_{X_1}} X_2^{n_{X_2}} X_3^{n_{X_3}} X_4^{n_{X_4}} < \frac{1}{2^{\frac{\omega(\omega-1)}{4}} (\sqrt{\omega})^{\omega-2}} < 1. \quad (4)$$

By considering the dominant terms in (3) along with the bounds in (1), and neglecting smaller values, we obtain

$$\sigma\zeta^2 + (\gamma + 2\delta + 4\sigma - 4)\zeta + 2\alpha + 2\gamma + 4\delta + 4\sigma - 8 < 0, \quad (5)$$

in which the optimal value for $\zeta$ is

$$\zeta_0 = \frac{2 - \delta - \frac{\gamma}{2} - 2\sigma}{\sigma}.$$

To ensure that $\zeta_0 > 0$, the parameters must satisfy

$$\delta + \frac{\gamma}{2} < 2 - 2\sigma. \quad (6)$$

Plugging $\zeta_0$ in (5), we arrive at

$$-4\delta^2 - 4(\gamma - 4)\delta - \gamma^2 + 8\alpha\sigma + 8\gamma - 16 < 0.$$

Solving the former inequation for $\delta$, we obtain

$$\delta < 2 - \sqrt{2\sigma\alpha} - \frac{\gamma}{2}.$$
Using the assumption $\alpha > 2\sigma$ and (6), we obtain

$$ \delta + \frac{\gamma}{2} < \min(2 - \sqrt{2\sigma\alpha}, 2 - 2\sigma) = 2 - \sqrt{2\sigma\alpha}. $$

In addition, given that $\delta \ge 0$ and $\gamma \ge 0$, the inequality

$$ 2 - \sqrt{2\sigma\alpha} > 0, $$

is satisfied if $\alpha < \frac{2}{\sigma}$.

Afterward, we select four reduced and algebraically independent polynomials, denoted as $r_i(x_1, x_2, x_3, x_4)$ for $1 \le i \le 4$. By solving the system of equations $r_i(x_1, x_2, x_3, x_4) = 0$ for $i = 1, 2, 3, 4$ over the integers, using either the Gröbner basis approach or resultant techniques, we can extract

$$ x_2^{(0)} = p + q - \tilde{p} - \tilde{q}. $$

Finally, solving the system $N = pq$ and $x_2^{(0)} + \tilde{p} + \tilde{q} = p + q$, we can recover $p$ and $q$. This concludes the proof. □

A consequence of Theorem 3 is the following result, which concerns the case where the modulus $N = pq$ is the product of two primes, $p$ and $q$, with a sufficiently small difference $|p - q|$.

**Corollary 1.** Let $(N, e)$ denote an RSA public key where $N = pq$, with $q < p < 2q$, and $e = N^\alpha$. Assume the existence of two parameters, $|u| \le N^\delta$ and $|z| \le N^\gamma$, such that $\mathrm{eu} \equiv z \pmod{\psi(N)}$, where $\psi(N) = (p^2 - 1)(q^2 - 1)$. Furthermore, suppose that the prime difference $|p - q| \le N^\sigma$ is small, with $0 \le \sigma \le \frac{1}{2}$. If

$$ 2\sigma < \alpha < \frac{2}{\sigma} \quad \text{and} \quad \delta + \frac{\gamma}{2} < 2 - \sqrt{2\sigma\alpha}, $$

then we can recover $p$ and $q$ in polynomial time.

**Proof.** Assume that $p - q < N^\sigma$. According to Lemma 1, we have $q < \sqrt{N} < p$, which implies that

$$ 0 < p - \sqrt{N} < p - q \le N^\sigma. $$

This suggests that $\tilde{p} = \sqrt{N}$ is a close approximation of $p$, with $|p - \tilde{p}| < N^\sigma$. Applying Theorem 3, we can factor $N = pq$ under the conditions

$$ 2\sigma < \alpha < \frac{2}{\sigma} \quad \text{and} \quad \delta + \frac{\gamma}{2} < 2 - \sqrt{2\sigma\alpha}. $$

This completes the proof. □

# 4. Comparison with the Existing Attacks

In this section, we compare the bounds of our attack with those of previous approaches.

## 4.1. Comparison with Peng et al.'s Attack

In [12], Peng et al. proposed an attack against the RSA variants based on the key equation

$$ ed - k(p^2 - 1)(q^2 - 1) = 1. $$

They demonstrated that the system is vulnerable when $e = N^\alpha$, $d = N^\delta$, and $\delta < 2 - \sqrt{\alpha}$. This represents the optimal bound for attacks targeting small private exponents in such
schemes. This bound can be obtained by taking $\gamma = 0$ and $\sigma = \frac{1}{2}$. As a consequence, our attack can be seen as an extension of the attack of Peng et al.

## 4.2. Comparison with Feng et al.'s Attack

In [13], Feng et al. introduced an attack on cryptographic systems defined by the key equation $ed - k(p^2 - 1)(q^2 - 1) = 1$. They showed that for a modulus $N = pq$, where $e = N^\alpha$, $d < N^\delta$, and $|p - \tilde{p}| = N^\sigma$ with $\tilde{p}$ being an approximation of $p$, the scheme becomes susceptible to attack when $\delta < 2 - \sqrt{2\alpha\sigma}$. This vulnerability threshold is derived by setting $\gamma = 0$ in Theorem 3, highlighting that the approach of Feng et al. is a particular case within the broader framework presented in our methodology.

Additionally, the number of exponents $e$ of size $N^\alpha$ that are prone to the attack of Feng et al. can be approximated by

$$ \#\{d \mid d < N^{2-\sqrt{2\sigma\alpha}}, \gcd(d, \psi(N)) = 1\} = \mathcal{O}(N^{2-\sqrt{2\sigma\alpha}-\varepsilon}), $$

where $\varepsilon$ is a small positive parameter representing the exponents that are not coprime with $\psi(N) = (p^2 - 1)(q^2 - 1)$.

Alternatively, the quantity of the weak exponents $e$ of size $N^\alpha$ associated with our attack can be expressed as

$$ Q = \#\{ (u, z) \mid |u| \le N^\delta, |z| \le N^\gamma, \delta + \frac{1}{2}\gamma < 2 - \sqrt{2\sigma\alpha}, \gcd(u, \psi(N)) = 1 \}. $$

Hence,

$$ Q \le \#\{ (u, z) \mid |u| \le N^\delta, |z| \le N^\gamma, |u|\sqrt{|z|} < N^{2-\sqrt{2\sigma\alpha}}, \gcd(u, \psi(N)) = 1 \}. $$

By setting $\rho = 2 - \sqrt{2\sigma\alpha}$, and observing $1 \le |z| < \frac{N^{2\rho}}{|u|^2}$, where $1 \le |u| < N^\rho$, an upper bound for this quantity is determined by summing the possible values of $|z|$ within the interval $[1, \frac{N^{2\rho}}{|u|^2}]$ for each $u$ satisfying $1 \le |u| < N^\rho$. This results in

$$ Q \le 4 \sum_{u=1}^{N^\rho} \sum_{z=1}^{\frac{N^{2\rho}}{|u|^2}} 1 = 4 \sum_{u=1}^{N^\rho} \frac{N^{2\rho}}{|u|^2} = 4N^{2\rho} \sum_{u=1}^{N^\rho} \frac{1}{|u|^2} \le \frac{2\pi^2}{3} N^{2\rho}, $$

where we utilized the established result $\sum_{k=1}^{+\infty} \frac{1}{k^2} = \frac{\pi^2}{6}$. Thus,

$$ Q = \mathcal{O}(N^{2(2-\sqrt{2\sigma\alpha})-\varepsilon}), $$

where $\varepsilon$ is a small positive constant representing the integers $u$ that are not coprime with $\psi(N)$. This bound greatly exceeds the number of exponents $e$ of size $N^\alpha$ that are susceptible to the attack introduced by Feng et al. [13].

# 5. Experimental Results

In this section, we provide two small numerical examples to demonstrate that our new method successfully breaks the RSA variants where previous methods fail, and present a table to show that it also works for large examples of real-world size. The computations were carried out using SageMath 10.4 [22] on a PC running Ubuntu 22.04.3 LTS, equipped with an Intel(R) Core(TM) i5-4460 CPU @ 3.20GHz (4 cores) and 8.00 GB of RAM.
5.1. A Numerical Example with a Sufficiently Small Prime Gap

This numerical example illustrates how Theorem 3 can be leveraged to break the schemes when the difference between the RSA primes is sufficiently small.

Let us examine the following public parameters, with $N$ being a 300-bit number and $e$ being a 591-bit number

$$N = 154979168861015678139379817043779303050456195924935465847814228\backslash 2890859680277309141134732469,$$

$$e = 457288125509831890795785821136858794210767210242104567444220851\backslash 229578313165377666751566097358780811176150123829929919164675754\backslash 9806692842556025667935819822827034254195266303881105.$$

This implies that $e = N^{\alpha}$, with $\alpha \approx 1.9698$.

From Corollary 1, the quantity $\tilde{p} = \lfloor \sqrt{N} \rfloor$ provides an estimate for $p$, such that

$$\tilde{p} = 1244906297120452669049070335354223115387563820.$$

The computation of $\lfloor \frac{\tilde{p}}{N} \rfloor$ subsequently results in

$$\tilde{q} = \lfloor \frac{\tilde{p}}{N} \rfloor = 1244906297120452669049070335354223115387563821.$$

The goal here is to solve the modular equation

$$x_1(x_2^2 + ax_2 + b) \equiv x_3 \pmod{e},$$

where

$$a = 2(\tilde{p} + \tilde{q}), \quad b = (\tilde{p} + \tilde{q})^2 - (N + 1)^2.$$

More specifically, we have

$$a = 4979625188481810676196281341416892461550255282,$$

$$b = -240185427808512116073417421646903712871170445256523888858285\backslash 019886634239027251972324059413204652277359229823499357615430045\backslash 0691818616461378580654179335980030497821387859658630076019.$$

To implement the approach specified in Theorem 3, an attacker without knowledge of $u$, $z$, and, $p$ can try different values for $\delta$, $\gamma$, and $\sigma$. Assume that $\delta = 0.235$, $\gamma = 0.294$, and $\sigma = 0.484$ such that $|u| \le N^{\delta}$, $|z| \le N^{\gamma}$ and $|p - p_1| \le N^{\sigma}$. These values satisfy the necessary inequalities of Theorem 3, namely

$$2\sigma \approx 0.968 < \alpha < \frac{2}{\sigma} \approx 4.132,$$

and

$$\delta + \frac{\gamma}{2} \approx 0.382 < 2 - \sqrt{2\sigma\alpha} \approx 0.619.$$
Next, we set the bounds

$$X_1 = \lfloor 4N^{\alpha+\delta-2} \rfloor = 11831177466857048064,$$

$$X_2 = \lfloor 2N^{\sigma} \rfloor = 89768152296567761007830082898706151812104192,$$

$$X_3 = \lfloor N^{\gamma} \rfloor = 328050238835591035454750720,$$

$$X_4 = 2X_1 X_2^2 = 190678855617257854312232486748643825499976561448821233\backslash 845028452847741564061825373741977013396720419279470592.$$

The lattice $\mathcal{L}$ is constructed by choosing $\mu = 5$ and $\zeta = 4$ and using the coefficient vectors of the polynomials $G_{w,a,b}(X_1x_1, X_2x_2, X_3x_3, X_4x_4)$, where

$$G_{w,a,b}(x_1, x_2, x_3, x_4) = x_1^a x_2^b x_3^{\mu-a-w} g(x_1, x_2, x_4)^w e^{\mu-w}, \quad (w, a, b) \in \mathcal{C} \cup \mathcal{D},$$

$g(x_1, x_2, x_4) = x_1(ax_2 + b) + x_4$, and the substitution $x_1x_2^2 = x_3 + x_4$ is also applied. The sets $\mathcal{C}$ and $\mathcal{D}$ are defined by

$$\mathcal{C} = \{(w, a, b) \mid b = 0, 1, w = 0, \dots, \mu, a = 1, \dots, \mu - w\},$$

$$\mathcal{D} = \{(w, a, b) \mid b = 0, \dots, \lfloor \zeta \rfloor, w = \lfloor \frac{\mu}{\zeta} \rfloor b, \dots, \mu, a = 0\}.$$

The lattice $\mathcal{L}$ has a dimension of $\omega = 50$. After applying the LLL reduction algorithm, an output of 50 polynomials is obtained. By leveraging the Gröbner basis method, four polynomials are extracted and solved over the integers, providing the desired solution

$$x_1^{(0)} = 2118139169990949806,$$

$$x_2^{(0)} = 390817915437012442315843242819187471908433,$$

$$x_3^{(0)} = 215787365557955890516827161,$$

$$x_4^{(0)} = 32352170256576205797755149595806747150304278873868333447245\backslash 5668311351552253549441721597993613823717973.$$

Combining $x_2^{(0)} + \bar{p} + \bar{q} = p + q$ with $N = pq$ gives

$$p = 1267160034859286529528805631615411782484795507,$$

$$q = 1223043377297055821011650882335853635762240567.$$

The LLL algorithm and Gröbner basis computations were completed in under 3.2 s. Notice that

$$eu \equiv z \pmod{(p^2 - 1)(q^2 - 1)},$$

where

$$u = 1112528697601846621961.$$

The hypotheses $|x_3^{(0)}| < x_1^{(0)}(x_2^{(0)})^2$ as well as $|z| < e|u|$ are well satisfied as outlined in the proof of Theorem 3.

Next, one can compute the private exponent corresponding to $e$ via

$$d \equiv \frac{1}{e} \pmod{(p^2 - 1)(q^2 - 1)}.$$
Hence,

$$d = 605002709727751669617165546601883006212903964271667723683291\ \ 018629338222112941267558151236353614233660075317610862453388\ \ 60942430869431283894009332939209545056528528907125307870961.$$

Observe that $d = N^{\delta_0}$ with $\delta_0 \approx 1.982$.

To experimentally validate the comparisons made in Section 4, we observed that $|p - \tilde{p}| \le N^{\sigma_0}$, where $\sigma_0 \approx 0.48062$.

Feng et al. [13] proposed an optimal bound for breaking RSA schemes, given by $\delta_0 < 2 - \sqrt{2\sigma_0\alpha}$, where $d \le N^{\delta_0}$ defines the threshold for partial prime exposure attacks. In the numerical example considered here, we calculate $2 - \sqrt{2\sigma_0\alpha} \approx 0.623$, which is smaller than $\delta_0$. This result demonstrates that Feng's method is ineffective in compromising the system in this particular case.

In the same manner, the optimal bound for small private exponent attacks, as proposed by Peng et al. [12], is $\delta_0 < 2 - \sqrt{\alpha}$. In our case, we compute $2 - \sqrt{\alpha} \approx 0.596$, which is also smaller than $\delta_0$. This shows that their method is not sufficient to break the systems in this particular instance.

## 5.2. A Numerical Example Highlighting the Use of a Proper Approximation

In this numerical example, we illustrate the process of recovering RSA primes when an integer that is near one of the RSA primes is accessible.

Consider the following public parameters, where $N$ is a 602-bit number and $e$ is a 1203-bit number

$$N = 966492835405917565828743876772306537872563335866019903185649724\ \ 585072428210443099203551461953784012336521319066373953079442564\ \ 5096246950121860628973430859686177613488569115359388469,$$

$$e = 777696331000137048626324377418300225698121769798015281961785263\ \ 396314104341430708362418250852799801319640832347407155148403524\ \ 830446594816250177319485494227260306500966008079178804053714386\ \ 550565059933158714405685845984477756481877004637940295537785063\ \ 120660318119031261121321236386018313549302989253240895952509090\ \ 12701494724121570822144212683726079127519436075.$$

As a result, we obtain $e = N^{\alpha}$, where $\alpha \approx 1.9996$. Suppose that $\tilde{p}$ serves as an approximation for $p$

$$\tilde{p} = 364610523335379592284389421573659615395758581802091912160143469\ \ 2397675330348189905978392575.$$

In addition,

$$\tilde{q} = \lfloor \frac{\tilde{p}}{N} \rfloor = 26507540884027330731045765925267078004728846420158921488\ \ 30934441516667046167116343321796511.$$
Using the same approach as before, we set $\delta = 0.5$, $\gamma = 0.48$, and $\sigma = 0.35$, assuming that $|u| \le N^\delta$, $|z| \le N^\gamma$, and $|p - \tilde{p}| \le N^\sigma$, also setting $\mu = 3$ and $\zeta = 2$, for which the lattice has dimension 21. This yields

$$b = -934108400890970063113012658149447009177943086257627895908427\ \ 452430596466687391156490830430984129377337370262845368309072316\ \ 837147048999456798902983065075413979216608100055377703331416184\ \ 593193736239252540424061026130258781942275427721679167321317591\ \ 128546008317439625034646622430589530983004348180039059143417035\ \ 28114881439971427073016598854361702457857015425504,$$

$$a = 125937186435130579918969416165266079088609409200736225408647382\ \ 67828684753030612498600378172.$$

and

$$X_1 = [4N^{\alpha+\delta-2}] = 10526045218379553266784328389710180922200405020583\ \ 344587683953736983232496439578853778653184,$$

$$X_2 = [2N^\sigma] = 442435044439138152363855736582994067244877411503118598\ \ 5007255552,$$

$$X_3 = [N^\gamma] = 746268905988929664887076686742541830260450951567549101\ \ 674427835233703688367285274148864,$$

$$X_4 = 2X_1 X_2^2 = 41209207783538205815969522326106407631768819589618604\ \ 56896053520766911584121244573412698478084094774623230437845253\ \ 00839108720405531155708393071899115390281782418196043961370236\ \ 047805596490885666949991968070301302915072.$$

By applying the Gröbner basis technique, we choose four of these polynomials and find their integer solution, resulting in

$$x_1^{(0)} = 927289119299658614013919916110587398358183024721353315997217625\ \ 364986735038070234,$$

$$x_2^{(0)} = -81742039631074545148932102760,$$

$$x_3^{(0)} = 155307939029434956997630259985238998486681453560506681476796626\ \ 0825646610673424375909,$$

$$x_4^{(0)} = 619592431297889806198462072567183158811595584795214277160999337\ \ 875469111193070308053807933256693043581463662201635520498003358\ \ 3325318142491.$$

By combining $x_2^{(0)} + \tilde{p} + \tilde{q} = p + q$ with $N = pq$, we obtain

$$p = 364610523335379592284389421573659615395758581802091912160143439\ \ 2965580440330615005275393973,$$

$$q = 265075408840273307310457659252670780047288464201589214883093465\ \ 9206722305110146095092692353.$$
The LLL algorithm and Gröbner basis computations were executed in less than 1 seconds. It is noteworthy that

$$eu \equiv z \pmod{(p^2 - 1)(q^2 - 1)},$$

where

$$u = 111378763389388734375287265457126953482575338986119066859878424\ 0128288156171976879.$$

The conditions $|x_3^{(0)}| < x_1^{(0)}(x_2^{(0)})^2$ and $|z| < e|u|$ are both fulfilled, as shown in the proof of Theorem 3.

The private exponent corresponding to $e$ is

$$d = 564448283796874259566671584629302225976460091746908933141533\ 804413103523490851354858189883202173086020496673336692715487\ 554862018821458311786572683162197275601409613473916288085307\ 058668848088231546671437275383745312900782226914748122021439\ 579982887102015568949798945581022534542357068682965632698913\ 800869603835969819422745866337071597390377632698184191607171.$$

Notice that $d = N^{\delta_0}$ with $\delta_0 \approx 1.988$.

To rigorously validate the comparisons presented in Section 4, we note that

$$|p - \bar{p}| \le N^{\delta_0}, \text{ where } \delta_0 \approx 0.1628.$$

Next, we begin by considering the optimal bound for small private exponent attacks, as established by Peng et al. [12]. This bound is given by

$$\delta_0 < 2 - \sqrt{\alpha}.$$

For the parameters of our case, we compute

$$2 - \sqrt{\alpha} \approx 0.585,$$

which is smaller than $\delta_0$. This result demonstrates that Peng et al.'s method is inadequate for breaking the system in this particular instance.

Similarly, the optimal bound proposed by Feng et al. [13] is expressed as

$$\delta_0 < 2 - \sqrt{2\sigma_0\alpha},$$

where $d \le N^{\delta_0}$ represents the threshold for partial prime exposure attacks. For the numerical example under consideration, we calculate

$$2 - \sqrt{2\sigma_0\alpha} \approx 1.192,$$

and since this value is smaller than $\delta_0$, we conclude that Feng et al.'s method is also ineffective in compromising the systems for this particular case.
### 5.3. Experiments with Large Examples

We applied the procedure described in Theorem 3 to examine cases where the public key $(N, e)$ involves large values. By conducting a series of computational tests, we successfully resolved the modular equation

$$x_1(x_2^2 + ax_2 + b) \equiv x_3 \pmod{e},$$

where

$$a = 2(\tilde{p} + \tilde{q}), \quad b = (\tilde{p} + \tilde{q})^2 - (N + 1)^2.$$

This method enables an efficient factorization of the modulus $N = pq$ when an amount of the most significant bits of $p$ is available. Moreover, the conditions $d > N^{2-\sqrt{\alpha}}$ and $d > N^{2-\sqrt{2\alpha\sigma}}$ are satisfied, which demonstrates that the optimal bounds in the literature [12,13] fail to break these RSA variants.

The outcomes of these experiments are presented in Table 2, where each row specifies the corresponding parameters:

* $bl(n)$ represents the bit-length of the value $n$.

* $\delta$ is a parameter where $|u| \le N^\delta$ holds.

* $\delta_0$ denotes a parameter such that $d \approx N^{\delta_0}$.

* $\alpha$ is defined through the relation $e \approx N^\alpha$.

* $\gamma$ corresponds to a parameter satisfying $|z| \le N^\gamma$.

* $\sigma$ is a parameter satisfying $|p - \tilde{p}| \le N^\sigma$.

* $Ns(p)$ denotes the number of known most significant bits of $p$.

* $\mu$ and $\zeta$ are parameters involved in the construction of the lattice $\mathcal{L}$, which has dimension $\omega$ as shown in Theorem 3.

* $\mathcal{T}(s)$ refers to the computation time in seconds required for executing the LLL algorithm and the Gröbner basis computation.

<table><caption>**Table 2.** Experiments for various values of $(N, e)$.</caption><thead><tr><th>bl(N)</th><th>bl(e)</th><th>δ</th><th>δ₀</th><th>α</th><th>γ</th><th>σ</th><th>Ns(p)</th><th>μ</th><th>ζ</th><th>ω</th><th>T(s)</th></tr></thead><tbody><tr><td>1024</td><td>2047</td><td>0.390</td><td>1.994</td><td>2.00</td><td>0.488</td><td>0.293</td><td>212</td><td>3</td><td>3</td><td>52</td><td>8.00</td></tr><tr><td>1100</td><td>2198</td><td>0.454</td><td>1.999</td><td>2.00</td><td>0.490</td><td>0.266</td><td>250</td><td>3</td><td>3</td><td>52</td><td>10.09</td></tr><tr><td>1200</td><td>2398</td><td>0.426</td><td>1.999</td><td>2.00</td><td>0.500</td><td>0.325</td><td>210</td><td>3</td><td>3</td><td>52</td><td>9.98</td></tr><tr><td>1300</td><td>2598</td><td>0.477</td><td>2.000</td><td>2.00</td><td>0.500</td><td>0.317</td><td>237</td><td>3</td><td>3</td><td>52</td><td>10.48</td></tr><tr><td>1400</td><td>2797</td><td>0.486</td><td>1.999</td><td>2.00</td><td>0.500</td><td>0.279</td><td>310</td><td>3</td><td>3</td><td>52</td><td>14.81</td></tr><tr><td>1500</td><td>2997</td><td>0.487</td><td>1.999</td><td>2.00</td><td>0.500</td><td>0.328</td><td>255</td><td>3</td><td>3</td><td>52</td><td>13.15</td></tr><tr><td>1600</td><td>3199</td><td>0.469</td><td>1.999</td><td>2.00</td><td>0.500</td><td>0.355</td><td>231</td><td>3</td><td>2</td><td>40</td><td>5.34</td></tr><tr><td>1700</td><td>3399</td><td>0.494</td><td>2.000</td><td>2.00</td><td>0.500</td><td>0.347</td><td>260</td><td>3</td><td>2</td><td>40</td><td>5.69</td></tr><tr><td>1800</td><td>3595</td><td>0.497</td><td>2.000</td><td>2.00</td><td>0.506</td><td>0.366</td><td>241</td><td>3</td><td>1</td><td>22</td><td>1.38</td></tr><tr><td>1900</td><td>3794</td><td>0.495</td><td>2.000</td><td>2.00</td><td>0.500</td><td>0.316</td><td>350</td><td>3</td><td>1</td><td>22</td><td>1.98</td></tr><tr><td>2048</td><td>4096</td><td>0.487</td><td>2.000</td><td>2.00</td><td>0.488</td><td>0.369</td><td>269</td><td>2</td><td>2</td><td>21</td><td>0.5</td></tr></tbody></table>

## 6. Conclusions

In this paper, we presented an enhanced cryptanalytic approach that builds upon Copersmith's method and incorporates lattice basis reduction. We applied this technique to analyze several variants of RSA where the modulus is $N = pq$, the modified totient function is $\psi(N) = (p^2 - 1)(q^2 - 1)$, and the generalized key equation is $eu \equiv z \pmod{\psi(N)}$. Our method successfully enables the factorization of the RSA modulus $N$ in polynomial time, even for real-world examples on a large scale. Our method works in the scenario where an amount of the most significant bits of $p$ is known, and the unknown parameters $u, z$ in the equation $eu \equiv z \pmod{\psi(N)}$ are suitably small. Our method extends all methods
where the equation is $ed \equiv 1 \pmod{\psi(N)}$ with small $d$. In addition, the results of this paper highlight the superiority of our attack over existing techniques that are not based on quantum computation, especially in scenarios involving small private exponents and partial prime information.

**Author Contributions:** Conceptualization, M.R. and A.N.; methodology, M.R. and A.N.; software, M.R.; validation, M.R., A.N. and M.Z.; formal analysis, M.R. and A.N.; investigation, M.R. and A.N.; resources, M.R. and A.N.; data curation, M.R. and A.N.; writing—original draft preparation, M.R.; writing—review and editing, M.R. and A.N.; visualization, M.R. and A.N.; supervision, M.R., A.N. and M.Z.; project administration, M.R., A.N. and M.Z. All authors have read and agreed to the published version of the manuscript.

**Funding:** This research received no external funding.

**Data Availability Statement:** The original contributions presented in this study are included in the article. Further inquiries can be directed to the corresponding author.

**Conflicts of Interest:** The authors declare no conflicts of interest.

## Abbreviations

The following abbreviations are used in this manuscript:

RSA Rivest, Shamir, Adleman

CRT Chinese Remainder Theorem

LLL Lenstra, Lenstra, and Lovász

## References

1. Diffie, W.; Hellman, M. New directions in cryptography. *IEEE Trans. Inf. Theory* **1976**, *22*, 644–654.

2. Rivest, R.; Shamir, A.; Adleman, L. A Method for Obtaining digital signatures and public-key cryptosystems. *Commun. ACM* **1978**, *21*, 120–126.

3. Wiener, M. Cryptanalysis of short RSA secret exponents. *IEEE Trans. Inf. Theory* **1990**, *36*, 553–558.

4. Boneh, D.; Durfee, G. Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$, Advances in Cryptology-Eurocrypt'99. In *Lecture Notes in Computer Science*; Springer: Berlin/Heidelberg, Germany, 1992; pp. 1–11.

5. Quisquater, J.J.; Couvreur, C. Fast decipherment algorithm for RSA public-key cryptosystem. *Electron. Lett.* **1982**, *18*, 905–907.

6. Collins, T.; Hopkins, D.; Langford, S.; Sabin, M. Public key cryptographic apparatus and Method. US Patent #5,848,159, 8 December 1998.

7. Kuwakado, H.; Koyama, K.; Tsuruoka, Y. A New RSA-Type Scheme Based on Singular Cubic Curves with equation $y^2 \equiv x^3 + bx^2 \pmod N$. *IEICE Trans. Fundam.* **1995**, *78*, 27–33.

8. Elkamchouchi, H.; Elshenawy, K.; Shaban, H. Extended RSA cryptosystem and digital signature schemes in the domain of Gaussian integers. In Proceedings of the 8th International Conference on Communication Systems, Singapore, 28–28 November 2002; Volume 1, pp. 91–95.

9. Said, M.R.M.; Loxton, J. A cubic analogue of the RSA cryptosystem. *Bull. Aust. Math. Soc.* **2003**, *68*, 21–38.

10. Smith, P.J.; Lennon, M.J.J. LUC: A New Public Key System. In Proceedings of the ninth IFIP International Symposium on Computer Security, Toronto, ON, Canada, 12–14 May 1993; pp. 103–117.

11. Boneh, D. Twenty years of attacks on the RSA cryptosystem. *Notices Amer. Math. Soc.* **1999**, *46*, 203–213.

12. Peng, L.; Hu, L.; Lu, Y.; Wei, H. An improved analysis on three variants of the RSA cryptosystem. *Int. Conf. Inf. Secur. Cryptol.* **2016**, *10143*, 140–149.

13. Feng, Y.; Nitaj, A.; Pan, Y. Partial prime factor exposure attacks on some RSA variants. *Theor. Comput. Sci.* **2024**, *999*, 1145–1159.

14. Nitaj, A. *Another Generalization of Wiener's Attack on RSA*; Africacrypt 2008 LNCS; Vaudenay, S., Ed.; Springer: Berlin/Heidelberg, Germany, 2008; Volume 5023, pp. 174–190.

15. Castagnos, G. An efficient probabilistic public-key cryptosystem over quadratic fields quotients. *Finite Fields Their Appl.* **2007**, *13*,563–576.

16. Lenstra, A.K.; Lenstra, H.W. Lovász, L. Factoring polynomials with rational coefficients. *Math. Ann.* **1982**, *261*, 513–534.

17. May, A. New RSA Vulnerabilities Using Lattice Reduction Methods. Ph.D. Thesis, University of Paderborn, Paderborn, Germany, 2003.

18. Coppersmith, D. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. *J. Cryptol.* **1997**, *10*, 233–260.
19. Howgrave-Graham, N. Finding small roots of univariate modular equations revisited. In Proceedings of the IMA International Conference on Cryptography and Coding, LNCS 1355, Cirencester, UK, 17–19 December 1997; Springer: Berlin/Heidelberg, Germany, 1997; pp. 131–142.

20. Jochemsz, E.; May, A. *A strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants*; ASIACRYPT 2006, LNCS 4284; Springer: Berlin/Heidelberg, Germany, 2006; pp. 267–282.

21. Zheng, M.; Kunihiro, N.; Yao, Y. Cryptanalysis of the RSA variant based on cubic Pell equation. *Theor. Comput. Sci.* **2021**, *889*, 135–144.

22. The Sage Developers: SageMath, the Sage Mathematics Software System (Version 10.4) (2025), Available online: https://www.sagemath.org (accessed on 8 April 2025).

**Disclaimer/Publisher's Note:** The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.