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:

a,b,K sind privat; g,p,A,B sind öffentlich

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 Zahl aus: a = 5. (a muss kleiner als p sein)	---	Bob denkt sich eine geheime Zahl aus: b = 8. (b muss kleiner als p sein.)
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!	---

Taschenrechner / Online-Rechner

Mit dem Casio-Taschenrechner kommt man am einfachsten so zum Modulo-Rechnen:

• OPTN -> F6 -> F4 -> F6 -> F4
• Eingabe dann z.B.: MOD(27,6)
  Dann müsste 3 rauskommen.

Der Taschenrechner hat allerdings Probleme, modulo für große Zahlen zu berechnen.

Das kann man VIEL BESSER online machen!

Folgende Online-Rechner sind geeignet:

• web2.0rechner.de.
  (Modulo ist 2nd ÷ )

• [1]
  Den braucht man, wenn auch der web2.0rechner überfordert ist, z.B. für 123456789^123456789 mod 987654321
  allgemein: Basis ^ Exponent mod Modulo
  

• Primitiv-Wurzel-Rechner
  Zum Suchen von Primitivwurzeln.

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

Man-In-The-Middle-Attack auf Diffie-Hellman

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

D.h. wenn sich Mallory unbemerkt in den Schlüsselaustausch "einklinkt", indem sie Alice vorspiegelt, sie sei Bob und Bob vorspiegelt, sie sei Alice, dann kann Mallory 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 dem bösen Mallory vereinbart!)

Details dazu bei wikipedia

Veranschaulichung: Mischen von Farben

Das Diffie-Hellman-Verfahren wird häufig durch ein Farbmisch-Verfahren veranschaulicht.