Cryptography Reference
In-Depth Information
i
q
r
i
s
i
t
i
−
−−
1
86063528783122081
1
0
−−
0
14772019882186053
0
1
1
5
12203429372191816
1
−
5
2
1
2568590509994237
−
1
6
3
4
1929067332214868
5
−
29
4
1
639523177779369
−
6
35
5
3
10497798876761
23
−
134
6
60
9655245173709
−
138
8075
7
1
842553703052
1409
−
8209
One sees that
d
is found in only 7 steps.
Exercise
24.5.4
Consider
the
RSA
public
key
(
N,e
)
=
(11068562742977
,
10543583750987). Use the Wiener attack to determine the private key.
Exercise 24.5.5
Show how to perform the Wiener attack when
ϕ
(
N
) is replaced by
λ
(
N
).
What is the bound on the size of
d
for which the attack works?
Exercise 24.5.6
Let (
N,e
)
=
(63875799947551
,
4543741325953) be an RSA public key
where
N
=
pq
with gcd(
p
−
1
,q
−
1)
>
2 and small private exponent
d
such that
ed
≡
1(mod
λ
(
N
)). Use the Wiener attack to find
d
.
Exercise 24.5.7
Show that one can prevent the Wiener attack by adding a sufficiently large
multiple of
ϕ
(
N
)to
e
.
Wiener's result has been extended in several ways. Dujella [
170
] and Verheul and van
Tilborg [
557
] show how to extend the range of
d
while still using Euclid's algorithm. Their
algorithms are exponential time. Boneh and Durfee [
73
] used lattices to extend the attack
to
d<N
0
.
284
and, with significant further work, extended the range to
d<N
0
.
292
.Blomer
and May [
66
] give a simpler formulation of the Boneh-Durfee attack for
d<N
0
.
284
.
24.5.2 Small CRT private exponents
As mentioned in Section
24.1.1
, a common way to speed up RSA decryption is to use
the Chinese remainder theorem. Indeed, one can choose the CRT private exponents
d
p
and
d
q
to be small (subject to
d
p
≡
d
q
(mod gcd(
p
−
1
,q
−
1)) and define
e
such that
ed
p
≡
d
q
,or
else one can just apply the Wiener attack. We now show that these values cannot be taken
to be too small.
1(mod
p
−
1) and
ed
q
≡
1(mod
q
−
1). Of course, one should take
d
p
=
Exercise 24.5.8
Give a brute-force attack on small private CRT exponents.
We now present a “birthday attack”, which is attributed to Pinch in [
442
]. Let
d
p
be such
that
ed
p
≡
1(mod
p
−
1) and
ed
p
≡
1(mod
q
−
1). Suppose we know that 1
<d
p
<K
