Practical attacks on small private exponent RSA: new records and new insights

Abstract

As a typical representative of the public key cryptosystem, RSA has attracted a great deal of cryptanalysis since its invention, among which a famous attack is the small private exponent attack. It is well-known that the best theoretical upper bound for the private exponent d that can be attacked is $d\le N^{0.292}$, where N is a RSA modulus. However, this bound may not be achieved in practical attacks since the lattice constructed by Coppersmith method may have a large enough dimension and the lattice-based reduction algorithms cannot work so well in both efficiency and quality. In this paper, we propose a new practical attack based on the binary search for the most significant bits (MSBs) of prime divisors of N and the Herrmann-May’s attack in 2010. The idea of binary search is inspired by the discovery of phenomena called “multivalued-continuous phenomena”, which can significantly accelerate our attack. Together with several carefully selected parameters according to our exact and effective numerical estimations, we can improve the upper bound of d that can be practically achieved. More specifically, without the binary search method, we successfully attack RSA with a 1024-bit-modulus N when $d\le N^{0.285}$. Moreover, by our new method, we can implement a successful attack for a 1024-bit-modulus RSA when $d\le N^{0.292}$ and for a 2048-bit-modulus RSA when $d\le N^{0.287}$ in about a month. We believe our method can provide some inspiration to practical attacks on RSA with mainstream-size moduli.

1 Introduction

1.1 Background

Since it was proposed in 1978, RSA public key cryptosystem [25] plays an important role in lots of fields such as data encryption, key encapsulation, etc. A variety of security analysis come along with its widespread application. As is known to all, the small private exponent attack is one kind of the most famous attacks on RSA.

For the sake of efficiency in the decryption process, one may choose a small private exponent d relative to the RSA modulus N when generating the parameters. Unfortunately, in 1990, Wiener [32] showed that the RSA cryptosystem was insecure once $d\le \frac{1}{3}N^{1/4}$ using a continued fraction method. Many attempts were made based on Wiener’s idea, $N^{1/4}$ was still the order of magnitude of the upper bound of d without any additional condition, though multiplied by a better coefficient [2, 5, 30].

A vital improvement was made in [4] by Boneh and Durfee with the lattice-based strategy using the Coppersmith method. They firstly constructed a triangular lattice and got a bound $d\le N^{0.284}$. By removing some unhelpful polynomials, they obtained a sublattice from the original one and improved the bound to $d\le N^{0.292}$. However, the non-square sublattice brought plenty of troubles in the computation of the lattice determinant. In 2010, Herrmann and May [13] (we call it HM2010 attack for short below) applied the technique of unravelled linearization, which is introduced by Herrmann and May [12], to attack RSA and achieved the same bound as [4]. More importantly, the lattice constructed in [13] is a lower triangular square matrix which can avoid the complicated computation in [4]. Some generalizations of Boneh-Durfee’s result can be seen in [14, 22], but the upper bound of d was no better than [4] indeed. Overall, the upper bound $d\le N^{0.292}$ showed by Boneh and Durfee remains to be the best theoretical achievement till now.

1.2 Previous works

We note that all the bounds of the private exponent above are theoretical, i.e., those bounds are asymptotic which means that they will be achieved only if the lattice dimensions are large enough. As we know, the reduction algorithm cannot work so well in both efficiency and quality in a high-dimension lattice, which means that the best theoretical upper bound given in [4, 13] may not be achieved in practice. A natural question is what practical bound can be achieved. Therefore, many attempts have been made hoping to give an answer to this question.

One kind of the implementation of the practical small private exponent attacks is using the lattices constructed in [4, 13]. In [3], Boneh and Durfee ran their experiments to attack the RSA cryptosystem successfully when $d\le N^{0.265}$ with moduli of 1000 bits, 3000 bits and 10000 bits. Later, Durfee got a better results, namely, $d\le N^{0.277}$ for a 1024-bit-modulus RSA and $d\le N^{0.275}$ for a 2048-bit-modulus RSA [10]. In 2001, Blömer and May proposed a new attack and carried out some experiments [1]. In comparison with [3], they did not improve the asymptotic bound but the dimension of the lattice they constructed was lower under the same bound of d and the same size of N. For a 1000-bit modulus N, they can implement an effective attack in 6 days as long as $d\le N^{0.278}$. Without the additional tricks like [4] (such as using a reduction variant, Chebychev polynomials or some guess strategy), the early lattice-based practical attacks [1, 3, 10] as well as the attack in [33] did not seem to break through the bound $d\le N^{0.278}$ when the size of N is not less than 1024 bits. In 2021, Miller et al. [19] carried out their “focus group” attack in which the bound of d was improved to $d\le N^{0.280}$ for a 1000-bit modulus N.

Another kind of RSA practical attacks aimed to improve the bound of d is implemented with knowledge of some bits of a prime factor p of N. Early attacks of this kind were mainly theoretical since a large continuous fragment of bits must be known [8, 24], which may not be feasible in practice. In 2003, Suk stated that by knowing just $\frac{1}{100} \log _{2}N$ most significant bits (MSBs) of p, one could break the RSA cryptosystem for $d<N^{0.30}$ [29]. However, in his experiments, by knowing 10 MSBs of p, he got a bound $d\le N^{0.285}$ for a 1000-bit modulus N, which did not reach $N^{0.30}$ as he stated (detailed results can be seen in Table 5.8 in [29]). Later in 2008, Sarkar et al. ran large numbers of experiments and got some more detailed corresponding tables like [29] by searching exhaustively a few MSBs of p [27]. The tables highlight that the small private exponent RSA can be successfully attacked with a low-dimension lattice in practice. Note that the experiments in [29] and [27] are confirmatory, i.e., they verified that RSA can be broken when a few MSBs of p were already known, instead of searching for each candidate of their values. They did not finish the complete attack and the running time of the complete attack was estimated. For example, in [27] they stated that, to break a 1000-bit-modulus RSA for $d\le N^{0.285}$, the total time was $2^{15}\times 484$ seconds since each run required around 484 s and 15 MSBs were needed to search, which means that they needed about a week with a cluster of 26 machines using a 48-dimension lattice. More results of this kind can be seen in [11, 17, 18, 23, 26].

1.3 Our contributions

In this paper, we focus on the practical attack on RSA. As we can see from the previous works, there is still a considerable gap between the best theoretical bound of d and the practical one. Then, can the gap be further narrowed? If so, what can be done to achieve this goal? With these questions, we firstly take 1024-bit-modulus RSA as an example to carry out our practical attack and then expand to the practical attack of RSA with other moduli, such as 2048-bit-modulus RSA.

Firstly, we give a detailed and relatively accurate numerical estimation for the bound of ${\varvec{d}}$. And then, guided by the estimation, we achieve an upper bound $\varvec{d\le N^{0.285}}$ for a 1024-bit-modulus ${\varvec{N}}$ within a month, which is the best upper bound of this kind of attack as far as we know. For the parameters m and t of Coppersmith method (for detailed introduction, see Sect. 2.2 and Sect. 3), we get the optimal value of t responding to every value of m by using our calculated accurate analytical approximations. After that, based on the specific numerical parameter values and the experimental performance estimation of LLL algorithm provided by Nguyen and Stehlé [21], we give a detailed and relatively accurate estimation for the bound of d. The estimation table for the solvable upper bound of d we make is well consistent with both our experimental results and those in [27] especially in the case of medium-dimension lattices, which is mainly used in our practical attack. Guided by our estimation table, we implement our first practical attack to find the upper bound we can achieve based on the HM2010’s lattice. When the parameters m and t are set to 25 and 10, within 17 days on our PC, we successfully attack 1024-bit-modulus RSA for $d\le N^{0.285}$ (without any exhaustion strategy or additional side channel information), which is better than all the previous results we know.

Secondly, inspired by the multivalued-continuous phenomena in our experiments, we propose a new effective practical attack based on the binary search for some MSBs of ${\textbf {p }}$. Our experiments imply that it seems very difficult to successfully attack RSA for $d > N^{0.285}$ in practice within a month if no other tricks are added. Then what can we do to further improve the practical bound of d ? A natural idea may be to enumerate all possible values of several MSBs of p, which had been tried in some previous works. Frankly speaking, this idea is simple and trivial. However, during our implementations, we find some nontrivial and inspiring phenomena, which is called the “multivalued-continuous phenomena” for convenience: (I) besides the real values of the MSBs of p and q, much more additional exhaustive values (helpful guess values) can also help to attack the RSA cryptosystem successfully; (II) the helpful guess values appear continuously around real values of the MSBs of p and q; (III) the closer p and q are, the more helpful guess values there will be. Based on these inspiring phenomena, we propose a new practical attack in which one helpful guess value can be efficiently found by the binary search. As a result, we can significantly accelerate the attack, which is far better than other current practical results. More precisely, for a relatively close p and q, e.g., they share 4 MSBs, a 1024-bit-modulus RSA can be successfully attacked within several hours in a single PC for $d\le N^{0.292}$; even when p is quite far from q, the overwhelming majority of 1024-bit-modulus RSA can be broken within a month with a single PC for $d\le N^{0.292}$. By the way, the expression “p is close to q” means the value of $\vert p-q \vert$ is relatively small, while “p is far from q” means the value of $\vert p-q \vert$ is relatively large. Moreover, our attack scenario “p is close to q” is quite different from that in [9] (for details, see Sect. 4.3.1).

Finally, we implement our new practical attack on 2048-bit-modulus RSA and also get a nice upper bound. For a relatively close p and q in our experiment (p and q share about 3 MSBs), the RSA can be successfully attacked in about a week with a single PC for $d\le N^{0.287}$; when p is quite far from q, the overwhelming majority of 2048-bit-modulus RSA can be broken in about a month with a single PC for $d\le N^{0.287}$. Moreover, for a quite close p and q, the RSA also can be efficiently broken for $d\le N^{0.292}$, e.g., in our experiment, with p and q sharing 50 MSBs, the RSA can be successfully attacked within 12 days with a single PC for $d\le N^{0.292}$. Though the promotion effect is not so good as that of attack on 1024-bit-modulus RSA, the bound $d\le N^{0.287}$ (our attack on RSA can succeed with very special p and q for $d\le N^{0.292}$ but may not work well in a general case) is still better than all previous works as far as we know.

We would like to note that all our experimental results are obtained with a single PC, for more computing power, the running time given by our attack will surely be further improved.

1.4 Organization of the paper

The rest of this paper is organized as follows. In Sect. 2, we recall some preliminary knowledge and lemmas to be used latter. In Sect. 3, we revisit the Herrmann and May’s attack in 2010. In Sect. 4, we introduce in detail our new practical attack on RSA based on the binary search. In Sect. 5, we show some results of our experiments. Section 6 is the conclusion.

2 Preliminaries

2.1 Lattices and the LLL algorithm

Let ${\varvec{u}}_{1},\ldots ,{\varvec{u}}_{w}\in {\mathbb {R}} ^{n}$ be w linearly independent vectors with $w\le n$. The n-dimensional lattice L, spanned by ${\varvec{u}}_{1},\ldots ,{\varvec{u}}_{w}$, is the set of all integer linear combinations of ${\varvec{u}}_{1},\ldots ,{\varvec{u}}_{w}$, namely,

$$\begin{aligned} L=\left\{ \sum _{i=1}^{w}k_{i}{\varvec{u}}_{i} \mid k_{1},\ldots ,k_{w}\in {\mathbb {Z}} \right\} . \end{aligned}$$

The set of vectors ${\varvec{u}}_{1},\ldots ,{\varvec{u}}_{w}$ is called a basis of L and the integer w is called the rank of L while n is called the dimension. Specially, the lattice L is called full rank if $w=n$. Let ${\varvec{U}}$ be the $w\times n$ matrix consisting of row vectors ${\varvec{u}}_{1},\ldots ,{\varvec{u}}_{w}$. Then the determinant of L is defined by $\det L=\sqrt{{\varvec{U}} {\varvec{U}}^{t}}$. A famous hard problem is to find a short non-zero vector in L, especially the shortest one. The famous LLL algorithm [16] behaves well in finding a relatively short and nearly orthogonal lattice basis in polynomial time. Specifically, the properties of the output lattice basis by LLL algorithm can be seen in the following lemma.

Lemma 1

(LLL [16]) Let L be a full-rank lattice of dimension w and let $\tilde{{\varvec{v}}}_{1},\ldots ,\tilde{{\varvec{v}}}_{w}$ be a reduced basis of L output by the LLL algorithm. Then

$$\begin{aligned} \Vert \tilde{{\varvec{v}}}_{i}\Vert \le 2^{\frac{w(w-1)}{4(w+1-i)}}(\det L)^{\frac{1}{ (w+1-i)}} \,\text {for any }1\le i\le w, \end{aligned}$$

where $\Vert \tilde{{\varvec{v}}}_{i}\Vert$ is the Euclidean norm of $\tilde{{\varvec{v}}}_{i}$.

In most cases, the first reduced basis vector $\tilde{\varvec{v}}_{1}$ attracts major attention. However, the upper bound $2^{\frac{w-1}{4}}(\det L)^{\frac{1}{w}}$ of $\tilde{\varvec{v}}_{1}$ given by Lemma 1 is quite rough. In order to give a precise estimation as an instruction for our practical attack, we need a more accurate bound for $\tilde{{\varvec{v}}}_{1}$. In our attack implementations, we use the following estimation assumption given by Nguyen et al. [21].

Assumption 1

With the same notations as above in this section, let $\lambda _{1}(L)$ denote the Euclidean norm of the shortest lattice vector L, then

$$\begin{aligned} \lambda _{1}(L)/(\det L)^{1/w}\approx (1.02)^{w}. \end{aligned}$$

The experimental LLL bound $1.02^{w}(\det L)^{1/w}$ was got when Nguyen et al. investigated the practical behaviors of LLL, based on hundreds of experiments on different kinds of lattices with dimensions varied from 50 to 130. Since the value of $1.02^w$ is significantly less than $2^{(w-1)/4}$ when the dimension w is suitably high (e.g., $w=50$), they thought this may be why cryptanalysts used to believe LLL returns vectors surprisingly small compared to the original estimation. For more details, see Sect. 4.1 in [21]. We will also check the validation of Assumption 1 in Sect. 4.1.

2.2 Coppersmith method

Let $\Vert h(x_{1},...,x_{r})\Vert$ denote the norm of a polynomial $h(x_{1},...,x_{r})$ which represents the Euclidean norm of the coefficient vector. Consider a modular equation $h(x_{1},...,x_{r})=0\ (\bmod \ M)$, where all the absolute values of the target solutions $x_{1},...,x_{r}$ are bounded by $X_{1},...,X_{r}$, respectively. In 1996, a polynomial time algorithm to find all the solutions under the boundary was given by Coppersmith if $\Pi _{i=1}^{r}X_{i}$ is smaller than M, determinately when $r\le 2$ and heuristically when $r>2$ [7]. Later, an important work was done by Howgrave-Graham [15] who gave a simpler sufficient condition to transform a modular equation into an integer equation.

Lemma 2

(Howgrave-Graham) Let $m,M,X_{1},...,X_{r}$ be positive integers. Let $g(x_{1},...,x_{r})\in {\mathbb {Z}} [x_{1},...,x_{r}]$ be a polynomial with at most n monomials and let $\Vert g(x_{1},...,x_{r})\Vert$ denote the norm of the polynomial $g(x_{1},...,x_{r})$. If

• (1) $g(\tilde{x}_{1},...,\tilde{x}_{r})=0\ (\bmod \ M^{m}),\text { where }\vert \tilde{x}_{1}\vert<X_{1},...,\vert \tilde{x}_{r}\vert <X_{r}\text { and}$

• (2) $\Vert g(x_{1}X_{1},...,x_{r}X_{r})\Vert <M^{m}/\sqrt{n}$,

then $g(\tilde{x}_{1},...,\tilde{x}_{r})=0$ holds over ${\mathbb {Z}}$.

Lemma 2 provides a key instruction in RSA cryptanalysis. From Condition (2) of Lemma 2, we need to find polynomials with relatively small norms. Since there is one-to-one correspondence between a polynomial and its coefficient vector, the target of finding polynomials with small norms boils down to finding short non-zero vectors in the constructed lattice, which can be achieved in polynomial time by LLL algorithm.

After finding enough short nonzero vectors, we need to compute the common roots of the polynomials corresponding to the vectors. Usually, we need the following heuristic assumption. Recall that polynomials $f_{1},f_{2},\ldots ,f_{m}\in k[x_{1},x_{2},\ldots ,x_{n}]$ are called algebraically independent over a field k, if there is no nonzero m -variate polynomial $\Phi$ $\in k[y_{1},y_{2},\ldots ,y_{m}]$ such that $\Phi (f_{1},f_{2},\ldots ,f_{m})=0.$

Assumption 2

The polynomials output by the LLL algorithm are algebraically independent, and so the common roots of these polynomials can be computed by computing resultants or finding a Gröbner basis.

This assumption has been verified by experiments before as well as ours in Sect. 5.

3 The HM2010 attack revisited

Our practical attack on RSA in this paper relies heavily on the work of Herrmann and May. Therefore, in this section we will revisit the HM2010 attack briefly. In order to show its essence, we will revisit Boneh and Durfee’s work together. For convenience, the lattices given by Boneh and Durfee that yield the bounds 0.284 and 0.292 are called BD$-$0.284-lattice and BD$-$0.292-lattice, respectively.

Let $N=pq$ be a public RSA modulus whose prime factors p and q are of the same bitsize. A public exponent e and a private exponent d satisfy $ed\equiv 1\ (\bmod \ \varphi (N))$, i.e.,

$$\begin{aligned} ed-k(N+1-p-q)=1 \end{aligned}$$

(1)

for some integer k. Let $A=N+1$ and $s=-p-q$. Then it can be seen from (1) that

$$\begin{aligned} k(A+s)+1\equiv 0\ (\bmod \ e). \end{aligned}$$

Denote $f(x,y):=x(A+y)+1$. The original aim to recover d and factor N became to find small roots of the polynomial $f(x,y)(\bmod \ e)$. With a fixed positive integer m, a parameter t to be optimized and the definitions of the following polynomials (usually called x-shift polynomials and y -shift polynomials respectively)

$$\begin{aligned} g_{i,k}(x,y)&:=x^{i}f^{k}e^{m-k},k=0,\ldots ,m\text { and }i=0,\ldots ,m-k; \\ h_{j,k}(x,y)&:=y^{j}f^{k}e^{m-k},k=0,\ldots ,m\text { and }j=1,\ldots ,t, \end{aligned}$$

Boneh and Durfee constructed the BD$-$0.284-lattice using the Coppersmith method. All the used shift polynomials are ordered as

$$\begin{aligned} g_{i,k}(x,y)&\prec h_{j,k^{\prime }}(x,y)\text { for any } i,j,k,k^{\prime }, \\ g_{i,k}(x,y)&\prec g_{i^{\prime },k^{\prime }}(x,y)\text { for } i+k<i^{\prime }+k^{\prime }, \\ g_{i,k}(x,y)&\prec g_{i^{\prime },k^{\prime }}(x,y)\text { for } i+k=i^{\prime }+k^{^{\prime }}\text { and }i>i^{\prime }, \\ h_{j,k}(x,y)&\prec h_{j^{\prime },k^{\prime }}(x,y)\text { for } j<j^{^{\prime }}, \\ h_{j,k}(x,y)&\prec h_{j,k^{\prime }}(x,y)\text { for }k<k^{\prime }. \end{aligned}$$

A simple BD$-$0.284-lattice with $m=2,t=1$ is shown below ($9\times 9$ matrix).

	1	x	xy	$x^{2}$	$x^{2}y$	$x^{2}y^{2}$	y	$xy^{2}$	$x^{2}y^{3}$
$e^{2}$	$e^{2}$
$xe^{2}$		$e^{2}X$
fe	e	eAX	eXY
$x^{2}e^{2}$				$e^{2}X^{2}$
xfe		eX		$eAX^{2}$	$eX^{2}Y$
$f^{2}$	1	2AX	2XY	$A^{2}X^{2}$	$2AX^{2}Y$	$X^{2}Y^{2}$
$\varvec{ye}^{2}$							${\varvec{e}}^{2}{\varvec{Y}}$
$\varvec{yfe}$			$\varvec{eAXY}$				$\varvec{eY}$	$\varvec{eXY}^{2}$
$yf^{2}$			2AXY		$A^{2}X^{2}Y$	$2AX^{2}Y^{2}$	Y	$2XY^{2}$	$X^{2}Y^{3}$

Using the BD$-$0.284-lattice together with $m\rightarrow \infty$, they got the bound $d\le N^{0.284}$. In order to decrease the determinant of the lattice and improve the upper bound of d, they tried to remove some rows that enlarge the determinant. They constructed the BD$-$0.292-lattice by throwing away the y-shift polynomials $y^{j}f^{k}e^{m-k}$ from the BD$-$0.284-lattice for all j and $k<\lfloor m/t\rfloor j$. For example, when $m=2$ and $t=1$, the bold rows of the above BD$-$0.284-lattice is removed, and then the BD$-$0.292-lattice is as follows ($7\times 9$ matrix).

	1	x	xy	$x^{2}$	$x^{2}y$	$x^{2}y^{2}$	y	$xy^{2}$	$x^{2}y^{3}$
$e^{2}$	$e^{2}$
$xe^{2}$		$e^{2}X$
fe	e	eAX	eXY
$x^{2}e^{2}$				$e^{2}X^{2}$
xfe		eX		$eAX^{2}$	$eX^{2}Y$
$f^{2}$	1	2AX	2XY	$A^{2}X^{2}$	$2AX^{2}Y$	$X^{2}Y^{2}$
$yf^{2}$			2AXY		$A^{2}X^{2}Y$	$2AX^{2}Y^{2}$	Y	$2XY^{2}$	$X^{2}Y^{3}$

With the BD$-$0.292-lattice, the upper bound of d is improved to $d \le N^{0.292}$. However, the BD$-$0.292-lattice is not a square matrix which results in a complex computation of the lattice determinant.

In order to avoid the complex computation of the determinant, Herrmann and May applied a technique of unravelled linearization to construct a new square lattice and got the same bound $d\le N^{0.292}.$ They stated the reason why the BD$-$0.292-lattice is not square is that the first y-shift polynomial brings more than one new term to the lattice. This phenomenon results in more than one column adding to the lattice when one row is added. To solve the trouble, they applied the unravelled linearization technique to their lattice construction. In the technique the substitution $xy=u-1$ is used twice. The first use changes f(x, y) to $\tilde{f}(u,x)=u+Ax$. Since all the shift polynomials are added according to the order defined above, the second use can make sure that every new-added y-shift polynomial adds only one new term to the set constituted by all the terms of the former polynomials, which keeps the lattice being a square matrix. More detailed, consider $y^{j}\tilde{f}^{k}$ being added to the lattice (the factor $e^{m-k}$ is omitted as it does not influence the set of terms). Since $\tilde{f}(u,x)=u+Ax$, it follows that

$$\begin{aligned} y^{j}\tilde{f}^{k}=u^{k}y^{j}+\sum _{i=1}^{k}\left( \begin{array}{c} k \\ i \end{array} \right) A^{i}u^{k-i}x^{i}y^{j}. \end{aligned}$$

The term $u^{k}y^{j}$ is a new-added term. Consider the other terms in $y^{j}\tilde{f}^{k}$. Using the second substitution $xy=u-1$ one can get

$$\begin{aligned} u^{k-i}x^{i}y^{j}=u^{k-i}(u-1)^{\min \{i,j\}}x^{i-\min \{i,j\}}y^{j-\min \{i,j\}}. \end{aligned}$$

If $i\ge j$, then

$$\begin{aligned} u^{k-i}x^{i}y^{j}=u^{k-i}(u-1)^{j}x^{i-j}= \sum _{l=0}^{j}\left( \begin{array}{c} j \\ l \end{array} \right) (-1)^{j-l}u^{k-i+l}x^{i-j}, \end{aligned}$$

whose terms already appear in the x-shift polynomials $x^{i-j}\tilde{f}^{k-i},\ldots ,x^{i-j}\tilde{f}^{k-i+j}$; if $i<j$, then

$$\begin{aligned} u^{k-i}x^{i}y^{j}=u^{k-i}(u-1)^{i}y^{j-i}=\sum _{l=0}^{i}\left( \begin{array}{c} i \\ l \end{array} \right) (-1)^{i-l}u^{k-i+l}y^{j-i}, \end{aligned}$$

whose terms already appear in $y^{j-i}\tilde{f} ^{k-i},\ldots ,y^{j-i}\tilde{f}^{k}$. All these polynomials as well as the terms have been added to the lattice before. Therefore, by this technique, every y-shift polynomial $y^{j}\tilde{f}^{k}$ adds only one new term $u^{k}y^{j}$ to the lattice, which makes sure that the lattice is square. A simple HM2010 lattice with $m=2,t=1$ is shown below ($7\times 7$ matrix).

	1	x	u	$x^{2}$	xu	$u^{2}$	$u^{2}y$
$e^{2}$	$e^{2}$
$xe^{2}$		$e^{2}X$
$\tilde{f}e$		eAX	eU
$x^{2}e^{2}$				$e^{2}X^{2}$
$x\tilde{f}e$				$eAX^{2}$	eXU
$\tilde{f}^{2}$				$A^{2}X^{2}$	2AXU	$U^{2}$
$y\tilde{f}^{2}$		$-A^{2}X$	$-2AU$		$A^{2}XU$	$2AU^{2}$	$U^{2}Y$

Overall, the complete HM2010 attack can be briefly summarized as follows.

• (1) Use the substitution $xy=u-1$, f(x, y) becomes to $\tilde{f} (u,x)=u+Ax$, and then $g_{i,k}(x,y)$ and $h_{j,k}(x,y)$ are changed to $\tilde{g}_{i,k}(u,x)$ and $\tilde{h}_{j,k}(u,x,y)$.

• (2) Discard the y-shift polynomials $\tilde{h}_{j,k}(u,x,y)$ if $k<\lfloor m/t\rfloor j$, and then the retained y-shift polynomials are $\tilde{h}_{j,k}(u,x,y):=y^{j}\tilde{f}^{k}e^{m-k}$ with $j=1,\ldots ,t$ and $k=\lfloor m/t\rfloor j,\ldots ,m$.

• (3) Reuse the substitution $xy=u-1$ to substitute all the xy in the monomials of $\tilde{g}_{i,k}(u,x)$ and $\tilde{h}_{j,k}(u,x,y)$.

• (4) Construct a lower triangular lattice L based on $\tilde{g}_{i,k}(u,x)$ ($k=0,\ldots ,m$ and $i=0,\ldots ,m-k$) and $\tilde{h}_{j,k}(u,x,y)$ $(j=1,\ldots ,t$ and $k=\lfloor m/t\rfloor j,\ldots ,m$).

• (5) Use the lattice basis reduction algorithm together with resultants computation or a Gröbner basis method and finally get the value of d.

The core point of this technique is the double use of the substitution $xy=u-1$ in step (1) and (3). The first use greatly reduces the terms of the polynomials and results in a decrease of the lattice dimension. The second use makes sure that every new-added y-shift polynomial adds only one new term to the set constituted by all the terms of the former polynomials, which keeps the lattice being a square matrix.

Let $d\le N^{\delta }$ for some real number $\delta$. Let $\tau =t/m$ and let $s_{X},s_{Y},s_{U},s_{e}$ denote the contribution of X, Y, U, e to the determinant $\det L$. Based on the simplified condition $\det L=X^{s_{X}}Y^{s_{Y}}U^{s_{U}}e^{s_{e}}\le e^{m\dim L}$ from Lemma 2, it can be obtained that

$$\begin{aligned} \delta \cdot \frac{m^{3}}{6}+\frac{1}{2}\cdot \frac{\tau ^{2}m^{3}}{6} +\left( \delta +\frac{1}{2}\right) \cdot \frac{(1+2\tau )m^{3}}{6}+\frac{(2+\tau )m^{3}}{6 }\le \frac{(1+\tau )m^{2}}{2}\cdot m, \end{aligned}$$

(2)

using the upper bounds $X=N^{\delta },Y=N^{1/2},U=N^{\delta +1/2}$ together with the approximate calculations of

$$\begin{aligned} s_{X}= & {} \frac{m^{3}}{6}+o(m^{3}), \\ s_{Y}= & {} \frac{\tau ^{2}m^{3}}{6}+o(m^{3}), \\ s_{U}= & {} \frac{(1+2\tau )m^{3}}{6}+o(m^{3}), \\ s_{e}= & {} \frac{(2+\tau )m^{3}}{6}+o(m^{3}), \\ \dim L= & {} \frac{(1+\tau )m^{2}}{2}+o(m^{2}). \end{aligned}$$

After getting an optimized value of $\tau =(1-2\delta )$, they finally successfully obtained the desired Boneh-Durfee bound

$$\begin{aligned} \delta \le 1-\frac{\sqrt{2}}{2}\approx 0.292. \end{aligned}$$

For details, see [13].

4 A new practical small private exponent attack on RSA

The majority of small private exponent attacks on RSA mainly focus on the theoretical asymptotic upper bound of the private exponent d. Therefore, as far as we know, when calculating the values of the exponents in the lattice determinant, only the highest order terms of the parameter m are retained. Considering that the value of m cannot be too large in the practical attack, the low-order terms should be retained for accurate estimations. In this section, we will consider the modulus N with $\eta$-bit-size prime factors p and q where $q<p<2q$ and set $d=N^{\delta }$.

With the same notations as Sect. 3, specific and relatively exact values of some parameters used in the calculations of the dimension $\dim L$ and the determinant $\det L$ are shown as follows.

Lemma 3

With the same notations as Sect. 3, we have

$$\begin{aligned} \dim L= & {} \sum _{k=0}^{m}\sum _{i=0}^{m-k}1+\sum _{j=1}^{\tau m}\sum _{k=\big \lfloor \frac{1}{\tau }\big \rfloor j}^{m}1\approx \frac{ (m+1)(m+2)}{2}+\frac{\tau m^{2}+(2\tau -1)m}{2}, \\ \det L= & {} X^{s_{X}}Y^{s_{Y}}U^{s_{U}}e^{s_{e}}, \end{aligned}$$

where

$$\begin{aligned} s_{X}= & {} \sum _{k=0}^{m}\sum _{i=0}^{m-k}i=\frac{m(m+1)(m+2)}{6}, \\ s_{Y}= & {} \sum _{j=1}^{\tau m}\sum _{k=\big \lfloor \frac{1}{\tau } \big \rfloor j}^{m}j\approx \frac{\tau ^{2}m^{3}+3\tau ^{2}m^{2}+3\tau m-m}{ 6}, \\ s_{U}= & {} \sum _{k=0}^{m}\sum _{i=0}^{m-k}k+\sum _{j=1}^{\tau m}\sum _{k=\big \lfloor \frac{1}{\tau }\big \rfloor j}^{m}k\approx \frac{ (4\tau ^{2}+2\tau )m^{3}+(9\tau ^{2}+3\tau )m^{2}+(7\tau -1)m}{12\tau }, \\ s_{e}= & {} \sum _{k=0}^{m}\sum _{i=0}^{m-k}(m-k)+\sum _{j=1}^{\tau m}\sum _{k=\big \lfloor \frac{1}{\tau }\big \rfloor j}^{m}(m-k) \\\approx & {} \frac{m(m+1)(m+2)}{3}+\frac{2\tau ^{2}m^{3}+(3\tau ^{2}-3\tau )m^{2}-(3\tau -1)m}{12\tau }. \end{aligned}$$

Proof. See Appendix A.

With the same consideration as above, the second condition in Lemma 2 cannot be simplified as $\det L\le e^{m\dim L}$. Let $\tilde{{\varvec{v}}}_{1}$ be the first reduced basis vector output by LLL algorithm. Strictly following Lemma 2, we need

$$\begin{aligned} \Vert \tilde{{\varvec{v}}}_{1}\Vert <\frac{e^{m}}{\sqrt{\dim L}}. \end{aligned}$$

By the LLL algorithm, the theoretical upper bound of $\tilde{{\varvec{v}}}_{1}$ can be given by

$$\begin{aligned} \Vert \tilde{{\varvec{v}}}_{1}\Vert <2^{(\dim L-1)/4}(\det L)^{1/\dim L}. \end{aligned}$$

However, this estimation is too rough to instruct our experiments. Instead, in the practical attack, we adopt the experimental estimation of $\tilde{{\varvec{v}}}_{1}$ given by Nguyen et al. in [21], i.e.,

$$\begin{aligned} \Vert \tilde{{\varvec{v}}}_{1}\Vert <(1.02)^{\dim L}(\det L)^{1/\dim L}. \end{aligned}$$

Then we can utilize the following modified estimation formula to obtain the upper bound of the solvable $\delta$, namely,

$$\begin{aligned} (1.02)^{\dim L}(\det L)^{1/\dim L}<\frac{e^{m}}{\sqrt{\dim L}}. \end{aligned}$$

(3)

In the rest of this section, we will at first explore the practical solvable bound of $\delta$ using HM2010’s method. In order to break through the bound, we then try a few MSBs exhaustion of p to obtain new bounds of $\delta$. At last, we introduce our new attack based on the binary search.

4.1 The practical solvable bound of $\delta$ in HM2010 attack

Firstly, we use the above method to estimate the upper bound of the solvable $\delta$. Take the logarithm of both sides of Inequality (3) to base N, we can obtain

$$\begin{aligned} (\dim L)^{2}\cdot \log _{N}1.02+\frac{1}{2}\dim L\cdot \log _{N}\dim L+\log _{N}\det L<m\cdot \dim L\cdot \log _{N}e. \end{aligned}$$

Since

$$\begin{aligned}{} & {} \log _{N}1.02\approx \frac{\log _{2}1.02}{2\eta },\,\log _{N}\dim L\approx \frac{1}{2\eta }\log _{2}\dim L,\\{} & {} \log _{N}e\approx 1,\,\log _{N}\det L\approx \delta \cdot s_{X}+\frac{1 }{2}s_{Y}+\left( \delta +\frac{1}{2}\right) \cdot s_{U}+s_{e}, \end{aligned}$$

it follows that

$$\begin{aligned} \delta <\frac{-(\dim L)^{2}\cdot \frac{\log _{2}1.02}{2\eta }+\left( m-\frac{\log _{2}\dim L}{4\eta }\right) \cdot \dim L-\frac{1}{2}(s_{Y}+s_{U}) -s_{e}}{s_{X}+s_{U}}. \end{aligned}$$

(4)

Since (4) is too complicated for us to give an optimal analytical expression of the bound, instead we show the discrete corresponding relation of the upper bound of $\delta$ with m and t. Using (4) together with analytical approximations in Lemma 3, we can get the optimal t corresponding to various m. Based on the parameters m and the optimal t, we can obtain the value of $1/\tau$ (namely, m/t), which can help us to get all the real values of the parameters in Lemma 3 by a rounding operation. Based on the real values and (4), a corresponding relation between the upper bound of $\delta$ and m, t is displayed in Table 1.

Table 1 A corresponding relation between $\delta$ and m, t for $2\eta =1024$

As can be seen from Table 1, when $m=21,t=9$ and $\delta \le 0.284$, the method of HM2010 can successfully recover the private exponent d. This is also consistent with our experimental results. Theoretical estimations and experimental results show that the minimum parameters selected for solving $\delta \le 0.284$ are $m=21,t=9$, and the success rate of such experiments is more than $60\%$ with 100 experiments. Similarly, if the private exponent d with the size $\delta \le 0.285$ is required to be solved, the minimum parameters to be chosen are $m=25,t=10$. This is also consistent with our experiments since the rate of our experiments is about $60\%$ (see Sect. 5 for details of our experiments). Considering the running time of our attack for $\delta \approx 0.285$ and the fact that we fail to attack RSA for $d \ge N^{0.286}$ within a month, it seems very difficult to get a better bound of $\delta$ in practical attacks on RSA.

Remark 1

The validation of Assumption 1 is checked by some representative experiments when we give Table 1. Specially, we check the value of $(\frac{\Vert \tilde{\varvec{v}}_{1}\Vert }{(\det L)^{1/w}})^{1/w}$ when $m=5, 10, 12, 14$. Our experiments show that the value 1.011 when $m=5$ is slightly less than 1.02 and the values 1.017, 1.019, 1.020 are nearly equal to 1.02 when $m=10, 12, 14$. This result implies that Assumption 1 is valid for lattices with medium dimensions, which is consistent with [21].

From Table 1 we can see that, to get a better bound of $\delta$, we need a lager value of m, thus resulting in a lattice with a higher dimension. However, as we know, the LLL algorithm does not perform well in a lattice with a high dimension. This fact makes it unpractical to further improve the bound by utilizing HM2010’s lattice merely. There is no doubt that new ideas need to be added into the attack in order to improve the practical bound of $\delta$.

4.2 New bounds of $\delta$ with some MSBs exhaustion of p

When using HM2010 method directly to attack the small private exponent of RSA, there will inevitably be a bottleneck. That is, a larger value of m would lead to a larger practical upper bound of solvable $\delta$; while at the same time, when m increases, the dimension of the lattice increases rapidly, which results in a sharp rise in the running time. Based on our experiments, it seems very difficult to break 1024-bit-modulus RSA within a month if $\delta >0.285.$

In order to further improve the practical upper bound of the assaultable private exponent, we look back to Inequality (3). We note that, when m and t are fixed, decreasing the value of $\det L$ will raise the upper bound of $\delta$. In fact, let us consider the equation

$$\begin{aligned} \det L=X^{s_{X}}Y^{s_{Y}}U^{s_{U}}e^{s_{e}}. \end{aligned}$$

It can be seen from Lemma 3 that $s_{X},s_{Y},s_{U},s_{e}$ will remain unchanged for fixed m and t. It is clear that if the bounds Y and U are decreased, then $\det L$ will decrease. A natural and trivial idea to achieve this goal is to try an exhaustive search for some MSBs of p, which is the same thought as Suk in [29] and Sarkar in [27]. In [29] and [27], Suk and Sarkar et al. directly used $N/p^{\prime }$ as an approximation of q where $p^{\prime }$ is an approximation of p constructed from the MSBs of p. With the approximation, Suk completed his simple extension of the Boneh-Durfee attack and Sarkar et al. successfully realized their attack with low lattice dimensions. In [29] and [27], they did not give the concrete construction of $p^{\prime }$ and discuss the deviation of MSBs from the approximation to the real value. However, in this paper, in order to explain clearly the multivalued-continuous phenomena, we should make sure that the calculated approximate MSBs value we derive from $p_{m}$ (i.e., the s MSBs of p) is a perfect approximation of $q_{m}$ (i.e., the s MSBs of q), that is, the derivation must be quite small. Under this consideration, we give a lemma as follows.

Lemma 4

Let $N=pq$ and the $\eta$-bit-size prime factors p and q satisfy $q<p<2q$. Let $p_{m},q_{m}$ be the s MSBs of p, q and let $p_{l},q_{l}$ be the $\eta -s$ least significant bits (LSBs) of p, q. Then we have

$$\begin{aligned} q_{m}&=\Bigg \lfloor \Bigg \lfloor \frac{N}{p_{m}\cdot 2^{\eta -s}+2^{\eta -s-1}}\Bigg \rfloor /2^{\eta -s}\Bigg \rfloor +\alpha , \alpha \in \{-1,0,1\}, \end{aligned}$$

(5)

$$\begin{aligned} p_{m}&=\Bigg \lfloor \Bigg \lfloor \frac{N}{q_{m}\cdot 2^{\eta -s}+2^{\eta -s-1}}\Bigg \rfloor /2^{\eta -s}\Bigg \rfloor +\alpha ^{\prime }, \alpha ^{\prime }\in \{-1,0,1\}. \end{aligned}$$

(6)

Proof

Let $\tilde{p}=p_{m}\cdot 2^{\eta -s}+2^{\eta -s-1}$ and denote $\tilde{q}=N/\tilde{p}$. Then

$$\begin{aligned} \vert q-\tilde{q}\vert =\left| q-\frac{N}{\tilde{p}}\right| =\frac{q\vert p-\tilde{p}\vert }{\tilde{p}}=\frac{ q\vert p_{l}-2^{\eta -s-1}\vert }{\tilde{p}}. \end{aligned}$$

The inequality $\vert p_{l}-2^{\eta -s-1}\vert <2^{\eta -s-1}$ holds since $0<p_{l}<2^{\eta -s}$. Since $q<p<2\tilde{p}$, we can get

$$\begin{aligned} \vert q-\tilde{q}\vert =\frac{q\cdot 2\vert p_{l}-2^{\eta -s-1}\vert }{2\tilde{p}}<2\vert p_{l}-2^{\eta -s-1}\vert <2\cdot 2^{\eta -s-1}=2^{\eta -s}. \end{aligned}$$

(7)

Let $\tilde{q}_{m}$ be the s MSBs of $\lfloor \tilde{q}\rfloor$, that is

$$\begin{aligned} \tilde{q}_{m}=\Bigg \lfloor \frac{\lfloor \tilde{q}\rfloor }{2^{\eta -s}}\Bigg \rfloor =\Bigg \lfloor \Bigg \lfloor \frac{N}{p_{m}\cdot 2^{\eta -s}+2^{\eta -s-1}}\Bigg \rfloor /2^{\eta -s}\Bigg \rfloor . \end{aligned}$$

From (7), we can get $\vert q_{m}-\tilde{q}_{m}\vert \le 1$ (otherwise, $\vert q_{m}-\tilde{q}_{m}\vert \ge 2$, and so $\vert q-\tilde{q}\vert >2^{\eta -s}$, which leads to a contradiction), and then (5) is obviously true.

Similarly, $p_{m}$ can also be computed when $q_{m}$ is known. Let $\tilde{q}=q_{m}\cdot 2^{\eta -s}+2^{\eta -s-1}$ and $\tilde{p}=N/\tilde{q}$. Then

$$\begin{aligned} \vert p-\tilde{p}\vert =\left| p-\frac{N}{\tilde{q}}\right| =\frac{p\vert q-\tilde{q}\vert }{\tilde{q}}=\frac{p\vert q_{l}-2^{\eta -s-1}\vert }{\tilde{q}}. \end{aligned}$$

The inequality $\vert q_{l}-2^{\eta -s-1}\vert <2^{\eta -s-1}$ holds since $0<q_{l}<2^{\eta -s}$. We note that $p,q,\tilde{q}$ are all n-bit numbers, and so it is clear that $p<2\tilde{q}$. Therefore, we can get

$$\begin{aligned} \vert p-\tilde{p}\vert =\frac{p\cdot 2\vert q_{l}-2^{\eta -s-1}\vert }{2\tilde{q}}<2\vert q_{l}-2^{\eta -s-1}\vert <2^{\eta -s}, \end{aligned}$$

which implies that (6) is true with a same discussion as above. This completes the proof. $\square$

Remark 2

From Lemma 4 we know, for $p_{m}$ and $q_{m}$, no matter which one is known, the other one can be computed successfully by the same method. Therefore, in our experiments, $p_{m}$ and $q_{m}$ have the same status and effect.

In our new practical attack, we will take $\alpha =0$ (or take $\alpha ^{\prime }=0$ if we need) in Lemma 4. Although $\alpha =0$ does not always hold in practice, it will not be an obstruction to our practical attack, since good approximations of $p_{m}$ and $q_{m}$ can also help to realize a successful attack thanks to the multivalued-continuous phenomena which will be introduced in Sect. 4.3.

When s MSBs of p are enumerated, Eq. (1) then becomes to

$$\begin{aligned} ed-1=k(N+1-(p_{m}+q_{m})\cdot 2^{\eta -s}-(p_{l}+q_{l})) . \end{aligned}$$

Let $A^{\prime }=N+1-(p_{m}+q_{m})\cdot 2^{\eta -s}, y^{\prime }=-(p_{l}+q_{l}), x^{\prime }=x=k.$ Then we have

$$\begin{aligned} f^{\prime }(x^{\prime },y^{\prime })=x^{\prime }(A^{\prime }+y^{\prime })+1\equiv 0\ (\bmod \ e). \end{aligned}$$

Using the substitution $u^{\prime }=x^{\prime }y^{\prime }+1$, the equation above changes to

$$\begin{aligned} f^{\prime }(u^{\prime },x^{\prime })=u^{\prime }+A^{\prime }x^{\prime }\equiv 0\ (\bmod \ e). \end{aligned}$$

Let $2^{s}=N^{\xi }$. Then the bounds of the new variables become to

$$\begin{aligned}&x^{\prime }<X^{\prime }=N^{\delta },\,y^{\prime }<Y^{\prime }=N^{ \frac{1}{2}-\xi },\\&e<N,\,u^{\prime }<U^{\prime }=N^{\delta +\frac{1}{2}-\xi }. \end{aligned}$$

A result similar to (4) can be obtained, i.e.,

$$\begin{aligned} \delta <\frac{-(\dim L)^{2}\cdot \frac{\log _{2}1.02}{2\eta }+\left( m-\frac{\log _{2}\dim L}{4\eta }\right) \cdot \dim L-(\frac{1}{2}-\xi )(s_{Y}+s_{U})-s_{e}}{s_{X}+s_{U}}. \end{aligned}$$

(8)

Similar to Sarkar in [27], we hence adopt the discrete strategy to show the relationship numerically instead. Partial numerical corresponding relations between $\delta$ and s are given in Tables 2 and 3.

Table 2 Partial numerical corresponding relation between $\delta$ and s with $m=7$, $t=3,2\eta =1024$

Table 3 Partial numerical corresponding relation between $\delta$ and s with $m=12$, $t=5,2\eta =1024$

As can be seen from Tables 2 and 3, for a 1024-bit-modulus RSA, when $m=7$ and $t=3$, at least 27 MSBs of p need to be exhausted to raise the upper bound of $\delta$ to 0.292. Similarly, when $m=12$ and $t=5$, the necessary number of exhausted MSBs is 18 to achieve the same bound with a 1024-bit N. This is well consistent with our experiments. In details, when $m=7$ and $t=3$, the success rate with a 26-MSB exhaustion is 13%, while in sharp contrast the rate with 27-MSB exhaustion is 87%; when $m=12$ and $t=5$, the success rates of 17-MSB exhaustion and 18-MSB exhaustion are 50% and 94%. For more details, see Sect. 5.

Remark 3

Tables 2 and 3 will play an important role in our new practical attack which is introduced in Sect. 4.3. Since the necessary numbers of exhausted MSBs in Tables 2 and 3 are given by our estimations and well consistent with our experiments, they may be nice instructors for us to choose suitable parameters (namely m, t, s) to implement our attack.

Similar results can be seen in [29] and [27] and we display part of them below in Table 4. We note that the necessary numbers of exhausted MSBs in [29] were given by estimations while those in [27] were given by experiments. Moreover, the maximum number, the minimum number and the mean number of the necessary exhausted MSBs were provided in [27] by large amounts of experiments. From Table 4 we can see, 20-MSB exhaustion is needed to attain the bound $\delta \le 0.291$ in [29] while the mean number of necessary exhausted MSBs to attain the bound $\delta \le 0.290$ is 23.8 in [27]; our estimations show that 24-MSB exhaustion is needed to attain the bound $\delta \le 0.2903$, roughly the same as [27]. This implies that our estimation is reasonable and more consistent with implementations than [29].

Table 4 Partial corresponding relation between $\delta$ and s given in [27, 29] and ours with $m=7,t=3$

4.3 A new practical attack based on the binary search

When implementing our practical small private exponent attack on RSA, some interesting and nontrivial phenomena appear: (I) besides $p_{m}$ and $q_{m}$, the real values of the MSBs of p and q, a value close to $p_{m}$ or $q_{m}$ can also help to attack RSA successfully in the exhaustion process; (II) these additional exhaustive values appear continuously around $p_{m}$ and $q_{m}$ (the word “continuously” here means continuous integral point in the interval); (III) the closer p and q are, the more additional exhaustive values there will be. We call the above phenomena the “multivalued-continuous phenomena”. The multivalued-continuous phenomena immediately inspire us a new attack based on the binary search. That is, to complete the attack effectively, we can try the binary search for the MSBs of p in the exhausted space. The binary search means that we need neither to go through the exhausted space from the smallest value to the largest ineffectively to find the real values of $p_{m}$ and $q_{m}$, nor to know the exact amount of these values close to $p_{m}$ and $q_{m}$ who can help to attack RSA successfully. What we should do is just to efficiently find one of such values. Our experiments have verified the correctness and effectiveness of our algorithm based on the binary search.

4.3.1 The multivalued-continuous phenomena

At first we give a necessary lemma, which will be helpful to prove the multivalued-continuous phenomena.

Lemma 5

Let

$$\begin{aligned} h(x)=x+\Bigg \lfloor \Bigg \lfloor \frac{N}{bx+b/2}\Bigg \rfloor /b\Bigg \rfloor -c, \end{aligned}$$

where x is a non-negative integer and N, b, c are positive integers. Then

$$\begin{aligned} h(x)\le h(x-1)&\text { if }\text { } 1 \le x \le \Bigg \lfloor \sqrt{\frac{N}{b^2}+\frac{1}{4}}\Bigg \rfloor ; \text {and}\\ h(x)\ge h(x-1)&\text { if }\text { } x \ge \Bigg \lceil \sqrt{\frac{N}{b^2}+\frac{1}{4}}\Bigg \rceil . \end{aligned}$$

Proof

If $1 \le x \le \Bigg \lfloor \sqrt{\frac{N}{b^2}+\frac{1}{4}}\Bigg \rfloor$, then $N\ge b^2(x+1/2)(x-1/2)$, and so

$$\begin{aligned} \frac{N}{b(x-1)+b/2}-\frac{N}{bx+b/2}=\frac{Nb}{(bx+b/2)(b(x-1)+b/2)}=\frac{Nb}{b^2(x+1/2)(x-1/2)}\ge b. \end{aligned}$$

We note that $\big \lfloor u\big \rfloor -\big \lfloor v\big \rfloor \ge w$ naturally holds for any positive real numbers u, v and positive integer w with $u-v\ge w$. Therefore, we have

$$\begin{aligned} \Bigg \lfloor \frac{N}{b(x-1)+b/2}\Bigg \rfloor -\Bigg \lfloor \frac{N}{bx+b/2}\Bigg \rfloor \ge b, \end{aligned}$$

and hence

$$\begin{aligned} \Bigg \lfloor \frac{N}{b(x-1)+b/2}\Bigg \rfloor /b-\Bigg \lfloor \frac{N}{bx+b/2}\Bigg \rfloor /b \ge 1, \end{aligned}$$

which implies that

$$\begin{aligned} \Bigg \lfloor \Bigg \lfloor \frac{N}{b(x-1)+b/2}\Bigg \rfloor /b\Bigg \rfloor -\Bigg \lfloor \Bigg \lfloor \frac{N}{bx+b/2}\Bigg \rfloor /b\Bigg \rfloor \ge 1. \end{aligned}$$

Note that

$$\begin{aligned} h(x-1)-h(x)&=x-1+\Bigg \lfloor \Bigg \lfloor \frac{N}{b(x-1)+b/2}\Bigg \rfloor /b\Bigg \rfloor -x-\Bigg \lfloor \Bigg \lfloor \frac{N}{bx+b/2}\Bigg \rfloor /b\Bigg \rfloor \\&=\Bigg \lfloor \Bigg \lfloor \frac{N}{b(x-1)+b/2}\Bigg \rfloor /b\Bigg \rfloor -\Bigg \lfloor \Bigg \lfloor \frac{N}{bx+b/2}\Bigg \rfloor /b\Bigg \rfloor -1. \end{aligned}$$

Therefore, $h(x)\le h(x-1)$ holds if $1 \le x \le \Bigg \lfloor \sqrt{\frac{N}{b^2}+\frac{1}{4}}\Bigg \rfloor$.

If $x \ge \Bigg \lceil \sqrt{\frac{N}{b^2}+\frac{1}{4}}\Bigg \rceil$, then $N\le b^2(x+1/2)(x-1/2)$, and so

$$\begin{aligned} \frac{N}{b(x-1)+b/2}-\frac{N}{bx+b/2}=\frac{Nb}{b^2(x+1/2)(x-1/2)}\le b. \end{aligned}$$

With a similar discussion as above, we can get $h(x)\ge h(x-1)$. This completes the proof. $\square$

Remark 4

It is not difficult to see that, for $x\ge 1$,

$$\begin{aligned} h(x)-h(x-1)=\Bigg \lfloor \Bigg \lfloor \frac{N}{bx+b/2}\Bigg \rfloor /b\Bigg \rfloor -\Bigg \lfloor \Bigg \lfloor \frac{N}{b(x-1)+b/2}\Bigg \rfloor /b\Bigg \rfloor +1\le 1 \end{aligned}$$

since $\frac{N}{bx+b/2}<\frac{N}{b(x-1)+b/2}$. Then combining with Lemma 5 we can conclude that: if $x \ge \Bigg \lceil \sqrt{\frac{N}{b^2}+\frac{1}{4}}\Bigg \rceil$, then $0\le h(x)-h(x-1)\le 1$.

Let us consider the case where $p_{m}$ is known. Let $A^{\prime }=N+1-(p_{m}+q_{m})\cdot 2^{\eta -s}$. Then

$$\begin{aligned} ed-1=x^{\prime }(A^{\prime }+y^{\prime }) \end{aligned}$$

(9)

obviously holds if $y^{\prime }=-(p_{l}+q_{l}),\,x^{\prime }=k$. Without loss of generality, we assume ${s>2}$ and the value of s we choose will make sure that d can be correctly recovered based on Eq. (9).

Let $\tilde{p}_{m}$ be a guess value of $p_{m}$. Since the MSB of p is 1, we can assume that $2^{s-1}\le \tilde{p}_{m}<2^{s}$. Then by Lemma 4,

$$\begin{aligned} \tilde{q}_{m}=\Bigg \lfloor \Bigg \lfloor \frac{N}{\tilde{p}_{m}\cdot 2^{\eta -s}+2^{\eta -s-1}}\Bigg \rfloor /2^{\eta -s}\Bigg \rfloor \end{aligned}$$

(10)

is a good approximation of $q_{m}$. Let

$$\begin{aligned} \Delta (x)= x+\Bigg \lfloor \Bigg \lfloor \frac{N}{bx+b/2}\Bigg \rfloor /b\Bigg \rfloor -(p_{m}+q_{m}), \,x\in [2^{s-1},2^{s}), \end{aligned}$$

(11)

where $b=2^{\eta -s}$. It is clear that $\Delta (\tilde{p}_{m})=(\tilde{p}_{m}+\tilde{q}_{m})-(p_{m}+q_{m})$. Let

$$\begin{aligned} \tilde{p}_{l}=p-\tilde{p}_{m}\cdot 2^{\eta -s}, \tilde{q}_{l}=q-\tilde{q}_{m}\cdot 2^{\eta -s} \text { and } A^{\prime \prime }=N+1-(\tilde{p}_{m}+\tilde{q}_{m})\cdot 2^{\eta -s}. \end{aligned}$$

Then

$$\begin{aligned} ed-1=x^{\prime \prime }(A^{\prime \prime }+y^{\prime \prime }) \end{aligned}$$

(12)

obviously holds if $y^{\prime \prime }=-(\tilde{p}_{l}+\tilde{q}_{l}),\,x^{\prime \prime }=k$.

In our experiments, we find that there are some other guess values except $p_{m}$ and $q_{m}$ that can help to correctly recover d. The reason why these guess values exist may come from two aspects. The first one is that in most cases there exist some additional $\tilde{p}_{m}$ besides $p_{m}$ and $q_{m}$ such that $\Delta (\tilde{p}_{m})=0$ (i.e., $\tilde{p}_{m}+\tilde{q}_{m}={p}_{m}+{q}_{m}$), which implies that Eq. (12) is the same as Eq. (9). In this case d can be correctly recovered based on Eq. (12). The second one is that the bound in Condition (1) of Lemma 2 is not so tight. In other words, in practical cases, when the values of some variables slightly exceed their presupposed upper bounds and other conditions remain unchanged, $g(\tilde{x}_{1},...,\tilde{x}_{r})=0$ may still hold over ${\mathbb {Z}}$. This means that, in our experiments, even if $\vert \Delta (\tilde{p}_{m})\vert$ is slightly larger than 0, the private exponent d may be correctly recovered based on Eq. (12), though the value of $\vert -(\tilde{p}_{l}+\tilde{q}_{l})\vert$ may exceed its presupposed upper bound $2^{\eta -s}=N^{\frac{1}{2}-\xi }$.

From the discussion above, if d can be correctly recovered based on Eq. (12), the practical small private exponent attack will be successful. For convenience, a guess value $\tilde{p}_{m}$ that can help to realize a successful small private exponent attack on RSA is called a helpful guess value. A pair ($\tilde{p}_{m}$, $\tilde{q}_{m}$) is called a helpful guess pair if $\tilde{p}_{m}$ is a helpful guess value. Such a set which consists of all the helpful guess values is called the Helpful Guess Set, denoted by $\Omega$. Note that the parameter s we choose will guarantee that d can be correctly recovered based on Eq. (9). Therefore, we have $\{p_{m},q_{m}\}\subseteq \Omega$.

In order to present a better understanding of the “continuous” property, we need a heuristic assumption as follows.

Assumption 3

There exist two largest non-negative integers $\rho _{1}$ and $\rho _{2}$ such that: if $-\rho _{1}\le \Delta (\tilde{p}_{m})\le \rho _{2}$, then the private exponent d can be correctly recovered based on Eq. (12) by the CopperSmith method with the help of the LLL algorithm and resultants computation.

Our experiments imply that $\rho _{1}$ and $\rho _{2}$ are small integers, which are closely related to specific experimental instances (i.e., $N,e,\delta$), the dimension of the lattice constructed with the CopperSmith method and the ability of the LLL algorithm.

Now we give a strict statement of the “multivalued-continuous” phenomena, which is stated as follows.

Theorem 1

Let $\Omega$ denote the Helpful Guess Set. Let $\Delta (x)$ be defined as (11) and $\rho _{1}$, $\rho _{2}$ be the same as Assumption 3. Let $p_{min}\in [2^{s-1},2^{s})\cap {\mathbb {Z}}$ satisfying that $\Delta (p_{min})=\min \{\Delta (x)\mid x\in [2^{s-1},2^{s})\cap {\mathbb {Z}} \}$.

• (I) If $\Delta (p_{min})\ge -\rho _{1}$, then there exist two integers $a_{1}\le a_{2}$ such that $\{a_{1},a_{1}+1, \ldots , a_{2}\}\subseteq \Omega$, where $a_{1}$, $a_{2}$ can be uniquely determined by $\rho _{2}$ satisfying that

  $$\begin{aligned} \Delta (a_{1})\le \rho _{2}<\Delta (a_{1}-1), \,\Delta (a_{2})=\rho _{2}<\Delta (a_{2}+1). \end{aligned}$$

• (II) If $\Delta (p_{min})<-\rho _{1}$, then there exist four integers $b_{1}\le b_{2}<b_{3}\le b_{4}$ such that $\{b_{1},b_{1}+1,\ldots ,b_{2}\}\cup \{b_{3},b_{3}+1,\ldots ,b_{4}\}\subseteq \Omega$, where $b_{1}, b_{2}, b_{3}, b_{4}$ can be uniquely determined by $\rho _{1}$, $\rho _{2}$ satisfying that

  $$\begin{aligned}{} & {} \Delta (b_{1})\le \rho _{2}<\Delta (b_{1}-1),\,\Delta (b_{4})=\rho _{2}<\Delta (b_{4}+1),\\{} & {} \Delta (b_{2}+1)<-\rho _{1}\le \Delta (b_{2}), \,\Delta (b_{3}-1)<\Delta (b_{3})=-\rho _{1}. \end{aligned}$$

Proof

We note first that by Remark 4, for an arbitrary integer $\rho$ between $\Delta \left( \Bigg \lceil \sqrt{\frac{N}{b^2}+\frac{1}{4}}\Bigg \rceil \right)$ and $\Delta \left( 2^{s}-1\right)$, there exists at least one guess value $\tilde{p}_{m_{\rho }}$ such that $\Delta (\tilde{p}_{m_{\rho }})=\rho$.

Fig. 1

A simple visualization of the two cases in the proof of Theorem 1

Case I $\Delta (p_{min})\ge -\rho _{1}$.

Let $p_{m}, p_{l}, q_{m}, q_{l}$ be the same meanings as above and $b=2^{\eta -s}$. Note that $p_{m}\ge q_{m}$. Since

$$\begin{aligned} \frac{N}{b^2}+\frac{1}{4} > \frac{N}{b^2}=\frac{(p_{m}b+p_{l})(q_{m}b+q_{l})}{b^2}\ge \frac{b^2 q_{m}^2}{b^2}=q_{m}^2, \end{aligned}$$

it can be seen that $q_{m}\le \Bigg \lfloor \sqrt{\frac{N}{b^2}+\frac{1}{4}}\Bigg \rfloor$. Note that $-\rho _{1} \le \Delta (q_{m}) \le \rho _{2}$ since the value of s we choose will guarantee the success of our attack. Therefore, according to Lemma 5, if $\Delta (2^{s-1})> \rho _{2}$, then there must exist an integer $a_{1}\le \Bigg \lfloor \sqrt{\frac{N}{b^2}+\frac{1}{4}}\Bigg \rfloor$ such that

$$\begin{aligned} \Delta (a_{1})\le \rho _{2}<\Delta (a_{1}-1). \end{aligned}$$

(13)

Meanwhile, according to Lemma 5 and the discussion at the beginning of this proof, if $\Delta (2^{s}-1)> \rho _{2}$, there must exist an integer $a_{2} \ge \Bigg \lceil \sqrt{\frac{N}{b^2}+\frac{1}{4}}\Bigg \rceil$ such that $\Delta (a_{2})=\rho _{2}<\Delta (a_{2}+1)$. For $\beta \in [a_{1},a_{2}]\cap {\mathbb {Z}}$, we have

$$\begin{aligned} -\rho _{1} \le \Delta (p_{min})\le \Delta (\beta )\le \max \{\Delta (a_{1}),\Delta (a_{2})\} = \rho _{2}. \end{aligned}$$

Therefore, according to Assumption 3, for any $\beta \in [a_{1},a_{2}]\cap {\mathbb {Z}}$, the private exponent d can be correctly recovered based on Eq. (12).

If $\Delta (2^{s-1}) \le \rho _{2}$ or $\Delta (2^{s}-1)\le \rho _{2}$, we can take $a_{1}=2^{s-1}$ or $a_{2}=2^{s}-1$ and get the same conclusion. A simple visualization of this case can be seen in Case I of Fig. 1.

To finish the proof of Case I, it suffices to show the uniqueness of $a_{1}$ and $a_{2}$. Suppose there exists another integer $a^{\prime }_{1} \le \Bigg \lfloor \sqrt{\frac{N}{b^2}+\frac{1}{4}}\Bigg \rfloor$ such that

$$\begin{aligned} \Delta (a^{\prime }_{1})\le \rho _{2}<\Delta (a^{\prime }_{1}-1). \end{aligned}$$

(14)

If $a^{\prime }_{1}\ge a_{1}+1$, then it follows from Lemma 5 and Eqs. (13) and (14) that $\Delta (a^{\prime }_{1}-1)\le \Delta (a_{1})\le \rho _{2}<\Delta (a^{\prime }_{1}-1)$, a contradiction; if $a^{\prime }_{1}\le a_{1}-1$, we can get that $\Delta (a^{\prime }_{1})\ge \Delta (a_{1}-1)> \rho _{2}\ge \Delta (a^{\prime }_{1})$, still a contradiction. As a result, it must hold that $a^{\prime }_{1}=a_{1}$. The uniqueness of $a_{2}$ can be proved similarly.

Case II $\Delta (p_{min})< -\rho _{1}$.

If $\Delta (2^{s-1})> \rho _{2}$ and $\Delta (2^{s}-1)> \rho _{2}$, with a similar discussion as Case I, we can find $b_{1}\le b_{2}< p_{min}< b_{3}\le b_{4}$ such that

$$\begin{aligned}{} & {} \Delta (b_{1})\le \rho _{2}<\Delta (b_{1}-1),\,\Delta (b_{4})=\rho _{2}<\Delta (b_{4}+1),\\{} & {} \Delta (b_{2}+1)<-\rho _{1}\le \Delta (b_{2}), \,\Delta (b_{3}-1)<\Delta (b_{3})=-\rho _{1}. \end{aligned}$$

For any $\beta \in \{[b_{1},b_{2}]\cap {\mathbb {Z}}\}\cup \{[b_{3},b_{4}]\cap {\mathbb {Z}}\}$, according to Lemma 5, we have

$$\begin{aligned} -\rho _{1}= \min \{\Delta (b_{2}), \Delta (b_{3})\} \le \Delta (\beta )\le \max \{\Delta (b_{1}),\Delta (b_{4})\} = \rho _{2}. \end{aligned}$$

If $\Delta (2^{s-1})\le \rho _{2}$ or $\Delta (2^{s}-1)\le \rho _{2}$, we can take $b_{1}=2^{s-1}$ or $b_{4}=2^{s}-1$ and get the same conclusion.

A simple visualization of this case can be seen in Case II of Fig. 1.

Similarly, the uniqueness of $b_{1},b_{2}, b_{3},b_{4}$ can be proved as Case I. This completes the proof of Theorem 1. $\square$

Table 5 Experimental presentation of the multivalued-continuous phenomena for $\delta \le 0.292$

In order to give a more intuitive presentation of the phenomena, we provide partial specific experimental data in Table 5. As shown in Table 5, when $\vert \Delta (\tilde{p}_{m})\vert$ is slight greater than 0, such $\tilde{p}_{m}$ may still be a helpful guess value. For the first specific (p, q, d), the set $\Omega$ contains two continuous intervals over ${\mathbb {Z}}$. For example, when $(m,t,s)=(7,3,27)$, we find 38 helpful guess values which appear as two parts around $p_{m}=108904923$ and $q_{m}=77936267$ respectively. For the second specific (p, q, d), the set $\Omega$ contains one continuous interval over ${\mathbb {Z}}$. For example, when $(m,t,s)=(12,5,19)$, we find 2093 helpful guess values which appear as a continuous integer interval including $p_{m}=265700$ and $q_{m}=265446$.

Another phenomenon should be mentioned that there are much more helpful guess values when p is close to q in our experiments (one of the detailed comparison can be seen in Table 5, noting that the first $\vert p-q \vert$ is much greater than the second one). The “p close to q” contributes to the efficiency of our experiments pretty well. It must be mentioned that the use of “p close to q” in our attack is quite different from the attacks with small prime difference in [9]. In [9], p and q should share tens or even hundreds of MSBs to effectively implement the Fermat factoring attack or the extension of the Wiener attack, while in our attack, a significant improvement can be get when p and q share only several bits (detailed results, see Tables 9 and 10); for the extension of the Boneh-Durfee attack, the upper bound of $\vert p-q \vert$ should be known ahead, since the information of $\Delta =p-q$ will be used in the improved lattice, while in our attack, without knowing how close between p and q in advance, our new method will make good use of the hidden information of $p-q$ to complete the attack.

4.3.2 A new practical attack based on the binary search

Based on the multivalued-continuous phenomena, we propose a new practical small private exponent attack on RSA based on the binary search. The complete and detailed algorithm is displayed as follows.

Algorithm 1: New practical attack based on the binary search
Input: $N,e,\delta ;m,t,s$
Output: $p,q,d$
0 $\eta \leftarrow \lfloor \log _{2}p \rfloor$
1 for $j := 1,\cdots ,s-1$
2for $i :=1,\cdots ,2^{j-1}$
3 $\ \ \ \ \ \ \tilde{p}_{m}\leftarrow 2^{s-1}+(2i-1)\cdot 2^{s-1-j};$
4$\ \ \ \ \ \tilde{q}_{m}\leftarrow \left\lfloor \left\lfloor \frac{N}{\tilde{p}_{m}\cdot 2^{\eta -s}+2^{\eta -s-1}}\right\rfloor /2^{\eta -s}\right\rfloor$;
5$\ \ \ \ \ \ A\leftarrow N+1-(\tilde{p}_{m}+\tilde{q}_{m})\cdot 2^{\eta -s}$;
6 $\ \ \ \ \ \ Y\leftarrow \left\lfloor \sqrt{N}/2^{s}\right\rfloor$, $X\leftarrow N^{\delta }$, $U\leftarrow \left\lfloor \sqrt{N}/2^{s}\right\rfloor \cdot N^{\delta }$;
7 Run HM2010 attack with bounds in step 6;
8if d is correctly found then
9return d, p, q;
10end if
11end for
12 end for

We note that, the efficiency of Algorithm 1 relies on its input parameters m, t, s. Then a question may come up immediately that how should we choose appropriate m, t and s in order to attack the RSA cryptosystem efficiently.

According to our experiments and Miller’s discussion in [19], BKZ reduction algorithm doesn’t perform well in the HM2010 attack. Therefore, we adopt LLL algorithm in SageMath to carry out the lattice basis reduction in our attack.

It is not difficult to see that the total running time of our attack mainly comes from two parts: the search of a helpful guess value and the lattice basis reduction. In the following of this subsection, we first focus on the cost of LLL algorithm, and then discuss how to find appropriate m, t and s based on some theoretical derivation and experimental results.

The time complexity of LLL algorithm and its variants is displayed below (the vector length, the number of basis vectors, the size of vector norm are denoted by n, d, B respectively).

LLL (1982) [16]	LLL (Schnorr 1988) [28]	$L^{2}$ (Nguyen 2005) [20]
$O(d^{5}nB^{3})$	$O(d^{3}n(d+B)^{2}B)$	$O(d^{4}n(d+B)B)$

Making a specific analysis on the lattice we constructed, we get

$$\begin{aligned} n=d=\dim L^{\prime }=\frac{(m+1)(m+2)}{2}+\frac{\tau m^{2}+(2\tau -1)m}{2}. \end{aligned}$$

(15)

The size of the vector norm B is given by the following Proposition 1.

Proposition 1

With the notations as above, the approximate size of the largest vector norm B in our new lattice is $(m+\delta m+(\frac{1}{2}-\xi )\tau m)\log N$, where $2^{s}=N^{\xi }$.

Proof

See Appendix B.

It is not difficult to see that, the approximation size of B in Proposition 1 changes very little with s, since s is at most several dozens and the size of N is more than 1000 bits in our experiments. Note that the optimal t is determined and so is the parameter $\tau$ since $\tau =t/m$ for a fixed m. Therefore, based on Eq. (15) and Proposition 1, the dimension remains unchanged and vector norm B is almost unchanged for fixed m. Above all, no matter whether MSBs guess strategy is added to HM2010 attack or not, the running time of the LLL algorithm is nearly unchanged, which is consistent with the results of our experiments.

Now we can try to determine the parameters m, t, s. Several groups of experiments are implemented and one of them is displayed in Table 6. The set $\Omega$ consists of two consecutive parts and the amount of helpful guess values is the sum of the two parts. For the same m and t, as s increases by 1, the amount of helpful guess values is less than twice as the original ones (all our experiments have verified the conclusion). This result indicates that the guess bit should try as few as possible. Meanwhile, after a simple computation we can conclude that an appropriately large m will reduce the total running time of our new attack. As can be seen from Table 1, when m increases continuously the improvement effect of upper bound of $\delta$ is less and less significant. Therefore, we would like to choose a medium m for our attack.

Table 6 Helpful guess values and running time with different m, t, s for a specific p, q, d

From the discussion above, to get a practical bound $\delta \le 0.292$ for 1024-bit-modulus RSA, the recommended parameters we provide are $m=12,t=5,s=18$. The reason why we don’t recommend $s=17$ is that the success rate cannot be guaranteed both from the estimation in Table 3 and the experimental results in Table 8. These parameters may not be the optimal ones, but they can help to implement our new attack very well to recover the private exponent for RSA with a 1024-bit modulus. With the same discussion, for 2048-bit-modulus RSA, the recommended parameters we provide are $m=12,t=5,s=19$ to attain the bound $\delta \le 0.287$.

5 Experiments

All our experiments are implemented in SageMath 9.1 on our PC with Intel(R) Xeon(R) W-2255 CPU (3.70GHz, 160GB RAM Windows 10). The codes of experiments which are shown in Tables 7, 9 and 10 can be seen in https://pastebin.com/zpUkrfDh.

We carry out some experiments to research the practical bound of $\delta$ based on HM2010 attack at first. Our experimental results on the upper bound of $\delta$ and some comparison with [1, 3, 10, 19] are provided in Table 7.

Table 7 Our experimental results on the upper bound of $\delta$ and some comparison with [1, 3, 10, 19]

It should be made clear that the upper bound of $\delta$ we get in Table 7 is just based on HM2010 attack. We implement 100 experiments for the bound 0.284. And for the bound 0.285, 5 experiments have been done since the running time is too long. From the experiments, we get a nice bound within a month with a reasonable success rate. Moreover, for a no-less-than-1000-bit modulus N, this bound is the best practical one within a month for this kind of attacks as far as we know.

In order to investigate the necessary number of exhausted MSBs that can guarantee the success of the attack, we implement some experiments to verify the estimations for $\delta =0.292$ in Tables 2 and 3, which is displayed in Table 8. As can be seen in Table 8, when $m=7$, we should choose $s=27$ considering the comparison of success rates; similarly, when $m=12$, s should be chosen to 18 for the same reason.

Table 8 Experimental comparison of success rates with $\delta =0.292, 2\eta =1024$ when $m=7$ and $m=12$

Based on Algorithm 1, we implement our new practical attack. The results are shown in Table 9 below.

Table 9 Experimental results of our new practical attack on RSA with $d\le N^{0.292}$ for 1024-bit moduli

All the three experiments above successfully recover the private exponent of 1024-bit-modulus RSA with $d\le N^{0.292}$ within a month, which is certainly an acceptable running time for a practical attack on a cryptosystem. The validity of our algorithm and the rationality of the recommended parameters are verified by the success of the experiments. As we can see from Table 9, the helpful guess value $\tilde{p}_{m}$ who contributes to the recovery of the private exponent actually does not equal to $p_{m}$. It needs still long to reach the real value $p_{m}$ by the binary search. The smaller $\vert p-q \vert$ is, the more helpful guess values there will be, thus leads to a shorter total running time. Detailed parameters of the three experiments are shown in Appendix C.

As can be seen in [27], to implement an experiment for $\delta \approx 0.285$ with a 1000-bit modulus, they need about a week with a cluster of 26 machines. While in our implementations for $\delta \approx 0.292$ with a 1024-bit modulus, we can successfully complete them in about 3 weeks with a single PC. Particularly, the running time may reach several hours when p is appropriately close to q (e.g., p shares just several MSBs with q in Exp. 1 in Table 9).

At last, we apply Algorithm 1 to a 2048-bit-modulus RSA. The improving effect of upper bound of $\delta$ is not so good as the 1024-bit one since the proportion $s/\log _{2}N$ decreases for the same amount of guess bits. Moreover, the running time becomes about triple longer since the data size B in LLL reduction is twice as the original. Three experiments are carried out for 2048-bit-modulus RSA, which are displayed in Table 10.

Table 10 Experimental results of our new practical attack on RSA with 2048-bit moduli

From Table 10 we can see that, for random primes p and q (such as p, q in Exp. 5), a majority of the 2048-bit-modulus RSA can be successfully attacked in about a month for $\delta \le 0.287$; if p is slightly close to q (e.g., in Exp. 4, p, q share 3 MSBs), the efficiency will be better than random case; while p is quite close to q (e.g., in our setting in Exp. 6, p and q 50 MSBs), we can effectively recover the private exponent when $\delta \le 0.292$. Detailed parameters can be seen in Appendix D.

6 Conclusion

In this paper, we focus on the practical small private exponent attack on RSA. After some detailed and relatively exact calculations of related parameters in the lattice determinant, we give a few precise estimations about the upper bound of solvable $\delta$ based the experimental LLL estimation by Nguyen et al.. With the instruction of our estimations, we implement the HM2010 attack and get a bound $\delta \le 0.285$ for a 1024-bit-modulus RSA within a month, which is better than the former results as far as we know. To improve the bound we can achieve by the HM2010 attack, we add a simple idea of the MSBs guess of p. Based on the nontrivial and inspiring multivalued-continuous phenomena, we propose a new attack based on the binary search and succeed to attack the 1024-bit-modulus RSA cryptosystem for $\delta \le 0.292$. Additionally, a slightly weaker result $\delta \le 0.287$ can be obtained after applying our new attack to 2048-bit-modulus RSA, which is also the best one among this kind of attacks as far as we know.

Furthermore, there are still some questions to be answered. Since the number of helpful guess values has close relation to the value of $\vert p-q \vert$ from the experiments, how should we exactly understand the relationship? How can we estimate the lower bound of the size of $\Omega$? As the effect of our new attack turns weak in a 2048-bit-modulus RSA attack, what else should we try to break through the 0.292 bound for a mainstream practical RSA? Although the gaps still exist, we believe our attack can provide some inspiration to search more practical attacks on RSA.

Appendices

Appendix A: Proof of Lamma 3

Proof

Take $\tau =t/m$, then we have

$$\begin{aligned} s_{X}= & {} \sum _{k=0}^{m}\sum _{i=0}^{m-k}i=\sum _{k=0}^{m}\frac{(m-k)(m-k+1)}{2} \\= & {} \frac{1}{2}\sum _{k=0}^{m}\left( m(m+1)-(2m+1)k+k^{2}\right) \\= & {} \frac{1}{2}\left( m(m+1)^{2}-(2m+1)\frac{m(m+1)}{2}+\frac{m(m+1)(2m+1)}{6} \right) \\= & {} \frac{m(m+1)(m+2)}{6}, \\ s_{Y}= & {} \sum _{j=1}^{\tau m}\sum _{k=\big \lfloor \frac{1}{\tau } \big \rfloor j}^{m}j=\sum _{j=1}^{\tau m}j\left( m-\Bigg \lfloor \frac{1}{ \tau }\Bigg \rfloor j+1\right) \\= & {} \sum _{j=1}^{\tau m}(m+1)j-\sum _{j=1}^{\tau m}\Bigg \lfloor \frac{1}{\tau } \Bigg \rfloor j^{2} \\= & {} \frac{(m+1)\tau m(\tau m+1)}{2}-\Bigg \lfloor \frac{1}{\tau }\Bigg \rfloor \cdot \frac{\tau m(\tau m+1)(2\tau m+1)}{6} \\\approx & {} \frac{(m+1)\tau m(\tau m+1)}{2}-\frac{1}{\tau }\cdot \frac{\tau m(\tau m+1)(2\tau m+1)}{6} \\= & {} \frac{\tau ^{2}m^{3}+3\tau ^{2}m^{2}+3\tau m-m}{6}, \\ s_{U}= & {} \sum _{k=0}^{m}\sum _{i=0}^{m-k}k+\sum _{j=1}^{\tau m}\sum _{k=\big \lfloor \frac{1}{\tau }\big \rfloor j}^{m}k \\= & {} \sum _{k=0}^{m}k(m-k+1)+\sum _{j=1}^{\tau m}\frac{\left( m+\Bigg \lfloor \frac{1}{\tau }\Bigg \rfloor j\right) \left( m-\Bigg \lfloor \frac{1}{\tau } \Bigg \rfloor j+1\right) }{2} \\\approx & {} \sum _{k=0}^{m}k(m-k+1)+\sum _{j=1}^{\tau m}\frac{(m+\frac{1}{\tau } j)(m-\frac{1}{\tau }j+1)}{2} \\= & {} \sum _{k=0}^{m}k(m+1)-\sum _{k=0}^{m}k^{2}+\frac{1}{2}\sum _{j=1}^{\tau m}(m+ \frac{1}{\tau }j)(m-\frac{1}{\tau }j+1) \\= & {} \sum _{k=0}^{m}k(m+1)-\sum _{k=0}^{m}k^{2}+\frac{1}{2}\sum _{j=1}^{\tau m}\left( m(m+1)+\frac{1}{\tau }j-\frac{1}{\tau ^{2}}j^{2}\right) \\= & {} \frac{m(m+1)^{2}}{2}-\frac{m(m+1)(2m+1)}{6} \\{} & {} +\frac{1}{2}\left( m(m+1)\tau m+\frac{\tau m(\tau m+1)}{2\tau }-\frac{\tau m(\tau m+1)(2\tau m+1)}{6\tau ^{2}}\right) \\= & {} \frac{m(m+1)(m+2)}{6}+\frac{(4\tau ^{2}m^{3}+(9\tau ^{2}-3\tau )m^{2}+(3\tau -1)m)}{12\tau } \\= & {} \frac{(4\tau ^{2}+2\tau )m^{3}+(9\tau ^{2}+3\tau )m^{2}+(7\tau -1)m}{ 12\tau },\\ s_{e}= & {} \sum _{k=0}^{m}\sum _{i=0}^{m-k}(m-k)+\sum _{j=1}^{\tau m}\sum _{k=\big \lfloor \frac{1}{\tau }\big \rfloor j}^{m}(m-k) \\= & {} \sum _{k=0}^{m}(m-k)(m-k+1) \\{} & {} +\sum _{j=1}^{\tau m}\left( m\left( m-\Bigg \lfloor \frac{1}{\tau }\Bigg \rfloor j+1\right) -\frac{\left( m+\Bigg \lfloor \frac{1}{\tau }\Bigg \rfloor j\right) \left( m-\Bigg \lfloor \frac{1}{\tau }\Bigg \rfloor j+1\right) }{2}\right) \\\approx & {} \sum _{k=0}^{m}(m-k)(m-k+1) \\{} & {} +\sum _{j=1}^{\tau m}\left( m\left( m-\frac{1}{\tau }j+1\right) -\frac{\left( m+\frac{1}{\tau } j\right) \left( m-\frac{1}{\tau }j+1\right) }{2}\right) \\= & {} \sum _{k=0}^{m}(m(m+1)-(2m+1)k+k^{2})+\frac{1}{2}\sum _{j=1}^{\tau m}\left( \left( m-\frac{1}{\tau }j\right) \left( m-\frac{1}{\tau }j+1\right) \right) \\= & {} m(m+1)^{2}-\frac{(2m+1)m(m+1)}{2}+\frac{m(m+1)(2m+1)}{6} \\{} & {} +\sum _{j=1}^{\tau m}\left( m(m+1)-(2m+1)\frac{1}{\tau }j+\frac{1}{\tau ^{2} }j^{2}\right) \\= & {} \frac{m(m+1)(m+2)}{3} \\{} & {} +\frac{1}{2}\left( m(m+1)\tau m-\frac{(2m+1)\tau m(\tau m+1)}{2\tau }+ \frac{\tau m(\tau m+1)(2\tau m+1)}{6\tau ^{2}}\right) \\= & {} \frac{m(m+1)(m+2)}{3}+\frac{2\tau ^{2}m^{3}+(3\tau ^{2}-3\tau )m^{2}-(3\tau -1)m}{12\tau }, \\ \dim L= & {} \sum _{k=0}^{m}\sum _{i=0}^{m-k}1+\sum _{j=1}^{\tau m}\sum _{k=\big \lfloor \frac{1}{\tau }\big \rfloor j}^{m}1 \\= & {} \sum _{k=0}^{m}(m-k+1)+\sum _{j=1}^{\tau m}\left( m-\Bigg \lfloor \frac{1}{ \tau }\Bigg \rfloor j+1\right) \\\approx & {} \sum _{k=0}^{m}(m-k+1)+\sum _{j=1}^{\tau m}\left( m-\frac{1}{\tau } j+1\right) \\= & {} (m+1)^{2}-\frac{m(m+1)}{2}+\tau m(m+1)-\frac{1}{\tau }\cdot \frac{\tau m(\tau m+1)}{2} \\= & {} \frac{(m+1)(m+2)}{2}+\frac{\tau m^{2}+(2\tau -1)m}{2}. \end{aligned}$$

The proof of Lamma 3 has completed. $\square$

Appendix B: Proof of Proposition 1

Proof

It must be pointed out that the largest size of the vector norm B can be perfectly approximated by the maximum component of all the vectors in the lattice basis, e.g., the maximum coefficient of the term in all the polynomials.

At first we compute B in the lattice of the HM2010 attack. Note that vectors are produced by x-shift polynomials and y-shift polynomials:

$$\begin{aligned} \tilde{g}_{i,k}(u,x)&=x^{i}\tilde{f}^{k}e^{m-k},\,i=0,\ldots ,m-k, \,k=0,\ldots ,m \\ \tilde{h}_{j,k}(u,x,y)&=y^{j}\tilde{f}^{k}e^{m-k},\,j=1,\ldots ,\tau m, \,k=\lfloor 1/\tau \rfloor j,\ldots ,m, \end{aligned}$$

where $\tilde{f}(u,x)=A+ux$ and $t=\tau m$.

(I) The size of the maximum coefficient in ${\varvec{x}}$ -shift polynomials

Note that

$$\begin{aligned} \tilde{g}_{i,k}(u,x)=x^{i}\tilde{f}^{k}e^{m-k}=\sum \limits _{a=0}^{k}\left( {\begin{array}{c}k \\ a\end{array}}\right) x^{i}u^{a}A^{k-a}x^{k-a}e^{m-k}. \end{aligned}$$

Terms in $\tilde{g}_{i,k}(u,x)$ are of the form $\left( {\begin{array}{c}k\\ a\end{array}}\right) u^{a}A^{k-a}x^{k-a+i}e^{m-k}.$ The final coefficients of such terms (i.e., the values of vector components when constructing lattices) is $\left( {\begin{array}{c}k\\ a\end{array}}\right) U^{a}A^{k-a}X^{k-a+i}e^{m-k}$ with a size of

$$\begin{aligned} \left( a\left( \frac{1}{2}+\delta \right) +k-a+(k-a+i)\delta +m-k\right) \log N=\left( m- \frac{1}{2}a+(k+i)\delta \right) \log N. \end{aligned}$$

The size of the maximum coefficient is $\varvec{(m+m\delta )\log N}$ according to the formula above since $0\le a\le k<m,0\le k+i\le k+m-k=m.$

(II) The size of the maximum coefficient in ${\varvec{y}}$ -shift polynomials

Note that Terms in $\tilde{h}_{j,k}(u,x,y)$ is of the form $\left( {\begin{array}{c}k\\ b\end{array}}\right) y^{j}u^{b}A^{k-b}x^{k-b}e^{m-k}.$

Case A

When $j\ge k-b$,

$$\begin{aligned} \sum \limits _{b=0}^{k}\left( {\begin{array}{c}k\\ b\end{array}}\right) y^{j}u^{b}A^{k-b}x^{k-b}e^{m-k} = \sum \limits _{b=0}^{k}\left( {\begin{array}{c}k\\ b\end{array}}\right) y^{j-(k-b)}u^{b}A^{k-b}e^{m-k}(u-1)^{k-b}. \end{aligned}$$

Therefore, the term which has the maximum coefficient is $\left( {\begin{array}{c}k\\ b\end{array}}\right) y^{j-(k-b)}A^{k-b}u^{k}e^{m-k}$ with the final coefficient $\left( {\begin{array}{c}k\\ b\end{array}}\right) Y^{j-(k-b)}A^{k-b}U^{k}e^{m-k}.$ In this case the size of the maximum coefficient is

$$\begin{aligned} \left( \frac{1}{2}(j-(k-b))+k\left( \frac{1}{2}+\delta \right) +k-b+m-k\right) \log N=\left( \frac{1}{2}j-\frac{1}{2}b+\delta k+m\right) \log N. \end{aligned}$$

We get $\left( \frac{1}{2}j-\frac{1}{2}b+\delta k+m\right) \log N\le ( \frac{1}{2}j-\frac{1}{2}b+\delta j+\delta b+m)$ for $k\le j+b.$ Finally, the size of the maximum coefficient is $\varvec{(m+\tau \delta m+\frac{1}{2}\tau m)\log N}$ when $j=\tau m, b=0$ as $0\le b\le k\le m,1\le j\le \tau m.$

Case B

When $j< k-b$, after a similar discussion as Case A, we can get the size of the maximum coefficient in $y^{j}\tilde{f}^{k}e^{m-k}$ is

$$\begin{aligned} \left( (b+j)\left( \frac{1}{2}+\delta \right) +k-b+(k-b-j)\delta +m-k\right) \log N=\left( \frac{1}{2}j-\frac{1}{2}b+\delta k+m\right) \log N. \end{aligned}$$

Finally, since $j< k-b,0\le b\le k,1\le j\le \tau m,\lfloor 1/\tau \rfloor j\le k\le m$, the size of the maximum coefficient is $\varvec{(m+\delta m+ \frac{1}{2}\tau m)\log N}$ when $j=\tau m,b=0,k=m$.

According to the detailed discussion, we obtain that

$$\begin{aligned} B&=\max \left\{ (m+m\delta )\log N,\left( m+\tau \delta m+\frac{1}{2}\tau m\right) \log N,\left( m+\delta m+\frac{1}{2}\tau m\right) \log N\right\} \\&=\left( m+\delta m+\frac{1}{2}\tau m\right) \log N. \end{aligned}$$

At the second step we compute B in our lattice. Use the notations above, the upper bound of each variable becomes to

$$\begin{aligned} x^{\prime }< & {} X^{\prime }=N^{\delta },\,y^{\prime }<Y^{\prime }=N^{ \frac{1}{2}-\xi }, \\ e< & {} N,\,u^{\prime }<U^{\prime }=N^{\delta +\frac{1}{2}-\xi }, \end{aligned}$$

where $2^{s}=N^{\xi }$ and s is the amount of MSBs exhaustion. Note that the terms in the polynomials do not change while the bounds of variables differs comparing the lattice of HM2010 with ours. With a simple analysis as former, we can obtain the maximum sizes of coefficient in $x^{\prime }$-shift polynomials and $y^{\prime }$-shift polynomials are $(m+m\delta )\log N$ and $(m+\delta m+(\frac{1}{2}-\xi ) \tau m)\log N$. Finally we obtain $\varvec{B=(m+\delta m+(\frac{1}{2}-\xi )\tau m)\log N}.$

Based on the discussion above, we can see that the largest size of vector norm B is $\varvec{(m+\delta m+(\frac{1}{2}-\xi )\tau m)\log N}$. The proof of Proposition 1 has completed. $\square$

Appendix C: Detailed parameters of the three experiments in Table 9

Exp. 1

$N=$

$$\begin{aligned}{} & {} 46126089040452448339448600417060313922101098426244293259787635 \\{} & {} 87074530673491676174094741308570008991308086429133694253082502 \\{} & {} 08322979383825756505663848479411358228528222527395327435101891 \\{} & {} 24124500359010333442383692988340095271183825614638791911699269 \\{} & {} 162046275028679426500348785157345976662456325437259705160061 \end{aligned}$$

$e=$

$$\begin{aligned}{} & {} 36614584641331081308456049556562616703353184435474954472543851 \\{} & {} 64159874655507513240178939924241301243795285290427026969984191 \\{} & {} 93417336370186256151741426122690631967234543279797441311494545 \\{} & {} 48205774006091224643569311902728986446145416739772661245661572 \\{} & {} 872595702072188094041649860081717657262961694486055770442903 \end{aligned}$$

$p=$

$$\begin{aligned}{} & {} 67948679188399660033177882768593480036059591634701532395565550 \\{} & {} 86565666723761153014913169297896634069961179454031340099285043 \\{} & {} 376680194594851361518965438191 \end{aligned}$$

$q=$

$$\begin{aligned}{} & {} 67883716933716631074522673334050992083124031396996898938020837 \\{} & {} 71485358806632262195329165541096647967833821293875054198640528 \\{} & {} 209010624705809648621661183571 \end{aligned}$$

$d=$

$$\begin{aligned}{} & {} 68845001992677564960353986498476584008893082985088950620216788 \\{} & {} 3636867990095285712393863167 \end{aligned}$$

Exp. 2

$N=$

$$\begin{aligned}{} & {} 93502450932903310633064573151907317024294867669134678632093362 \\{} & {} 46297788099166895737544153127851852138932264560083819167132205 \\{} & {} 42943047406167744180006421454219231575086254775401435086568101 \\{} & {} 80893794178324182089403622394064939255883017451942933893424910 \\{} & {} 850870147643227272288485474147840684850717753717586472451201 \end{aligned}$$

$e=$

$$\begin{aligned}{} & {} 66858620224726705843141951973966747720864781039484831550691634 \\{} & {} 09294281451926768980157225811154880346715028924829626919171141 \\{} & {} 60786364943066431341308061576266724936876531701099477141597025 \\{} & {} 75928828432166081285992511952702707653041998543208057095834381 \\{} & {} 069598542543859865005532560613469773387993762913083830903645 \end{aligned}$$

$p=$

$$\begin{aligned}{} & {} 99518569133681654608883617987619781762536839523918823141580161 \\{} & {} 97123835376178581844008644586889905048955222245453609041221097 \\{} & {} 121126837776453250821684510563 \end{aligned}$$

$q=$

$$\begin{aligned}{} & {} 93954778235710974203677377216985836253852371657508142242651124 \\{} & {} 33882347772961954728089804437932682899351880809635985985823721 \\{} & {} 278448590959326657930561582027 \end{aligned}$$

$d=$

$$\begin{aligned}{} & {} 84621421118866086279480677455817189905395785567701311624227231 \\{} & {} 1992184907517426187202723837 \end{aligned}$$

Exp. 3

$N=$

$$\begin{aligned}{} & {} 10205793884912309428243538885795108687967400364358859068757105 \\{} & {} 27366676256258700648163154922583229485417321567269849917383364 \\{} & {} 64656067954130787989822823376442710598097310129836268241537114 \\{} & {} 71952829908327055972448207678376586518255364121854918727930884 \\{} & {} 3770512577006453837517293155340490761206708661611812914183899 \end{aligned}$$

$e=$

$$\begin{aligned}{} & {} 80900458040712014796201499026385729329804135026384835491013425 \\{} & {} 86092605732136485389209880857013543736344572515888256253718707 \\{} & {} 08436780537181756263571337006232687007715876604623603003318929 \\{} & {} 36401425760635712653711506424050436067133668344381418365690036 \\{} & {} 931579614717233156905341293247889945042931394909865508914479 \end{aligned}$$

$p=$

$$\begin{aligned}{} & {} 130550858861846841747727958575739547701679174283776488146464000 \\{} & {} 035126653179894990637272044524427541060375052834227051238884085 \\{} & {} 86029300473284150150163760489 \end{aligned}$$

$q=$

$$\begin{aligned}{} & {} 781748505822731655261191706621539039622764767903458858428781536 \\{} & {} 263460148861416123276603543978929241699568615263385404823218907 \\{} & {} 1292155782177922355115574691 \end{aligned}$$

$d=$

$$\begin{aligned}{} & {} 868126999952902548361525189983896174511773826207382896837234598 \\{} & {} 157112101757767726001029119 \end{aligned}$$

Appendix D: Detailed parameters of the three experiments in Table 10

Exp. 4

$N=$

$$\begin{aligned}{} & {} 13108249020538785310663414698582637064820950198561878706735851 \\{} & {} 65703644339810427940041439226962830915168487281788869208017778 \\{} & {} 64923887358082167988616026368541195282045124591109789444274263 \\{} & {} 26718715032735164557685449265721895500116475985815536552066383 \\{} & {} 98902635748400290357538362875036895327848802671465354828268316 \\{} & {} 19459190428496888414853786863007208331552517424436288121969788 \\{} & {} 57993634225342593766658498158262129054566502609859174903015093 \\{} & {} 10543060200243513864877744474764130353698543557524799219837216 \\{} & {} 81177688022836416789341375825625350075504640416012415003418082 \\{} & {} 73695609938403611734357471580735947449865433515838599015767 \end{aligned}$$

$e=$

$$\begin{aligned}{} & {} 89451479500251299951266471597772406719039486388733814263161727 \\{} & {} 77277693744087994022236345476762214316234081707614457014149993 \\{} & {} 07086353862705412696231771650983658024823969641299772311875452 \\{} & {} 35751367575578627668994418983506635558378045495835658481986197 \\{} & {} 64498956959651824723201619704850371101473507734971701102683193 \\{} & {} 24725402870657449338885605852347781947910706904405925408817023 \\{} & {} 60111680067003156460400937994396681812731602263538839593687345 \\{} & {} 62219589235850846108119781315380911546600335260644624325458166 \\{} & {} 47435720465040339844832330681577201708958823066483795645154297 \\{} & {} 8645874176685545024632447680732323591071139368778498577639 \end{aligned}$$

$p=$

$$\begin{aligned}{} & {} 12475716189463277471168125160458453539576717759904860818958950 \\{} & {} 12014825348919743719578184669777821230125550070704404895576204 \\{} & {} 52941396889634025921970794255590369593505603793752936553527919 \\{} & {} 38379990938303607598997653011866480954848015397181895617491220 \\{} & {} 3077504115908974119391542269233365957211095336385587786710643 \end{aligned}$$

$q=$

$$\begin{aligned}{} & {} 10507011238047985984905944714077857914018323916121653018787711 \\{} & {} 19630266681204488009378026133638912480941505942176252858307437 \\{} & {} 32991043217939651634566680101998984493904772645000773580396638 \\{} & {} 66392564560306397986626626825696478790443273047686349310580634 \\{} & {} 5028770283044102294594624281933734776943133629178895741769869 \end{aligned}$$

$d=$

$$\begin{aligned}{} & {} 16203833775447352356853531181274614215508930119487698497783433 \\{} & {} 20417126835821821597640064942591829248499538916881397751938428 \\{} & {} 70347081603575753080006255052855504063533452418351103 \end{aligned}$$

Exp. 5

$N=$

$$\begin{aligned}{} & {} 18909672181904151395097968169920434800151774976081336450891174\\{} & {} 87637992213220042585977009330732380044765810427401976038590837\\{} & {} 11873143826745772602607516127893011661052190642253756693227076\\{} & {} 98926584779010796261564768643160271391197294787916627864241401\\{} & {} 91442506166372883954050983092065122469794049346568026032600851\\{} & {} 06520619119309685394418339932570134971764214265160652504821910\\{} & {} 54728868131847284573195025675911240577689925121207663441802463\\{} & {} 95424763276465590987069458679529387973710595569647138338589685\\{} & {} 41003463475729539029975985698319117707054049488848688491897152\\{} & {} 76445558134402328090544913847971380379882458726005541831877 \end{aligned}$$

$e=$

$$\begin{aligned}{} & {} 71750525858644602573827151612109334198329801833575974634891308\\{} & {} 81495398383619485101066743946892399989979056836606216684862725\\{} & {} 57211251358518687663563498732052487860671897005525731875587709\\{} & {} 48285298803158025787222714686015007936511780408515333161477308\\{} & {} 33938515599770436750069222320451660592526204534805678560379611\\{} & {} 66401313318683780361047153401836775380248541241640858508425424\\{} & {} 17567958496040977474953521700071041506080838448030690016792476\\{} & {} 72933113105225110610011794291511678512931585633775157710522063\\{} & {} 46208952124338836289923112469153753848820848393483936342199771\\{} & {} 0031387152470262859696222361705999483806613844394759888651 \end{aligned}$$

$p=$

$$\begin{aligned}{} & {} 17632053007251238779460491844609267953184637057432293238819260\\{} & {} 45182034840480286908458849795483938148101996899679104684164224\\{} & {} 74443986695404811633893785378170226481910000920070470403858119\\{} & {} 63853022804280585705368356890551045545683993527388328068472661\\{} & {} 0142603148675130345130093490471284531708421254883794726933731 \end{aligned}$$

$q=$

$$\begin{aligned}{} & {} 10724600348086231138978615424494121452147302572884539393558466\\{} & {} 49494608032097842525445414641585733688186933655325569963690234\\{} & {} 73297386324910499142225474129024782995490552263782465106021625\\{} & {} 38318333121616296839163140328592966430893795983414382893135148\\{} & {} 9815771244076937362708739778582739737422552531974179680294967 \end{aligned}$$

$d=$

$$\begin{aligned}{} & {} 74371802615146241472896188271041978689492703240379646141995046\\{} & {} 73820493661253184594168451370887921723607130820247798059973262\\{} & {} 06710810842150444333271043589416784775482885854461951 \end{aligned}$$

Exp. 6

$N=$

$$\begin{aligned}{} & {} 23106605651041615213646000110077851420712757917776430930326056 \\{} & {} 60296830951476238797402172985663226841689573922131931924256474 \\{} & {} 42373164767688138199312178870617014197433167498889179888412544 \\{} & {} 74185076959806015212320711881448073618683164329640885570487353 \\{} & {} 50354182223829749002048540419684771479273577984952576597834431 \\{} & {} 10876017808739917408013571983470008797535808485837831985030128 \\{} & {} 18980694013921518439031616253599644305480276822960370194442400 \\{} & {} 29680528535253331304066794571579472555287555198582878649996706 \\{} & {} 70189200424088850932169339900976909686922394456370919349825147 \\{} & {} 79933248467489575820613721302800274215988236180595306270631 \end{aligned}$$

$e=$

$$\begin{aligned}{} & {} 12306595799514227604950469560934424785746654745458886525393457 \\{} & {} 58899783970499242533791938472818667104241589586924790854906048 \\{} & {} 54925263611470499944927026328816440185366245189763792436116837 \\{} & {} 57561103528778660481890339014924778781448952317743651644045890 \\{} & {} 34734358672625085976939766863203987473622112403467008193246531 \\{} & {} 18811333558134310761081974826858002018445896729330025874175254 \\{} & {} 08511656625722972253589317139568494268155847524384162663775384 \\{} & {} 56174150943940984854862543628588707580008442653426773237869939 \\{} & {} 26533039846186871551451618391840130895864570824139236237941156 \\{} & {} 12847782672209965094853232413711557861305091453331658286885 \end{aligned}$$

$p=$

$$\begin{aligned}{} & {} 15200857097888143612235928515088793346264155533550218885999558 \\{} & {} 43118029224237682629271323091741303390999578531540748865895441 \\{} & {} 28299767695057057649418113935154004959819709868376351089412151 \\{} & {} 66689369221389374628670381926958230967689721241987218903900245 \\{} & {} 6978031157591446602279278447377998069848764568730671548941379 \end{aligned}$$

$q=$

$$\begin{aligned}{} & {} 15200857097888130222480933300617571310430741971257868954229473 \\{} & {} 99010773432783299974566489666130612156702118428957004402934567 \\{} & {} 26259649410467624692928043525938992850157984384838932304533523 \\{} & {} 37960458325033282161048364788519071913365063106030773291799585 \\{} & {} 7967631386967340066303738923024637820931061972877004540650189 \end{aligned}$$

$d=$

$$\begin{aligned}{} & {} 95106665770280602013064006456747612094114888110214050993001292 \\{} & {} 18842148846561624186845878708855870619895801364016214375097533 \\{} & {} 53978037760812938848119029882054844495851034227001786365 \end{aligned}$$