Diffie Hellman

Grundlagen

• Der Diffie-Hellman-Schlüsselaustausch ist ein Protokoll zur Schlüsselvereinbarung.
• Es ermöglicht, dass zwei Kommunikationspartner über eine öffentliche, abhörbare Leitung einen gemeinsamen geheimen Schlüssel in Form einer Zahl vereinbaren können, den nur diese kennen und ein potenzieller Lauscher nicht berechnen kann.
• Der dadurch vereinbarte Schlüssel kann anschließend für ein symmetrisches Kryptosystem verwendet werden.
• Unterschiedliche Varianten des Diffie-Hellman-Merkle-Verfahrens werden heute für die Schlüsselverteilung in den Kommunikations- und Sicherheitsprotokollen des Internet eingesetzt.

Prinzip

[Bearbeiten]

Beispiel

Das folgende Beispiel dient zur Veranschaulichung und benutzt deshalb sehr kleine Zahlen. In der tatsächlichen Anwendung werden dagegen Primzahlen mit mindestens mehreren hundert Stellen benutzt.

Berechnung

• Alice legt die beiden öffentlichen Schlüssel $p=13$ und $g=2$ fest.
• p muss auf jeden Fall eine Primzahl sein.
• Alice wählt die Zufallszahl $a=5$ als geheimen Schlüssel.
• Nun berechnet Alice Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A = g^a\ \bmod\ p = 2^5\ \bmod\ 13 = 32 \bmod\ 13 = 6 }
• Alice sendet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g,p,A} an Bob.
• Bob wählt die Zufallszahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b = 8} als geheimen Schlüssel.
• Bob berechnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B = g^b\ \bmod\ p = 2^8\ \bmod\ 13 = 256 \bmod\ 13 = 9}
• Bob sendet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B} an Alice.
• Alice berechnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_1 = B^a\ \bmod\ p = 9^5\ \bmod\ 13 = 59049 \bmod\ 13 = 3} .
• Bob berechnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K_2 = A^b\ \bmod\ p = 6^8\ \bmod\ 13 = 1679616 \bmod\ 13 = 3} .
• Beide erhalten das gleiche Ergebnis $K=K_{1}=K_{2}=3$.

Sicherheit

• Die Lauscherin Eve kann zwar die Zahlen 13, 2, 6 und 9 mithören.
• Das eigentliche gemeinsame Geheimnis von Alice und Bob $K=3$ bleibt ihr aber verborgen.
• $K=3$ kann als Schlüssel für die nachfolgende Kommunikation verwendet werden.

Lauschen

• Mit Hilfe der abgefangenen Nachrichten kann Eve immerhin die folgenden Gleichungen aufstellen:

  $6=2^{a}\ {\bmod {\ }}13$

  $9=2^{b}\ {\bmod {\ }}13$

• Daraus kann sie beispielsweise durch Ausprobieren die beiden geheimen Zahlen $a=5$ und $b=8$ bestimmen.
• Den vereinbarten Schlüssel $K$ von Alice und Bob kann sie nun mit

  $K=g^{ab}\ {\bmod {\ }}p$ berechnen.

• Wenn jedoch die Primzahl $p$ groß genug gewählt wird und $g$
• ein Generator der Gruppe $\mathbb {Z} _{p}^{*}$ ist, ist es für Eve zu aufwändig,
• um alle Zahlen zwischen $1$ und $p-1$ durchzuprobieren,
• die als Resultat der modularen Potenz $g^{a}\ {\bmod {\ }}p$ in Frage kommen.

Perfect Forward Secrecy

• Früher wurden neue Sitzungsschlüssel aus den alten berechnet.
• Das führte zu dem Problem, dass wenn ein Schlüssel geknackt wurde, man den gesamten mitgeschnittenen Datenverkehr entschlüsseln konnte.
• Mittlerweile werden Sitzungsschlüssel mit dem Diffie-Hellman-Verfahren erzeugt.
• Vorteil: Wird ein Sitzungsschlüssel gefunden, kann damit nur ein kleiner Teil des Datenverkehrs entschlüsselt werden.

Script zum berechnen

• Diffie-Hellman-Script

Videos

• Diffie-Hellman principle

https://www.youtube.com/watch?v=NmM9HA2MQGI

• Math part

https://www.youtube.com/watch?v=Yjrfm_oRO0w