Concurrent factorization of RSA moduli via weak key equations

1.   Introduction

Information technology is the cornerstone of contemporary society, permeating nearly every facet of daily life. The rapid expansion of today's technological landscape generates an ever-increasing volume of data. As this digital universe expands, the imperative to safeguard and preserve data privacy intensifies, a concern shared by individuals and organizations alike. Security has long been a paramount issue within the realm of computing, particularly concerning the secure transmission of information and data across the Internet. Across various channels, whether via the Internet or through smart devices, reports of data thefts and breaches have shown a consistent upward trend ^[1]. In response to these challenges, researchers and cryptographers endeavour to innovate novel cryptographic models and enhance existing cryptographic algorithms. These advancements are geared toward practical implementation in real-world applications, aiming to enhance user privacy, fortify data security, strengthen authentication mechanisms, and address many related features ^[2].

In the domain of cryptographic algorithms, the RSA public key cryptographic algorithm stands out as one of the earliest and most widely adopted. Known as the RSA cryptosystem, it takes its name from its creators: Ron Rivest, Adi Shamir, and Leonard Adleman, who introduced RSA in their seminal 1977 paper ^[3]. Contemporary applications of the traditional RSA algorithm encompass key exchanges, digital signatures, and secure communication protocols employed in web browsers, chat applications, email services, VPNs, and other methods necessitating secure data transmission between entities. Initially, a fundamental aspect of the RSA cryptosystem involves multiplying two random prime numbers, denoted as $p$ and $q$, resulting in the RSA modulus, represented by $N$. Selecting $p$ and $q$ must adhere to the constraint $q < p < 2q$ to prevent factorization using general factoring techniques. Subsequently, the Euler's totient function for $N$, denoted as $\phi(N)$, is computed as $(p-1)(q-1)$. Once $\phi(N)$ is determined, an integer $e$ less than $\phi(N)$ is chosen. The private key component, $d$, is computed such that $ed \equiv 1 \pmod{\phi(N)}$. Next, the pair $(N, e)$ is made publicly available for any encryptor, and the pair $(d, N)$ is only available for the decryptor, with $p$, $q$, and $\phi(N)$ remaining as secret parameters.

RSA's strength is primarily based on the significant challenge of addressing the integer factorization problem (IFP) for a large integer $N$ and the challenge of resolving the $e^{th}$ root problem. While RSA is generally considered secure, several attacks have been designed to exploit the structure of its key equation. The quadratic sieve (QS) is an efficient algorithm for factoring $N$, functioning in sub-exponential time due to the use of large $n$-bit primes for RSA primes $p$ and $q$ ^[4]. Regarding algorithmic efficiency, the general number field sieve (GNFS) is also highly effective within sub-exponential time, typically with $n$ set to 1024 bits ^[5]. Note that QS is favored for its simplicity over GNFS and is the fastest method for factoring integers below 100 decimal digits. However, for integers in the 110 to 120 digits range, GNFS outperforms QS.

In 2013, the government digital IDs agenda with RSA keys of Taiwanese citizens was signed by certificate authorities (CAs) and kept in the Citizen Digital Certificates (CDCs) database. As reported in ^[6], an attack successfully obtained the prime factors of 184 distinct RSA keys of 1024-bit size, revealing significant susceptibility in the RSA keys and emphasizing the need for robust cryptographic practices. Similarly, in 2017, ^[7] identified vulnerabilities in both Belgium's e-ID cards and Estonia's digital identity cards, compromising millions of RSA keys. This attack allowed the private key to be derived from the public key, contradicting the RSA principle that factoring the primes of the public key should be computationally infeasible. Due to shortcuts in key generation, it has become possible to factorize 1024-bit keys in minutes and 2048-bit keys in weeks. Ongoing research into RSA public key aggregation is crucial to prevent such vulnerabilities. Note that both notorious cryptanalysis incidents used Coppersmith's partial-key-recovery technique.

In the context of related work, it is crucial to consider advancements in other areas of secure communication and computational frameworks. For instance, the study in ^[8] explores using advanced neural network architectures in the Internet of Things (IoT) for police applications. Using memristive systems enhances neural networks' dynamic analysis and performance, which can be crucial for real-time data processing and security in IoT environments. Although this study focuses on a different application area, the underlying principle of improving system robustness and security is highly relevant to our work on RSA vulnerabilities. The techniques developed in memristive neural networks could inspire new approaches to strengthening cryptographic systems. Similarly, ^[9] emphasizes the importance of privacy protection in the Internet of Medical Things (IoMT). By leveraging hyperchaotic behaviour in memristive Hopfield neural networks (HNN), this study addresses the need for secure data transmission and storage in medical applications. This study's emphasis on privacy and data protection parallels our objective of identifying and mitigating vulnerabilities in RSA encryption, ensuring the confidentiality and integrity of sensitive information. Additionally, ^[10] explores the design of complex dynamical systems with hidden and hyperchaotic behaviours. Developing fractional-order systems with multi-scroll attractors highlights the potential for creating intricate and secure communication protocols. The insights gained from analysing these systems can be applied to cryptographic research, particularly in developing new algorithms that resist attacks by leveraging the unpredictable nature of hyperchaotic systems. This aligns with our study's focus on addressing the inherent weaknesses in RSA by exploring new mathematical models and techniques.

Moreover, ^[11] introduces a Fibonacci-like prime sequence for prime numbers, the study showcases the utility of such sequences in predicting orbits within a fractal space. This concept relates to our work because both studies use advanced mathematical techniques to solve complex problems. In our cryptanalysis, the identification of weak RSA key equations and the concurrent factorization of multiple RSA moduli are achieved through sophisticated mathematical approaches such as Diophantine approximation and Coppersmith's lattice-based method. The Fibonacci-like prime sequence offers a novel perspective that could inspire further exploration of mathematical structures in cryptographic applications, potentially leading to new methods for identifying and mitigating vulnerabilities. Thus, integrating advanced mathematical techniques and dynamic system analysis, as seen in the referenced studies, provides valuable insights that can be applied to cryptographic research. Our findings on RSA vulnerabilities contribute to the ongoing efforts to enhance the security of encryption systems, ensuring the protection of sensitive information in various applications, from IoT and IoMT to broader communication frameworks. The practical implications of our study highlight the need for continuous evaluation and improvement of cryptographic protocols to stay ahead of potential adversaries.

1.1.   Our contributions

This cryptanalysis study explores an adversary's ability to access $k$ RSA moduli, $N_i = p_i q_i$, and their public exponents $e_i$. We present two attacks exploiting weak RSA key equations. The study demonstrates the simultaneous factorization of $k$ RSA moduli $(N_i, e_i)$ using a constant $r$ that satisfies $e_i r - (N_i - p_i - q_i + u_i) s_i = t_i$. Our primary finding reveals that weaknesses in RSA public-key pairs can be exploited under certain conditions, allowing an adversary to simultaneously factorize multiple RSA moduli $N_i$. Another vulnerability is identified when RSA parameters satisfy $e_i r_i - s(N_i - p_i - q_i + u_i) = t_i$, allowing concurrent factorization with small, unknown integers $s, r_i, u_i$, and $t_i$. Resolving the factorization of each RSA modulus, $N_i$, using lattice basis reduction enabled the discovery of this vulnerability. Our study demonstrates this new attack and includes a comparative evaluation with existing research, highlighting the novelty and significance of our findings, which extend the comprehension of RSA vulnerabilities and its security measures.

1.2.   Paper organization

The remainder of this paper is organized in the following manner. The essential background information, including foundational theorems on continued fractions, lattice basis reduction, simultaneous Diophantine approximations, and other relevant theorems, is provided in Section 2. Our main work, including the proof of our primary attack and illustrative numerical examples, is presented in Section 3. This is followed by a comparison of our results with previously documented attacks on $k$ RSA moduli instances in Section 4. Finally, the paper concludes with a summary of our findings and key takeaways in Section 5.

2.   Foundational information

First, we introduce an essential tool for solving Diophantine equations. Continued fractions approximate rational and irrational numbers, forming the foundation for constructing the RSA cryptanalysis (and its variants). Continued fractions are defined as follows:

Definition 2.1. Given any positive $\xi \in \mathbb{R}$, start with $\xi_{0} = \xi$. For each $i = 1, 2, \ldots, n$, define $\xi_{i}$ as $\left\lfloor x_i\right\rfloor$ and let $\xi_{i+1} = \frac{1}{\xi_{i} - x_{i}}$ until $\xi_{n} \in \mathbb{Z}$. As a result, $\xi$ can be represented as continued fractions in the following form:

For simplicity, a continued fraction is an expression created by iteratively representing a number as the sum of its integer part and the reciprocal of another number. This process is repeated by writing the new number as the sum of its integer part and another reciprocal, and so on. A finite continued fraction, or terminated continued fraction, stops this iteration after a certain number of steps, using an integer instead of another continued fraction. Conversely, an infinite continued fraction continues indefinitely. In both types, all integers in the sequence, except for the first, must be positive. The integers $x_{i}$ are known as the coefficients or terms of the continued fraction.

The convergents $\frac{x}{y}$ of $\xi$ are fractions denoted by $\frac{x}{y} = [x_0, x_1, \cdots, x_i]$ for $i \geq 0$. Importantly, suppose $\xi = \frac{x}{y}$ is a rational number with $\gcd(x, y) = 1$. In that case, the continued fraction expansion of $\xi$ can be determined using the Euclidean algorithm in $\mathcal{O}(\log (y))$ time.

According to Theorem 2.1 (Legendre's theorem), the unknown integers $m$ and $n$ are guaranteed to be among the list of convergents in the continued fraction expansion of a rational number $\chi$, which satisfies the inequality specified in (2.2).

Theorem 2.1. Consider a rational number $\chi$ and let $m$ and $n$ be positive integers such that gcd$(m, n) = 1$. If the inequality

is satisfied, then $\frac{m}{n}$ is a convergent in the continued fraction expansion of $\chi$.

Proof. Please see ^[12] for the proof.

The primes in the RSA cryptosystem's key generation should be of the same bit size to enhance its security. Allowing uneven factors is a potential security risk because the "small" factor could be easily found. Hence, the notation $q < p < 2q$ indicates that the primes $p, q$ are balanced. Recalled that in Lemma 2.1, we have fixed the lower and upper bounds of the RSA primes of modulus $N$ as follows:

Lemma 2.1. For an RSA modulus $N = pq$ with $p$ and $q$ being primes of equal bit length such that $q < p < 2q$, the following inequality is satisfied:

Proof. Please see Lemma 1 of ^[13] for the proof.

In the subsequent Lemma 2.2, we demonstrate that the term $p+q$ adheres to the inequalities given in (2.3):

Lemma 2.2. For an RSA modulus $N = pq$ with $p$ and $q$ being primes of equal bit length with the condition $q < p < 2q$, the following statement is true:

Proof. Please see Lemma 1 of ^[14] for the proof.

Given an accurate approximation of any multiple of a divisor of $N$, Coppersmith's general result directly offers an efficient factoring method, as shown in Theorems 2.2 and 2.3. These theorems demonstrate that the remaining bits can be determined if a significant portion of $p$ bits are known.

Theorem 2.2. Consider an RSA modulus $N = pq$ with $p > q$. Suppose there is an unknown integer $b$ that is not divisible by $q$ and an approximation $\tilde{p}$ of $bp$ such that

In this case, $N$ can be factorized in polynomial time relative to $\log N$.

Proof. Please see ^[15] for the proof.

Theorem 2.3. Suppose $N = pq$ is an RSA modulus with $p > q$. Let $b$ be an unknown integer that does not divide by $q$. Given an approximation $\tilde{p}$ of $bp$ satisfying

then $N$ can be factorized in polynomial time relative to $\log N$.

Proof. Please see ^[15] for the proof.

As a result, having an approximation of $p+q$ allows us to determine an integer $p$.

Lemma 2.3. Suppose $N = pq$ is a valid RSA modulus satisfying $q < p < 2q$. Let $S$ denote the approximation of $p+q$ where $S > 2N^{\frac{1}{2}}$ and fulfills:

Then an integer $p$ can be estimated as:

This approximation guarantees that:

Proof. Suppose that $S > 2N^{\frac{1}{2}}$ and let $D = \sqrt{S^{2}-4N}$. We have

Observe that (2.6) can also be written as:

Dividing (2.7) by $(p-q+D)$ will yield

Next, suppose $|p+q-S| < \frac{p-q}{3(p+q)}N^{\frac{1}{4}}$. Since $\frac{p-q}{3(p+q)}N^{\frac{1}{4}} < N^{\frac{1}{4}}$, then

Considering $p-q+D > p-q$, we infer that:

Next, set $\tilde{p} = \frac{S+D}{2}$ which yields:

where we used $\frac{1}{2}\cdot\frac{p-q}{3(p+q)} < \frac{1}{2}$. □

Using Lemma 2.2, we can straightforwardly deduce:

Suppose we satisfy specific conditions for approximating the term $p + q$ via $S$. We can apply the same concept when estimating an integer $p$ via $\tilde{P}$, ensuring the error is less than $N^{1/4}$. A notable benefit of the LLL algorithm, as discussed in ^[16], is its proficiency in addressing simultaneous Diophantine approximations (see Theorem 2.4).

Theorem 2.4. Let $\alpha_1, \alpha_2, \ldots, \alpha_n$ be a set of rational numbers, and let $0 < \varepsilon < 1$. Suppose there exists an algorithm capable of efficiently computing a sequence of integers $p_i$ and an integer $q$ with a computation time that is polynomial in $\log(p_i)$ such that $i = 1, 2, \ldots, k$. The theorem holds under the following conditions:

Proof. Refer to ^[17] for the proof.

A method for factoring the prime numbers $p_i$ and $q_i$ by solving equations involving multiple RSA moduli is detailed in Theorem 2.5.

Theorem 2.5. Suppose there are $k$ RSA moduli $N_i = p_i q_i$, with $N$ being the smallest among them, and $k$ public exponents $e_i$ for $i = 1, 2, \ldots, k$, where $k \geq 2$. Let $\delta$ as $\delta = \frac{k}{2(k+1)}$. If there exists an integer $x < N^\delta$ and $k$ integers $y_i < N^\delta$ and $|z_i| < \frac{p_i - q_i}{3(p_i + q_i)} y_i N^{1/4}$, satisfying the Diophantine equation $e_{i}x-y_{i}\phi(N_{i}) = z_{i},$ then $k$ RSA moduli, specifically, $N_1, \ldots, N_k$, can be factorized in polynomial time.

Proof. Refer to ^[17] for the proof.

3.   Successful cryptanalysis on the system of weak RSA key equations

This section describes conditions under which an attacker can factorize $k$ RSA moduli $N_i$ concurrently. This vulnerability occurs when the attacker accesses RSA public-key pairs with specific vulnerabilities, allowing each $N_i$ to be efficiently factored in polynomial time. Notably, this vulnerability was identified by employing the lattice basis reduction method to solve the factorization of each RSA modulus $N_i$. The RSA keys under consideration have parameters that meet the following equations:

● Case Ⅰ: $e_{i}r-s_{i}(N_{i}-p_{i}-q_{i}+u_{i}) = t_{i}.$

● Case Ⅱ: $e_{i}r_{i}-s(N_{i}-p_{i}-q_{i}+u_{i}) = t_{i}$.

3.1.   Case Ⅰ: Successful cryptanalysis on the system of weak RSA key equations

Based on the earlier motivation, we introduce another vulnerability in the RSA cryptosystem. This newly discovered weakness is revealed when an attacker acquires a collection of RSA key pairs with specific flaws, enabling each $N_i$ to be factored within polynomial time. Assume the RSA public tuples $(N_i, e_i)$ fulfil the following system of equations:

where concurrent factorization of the system is possible if the integers $r, u_i, s_i,$ and $t_i$ are suitably small and unknown. This vulnerability was identified by factorizing each RSA modulus $N_i$ using the lattice basis reduction method. The following theorem outlines the specific conditions for this cryptanalysis approach.

Theorem 3.1. Examine $k$ RSA moduli, each represented as $N_i = p_i q_i$, where this holds true for each $i$ from $1$ to $k$, with $k \geq 3$. Denote by $N$ the smallest among these moduli and by $e_i$ the corresponding public exponents. Assume there exists a fixed integer $r < N^{\delta}$, $k$ integers $s_i < N^{\delta}$, and positive integers $u_i$ such that $u_i+\frac{|t_i|}{s_i} < \frac{p_i - q_i}{p_i + q_i} N^{0.25}$ for each $i$, where $\delta = \frac{k}{2(k+1)}$. If the values meet the conditions of the system of equations

then it is possible to efficiently factor the primes of $k$ RSA moduli $N_i$.

Proof. Assume $k \geq 3$ where $k$ RSA moduli $N_i = p_i q_i$ are valid for $i = 1, \cdots, k$. The equation $e_i r - (N_i - p_i - q_i + u_i) s_i = t_i$ can be rewritten as:

Dividing (3.1) with $N_{i}+u_{i}$ will yield

From (3.1), let $N = \min{N_i}$ and assume that $s_{i} < N^{\delta}$, $u_{i} > 0$, and $u_i+\frac{|t_{i}|}{s_{i}} < \frac{p_{i}-q_{i}}{p_{i}+q_{i}}N^{0.25}$. Then we can have $|t_i| < \frac{p_{i}-q_{i}}{p_{i}+q_{i}}s_{i}N^{0.25} < s_{i}N^{0.25} < N^{\delta}N^{0.25} < N^{\delta+0.25}$. Since from Lemma 2.2, $p_i + q_i < \frac{3\sqrt{2N}}{2}$, hence we obtain

Plugging (3.3) into (3.2), we get

The existence of an integer $r$ is demonstrated as follows. Let $\delta = \frac{k}{2(k+1)}$ and $\varepsilon = \sqrt{5}N^{\delta-\frac{1}{2}}$. Here, we get:

Since $\delta = \frac{k}{2(k+1)}$, (3.4) becomes

Combining (3.4) and (3.5), we obtain

Hence, if $r < N^\delta$, it follows that $r < 2^{\frac{k(k-3)}{4}} \cdot 3^k \cdot \varepsilon^{-k}$. Consequently, it holds that:

which meets the conditions stated in Theorem 2.4, allowing for the successful determination of $r\in\mathbb{Z}$ and $s_{i}\in\mathbb{Z}$. Subsequently, via the equation $e_{i}r-(N_{i}-p_{i}-q_{i}+u_{i})s_{i} = t_{i}$ will lead us to:

Given that $\frac{|t_{i}|}{s_{i}}+u_{i} < \frac{p_{i}-q_{i}}{p_{i}+q_{i}}N^{\frac{1}{4}}$ and $X_{i} = N_{i}-\frac{e_{i}r}{s_{i}}$ is an integer close to the sum of $p_{i}+q_{i}$ with an absolute difference smaller than $\frac{p_{i}-q_{i}}{p_{i}+q_{i}}N^{\frac{1}{4}}$, it is possible to approximate $p_{i}$ via $\tilde{P}_{i} = \frac{1}{2}(X_{i}+\sqrt{X_{i}^{2}-4N_{i}})$, where $|p_{i}-\tilde{P}_{i}| < N_{i}^{\frac{1}{4}}$. Therefore, Theorem 2.5 states that it is possible to concurrently determine the prime factors of $N_{1}, N_{2}, \ldots, N_{k}$ within polynomial time. □

Algorithm 1 is introduced next to demonstrate the process of factorizing $N_i = p_{i}q_{i}$ according to the approach described in Theorem 3.1.

To demonstrate the attack detailed in Theorem 3.1 and implemented via Algorithm 1, we present the following example. This attack was performed on a Windows 10 system, utilizing a computer equipped with an Intel (R) Core (TM) i5-8265U CPU running at 1.60 GHz and 12.0 GB of RAM.

Example 3.1. Assume an attacker has obtained three different RSA-256 moduli $N_i$, each paired with its respective public exponent $e_i$, given by:

Start by selecting $N$ as the smallest among $N_{1}$–$N_{3}$.

Setting $k = 3$, we compute $\delta$ using the formula $\delta = \frac{k}{2(k+1)} = 0.3750$. Subsequently, $\varepsilon$ is determined by $\sqrt{5}N^{\delta-\frac{1}{2}}\approx 5.852\times10^{-10}$. The next step involves calculating:

Additionally, for $i = 1, 2, 3$, we compute:

which yielded the following results:

Proceeding to step 5, a lattice $\mathcal{L}$ is generated by the entries of the matrix $\mathcal{A}$.

Subsequently, the LLL algorithm is executed on matrix $\mathcal{A}$ to generate a reduced basis matrix $\mathcal{B}$:

which has the following entries:

In step 7, we compute the matrix $\mathcal{D}$ by performing $\mathcal{D} = \mathcal{B} \cdot \mathcal{A}^{-1}$.

where

In step 8, assign the labels $r, s_1$–$s_3$ from left to right to the elements in the first row of $\mathcal{D}$ as follows:

Now, compute $X_{i}$ via the formula $X_{i} = \bigg[N_{i}-\frac{e_{i}r}{s_{i}}\bigg]$ which outputs:

Then, we compute $\tilde{P}_{i} = \frac{1}{2}(X_{i}+\sqrt{X_{i}^{2}-4N_{i}})$ resulting in the following output:

Observe that the value $\tilde{P}_{i}$ is an approximation of the prime $p_i$ and satisfies $|p_{i}-\tilde{P_{i}}| < N^{0.25}$. Therefore, we utilize Coppersmith's method on $\tilde{P}_{i}$ to determine $p_{i}$:

Finally, we factor $N_{1}$–$N_{3}$ by identifying $q_{1}$–$q_{3}$ such that $q_i = \frac{N_i}{p_i}$. The obtained values are as follows:

Remark 3.1. It is crucial to observe that in Example 3.1, the value of $r$, which approximates $N^{0.369}$, exceeds the thresholds set by previous research. Notably, it surpasses the limit of $x < \frac{1}{3}N^{0.25}$ as reported in ^[18], as well as the bounds of $x \approx N^{0.344}$ found in ^[17] and $d \approx N^{0.345}$ in ^[19].

3.2.   Case Ⅱ: Successful cryptanalysis on the system of weak RSA key equations

Given the earlier motivation discussed, we highlight an additional vulnerability in the RSA encryption system. That is when an adversary obtains a collection of RSA public key pairs exhibiting certain vulnerabilities, this newfound weakness permits the simultaneous factorization of each $N_i$ in polynomial time. In particular, the RSA keys in this collection include parameters that satisfy the conditions of the following system of equations:

allowing for concurrent factorization if suitably small, unknown integers $s, u_i, r_i,$ and $t_i$ are present. Notably, this vulnerability was discovered by successfully factoring each RSA modulus $N_i$ via the lattice basis reduction method. The theorem below details this cryptanalytic technique.

Theorem 3.2. Consider $k$ RSA moduli of the form $N_i = p_i q_i$ for each $i$ from $1$ to $k$, with $k \geq 3$. Let $N$ denote the largest modulus among these, and let $e_i$ be $k$ public exponents where $\min{e_i} = N^\alpha$. Suppose there exists an integer $s$ with $s\frac{|t_i|}{s_i} + u_i < \frac{p_i - q_i}{p_i + q_i} N^\frac{1}{4}$, where $\delta = \frac{k(2\alpha - 1)}{2(k + 1)}$. These conditions must satisfy the equation

Under these conditions, the factorization of all $k$ RSA moduli can be performed simultaneously in polynomial time.

Proof. Rewrite the equation $e_ir_i-s(N_i-p_i-q_i+u_i) = t_i$ as $e_ir_i-s N_i = t_i-s(p_i+q_i-u_i)$ and divide both sides of the equation by $e_i$. Subsequently, take the absolute value on both sides of the equation, resulting in:

Choose $N = max\{N_i\}$ and assume that $s < N^\delta$, $u_i > 0$, and $\frac{|t_i|}{s}+u_i < \frac{p_i-q_i}{p_i+q_i}N^\frac{1}{4}$. Consequently, $|t_i| < \frac{p_i-q_i}{p_i+q_i}sN^\frac{1}{4} < sN^\frac{1}{4} < N^\delta N^\frac{1}{4} < N^{\delta +\frac{1}{4}}$. Utilizing Lemma 2.2, which asserts $p_i+q_i < \frac{3\sqrt{2}\sqrt{N}}{2}$, and considering $\min{e_i} = N^\alpha$, we derive:

Substituting (3.7) into (3.6), we obtain

Our goal now is to verify the existence of an integer $s$. Define $\delta = \frac{k(2\alpha-1)}{2(k+1)}$ and $\epsilon = \sqrt{5}N^{\delta+\frac{1}{2}-\alpha}$. The subsequent calculations unfold as follows:

Consequently, we derive

If $s < N^\delta$, then $s < 2^{\frac{k(k-3)}{4}}\cdot 3^k\cdot \epsilon^{-k}$. Now, we summarize for:

Thus, the conditions of Theorem 2.4 are satisfied, which enables us to determine $s$ and $r_i$. Subsequently, using the equation $e_ir_i-s(N_i-p_i-q_i+u_i) = t_i$, we obtain:

Since $\frac{|t_i|}{s}+u_i < \frac{p_i-q_i}{p_i+q_i}N^\frac{1}{4}$, it follows that $|\frac{t_i}{s}+u_i| < \frac{|t_i|}{s}+u_i < \frac{p_i-q_i}{p_i+q_i}N^\frac{1}{4}$ and $A_i = N_i-\frac{e_ir}{s}$ approximates $p_i+q_i$ with an error less than $\frac{p_i-q_i}{p_i+q_i}N^\frac{1}{4}$. Therefore, according to Lemma 3, let $B_i = \sqrt{|A_i^2-4N_i|}$, and we can determine an approximation $\widetilde{P_i} = \frac{1}{2}(A_i+B_i)$ of $p_i$ satisfying $|p_i-\widetilde{P_i}| < N^{\frac{1}{4}}$.

As a result, for each $i = 1, 2, \cdots, k$, we can determine $p_i$ using Theorem 2.5, thereby achieving the factorization of $N_1, N_2, \cdots, N_k$.

Next, Algorithm 2 is provided to explain the steps involved in factorizing $N_i = p_{i}q_{i}$ using the methodology described in Theorem 3.2.

In this section, we illustrate to clarify the methodology outlined in Theorem 3.2, employing Algorithm 2. The attack detailed in Theorem 3.2 was executed on a Windows 10 system, using a computer equipped with an Intel(R) Core(TM) i5-8265U CPU operating at 1.60 GHz and 12.0 GB of RAM.

Example 3.2. Suppose an attacker has acquired three distinct pairs of RSA-140 moduli $N_i$, each associated with its corresponding public exponent $e_i$ as follows:

Start by selecting $N$ as the maximum among $N_{1}$–$N_{3}$ and $e = \min(e_1, e_2, e_3)$.

Since $N^\alpha = \min(e_1, e_2, e_3)$, we can get $\alpha = 0.951981$. Let $k = 3$. Following this, we obtain $\delta = \frac{k(2\alpha-1)}{2(k+1)} = 0.338985$ and $\epsilon = \sqrt{5}N^{\delta+\frac{1}{2}-\alpha}\approx 0.0000411678$.

Next, the following calculation is performed:

Then, we calculate the following for $i = 1, 2, 3$:

which yields the following results:

Proceeding to step 6, we form a lattice using the entries of the matrix $\mathscr{M}$ as its generating elements.

Subsequently, the LLL algorithm is executed on matrix $\mathscr{M}$ to generate a reduced basis matrix $\mathscr{K}$:

Next, compute matrix $\mathscr{H} = \mathscr{K} \cdot \mathscr{M}^{-1}$:

Observe the first row of the matrix $\mathscr{H}$ as follows:

Now, deduce the elements in the first row of $\mathscr{H}$ as $s, r_1$–$r_3$ from left to right as follows:

Then, define $A_i = N_i-\frac{e_ir_i}{s}$ and $B_i = \sqrt{|A_i^2-4N_i|}$ which yield the following outputs:

Then, compute $\widetilde{p_i} = \frac{1}{2}(A_i+B_i)$, which returns:

Observe that the value $\tilde{P}_{i}$ is an approximation of the prime $p_i$ and satisfies $|p_{i}-\tilde{P_{i}}| < N^{0.25}$. Therefore, we utilize Coppersmith's method on $\widetilde{p}_{i}$ to determine $p_{i}$. Finally, we complete the factorization of $N_{1}$–$N_{3}$ by identifying $q_{1}$–$q_{3}$ such that $q_i = \frac{N_i}{p_i}$. The obtained values are as follows:

Remark 3.2. In Example 3.2, we observe that $\min(r_{1}, r_{2}, r_{3})\approx N^{0.350}$ surpasses the limits set by previous research. Specifically, it exceeds the bounds established by Blömer-May ($x < \frac{1}{3}N^{0.25}$) as documented in ^[18], by Ariffin et al. ($d\approx N^{0.336}$) as reported in ^[19], and by Nitaj et al. ($x\approx N^{0.337}$) as mentioned in ^[17].

4.   Comparing results

As shown in Table 1, our findings are compared with established cryptanalysis on multiple instances of RSA moduli, each represented as $N_i = p_i q_i$. We classify these attacks based on the specific modifications made to the key equation's structure and the corresponding requirements to execute them. The table highlights the specific conditions and parameters under which these attacks succeed.

Our comparison criteria include the type of RSA moduli, weaknesses exploited in the key generation process, and mathematical techniques, such as lattice basis reduction or Coppersmith's method. Our findings demonstrate broader applicability and robustness compared to previously documented attacks requiring specific conditions. This analysis underscores the significant impact of our contributions to cryptanalysis and the need to revisit RSA-based systems' security assumptions.

In summary, Table 1 illustrates the advancements made by our study about existing cryptanalysis, reinforcing the importance of ongoing research to enhance RSA encryption security.

5.   Conclusions

In conclusion, our research has effectively shown the simultaneous factorization of $(N_i, e_i)$ for $k$ RSA moduli instances. This was achieved by utilizing a constant value $r$ that meets the weak RSA key equation $e_{i}r-(N_{i}-p_{i}-q_{i}+u_{i})s_{i} = t_{i}$. Our study's key finding is that, given certain detailed conditions, an attacker can concurrently factorize multiple RSA moduli $N_i$. The defect occurs once the attacker obtains a collection of RSA key pairs with specific flaws, enabling each $N_i$ to be factored concurrently in polynomial time, given the existence of suitably small, unknown integers $r, s_i, u_i,$ and $t_i$.

Additionally, we discovered another weakness where an adversary can exploit RSA parameters that satisfy the system of equations $e_{i}r_{i}-(N_{i}-p_{i}-q_{i}+u_{i})s = t_{i}$. These parameters can be factored simultaneously if the necessary small, unknown integers $s, r_i, u_i,$ and $t_i$ are present. It is essential to note that this vulnerability was identified through the factorization of each RSA modulus $N_i$ using Diophantine approximation and Coppersmith's lattice-based technique. Furthermore, our cryptanalysis demonstrates this new attack and provides a comparative analysis with existing research.

Significantly, the results of this work broaden the scope of insecure RSA decryption exponents. For example, consider the case of rogue certificate authorities (RCAs). RCA can issue seemingly legitimate but compromised certificates, introducing hidden vulnerabilities into the public key infrastructure. These certificates can be exploited between issuance and discovery to compromise private keys. The existence of RCAs underscores the importance of identifying weak public keys. Since the weak keys often meet standard key generation criteria, the cryptosystem may continue operating undetected. If an adversary uncovers these certificates, they can exploit them to derive private keys, even without direct access to private information. Certificate authorities and organizations must adopt proactive strategies to mitigate these risks. Strengthening key generation practices, avoiding predictable patterns, and addressing weak keys as vulnerabilities can help reduce the risks. This paper explores a potential RCA methodology for the RSA cryptosystem, offering practical solutions to enhance cryptosystem resilience.

Author contributions

Wan Nur Aqlili Ruzai: Writing-original draft, Writing-review & editing, Methodology, Conceptualization, Formal analysis; You Ying: Writing-original draft, Formal analysis, Software; Khairun Nisak Muhammad: Writing-review & editing, Validation; Muhammad Asyraf Asbullah: Conceptualization, Methodology, Funding acquisition, Validation, Writing-review & editing; Muhammad Rezal Kamel Ariffin: Supervision, Validation. All authors have read and approved the final version of the manuscript for publication.

Acknowledgments

The authors sincerely thank the anonymous reviewers for their insightful comments and constructive suggestions.

This research was made possible through financial support from Universiti Putra Malaysia.

Conflict of interest

The authors declare no conflict of interest.