Der Diffie-Hellman-Schlüsselaustausch erklärt
Jahrtausendelang bedeutete das Senden einer geheimen Nachricht, zuerst einen geheimen Schlüssel persönlich oder per Kurier auszutauschen. 1976 zeigten zwei Forscher in Stanford, dass zwei Parteien einen gemeinsamen Schlüssel aus dem Nichts erzeugen können, indem sie vor aller Augen Nachrichten austauschen. Die Idee eröffnete das Zeitalter der Public-Key-Kryptografie und ist noch immer jedes Mal am Werk, wenn ein Browser ein Vorhängeschloss anzeigt.
Das Problem der Schlüsselverteilung
Eine Verschlüsselung wie AES ist nur so sicher wie ihr Schlüssel, und beide Seiten brauchen denselben Schlüssel. Vor 1976 musste der Schlüssel geheim überbracht werden: im Diplomatengepäck, durch vertrauenswürdige Kuriere oder mit vorab gedruckten Codebüchern. Für zwei Fremde, die sofort sicher miteinander kommunizieren wollen, etwa einen Shop und einen Kunden im Internet, ist das unmöglich. Whitfield Diffies und Martin Hellmans Aufsatz „New Directions in Cryptography“ löste das Problem mit einem Verfahren, das überhaupt kein vorher geteiltes Geheimnis braucht.
Rechnen auf einer Uhr
Der Austausch nutzt modulare Arithmetik: Rechnungen auf einer Uhr mit p Stunden, wobei p eine große Primzahl ist. Potenzen verhalten sich auf dieser Uhr bemerkenswert. Ist g eine Primitivwurzel, springen die Zahlen g, g², g³, … mod p umher und besuchen jede Stunde von 1 bis p − 1, bevor sie sich wiederholen, in einer Reihenfolge, die zufällig wirkt. gᵃ mod p zu berechnen geht schnell, mit etwa so vielen Multiplikationen, wie a Binärstellen hat. Die Umkehrung nicht.
Der Austausch Schritt für Schritt
Alice und Bob vereinbaren offen p und g. Alice wählt ein Geheimnis a und sendet A = gᵃ mod p; Bob wählt ein Geheimnis b und sendet B = gᵇ mod p. Alice berechnet Bᵃ = (gᵇ)ᵃ und Bob berechnet Aᵇ = (gᵃ)ᵇ, beides mod p. Da die Reihenfolge der Exponenten keine Rolle spielt, erhalten beide g^(ab) mod p. Im klassischen kleinen Beispiel mit p = 23, g = 5, a = 6 und b = 15 sendet Alice 8, Bob sendet 19, und beide gelangen zum gemeinsamen Geheimnis 2.
Das Problem des diskreten Logarithmus
Eve sieht p, g, A und B. Könnte sie a aus A = gᵃ mod p bestimmen, könnte sie das Geheimnis genauso berechnen wie Alice. Das ist das Problem des diskreten Logarithmus. Die besten bekannten klassischen Algorithmen, etwa das Zahlkörpersieb, sind weit schneller als das Ausprobieren jedes Exponenten, brauchen aber immer noch eine Zeit, die schneller wächst als jede Potenz der Stellenzahl. Bei Primzahlen mit 2048 Bit ist das Problem für jeden existierenden Computer außer Reichweite. Ob etwas Schnelleres möglich ist, ist unbekannt, und die Sicherheit des Austauschs beruht auf dieser Annahme.
Man-in-the-Middle
Diffie-Hellman schützt vor einem Lauscher, aber nicht vor einem Betrüger. Mallory, der zwischen Alice und Bob sitzt, kann mit jedem der beiden einen eigenen Austausch durchführen und die Nachrichten weiterreichen, wobei er alles mitliest. Die Abwehr ist Authentifizierung: Bei HTTPS signiert der Server seinen Teil des Austauschs mit einem Schlüssel, der von einer vertrauenswürdigen Stelle zertifiziert ist, sodass der Browser weiß, dass er wirklich mit der richtigen Website spricht. Schlüsselaustausch und Signaturen gehören immer zusammen.
Wer hat es erfunden?
Diffie und Hellman veröffentlichten 1976 und bauten dabei auf Ideen von Ralph Merkle auf, für den Hellman später ebenfalls Anerkennung forderte. 1997 enthüllte der britische Nachrichtendienst GCHQ, dass seine Mathematiker zuerst darauf gekommen waren: James Ellis hatte 1970 die Idee der Public-Key-Kryptografie, Clifford Cocks fand 1973 ein RSA-ähnliches System, und Malcolm Williamson entdeckte 1974 denselben Schlüsselaustausch, alles über zwanzig Jahre lang geheim gehalten.
Diffie-Hellman heute
Moderne Verbindungen nutzen meist Diffie-Hellman auf elliptischen Kurven, das dieselbe Sicherheit mit viel kürzeren Zahlen bietet, zum Beispiel die Kurve X25519 in TLS 1.3, Signal und WhatsApp. Ein frisches Paar von Geheimnissen für jede Verbindung sorgt für Forward Secrecy: Selbst wenn der langfristige Schlüssel eines Servers später gestohlen wird, bleiben vergangene Gespräche sicher. Schwache Parameter bleiben eine Gefahr, wie der Logjam-Angriff von 2015 für alte 512-Bit-Primzahlen zeigte, und ein großer Quantencomputer mit Shors Algorithmus würde sowohl klassisches Diffie-Hellman als auch Diffie-Hellman auf elliptischen Kurven brechen, weshalb inzwischen Post-Quanten-Schlüsselaustauschverfahren parallel dazu eingeführt werden.
Selbst ausprobieren
Öffnen Sie die Diffie-Hellman-Visualisierung, um die fünf Schritte auf einer Tafel zu verfolgen, die zeigt, was Alice, der öffentliche Kanal und Bob wissen, als Farbe und als Zahlen. Wählen Sie Primzahlen von 23 bis 2.147.483.647, legen Sie die Geheimnisse selbst fest und lassen Sie Eve angreifen, indem sie jeden Exponenten ausprobiert: Sehen Sie zu, wie sie bei kleinen Primzahlen sofort Erfolg hat, und wie die geschätzte Suchzeit wächst, je länger die Primzahl wird.
Häufig gestellte Fragen
Ist Diffie-Hellman dasselbe wie RSA?
Nein, obwohl beides Public-Key-Verfahren aus den 1970er-Jahren sind. RSA, 1977 veröffentlicht, kann mit einem öffentlichen und einem privaten Schlüssel verschlüsseln und signieren und beruht auf der Schwierigkeit, große Zahlen zu faktorisieren. Diffie-Hellman vereinbart nur ein gemeinsames Geheimnis und beruht auf dem Problem des diskreten Logarithmus.
Wie groß sind die Zahlen in der Praxis?
Klassisches Diffie-Hellman verwendet Primzahlen mit mindestens 2048 Bit, etwa 617 Dezimalstellen, oft auch 3072 oder 4096 Bit. Varianten mit elliptischen Kurven verwenden für vergleichbare Sicherheit Schlüssel mit etwa 256 Bit.
Warum verdoppelt jedes zusätzliche Bit Eves Aufwand?
Eine Primzahl mit einem Bit mehr ist etwa doppelt so groß, also gibt es etwa doppelt so viele Exponenten auszuprobieren. Echte Angriffe sind raffinierter als das Ausprobieren jedes Exponenten, aber ihre Kosten wachsen trotzdem sehr schnell mit der Größe der Primzahl.
Warum brauchen Alice und Bob eine Primzahl?
Bei einem Primzahlmodul hat jede Zahl von 1 bis p − 1 ein Inverses, und es gibt Primitivwurzeln, sodass die Potenzen von g alle Möglichkeiten abdecken. Oft wählt man sichere Primzahlen, bei denen auch (p − 1)/2 eine Primzahl ist, um Abkürzungen auszuschließen, die kleine Faktoren von p − 1 ausnutzen.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Diffie-Hellman-Visualisierung öffnen