Diffie-Hellman aus mathematischer Sicht

Problem des Schlüsselaustausches

Wenn man Daten oder Nachrichten übertragen will, ohne dass eine fremde Person sie lesen kann, so muss man sie wohl oder übel verschlüsseln. Um das zu tun braucht man, zumindest bei der symmetrischen Verschlüsselung einen geheimen gemeinsamen Schlüssel. Nun ist aber das nicht zu unterschätzende Problem des Schlüsselaustausches zu beachten: Wie bekommt mein Partner den Schlüssel für meine Nachricht, ohne ihn über das Internet, das Telefon zu schicken oder gar persönlich zu überreichen?
Dieses Probelm löst der Diffie-Hellman Algorithmus, den wir im folgenden darstellen wollen und uns auf die mathematischen Prinzipien konzentrieren. Weiterhin nehmen wir an, dass Alice und Bob miteinander verschlüsselt kommunizieren wollen, und Eve diese Nachrichten unbedingt lesen will.

Ausführen des Diffie-Hellamn Algorithmus an einem Bespiel




Im Vorfeld haben sich Bob und Alice auf eine Zahl Y telefonisch geinigt, die die Basis einer Gleichung
f(x) = Yx bildet.

1. Schritt:

Alice wählt eine Zahl A für sich und hält sie geheim. Als Beispiel nehmen wir A=3. Auch Bob entscheidet sich für eine Zahl, z.B. B=6. Auch diese wird geheim gehalten.

2. Schritt:

Alice setzt ihre Zahl A in die Funktion ein und rechnet dann 7A: 73=343 Bob setzt seine gewählte Zahl B in diese Funktion und berechnet das Ergebnis von 7B: 76=117649

3. Schritt:

Alice hat das Ergebnis α=343, Bob das Ergebnis β=117649
Beide schicken sich diese Ergebnisse über das Telefon o.ä.
Jetzt besteht die Gefahr, dass Eve ihr Gespräch abhören kann und so wichtige Daten erfährt. Mit unseren Gleichungen, die wir verwenden ist dies sicherlich möglich, da wir zu Demonstrationszwecken einfachere Gleichungen verwendet haben. Jedoch werden wir nach der Dokumentation des Verfahrens noch gewisse 'Einwegfunktionen' vorstellen, mit der Eve nur sehr schwer auf die Ursprünglich verwendeten Zahlen schließen kann. Doch dazu später.

4. Schritt

Alice nimmt nun Bobs Ergebnis β=117649 als Basis ihrer Gleichung und berechnet dann β3 = 1628413597910449.
Bob nimmt nun Alices Ergebnis α=343 als Basis ihrer Gleichung und berechnet dann α6 = 1628413597910449.
Beide haben sich den gleichen Schlüssel errechnet!

Abhörsicherheit

Nun kann man ja, wie oben schon beschrieben, wenn man die Basis und das Ergebnis einer Gleichung xn = p weiß, ganz einfachdurch logxP auf n schließen. Um dies zu verhindern verwendet man bei Diffie-Hellman "Einwegfunktionen", d.h. Funktionen, die man leicht ausführen, aber nicht oder nur sehr schwer umkehren kann.
Viele Beispiele dafür kommen aus der Modul-Arithmetik, wo "endliche Gruppen" von Zahlen untersucht werden, die "auf einer Schleife oder auch Uhr angeordnet sind:



Weitere Beispiele, natürlich mit veränderter Uhr: 
 z.B. : (2*6)   mod 10 = 2  (Rest von ((2*6)/10))
 oder : (3*7)   mod 6  = 3  (Rest von ((3*7)/6))
 oder : (3*3*3) mod 4  = 1  (Rest von ((3*3*3)/4))
Diese Funktionsvorschriften sind einfach auszuführen. Wenn man aber nur das Ergebnis weiß und das Modul, kann man nicht eindeutig sagen, welche Zahlen in der Klammer stehen.

Beispiel:
Es gibt ein X und ein Y für das gilt: (X*Y) mod 10 = 5. Welche WErte können X und Y annehmen?

X und Y können zum Beispiel 5 sein, oder X=5 Y=7 usw. Wir sehen, wir können keine eindeutige Lösung herausbekommen.

Ein weiteres Plus ist die Unstetigkeit der Ergebnisse. Bei einer "normalen" Funktion z.B. der Form f(x) = 3x können wir sicher sein, dass mit steigendem x auch f(x) größer wird.
Dies ist nicht so, wenn wir die gleiche Funktion benutzen und sie durch modulo 7 teilen:



Nehmen wir nun eine solche Funktion aus der Modul-Arithmetik der Form f(x) = Yx mod P; Y<P, dann können wir auch den Schlüssel sicher übertragen, da niemand (z.B. Eve) bei sehr großen Zahlen in der Lage ist, diese Funktion umzukehren.

Vorgehen mit einer Gleichung aus der Modul-Arithmetik



Quellen:
Geheime Botschaften, Simon Singh, dtv-Verlag, ISBN 3-423-33071-6