Asymmetrische Verschlüsselung - Kryptografie - page 185

leme. Im Gegensatz dazu sind keine effizienten Verfahren bekannt, mit denen aus
dem Produkt zweier Primzahlen die beiden Faktoren bestimmt werden können.
Um dies nachvollziehen zu können, hier ein kleiner Test: Berechnen Sie im Kopf
das Resultat der Multiplikation 13·17. Dann bestimmen Sie zum Vergleich die
beiden Primzahlen, die miteinander multipliziert 217 ergeben (natürlich auch im
Kopf). Damit können Sie sich in etwa vorstellen, warum die Primzahl-Multi-
plikation als Einwegfunktion gilt.
Es gibt auch tiefer gehende Untersuchungen, und diese haben ähnliche Resul-
tate hervorgebracht wie bei der Modulo-Exponentiation: Auch wenn sich nicht
beweisen lässt, dass die Primzahl-Multiplikation eine Einwegfunktion ist, so
spricht doch alles dafür. Man bezeichnet das Zerlegen eines Primzahlprodukts
auch als Faktorisierung und spricht in diesem Zusammenhang vom Faktorisie-
rungsproblem . Dieses spielt in der Kryptografie eine wichtige Rolle (ein interes-
santer Artikel dazu ist [Buch96]). Einen Computer dürfte die Faktorisierung einer
Zahl wie 217 zwar noch nicht in Verlegenheit bringen. Bei einigen hundert Bit
jedoch geht selbst der stärkste Superrechner in die Knie. Wie sich die Einweg-
funktion Primzahl-Multiplikation in eine Falltürfunktion umwandeln lässt,
erfahren Sie im Abschnitt über RSA (11.3).

11.2 Der Diffie-Hellman-Schlüsselaustausch

Kehren wir nach diesem mathematischen Exkurs wieder zum Ausgangspunkt
dieses Kapitels zurück: Alice und Bob wollen verschlüsselt kommunizieren, ohne
dabei einen geheimen Schlüssel über das Netz schicken zu müssen (Schlüsselaus-
tauschproblem). Einweg- und Falltürfunktionen sind in der Lage, dieses Problem
zu lösen. Ein Verfahren, das den diskreten Logarithmus zur Lösung des Schlüssel-
austauschproblems verwendet, wurde von den Kryptografen Whitfield Diffie und
Martin Hellman erfunden und wird deshalb als Diffie-Hellman-Schlüsselaus-
tausch (oder auch nur als Diffie-Hellman-Verfahren ) bezeichnet. Mit ihrem Ver-
fahren begründeten Diffie und Hellman die asymmetrische Kryptografie und
sorgten für einen gewaltigen Schub in einer Wissenschaft, die damals noch nicht
sehr lange öffentlich betrieben wurde. Kein Wunder, dass die beiden ihre 1976
veröffentlichte Forschungsarbeit »New Directions in Cryptography« nannten
[DifHel].

11.2.1 Funktionsweise von Diffie-Hellman

Um einen Diffie-Hellman-Schlüsselaustausch durchzuführen, einigen sich Alice
und Bob auf eine Primzahl p und auf eine natürliche Zahl g . g sollte idealerweise
ein Generator der Gruppe Z( p ,·) sein, das Verfahren funktioniert aber auch,
wenn g einen anderen Wert kleiner als p annimmt. Die Zahlen p und g können
Alice und Bob guten Gewissens über das Internet schicken, denn Mallory darf sie