Exposing An RSA Private Key Given A Small Fraction of Bits
Exposing An RSA Private Key Given A Small Fraction of Bits
Exposing An RSA Private Key Given A Small Fraction of Bits
dabo
s.stanford.edu
Stanford University
Glenn Durfeey
gdurf
s.stanford.edu
Stanford University
Yair Frankel
yfrankel
ryptographers.
om
Te
hTegrity LLC
Abstra
t
We show that for low publi
exponent rsa, given a quarter of the bits of the private key
an adversary
an re
over the entire private key. Similar results (though not as strong) are
obtained for larger values of e. For instan
e, when e is a prime in the range [N 1=4 ; N 1=2,
half the bits of the private key su
e to re
onstru
t the entire private key. Our results point
out the danger of partial key exposure in the rsa publi
key system.
1
Introdu tion
as an n-bit string. When referring to the t most signi
ant bits of d we refer to the t leftmost
bits of d when viewed
anoni
ally as an n-bit string. For instan
e, it is possible that the t most
signi
ant bits of d are all zero, for some t. Similarly, a quarter of the bits of d always refers to
n=4 bits.
d
1.1
Summary of Results
We summarize our results in the following two theorems. The proofs are given in the body of
the paper. The rst theorem applies to low publi
exponent rsa. Thep se
ond applies toplarger
values of e. Throughout we assume N = pq is an rsa modulus with N =2 < q < p < 2 N .
Theorem 1.1 Let N = pq be an n-bit rsa modulus with N = 3 mod 4. Let 1 e; d (N )
satisfy ed 1 mod (N ) and e < 2 n=
. Then there is an algorithm that given hN; ei and
the n=4 least signi
ant bits of d
omputes all of d in polynomial time in n and e.
As we shall see, the running time of the atta
k algorithm in the above theorem is in fa
t
linear in e log e. Consequently, as long as e is not \too large" the atta
k
an be e
iently
mounted. For a very small value of e su
h as e = 3 we will show in Se
tion 5 that the atta
k
runs in a reasonable amount of time. For larger values, su
h as e = 65537, the atta
k is still
feasible, though
learly takes mu
h longer.
Theorem 1.2 Let N = pq be an n-bit rsa modulus. Let 1 e; d (N ) satisfy ed
1 mod (N ).
1. Suppose e is a prime in the range f2t ; : : : ; 2t g with n=4 t n=2. Then given the t
(
4)
+1
2. More generally, suppose e 2 f2t ; : : : ; 2t+1 g is the produ
t of at most r distin
t primes with
n=4 t n=2. Then given the fa
torization of e and the t most signi
ant bits of d there
is an algorithm to
ompute all of d in time polynomial in n and 2r .
3. When the fa
torization of e is unknown, we obtain a weaker result. Suppose e is in the
range f2t ; : : : ; 2t+1 g with t 2 0 : : : n=2. Further, suppose d > N for some > 0. Then
there is a polynomial time (in n and 1=) algorithm that given the n t most signi
ant
bits of d,
omputes all of d.
Theorem 1.2 applies to publi
exponents e in the range 2n= e 2n= . Unlike the previous
theorem, Theorem 1.2 makes use of the most signi
ant bits of d. When e is prime, at most half
the bits of d are required to mount the atta
k. Fewer bits are needed when e is smaller. Indeed,
if e is
lose to N = only a quarter of the msb bits of d are required. The same result holds
when e is not prime, as long as we are given the fa
torization of e and e does not have too many
distin
t prime fa
tors. The last part of the theorem applies to e < N = when the fa
torization
of e is not known. To mount the atta
k, at least half the msb bits of d are required. More
bits are ne
essary, the smaller e is. The atta
k algorithm works for most e, but may fail if d is
signi
antly smaller than N .
One may rene Theorem 1.2 in many ways. It is possible to obtain other results along these
lines for publi
exponents e < N = . For instan
e,
onsider the
ase when the fa
torization
of e is unknown. If the adversary is given half the most signi
ant bits of d and a quarter
4
1 4
1 2
1 2
of the least signi
ant bits then we show the adversary
an re
over all of d. When e < N =
this is better than the results of Theorem 1.2 part (3). However, we view atta
ks that require
non-
onse
utive bits of d as arti
ial. We brie
y sket
h these variants in Se
tion 4.3.
1 4
1.2
Related Work
We note that Wiener [24 showed that rsa is inse
ure whenever the private exponent
d is less
p
than N = (the bound was re
ently improved by Boneh and Durfee [3 to N = N : ).
In other words, Wiener's bound shows that when the 3=4 most signi
ant bits of d are zero
an adversary
an e
iently re
over the remaining quarter. These results do not apply to our
problem: Wiener's
ontinued fra
tions approa
h, as well as the method used by Boneh and
Durfee, does not work e
iently when the most signi
ant bits of d are given to the adversary
but they are non-zero.
Maurer [17 studies the problem of fa
toring an rsa modulus N with the help of an (innitely
powerful) ora
le that answers arbitrary yes/no questions. He shows that n queries su
e to
fa
tor N in probabilisiti
polynomial time with failure probability at most N = . One may
view our results as a method for fa
toring N using between n=4 and 3n=4 queries of an ora
le,
but one based on a weaker (and seemingly more natural) assumption. Namely, when viewed in
this way, our atta
ks use an ora
le that is restri
ted to revealing
ertain bits of an rsa private
exponent.
There has been re
ent work on prote
ting against partial key exposure using exposure resilient
ryptography. Initial progress was made several years ago by Chor et al. [5, who develop
the notion of t-resilient fun
tions and dis
uss an appli
ation to prote
tion against partially
leaked
ryptographi
keys. More re
ent work has fo
used on exposure resilient fun
tions, introdu
ed by Canetti et al. [4, whi
h
an be used to prote
t against partial key exposure for
a variety of
ryptographi
primitives. These ideas were later rened by Dodis [9 and Dodis,
Sahai, and Smith [10. For the rsa publi
key
ryptosystem, Steinfeld and Zheng [23 have
shown that by
arefully
hoosing p and q (instead of sele
ting them at random as is typi
al in
pra
ti
e) the low publi
exponent partial key exposure atta
ks presented in this paper
an be
prevented.
1 4
(1
2)
0 292
1.3
Notation
Throughout the paper we let Np= pq denote an n-bit rsa modulus. We assume the primes p
and q are distin
t and
lose to N . More pre
isely, we assume
p
p
4 < N =2 < q < p < 2 N
(1)
Our results also apply to rsa moduli N = pq where p is mu
h larger than q, but we do not give
the details here.
p
Noti
e that equation (1) implies p + q < 3 N . For
onvenien
e, throughout the paper we
set
s := p + q:
3
Our results make heavy use of seminal results due to Coppersmith. Using the latti
e basis
redu
tion algorithm of Lenstra, Lenstra, and Lovasz [14, Coppersmith [6 shows how to nd
small solutions (x ; y ) to a bivariate polynomial f (x; y), provided appropriate bounds on x
and y are known in advan
e.
Theorem 2.1 (Coppersmith[6) Let f (x; y ) be a polynomial in two variables over Z, of maximum degree in ea
h variable separately, and assume the
oe
ients of f are relatively prime
as a set. Let X , Y be bounds on the desired solutions x , y . Dene f~(x; y) := f (Xx; Y y) and
let D be the absolute value of the largest
oe
ient of f~. If XY < D = , then in time polynomial in log D and 2 , we
an nd all integer pairs (x ; y ) with p(x ; y ) = 0; jx j < X; jy j < Y .
We make use of an immediate
onsequen
e of this theorem, whi
h is a slight generalization
of a result in [6.
Corollary 2.2 Let N = pq be an n-bit rsa modulus. Let r 2n= be given and suppose
p := p mod r is known. Then it is possible to fa
tor N in time polynomial in n. (We denote
this running time TC (n)).
Proof Without loss of generality, assume p and r are relatively prime (otherwise the problem
is trivial). Then, p and r are also relatively prime. From p := p mod r we may nd q :=
q N=p mod r . We seek a solution (x ; y ) to f (x; y ) = (rx + p )(ry + q )
N , where
n=
n=
0 x < X = 2 =r (similarly y < Y = 2 =r). Noti
e, however, that the greatest
ommon divisor of the
oe
ients of the polynomial f (x; y) is r, so to use Theorem 2.1, we
must divide through by r to get a new polynomial g(x; y) = f (x; y)=r. Now noti
e that the
largest
oe
ient of g~(x; y) = g(Xx; Y y) is at least 2n =r. So, to use Theorem 2.1 we require
XY = r 2n < (2n =r ) = ;
whi
h is satised whenever r > 2 n = . By exhaustive sear
h on the rst two bits of x and
y this
an be redu
ed to r 2n= .
0
2 (3 )
2+1
2+1
+2
+2
( +2) 4
+2
2 3
Throughout the remainder of the paper, we denote by TC (n) the running time of the algorithm of Corollary 2.2. We remark that TC (n) =
(n ), so the running time of this algorithm
dominates other arithmeti
operations in our atta
ks.
3
In this se
tion we
onsider atta
ks on the rsa
ryptosystem with a \small" exponent e. For
our purposes, \small" implies that exhaustive sear
h on all values less than e is feasible. In
parti
ular, sin
e k e holds, our atta
k algorithm
an exhaustively sear
h all possible
andidates k0 for k (re
all that k is the unique integer satisfying de k(N ) = 1). We
an now prove
Theorem 1.1, restated more pre
isely as follows.
Theorem 3.1 With the notation as in Se
tion 1.3, suppose N 3 mod 4 and e 2 n=
.
Then given the n=4 least signi
ant bits of d, we
an fa
tor N in time O(TC (n) e log e).
Proof Suppose we are given the least-signi
ant n=4-bit blo
k of d; that is, we know some d
su
h that d d mod 2n= . Redu
ing equation (4) modulo 2n= and substituting s = p + N=p,
we see that p mod 2n= is a solution for x in the equation
ed 1 + k (N
x N=x + 1) (mod 2n= ):
This leads to the following quadrati
equation in x:
kx + (ed
k (N + 1) 1)x + kN 0 (mod 2n= ):
(5)
The atta
k works as follows: for every
andidate value k0 for k in the range f1; : : : ; eg do:
1. Use the algorithm outlined below to
ompute all solutions for x mod 2n= to the equation
k 0 x + (ed
k 0 (N + 1) 1)x + k 0 N 0 (mod 2n= ):
(6)
2. For ea
h solution x mod 2n= so obtained use the algorithm of Corollary 2.2 to attempt to
fa
tor N . Sin
e one of these solutions will satisfy x p mod 2n= the atta
k will su
eed in
fa
toring N .
To
omplete the des
ription of this atta
k we must des
ribe the algorithm to obtain solutions
to equation (6) and we must bound the total number of solutions as k0 ranges over all
andidates
for k. Consider rst the
ase k0 = k. Noti
e that k divides the
oe
ients of the quadrati
term and the
onstant term of equation (5); to see that k divides the
oe
ient of the linear
term, observe ed k(N + 1) 1 = k(p + q). Suppose k = 2tk m for some integer tk and odd
integer m. Then every solution x to equation (5) satises
mx
m(p + q )x + mN 0 (mod 2 n= tk ):
Furthermore, m is odd so m mod 2 n= tk is well-dened, thus every su
h solution x satises
x
(p + q)x + N 0 (mod 2 n= tk ):
(7)
We may
omplete the square to obtain
(x (p + q)=2) ((p q)=2) (mod 2 n= tk ):
(8)
(
4)
4)
4)
4)
4)
We note that the fra tions in this expression represent divison over the integers, whi h is well-dened sin e
p q mod 2.
4)
2+
2+
2+
2+
The
ase N 1 mod 4 requires
areful analysis, and R. Steinfeld and Y. Zheng
show that a modi
ation of the above atta
k has an expe
ted running time of O(TC (n) n
e log e) over random
hoi
e of n=2-bit primes p and q [23. They go on to des
ribe how to
hoose p and q to resist the above partial key exposure atta
k; this is a
hieved by for
ing p q
mod 2u for large values of u.
Remark 1.
2
We did not employ the full generality of Corollary 2.2, as mod r bits
ould have been used
for any r 2n= . This will be used in the next se
tion where we
onsider more sophisti
ated
key exposure atta
ks.
One may wonder whether a similar partial key exposure atta
k is possible using the most
signi
ant bits of d. The answer is no. The reason is that low publi
exponent rsa leaks half
the most signi
ant bits of d. In other words, the adversary may obtain half the most signi
ant
bits of d from e and N alone. Consequently, revealing the most signi
ant bits of d does not
help the adversary in exposing the rest of d. This is stated more pre
isely in the following fa
t.
4
()
()
Proof
)) . Let d~ be
q =e
Then
p
p
0 d~ d k(p + q)=e 3k N =e < 3 N
It follows that d~ mat
hes d on the n=2 most signi
ant bits of d. Hen
e, on
e k is known, the
half most signi
ant bits of d are exposed. With this observation, algorithm B
an work as
follows: try all possible values k0 for k in the range f1; : : : ; eg. For ea
h
andidate k0,
ompute
the
orresponding value d~ using k0 as a guess for k. Run algorithm A giving it half the most
signi
ant bits of d~. On
e the k0 = k, the entire private key is exposed.
Fa
t 3.2 demonstrates that
omputing the exponentiation asso
iated with the
half high-order bits of d
an be performed by an untrusted server. This may be of use in
server-aided rsa systems where te
hniques using the Chinese Remainder Theorem
annot be
employed. For instan
e, in threshold rsa [12, the fa
torization of the modulus is not known to
any party, so Chinese Remainder te
hniques are of no help in a
elerating
omputation. Fa
t
3.2 suggests that the half high-order bits of d
an be revealed to the server with no additional
ompromise in se
urity, allowing a
elerated
omputation by o-loading that portion of the
exponentiation operation.
Remark 2.
Fa
t 3.2 explains why for low exponent rsa one
annot mount a partial key re
overy atta
k
given the most signi
ant bits of d. It is natural to ask whether one
an expose all of d given
a quarter of the low order bits of d that are not ne
essarily the least signi
ant ones. For
instan
e, the following atta
k uses n=4 bits of d in bit positions n=4 to n=2, outlined below as
Theorem 3.3. Is it possible to generalize this result to every subsequen
e of n=4 bits from the
n=2 low-order bits of d? At the moment this is an open question.
Theorem 3.3 With the notation as in Se
tion 1.3, suppose jp q j 2 n=
and e 2 n=
.
Then given n=4 bits of d in positions n=4 to n=2, we
an fa
tor N in time O(TC (n) e ).
Proof Using the approximation d~ developed in Fa
t 3.2 and small exhaustive sear
h, we may
ompute bits n=2 to n of d. We now know bits n=4 to n of d; we denote this by d , so that
jd d j < 2n= . The atta
k tries every
andidate value k0 for k in the range f1; : : : ; eg. Dene
ed
1:
s := 1 + N
(
2)
k0
p1
d1
:= 12 (s +
1
<
s21
2 n=
(
4)+log 2
4N );
e:
4)
4)+5+log 2
We des
ribe several atta
ks on the rsa system that
an be employed when the publi
key e is
in the range 2n= to 2n= . Unlike the previous se
tion, these atta
ks require the most signi
ant
bits of d to be given. We mount the atta
k by
arefully studying equation (4):
ed k (N
s + 1) = 1
Re
all that s = p + q.
The key to mounting these atta
ks is in nding k. Sear
hing for k by brute for
e is infeasible,
sin
e k is an arbitrary element in the range f1; : : : ; eg. Fortunately, given su
iently many msb's
of d, we may
ompute k dire
tly, eliminating it as an unknown from equation (4). On
e k is
revealed, we are left with two unknowns, d and s whi
h we re
over using various methods. The
mainptool for dis
overing k is presented in the following theorem. It shows that as long as
e < N we
an nd k given only log e msb bits of d. The theorem produ
es a small
onstant
size interval
ontaining k. As always, we try all possible values of k in the interval until our
atta
k algorithm su
eeds.
Theorem 4.1 With the notation as in Se
tion 1.3, let t be an integer in the range f0; : : : ; n=2g.
Suppose 2t < e < 2t and we know the t most signi
ant bits of d. Then we
an e
iently
4
+1
The proof of Theorem 4.1 relies on the following lemma, whi
h provides general
onditions
under whi
h k
an be dedu
ed by rounding.
Lemma 4.2
j(
(i) e d
Suppose
d0
d0
)j <
N , and
1
satisfying ed k(N )
and = 2(8
2 + 2
1 ).
k
~ = (ed 1)=N
~ = (ed 1)=N . Then
Proof Let k
1 + e(d d )
~ k = (ed 1) 1
k
(N )
N
(N )
8
k
<
2 N =
3 2
( ) +
N
(N )N
(N )
N
Sin e N
( ) 4
The most signi
ant bits of d enable us to
onstru
t an integer d satisfying jd d j < 2n t .
We use Lemma 4.2 to
ompute k. By the restri
tion on e,
ondition (i) is satised with
= 2.
Sin
e d < N ,
ondition (ii) holds with
= 2. Hen
e k is an integer in a known interval of
width 40.
0
4.1
We are now ready to prove part (1) of Theorem 1.2. Theorem 4.1 enables us to nd k. On
e
is found we redu
e equation (4) modulo e. This removes d from the equation. We
an then
solve for s mod e. Given s mod e we are able to fa
tor the modulus.
Theorem 4.3 With the notation of Se
tion 1.3, let t be an integer in the range n=4 t n=2.
Suppose e is a prime in the range f2t ; : : : ; 2t g. Furthermore suppose we are given the t most
signi
ant bits of d. Then we
an fa
tor N in time O(TC (n)).
Proof The assumptions of the theorem satisfy the
onditions of Theorem 4.1. Consequently,
k is known to be an integer in a
onstant size range. We try all
andidate values k 0 for k . For
ea
h one we do the following:
1. Compute s0 N + 1 k0 (mod e). This is well-dened sin
e g
d(e; k0 ) = 1.
2. Compute a root p0 mod e for x in the quadrati
x
s0 x + N 0 (mod e)
(9)
This
an be done e
iently (in probabilisti
polynomial time) sin
e e is prime. Indeed,
on
e s0 s p + q mod e, then p0 p mod e.
3. Use Corollary 2.2 to nd p given p mod e. This is possible sin
e e 2n= .
On
e the
orre
t
andidate k0 = k is found (after a
onstant number of attempts) the
fa
torization of N is exposed. Ea
h attempt runs the algorithm of Corollary 2.2 on
e, leading
to a total running time that is O(TC (n)).
k
+1
A surprising
onsequen
e of this theorem is that, when e is prime and is roughly = 2n= ,
only the rst n=4 msb's of d are needed to mount the atta
k. This atta
k is as strong as the
one on low publi
exponent rsa. In any
ase, for prime e 2 f2n= ; : : : ; 2n= g, the rst n=2 most
signi
ant bits of d always su
e.
4
The proof shows that it is not ne
essary for e to be prime. As long as we
an solve the
quadrati
in step (2) the proof
an be made to work. In order to solve the quadrati
we must be
given the fa
torization of e. Unfortunately, modulo a
omposite, the quadrati
may have many
roots. We must try them all. If e has r distin
t prime fa
tors, there are at most 2r solutions
to
onsider. As a result, we must also bound the number of prime fa
tors of e. We obtain part
(2) of Theorem 1.2.
Corollary 4.4 As in Theorem 4.3 suppose e is an integer in the range f2t ; : : : ; 2t g. If e has
at most r distin
t prime fa
tors, and its fa
torization is known, then given the t most signi
ant
bits of d we
an fa
tor time O(TC (n) 2r ).
We point out that when e is
lose to 2n= the same atta
k
an be mounted even if the
fa
torization of e is unknown. In other words, for all e su
iently
lose to 2n= , half the msb's
of d are su
ient to re
onstru
t all of d. Indeed, the range f1; : : : ; d2n= =eeg
an be sear
hed
exhaustively to nd ds=ee. Given the value of ds=ee we
an obtain s (sin
e s mod e is already
known.) Sin
e s is now known in the integers, we
an dire
tly nd p using equation (2).
+1
2+2
4.2
We now turn to proving part (3) of Theorem 1.2. We
onsider the
ase when e is in the range
f2t ; : : : ; 2t g with 0 t n=2. The fa
torization of e is unknown. The following result
establishes that we
an still nd all of d, given some of its msb's. Our atta
k works as long
as k is not signi
antly smaller than e. At the end of the se
tion we note that the atta
k
heuristi
ally works for almost all e in the range f2t ; : : : ; 2t g.
Theorem 4.5 With the notation as in Se
tion 1.3, let t be an integer in the range f0; : : : ; n=2g.
Suppose e is in the range f2t ; : : : ; 2t g. Further suppose k > e for some > 0. Then there
is an algorithm that given the n t most signi
ant bits of d nds all of d. The algorithm runs
in time O(n =).
Proof Given the n t most signi
ant bits of d we
an
onstru
t a d su
h that 0 d d < 2t .
Sin
e e < 2n= we
an use d and Theorem 4.1 to limit k to a
onstant size interval. For ea
h
andidate k0 for k we do the following:
1. Compute d e mod k0 . This is possible sin
e e and k are relatively prime, so only
andidates k0 relatively prime to e are worth
onsidering. Sin
e ed k(n) = 1 we know
that d d mod k0 when k0 = k.
2. By assumption k0 > 2t . Note that at this point we know d mod k0 as well as the n t
msb's of d. We determine the rest of the bits by an exhaustive sear
h. More pre
isely,
write
d = k0 d + d
Then d = d =k0 +(d d )=k0 d =k0 . The only unknown term in this sum is v = (d d )=k0 .
Sin
e k0 > 2t we know that v = (d d )=k0 < 1=. To nd v, we try all possible
andidates v0 in the range f0; : : : ; 1=g. For ea
h pair (k0 ; v0 ) of
andidates we
ompute
the
orresponding value of d and test it.
3. On
e the
orre
t values v0 = v and k0 = k are found, d is exposed. Testing ea
h pair
(k0 ; v0 ) of
andidates takes O(n ) time, and there are O(1=)
andidate pairs to test.
+1
+1
+1
10
Theorem 4.5 works without having to know the fa
torization of e. Unfortunately, the results
are not as strong as in the previous se
tion. When e is
lose to N = , Theorem 4.5 implies that
3=4 of the bits of d are needed to re
onstru
t d. This is mu
h worse than the
orresponding
bound a
hieved in the previous se
tion, where only 1=4 the bits were required. When e is
lose
to N = the theorem produ
es results similar to the previous se
tion.
Theorem 4.5
an only be applied when k > e. Intuitively, k behaves roughly as a random
integer in the range f1; : : : ; eg. As su
h, we should have k > e=10 for about 90% of the
e 2 f2t ; : : : ; 2t g. Hen
e, heuristi
ally the atta
k works e
iently for almost all e.
1 4
1 2
+1
4.3
Further Results
What if the fa
torization of e is unknown and e was not randomly
hosen? Although it may be
omputationally infeasible, it is possible for e; d to be spe
i
ally
hosen as fa
tors of 1+ k(N )
for very small k, violating the
onditions of Theorem 4.5. We stress that this is parti
ularly
unlikely, as not only would the rather large value of 1 + k(N ) would need to be fa
tored
into ed, but a fa
tor e in the range f2n= ; : : : ; 2n= g would need to be obtained, and one that
itself
annot easily be fa
tored (making it vulnerable to Corollary 4.4). However, under these
ir
umstan
es, the above atta
ks would not apply. We
on
lude with the following general
result whi
h holds for all e < 2n= . Unfortunately, the result requires non-
onse
utive bits of d.
Theorem 4.6 With the notation as in Se
tion 1.3, let t be an integer in f1; : : : ; n=2g and e in
f2t ; : : : ; 2t g. Suppose we are given the t most signi
ant bits of d and the n=4 least signi
ant
bits of d. Then we
an fa
tor N in time O(TC (n)).
Proof Sket
h Using Theorem 4.1 we may
ompute a
onstant size interval I
ontaining k .
Observe that the proof of Theorem 3.1 applies for all e, as long as k and the n=4 least signi
ant
bits of d are known. To re
over d, run the algorithm of Theorem 3.1 on all
andidate values of
k in I .
4
+1
Experiments
To test the ee
tiveness of our atta
ks, we implemented them using the C++ programming
language with the Number Theory Library pa
kage by V. Shoup [22. The algorithm of Corollary 2.2 dominates the running time of our atta
ks (all other steps are e
ient arithmeti
operations), so its running time is the primary obje
t of dis
ussion in this se
tion.
It turns out that the most e
ient way to implement Corollary 2.2 is not to use the te
hnique
of Coppersmith to nd solutions to bivariate polynomials (as in Theorem 2.1), but instead to use
the Latti
e Fa
toring Method developed by Boneh, Durfee, and Howgrave-Graham for fa
toring
integers of the form pq. [2. We observe that a slight extension of the Latti
e Fa
toring Method,
des
ribed brie
y here,
an be used when we are given least signi
ant bits of one of the fa
tors
of an rsa modulus N = pq. (See [2, Lemma 3.3.) Suppose we are given p su
h that p p
modulo 2 n= . We seek a solution x for x in the equation
2 n= x + p 0 (mod p):
(10)
(
4)+
4)+
11
If we set A := (2 n=
4)+
4)+
1 4
0
4) 1
4)
+1
+1
512 bits
768 bits
1024 bits
bits of d exposed latti
e dim. LLL runtime ( TC (n)) observed total runtime
128 bits
16
13 se
onds
6
11 minutes
192 bits
24
6:3 minutes
5
2:8 hours
256 bits
24
26:8 minutes
6
21 hours
These experiments were run on a 500MHz Intel Pentium III pro
essor running Solaris.
Further optimization is possible if additional bits of d beyond the least n=4 are exposed:
ea
h additional bit of d redu
es by one, halving the exhaustive sear
h required; on
e = 0,
additional bits of d benet the algorithm by giving
loser approximations to p, allowing a
de
rease in the size of the latti
e.
For medium publi
exponent e, where e is prime, the atta
k pro
eeds similarly: with the
right guess for k, the value p mod e
an be determined, whi
h (unless e is very
lose to 2n= )
will reveal enough information to run the above algorithm with = 0. Thus, the running time
of an atta
k on medium, prime publi
exponent e will be equal to TC (n) in the table above
times the number of
andidates for k that must be
he
ked, whi
h is always less than or equal
to 40. With e of known fa
torization and r fa
tors, there is a multipli
ative in
rease of 2r in
running time to
ompute and
he
k the distin
t solutions to equation (9).
When the fa
tors of e are unknown and the n log e bits of d are given, the atta
k is
immediate { the algorithm suggested in Theorem 4.5 involves only a few simple arithmeti
operations and a very small sear
h.
4
Con lusions
We study rsa's vulnerability to partial key exposure. We showed that for low exponent rsa,
a quarter of the least signi
ant bits of d are su
ient for e
iently re
onstu
ting all of d. We
12
obtain
p similar results for larger values of e as long as e < N . For instan
e, when e is
lose to
N , half the most signi
ant bits of d su
e.
The results presented demonstrate the danger of leaking a fra
tion of the bits of d. We note
that dis
rete log s
hemes (e.g. DSS, ElGamal) do not seem vulnerable to partial key exposure.
A fra
tion of the bits of the private key in a dis
rete log based system does not seem to enable
the adversary to e
iently break the system.
There are a number of related open problems:
Does there exist a polynomial time algorithm
p whi
h enables one to break the rsa system
for values of e substantially larger than N , given only a subset of the bits of d?
Our strongest result with respe
t to the fewest bits of d required to break the system is
for an e in the range fN = ; : : : ; N = g with known fa
torization. For an e with unknown
fa
toriziation and in the same range, does there exist a polynomial time algorithm whi
h
provides as strong a result?
1 4
1 2
A knowledgements
The authors would like to thank Phong Nguyen, Ron Steinfeld, Yuliang Zheng, and Mi
hael
Jason Hinek for several helpful suggestions regarding the preliminary version of this paper.
Referen
es
[1 D. Boneh, G. Durfee, and Y. Frankel. An atta
k on RSA given a small fra
tion of the
private key bits. In pro
eedings Asia
rypt '98, Le
ture Notes in Computer S
ien
e,
vol. 1514, Springer-Verlag, pp. 25{34, 1998.
[2 D. Boneh, G. Durfee, and N. Howgrave-Graham. Fa
toring N = pr q for large r. In
pro
eedings Crypto '99, Le
ture Notes in Computer S
ien
e, vol. 1666, Springer-Verlag,
pp. 326{337, 1999.
[3 D. Boneh and G. Durfee. Cryptanalysis of RSA with Private Key d Less Than N : .
IEEE Transa
tions on Information Theory, vol. 46, no. 4, pp. 1339{1349, July 2000.
Extended abstra
t in Pro
eedings of Euro
rypt '99, LNCS vol. 1592, Springer-Verlag,
pp. 1{11, 1999.
[4 R. Canetti, Y. Dodis, S. Halevi, E. Kushilevitz, A. Sahai. Exposure-Resilient Fun
tions and All-or-Nothing Transforms. In pro
eedings Euro
rypt 2000, Le
ture Notes in
Computer S
ien
e, vol. 1807, Springer-Verlag, pp. 453{469, 2000.
[5 B. Chor, J. Friedman, O. Goldrei
h, J. Hastad, S. Rudi
h, R. Smolensky. The bit
extra
tion problem or t-resilient fun
tions. In pro
eedings 26th Annual Symposium on
Foundations of Computer S
ien
e (FOCS), pp. 396{407, 1985.
[6 D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA
vulnerabilities. Journal of Cryptology, vol. 10, pp. 233{260, 1997.
0 292
13
[7 C. Coupe, P. Nguyen, and J. Stern. The ee
tiveness of latti
e atta
ks against lowexponent RSA. In pro
eedings Publi
Key Cryptography '99, Le
ture Notes in Computer
S
ien
e, vol. 1751, Springer-Verlag, 1999.
[8 J-F. Dhem, F. Koeune, P. Leroux, P. Mestre, J-J. Quisquater, and J-L. Willems. A pra
ti
al implementation of the timing atta
k. In pro
eedings CARDIS '98 { Third smart
ard resear
h and advan
ed appli
ation
onferen
e, UCL, Louvain-la-Neuve, Belgium,
Sep. 14-16, 1998.
[9 Y. Dodis. Exposure-Resilient Cryptography. Ph.D. Thesis, MIT, 2000.
[10 Y. Dodis, A. Sahai, A. Smith. On perfe
t and adaptive se
urity in exposure-resilient
ryptography. In pro
eedings Euro
rypt 2001, Le
ture Notes in Computer S
ien
e,
vol. 2045, Springer-Verlag, pp. 301{324, 2001.
[11 T. ElGamal. A publi
key
ryptosystem and a signature s
heme based on the dis
rete
logarithm. IEEE Transa
tions on Information Theory, vol. 31, no. 4, pp. 469{472, 1985.
[12 Y. Frankel. A pra
ti
al proto
ol for large group oriented networks. In pro
eedings
Euro
rypt '89, Le
ture Notes in Computer S
ien
e, vol. 434, Springer-Verlag, pp. 56{
61, 1989.
[13 P. Ko
her. Timing atta
ks on implementations of Die-Hellman, RSA, DSS, and other
systems. In pro
eedings Crypto '96, Le
ture Notes in Computer S
ien
e, vol. 1109,
Springer-Verlag, pp. 104{113, 1996.
[14 A. Lenstra, H. Lenstra, and L. Lovasz. Fa
toring polynomials with rational
oe
ients.
Mathematis
he Annalen, vol. 261, pp. 515{534, 1982.
[15 H. Lenstra. Divisors in Residue Classes. Mathemati
s of Computation, vol. 42, no. 165,
pp. 331-340, 1984.
[16 N. Howgrave-Graham. Finding small roots of univariate modular equations revisited.
In pro
eedings Cryptography and Coding, Le
ture Notes in Computer S
ien
e, vol. 1355,
Springer-Verlag, pp. 131{142, 1997.
[17 U. Maurer. On the Ora
le Complexity of Fa
toring Integers. Computational Complexity,
vol. 5, pp. 237-247, 1996.
[18 P. Nguyen. Private
ommuni
ations, November 1998.
[19 I. Niven, H. Zu
kerman, and H. Montgomery. An Introdu
tion to the Theory of Numbers. Jon Wiley & Sons, Fifth Edition, pp. 87{88, 1991.
[20 D. Redmond. Number Theory: An Introdu
tion. Monographs and Textbooks in Pure
and Applied Mathemati
s, no. 201, Mar
el Dekker, 1996.
[21 R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and
publi
-key
ryptosystems. Communi
ations of the ACM, vol. 21, no. 2, pp. 120{126,
1978.
14
This appendix
onsiders the problem of nding solutions for y in equations of the form
y
(mod 2u );
(11)
where u 3 and
1 mod 8.
We begin with an algorithm to nd a solution to this equation presented in the following lemma. The proof appears in [20, p. 184. For
onvenien
e we rst dene the following
polynomial (with
oe
ients in Q ):
P (z ) :=
( 1) i 4i (2i1 1) 2ii zi :
i
Lemma A.1 Suppose u 3 and
1 mod 8. Then y := Pu (
1) is an integer whi
h
satises (y )
mod 2u .
This provides one solution to equation (11). The following shows how to
onvert any solution
to equation (11) into any other solution. We provide a proof dierent from what appears in [20.
Lemma A.2 Assume y ; y are in the range f0; : : : ; 2u 1g, and suppose y is a solution for
2
1)
=0
y1
y + 2u (mod 2u)
for some 2 f 1; 1g and 2 f0; 1g.
Proof Let 2 f 1; 1g and 2 f0; 1g be arbitrary, and let y be any solution to equation (11).
y1
If we dene y := y + 2u then we see
(y ) (y ) + 2uy + 2 u (mod 2u):
Sin
e u 3, we have 2u 2 u, so redu
ing modulo 2u yields
(y ) (y ) + 2u y + 2 u : (y ) (y )
(mod 2u );
so y is a solution for y in equation (11).
Now suppose that y and y are arbitrary soultions to equation (11). Sin
e
1 mod 8,
it follows that y y 1 mod 4. So y y mod 4, where 2 f 1; 1g. Thus there exists
some integer v su
h that y = y + 4v. From equation (11) we see
y (y + 4v ) y + 8y v + 16v
(mod 2u );
1
2
0
2
1
2 2
2 2
2
1
2
0
15
implying 8y v + 16v 0 mod 2u. So 2u divides 8y v + 16v = 8v(y + 2v ). Now, 2v is
even and y is odd (re
all y 1 mod 8), so it must be the
ase that 2u divides v. Hen
e,
y = y + 4v = y + 2u . Sin
e we are interested in solutions modulo 2u , all
hoi
es of
are equivalent to either = 0 or = 1.
2
2
0
1
The proof of the rst
lause is an immediate
onsequen
e of Lemmas A.1 and A.2. The
running time analysis follows from the des
ription of Lemma A.1. Note that it is espe
ially
e
ient to evaluate Pu (
1) when only its result modulo 2u is desired.
3
This appendix
onsiders the problem of bounding the error of the square roots of approximated
values. The main tool is the following lemma, needed for Theorem 3.3.
Lemma B.1 With the notation as in Se
tion 1.3, suppose jp q j 2 n=
and e 2 n=
.
n=
Furthermore suppose the quantities d ; s ; p satisfy jd dj < 2 ,
1
e;
js sj 2 n=
p = (s + s
4N ):
2
(
2)
4)
Then
4)+log 2
jp
j 2 n=
(
2
1
4)+5+log 2
e:
2
1
2
1
3+(
4)
1+log 2
4)
1+log 2
4)+5+log 2
16
2)
4)+log 2
2
4)+4+log 2
) 2 n=
(
4)
. The
as desired.
17