Cryptography Reference
In-Depth Information
Beispiel
Ein Netzwerk bestehe aus drei Teilnehmern, die zur Verschlüsselung ihrer Kom-
munikation das RSA-Verfahren benutzen. Die öffentlichen Schlüssel der Teilneh-
mer seien
(
)
(
)
(
)
n
1
,3
,
n
2
,3
bzw.
n
3
,3
mit
=
=
=
n
1
205 ,
n
2
319 ,
n
3
391 .
Ein Klartext wird mit dem öffentlichen Schlüssel der drei Teilnehmer zu den Ge-
heimtexten
C
3
verschlüsselt und an diese gesandt. Dabei gelangen einem
Angreifer
A
die Geheimtexte
C
1
,
C
2
,
C
1
=
102 ,
C
2
=
193 ,
C
3
=
121
in die Hände. Der Angreifer
A
berechnet hieraus mithilfe des chinesischen Rest-
satzes die eindeutig bestimmte Lösung des Kongruenzgleichungssystems
X
≡
102
(
mod
n
1
)
,
X
≡
193
(
mod
n
2
)
,
X
≡
121
(
mod
n
3
)
und erhält
c
=
512. Durch Ziehen der dritten Wurzel aus
c
erhält
A
die Zahl
=
a
8. Das ist der Klartext.
Bemerkung
Häufig wird
e
2
16
=
+
1 gewählt. Diese Fermat'sche Primzahl ist ziemlich sicher
teilerfremd. Für die Berechnung von
a
e
mit der schnellen Exponentiation
(siehe Abschnitt 6.3) werden nur 17 Multiplikationen benötigt.
zu
ϕ
(
n
)
7.4.3 Die Wahl von
d
Die Zahl
d
ist bestimmt durch die Wahl von
e
. Aber man sollte beachten, dass
die Zahl
d
nicht zu klein ausfällt. Falls doch, so sollte ein anderes
e
gewählt wer-
den. Bei kleinem
d
ist nämlich der sogenannte
Wiener-Angriff
ernst zu nehmen.
Wir erläutern diesen nach der hierzu notwendigen Einführung in die Theorie der
Kettenbrüche.
7.5 Kettenbrüche *
Der
Wiener-Angriff
auf RSA basiert auf der Theorie der Kettenbrüche. Ketten-
brüche liefern eigentlich ein Verfahren, reelle Zahlen durch rationale Zahlen zu
approximieren. Wir konzentrieren uns darauf, rationale Zahlen durch rationale
zu approximieren, daher werden wir mit meist mit
endlichen
Kettenbrüchen aus-
kommen.
