Cryptography Reference
In-Depth Information
7 Das RSA-Verfahren
Durch eine Modifikation des Pohlig-Hellman-Verfahrens gelangen wir zum
RSA-
Verfahren
, benannt nach R. L. Rivest, A. Shamir und L. Adleman. Dieses Ver-
schlüsselungsverfahren wurde 1977 vorgestellt. Es ist ein
asymmetrisches
oder
Public-Key-Verfahren
(vgl. Abschnitt 4.4). Zum Verschlüsseln einer Nachricht ist
kein vorheriger Schlüsselaustausch nötig, der Schlüssel zum Verschlüsseln eines
Klartextes ist öffentlich zugänglich.
Will der Sender
S
an den Empfänger
R
eine Nachricht
senden, so sucht
S
in
einem öffentlichen Verzeichnis den öffentlichen Schlüssel
e
von
R
, wendet ihn
auf seinen Klartext
N
N
an und sendet dann
R
den so erhaltenen Geheimtext
C
=
(
N
)
e
. Der Empfänger
R
hat einen geheimen Schlüssel
d
. Mit ihm kann er aus
dem Geheimtext
.
Die Sicherheit des Verfahrens beruht darauf, dass aus dem Geheimtext
C
den Klartext
N
wiederherstellen:
N
=
d
(
e
(
N
))
(
N
)
und dem öffentlichen Schlüssel
e
- der jedem zugänglich ist - in vertretbarer Zeit
nicht auf den Klartext
C
=
e
N
und auch nicht auf den geheimen Schlüssel
d
geschlos-
sen werden kann.
Dieses geniale Prinzip hat einen wesentlichen Vorteil: Die Schlüsselverwaltung
wird deutlich vereinfacht. Während bei einem symmetrischen Verfahren, d. h., es
ist ein vorheriger Schlüsselaustausch zwischen je zwei Teilnehmern nötig, für
n
Teilnehmer
n
(
−
)
/2 geheime Schlüssel ausgetauscht werden müssen, ist bei
einem Public-Key-Verfahren ein Verzeichnis aus nur
n
Schlüsseln nötig. Aber es
gibt auch einen Nachteil: Der Rechenaufwand bei allen bekannten asymmetri-
schen Verfahren ist deutlich höher als der bei einem symmetrischen Verfahren.
Für die Sicherheit des RSA-Verfahrens ist es wichtig, dass es imAllgemeinen sehr
schwer ist, eine (beim Verfahren benutzte und öffentlich bekannte)
große
natürli-
che Zahl
n
in ihre Primfaktoren zu zerlegen. Wir gehen auf diese und weitere
Fragen zur Sicherheit des RSA-Verfahrens ein und behandeln auch den
Wiener-
Angriff
, mit dem das RSA-Verfahren in einigen Spezialfällen gebrochen werden
kann, ohne die
große
natürliche Zahl
n
in ihre Primfaktoren zerlegen zu können.
Dieser Angriff erfordert einen etwas aufwändigen Einblick in die Theorie der
(endlichen) Kettenbrüche. Dieser Aufwand lohnt sich aber, weil wir beim Fakto-
risierungsproblem in Kapitel 11 diese Theorie erneut aufgreifen werden.
n
1
7.1 Das Verfahren von
R
ivest,
S
hamir und
A
dleman
Das Prinzip ist einfach: In einem öffentlich zugänglichen Verzeichnis liegen die
offenen Schlösser aller Teilnehmer. Sie wollen an
R
eine geheime Nachricht schi-
