Cryptography Reference
In-Depth Information
7.6 Der Wiener-Angriff *
Der
Wiener-Angriff
auf RSA wurde 1990 von Michael Wiener [30] vorgestellt. Ist
der geheime Schlüssel
d
beim RSA-Verfahren nur
klein genug
, so erhält man even-
tuell den geheimen Schlüssel
d
als Nenner eines der Näherungsbrüche von
e
n
- hierbei sind
e
und
n
die Zahlen des öffentlichen Schlüssels
beim RSA-
Verfahren. Man kann den geheimen Schlüssel in diesem Fall also
einfach
ermit-
teln. Der Angriff basiert auf dem folgenden Satz:
(
n
,
e
)
Satz 7.18
Es seien p
,
q Primzahlen mit q
<
p
<
2
q, n
:
=
pq,
1
<
d
,
e
<
ϕ
(
n
)
,
1
3
n
1/4
. Dann ist
r
d
e
≡
(
ϕ
(
))
<
ed
1
mod
n
,d
ein Näherungsbruch für
n
, wobei
ed
−
1
=
)
∈
N
r
:
.
ϕ
(
n
<
√
n
. Damit gilt
p
gilt
q
2
<
<
=
Beweis.
Wegen
q
pq
n
, also
q
3
√
n
.
(
∗
)
n
−
ϕ
(
n
)=
pq
−
(
p
−
1
)(
q
−
1
)=
p
+
q
−
1
<
3
q
<
1
3
n
1/4
und somit
=
+
ϕ
(
)
ϕ
(
)
<
< ϕ
(
)
Und aus
ed
1
r
n
erhalten wir
r
n
ed
n
1
3
n
1/4
.
(
∗∗
)
r
<
Es folgt nun mit
(
∗
)
und
(
∗∗
)
:
−
=
−
(
+
ϕ
(
)) =
(
− ϕ
(
))
−
<
(
− ϕ
(
))
rn
ed
rn
1
r
n
r
n
n
1
r
n
n
3
n
1/4
3
√
n
1
n
3/4
.
<
=
Wir teilen diese Ungleichung durch
nd
und erhalten:
n
<
r
d
−
e
1
dn
1/4
1
3
d
2
1
2
d
2
.
<
<
Nun folgt mit Satz 7.17 (b) die Behauptung.
r
d
Der Quotient
lässt sich als Näherungsbruch effizient berechnen. Wegen
r
=
−
ed
1
gilt
ϕ
(
)
n
ed
−
r
ϕ
(
n
)=
1,
sodass die Zahlen
r
und
d
nach Lemma 4.8 (d) teilerfremd sind. Daher findet man
die Zahlen
r
und
d
mit Lemma 7.13 als Zähler und Nenner eines Näherungs-
bruchs von
n
.
Wir schildern nun den
Wiener-Angriff
auf RSA. Dabei gehen wir davon aus,
dass die Primzahlen
p
und
q
und der geheime Schlüssel
d
die Voraussetzungen
des Satzes 7.18 erfüllen:
Der Angreifer bestimmt alle Näherungsbrüche von
n
und testet, ob der Nähe-
rungsbruch
k
der gesuchte Bruch ist, d. h., ob
k
=
r
und
=
d
gilt.
