Diffie-Hellmann-Schlüsseltausch

Der Diffie-Hellmann-Schlüsseltausch ermöglicht es zwei Kommunikationspartnern einen geheimen Schlüssel zu vereinbaren.

Das Besondere dabei ist, dass mögliche Angreifer die gesamte Kommunikation mithören können, aber trotzdem nicht an den Schlüssel kommen.

Verfahren

Die beiden Kommunikationspartner (Alice und Bob) einigen sich auf eine Primzahl p und eine Primitivwurzel g modulo p.

Diese beiden Zahlen können öffentlich sein, d.h. auch mögliche Angreifer (Eve) dürfen sie erfahren.

Jetzt läuft das Verfahren wie folgt ab:

Alice	Kommunikation (belauscht von Eve!)	Bob
---	Alice und Bob einigen sich auf p und g	---
Alice denkt sich eine geheime Zahl a aus. (a muss kleiner als p sein.)	---	Bob denkt sich eine geheime Primzahl b aus. (b muss kleiner als p sein.)
Alice berechnet A = ga mod p	---	Bob berechnet B = gb mod p
---	Alice schickt A an Bob. Bob schickt B an Alice.	---
Alice berechnet K = Ba mod p und hat den Schlüssel K!	---	Bob berechnet K = Ab mod p und hat ebenfalls den Schlüssel K!
---	Eve kann aus p, g, A und B den Schlüssel K nicht berechnen!	---

Beispiel

Alice	Kommunikation (belauscht von Eve!)	Bob
---	Alice und Bob einigen sich auf p = 13 und g = 2	---
Alice denkt sich eine geheime Primzahl aus: a = 5.	---	Bob denkt sich eine geheime Primzahl b = 8.
Alice berechnet A = ga mod p A = 25 mod 13 = 32 mod 13 = 6	---	Bob berechnet B = gb mod p B = 28 mod 13 = 256 mod 13 = 9
---	Alice schickt A = 6 an Bob. Bob schickt B = 9 an Alice.	---
Alice berechnet K = Ba mod p K = 95 mod 13 = 59049 mod 13 = 3 und hat den Schlüssel K = 3!	---	Bob berechnet K = Ab mod p K = 6^8 mod 13 = 1679616 mod 13 = 3 und hat den Schlüssel K = 3!
---	Eve kann aus p = 13, g = 2, A = 6 und B = 9 den Schlüssel K nicht berechnen!	---

Warum funktioniert das?

• Alices Berechnug für K ist: K = B^a mod p = (g^b)^a mod p = g^ab mod p
• Bobs Berechnung für K ist: K = A^b mod p = (g^a)^b mod p = g^ba mod p = g^ab mod p
• Also haben Alice und Bob den gleichen Schlüssel!

Allgemeine Anforderungen an die Verschlüsselungsfunktion

Allgemein gesprochen muss die Verschlüsselungsfunktion kommutativ sein, d.h. f_a(f_b(x)) = f_b(f_a(x)).

Das ist wichtig, damit Alice und Bob den gleichen Schlüssel erhalten!

Die Exponentialfunktion modulo p ist kommutativ, wie oben gezeigt.

Außerdem muss die Verschlüsselungsfunktion eine Einwegfunktion sein, d.h. die Umkehrung der Rechnung muss unmöglich oder mindestens sehr zeitintensiv sein.

Das ist wichtig, damit man nicht aus den öffentlichen Teilen der Kommunikation die privaten Werte von Alice und Bob errechnen kann.

Dass die Exponentialfunktion modulo p eine Einwegfunktion ist, ist mathematisch bewiesen; siehe Warum ist das sicher?

Warum ist das sicher?

• Um aus p, g, A und B den geheimen Schlüssel K (oder die geheimen Primzahlen a und b) zu ermitteln, muss Alice den sog. "diskreten Logarithmus" bilden
  d.h. sie muss eine Zahl x finden, so dass g^x mod p = A.
• Das erfordert für große Zahlen eine sehr lange Rechendauer; man kann sogar angeben, wie groß die Zahlen sein müssen, damit Eve mit aller Rechenleistung der Welt 10 Jahre, 100 Jahre oder 1000 Jahre braucht...

Mehr Details zur Sicherheit bei wikipedia

Praxis

In der Praxis nimmt man für p, g, a und b Zahlen mit mehreren hundert Stellen.

Man-In-The-Middle-Attack

Der Diffie-Hellmann-Schlüsseltausch ist anfällig für die Man-In-The-Middle-Attack.

D.h. wenn sich Eve unbemerkt in den Schlüsselaustausch "einklinkt", indem sie Alice vorspiegelt, sie sei Bob und Bob vorspiegelt, sie sei Alice, dann kann Eve mit jeder Seite einen Schlüssel vereinbaren - und Alice und Bob denken, sie hätten miteinander einen Schlüssel vereinbart. (Dabei haben beide jeweils nur einen Schlüssel mit der bösen Eve vereinbart!)

Details dazu bei wikipedia