# An Improved Attack on the RSA Variant Based on Cubic Pell Equation

Mohammed Rahmani, Abderrahmane Nitaj, Abdelhamid Tadmori, Mhammed Ziane

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

► To cite this version:

Mohammed Rahmani, Abderrahmane Nitaj, Abdelhamid Tadmori, Mhammed Ziane. An Improved Attack on the RSA Variant Based on Cubic Pell Equation. Cryptography, 2025, 9 (2), pp.40. 10.3390/cryptography9020040 . hal-05415089

HAL Id: hal-05415089

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

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_2.png" /></figure>
Article

# An Improved Attack on the RSA Variant Based on Cubic Pell Equation

Mohammed Rahmani<sup>1, ∗</sup>, Abderrahmane Nitaj<sup>2, ∗</sup>, Abdelhamid Tadmori<sup>3</sup> and Mhammed Ziane<sup>1</sup>

**Abstract:** In this paper, we present a novel method to solve trivariate polynomial modular equations of the form $x(y^2 + Ay + B) + z \equiv 0 \pmod e$. Our approach integrates Coppersmith's method with lattice basis reduction to efficiently solve the former equation. Several variants of RSA are based on the cubic Pell equation $x^3 + fy^3 + f^2z^3 - 3fxyz \equiv 1 \pmod N$, where $f$ is a cubic nonresidue modulus $N = pq$. In these variants, the public exponent $e$ and the private exponent $d$ satisfy $ed \equiv 1 \pmod{\psi(N)}$ with $\psi(N) = (p^2 + p + 1)(q^2 + q + 1)$. Moreover, $d$ can be written in the form $d \equiv \frac{v_0}{z_0} \pmod{\psi(N)}$ with any $z_0$ satisfying $\gcd(z_0, \psi(N)) = 1$. In this paper, we apply our method to attack the variants when $d \equiv \frac{v_0}{z_0} \pmod{\psi(N)}$ and when $|z_0|$ and $|v_0|$ are suitably small. We also show that our method significantly improves the bounds of the private exponents $d$ of the previous attacks on the variants, particularly in the scenario of small private exponents and in the scenarios where partial information about the primes is available.

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

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

check for
updates

Academic Editor: Josef Pieprzyk

Received: 25 April 2025

Revised: 2 June 2025

Accepted: 3 June 2025

Published: 6 June 2025

**Citation:** Rahmani, M.; Nitaj, A.; Tadmori, A.; Ziane, M. An Improved Attack on the RSA Variant Based on Cubic Pell Equation. *Cryptography* **2025**, *9*, 40. https://doi.org/10.3390/cryptography9020040

**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/).

# 1. Introduction

In 1978, Rivest, Shamir, and Adleman [1] proposed a number theoretic system, called RSA, as the first public key cryptosystem. It is highly significant in terms of its practical applications. Its security is based on hard mathematical problems such as the integer factorization problem. In the RSA cryptosystem, two large prime numbers $p$ and $q$ of equal bit size are generated, and the RSA modulus $N = pq$ is then computed. Next, a public exponent $e$ is selected to satisfy $\gcd(e, \varphi(N)) = 1$, where $\varphi(N) = (p-1)(q-1)$ is the Euler's totient function. This enables computation of the private exponent $d$, which is the inverse of $e$ modulo $\varphi(N)$, that is, $d$ satisfies the modular equation $ed \equiv 1 \pmod{\varphi(N)}$. The equation $ed - k\varphi(N) = 1$ is well defined and called the key equation. The public key consists of the pair $(N, e)$, whereas $(N, d)$ is the private key. For a plaintext $m$ such that $m < N$, the encryption is done by computing $c \equiv m^e \pmod N$. The decryption of the ciphertext $c$ is performed by calculating $m \equiv c^d \pmod N$. It is well known that the encryption time is $O((\log(N))^2 \log(e))$, while the decryption time is $O((\log(N))^2 \log(d))$.

To enhance the performance of RSA, small private exponents are tempting to use.
However, in 1990, Wiener [2] showed that one can break RSA for private exponents
$d < \frac{1}{3}N^{\frac{1}{4}}$. This bound was later improved by Boneh and Durfee [3] up to $N^{0.292}$.

In 1996, Coppersmith [4] proposed a polynomial time algorithm to find small roots
of modular polynomial equations of the form $f(x) \equiv 0 \pmod M$, where $f(x) \in \mathbb{Z}[x]$,

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

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

<footnote n="3">3 Faculty of Sciences and Technology Al Hoceima, Abdelmalek Essaadi University, BP 34. Ajdir, Al Hoceima 32003, Morocco; a.tadmori@uae.ac.ma</footnote>

<footnote>∗ Correspondence: abderrahmane.nitaj@unicaen.fr</footnote>
and $M$ is an integer of unknown factorization. As a consequence, Coppersmith showed that one can break RSA if the public exponent is 3 under some constraints. Since then, Coppersmith's method has been generalized to polynomials with more variables.

In 1998, Boneh and Durfee [3] presented an attack on RSA by transforming the key equation $ed - k\varphi(N) = 1$ into a specific equation $x(-N + y) \equiv 1 \pmod e$. They used Coppersmith's method to extract the root $(x, y) = (k, p + q - 1)$ and then factored the modulus $N$ in polynomial time. As a significant result, they improved Wiener's bound up to $N^{0.292}$.

To enhance both security and efficiency in RSA, alternative schemes have been proposed. Some of these variants retain the same modulus $N = pq$ but modify the Euler totient function $\varphi(N)$, replacing it with $\psi(N) = (p^2 + p + 1)(q^2 + q + 1)m$ as in [5], or with $\psi'(N) = (p^2 - 1)(q^2 - 1)$, as in [6–9].

Recently, Feng et al. [10] proposed a new method to solve the modular polynomial equation $f(x, y) \equiv 0 \pmod e$, where $f(x, y) = x(y^2 + Ay + B) + 1$. Their method is based on Coppersmith's method and lattice-based reduction. They showed that $e = N^\alpha, |x| \le N^\beta, |y| \le N^\gamma$, and

$$ \beta < \begin{cases} \alpha - \sqrt{2\gamma\alpha}, & \text{if } \beta + 2\gamma < \alpha < \beta + 3\gamma, \\ \min\left(\frac{2}{3}\alpha - \frac{3}{2}\gamma, \alpha - 3\gamma\right), & \text{if } \alpha \ge \beta + 3\gamma. \end{cases} $$

Thus, one can find $x$ and $y$ in polynomial time. They used their method to break some RSA variants by performing a partial prime exposure attack. They proved that if $N = pq$ is an RSA modulus, $p_0$ is an approximation of $p$ such that $|p - p_0| = N^\gamma$, and $e = N^\alpha$ satisfies the key equation $ed - k\psi(N) = 1$ with $d < N^\delta$, then the factorization of $N$ can be found under the conditions

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

Observe that a private exponent $d$ can be written in the form $d \equiv \frac{v_0}{z_0} \pmod{\psi(N)}$ with any $z_0$, satisfying $\gcd(z_0, \psi(N)) = 1$ and $v_0 \equiv dz_0 \pmod{\psi(N)}$. From the modular equation $ed \equiv 1 \pmod{\psi(N)}$, one gets $e^{\frac{v_0}{z_0}} \equiv 1 \pmod{\psi(N)}$, and consequently, $e^{v_0} \equiv z_0 \pmod{\psi(N)}$.

In this paper, we transform the modular equation $e^{v_0} \equiv z_0 \pmod{\psi(N)}$ into an equation of the form $x(y^2 + Ay + B) + z \equiv 0 \pmod e$ and present a method to find its small solutions $(x, y, z)$. We then apply our method to attack the variants when $d \equiv \frac{v_0}{z_0} \pmod{\psi(N)}$, and $|z_0|$ and $|v_0|$ are suitably small.

As a byproduct, we revisit the work of Feng et al. [10] by presenting a different approach for solving the generalized equation $x(y^2 + Ay + B) + z \equiv 0 \pmod e$. We prove that if $e = N^\alpha, |x| \le N^\beta, |y| \le N^\gamma, z \le N^\mu, \alpha \ge 2\gamma$, and $\beta + \frac{1}{2}\mu < \alpha - \sqrt{2\alpha\gamma}$, one can find $x, y$, and $z$ in polynomial time. This improves the bound of Feng et al. [10] for $\alpha \ge \beta + 3\gamma$. Notice that their method becomes a particular case of our method if $\mu = 0$ and $\beta + 2\gamma < \alpha < \beta + 3\gamma$.

The organization of the paper is as follows. In Section 2, we present some useful preliminaries. In Section 3, we introduce the new method to find the small roots of the equation $x(y^2 + Ay + B) + z \equiv 0 \pmod e$. In Section 4, we compare our method with the method of Feng et al. [10] in Section 5, we apply the method to break the RSA variant. In Section 6, we compare our attack with the existing attacks. In Section 7, we conduct
numerical experiments to confirm the effectiveness of our new method. Finally, we conclude the paper in Section 8.

## 2. Preliminaries

In this section, we introduce essential results and key concepts that are relevant to our approach.

### 2.1. The Cubic Pell Curve

Let $N$ be a positive integer and $f$ be a noncubic residue in $\mathbb{Z}/NZ$. The cubic Pell curve is defined by the equation

$$x^3 + fy^3 + f^2z^3 - 3fxyz \equiv 1 \pmod{N}. \qquad (1)$$

The set of the integers $(x, y, z) \in \mathbb{Z}/NZ^3$ satisfying (1) form a group where the addition of two points $P_1 = (x_1, y_1, z_1)$ and $P_2 = (x_2, y_2, z_2)$ is defined by

$$P_1 \oplus P_2 = (x_1x_2 + f(y_2z_1 + y_1z_2), x_2y_1 + x_1y_2 + fz_1z_2, y_1y_2 + x_2z_1 + x_1z_2).$$

The neutral element is $O = (1,0,0)$, and the inverse of $P = (x,y,z)$ is given by $P^{-1} = (x^2 - fyz, fz^2 - xy, y^2 - xz)$.

The use of the cubic Pell curve in cryptography was first proposed by Murru and Saettone in [5]. The proposed scheme is a variant of the RSA scheme, and the key equation is of the form $ed \equiv 1 \pmod{\psi(N)}$.

### 2.2. Useful Lemmas

Let $N = pq$ denote an RSA modulus with $q < p < 2q$. The result that follows specifies the bounds for $p$ and $q$ using $N$.

**Lemma 1** ([11]). Let $p$ and $q$ be two prime numbers such that $N = pq$ and $q < p < 2q$. Then,

$$\frac{\sqrt{2}}{2} \sqrt{N} < q < \sqrt{N} < p < \sqrt{2\sqrt{N}},$$

and

$$2\sqrt{N} < p + q < 3\sqrt{N}.$$

The result below demonstrates that, given an approximation of $p$ for a modulus $N = pq$, it is possible to approximate both $q$ and $p+q$.

**Lemma 2** ([10]). Let $N = pq$ represent an RSA modulus, where $q < p < 2q$. Suppose $p_0$ is an approximation of $p$ such that $|p - p_0| = N^\gamma$. Then, the quantity $q_0 = \lfloor \frac{N}{p_0} \rfloor$ is an approximation of $q$, and the following inequalities hold

$$|q - q_0| < N^\gamma, \quad |p + q - p_0 - q_0| < 2N^\gamma.$$

### 2.3. RSA Variants with the Key Equation $ed - k\psi(N) = 1$

In 2003, Said and Loxton [9] introduced LUC$_3$, an enhanced version of the LUC cryptosystem that leverages the third-order linear recurrence of the Lucas function for both encryption and decryption. The system operates with a modulus $N = pq$, where $p$ and $q$ are distinct primes. It employs a public exponent $e$ and a private exponent $d$, which satisfy the congruence relation $ed \equiv 1 \pmod{\Phi(N)}$. Here, $\Phi$ is an extension of Euler's totient function, which can take forms such as $\Phi(N) = (p^2 - 1)(q^2 - 1)$ or $\Phi(N) = \psi(N)$.
In 2018, Murru and Saettone [5] developed a variant of RSA that incorporates a novel arithmetic operation $\odot$ based on the cubic Pell equation $x^3 + fy^3 + f^2z^3 - 3fxyz \equiv 1 \pmod N$. In this context, $N = pq$, and $f$ is defined as a cube nonresidue modulo of both $p$ and $q$. The public exponent $e$ is selected such that $\gcd(e, \psi(N)) = 1$. The private exponent $d$ fulfills the condition $ed \equiv 1 \pmod{\psi(N)}$.

Encryption within this framework transforms a plaintext message $(m_1, m_2)$ into the ciphertext $(c_1, c_2) = (m_1, m_2)^{\circ e} \pmod N$, while decryption retrieves the original plaintext via $(m_1, m_2) = (c_1, c_2)^{\circ d} \pmod N$.

## 2.4. Lattice Basis Reduction

In the geometry of numbers, lattices serve as fundamental mathematical structures, representing discrete subgroups within finite-dimensional vector spaces.

Specifically, when the vector space in question is $\mathbb{R}^d$, a lattice can be formally defined as follows.

**Definition 1.** Let $\omega$ and $d$ be positive integers such that $\omega \le d$. Consider $\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_\omega$ as $\omega$ linearly independent vectors in $\mathbb{R}^d$. The lattice $\mathcal{L} \subset \mathbb{R}^d$ spanned by $\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_\omega\}$ is the set of all integer linear combinations of these vectors, that is,

$$ \mathcal{L} = \mathbb{Z}\mathbf{v}_1 + \mathbb{Z}\mathbf{v}_2 + \dots + \mathbb{Z}\mathbf{v}_\omega. $$

The set $\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_\omega\}$ is called a basis of the lattice $\mathcal{L}$. The positive integers $d$ and $\omega$ are referred to as the dimension and rank of the lattice $\mathcal{L}$, respectively. If $\omega = d$, the lattice $\mathcal{L}$ is said to have full rank.

A lattice $\mathcal{L}$ can be represented by a matrix $\mathcal{B}$, where the rows of $\mathcal{B}$ correspond to the basis vectors $\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_\omega$. The determinant of the lattice $\mathcal{L}$ is defined as

$$ \det(\mathcal{L}) = \sqrt{\det(\mathcal{B}^t \mathcal{B})}, $$

where $\mathcal{B}^t$ denotes the transpose of $\mathcal{B}$. For a full-rank lattice, the determinant simplifies to $\det(\mathcal{L}) = |\det(\mathcal{B})|$.

It is well known that a lattice $\mathcal{L}$ of rank $\omega \ge 2$ admits infinitely many bases, which are all composed of $\omega$ vectors and sharing the same determinant (see [12]). However, finding a basis consisting of short vectors is a computationally difficult problem, especially as the lattice's dimension increases.

In 1982, Lenstra, Lenstra, and Lovász [12] introduced the LLL algorithm, which provides an efficient polynomial-time method for finding a reduced basis with relatively short vectors. The following theorem, adapted from [13], quantifies the properties of a reduced basis produced by the LLL algorithm.

**Theorem 1 ([13]).** Let $\mathcal{L}$ be a lattice spanned by a basis $\{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_\omega\}$. The LLL algorithm computes a reduced basis $\{\mathbf{w}_1, \mathbf{w}_2, \dots, \mathbf{w}_\omega\}$, satisfying

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

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

## 2.5. Coppersmith's Method

Cryptanalysis frequently involves solving polynomial equations. In 1996, Copper- smith [4] introduced a powerful method for efficiently finding small roots of modular
polynomial equations of the form $F(y) \equiv 0 \pmod{N}$, even when the factorization of the modulus $N$ is unavailable. Over time, this approach has been extended to multivariate polynomials expressed as

$$F(y_1, y_2, \dots, y_n) = \sum_{i_1, i_2, \dots, i_n} \gamma_{i_1, i_2, \dots, i_n} y_1^{i_1} y_2^{i_2} \dots y_n^{i_n},$$

where the coefficients $\gamma_{i_1, i_2, \dots, i_n}$ are integers. The Euclidean norm of such a polynomial is defined as

$$\|F(y_1, y_2, \dots, y_n)\| = \sqrt{\sum_{i_1, i_2, \dots, i_n} \gamma_{i_1, i_2, \dots, i_n}^2}.$$

In 1997, Howgrave-Graham [14] enhanced Coppersmith's method, presenting a new approach for identifying small roots. This breakthrough led to a fundamental result that became a cornerstone in the field.

**Theorem 2 ([14]).** Let $F(y_1, y_2, \dots, y_n) \in \mathbb{Z}[y_1, y_2, \dots, y_n]$ be a multivariate polynomial containing at most $\omega$ monomials. For positive integers $e$ and $m$, assume that the following conditions hold:

1. $F(y_1^{(0)}, y_2^{(0)}, \dots, y_n^{(0)}) \equiv 0 \pmod{e^m}$;

2. $\|F(y_1, y_2, y_3, \dots, y_n, y_n)\| < \frac{e^m}{\sqrt{\omega}}$;

3. For each $i = 1, \dots, n$, $|y_i^{(0)}| < Y_i$.

Then, $F(y_1^{(0)}, y_2^{(0)}, \dots, y_n^{(0)}) = 0$ holds over the integers.

When working with systems involving more than two variables, extensions of Coppersmith's method often rely on heuristic techniques. For this work, we make the following assumption [3,15–17].

**Assumption 1.** The polynomials $f_1, f_2, \dots, f_\omega$ derived using the LLL algorithm are algebraically independent.

Under this assumption, the unique solution $(y_1^{(0)}, y_2^{(0)}, \dots, y_n^{(0)})$ satisfying the system of polynomial equations $f_i(y_1, y_2, \dots, y_n) = 0$ for $i = 1, \dots, n$ can be determined using methods such as Gröbner basis computations or resultants.

### 3. Solving the Trivariate Polynomial Equation $x(y^2 + Ay + B) + z \equiv 0 \pmod{e}$

In this section, we present our method to solve the equation $x(y^2 + Ay + B) + z \equiv 0 \pmod{e}$ and present a numerical example to show the details.

#### 3.1. Solving the Equation

**Theorem 3.** Let $N$ and $e$ be two positive integers. Let $R(y) \in \mathbb{Z}[y]$ be a monic polynomial with degree 2. Suppose there exist three integers $x_0, y_0$, and $z_0$ such that $x_0R(y_0) + z_0 \equiv 0 \pmod{e}$, with $e = N^\alpha$, $|x_0| \le N^\beta$, $|y_0| \le N^\gamma$, and $|z_0| \le N^\mu$. Then, one can find $x_0, y_0$, and $z_0$ in polynomial time if $\alpha \ge 2\gamma$ and

$$\beta + \frac{1}{2}\mu < \alpha - \sqrt{2\alpha\gamma}.$$

**Proof.** Write $R(y) = y^2 + Ay + B \in \mathbb{Z}[y]$ and put $h(x, y, z) = xR(y) + z$. We use Coppersmith's method [4] to solve the equation $h(x, y, z) \equiv 0 \pmod{e}$. Let $m \ge 1$ be an integer and $t > 0$ be a parameter to be optimized. Let $w = xy^2 + z$. Then, $h(x, y, z) = H(x, y, w)$, where

$$H(x, y, w) = w + x(Ay + B).$$
Next, consider the polynomial

$$H_{k,e_x,e_y,e_z}(x,y,z,w) = x^{e_x} y^{e_y} z^{e_z} H(x,y,w)^k e^{m-k},$$

where $(k, e_x, e_y, e_z)$ in one of the two disjoint sets

$$\mathcal{A} = \{(k, e_x, e_y, e_z) \mid e_y = 0, 1, k = 0, \dots, m, e_x = 1, \dots, m-k, e_z = m - e_x - k\},$$

$$\mathcal{B} = \{(k, e_x, e_y, e_z) \mid e_y = 0, \dots, \lfloor mt \rfloor, k = \lfloor \frac{1}{t} \rfloor \mid e_y, \dots, m, e_x = 0, e_z = m - k\}.$$

Setting $w_0 = x_0y_0^2 + z_0$, then the former polynomials satisfy

$$H_{k,e_x,e_y,e_z}(x_0,y_0,z_0,w_0) \equiv 0 \pmod{e^m}.$$

To apply Coppersmith's ideas, the starting point is to consider the lattice $\mathcal{L}$ spanned by the matrix whose rows are the coefficient vectors of the polynomials $H_{k,e_x,e_y,e_z}(xX, yY, zZ, wW)$, where $X, Y, Z$, and $W$ are positive integers to be determined later. For $(k, e_x, e_y, e_z) \in \mathcal{A} \cup \mathcal{B}$, we can structure the lattice basis matrix in a left triangular form by arranging the rows according to the tuples $(k, e_x, e_y)$ in lexicographical order. Specifically, we say that $(k, e_x, e_y) \prec_{\text{lex}} (k', e'_x, e'_y)$ if $k < k'$, or if $k = k'$ and $e_x < e'_x$, or if $k = k'$, $e_x = e'_x$ and $e_y < e'_y$. Similarly, we order the monomials $x^{e_x}y^{e_y}z^{e_z}w^k$ that correspond to the columns of the matrix. Table 1 presents a typical example with $m = 2$ and $t = 1$. The star entries are nonzero terms which do not contribute to the determinant.

<table><caption>**Table 1.** The lattice basis matrix for $(m, t) = (2, 1)$, where a $\star$ represents a nonzero entry.</caption><thead><tr><th>H<sub>k,e<sub>x</sub>e<sub>y</sub>e<sub>z</sub></sub></th><th>z<sup>2</sup></th><th>xz</th><th>xyz</th><th>x<sup>2</sup></th><th>x<sup>2</sup>y</th><th>zw</th><th>yzw</th><th>xw</th><th>xyw</th><th>w<sup>2</sup></th><th>yw<sup>2</sup></th><th>y<sup>2</sup>w<sup>2</sup></th></tr></thead><tbody><tr><td>H<sub>0,0,0,2</sub></td><td>e<sup>2</sup>Z<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>H<sub>0,1,0,1</sub></td><td>0</td><td>e<sup>2</sup>XZ</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>H<sub>0,1,1,1</sub></td><td>0</td><td>0</td><td>e<sup>2</sup>XYZ</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>H<sub>0,2,0,0</sub></td><td>0</td><td>0</td><td>0</td><td>e<sup>2</sup>X<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>H<sub>0,2,1,0</sub></td><td>0</td><td>0</td><td>0</td><td>0</td><td>e<sup>2</sup>X<sup>2</sup>Y</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>H<sub>1,0,0,1</sub></td><td>0</td><td>★</td><td>★</td><td>0</td><td>0</td><td>eZW</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>H<sub>1,0,1,1</sub></td><td>★</td><td>0</td><td>★</td><td>0</td><td>0</td><td>★</td><td>eYZW</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>H<sub>1,1,0,0</sub></td><td>0</td><td>0</td><td>0</td><td>★</td><td>★</td><td>0</td><td>0</td><td>eXW</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>H<sub>1,1,1,0</sub></td><td>0</td><td>★</td><td>0</td><td>0</td><td>★</td><td>0</td><td>0</td><td>★</td><td>eXYW</td><td>0</td><td>0</td><td>0</td></tr><tr><td>H<sub>2,0,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>W<sup>2</sup></td><td>0</td><td>0</td></tr><tr><td>H<sub>2,0,1,0</sub></td><td>0</td><td>★</td><td>★</td><td>0</td><td>★</td><td>0</td><td>★</td><td>★</td><td>★</td><td>★</td><td>YW<sup>2</sup></td><td>0</td></tr><tr><td>H<sub>2,0,2,0</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>Y<sup>2</sup>W<sup>2</sup></td></tr></tbody></table>

Since the matrix of the lattice is triangular, then its determinant is of the form

$$\det(\mathcal{L}) = X^{\tilde{\xi}_X} Y^{\tilde{\xi}_Y} Z^{\tilde{\xi}_Z} W^{\tilde{\xi}_W} e^{\tilde{\xi}_e}. \qquad (2)$$

To compute the former exponents, we need to define the function $s \mapsto \sigma(s)$ defined by

$$\sigma(s) = \sum_{e_y=0}^{1} \sum_{k=0}^{m} \sum_{e_x=1}^{m-k} s + \sum_{e_y=0}^{\lfloor mt \rfloor} \sum_{k=\lfloor \frac{1}{t} \rfloor}^{m} \sum_{e_y}^{0} s.$$

To simplify the computations, we approximate $\lfloor mt \rfloor \approx mt$ and $\lfloor \frac{1}{t} \rfloor \approx \frac{1}{t}$. Then, the dominant parts of the former parameters, as well as of the dimension $\omega$ of the lattice, satisfy
$$
\begin{align*}
\xi_X &= \sigma(e_X) = \frac{1}{3}m^3 + o(m^3) \\
\xi_Y &= \sigma(e_Y) = \frac{1}{6}t^2m^3 + o(m^3) \\
\xi_Z &= \sigma(m - e_X - k) = \frac{1}{6}(t+2)m^3 + o(m^3) \tag{3} \\
\xi_W &= \sigma(k) = \frac{1}{3}(t+1)m^3 + o(m^3) \\
\xi_e &= \sigma(m-k) = \frac{1}{6}(t+4)m^3 + o(m^3) \\
\omega &= \sigma(1) = \frac{1}{2}(t+2)m^2 + o(m^2).
\end{align*}
$$

Let $e = N^\alpha$, $|x_0| \le N^\beta$, $|y_0| \le N^\gamma$, and $|z_0| \le N^\mu$. To obtain a bound of $w_0$, we suppose $|z_0| < |x_0|y_0^2$ so that $|w_0| = |x_0y_0^2 + z_0| < 2|x_0|y_0^2$. Hence, the bounds X, Y, Z, and W can be defined in terms of N as follows:

$$
|x_0| \le X = N^\beta, \quad |y_0| \le Y = N^\gamma, \quad |z_0| \le Z = N^\mu, \quad |w_0| < W = 2N^{\beta+2\gamma}. \quad (4)
$$

Next, we combine Theorem 2 and Theorem 1 with $i = 4$ by setting

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

In addition to (2), this gives

$$
e^{\xi_e - m(\omega - 3)} X \xi_X Y \xi_Y Z \xi_Z W \xi_W < 2^{-\frac{\omega(\omega-1)}{4}} \omega^{-\frac{\omega-3}{2}}. \quad (5)
$$

Substituting $X = N^\beta$, $Y = N^\gamma$, $Z = N^\mu$, $W = 2N^{\beta+r\gamma}$, and $e = N^\alpha$, the former inequality
can be simplified as

$$
\gamma t^2 + (4\gamma - 2\alpha + 2\beta + \mu)t + 4\gamma - 2\alpha + 4\beta + 2\mu < -\epsilon, \quad (6)
$$

where $\epsilon$ is a small positive constant related to $m$ and $N$. The optimal value for $t$ is
$t_0 = \frac{2\alpha - 2\beta - 4\gamma - \mu}{2\gamma}$. To satisfy $t_0 \ge 0$, the following parameters should hold:

$$
\alpha \ge \beta + 2\gamma + \frac{1}{2}\mu. \tag{7}
$$

The former inequality implies that $\alpha \ge 2\gamma$. Plugging $t_0$ in (6), we get

$$
-2\beta^2 + 2(2\alpha - \mu)\beta + 4\alpha\gamma - 2\alpha^2 + 2\alpha\mu - \frac{1}{2}\mu^2 < -\epsilon_2,
$$

for a small $\epsilon_2 > 0$. Solving the inequality for $\beta$, we get

$$
\beta + \frac{1}{2}\mu < \alpha - \sqrt{2\alpha\gamma}.
$$

Combining with (7), we get for $\alpha \ge 2\gamma$ that

$$
\beta + \frac{1}{2}\mu < \min\left(\alpha - \sqrt{2\alpha\gamma}, \alpha - 2\gamma\right) = \alpha - \sqrt{2\alpha\gamma}.
$$

By utilizing four reduced, algebraically independent polynomials $f_1(x, y, z, w)$, $f_2(x, y, z, w)$,
$f_3(x, y, z, w)$, and $f_4(x, y, z, w)$, one can determine the values of $(x, y, z, w)$ by solving the
system of equations $f_i(x, y, z, w) = 0$ over the integers. This can be achieved through the application of Gröbner basis methods or resultant techniques, thereby completing the proof. □

## 3.2. A Numerical Example

Consider the following parameters:

$$N = 2635819154519362642659647391448070624651311688183462920698769,$$

$$A = 288413866445919312540060749549882831925138520643501991055090,$$

$$B = 8318255835828458190632643460128245929395808370538368180671214\backslash 794571788522608753534458460815328697439209903199865441742833,$$

$$e = 7229977954052138524685255760410197558319269011060224222175946\backslash 238982678044782565876339409047548555673030291683414635524257.$$

imply that $e = N^\alpha$, with $\alpha \approx 2$.

The goal here is to find a small solution $(x_0, y_0, z_0)$ of the equation $x(y^2 + Ay + B) + z \equiv 0 \pmod{e}$, with $z_0 = 1$. To apply Theorem 3, we set $\beta = 0.4$, $\gamma = 0.51$, and $\mu = 0$. Hence, the conditions of Theorem 3 are satisfied, namely, $\alpha \ge 2\gamma$ and $\beta + \frac{1}{2}\mu < \alpha - \sqrt{2\alpha\gamma} \approx 0.571$. Together with the bound $Z = 1$, we take

$$X \approx \lfloor N^\beta \rfloor = 1527588761761190743375872,$$

$$Y \approx \lfloor N^\gamma \rfloor = 6832949794180177482773906325504,$$

$$W \approx 2XY^2 = 50785084508005144657742888380047856602690371809450716988\backslash 0416349290534591020103683276800.$$

Let $(m, t) = (3, 2)$. The lattice $\mathcal{L}$ is built by the coefficients of the polynomials

$$H_{k,e_x,e_y,e_z}(x,y,z,w) = x^{e_x}y^{e_y}z^{e_z}H(x,y,w)^k e^{m-k},$$

where $(k, e_x, e_y, e_z)$ in one of the two disjoint sets

$$\mathcal{A} = \{(k, e_x, e_y, e_z) \mid e_y = 0, 1, k = 0, \dots, m, e_x = 1, \dots, m-k, e_z = m - e_x - k\},$$

$$\mathcal{B} = \{(k, e_x, e_y, e_z) \mid e_y = 0, \dots, \lfloor mt \rfloor, k = \lfloor \frac{1}{t} \rfloor e_y, \dots, m, e_x = 0, e_z = m - k\},$$

and each term $xy^2$ is replaced by $w-z$. The lattice has dimension $\omega = 40$. Applying the LLL algorithm to the lattice $\mathcal{L}$ yields a reduced matrix, from which we derive 40 polynomials. A computation of the Gröbner basis then provides the solution

$$x_0 = 775498829232538581123082,$$

$$y_0 = 3487384624245570654520525920690,$$

$$w_0 = 943150161306261052140984582339690768969934167219917544953518167111\backslash 1521807051406540201.$$

Both the LLL algorithm and Gröbner basis method took less than one second. Notice that $\alpha \ge \beta + 3\gamma = 1.93$, and then the bound of Feng et al. [10] is $\min(\frac{2}{3}\alpha - \frac{3}{2}\gamma, \alpha - 3\gamma) \approx 0.469$, which is lower than our bound $\alpha - \sqrt{2\alpha\gamma} \approx 0.571$.
## 4. Comparison with the Method of Feng et al. [10]

In 2024, Feng et al. [10] solved the modular equation $x(y^2 + Ay + B) + 1 \equiv 0 \pmod{e}$. They showed that if $|x| \le N^\beta$ and $|y| \le N^\gamma$, then one can find $x$ and $y$ if

$$ \beta < \begin{cases} \alpha - \sqrt{2\gamma\alpha}, & \text{if } \beta + 2\gamma < \alpha < \beta + 3\gamma, \\ \min\left(\frac{2}{3}\alpha - \frac{3}{2}\gamma, \alpha - 3\gamma\right), & \text{if } \alpha \ge \beta + 3\gamma. \end{cases} $$

In our method, we can solve the equation $x(y^2 + Ay + B) + 1 \equiv 0 \pmod{e}$ whenever $\alpha \ge 2\gamma$ and $\beta < \alpha - \sqrt{2\gamma\alpha}$. This shows that the range of $\alpha$ is larger their range. Let us compare the bounds of $\beta$. Denote by $\Delta$ the difference between our bound and their bound.

If $\beta + 2\gamma < \alpha < \beta + 3\gamma$, we can retrieve their bound by setting $\mu = 0$ in Theorem 3. This shows that their method is a special case of ours.

If $\alpha \ge \beta + 3\gamma$, their bound is

$$ \min\left(\frac{2}{3}\alpha - \frac{3}{2}\gamma, \alpha - 3\gamma\right) = \begin{cases} \frac{2}{3}\alpha - \frac{3}{2}\gamma, & \text{if } \alpha \ge \frac{9}{2}\gamma, \\ \alpha - 3\gamma, & \text{if } \alpha < \frac{9}{2}\gamma. \end{cases} $$

For $\alpha \ge \frac{9}{2}\gamma$, a simple calculation yields

$$ \begin{aligned} \Delta &= \left(\alpha - \sqrt{2\gamma\alpha}\right) - \left(\frac{2}{3}\alpha - \frac{3}{2}\gamma\right) \\ &= \frac{(2\alpha - 9\gamma)^2}{2\alpha + 9\gamma + 6\sqrt{2\gamma\alpha}} \ge 0, \end{aligned} $$

which shows that our bound is better than their bound.

For $\alpha < \frac{9}{2}\gamma$, a straightforward computation gives

$$ \begin{aligned} \Delta &= \left(\alpha - \sqrt{2\gamma\alpha}\right) - (\alpha - 3\gamma) \\ &= \frac{\gamma(9\gamma - 2\alpha)}{3\gamma + \sqrt{2\gamma\alpha}} > 0, \end{aligned} $$

which shows again that our bound is better than theirs.

## 5. Application of the New Method

In this section, we apply Theorem 3 to break RSA variants with a key equation of the form $ev - x\psi(N) = z$.

**Theorem 4.** Let $(N, e)$ be an RSA public key with $N = pq$, $q < p < 2q$, and $e = N^\alpha$. Suppose there are three integers $v_0, x_0$, and $z_0$ such that $|z_0| \le N^\mu$, $|v_0| \le N^\zeta$ and $ev_0 - x_0\psi(N) = z_0$. If $p_0$ is a known approximation of $p$ such that $|p - p_0| = N^\gamma$, with $0 \le \gamma \le \frac{1}{2}$, $2\gamma \le \alpha \le \frac{2}{\gamma}$, and $\zeta + \frac{1}{2}\mu < 2 - \sqrt{2\alpha\gamma}$, then the modulus $N$ can be factored in polynomial time.

**Proof.** Let $p_0$ be an approximation of $p$ such that $|p - p_0| = N^\gamma$. According to Lemma 2, the integer $q_0 = \lfloor \frac{N}{p_0} \rfloor$ is an approximation of $q$ such that

$$ |q - q_0| < N^\gamma, \quad |p + q - p_0 - q_0| < 2N^\gamma. $$
If $N = pq$, then the equation $ev_0 - x_0\psi(N) = z_0$ can be rewritten as a modular one, namely, $x_0(y_0^2 + Ay_0 + B) + z_0 \equiv 0 \pmod{e}$, where $y_0 = p+q-p_0-q_0$, $A = N+2(p_0+q_0)+1$, and

$$B = N^2 + (p_0 + q_0 - 1)N + (p_0 + q_0)^2 + p_0 + q_0 + 1.$$

On the other hand, using $\psi(N) > N^2$, and assuming that $|z_0| < ev_0$, we get

$$x_0 = \frac{ev_0 - z_0}{\psi(N)} < \frac{2ev_0}{N^2} \le 2N^{\alpha+\zeta-2} = X.$$

Also, we have $|y_0| < 2N^\gamma = Y$. To apply Theorem 3, we need a bound for $w_0 = x_0y_0^2 + z_0$. We assume $|z_0| < x_0y_0^2$ so that $|w| < 2XY^2 = W$. Then, by applying Theorem 3 for $\beta = \alpha + \zeta - 2$ and $\gamma$, the inequality $\beta + \frac{1}{2}\mu < \alpha - \sqrt{2\alpha\gamma}$ leads to $\zeta + \frac{1}{2}\mu < 2 - \sqrt{2\alpha\gamma}$, and the conditions $\alpha \ge 2\gamma$, $0 \le \zeta < 2 - \sqrt{2\alpha\gamma}$ turn to $2\gamma \le \alpha \le \frac{2}{\gamma}$. After finding the root $(x_0, y_0, z_0, w_0)$ and using the values of $N = pq$ and $y_0 + p_0 + q_0 = p+q$, we get $p$ and $q$. This concludes the proof. $\square$

# 6. Comparison with the Former Attacks

In this section, we compare our attack with the former attacks in terms of the bounds.

## 6.1. Comparison with the Attack of Zheng et al. [17]

In [17], Zheng et al. proposed an attack targeting the RSA variant introduced by Murru and Saettone [5], which is based on the key equation $ed - k\psi(N) = 1$. They showed that the system is vulnerable when $e = N^\alpha$, $d = N^\delta$, and $\delta < 2 - \sqrt{\alpha}$. This represents the optimal bound for small private exponent attacks on this scheme.

Let $\Delta$ denote the difference between the bound established in Theorem 4, and then we have $2 - \sqrt{\alpha}$. Then,

$$\Delta = 2 - \sqrt{2\alpha\gamma} - (2 - \sqrt{\alpha}) = \sqrt{\alpha}(1 - \sqrt{2\gamma}).$$

By fixing $\gamma < 0.5$, it follows that $\Delta > 0$, confirming that our bound is always better than theirs.

## 6.2. Comparison with the Attack of Feng et al. [10]

In [10], Feng et al. proposed an attack on the cryptographic scheme introduced by Murru and Saettone [5], refining the earlier results of Zheng et al. [17]. They demonstrated that for $N = pq$, $e = N^\alpha$, $d < N^\delta$, and $|p - p_0| = N^\gamma$, where $p_0$ is an approximation of $p$, and the scheme becomes vulnerable if $\delta < 2 - \sqrt{2\alpha\gamma}$. Notably, this bound can be obtained by setting $\mu = 0$ in Theorem 4, indicating that Feng et al.'s method is a specific instance of the more general framework presented in our approach.

On the one hand, the number of exponents $e$ of size $N^\alpha$ that are vulnerable to this attack can be approximated by

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

where $\epsilon$ is a small positive value that reflects the exponents that are not coprime with $\psi(N)$.

On the other hand, the number of weak exponents $e$ of size $N^\alpha$ relative to our attack is given by

$$W = \#\{(v_0, z_0) \mid |v_0| \le N^\zeta, |z_0| \le N^\mu, \zeta + \frac{1}{2}\mu < 2 - \sqrt{2\gamma\alpha}, \gcd(v_0, \psi(N)) = 1\}.$$
This implies that

$$W \le \# \left\{ (v_0, z_0) \mid |v_0| \le N^{\zeta}, |z_0| \le N^{\mu}, |v_0| \sqrt{|z_0|} < N^{2-\sqrt{2\gamma\alpha}}, \text{gcd}(v_0, \psi(N)) = 1 \right\}.$$

Let $b = 2 - \sqrt{2\gamma\alpha}$. Then, $1 \le |z_0| < \frac{N^{2b}}{|v_0|^2}$, with $1 \le |v_0| < N^b$. The upper bound for this count is obtained by summing the number of possible values of $|z_0|$ in the interval $[1, \frac{N^{2b}}{|v_0|^2}]$ for each $v_0$ such that $1 \le |v_0| < N^b$. This gives

$$W \le 4 \sum_{v_0=1}^{N^b} \sum_{z_0=1}^{\frac{N^{2b}}{|v_0|^2}} 1 = 4 \sum_{v_0=1}^{N^b} \frac{N^{2b}}{|v_0|^2} = 4N^{2b} \sum_{v_0=1}^{N^b} \frac{1}{|v_0|^2} \le \frac{2\pi^2}{3} N^{2b},$$

where we used the known result $\sum_{s=1}^{+\infty} \frac{1}{s^2} = \frac{\pi^2}{6}$. Consequently,

$$W = O\left(N^{2\left(2-\sqrt{2\gamma\alpha}\right)}\right),$$

where $\epsilon$ is a small positive constant accounting for the integers $v_0$ that are not coprime with $\psi(N)$. This bound is significantly larger than the number of exponents $e$ of size $N^\alpha$ that are vulnerable to the attack proposed by Feng et al. [10].

## 7. Experimental Results

In this section, we verify the validity of our proposed attacks. The experiments were carried out employing the HPC-MARWAN cluster [18] using SageMath software (version 10.0). HPC-MARWAN is a cluster dedicated to scientific research, providing computational power and storage capacity, deployed by the National Center for Scientific and Technical Research (CNRST) in Morocco.

We showcase the effectiveness of our method in breaking the RSA variant. We also highlight that our attack retains its efficacy even when both the public exponent $e$ and the private exponent $d$ are approximately of size $N^2$, which is a scenario in which existing attacks fail to be effective.

### 7.1. A Detailed Example for Theorem 4 with the Equation $ev - x(y^2 + Ay + B) = z$

Here are the following public values to consider: $N \approx 2^{512}$ and $e \approx 2^{1022}$. Furthermore, we have

$$N = 92090123703993789630510505576230736645889095247500414117819966585 \\ 56971851097330338536685771902273569360378931731016906043849221198 \\ 198036935744123832820589,$

$$e = 38934215691607950469120012361006013254362521225220257539170479082 \\ 12083936845833181184061443322817097190960300942509047121150184684 \\ 05032721615209801105248073935917468358425919934056305719304476900 \\ 13326171658830108432349387168622831806240456963423109366659468641 \\ 767246402078467795775932869025626858492401033951,$

$$p_0 = 11579208923731619542357098500868790785326998466564056403945758400 \\ 7913129619533.$$
This yields $e = N^{\alpha}$, with $\alpha \approx 1.9978$. Additionally, $q_0 = \lfloor \frac{N}{p_0} \rfloor$ provides an approximation of $q$, where

$$q_0 = 795305830567188711157306392157135729480301169187366271932474635603\ \text{00498156651.}$$

The objective is to find a small solution $(x_0, y_0, z_0)$ to the equation

$$x(y^2 + Ay + B) + z \equiv 0 \pmod{\psi(N)},$$

where the coefficients $A$ and $B$ are given by

$$A = N + 2(p_0 + q_0) + 1,$$ $$B = N^2 + (p_0 + q_0 - 1)N + (p_0 + q_0)^2 + p_0 + q_0 + 1.$$

Specifically, we have

$$A = 920901237039937896305105055762307366458890952475004141178199\ 665855697185109772098388127384203535217260882773469261950624\ 7017975580663447030880551088372958,$$

$$B = 848059088381687885222692986094202987557717535259737888174631\ 414964151825948608250261552605339973955837573041297651395427\ 901782819579679100678550541876230524170482254615158647078480\ 961854145040641977050073093968898196703731531353503540263696\ 969306755617743680388039859455084301800191045010714420214587\ 73916749.$$

To apply the method outlined in Theorem 4, we assume the following conditions $|v_0| \le N^{\zeta}$, $|z_0| \le N^{\mu}$, and $|p - p_0| \approx N^{\gamma}$, where $\zeta = 0.4$, $\mu = 0.3899$, and $\gamma = 0.49179$. It is important to note that these conditions satisfy the requirements of Theorem 4, specifically

$$\begin{cases} 2\gamma \approx 0.983 < \alpha < \frac{2}{\gamma} \approx 4.066, \\ \zeta + \frac{1}{2}\mu \approx 0.594 < 2 - \sqrt{2\alpha\gamma} \approx 0.598. \end{cases}$$

This establishes the bounds

$$X \approx \lfloor 2N^{\alpha+\zeta-2} \rfloor = 35317824933741584086703883528303714266057154312907285\ 271150592,$$

$$Y \approx \lfloor 2N^{\gamma} \rfloor = 104493754698738524355519630920748673797643265656422206730\ 78934100159252922368,$$

$$Z \approx \lfloor N^{\mu} \rfloor = 1073116001210012283097441801606665179596152191451837623173\ 120,$$

$$W = 2XY^2 \approx 7712667597695774572677877060455265161976005042632523391603\ 081758469953781216418569262422889415953648852041303652656380831526898\ 381818448408398069785728319647442138981910138399151181599383434359979\ 090634271952470016.$$
Setting $m = 4$ and $t = 2$, we construct a lattice $\mathcal{L}$ of dimension $\omega = 65$ using the previous methodology. By applying the LLL algorithm, we obtain a reduced matrix from which we derive 65 polynomials. Utilizing the Gröbner basis method, we then select the first four polynomials and solve them over the integers. This process yields the following solution

$$
\begin{align*}
x_0 &= 476922631141216258824709909224364166021406637821749589143304, \\
y_0 &= -14656198973036963042431218136491400396244274845042329427279636 \\
    &\qquad \setminus 15709918784714, \\
z_0 &= 996433282843842715907804162488388224532595860353406044735637, \\
w_0 &= 1024449691435018776340137001955759656771048969519650439490082783 \\
    &\qquad \setminus 2638023125347661454319655031429861706474386683637844031231494225 \\
    &\qquad \setminus 2383581431101959647815237784662331111283958734677149072166350844 \\
    &\qquad \setminus 5598874271464349621.
\end{align*}
$$

Consequently, $v_0$ can be computed using

$$
\begin{align*}
v_0 &= \frac{x_0(y_0^2 + Ay_0 + B) + z_0}{e}, \\
    &= 1038825528162352588568000862000004781199865632503791922107619.
\end{align*}
$$

Note that the conditions $|z_0| < ev_0$ and $|z_0| < x_0y_0^2$ are satisfied, as stipulated in Theorem 4. The LLL algorithm and the Gröbner basis method were executed in less than nine seconds. Using $N = pq$ and $y_0 + p_0 + q_0 = p + q$, we obtain

$$
\begin{align*}
p &= 110571356571418192257697953498072866373701107402166325725750051578 \\
  &\qquad \setminus 456079806541, \\
q &= 832856958253131779773605489126794743879745666977066325642270323740 \\
  &\qquad \setminus 47629184929.
\end{align*}
$$

Observe that $e$ is of the form

$$e \equiv \frac{z_0}{v_0} (\mod \psi(N)).$$

Then, we can compute $d \equiv \frac{1}{e} (\mod \psi(N))$, and obtain

$$
\begin{align*}
d &= 1655976650302073678969564407000807245248647342975144716132433455575 \\
  &\qquad \setminus 6230549465308393591474500785245363456869535980499891838145913408081 \\
  &\qquad \setminus 2794424287762914612538408390381867384695524863158843802553880691450 \\
  &\qquad \setminus 9112178358072157830766955945445112918958250946247537278292973203123 \\
  &\qquad \setminus 5295228023136388116354527659154529687250.
\end{align*}
$$

Hence $d = N^\delta$ with $\delta \approx 1.995$.

Notice that the condition established by Feng [10] for breaking the system is given by $\delta < 2 - \sqrt{2\gamma\alpha}$, which represents the optimal bound for partial prime exposure attacks. In this numerical example, we find that $2 - \sqrt{2\gamma\alpha} \approx 0.598 < \delta$. This shows that their method cannot be broken the system in this particular instance.
Similarly, the optimal bound for small private exponent attacks is given by $\delta < 2 - \sqrt{\alpha}$, as presented by Zheng et al. [17]. In our example, we find that $2 - \sqrt{\alpha} \approx 0.586 < \delta$. This indicates that their method is insufficient to break the system in this instance.

## 7.2. Experiments for Theorem 4 for Large Public Keys

We implement the method outlined in Theorem 4 using large values for the public key $(N, e)$. Through a series of experiments, we solve the equation $ev - xR(y) = z$, where

$$R(y) = y^2 + (N + 2(p_0 + q_0) + 1)y + N^2 + (p_0 + q_0 - 1)N + (p_0 + q_0)^2 + p_0 + q_0 + 1.$$

This approach allows us to factor the modulus $N = pq$ efficiently when the most significant bits of $p$ are known. The experiments are summarized in Table 2 where the parameters in each column are defined as follows.

* $nb(x)$ stands for the number of bits of $x$.

* $\zeta$ is a parameter satisfies $|v| \le N^\zeta$.

* $\delta$ is the parameter for which $d = N^\delta$.

* $\alpha$ is defined by $e = N^\alpha$.

* $\mu$ is a parameter such that $|z| \le N^\mu$.

* $\gamma$ is the parameter defined by $\gamma = \frac{\log(|p-p_0|)}{\log(N)}$.

* $nbk(p)$ stands for the number of known bits of $p$.

* $m$ and $t$ are parameters for constructing the lattice $\mathcal{L}$ with dimension $\omega$.

* Time is specified for the time in seconds required to perform both the LLL algorithm and the Gröbner basis method.

Table 2 presents our experimental results when the most significant bits of the prime factor $p$ of $N = pq$ are known. These results are related to the method of Theorem 4.

<table><caption>**Table 2.** Experimental results by exposing the most significant bits of $p$.</caption><thead><tr><th>nb (N)</th><th>nb (e)</th><th>ζ</th><th>δ</th><th>α</th><th>μ</th><th>γ</th><th>nbk (p)</th><th>m</th><th>t</th><th>ω</th><th>Time (s)</th></tr></thead><tbody><tr><td>700</td><td>1399</td><td>0.35657</td><td>2.000</td><td>1.9993</td><td>0.390</td><td>0.49676</td><td>50</td><td>4</td><td>2</td><td>65</td><td>13.48</td></tr><tr><td>800</td><td>1598</td><td>0.36285</td><td>1.994</td><td>1.9996</td><td>0.390</td><td>0.49710</td><td>88</td><td>4</td><td>2</td><td>65</td><td>16.59</td></tr><tr><td>899</td><td>1798</td><td>0.37716</td><td>1.999</td><td>1.9991</td><td>0.390</td><td>0.49734</td><td>138</td><td>4</td><td>2</td><td>65</td><td>18.47</td></tr><tr><td>1000</td><td>1999</td><td>0.36942</td><td>1.998</td><td>1.9988</td><td>0.390</td><td>0.49558</td><td>250</td><td>4</td><td>2</td><td>65</td><td>22.04</td></tr><tr><td>1299</td><td>2598</td><td>0.34597</td><td>2.000</td><td>2.0000</td><td>0.390</td><td>0.49879</td><td>177</td><td>4</td><td>2</td><td>65</td><td>35.99</td></tr><tr><td>1499</td><td>2996</td><td>0.37337</td><td>1.999</td><td>1.9992</td><td>0.390</td><td>0.49986</td><td>250</td><td>4</td><td>2</td><td>65</td><td>42.20</td></tr><tr><td>1999</td><td>3997</td><td>0.34999</td><td>1.999</td><td>1.9993</td><td>0.390</td><td>0.49904</td><td>270</td><td>3</td><td>3</td><td>52</td><td>09.06</td></tr><tr><td>2499</td><td>4997</td><td>0.36788</td><td>2.000</td><td>1.9997</td><td>0.390</td><td>0.49948</td><td>282</td><td>3</td><td>3</td><td>52</td><td>12.59</td></tr><tr><td>3000</td><td>5999</td><td>0.36650</td><td>2.000</td><td>1.9998</td><td>0.390</td><td>0.49895</td><td>532</td><td>3</td><td>3</td><td>52</td><td>17.37</td></tr></tbody></table>

# 8. Conclusions

In this paper, we introduced a novel approach for solving the generalized equation $ev - x(y^2 + Ay + B) = z$, where $x$, $y$, and $z$ are small unknown integers, and $A, B \in \mathbb{Z}$. Our method builds upon Coppersmith's technique and leverages lattice basis reduction. Furthermore, we applied this approach to the cryptanalysis of the RSA variants based on the cubic Pell equation, represented as $eu - x(p^2 + p + 1)(q^2 + q + 1) = z$. Notably, our technique enabled the factorization of the RSA modulus $N = pq$ in polynomial time. This research demonstrates that our attack improves upon previous methods such as the method of Feng et al. [10] and the method of Zheng et al. [17], targeting small private exponent attacks and partial prime exposure attacks.
**Author Contributions:** Conceptualization, M.R., A.T. and A.N.; methodology, M.R., A.T. and A.N.; software, M.R.; validation, M.R., A.T., 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. and A.N.; writing—review and editing, M.R., A.T. and A.N.; visualization, M.R., A.T. and A.N.; supervision, M.R., A.N. and M.Z.; project administration, M.R., A.N., A.T. 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:** Data sharing is not applicable

**Acknowledgments:** This work utilized the computational resources of HPC-MARWAN, made available by the National Center for Scientific and Technical Research (CNRST) in Rabat, Morocco.

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

## Abbreviations

The following abbreviations are used in this manuscript:

RSA Rivest, Shamir, Adleman

LLL Lenstra, Lenstra, and Lovász

CNRST Centre National de la Recherche Scientifique et Technique

$\varphi(N)$ Euler's totient function $\varphi(N) = (p-1)(q-1)$

$\psi(N)$ cubic totient function $\psi(N) = (p^2 + p + 1)(q^2 + q + 1)$

## References

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

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

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

4. Coppersmith, D. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. **1997**, 10, 233–260. [CrossRef]

5. Murru, N.; Saettone, F.M. A Novel RSA-Like Cryptosystem Based on a Generalization of the Rédei Rational Functions. In *Number-Theoretic Methods in Cryptology*; Kaczorowski, J., Pieprzyk, J., Pomykala, J., Eds.; NuTMiC 2017; Lecture Notes in Computer Science; Springer: Cham, Switzerland, 2018; Volume 10737, pp. 91–103.

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

7. 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, ICCS 2002, Singapore, 28 November 2002; IEEE: Piscataway, NJ, USA, 2002; Volume 1, pp. 91–95.

8. 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.

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

10. Feng, Y.; Nitaj, A.; Pan, Y. Partial prime factor exposure attacks on some RSA variants. Theor. Comput. Sci. **2024**, 999, 114549. [CrossRef]

11. Nitaj, A. Another generalization of Wiener’s attack on RSA. In *Africacrypt 2008*; Vaudenay, S., Ed.; LNCS; Springer: Berlin/Heidelberg, Germany, 2008; Volume 5023, pp. 174–190.

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

13. May, A. New RSA Vulnerabilities Using Lattice Reduction Methods. PhD Thesis, University of Paderborn, Paderborn, Germany, 2003.

14. Howgrave-Graham, N. Finding small roots of univariate modular equations revisited. In Proceedings of the IMA International Conference on Cryptography and Coding, Cirencester, UK, 17–19 December 1997; LNCS; Springer: Berlin/Heidelberg, Germany, 1997; Volume 1355, pp. 131–142.

15. Jochemsz, E.; May, A. A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants. In Proceedings of the ASIACRYPT 2006, Shanghai, China, 3–7 December 2006; LNCS; Springer: Berlin/Heidelberg, Germany, 2006; Volume 4284, pp. 267–282.
16. Peng, L.; Hu, L.; Lu, Y.; Wei, H. An improved analysis on three variants of the RSA cryptosystem. In Proceedings of the International Conference on Information Security and Cryptology, Beijing, China, 4–6 November 2016; Springer: Berlin/Heidelberg, Germany, 2016; Volume 10143, pp. 140–149.

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

18. HPC-MARWAN, National Center for Scientific and Technical Research (CNRST), Rabat, Morocco. Available Online: http://hpc.marwan.ma/index.php/en/ (accessed on 5 May 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.