Zum Inhalt springen

Diffie-Hellman-Schlüsselaustausch

Aus FLBK-Wiki
Version vom 15. November 2026, 07:44 Uhr von Flbkwikiadmin (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „Zwei Partner, die sich nie getroffen haben, wollen verschlüsselt kommunizieren. Jeder kann ihre Leitung abhören. Mit dem Diffie-Hellman-Schlüsselaustausch vereinbaren sie trotzdem einen Schlüssel, den kein Mithörer kennt. ==Definition== Der '''Diffie-Hellman-Schlüsselaustausch''' (kurz Diffie-Hellman-Verfahren) ist ein Verfahren, mit dem zwei Partner über einen öffentlichen Kanal einen gemeinsamen geheimen Schlüssel vereinbaren. Whitfield Diffie…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Zwei Partner, die sich nie getroffen haben, wollen verschlüsselt kommunizieren. Jeder kann ihre Leitung abhören. Mit dem Diffie-Hellman-Schlüsselaustausch vereinbaren sie trotzdem einen Schlüssel, den kein Mithörer kennt.

Definition

Der Diffie-Hellman-Schlüsselaustausch (kurz Diffie-Hellman-Verfahren) ist ein Verfahren, mit dem zwei Partner über einen öffentlichen Kanal einen gemeinsamen geheimen Schlüssel vereinbaren. Whitfield Diffie und Martin Hellman haben es 1976 veröffentlicht. Der vereinbarte Schlüssel dient anschließend als Schlüssel eines symmetrischen Verfahrens. Das Verfahren selbst verschlüsselt keine Nachricht.

Es löst das Schlüsselverteilungsproblem: Der Schlüssel wird nie übertragen, sondern von beiden Partnern berechnet.

Die Bezeichnungen:

  • öffentlich: eine Primzahl [math]\displaystyle{ p }[/math] und eine Basis [math]\displaystyle{ g }[/math] mit [math]\displaystyle{ 1 < g < p }[/math]
  • geheim: die Zahl [math]\displaystyle{ a }[/math] von Alice und die Zahl [math]\displaystyle{ b }[/math] von Bob
  • öffentlich: die Teilschlüssel [math]\displaystyle{ A }[/math] und [math]\displaystyle{ B }[/math]
  • geheim: der gemeinsame Schlüssel [math]\displaystyle{ K }[/math]

Ablauf

Ablauf als Sequenzdiagramm
  1. Alice und Bob einigen sich öffentlich auf eine Primzahl [math]\displaystyle{ p }[/math] und eine Basis [math]\displaystyle{ g }[/math].
  2. Alice wählt eine geheime Zahl [math]\displaystyle{ a }[/math], Bob eine geheime Zahl [math]\displaystyle{ b }[/math], beide zwischen 2 und [math]\displaystyle{ p - 2 }[/math].
  3. Alice berechnet ihren Teilschlüssel [math]\displaystyle{ A = g^a \bmod p }[/math], Bob seinen Teilschlüssel [math]\displaystyle{ B = g^b \bmod p }[/math].
  4. Alice sendet [math]\displaystyle{ A }[/math] an Bob, Bob sendet [math]\displaystyle{ B }[/math] an Alice. Beide Werte dürfen mitgelesen werden.
  5. Alice berechnet [math]\displaystyle{ K = B^a \bmod p }[/math], Bob berechnet [math]\displaystyle{ K = A^b \bmod p }[/math].

Beide erhalten denselben Wert [math]\displaystyle{ K }[/math]. Wie man die Potenzen berechnet, erklären die Artikel Modulo und Square-and-Multiply.

Das Verfahren lässt sich mit dem Mischen von Farben vergleichen: Zwei Farben zu mischen ist leicht, eine Mischung wieder in ihre Bestandteile zu zerlegen gelingt nicht.

Vergleich mit dem Mischen von Farben

Korrektheit

Alice und Bob berechnen denselben Schlüssel. Das folgt aus den Potenzgesetzen, hier für die Basis [math]\displaystyle{ g }[/math] und zwei natürliche Zahlen [math]\displaystyle{ u }[/math] und [math]\displaystyle{ v }[/math] als Exponenten,

[math]\displaystyle{ (g^u)^v = g^{u \cdot v} \quad \text{und} \quad g^u \cdot g^v = g^{u + v} }[/math]

und aus den Rechenregeln für Reste: Beim Multiplizieren darf man jederzeit zu den Resten übergehen. Der Teilschlüssel [math]\displaystyle{ B }[/math] lässt bei der Division durch [math]\displaystyle{ p }[/math] denselben Rest wie [math]\displaystyle{ g^b }[/math], der Teilschlüssel [math]\displaystyle{ A }[/math] denselben wie [math]\displaystyle{ g^a }[/math]. Deshalb gilt

[math]\displaystyle{ B^a \equiv (g^b)^a = g^{b \cdot a} = g^{a \cdot b} = (g^a)^b \equiv A^b \pmod{p} }[/math]

Beide Potenzen lassen also denselben Rest:

[math]\displaystyle{ B^a \bmod p = A^b \bmod p }[/math]

Sicherheit

Ein Mithörer kennt [math]\displaystyle{ p }[/math], [math]\displaystyle{ g }[/math], [math]\displaystyle{ A }[/math] und [math]\displaystyle{ B }[/math]. Der einzige bekannte Weg zum Schlüssel [math]\displaystyle{ K }[/math] führt über eine der geheimen Zahlen [math]\displaystyle{ a }[/math] oder [math]\displaystyle{ b }[/math]. Dazu müsste der Mithörer die Gleichung [math]\displaystyle{ A = g^a \bmod p }[/math] nach [math]\displaystyle{ a }[/math] auflösen. Diese Aufgabe heißt diskreter Logarithmus.

  • Einwegfunktion: Die Potenz [math]\displaystyle{ g^a \bmod p }[/math] lässt sich auch bei sehr großen Zahlen schnell berechnen, nämlich mit dem wiederholten Quadrieren und Multiplizieren (siehe Square-and-Multiply). Für die Umkehrung, den diskreten Logarithmus, ist bei sehr großen Zahlen kein Verfahren bekannt, das in vertretbarer Zeit zum Ziel kommt.
  • Kleine Zahlen sind unsicher: Bei kleinem [math]\displaystyle{ p }[/math] probiert der Angreifer alle Exponenten durch.
  • Große Zahlen: Für den diskreten Logarithmus gibt es Verfahren, die viel schneller sind als das Durchprobieren aller Exponenten. Deshalb muss [math]\displaystyle{ p }[/math] viel größer sein, als es das Durchprobieren allein verlangt. Das Bundesamt für Sicherheit in der Informationstechnik (BSI) empfiehlt für [math]\displaystyle{ p }[/math] eine Länge von mindestens 3000 Bit, das sind rund 900 Dezimalstellen (Technische Richtlinie TR-02102-1, Version 2026-01). Bei dieser Größe brauchen auch die schnelleren Verfahren viel zu lange.
  • Wahl der Basis: Die Basis [math]\displaystyle{ g }[/math] soll beim Potenzieren möglichst viele verschiedene Reste erzeugen. Ungeeignet sind zum Beispiel [math]\displaystyle{ g = 1 }[/math] und [math]\displaystyle{ g = p - 1 }[/math].
  • Wahl der geheimen Zahlen: Die geheimen Zahlen werden zufällig gewählt und liegen zwischen 2 und [math]\displaystyle{ p - 2 }[/math]. Mit der geheimen Zahl 1 wäre der Teilschlüssel gleich [math]\displaystyle{ g }[/math]. Mit [math]\displaystyle{ p - 1 }[/math] wäre er bei jeder Basis 1: Weil [math]\displaystyle{ p }[/math] eine Primzahl ist, ist jede Basis [math]\displaystyle{ g }[/math] mit [math]\displaystyle{ 1 < g < p }[/math] zu [math]\displaystyle{ p }[/math] teilerfremd, und es gilt [math]\displaystyle{ \varphi(p) = p - 1 }[/math]. Nach dem Satz von Euler ist deshalb [math]\displaystyle{ g^{p-1} \equiv 1 \pmod{p} }[/math].
  • Kein Schutz vor einem aktiven Angreifer: Das Verfahren prüft nicht, von wem ein Teilschlüssel stammt. Das nutzt der Man-in-the-Middle-Angriff aus. Abhilfe schaffen digitale Signaturen und Zertifikate.

Beispiele

Schlüssel mit kleinen Zahlen vereinbaren

Alice und Bob einigen sich öffentlich auf [math]\displaystyle{ p = 23 }[/math] und [math]\displaystyle{ g = 5 }[/math].

Alice wählt geheim [math]\displaystyle{ a = 7 }[/math] und berechnet ihren Teilschlüssel [math]\displaystyle{ A = 5^{7} \bmod 23 }[/math] Schritt für Schritt. Nach jeder Multiplikation bildet sie den Rest modulo 23:

[math]\displaystyle{ 5^{1} = 5 }[/math]
[math]\displaystyle{ 5^{2} \equiv 5 \cdot 5 = 25 \equiv 2 }[/math]
[math]\displaystyle{ 5^{3} \equiv 2 \cdot 5 = 10 }[/math]
[math]\displaystyle{ 5^{4} \equiv 10 \cdot 5 = 50 \equiv 4 }[/math]
[math]\displaystyle{ 5^{5} \equiv 4 \cdot 5 = 20 }[/math]
[math]\displaystyle{ 5^{6} \equiv 20 \cdot 5 = 100 \equiv 8 }[/math]
[math]\displaystyle{ 5^{7} \equiv 8 \cdot 5 = 40 \equiv 17 }[/math]

Also ist [math]\displaystyle{ A = 17 }[/math].

Bob wählt geheim [math]\displaystyle{ b = 8 }[/math] und berechnet ebenso [math]\displaystyle{ B = 5^{8} \bmod 23 = 16 }[/math].

Beide tauschen [math]\displaystyle{ A = 17 }[/math] und [math]\displaystyle{ B = 16 }[/math] über den öffentlichen Kanal aus.

Alice berechnet [math]\displaystyle{ K = B^a \bmod p = 16^{7} \bmod 23 }[/math]:

[math]\displaystyle{ 16^{1} = 16 }[/math]
[math]\displaystyle{ 16^{2} \equiv 16 \cdot 16 = 256 \equiv 3 }[/math]
[math]\displaystyle{ 16^{3} \equiv 3 \cdot 16 = 48 \equiv 2 }[/math]
[math]\displaystyle{ 16^{4} \equiv 2 \cdot 16 = 32 \equiv 9 }[/math]
[math]\displaystyle{ 16^{5} \equiv 9 \cdot 16 = 144 \equiv 6 }[/math]
[math]\displaystyle{ 16^{6} \equiv 6 \cdot 16 = 96 \equiv 4 }[/math]
[math]\displaystyle{ 16^{7} \equiv 4 \cdot 16 = 64 \equiv 18 }[/math]

Bob berechnet [math]\displaystyle{ K = A^b \bmod p = 17^{8} \bmod 23 = 18 }[/math].

Beide erhalten den gemeinsamen Schlüssel [math]\displaystyle{ K = 18 }[/math], obwohl er nie übertragen wurde.

Geheime Zahl durch Probieren ermitteln

Eve hat [math]\displaystyle{ p = 23 }[/math], [math]\displaystyle{ g = 5 }[/math], [math]\displaystyle{ A = 17 }[/math] und [math]\displaystyle{ B = 16 }[/math] mitgelesen. Bei so kleinen Zahlen probiert sie alle Exponenten durch:

[math]\displaystyle{ x }[/math] 1 2 3 4 5 6 7 8 9 10 11
[math]\displaystyle{ 5^x \bmod 23 }[/math] 5 2 10 4 20 8 17 16 11 9 22
[math]\displaystyle{ x }[/math] 12 13 14 15 16 17 18 19 20 21 22
[math]\displaystyle{ 5^x \bmod 23 }[/math] 18 21 13 19 3 15 6 7 12 14 1

Der Wert 17 steht bei [math]\displaystyle{ x = 7 }[/math], also ist [math]\displaystyle{ a = 7 }[/math]. Damit berechnet Eve den Schlüssel wie Alice: [math]\displaystyle{ K = 16^{7} \bmod 23 = 18 }[/math].

Bei einer Primzahl mit mehreren hundert Stellen ist diese Tabelle viel zu lang: Das Durchprobieren würde länger dauern, als das Universum alt ist.