Diffie-Hellman-Merkle-Schlüsselaustausch

Die klassische Kryptografie benutzt die symmetrische Verschlüsselung, d. h. das Sender und Empfänger den selben Schlüssel zum Ver- und Entschlüsseln benutzen.

Das Problem dabei ist, dass außer der Nachricht auch der Schlüssel an den Empfänger übergeben werden muss. Geschieht dies nicht auf sicherem Wege, dann ist die gesamte davon abhängige Kommunikation kompromittiert und der Feind die Geheimnachrichten entschlüsseln, und dies ohne das Wissen von Sender oder Empfänger, die dann in gutem Glauben den Schlüssel weiter benutzen.

Man muss also in ständiger Furcht leben, dass dem Feind der Schlüssel eventuell bereits in die Hände gefallen ist, sei es durch Einflussnahme auf einen Wissenden (z. B. durch Bestechung, Erpressung oder Folter) oder durch Finden eines Codebuches. Dieses Risiko kann man nur durch häufigen Austausch des Schlüssels verringern, was auf der anderen Seite allerdings jedesmal die Gefahr birgt, dass der Schlüssel auf dem Transport abgefangen wird.

Wie kann man diesem Dilemma begegnen? Die Idee, den Schlüssel verschlüsselt zu übertragen, führt zu nichts, denn den dafür nötigen Schlüssel müsste man ja ebenfalls übertragen. Hier beißt sich die Katze in den Schwanz.

Die einzige Lösungsmöglichkeit wäre es, auf die Übertragung eines Schlüssels zu verzichten. Aufbauend auf den nach Ralph Merkle benannten Puzzles hatten Whitfield Diffie und Martin Hellman eine Idee, der sie 1976 als das sogenannte Diffie-Hellman-Schlüsselaustausch-Verfahren veröffentlichen. Dabei chiffriert der Sender den Geheimtext mit seinem eigenen Schlüssel S, den er für sich behält. Das Chiffrat Chiff(Text,S) sendet er dann an den Empfänger, der das Erhaltene mit seinem Schlüssel E (den er ebenfalls für sich behält) verschlüsselt, was das Doppelchiffrat Chiff(Chiff(Text,S),E) ergibt, das er zurück an den Sender schickt. Der Sender wendet jetzt die Dechiffriermethode mit seinem Schlüssel S an, was dann einen nur noch mit dem Schlüssel des Empfängers E verschlüsseltes Chiffrat ergeben soll: Dechiff(Chiff(Chiff(Text,S),E),S) --> Chiff(Text,E), welches er wieder an den Empfänger schickt. Da das Paket jetzt nur noch mit dem Schlüssel des Empfängers verschlüsselt ist, kann dieser es mit seinem Schlüssel E dechiffrieren: Dechiff(Chiff(Text,E),E) -> Text.

Crux bei der Sache ist allerdings, dass das Verfahren für die Verschlüsselung so gestaltet sein müsste, dass es egal ist, in welcher Reihenfolge man die Schlüssel anwendet. Denn normalerweise müssen bei allen Verschlüsselungsverfahren bei einer Mehrfachverschlüsselung die Schlüssel für eine Entschlüsselung in umgekehrter Reihenfolge angewendet werden wie bei der Verschlüsselung: wenn ich Box A in Box B packe, muss ich zuerst Box B auspacken, bevor ich an Box A komme. Box A zu öffnen, ohne vorher Box B zu öffnen, geht nicht (Box-in-Box-Problem). Es musste ein mathematisches Verfahren gefunden werden, dass dies ermöglicht.

Und dieses Verfahren muss es gleichzeitig einem Angreifer (Mallory) unmöglich machen, aus den Informationen, die er zwischen Sender (Alice) und Empfänger (Bob) abhört, den Klartext zu gewinnen. Dieses Zurückrechnen ist allerdings möglich in all den Fällen, in denen das Box-in-Box-Problem nicht zutrifft, wie folgendes Beispiel eines Schlüsselaustausches via XOR zeigt: v = abhörbar von Mallory Klartext: 1001 1101 1100 0101 + Key A: 1010 1010 1001 0011 Alice verschlüsselt Klartext mit Key A (nur Alice bekannt) = Chiff(A) 0011 0111 0101 0110 X überträgt Chiff(A) an Bob + Key B: 0100 0011 1100 1010 Bob verschlüsselt Chiff(A) mit Key B (nur Bob bekannt) = Chiff(A,B) 0111 0100 1001 1100 X überträgt Chiff(A,B) zurück an Alice - Key A: 1010 1010 1001 0011 Alice rechnet aus Chiff(A,B) Key A (nur Alice bekannt) heraus = Chiff(B) 1101 1110 0000 1111 X überträgt Chiff(B) an Bob - Key B: 0100 0011 1100 1010 = Klartext: 1001 1101 1100 0101 Zum einen kann Alice auch Bobs Schlüssel errechnen (und Bob Alices), weil Alice das Chiffrat Chiff(A,B) sowie der eigene Schlüssel bekannt ist: Chiff(A,B) 0111 0100 1001 1100 XOR Key A 1010 1010 1001 0011 = Chiff B 1101 1110 0000 1111 XOR Klartext 1001 1101 1100 0101 = Key B 0100 0011 1100 1010 Aber was viel schlimmer ist und das Verfahren uneinsetzbar macht, ist die Tatsache, dass auch Mallory den Klartext errechnen kann: Chiff(A) 0011 0111 0101 0110 XOR Chiff(A,B) 0111 0100 1001 1100 = Key B 0100 0011 1100 1010 XOR Chiff B 1101 1110 0000 1111 = Klartext 1001 1101 1100 0101 Wenn man nun weder eine umkehrbare Chiffrierfunktion wegen der fehlenden Sicherheit noch eine nicht umkehrbare Chiffrierfunktion wegen des Box-in-Box-Problems einsetzen kann, wie kann man das Dilemma dann lösen? Die Antwort lautet: indem man eine Einbahnstraßenfunktion einsetzt: das ist etwas, was in eine Richtung schnell zu berechnen ist, aber dessen Umkehrung schwierig und langwierig zu berechnen ist.

Der Diffie-Hellman-Schlüsselaustausch funktioniert wie folgt: Sender und Empfänger einigen sich auf eine Primzahl P und eine natürliche Zahl N, die kleiner als P ist. Dabei kann diese Einigung ruhig durch einen Angreifer belauscht werden, da dieser aus diesem Wissen kein Nutzen ziehen können würde. Dann wählen Sender und Empfänger jeweils eine eigene Zahl, die sie für sich behalten und die kleiner P ist. Der Sender also eine Zahl S und der Empfänger eine Zahl E.

Nun berechnet der Sender die Zahl A nach der Formel A=N^E mod P und der Empfänger B=N^E mod P. Diese Berechnung stellt eine sogenannte Einwegfunktion dar, da die Berechnung in eine Richtung schnell und effizient geschehen kann, in die andere aber nicht oder nur mit untragbarem Aufwand. Ein Zurückrechnen ist also nicht möglich; es sei denn, man hat einen der geheimen Schlüsselteile, was den Aufwand ganz erheblich verringert. Die so berechneten Zahlen A und B werden wieder ausgetauscht.

Jetzt verfügt der Sender über P, N, A, B sowie S und der Empfänger über P, N, A, B sowie E. Ein mitlauschender Angreifer verfüge maximal über P, N, A und B.
Der Sender kann berechnen: K₁ = B^S mod P.
Der Empfänger kann berechnen: K₂ = A^E mod P.
Ein Angreifer geht leer aus, denn er kennt weder S noch E. Und alle Potenzen der Reihe nach durchzuprobieren würde untragbar lange dauern, den potenzieren ist rechenaufwendig.

K₁ ist gleich K₂ und der Schlüssel, den Sender und Empfänger gemeinsam für eine symmetrische Verschlüsselung verwenden.

Später wurde von Ronald L. Rivest, Adi Shamir und Leonard Adleman das RSA-Verfahren entwickelt, welches die anschließende symmetrische Verschlüsselung wegfallen lässt und mit zwei Schlüsseln (Private und Public Key) arbeitet und direkt verschlüsselt. Damit kann auf das Prozedere einer Schlüsseleinigung verzichtet werden, was RSA einfacher und schneller macht.

Quellen, Literaturverweise und weiterführende Links

Singh, Simon: Geheime Botschaften, Hanser Verlag 2000, S. 309
Kippenhahn, Rudolf: Verschlüsselte Botschaften, Nikol Verlag 2006, S. 270
Bauer, Friedrich L.: Entzifferte Geheimnisse, Springer Verlag 1995, S. 155
Gómez, Joan: Geheimsprachen und Decodierung, Librero Verlag 2016, S. 100
Beutelspacher, Albrecht: Geheimsprachen - Geschichte und Techniken, C. H. Beck Verlag, 2002, S. 52
Beutelspacher, Neumann und Schwarzpaul: Kryptografie in Theorie und Praxis, Vieweg Verlag 2005, S. 134-139
Ertel, Wolfgang: Angewandte Kryptographie, Hanser Verlag 2012, S. 91
Beutelspacher, Albrecht: Kryptologie - Eine Einführung..., Springer Spektrum Verlag 2015, S. 143
Schmeh, Klaus: Kryptografie: Verfahren - Protokolle - Infrastrukturen, dpunkt Verlag, 5. Auflage 2013, iX-Edition, S. 185
Kuhn, Nico: Das Buch der geheimen Verschlüsselungstechniken, Data Becker Verlag 2009, S. 103