II. Das Schlüsseltauschproblem und seine Lösung

1. Das Schlüsseltausch-Paradoxon

Das zentrale Problem der symmetrischen Kryptografie besteht darin, wie Alice und Bob einen gemeinsamen Schlüssel vereinbaren können, ohne dass jemand anderes in den Besitz dieses Schlüssels gelangt. Man muss dabei davon ausgehen, dass der Kanal zwischen Alice und Bob unsicher ist, d.h. dass jemand (Eve) jede Kommunikation zwischen Alice und Bob mithört (wäre der Kanal sicher, könnte man ja direkt die Meldung darüber verschicken und man müsste keine Verschlüsselung verwenden).

Lange dachte man, dass für dieses Problem keine Lösung existiert:
Wenn Eve alles mithört, dann hat sie genau dieselben Informationen wie Alice und Bob und sie kann doch den Schlüssel ihrerseits auch erstellen? Man dachte also, dass die einzige Lösung sei, den Schlüssel selbst verschlüsselt zu übertragen, wofür man wiederum einen Schlüssel benötigen würde u.s.w. Man spricht deshalb auch vom Schlüsselaustausch-Paradoxon. Lange Zeit wurden die Schlüssel somit persönlich übergeben, was natürlich sehr umständlich ist.

Ein Gedankenexperiment zur Lösung des Schlüsseltauschproblems

Zirka vor fünfzig Jahren gab es einige verwegene Kryptografen, die daran glaubten, dass es eine Lösung für das Schlüssel-Austauschproblem geben könnte. Zwei von ihnen waren Whitfield Diffie und Martin Hellman Ihre leidenschaftliche Suche nach einer Lösung für das Schlüsselproblem führte die beiden zusammen und die Ergebnisse ihrer gemeinsamen Bemühungen sollten schliesslich in die Geschichte der modernen Kryptografie eingehen.

Das folgende, einfache Gedankenexperiment liess Diffie und Hellman hoffen, dass es eine Lösung für das Problem geben könnte:

Angenommen der Schlüssel bestehe aus einer bestimmten Farbmischung. Wie können Alice und Bob eine gemeinsame Farbe mischen, ohne dass Eve dieselbe Mischung herstellen kann?

• A und B starten mit einem leeren Kanister, der drei Liter fasst. Eve wird ihrerseits einen Kanister mit drei Litern Inhalt besorgen.
• A und B vereinbaren eine bestimmte Farbe (beispielsweise Hellblau) und füllen einen Liter dieser Farbe in den Kanister.
• Da Eve alles mithört, wird auch sie einen Liter Hellblau in ihren Kanister geben.
• Nun wählen A und B je eine geheime Farbe und mischen einen Liter davon in ihren Kanister. A wählt z.B. Rot und erhält eine dunkelblau-violette Mischung und B wählt Gelb und erhält eine grüne Mischung.
• Die beiden Kanister werden ausgetauscht.
• Eve sieht die Kanister mit den Farbmischungen, doch sie kann die Mischungen nicht „trennen“, d.h. sie kann nicht herausfinden, welchen Farbton B resp. A hinzugefügt haben.
• Nach dem Erhalt des Kanisters fügen A und B jeweils einen Liter ihrer geheimen Farbe hinzu und so erhalten beide genau dieselbe Farbe: eine Mischung aus 1 Liter Hellblau, 1 Liter Rot und 1 Liter Gelb. Alice und Bob haben also eine gemeinsame Farbe (Braun) generiert, ohne dass es Eve möglich ist, diese Farbe herauszufinden.

2. Die Umsetzung durch Diffie und Hellman

Um die Idee aus dem Gedankenexperiment mit den Farbmischungen umsetzen zu können, benötigt man eine Funktion, die leicht auf eine Zahl angewendet werden kann, die aber nur sehr schwer rückgängig gemacht werden kann. Diese Funktionen können als Einwegfunktionen bezeichnet werden. Zudem müssen die Funktionen, die Alice und Bob anwenden untereinander kommutativ sein, d.h. die Reihenfolge in welcher sie angewendet werden darf keine Rolle spielen.

2.1 Diskrete Exponentialfunktion und diskreter Logarithmus

Betrachtet man Exponentialfunktionen modulo p (diskrete Exponentialfunktionen) $f(x)=a^x \mod p$, so fällt auf, dass für einige $a$ und $p$ nur sehr wenige y-Werte entstehen, während für andere $a$ und $p$ als y-Werte alle Zahlen von 1 bin p-1 entstehen:

Für $f(x) = 11^x \mod 19$ erhält man beispielsweise nur die drei Werte 1, 11 und 7 während man für $f(x)=3^x \mod 19$ alle Zahlen von 1 bis 18 erhält.

2.2 Der Schlüsseltausch nach Diffie/Hellman

Nun wollen wir uns an einem Beispiel den Schlüsseltausch nach Diffie und Hellman anschauen. Genau wie im Gedankenexperiment mit den Farben gibt es eine öffentliche Information, die Alice und Bob austauschen und es eine private Information, die Alice und Bob für sich behalten. Der Schlüsseltausch funktioniert folgendermassen:

1. Alice und Bob vereinbaren eine Zahl $g$ und eine Zahl $p$ und tauschen diese aus.
   Sie definieren damit eine Funktion $f(x) = g^x \mod p$
   Sie wählen beispielsweise $g = 53$ und $p = 127$ und erhalten die Funktion $f(x) = 53^x \mod 127$.
2. Nun wählt jeder für sich eine geheime Zahl. Alice wählt z.B. A=101 und Bob B=71.
3. Alice und Bob setzen ihre Geheimzahl in die Funktion ein. Alice erhält $f(101) = 53^{101} \mod 127 = 97$, Bob erhält $f(71)=53^{71} \mod 127 =48$.
4. Nun tauschen beide ihr Ergebnis aus, d.h. Alice schickt ihre Zahl $\alpha = 97$ an Bob und Bob schickt $\beta = 48$ an Alice.
5. Alice erhält die Zahl $\beta = 48$ von Bob und rechnet diese Zahl hoch ihre Geheimzahl (modulo 127). Sie erhält 91.
6. Bob erhält die Zahl $\alpha = 97$ von Alice und rechnet diese Zahl hoch seine Geheimzahl (modulo 127). Er erhält 91.

2.3 Welche Werte für g und p sind gut?

Wie kann man nun entscheiden, welche Kombination von g und p gut ist, d.h. wie weiss man, dass $f(x) = g^x \mod p$ alle Zahlen von 1 bis p-1 generiert ohne alle Zahlen ausrechnen zu müssen? Man spricht dann davon, dass $g$ ein Generator der Gruppe {1,2,3,… p-1} (Z modulo p) ist.

Hierfür gibt es den folgenden Satz:

Satz

Ist $q_1^{k1}\cdot q_2^{k2}\cdot q_3^{k3}\cdot ... q_n^{kn}$ die Primfaktorzerlegung von $p-1$, so ist $g$ genau dann ein Generator von Z modulo p, wenn $g^{(n-1)/q_i} \neq 1 \mod p$ für alle $q_i$.

Zurück zur Übersicht