Cryptography Reference
In-Depth Information
called
small private exponent RSA
.
8
We present the famous
Wiener attack
, which is a
polynomial-time attack on private exponents
d<N
1
/
4
.
Exercise 24.5.1
Give a brute-force attack on small private exponent RSA that tries each
odd integer
d>
1 in turn. What is the complexity of this attack?
We now sketch Wiener's idea [
564
]. We assume the key generation of Box
24.1
is used
so that
N
=
pq
where
p<q<
2
p
. Consider the equation defining
e
and
d
ed
=
1
+
kϕ
(
N
)
=
+
(a similar attack can be mounted using the equation
ed
1
kλ
(
N
), see
Exe
rcise
24.5.5
).
q
) and
√
N
=
+
−
+
≤
+
Sin
ce
e<ϕ
(
N
)wehave
k<d
.Now
ϕ
(
N
)
N
1
(
p
(
p
q
)
<
3
√
N
so
ϕ
(
N
)
3
√
N
. Rearranging gives
=
N
−
u
where 0
≤
u
=
p
+
q
−
1
≤
ku
)
<
3
k
√
N.
(24.3)
If
d
is smaller than
√
N/
3 then the right-hand side is
<N
. Hence, one could try to find
d
by running the extended Euclidean algorithm on (
e,N
) and testing the coefficient of
e
to see if it is a candidate value for
−
ed
+
kN
=
(
−
1
+
d
(e.g., by testing whether (
x
e
)
d
x
(mod
N
)fora
random 1
<x<N
). Note that one must use the basic extended Euclidean algorithm rather
than the faster variant of Algorithm
1
. We now explain that this method is guaranteed to
find
d
when it is sufficiently small.
±
≡
d
−
1
(mod
ϕ
(
N
))
where
0
<d<N
1
/
4
/
√
3
. Then given
(
N,e
)
one can compute d in polynomial-time.
Theorem 24.5.2
Let N
=
pq where p<q<
2
p are primes. Let e
=
Proof
Using the notati
on
above, (
d,k,uk
−
1) is a solution to equation (
24.3
) with 0
<
u<
3
√
N
.
The Euclidean algorithm finds all triples (
s,t,r
) satisfying
es
k<d
and 0
≤
+
Nt
=
r
with
|
sr
|
<N
and
|
tr
|
<e
. Hence, if
|
d
(
uk
−
1)
|
<N
then the required solution will be found. If 0
<
d<N
1
/
4
/
√
3 then
3
√
N
<d
2
u<
N
1
/
2
3
|
duk
|
=
N,
which completes the proof.
Example 24.5.3
Let
N
=
86063528783122081 with
d
=
8209. One computes that
e
=
14772019882186053.
One can check that
ed
=
1
+
1409
ϕ
(
N
)
.
Running Euclid's algorithm with
r
−
1
=
N
and
r
0
=
e
and writing
s
i
,t
i
to be such that
r
i
=
s
i
N
+
t
i
e
one finds the following table of values.
8
The reader should remember that, in practice, it is more efficient to use the Chinese remainder theorem to speed up RSA
decryption than small private exponents.
