IEICE TRANS. FUNDAMENTALS, VOL.E98–A, NO.

12 DECEMBER 2015
2677

PAPER
A New Attack on RSA with Known Middle Bits of the Private Key∗

Shixiong WANG†a) , Nonmember, Longjiang QU† , Member, Chao LI† , Nonmember, and Shaojing FU†† , Member

SUMMARY In this paper, we investigate the security property of RSA such as fault attacks [4], timing attacks [15] and power anal-
when some middle bits of the private key d are known to an attacker. Using yses [16]. In 1998, Boneh, Durfee and Frankel first pre-
the technique of unravelled linearization, we present a new attack on RSA
sented partial key exposure attacks on RSA [6], which are
with known middle bits, which improves a previous result under certain
circumstance. Our approach is based on Coppersmith’s method for finding based on a corollary of the conclusion in [8]. Let us denote
small roots of modular polynomial equations. most significant bits by MSBs and least significant bits by
key words: RSA, attack with known middle bits, Coppersmith’s method, LSBs. Given (log2 N)/4 LSBs of d, an attack was showed
lattice, LLL algorithm, unravelled linearization for small e in [6]. Other attacks of [6] require√knowledge
of MSBs, but only apply to the case of e < N. A nat-
1. Introduction ural question raised in [6] is whether knowledge of MSBs
or LSBs of d enables one to factor√N in polynomial time
In 1977, Rivest, Shamir and Aldeman proposed the well- when e is substantially larger than N. Based on Copper-
known RSA public key cryptosystem [23]. We let N = pq smith’s method, Blömer and May [3] and Ernst et al. [10]
be RSA modulus and let e and d be the public exponent and then independently described new partial key exposure at-
the private exponent respectively, i.e. e · d ≡ 1(mod ϕ(N)), tacks, and answered the question to some extent. Another
where ϕ(·) is the Euler’s totient function. We also call d the question raised in [6] is whether knowledge of (log2 N)/4
private key. middle bits of d enables one to factor N in polynomial time.
We consider lattice-based cryptanalysis of RSA, in This belongs to attacks with known middle bits of the pri-
which Coppersmith’s method plays an important role. The vate key.
method is to find small roots of v-variate modular polyno- Notice that there have been many partial key exposure
mial equations (or (v + 1)-variate integer polynomial equa- attacks, most of which only assume that MSBs or LSBs are
tions) in polynomial time based on lattice basis reduction. known [1], [3], [6], [10], [14], [25]. In this paper, we con-
Initially in 1996, Coppersmith got the results for the case sider the case of known middle bits. In 2011, Sarkar studied
of v = 1 [7], [8]. Later the method of [7] (and [8]) was re- partial key exposure attacks on RSA when the number of
formulated by Howgrave-Graham [12] (and Coron [9]) in a unexposed blocks in d is more than one [24]. And the case
simpler way which has been widely adopted by researchers of known middle bits of d is just the case of two unexposed
for cryptanalysis. The reformulation by Howgrave-Graham blocks in d. Later in 2014, Z. Huang et al. presented their
(and Coron) can be also extended to the case of v  2, in attack on Takagi’s variant of RSA, which assumes N = pr q
which the results are heuristic. In general, the reformulation for r  2, with known middle bits of d [13]. However, the
is used when we refer to Coppersmith’s method. result in [13] also applies to the case of r = 1. Both Theorem
There have been some attacks on RSA if a portion of 2 in [24] and Theorem 1 in [13] almost gave the same result
the private key d is known. These attacks, called partial of attack on RSA with known middle bits, though Theorem
(private) key exposure attacks, are usually based on Copper- 2 in [24] only considerd the case of e ≈ N. We summa-
smith’s method. The results are of practical interest since rize this known result as Result 2.1 in Sect. 2, which is the
implementations may leak bits of d via side channel attacks best result as we know. Our main work in this paper is to
improve Result 2.1 under certain circumstance.
Manuscript received March 30, 2015. In 1990, based on approximations using continued
Manuscript revised July 21, 2015. fractions, Wiener presented the first low private exponent at-
†
The authors are with the College of Science, National Univer- tack [27]. In 1999, based on Coppersmith’s method, Boneh
sity of Defense Technology, Changsha, China.
††
The author is with the College of Computer Science, National
and Durfee improved Wiener’s result [5]. They claimed that
University of Defense Technology, Changsha, China. one may factor√ N in polynomial time if the private expo-
∗
nent d  N 1− 2 −ε ≈ N 0.292−ε . As far as the authors know,
2
This paper was partially supported by the Basic Research
Fund of National University of Defense Technology (No. CJ 13- this result is the best low private exponent attack up to now.
02-01) and the Program for New Century Excellent Talents in
Though several papers revisited the work [2], [11], [17]–
University (NCET) and the Natural Science Foundation of Hunan
Province (No. 13JJ4005) and the Natural Science Foundation of [19], none of them improved this√ result. Boneh and Durfee
only gave the proof of d  N 6 − 3 −ε ≈ N 0.285−ε in the main
7 7
China (No. 11531002).
a) E-mail: wsx09@foxmail.com body of [5], while the proof of d  N 0.292−ε was placed in
DOI: 10.1587/transfun.E98.A.2677

Copyright 
c 2015 The Institute of Electronics, Information and Communication Engineers
 IEICE TRANS. FUNDAMENTALS, VOL.E98–A, NO.12 DECEMBER 2015
2678

the appendix. The latter is a very intricate proof, which is from Theorem 2 in [24] and Theorem 1 in [13].
independent of the idea of the main body. In 2010, Her-
rmann and May simplified the proof of d  N 0.292−ε using Result 2.1. Notations are defined as before. Under Assump-
the technique of unravelled linearization [11]. tion 3.4 (case v = 3), for any ε > 0, there exists an integer
Both proofs in [5] and [11] are the applications of Cop- N0 such that for any integer N > N0 , RSA modulus N can be
persmith’s method for finding small roots of v-variate mod- factored in polynomial time if
ular polynomial equations in the case of v = 2. In this paper, 7 1
we generalize the method of the proof of d  N 0.292−ε in β − (δ1 − δ2 )  − 48(α + β) − 39 − ε. (1)
8 8
[11] to the case of v = 3, and thus present a new attack with
known middle bits of d, i.e. an improvement to Result 2.1 In this paper, we restrict the known middle bits, and
under certain circumstance. Then we give a corollary of the present our new attack.
new attack. Note that though the result d  N 0.292−ε has
not been improved unconditionally, there are several attacks Theorem 2.2. Notations are defined as before, and suppose
which show that RSA is also insecure for larger d if more d2 < N β−0.5−δ2 . Under Assumption 3.4 (case v = 3), for
information is used. For example, [21] found RSA is vul- any ε > 0 (or ε > 0), there exists an integer N0 such that
nerable for some d > N 0.292 when e/N is approximated a for any integer N > N0 , RSA modulus N can be factored in
simple fraction, and [26] extended the bound of d for which polynomial time if
RSA is weak with the knowledge of a few MSBs of p (alter- 5 1
natively these bits can be searched exhaustively). Similarly, β − (δ1 − δ2 )  − 6(α + β) − 5 − ε (2)
6 3
our corollary shows that one may successfully attack RSA
for some d > N 0.292 if there exist enough many continuous 7 1
0 bits in d. ⇔ β  (δ1 −δ2 )+ − 6[α + (δ1 − δ2 )] + 1−ε . (3)
6 3
This paper is organized as follows. In Sect. 2, we recall
the known result (Result 2.1) and present our results as The- In Theorem 2.2, Inequality (3) is more useful in prac-
orem 2.2 and Corollary 2.3. In Sect. 3, we show how to de- tice. The value of N, α, β, δ1 , δ2 must be known to construct
rive the problem of finding small roots from the knowledge a lattice in our attack. Since N, α, δ1 , δ2 are already known,
of middle bits of d, and then recall Coppersmith’s method. we can get a value of β from Inequality (3). If d  N β holds,
The lattice for Coppersmith’s method is constructed and the the attack can be implemented.
proof of our attack is given in Sect. 4. In Sect. 5, we clarify Now let us compare the two results according to In-
why our new result is obtained technically. And the justifica- equality (1) and Inequality (2). One can check that 78 −
 
8 48(α + β) − 39  6 − 3 6(α + β) − 5, where “=” holds
1 5 1
tion of our approach is examined through some experiments
in Sect. 6. Section 7 is the conclusion. if and only if α+β = 1. Thus the result of Theorem 2.2 is bet-
ter than Result 2.1 under the condition d2 < N β−0.5−δ2 , which
2. Known Result and Our Contribution is also obvious from Fig. 1 and Fig. 2. Assuming d = N β , we
set α ≈ 1 (full size e) in Fig. 1 and set β ≈ 1 (full size d) in
In practice, the bit sizes of the prime factors p and q of Fig. 2. And the y-axis (δ1 − δ2 )/β in both figures denotes
RSA
√ modulus N usually√ differ at most 1. Thus we assume known fraction of d that is sufficient to implement the at-
N/2 < q < p < 2 N just like most partial key exposure tacks.
attacks. Similarly, we also assume ϕ(N) = N. In fact, if one The condition d2 < N β−0.5−δ2 naturally holds when d2 =
lets ϕ(N) = N γ (γ ≈ 1), the result only has little difference.
Let e = N α , d  N β , and let the bit size of d be nd . Besides,
we write
d = d1 · 2r1 + d2 · 2r2 + d3 , 0 < r2 < r1 < nd ,
0  d1 < 2nd −r1 , 0  d2 < 2r1 −r2 , 0  d3 < 2r2 .
Suppose that after some attacks such as side-channel at-
tacks, we get the value of d2 and r1 , r2 at the same time,
while d1 and d3 are still unknown. Define δ1 = logr1 N , δ2 =
2
δ1 r2 δ2
log2 N , namely 2 = N , 2 = N . In this paper, we study
r2 r1

the condition that α, β, δ1 , δ2 need to satisfy in order to factor

N in polynomial time. This is exactly the attack with known
middle bits of d. We first give the known result, and then
present our contribution. These results, just like most re-
sults of partial key exposure attacks, are heuristic since they
are based on Assumption 3.4 (see Sect. 3.2).
As recalled in Sect. 1, the following result is followed Fig. 1 Attack with known middle bits for full-size e and small d.
WANG et al.: A NEW ATTACK ON RSA WITH KNOWN MIDDLE BITS OF THE PRIVATE KEY
2679

choose a private key d consisting of many 0 bits in order to

improve the performance by lowering the Hamming weight
of d and thus reducing the total number of multiplications.
Hence Corollary 2.3 is useful when d contains enough con-
tinuous 0 bits for efficiency on implementation of RSA. At
last, we explain the exhaustive search for choices of (r1 , r2 )
in the proof of Corollary 2.3 and compare it with [26]. Since
0 < r2 < r1 < nd , the number of choices for (r2 , r1 ) is
Cn2d −1 , and Cn2d −1 < (nd − 1)2 < ( log2 N )2 . Hence the
time for our exhaustive search is polynomial in log2 N. [26]
does exhaustive search for a few MSBs of p (a factor of N)
to extend the bound of d for low private exponent attack.
Thus the time for exhaustive search in [26] is exponential in
log2 N. When log2 N = 1000, the time for [26] can be less
than our Corollary 2.3 and [26] successfully attacks RSA for
Fig. 2 Attack with known middle bits for full-size d and small e. d ≈ N 0.3 . But when log2 N = 10000, exhaustive search in
our Corollary 2.3 costs much less time than [26].
Table 1 Inequality (4) with α ≈ 1.
3. Problem Derivation and Coppersmith’s Method
lmax / log2 N 0 0.015 0.030 1/3
β 0.285 − ε 0.294 − ε 0.303 − ε 0.500 − ε
3.1 Derive the Problem of Finding Small Roots from the
Knowledge of Middle Bits of d
0. Hence we directly get a corollary of Theorem 2.2.
Since e · d ≡ 1(mod ϕ(N)), there exists a positive integer k
Corollary 2.3. Notations are defined as before. Besides, for such that
the private key d, we define
1 = ed−kϕ(N) = e(d1 ·N δ1 +d2 ·N δ2 +d3 )−k[N−(p+q−1)].
+
lmax = max{l ∈ Z |there exist l continuous bits
Let A = e · d2 · N δ2 − 1, W = e · N δ1 . Then from the equation
in d whose values are all 0.}
above we get
Under Assumption 3.4 (case v = 3), for any ε > 0, there
exists an integer N0 such that for any integer N > N0 , RSA A + e · d3 − N · k + k · (p + q − 1) ≡ 0 (mod W).
modulus N can be factored in polynomial time if Notice that 0  d3 < N δ2 , 0 < k = (ed − 1)/ϕ(N) < N α+β−1
 (we assume ϕ(N) = N), 0√< p + q − √ 1 < p + q < 3N 0.5
lmax 7 1 lmax √
β + − 6(α + ) + 1 − ε . (4) (we assume N/2 < q < N < p < 2 N). Thus from the
log2 N 6 3 log2 N problem of attacking RSA with known middle bits we get
the problem of finding small roots of a trivariate modular
Proof. We can do exhaustive search for all the choices of polynomial equation:
(r1 , r2 ), where 0 < r2 < r1 < nd and r1 , r2 ∈ Z. And one
of these choices must satisfy r1 − r2 = lmax . Thus Corollary A + ex − Ny + yz ≡ 0 (mod W), (5)
2.3 follows directly from Theorem 2.2 under the condition
d2 = 0.  |x| < X = N δ2 , |y| < Y = N α+β−1 , |z| < Z = 3N 0.5 .
The desired root is (x, y, z) = (x0 , y0 , z0 ) = (d3 , k, p + q − 1).
Two comments of Corollary 2.3 are as follows. First,
If we get the desired root, the value of z0 = p+q−1 is known
the result does not require any information of d. On the one
and RSA modulus N can be easily factored. In fact, what we
hand, none of bits of d are known. On the other hand, though
get are all the small roots. Thus we try each possible value
lmax is used in Inequality (4), we need not know the exact
of z0 = p + q − 1 for every small root until RSA modulus N
value of lmax in the attack. Second, notice that the best low
is factored. Following this way, we can give a new proof of
private exponent attack needs the condition β  0.292 − ε
Result 2.1, which is introduced in Sect. 5.
[5]. Let α ≈ 1 (the worst case) in Inequality (4), and we To prove Theorem 2.2, we need the technique of un-
get β  loglmax
+ 76 − 13 6 · log
lmax
+ 7 − ε (the condition of ravelled linearization, which is used in [11]. Dealing with
2N 2N
our attack). Some examples for this inequality are given in the bivariate modular polynomial equation −1 − Ny + yz ≡
Table 1. From Table 1, we know that if lmax is large enough, 0 (mod e), [11] uses the substitution u = yz−1 before finding
RSA may be insecure even for some d > N 0.292 (notice that the small roots of this equation. Similarly in our new attack,
d  N β ). It should be noted that from Result 2.1 one can get we let u = yz + A in Eq. (5). This needs a new condition
a similar corollary, but it is not as good as Corollary 2.3. d2 < N β−0.5−δ2 and finally improves Result 2.1.
When it comes to implementation of RSA, one may In fact, we let u = yz+ A and u0 = y0 z0 + A. From |y0 | <
 IEICE TRANS. FUNDAMENTALS, VOL.E98–A, NO.12 DECEMBER 2015
2680


Y, |z0 | < Z, we have |y0 z0 | < YZ = 3N α+β−0.5 . To restrict u0 , h(x1 , · · · , xn ) = |at1 ,··· ,tn |2 .
we hope A < N α+β−0.5 , namely d2 < (N α+β−0.5 + 1)/(e · N δ2 ).
Lemma 3.3. (Howgrave-Graham) Let h(x1 , · · · , xv ) ∈
Hence we can assume d2 < N α+β−0.5 /(e·N δ2 ), or equivalently
Z[x1 , · · · , xv ] be a polynomial that consists of at most s
d2 < N β−0.5−δ2 , and then get |u0 | < U = 4N α+β−0.5 . From the
monomials. Suppose that there exists (x1(0) , · · · , xv(0) ) ∈ Zv
above, under the condition d2 < N β−0.5−δ2 , we just need to
satisfying
find the desired root (x, y, z, u) = (x0 , y0 , z0 , u0 ) = (d3 , k, p +
q − 1, k(p + q − 1) + A) of the following modular equation: h(x1(0) , · · · , xv(0) ) ≡ 0 (mod V), |x1(0) | < X1 , · · · , |xv(0) | < Xv ,
√
ex− Ny+u ≡ 0 (mod W), |x| < X, |y| < Y, |z| < Z, |u| < U. h(X1 x1 , · · · , Xv xv ) < V/ s.
Then h(x1(0) , · · · , xv(0) ) = 0 holds over the integers.

3.2 Coppersmith’s Method Combining Fact 3.2 with Lemma 3.3, one can analyse
the bounds for the small roots. The method is called Cop-
To find small roots of modular polynomial equations, we persmith’s method, which has been widely adopted by re-
must introduce Coppersmith’s method. First of all, let us searchers for lattice-based cryptanalysis of RSA. Now we
recall the definition of lattice. summarize Coppersmith’s method for the case of v-variate
modular polynomial equations as follows.
Definition 3.1. Let b1 , b2 , · · · , bω ∈ R s be linearly inde- Finding small roots of v-variate modular polyno-
pendent (row) vectors for ω  s. A lattice Λ generated by mial equations can be described as finding each root
b1 , b2 , · · · , bω is the set of all integral linear combinations (x1(0) , · · · , xv(0) ) ∈ Zv of h0 (x1 , · · · , xv ) ≡ 0 (mod W), |x1 | <
of these vectors: X1 , · · · , |xv | < Xv . Let m be an undetermined parameter, and
⎧ ω ⎫ find a subset Λ∗ of Z[x1 , · · · , xv ] satisfying
⎪
⎪
⎨ ⎪
⎪
⎬
  
Λ = spanZ (b1 , b2 , · · · , bω ) = ⎪ x 
b | x ∈ Z, i = 1, 2, · · · , ω⎪ . h(x1(0) , · · · , xv(0) ) ≡ 0 (mod W m ), ∀ h(x1 , · · · , xv ) ∈ Λ∗ .
⎪
⎩ i i i ⎪
⎭
i=1
Given the order of some monomials of Z[x1 , · · · , xv ],
We call s the dimension of Λ and ω its rank. Row there is a one-to-one correspondence between a polynomial
vectors b1 , b2 , · · · , bω are a basis of Λ, and we denote the h(x1 , · · · , xv ) in Λ∗ and a vector in a subset Λ of R s , whose
basis as a matrix, called the basis matrix of Λ: components are coefficients of h(X1 x1 , · · · , Xv xv ) in order of
⎛ ⎞ corresponding monomials. We also require Λ to be a lat-
⎜⎜⎜ b1 ⎟⎟⎟ tice of dimension s. Notice that in fact v is far less than s.
⎜⎜⎜  ⎟⎟⎟
⎜b ⎟ Combining Fact 3.2 with Lemma 3.3, if
B = ⎜⎜⎜⎜ 2 ⎟⎟⎟⎟ ∈ Rω×s .
⎜⎜⎜⎝· · ·⎟⎟⎟⎠ √
2 s(s−1)/4(s−v+1) det(Λ)1/(s−v+1) < W m / s (6)
bω
 is satisfied, by running LLL algorithm one can get v polyno-
The determinant of Λ is defined as det(Λ) = det(BBT ), mials, which all share each root (x1(0) , · · · , xv(0) ) as a common
which is independent of the choice of the basis and only root over the integers. For the case of v = 1, one can find
determined by Λ. In this paper, we only consider lattices for each root x1(0) ∈ Z using standard root-finding algorithms.
the case of ω = s. Thus B is a square matrix and det(Λ) = For the case of v  2, Coppersmith’s method needs the fol-
| det B|. lowing assumption.
In 1982, Lenstra et al. proposed the famous LLL al-
Assumption 3.4. In Coppersmith’s method, the common
gorithm for lattice basis reduction [20]. It allows one to
roots of v polynomials outputted by LLL algorithm can be
find a short vector in a lattice in polynomial time. The
found by computing the resultants of these v polynomials.
proof of the following fact can be found in [22]. The
norm of a vector vi = (vi1 , vi2 , · · · , vis ) is defined as vi =
 Since Assumption 3.4 is heuristic, we need to perform
v2i1 + v2i2 + ··· + v2is . experiments to examine it in our attack, which is done in
Sect. 6.
Fact 3.2. (LLL) Let s be the dimension (and the rank) of Notice that Inequality (6) is equivalent to
Λ. Given a basis (square) matrix B of Λ, the LLL algorithm det(Λ) · 2 s(s−1)/4 s(s−v+1)/2 < W m(s−v+1) .
outputs a LLL-reduced basis v1 , v2 , · · · , vs satisfying
In practice, we ignore terms that do not depend on W. Thus
vi  2 s(s−1)/4(s−i+1) det(Λ)1/(s−i+1) , 1is we obtain
in polynomial time in s and in the bit sizes of the entries of det(Λ) < W m(s−v+1) . (7)
the basis matrix B.
According to the analysis above, under Assumption 3.4, us-
Next we introduce the following useful lemma due ing Coppersmith’s method to find small roots of v-variate
to Howgrave-Graham [12]. The norm of a polyno- modular polynomial equations just requires the condition

mial h(x1 , · · · , xn ) = at1 ,··· ,tn x1t1 · · · xntn is defined as Inequality (7).
WANG et al.: A NEW ATTACK ON RSA WITH KNOWN MIDDLE BITS OF THE PRIVATE KEY
2681

Table 2 Basis (square) matrix B with m = 2, τ = 1, θ1 = 2

1 x y u x2 xy xu y2 yu u2 zx2 zxu zu2
W2 W2
xW 2 XW 2
yW 2 YW 2
fW * * UW
x2 W 2 X2 W 2
xyW 2 XYW 2
xfW * * XUW
y2 W 2 Y2W2
yfW * * YUW
f2 * * * * * U2
zx2 W 2 ZX 2 W 2
zx f W * * * ZXUW
zf2 * * * * * * * * ZU 2

(1) h(x, y, z, u) ∈ B1 , h (x, y, z, u) ∈ B2 ;

4. Construction of Lattice and Proof of Theorem 2.2 (2) h(x, y, z, u) = xt1 yt2 ut3 ∈ Gt ⊂ B1 , h (x, y, z, u) =
t1 t2 t3
x y u ∈ Gt ⊂ B1 , and t < t or t = t , t1 > t1 or t = t , t1 =
For the attack with known middle bits under the condition t1 , t2  t2 ;
d2 < N β−0.5−δ2 , we need to find the desired root (x, y, z, u) = (3) h(x, y, z, u) = zi · xt1 ut3 ∈ Pi ⊂ B2 , h (x, y, z) =
i  
(x0 , y0 , z0 , u0 ) = (d3 , k, p + q − 1, k(p + q − 1) + A) of the z · xt1 ut3 ∈ Pi ⊂ B2 , and i < i or i = i , t1 + t3 < t1 + t3 or
following modular equation: i = i , t1 + t3 = t1 + t3 , t1  t1 .
Similarly, we can define a total order “∗ ” on set B∗
f (x, y, z, u) ≡ 0 (mod W), |x| < X, |y| < Y, |z| < Z, |u| < U, just like the total order on set B.
Now we construct matrix B as follows. First, for
where
any polynomial g(x, y, z, u) in set B∗ , we use the relation
f (x, y, z, u) = ex − Ny + u, yz = u − A to substitute each occurrence of monomial yz in
A = e · d2 · N δ2 − 1, W = e · N δ1 = N α+δ1 , g(x, y, z, u) by the term u − A. Second, we build a one-to-
one correspondence between a polynomial g(x, y, z, u) in set
X = N δ2 , Y = N α+β−1 , Z = 3N 0.5 , U = 4N α+β−0.5 . B∗ and a row vector, whose components are coefficients of
We discuss how to construct lattice Λ for our new at- g(Xx, Yy, Zz, Uu) in order of corresponding monomials in
tack. Let B denote the basis (square) matrix of Λ. Then we the totally ordered set B. Third, put all polynomials in B∗ as
just need to construct B. the row vectors in matrix B in order of “∗ ”.
Let nonnegative integers m, τ be undetermined param- Table 2 illustrates an example for matrix B with param-
eters. For t = 0, 1, 2, · · · , m and i = 1, 2, · · · , τ, we define eters m = 2, τ = 1, θ1 = 2. Here we use polynomial zx f W in
the following sets of monomials or polynomials: Table 2 to illustrate the one-to-one correspondence between
a polynomial and a row vector. Since zx f W = zx(ex − Ny +
Gt = {xt1 yt2 ut3 | t1 , t2 , t3 ∈ Z+ ∪ {0}, t1 + t2 + t3 = t}, u)W = (ezx2 − N xyz + zxu)W = [ezx2 − N x(u − A) + zxu]W =
G∗t = {xt1 yt2 f t3 W m−t3 | t1 , t2 , t3 ∈ Z+ ∪ {0}, t1 + t2 + t3 = t}, (NAx − N xu + ezx2 + zxu)W, its corresponding row vector
m is (0, NAXW, 0, 0, 0, 0, −NXUW, 0, 0, 0, eZX 2 W, ZXUW, 0).
Pi = Hi,t , Hi,t = {zi · xt1 ut3 | t1 , t3 ∈ Z+ ∪ {0}, t1 + t3 = t}, One may notice that matrix B is a lower triangular matrix.
t=θi Actually, we have the following important conclusion.

m
P∗i = H∗i,t , H∗i,t = {zi · xt1 f t3 W m−t3 | t1 , t3 ∈ Z+ ∪{0}, t1 +t3 = t}. Proposition 4.1. If θi+1  θi + 1 (i = 1, 2, · · · , τ − 1), then B
t=θi is a lattice basis matrix, and it is a lower triangular matrix.

Note that in the above equations x0 , y0 , z0 , u0 , f 0 etc. are re- The proof of Proposition 4.1 is given in Appendix A.
garded as 1. Besides, though sets G∗t , Pi , P∗i also depend on Under the condition θi+1  θi + 1 and with the help of sub-
parameter m, we omit it in the subscripts for convenience. stitution yz = u − A, here we note that the main point is to
The nonnegative integer θi in the definitions of Pi , P∗i is an- prove that every polynomial in set B∗ only contains mono-
other parameter, which will be determined later. mials (neglect coefficients) which belong to set B.
Next for sets of monomials τ we define B = Notice that Λ is the lattice generated by the basis ma-
B1 B2 , B1 = m G
t=0 t , B =
2  i=1 i P , and for
msets ∗of poly- trix B. It is obvious that all polynomials in set B∗ have
∗ ∗ ∗ ∗ ∗
nomials
τ ∗ we define B = B 1 B 2 , B 1 = t=0 Gt , B2 = (x0 , y0 , z0 , u0 ) = (d3 , k, p + q − 1, k(p + q − 1) + A) as a com-
i=1 Pi . mon root modulo W m . Thus all polynomials correspond-
We define a total order “” on set B. Let h(x, y, z, u), ing to all vectors in lattice Λ must have (x0 , y0 , z0 , u0 ) =
h (x, y, z, u) ∈ B. Then h(x, y, z, u)  h (x, y, z, u) if and only (d3 , k, p + q − 1, k(p + q − 1) + A) as a common root mod-
if one of the following cases occurs: ulo W m . Hence lattice Λ meets the requirement of Copper-
 IEICE TRANS. FUNDAMENTALS, VOL.E98–A, NO.12 DECEMBER 2015
2682

smith’s method. Denote the dimension of lattice Λ by s and and the calculation of s and det(Λ) we can get
the order of (square) matrix B by s(B). Then s = s(B). 4
o(m4 ) 1 4 1 2 o(m4 )
Notice that det(Λ) = | det B| = det B, and B is a lower tri- − 1
ξ 4 + 16 ξ+ 24
1
+ o(m4 ) − ξ +4ξ + 4
Y 24 +
1
X 24η3 m m4 Z 8η2 m

angular matrix. Therefore, det(Λ) is equal to the product of − 1

ξ 4 + 16 ξ+ 24
1 4
+ o(m4 ) − 1
ξ 4 + 16 ξ+ 24
1 4
+ o(m4 )
entries on the principal diagonal of B. Now we discuss how < W 24η3 m [U 24η3 m ]−1 .
to select the value of θi under the condition θi+1  θi + 1, and 4

then calculate s and det(Λ). We ignore terms o(m

m4
)
and ignore constant factors 3, 4 in Z, U
We define Hi,t as the submatrix of B whose rows (and while substituting X = N δ2 , Y = N α+β−1 , Z = 3N 0.5 , U =
columns) correspond to H∗i,t (and Hi,t ). The same applies to 4N α+β−0.5 , W = N α+δ1 . Then we obtain
the definitions of submatrix Gt and submatrix Pi . Thus we 1 4 1 2 1 1
have − 2
ξ + ξ − ηξ + (α + β − 1 − η) < 0, (8)
48η 8 6 24
⎛ i t m ⎞
⎜⎜⎜Z X W 0 ⎟⎟⎟
⎜⎜⎜⎜ Z i X t−1 UW m−1 ⎟⎟⎟⎟ where η = 12 − β + δ1 − δ2 = 12 − [β − (δ1 − δ2 )]. In order to
Hi,t = ⎜⎜⎜⎜⎜ ..
⎟⎟⎟
⎟⎟⎟ get the best possible result from Inequality (8), we need to
⎜⎜⎜ . ⎟⎟ minimize the left side. It is easy to check that the left side is
⎝ i t m−t ⎠
∗ ZUW a decreasing function of ξ. Notice that 0  ξ = mτ  η, and
we can select suitable integers τ, m to let ξ = mτ approach η.
for t = θi , θi + 1, θi + 2, · · · , m. The order of Hi,t is s(Hi,t ) = Thus we roughly take ξ = η in Inequality (8), and get
t + 1, and one can get det Hi,t = (Z i W m )t+1 (XUW −1 ) 2 t(t+1) .
1

Let v = 3 in Inequality (7) and get det(Λ) < W m(s−2) , which 3η2 + 2η − 2(α + β − 1) > 0. (9)
is the condition of our attack. Put H∗i,t and Hi,t in B∗ and B re- 
spectively, and it means that the left of Inequality (7) is mul- Since η > 0, it is obtained that η > − 13 + 16 24(α + β) − 20.
tiplied by det Hi,t while the right is multiplied by W ms(Hi,t ) . Finally we substitute η = 12 − [β − (δ1 − δ2 )] and get
Thus we hope det Hi,t  W ms(Hi,t ) , i.e. Z 2i (XUW −1 )t  1.
5 1
We roughly regard Z = 3N 0.5 as N 0.5 , and U = 4N α+β−0.5 as β − (δ1 − δ2 ) < − 6(α + β) − 5. (10)
N α+β−0.5 . Then we substitute Z, U and X = N δ2 , W = N α+δ1 6 3
in Z 2i (XUW −1 )t  1. Finally we can get t  1η i, where Notice that in calculation we ignore some terms, which con-
η = 12 − β + δ1 − δ2 = 12 − [β − (δ1 − δ2 )] > 0 (condition η > 0 tribute a “−ε” (ε > 0) in the right side of Inequality (10).
must be satisfied, otherwise we should take τ = 0 and finally The accurate analysis for ε is given in Appendix B, from
get 0 < α + β − 1 + ε < η  0, a contradiction). Since t is an which we know that ε is arbitrarily small if m and N are
integer, we have t  1η i , which means we select θi = 1η i . large enough. Replace “<” with “” in Inequality (10) with
From η < 12 we know condition θi+1  θi + 1 naturally holds. “−ε” added, and Theorem 2.2 follows.
Notice that neither of Pτ or P∗τ is a null set, which means
θτ = 1η τ  m, or 1η τ  m (m is an integer). Define ξ = mτ , 5. Why Theorem 2.2 Is Obtained Technically
and we get τ = ξm, 0  ξ  η < 12 . Now, let m → ∞ and Here we clarify why our new result is obtained technically.
we can get For this purpose, let us first introduce our proof of Result
m  2.1, which is similar to proofs in [24] and [13]. In fact,
s = s(Gt ) + τi=1 s(Pi )
t=0  ξm m [24] is to find small roots of integer polynomial equations,
= m
t=0
t
j=0 ( j + 1) + i=1 t=θi (t + 1) while [13] and we consider different modular polynomial
= [ 16 m3 + o(m3 )] + [(− 6η12 ξ3 + 12 ξ)m3 + o(m3 )] equations. Though three proofs have slight difference, the
= (− 6η12 ξ3 + 12 ξ + 16 )m3 + o(m3 ), ideas behind them are the same.
  Redefine f (x, y, z) = A + ex − Ny + yz, and do not use
det(Λ) = m t=0 (det Gt ) τi=1 (det Pi )
m  u = yz + A. Now sets of monomials or polynomials for the
= t=0 t1 ,t2 ,t3 ∈Z+ ∪{0}, t1 +t2 +t3 =t X t1 Y t2 U t3 W m−t3 ·
ξm m  i t1 t3 m−t3 construction of basis square matrix B are
i=1 t=θi t1 ,t3 ∈Z+ ∪{0}, t1 +t3 =t Z X U W
1 4
+o(m 4 1 4
+o(m 4
= [(XYU) 24 m )
W8 m )
]· Gt = {xt1 yt2 (yz)t3 | t1 , t2 , t3 ∈ Z+ ∪ {0}, t1 + t2 + t3 = t},
(− ξ + 4 ξ )m4 +o(m4 )
1 4 1 2
(− 1
ξ 4 + 16 ξ)m4 +o(m4 )
[Z 8η2 (XU) 24η3 · G∗t = {xt1 yt2 f t3 W m−t3 | t1 , t2 , t3 ∈ Z+ ∪ {0}, t1 + t2 + t3 = t},
1
ξ 4 − 12 ξ 3 + 13 ξ)m4 +o(m4 )
W
(
24η3 6η ] m
( 1
ξ 4 − 12 ξ 3 + 13 ξ+ 18 )m4 +o(m4 ) Pi = Hi,t , Hi,t = {zi · xt1 (yz)t3 | t1 , t3 ∈ Z+ ∪ {0}, t1 + t3 = t},
=W 24η3 6η · t=0
(− 1
ξ 4 + 16 ξ+ 24
1
)m4 +o(m4 )
X 24η3 · 
m

Y 24 m +o(m ) Z
1 4 4 (−
8η2
ξ + 4 ξ )m4 +o(m4 )
1 4 1 2
· P∗i = H∗i,t , H∗i,t = {zi · xt1 f t3 W m−t3 | t1 , t3 ∈ Z+ ∪{0}, t1 + t3 = t},
(− 1
ξ 4 + 16 ξ+ 24
1
)m4 +o(m4 ) t=0
U 24η3 .
where t = 0, 1, 2, · · · , m and i = 1, 2, · · · , τ. Notice that here
Notice that the condition of our attack is det(Λ) < we must always take θi = 0 in the definitions of Pi , P∗i to
W m(s−2) (let v = 3 in Inequality (7) ). From det(Λ) < W m(s−2) guarantee matrix B a lattice basis square matrix and a lower
WANG et al.: A NEW ATTACK ON RSA WITH KNOWN MIDDLE BITS OF THE PRIVATE KEY
2683

Table 3 Some results of our experiments (with α ≈ 1) under condition d2 < N β−0.5−δ2 .
N (bits) α β δ1 δ2 d2 m τ θ1 , θ2 , · · · , θτ s = dim(Λ) log2 (det(Λ)) Time for LLL Algorithm
1500 0.9981 0.6224 0.6144 0.0233 0 5 2 3, 5 77 9.348 × 105 281.3 seconds
1000 0.9979 0.6006 0.5666 0.0260 0 5 2 3, 5 77 6.064 × 105 133.1 seconds
2000 0.9992 0.5543 0.5293 0.0115 0 4 1 3 44 5.384 × 105 7.644 seconds
1500 0.9969 0.4503 0.4270 0.0367 =0 4 1 3 44 3.724 × 105 7.224 seconds
1000 0.9942 0.3866 0.2853 0.0400 =0 6 2 3, 6 113 8.618 × 105 798.2 seconds
2000 0.9997 0.3282 0.2331 0.0455 =0 6 2 3, 6 113 1.647 × 106 1187 seconds

triangular matrix. Let m → ∞ and ξ = mτ . Similarly we Case 2: Occasionally, Assumption 3.4 may fail even if
calculate the values of s and det(Λ) and substitute them in we compute resultants of more polynomials corresponding
the condition det(Λ) < W m(s−2) . To get the best possible to LLL-reduced basis vectors that share the desired root. In
result, one must take ξ = 23 η, where η = 12 − [β − (δ1 − δ2 )]. our experiments the examples are that we can only get one
And finally Result 2.1 follows. polynomial h(y, z) sharing the desired root. And we are not
We note that technique of unravelled linearization (i.e. able to eliminate y or z since any other polynomial g(y, z)
letting u = yz + A) enables us to throw away some H∗i,t (t = we can acquire is just a multiple of h(y, z) and thus their
0, 1, · · · , 1η i − 1) in P∗i while still guaranteeing B a lattice resultant is 0. Fortunately, all these examples in our exper-
basis square matrix and a lower triangular matrix, which is iments only occur when d2 = 0, and using the substitution
based on Proposition 4.1. According to our analysis before, yz = u+1 (d2 = 0) we can eliminate z in h(y, z) to get  h(y, u),
these H∗i,t (t = 0, 1, · · · , 1η i − 1) contribute more to the left which is just a homogeneous polynomial in y and u with de-
side than to the right side of det(Λ) < W m(s−2) . Thus Theo- gree at most 3. One example is that h(y, z) = a1 · (yz − 1)3 +
rem 2.2 improves Result 2.1 under condition d2 < N β−0.5−δ2 , a2 · y(yz − 1)2 + a3 · y2 (yz − 1) + a4 · y3 , a1 , a2 , a3 , a4 ∈ Z
the cost of technique of unravelled linearization. and thus  h(y, u) = a1 · u3 + a2 · yu2 + a3 · y2 u + a4 · y3 =
y · [a1 · (u/y)3 + a2 · (u/y)2 + a3 · (u/y) + a4 ]. Then one can
3

6. Experiments get at most 3 candidate values of u0 /y0 from  h(y0 , u0 ) = 0. It

can be checked that dk = N−ue0 /y0 and gcd(d, k) = 1 according
Just like other partial key exposure attacks based on Copper- to 1 = ed − kϕ(N). Hence we finally get the values of d, k
smith’s method, our approach is heuristic due to Assumption and thus also factor N.
3.4 as stated before. In order to show the correctness of our As the two cases show, in all of our experiments RSA
method, we have implemented several experiments in SAGE modulus N can be always successfully factored. Some re-
5.0 over Linux Fedora 16 on a desktop with 3.20GHz Intel sults of our experiments (with α ≈ 1), which belong to Case
Core2 CPU and 4GB RAM. 1 (the main case), are listed in Table 3.
Suppose using LLL algorithm we finally acquire three
polynomials  h1 (x, y, z, u), 
h2 (x, y, z, u), 
h3 (x, y, z, u) with de- 7. Conclusion
sired (x0 , y0 , z0 , u0 ) as a common root. One needs to substi-
tute u = yz + A to get h j (x, y, z) =  h j (x, y, z, yz + A), j = In this paper, by generalizing the method of [11], we show a
1, 2, 3. By computing resultants we can eliminate x and new partial key exposure attack on RSA with known middle
y, namely we obtain h12 (y, z) = Res x (h1 , h2 ), h13 (y, z) = bits of the private key d. This improves Result 2.1 under cer-
Res x (h1 , h3 ) and then h12,13 (z) = Resy (h12 , h13 ). If Assump- tain circumstance. And from the new attack we get Corol-
tion 3.4 holds, h12,13 (z)  0. Finally one can use any lary 2.3, which allows us to attack RSA for some d > N 0.292 .
standard root-finding algorithm to recover integer z0 from Thus one needs to avoid too many continuous 0 bits in d for
h12,13 (z) and then factor RSA modulus N. security of RSA.
Two cases in all of our experiments are summarized as The proof of Theorem 2.2 throws away some polyno-
follows. mials and monomials in the proof of Result 2.1. Another
Case 1: For most examples of our experiments, As- way is to add some new polynomials and monomials just
sumption 3.4 holds with some modification if necessary. as [1] did. [1] presented an attack with known LSBs and it
The modification is based on the fact that improved the corresponding result in [10]. We note that the
generalization of technique in [1] may give another possi-
gcd(g1 (y, z), g2 (y, z)) ∈ Z[y, z], gcd(g1 (y, z), g2 (y, z))  Z[z] ble improvement to Result 2.1, which is independent of our
main result Theorem 2.2. Since this generalization, includ-
must imply Resy (g1 (y, z), g2 (y, z)) ≡ 0. For example, it of- ing both proofs and computations, may be very complicated,
ten happens that gcd(h12 (y, z), h13 (y, z)) = ayb , a, b ∈ Z+ , we will discuss it in the future.
which makes h12,13 (z) = Resy (h12 , h13 ) ≡ 0. Thus we take
h12,13 (z) = Resy (h12 /ayb , h13 /ayb ) instead as the modifica- References
tion. Then Assumption 3.4 holds and we have h12,13 (z)  0,
from which we are able to obtain the desired roots and thus [1] Y. Aono, “A new lattice construction for partial key exposure at-
factor RSA modulus N. tack for RSA,” Public Key Cryptography-PKC 2009. LNCS 5443,
 IEICE TRANS. FUNDAMENTALS, VOL.E98–A, NO.12 DECEMBER 2015
2684

pp.34–53, Springer, Heidelberg, 2009. Ph.D. thesis, University of Paderborn, 2003.

[2] J. Blömer and A. May, “Low secret exponent RSA revisited,” [23] R.L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining
Cryptography and Lattices, Lecture Notes in Computer Science, digital signatures and public-key cryptosystems,” Commun. ACM,
vol.2146, pp.4–19, Springer, Heidelberg, 2001. vol.21, no.2, pp.120–126, 1978.
[3] J. Blömer and A. May, “New partial key exposure attacks on RSA,” [24] S. Sarkar, “Partial key exposure: Generalized framework to at-
Advances in Cryptology, CRYPTO 2003, vol.2729, pp.27–43, tack RSA,” Progress in Cryptology, INDOCRYPT 2011, LNCS,
Springer, Berlin, 2003. vol.7107, pp.76–92, Springer, Heidelberg, 2011.
[4] D. Boneh, R.A. DeMillo, and R.J. Lipton, “On the importance of [25] S. Sarkar, S.S. Gupta, and S. Maitra, “Partial key exposure attack
checking cryptographic protocols for faults,” Advances in Cryptol- on RSA — Improvements for limited lattice dimensions,” Progress
ogy, EUROCRYPT’97, LNCS, vol.1233, pp.37–51, Springer-Ver- in Cryptology, INDOCRYPT 2010, LNCS, vol.6498, pp.2–16,
lag, 1997. Springer-Verlag, Berlin Heidelberg, 2010.
[5] D. Boneh and G. Durfee, “Cryptanalysis of RSA with private key [26] S. Sarkar, S. Maitra, and S. Sarkar, “RSA cryptanalysis with in-
d Less than N 0.292 ,” Advances in Cryptology, EUROCRYPT’99, creased bounds on the secret exponent using less lattice dimension,”
LNCS, vol.1592, pp.1–11, Springer, Heidelberg, 1999. IACR ePrint Archive: Report 2008/315. 2008.
[6] D. Boneh, G. Durfee, and Y. Frankel, “An attack on RSA given a [27] M.J. Wiener, “Cryptanalysis of short RSA secret exponents,” IEEE
small fraction of the private key bits,” Advances in Cryptology, ASI- Trans. Inform. Theory, vol.36, no.3, pp.553–558, 1990.
ACRYPT’98, LNCS, vol.1514, pp.25–34, Springer, Berlin, Heidel-
berg, 1998.
[7] D. Coppersmith, “Finding a small root of a univariate modular equa- Appendix A: Proof of Proposition 4.1
tion,” Advances in Cryptology, EUROCRYPT’96, LNCS, vol.1070,
pp.155–165, Springer-Verlag, Berlin, 1996.
[8] D. Coppersmith, “Finding a small root of a bivariate integer equa-
Proof. B is a lattice basis matrix if and only if the follow-
tion; factoring with high bits known,” Advances in Cryptology, ing two statements
 hold: (1) for every polynomial in set
EUROCRYPT’96, LNCS, vol.1070, pp.178–189, Springer-Verlag, B∗ = B∗1 B∗2 , the monomials (neglect  coefficients) con-
Berlin, 1996. tained in it must belong to set B = B1 B2 , namely the
[9] J.-S. Coron, “Finding small roots of bivariate integer polynomial construction of matrix B makes sense; (2) the row vectors
equations revisited,” Advances in Cryptology, EUROCRYPT 2004,
in B are linearly independent.
LNCS, vol.3027, pp.492–505, 2004.
[10] M. Ernst, E. Jochemsz, A. May, and B. de Weger, “Partial key expo-
It is sufficient to prove that B is a lower triangular ma-
sure attacks on RSA up to full size exponents,” Advances in Cryptol- trix, which implies the result of (2) and needs the proof of
ogy, EUROCRYPT 2005, LNCS, vol.3494, pp.371–386, Springer, (1).
Berlin, 2005. For t = 0, 1, 2, · · · , m, let h1 (x, y, z, u) = xt1 yt2 f t3 W m−t3
[11] M. Herrmann and A. May, “Maximizing small root bounds by lin- ∈ Gt ⊂ B∗1 , where t1 , t2 , t3 ∈ Z+ ∪ {0} and t1 + t2 + t3 = t. We
∗
earization and applications to small secret exponent RSA,” Pub-
know that all the monomials contained in h1 (x, y, z, u) have
lic Key Cryptography, PKC 2010, LNCS, vol.6056, pp.53–69,
Springer, Heidelberg, 2010. the form of xt1 + j1 yt2 + j2 u j3 , where j1 + j2 + j3 = t3 . Thus they
[12] N. Howgrave-Graham, “Finding small roots of univariate modu- all belong to set Gt ⊂ B1 , and the rightmost one is xt1 yt2 ut3
lar equations revisited,” Proc. Crytography and Coding, LNCS, according to the definition of the total order “”.
vol.1355, pp.131–142, Springer-Verlag, 1997. For i = 1, 2, · · · , τ, let h2 (x, y, z, u) = zi · xt1 f t3 W m−t3 ∈
[13] Z. Huang, L. Hu, J. Xu, L. Peng, and Y. Xie, “Partial key exposure Hi,t ⊂ P∗i ⊂ B∗2 , where t1 , t3 ∈ Z+ ∪ {0}, t1 + t3 = t and
∗
attacks on Takagi’s variant of RSA,” Applied Cryptography and Net-
work Security, LNCS, vol.8479, pp.134–150, Springer, 2014.
t = θi , θi + 1, θi + 2, · · · , m. It is easy to check that all
[14] M. Joye and T. Lepoint, “Partial key exposure on RSA with private the monomials contained in h2 (x, y, z, u) have the form of
exponents larger than N,” Information Security Practice and Experi- zi xt1 x j1 y j2 u j3 , where j1 + j2 + j3 = t3 . If i  j2 , we have
ence, LNCS, vol.7232, pp.369–380, Springer, 2012.
[15] P.C. Kocher, “Timing attacks on implementations of Diffie-Hell- zi xt1 x j1 y j2 u j3 = xt1 + j1 y j2 −i (yz)i u j3 = xt1 + j1 y j2 −i (u − A)i u j3 .
man, RSA, DSS, and other systems,” Advances in Cryptology, ∗
CRYPTO’96, LNCS, vol.1109, pp.104–113, Springer, Berlin, 1996. Thus the monomials have the form of xt1 + j1 y j2 −i u j3 + j , where
[16] P. Kocher, J. Jaffe, and B. Jun, “Differential power analysis,” Ad- j∗ = 0, 1, 2, · · · , i. Notice that (t1 + j1 ) + ( j2 − i) + ( j3 + j∗ ) =
vances in Cryptology, CRYPTO’99, LNCS, vol.1666, pp.388–397, t1 + t3 − i + j∗ = t − i + j∗ , therefore
Springer, Berlin, 1999.
[17] N. Kunihiro, “Solving generalized small inverse problems,” In- ∗

t
formation Security and Privacy, LNCS, vol.6168, pp.248–263, xt1 + j1 y j2 −i u j3 + j ∈ Gt−i+ j∗ ⊂ G j ⊂ B1 .
Springer, Heidelberg, 2010. j=t−i
[18] N. Kunihiro, “On optimal bounds of small inverse problems and ap-
proximate GCD problems with higher degree,” Information Secu- If i > j2 , we have
rity, LNCS, vol.7483, pp.55–69, Springer, Heidelberg, 2012.
[19] N. Kunihiro, N. Shinohara, and T. Izu, “A unified framework for zi xt1 x j1 y j2 u j3 = zi− j2 xt1 + j1 (yz) j2 u j3 = zi− j2 xt1 + j1 (u−A) j2 u j3 .
small secret exponent attack on RSA,” Selected Areas in Cryptogra- ∗
phy, LNCS, vol.7118, pp.260–277, Springer, Heidelberg, 2012. Thus the monomials have the form of zi− j2 xt1 + j1 u j3 + j , where
[20] A.K. Lenstra, H.W. Lenstra, and L. Lovász, “Factoring polynomials j∗ = 0, 1, 2, · · · , j2 . Notice that (t1 + j1 ) + ( j3 + j∗ ) = t1 +
with rational coefficients,” Math. Ann., vol.261, no.4, pp.515–534, t3 − j2 + j∗ = t − j2 + j∗ . According to the condition θi∗ +1 
1982.
[21] S. Maitra and S. Sarkar, “A new class of weak encryption expo-
θi∗ + 1 (i∗ = 1, 2, · · · , τ − 1) in Proposition 4.1, we know
nents in RSA,” Cryptology-INDOCRYPT 2008, LNCS, vol.5365, θi  θi− j2 + j2 . Combining with j∗  0, t  θi , we get
pp.337–349, Springer-Verlag, Berlin Heidelberg, 2008. t − j2 + j∗  t − j2  θi − j2  θi− j2 . Namely the definitions
[22] A. May, New RSA vulnerabilities using lattice reduction methods. of set Hi− j2 ,t− j2 + j∗ and set H∗i− j2 ,t− j2 + j∗ make sense. And we
WANG et al.: A NEW ATTACK ON RSA WITH KNOWN MIDDLE BITS OF THE PRIVATE KEY
2685

have Longjiang Qu received his B.S. degree in

2002 and Ph.D. degree in 2007 in mathemat-
∗

t
ics from National University of Defense Tech-
zi− j2 xt1 + j1 u j3 + j ∈ Hi− j2 ,t− j2 + j∗ ⊂ Hi− j2 , j ⊂ Pi− j2 ⊂ B2 . nology, Changsha, China. He is now a pro-
j=t− j2 fessor with the Department of Mathematics and
System Science, National University of Defense
Similarly, the rightmost monomial must be zi xt1 ut3 (take Technology of China. His research fields in-
∗
j2 = 0, j∗ = 0, j1 = 0, j3 = t3 for zi− j2 xt1 + j1 u j3 + j ). clude cryptography and coding theory.
From the above, we have proved that the construction
of matrix B makes sense. And since the rightmost monomial
contained in h1 (x, y, z, u) = xt1 yt2 f t3 W m−t3 or h2 (x, y, z, u) =
zi · xt1 f t3 W m−t3 is xt1 yt2 ut3 or zi xt1 ut3 , we know that B is a Chao Li received the B.S. degree in math-
lower triangular matrix. Thus Proposition 4.1 follows.  ematics in 1987 from the University of Infor-
mation Engineering of China, the M.S. degree
in mathematics in 1990 from the University
Appendix B: Accurate Analysis for ε of Science and Technology of China, and the
Ph.D. degree in engineering in 2002 from the
National University of Defense Technology of
Precisely, the condition of our attack is
China. Since December 2001, he has been a pro-
fessor with the Department of Mathematics and
det(Λ)T 1 (s) < W m(s−v+1) , T 1 (s) = 2 s(s−1)/4 s(s−v+1)/2 , System Science, National University of Defense
Technology. His research fields include coding
and in calculation we should consider constant factors 3, 4 in theory, cryptography and sequences.
4
Z, U and terms o(m
m4
)
. Hence Inequality (9) should be rewrit-
ten as

3η2 + 2η − 2(α + β − 1) − ε∗ > 0, Shaojing Fu received the Ph.D. degree in

mathematics in 2010 from National Universitry
o(m4 ) of Defense Technology, Changsha, China. He
where ε∗ = ε1 + ε2 and ε1 = m4
, ε2 = logN T 2 (m, η), is now a associate professor with the College of
4 4
Computer Science, National University of De-
− ξ +12ξ 2 + o(m4 )
6 4
− ξ +8ξ+2+ o(m4 )
2 4 48
T 2 (m, ξ) = 3 η2 m 4 η3 m T 1 (s) m4 . fense Technology of China. His research fields
include cryptography and information security.
There exists large enough m to make |ε1 | arbitrarily small.
When we fix m, T 2 (m, η) is also fixed. Then we can select
large enough N to make |ε2 | arbitrarily small. Thus |ε∗ | can
be arbitrarily small. It is this “ε∗ ” that exactly contributes a
“−ε” in the right side of Inequality (10). After replacing ε
with |ε| (becomes a sufficient condition) and still denoting it
by ε, we have ε > 0. Since |ε∗ | is arbitrarily small, so is ε (if
m and N are large enough).

Shixiong Wang received his B.S. degree in

mathematics in 2013 from Tsinghua University,
Beijing, China. He is now a master student with
the Department of Mathematics and System Sci-
ence, National University of Defense Technol-
ogy of China. His research fields include cryp-
tography and coding theory.